1. Fejezet

LINEÁRIS ALGEBRA ÉS POLIÉDEREK

1.1 VEKTORTÉR, ALTÉR, LINEÁRIS FÜGGETLENSÉG

Azt mondjuk, hogy x ≥ y, ha x minden komponense nagyobb vagy egyenlő y megfelelő komponensénél. Amennyiben x ≤ y és x ≠ y, úgy az x < y jelölést használjuk. Amikor x minden komponense szigorúan kisebb az y megfelelő komponensénél, az x ≪ y jelölést használjuk.

Adott x_{1}, …, x_{k} vektorok és λ_{1}, …, λ_{k} számok esetén a b := λ_{1}x_{1} + … + λ_{k}x_{k} vektort az x_{1}, …, x_{k} vektorok egy lineáris kombinációjának nevezzük. Ha a λ_{i} számok összege 1, affin kombinációról beszélünk, ha valamennyi λ_{i} nem-negatív, úgy nem-negatív kombinációról van szó. Egy nem-negatív, affin kombinációt konvex kombinációnak mondunk. Amennyiben a b ≠ 0 elem előáll az x_{1}, …, x_{k} elemek lineáris kombinációjaként, úgy azt mondjuk, hogy b lineárisan függ az x_{1}, …, x_{k} elemektől. Ha b-nek nincs ilyen előállítása, akkor b lineárisan független az x_{1}, …, x_{k} elemektől. A lineáris kombináció triviális, ha mindegyik λ_{i} együttható 0. Ha legalább az egyikük nem-nulla, nemtriviális lineáris kombinációról beszélünk. Azt mondjuk, hogy az x_{1}, …, x_{k} vektorok lineárisan összefüggnek, ha a vektortér nulleleme előáll nem-triviális lineáris kombinációjukként. Ha nincs ilyen előállítás, úgy az x_{1}, …, x_{k} vektorokat lineárisan függetleneknek mondjuk.

Legyen X és Y két vektor-halmaz R^{n}-ben. Ekkor a vektor-összegükön vagy Minkowski összegükön (röviden, összegükön) az X + Y := {x + y : x ∈ X, y ∈ Y } halmazt értjük. A különbségük analóg módon definiálható.

A V vektortér A altere egy olyan nemüres részhalmaza V -nek, amelyre fennáll, hogy (1) x ∈ A ⇒ λx ∈ A minden λ ∈ R számra, és (2) x, y ∈ A ⇒ x + y ∈ A.

Nyilván az egyetlen nulla elemből álló halmaz altér, az ún. triviális altér. Egy altér dimenziója az altérből kiválasztható lineárisan független elemek maximális száma. Két n-dimenziós a = (a_{1}, …, a_{n}), b = (b_{1}, …, b_{n}) vektor skalárszorzata az ab := a_{1}b_{1} + … + a_{n}b_{n} szám. Természetesen ab = ba. Azt mondjuk, hogy a és b ortogonális, ha skalárszorzatuk 0. Az A, B ⊆ V halmazokról azt mondjuk, hogy egymásra ortogonálisak (vagy merőlegesek), ha A mindegyik eleme ortogonális B mindegyik elemére.

Ha x_{1}, …, x_{k} a V vektortér véges sok eleme, akkor a lineáris kombinációjukként előálló elemek halmaza alteret alkot, amit az x_{1}, …, x_{k} elemek által generált altérnek nevezünk. Ez nem más, mint az X := {x_{1}, …, x_{k}} halmazt tartalmazó alterek metszete.

Legyen a ∈ R^{n} nem-nulla vektor. Az a-ra ortogonális elemek {x ∈ R^{n} : ax = 0} halmazát origón átmenő vagy homogén hipersíknak nevezzük, melynek (egyik) normálisa vagy normál vektora a. Amennyiben a az i-dik egységvektor, úgy az a-ra merőleges vektorok halmazát koordináta-hipersíknak hívjuk.

Adott x_{1}, …, x_{k} vektorok mindegyikére ortogonális vektorok halmaza alteret alkot, melyet az x_{1}, …, x_{k} ortogonális kiegészítő alterének nevezünk. Ha az x_{i} vektorok mindegyike valamelyik (0, 0, …, 1, …, 0) alakú egységvektor, úgy ezek ortogonális kiegészítő alterét koordináta-altérnek hívjuk. Egy x pontnak az x_{j} koordináta (vagy tengely) menti vetületét úgy kapjuk, hogy x j-dik komponensét 0-re állítjuk. Valójában ez a belső vetület, megkülönböztetendő a külső vetülettől, amelyet úgy kapunk, hogy az x vektor j-dik komponensét eltöröljük.

Legyenek U és V vektorterek. Azt mondjuk, hogy a φ : U → V leképezés lineáris transzformáció (vagy leképezés), ha (1) x ∈ U, λ ∈ R esetén φ(λx) = λφ(x) és (2) x, y ∈ U esetén φ(x + y) = φ(x) + φ(y).

Az U azon elemeinek halmaza, amelyek a V nulla elemébe képződnek le az U-nak alterét alkotják, amely alteret a φ leképezés magterének neveznek. V azon elemei, amelyek valamely U-beli elem képeként állnak elő (azaz a {φ(u) : u ∈ U} halmaz elemei), a V -nek alterét alkotják, amely alteret a φ leképezés képterének neveznek.

1.2 MÁTRIXOK, EGYENLETRENDSZEREK

Az A mátrix sorterén az R^{n}-nek az A sorai által generált alterét értjük, amelynek jele S(A) vagy R^{m}A. A sortér tehát az {y^{t}A : y ∈ R^{m}} halmaz. Az A mátrix nulltere az A sorainak ortogonális kiegészítő altere, melynek jele N (A). A nulltér tehát az Ax = 0 egyenletrendszer {x ∈ R^{n} : Ax = 0} megoldás-halmaza. Az A oszlopai által generált altér az A oszloptere, jelölésben O(A) vagy AR^{n}, míg az oszlopainak merőleges altere a mátrix bal nulltere. Ennek jele BN (A).

Lemma 1.1 Ha a z ∈ R^{n} nem-nulla vektor ortogonális az A mindegyik sorára (azaz benne van A nullterében, vagyis Az = 0), akkor z lineárisan független az A soraitól, (azaz z nincs benne az A sorterében).

TÉTEL 1.2 Legyen A m×n-es mátrix, ahol 1 ≤ m < n. Ekkor az Az = 0 homogén lineáris egyenletrendszernek létezik nem-triviális megoldása. (Másszóval m-nél több m-dimenziós vektor mindig lineárisan összefüggő. Még másképp, A nulltere nem-triviális.)

Következmény 1.3 Ha egy mátrix oszlopai is és sorai is lineárisan függetlenek, akkor a mátrix négyzetes.

Következmény 1.4 Ha az A′ mátrixból lineárisan függetlenül kiválasztható sorok maximális száma kisebb, mint az oszlopok száma, akkor az A′z = 0 rendszernek van nem-triviális megoldása.

Lemma 1.5 Tegyük fel, hogy az A mátrixban az első r oszlop lineárisan független és a többi oszlop lineárisan függ ezektől. Hasonlóképp legyen az első s sor lineárisan független és a többi sor lineárisan függjön ezektől. Ekkor az első r oszlop és az első s sor által meghatározott A_{1} részmátrix oszlopai is és sorai is lineárisan függetlenek.

TÉTEL 1.6 Egy A mátrix lineárisan független oszlopainak maximális száma egyenlő a lineárisan független sorok maximális számával.

Ezt a közös maximális számot r(A)-val jelöljük és a mátrix rangjának nevezzük. Egy négyzetes mátrixot szingulárisnak neveznek, ha sorai (illetve ezzel ekvivalensen, oszlopai) lineárisan összefüggnek.

Következmény 1.7 Egy mátrix rangja nem változik, ha hozzáveszünk egy új oszlopot, amely lineárisan függ az oszlopoktól, vagy ha elhagyunk egy meglévő oszlopot, amely lineárisan függ a többi oszloptól. Analóg állítás érvényes sorokra. •

TÉTEL 1.8 Ha egy m × n-es A mátrix sorai lineárisan függetlenek (azaz r(A) = m), akkor tetszőleges n-dimenziós b vektorra az Ax = b egyenletrendszernek létezik megoldása (ami b ≠ 0 esetben azzal ekvivalens, hogy b lineárisan függ az A oszlopaitól.) Ha m = n, akkor a megoldás egyértelmű.

TÉTEL 1.9 A következők ekvivalensek. (A) Az Ax = b egyenletrendszernek létezik megoldása. (B) r(A) = r([A, b]), (ahol [A, b] az a mátrix, amely A-ból áll elő a b oszlop hozzávételével). (C) Nem létezik olyan y, amelyre yA = 0, yb ≠ 0.

Az 1.9 tételben az (A)-beli problémát primál problémának nevezzük. Ez tehát azt kérdezi, hogy a b oszlopvektor benne van-e az A oszlopainak alterében. A (C)-beli problémát duál (vagy duális) problémának hívjuk.

TÉTEL 1.10 (Fredholm féle alternatíva tétel) Az Ax = b rendszernek akkor és csak akkor van megoldása, ha nem létezik olyan y, amelyre yA = 0, yb ≠ 0. Ekvivalensen, egy [ b ] vektor vagy benne van egy altérben [melyet az A oszlopai generálnak], vagy elválasztható tőle [egy y normálisú] homogén hipersíkkal abban az értelemben, hogy a hipersík az alteret tartalmazza, de a vektort nem.

TÉTEL 1.11 Egy A n × n-es nem-szinguláris négyzetes mátrix első m sora által alkotott részmátrixot jelölje A_{1}, míg a maradékot A_{2}. Tegyük fel, hogy az A_{1} minden sora ortogonális A_{2} minden sorára. Ekkor A_{1} sortere éppen az A_{2} nulltere és A_{1} nulltere éppen az A_{2} sortere.

TÉTEL 1.12 Legyen A_{1} olyan m × n-es mátrix (m < n), amelynek sorai lineárisan függetlenek. Ekkor létezik olyan (n − m) × n méretű A_{2} mátrix, amelynek sorai ortogonálisak az A_{1} soraira és amely az A_{1}-gyel együtt egy n × n-es nem-szinguláris mátrixot alkot. (Az A_{2} sortere éppen az A_{1} sorterének az ortogonális kiegészítője.)

1.3 ALTEREK, AFFIN ALTEREK

Affin altéren vagy eltolt altéren (vagy affin halmazon) egy altér eltoltját értjük. A C affin altér dimenzióján a definiáló A altér dimenzióját értjük.

Két (különböző) pont affin kombinációinak halmazát a két pont összekötő egyenesének nevezzük, míg a két pont konvex kombinációinak halmaza a két pontot összekötő szakasz. Egy egy-dimenziós affin halmazt egyenesnek nevezünk.

TÉTEL 1.13 Tegyük fel, hogy az Ax = b egyenletrendszernek van egy x_{0} megoldása. Ekkor a megoldások M := {x : Ax = b} halmaza az R^{n} tér affin altere, nevezetesen az A nullterének eltoltja. Másként fogalmazva, az Ax = 0 homogén egyenletrendszer egy tetszőleges megoldását x_{0}-hoz adva megoldást kapunk, és M minden tagja így áll elő. Megfordítva, minden affin altér előáll egy egyenletrendszer megoldás-halmazaként.

Következmény 1.14 Amennyiben az Ax = b egyenletrendszernek van megoldása, úgy az M megoldáshalmaz dimenziója n − r(A), ahol n az oszlopok száma.

1.4 KÚPOK, POLIÉDEREK

Pontok egy halmazát akkor nevezzük konvexnek, ha zárt a konvex kombináció képzésre.

Könnyen ellenőrizhető, hogy konvex halmazok metszete is konvex. A C-t tartalmazó konvex halmazok metszete a C konvex burka (convex hull) és konv(C)-vel jelöljük. Ez a C elemeinek felhasználásával készült konvex kombinációk halmaza.

Amennyiben a ∈ R^{n} nem-nulla vektor, β tetszőleges szám, az ax = β lineáris egyenlet megoldás-halmazát hipersíknak (hyperplane) nevezzük. Az {ax ≤ β} egyenlőtlenség-rendszer megoldás halmazát, vagyis az {x : ax ≤ β} halmazt (zárt) féltérnek (closed halfspace) hívjuk, melynek {x = Ax = b} a határoló síkja, és amelynek normálisa a. (Ha szigorú egyenlőtlenség van, nyílt féltérről beszélünk). A β = 0 esetben azt mondjuk, hogy a féltér homogén.

Vektorok egy nemüres C halmazát kúpnak (cone) nevezzük, ha C zárt nemnegatív számmal történő szorzásra nézve, vagyis ha C bármely elemének nem-negatív számszorosa is C-hez tartozik. A kúp triviális, ha egyetlen pontja van (az origó). Amennyiben a kúp még az összeadásra is zárt, konvex kúpról beszélünk. Végesen generált kúp (röviden, generált kúp): Véges sok a_{1}, …, a_{n} vektor nemnegatív lineáris kombinációinak halmaza. Jelölése : kúp(a_{1}, …, a_{n}) := {z : z = ∑_{i} λ_{i}a_{i}, λ_{i} ≥ 0}. Metszetkúp (másnéven poliéder-kúp): Véges sok homogén féltér metszete; {x : b_{1}x ≤ 0, …, b_{m}x ≤ 0}. Például, {x : Ax ≤ 0} vagy {y : yA ≤ 0}.

Egy q nemnulla vektor esetén a {λq : λ ∈ R_{+}} generált kúpot végtelen iránynak vagy röviden iránynak vagy másként sugárnak (ray) mondjuk és q⃗-val jelöljük. A q⃗_{1}, …, q⃗_{k} irányok egy nemnegatív kombinációján a q_{1}, …, q_{k} vektorok egy nemnagatív kombinációjához tartozó irányt értjük. Egy z pontból induló q⃗ irányú félegyenesen a z + q⃗ := {x : x = z + λq, λ ∈ R_{+}} halmazt értjük.

Adott K kúphoz hozzárendelhetjük a K^{∗} := {x : xz ≤ 0 minden z ∈ K elemre} halmazt, és ezt a K polárisának nevezzük. Az A mátrixra jelölje G_{A} az A sorai által generált {yA : y ≥ 0} kúpot, míg M_{A} az A sorai által definiált {x : Ax ≤ 0} metszetkúpot.

Lemma 1.15 A G_{A} kúp polárisára (G_{A})^{∗} = M_{A}.

Lemma 1.16 Az M_{A} polárisára (M_{A})^{∗} ⊇ G_{A}.

Poliéder (polyhedron, tbsz: polyhedra): Véges sok féltér metszete: R := {x : Qx ≤ b} ahol Q egy m × n-es mátrix, b m-dimenziós vektor.

Egy poliédert akkor nevezünk korlátosnak, ha létezik olyan K pozitív szám, amelyre |x(i)| ≤ K a poliéder minden x pontjának mindegyik x(i) komponensére. Egy poliéder (külső) dimenzió-ján, (röviden dimenzióján) az őt tartalmazó legszűkebb affin altér dimenzióját értjük. A poliéder belső dimenziója, a tér benne fekvő affin alterek dimenziójának a maximuma. Politop (polytope): Véges sok pont konvex burka.

A poliéder egy z pontját csúcsnak nevezzük, ha nem áll elő a poliéder néhány más pontjának konvex kombinációjaként. A poliédert csúcsosnak (pointed) mondjuk, ha van csúcsa. Ha egy poliéder nem tartalmaz teljes egyenest (félegyenest) akkor azt mondjuk, hogy egyenes-mentes (félegyenes-mentes). A q⃗ irányt az R poliéder egy irányának nevezzük, ha van R-nek olyan z pontja, amelyre z + λq ∈ R minden pozitív λ-ra. A poliéder egy q⃗ irányát extrémnek nevezzük, ha nem áll elő a poliéder más irányainak nemnegatív kombinációjaként.

A P ⊆ R^{n} nemüres poliérderre legyen c ∈ R^{n} olyan vektor, amelyre max{cx : x ∈ P } létezik és értéke δ. A H = {x : cx = δ} hipersíkot a poliéder egy támasz-síkjának nevezzük. A H ∩ P halmazt pedig a poliéder egy oldalának. Minimális oldalon egy olyan oldalt értünk, amely nem tartalmaz valódi részhalmazként oldalt.

Lemma 1.17 Ha az R poliéder kúp, akkor metszetkúp.

LINEÁRIS EGYENLŐTLENSÉG-RENDSZEREK

2.1 A FOURIER-MOTZKIN ELIMINÁCIÓ

Legyen A olyan m·n-es mátrix (m ≥ 1, n ≥ 2), amelynek első, a_{1}-gyel jelölt oszlopa 0, ±1 értékű. Jelölje rendre I, J, K a sorok azon indexhalmazait, melyekre az a_{1}(i) értéke +1, −1 illetve 0. Készítsük el az A^{[1]} mátrixot a következőképpen. A K-nak megfelelő sorok változatlanul kerüljenek be A^{[1]}-be. Ezen kívül minden i ∈ I, j ∈ J választásra legyen _{i}a + _{j}a legyen az A^{[1]} egy sora, melyet jelöljünk _{[ij]}a-val.

2.1.1 A primál feladat

TÉTEL 2.1 Az

Ax ≤ 0  (2.1)

egyenlőtlenség-rendszernek bármely megoldása az

A^{[1]}x ≤ 0  (2.2)

rendszernek is megoldása. A (2.2) bármely megoldásának első komponensét alkalmasan megváltoztatva a (2.1) egy megoldását kapjuk. Következmény 2.2 Tegyük fel, hogy a Q mátrix első oszlopa 0, ±1 értékű, és rendeljük a

Qx′ ≤ b  (2.3)

egyenlőtlenség-rendszerhez a

Q^{[1]}x′ ≤ b^{[1]}  (2.4)

rendszert, ahol b^{[1]} az A := (Q, b) mátrixhoz tartozó A^{[1]} mátrix utolsó oszlopa. Ekkor (2.3) bármely megoldása (2.4)- nak is megoldása, és a (2.4) bármely megoldásának első komponensét alkalmasan megváltoztatva a (2.3) egy megoldását kapjuk. Következmény 2.3 Metszetkúp tengelymenti (külső vagy belső) vetülete metszetkúp. Következmény 2.4 Generált kúp előáll metszetkúpként. Lemma 2.5 Az M_{A} polárisára (M_{A})^{∗} = G_{A}. Következmény 2.6 Ha C generált- vagy metszetkúp, akkor C^{∗∗} = C. •

2.1.2 A duál feladat

TÉTEL 2.7 Legyen c ∈ R^{n} olyan vektor, amelyre c(1) = 0. Ekkor az

{yA = c, y ≥ 0}  (2.5)

rendszer akkor és csak akkor oldható meg, ha az

{y′A^{[1]} = c, y′ ≥ 0}  (2.6)

rendszer megoldható. Következmény 2.8 Legyen Q, b, A ugyanaz, mint a 2.2 következményben. Akkor és csak akkor létezik olyan y ≥ 0, amelyre yQ = 0, yb = −1, ha létezik olyan y′ ≥ 0, amelyre y′Q^{[1]} = 0, y′b^{[1]} = −1. Következmény 2.9 Generált kúp metszete koordináta-altérrel generált kúp. Következmény 2.10 Metszetkúp előáll generált kúpként.

2.1.3 Kúpok és poliéderek előállítása

TÉTEL 2.11 Egy P ⊆ R^{n} nemüres halmaz akkor és csak akkor metszetkúp, ha generált kúp. P akkor és csak akkor poliéder, ha előáll egy nemüres politop és egy generált kúp összegeként. Következmény 2.12 Egy R^{n}-beli halmaz akkor és csak akkor politop, ha korlátos poliéder.

2.1.4 Az FM eljárás hatékonysága 2.1.5 A 2-SAT probléma 2.1.6 Egy ütemezési feladat: PERT

2.2 MEGOLDHATÓSÁG: A FARKAS LEMMA

TÉTEL 2.13 (Farkas lemma, alap alak) Az {Ax = b, x ≥ 0} rendszernek pontosan akkor van megoldása, ha az {yA ≥ 0, yb < 0} rendszernek nincs.

Az {Ax = b, x ≥ 0} rendszert primál feladatnak, míg az {yA ≥ 0, yb < 0} rendszert duál vagy duális feladatnak nevezik. TÉTEL 2.14 (Farkas lemma, alap alak) A b vektor akkor és csak akkor van benne egy K generált kúpban, ha nincs olyan zárt homogén féltér, amely K-t tartalmazza, de b-t nem. TÉTEL 2.15 (Farkas lemma, (A) változat) A Qx ≤ b egyenlőtlenség-rendszer akkor és csak akkor oldható meg, ha nem létezik olyan y ≥ 0, amelyre yQ = 0, yb = −1. TÉTEL 2.16 (Farkas lemma, (B) változat) A {Bx ≤ b, x ≥ 0} egyenlőtlenség-rendszer akkor és csak akkor oldható meg, ha nem létezik olyan y ≥ 0, amelyre yB ≥ 0, yb = −1. TÉTEL 2.17 A

{P x = b_{0}, Qx ≤ b_{1}}  (2.7)

primál rendszer akkor és csak akkor oldható meg, ha az

{y_{0}P + y_{1}Q = 0, y_{1} ≥ 0, yb = −1}  (2.8)

duális nem, ahol y = (y_{0}, y_{1},), b = (b_{0}, b_{1}). TÉTEL 2.18 (Farkas lemma, általános alak) A

P x_{0} + Ax_{1} = b_{0}, Qx_{0} + Bx_{1} ≤ b_{1}, x_{1} ≥ 0  (2.9)

primál rendszernek akkor és csak akkor nincs megoldása, ha az

y_{0}P + y_{1}Q = 0, y_{0}A + y_{1}B ≥ 0, y_{1} ≥ 0, yb := y_{0}b_{0} + y_{1}b_{1} = −1  (2.10)

duális rendszernek van.

2.2.1 Direkt bizonyítás

TÉTEL 2.19 A

P x_{0} + Ax_{1} = b, x_{1} ≥ 0  (2.11)

primál feladatnak akkor és csak akkor nincsen megoldása, ha az

yP = 0, yA ≥ 0, yb = −1  (2.12)

duális feladatnak van. TÉTEL 2.20

y_{0}P′ + y_{1}Q′ = c′_{0}, y_{0}A′ + y_{1}B′ ≥ c′_{1}, y_{1} ≥ 0  (2.13)

primál rendszernek akkor és csak akkor nincs megoldása, ha a

P′x_{0} + A′x′_{1} = 0, Q′x_{0} + B′x′_{1} ≤ 0, x′_{1} ≥ 0, c′_{0}x_{0} + c′_{1}x′_{1} > 0  (2.14)

duális rendszernek van. •

2.3 KORLÁTOSSÁG

2.3.1 Bázis-megoldások

Legyen Q ≠ 0 egy m · n-es mátrix és jelölje R a Qx ≤ b egyenlőtlenség-rendszer megoldásainak halmazát. Ennek egy z elemére jelölje Q_{z}^{=} a Q azon soraiból álló részmátrixot, amelyekre az általuk meghatározott egyenlőtlenségeket a z egyenlőséggel teljesíti. Az ennek megfelelő jobboldal legyen b_{z}^{=}, míg a Q maradék részét jelölje Q_{z}^{<}. A z ∈ R elem σ(z)-vel jelölt szint-jén az r(Q) − r(Q_{z}^{=}) számot értjük. Ha ez a szám 0, úgy z-t bázis-megoldásnak nevezzük.

TÉTEL 2.21 Tegyük fel, hogy az R poliéder nemüres és R = {x : Qx ≤ b} = {x : Q′x ≤ b′}. Ekkor Q és Q′ sortere megegyezik. Tetszőleges z ∈ R esetén Q_{z}^{=} és Q′_{z}^{=} sortere megegyezik.

Következmény 2.22 Egy z ∈ R elem szintje csak a poliédertől függ és nem a poliédert meghatározó egyenlőtlenségrendszer konkrét alakjától. Speciálisan, a bázis-megoldás fogalma is csak a poliédertől függ.

TÉTEL 2.23 (i) Az {Ax = b, x ≥ 0} egy z megoldása akkor és csak akkor bázis-megoldás, ha a pozitív elemekhez tartozó A-beli oszlopok lineárisan függetlenek. (ii) Az {yA ≥ 0, yb = −1} rendszer egy y_{0} megoldása akkor és csak akkor bázis-megoldás, ha az A-ból lineárisan függetlenül kiválasztható, az y_{0}-ra merőleges oszlopok maximális száma r(A, b) − 1.

2.3.2 Erős bázis-megoldások

TÉTEL 2.24 Tegyük fel, hogy az R poliéder nemüres és R = {x : Qx ≤ b} = {x : Q′x ≤ b′}. A Q valamely j oszlopa pontosan akkor lineárisan független, ha Q′ megfelelő j oszlopa lineárisan független.

Következmény 2.25 Az erős bázis-megoldás fogalma csak a poliédertől függ és nem a poliédert meghatározó egyenlőtlenségrendszertől. •

Következmény 2.26 A {P x = b_{0}, Qx ≤ b_{1}} egyenlőtlenség-rendszer egy z bázis-megoldása pontosan akkor erős, ha

a z nem-nulla komponenseihez tartozó M-beli oszlopok lineárisan függetlenek, ahol M = ( \begin{matrix}P \\ Q \end{matrix} ). •

TÉTEL 2.27 A Qx ≤ b egyenlőtlenség-rendszer egy z megoldása akkor és csak akkor erős bázis-megoldás, ha létezik Q-nek egy olyan r(Q) sorból és r(Q) oszlopból álló nem-szinguláris Q′ részmátrixa, amelyre z a Q′x′ = b′ egyértelmű x′ megoldásából áll elő 0-komponensek hozzávételével (ahol b′ a b azon részét jelöli, amely a Q′ sorainak felel meg.)

Következmény 2.28 Tetszőleges egyenlőtlenség-rendszernek legfeljebb csak véges sok erős bázis-megoldása van. •

2.3.3 A korlátosság feltétele

Lemma 2.29 Legyen z a Qx ≤ b egyenlőtlenség-rendszernek egy megoldása, és c egy n-dimenziós vektor. Ha nem létezik olyan q vektor, amelyre cq > 0, Qq ≤ 0, akkor Qx ≤ b-nek létezik olyan x^{∗} bázis-megoldása, amelyre cx^{∗} ≥ cz.

Következmény 2.30 Ha egy egyenlőtlenség-rendszernek van megoldása, akkor létezik bázis-megoldása is. •

TÉTEL 2.31 (Korlátossági tétel, speciális alak) Tegyük fel, hogy az R := {x : Qx ≤ b} poliéder nemüres, és legyen c egy n-dimenziós vektor. A következők ekvivalensek.

(0) A {cx} lineáris függvény R-n felülről korlátos.

(1) Minden z ∈ R elemre létezik Qx ≤ b-nek olyan x^{∗} erős bázis-megoldása, amelyre cx^{∗} ≥ cz.

(2) Nem létezik olyan q vektor, amelyre cq > 0 és Qq ≤ 0.

(3) Létezik olyan y ≥ 0 vektor, amelyre yQ = c.

Következmény 2.32 Ha az R = {x : Qx ≤ b} poliéder nemüres, és {cx : x ∈ R} felülről korlátos, úgy max{cx : x ∈ R} létezik (azaz létezik olyan z ∈ R, amelyre cz = sup{cx : x ∈ R}).

Következmény 2.33 Ha egy egyenlőtlenség-rendszer megoldható, akkor van erős bázis-megoldása is.

Legyen R a

P x_{0} + Ax_{1} = b_{0}, Qx_{0} + Bx_{1} ≤ b_{1}, x_{1} ≥ 0  (2.15)

megoldás-halmaza.

TÉTEL 2.34 (Korlátossági tétel) Tegyük fel, hogy az R poliéder nemüres, és legyen c = (c_{0}, c_{1}) adott vektor. A következők ekvivalensek.

(0) A {cx} lineáris függvény R-n felülről korlátos.

(1) Minden z ∈ R elemre létezik (2.15)-nek olyan x^{∗} erős bázis-megoldása, amelyre cx^{∗} ≥ cz.

(2) Nem létezik olyan q = (q_{0}, q_{1}) vektor, amelyre cq > 0, és q_{1} ≥ 0, P q_{0} + Aq_{1} = 0, Qq_{0} + Bq_{1} ≤ 0.

(3) Létezik olyan y = (y_{0}, y_{1}) vektor, amelyre

y_{0}P + y_{1}Q = c_{0}, y_{0}A + y_{1}B ≥ c_{1}, y_{1} ≥ 0. •  (2.16)

TÉTEL 2.35 Az {Ax = b, x ≥ 0} rendszernek akkor és csak akkor van olyan megoldása, amelyben az x pozitív változóinak megfelelő A-beli oszlopok lineárisan függetlenek, ha nem létezik olyan y, amelyre yA ≥ 0, yb = −1 és A-nak létezik r(A, b) − r(b) lineárisan független oszlopa, amelyekre y merőleges. (Röviden, vagy a primál, vagy a duál problémának létezik bázis-megoldása). •

Következmény 2.36 (C. Caratheodory) Ha a d-dimenziós tér egy z pontja p ≥ d + 1 darab pont konvex kombinációja, akkor ezen pontok között van legfeljebb d + 1, amelyeknek z konvex kombinációja.

2.4 OPTIMALITÁS: A DUALITÁS TÉTEL

2.4.1 Optimalitási feltételek

Legyen x^{∗} az R = {x : Qx ≤ b} egy adott eleme. Azt mondjuk, hogy egy x′ irány x^{∗}-nál lehetséges elmozdulás, ha van olyan (kicsiny) pozitív λ szám, amelyre x^{∗} + λx′ ∈ R. Ha ráadásul cx′ > 0, akkor x′-t növelő iránynak hívjuk (c-re és x^{∗}-re nézve).

TÉTEL 2.37 Tegyük fel, hogy az R := {x : Qx ≤ b} poliéder nemüres és {cx : x ∈ R} felülről korlátos. Az R egy megadott x^{∗} elemére a következő állítások ekvivalensek.

(1) cx^{∗} ≥ cx minden x ∈ R, azaz x^{∗} maximalizálja a cx függvényt az R-n (röviden, x^{∗} optimális).

(2) Nem létezik növelő irány, azaz olyan x′ vektor, amelyre Q_{∗}^{=}x′ ≤ 0 és cx′ > 0.

(3) Létezik olyan y^{∗} vektor, amely kielégíti az

y^{∗} ≥ 0, y^{∗}Q = c  (2.17)

duális feltételt, és amelyre fennáll az

y^{∗}(i) > 0 ⇒ _{i}qx^{∗} = b(i)  (2.18)

optimalitási kritérium (ami szavakban: az y^{∗} bármely komponense csak akkor lehet pozitív, ha a neki megfelelő primál egyenlőtlenséget x^{∗} egyenlőséggel teljesít). (2.17) fennállása esetén (2.18) azzal ekvivalens, hogy

cx^{∗} = by^{∗},  (2.19)

továbbá azzal, hogy

y^{∗}(b − Qx^{∗}) = 0.  (2.20)

TÉTEL 2.38 Tegyük fel, hogy a

P x_{0} + Ax_{1} = b_{0}, Qx_{0} + Bx_{1} ≤ b_{1}, x_{1} ≥ 0  (2.21)

rendszerrel definiált R poliéder nemüres és {cx = c_{0}x_{0} + c_{1}x_{1} : x ∈ R} felülről korlátos. Legyen x^{∗} = (x_{0}^{∗}, x_{1}^{∗}) az R egy eleme, és jelölje (Q_{∗}^{=}, B_{∗}^{=}) a (Q, B) mátrix azon sorai által alkotott részmátrixot, amelyekre a hozzájuk tartozó egyenlőtlenségeket x^{∗} egyenlőséggel teljesíti, míg b_{1∗}^{=} jelölje a b_{1} megfelő részét. A következő állítások ekvivalensek.

(1) cx^{∗} ≥ cx minden x ∈ R, azaz x^{∗} maximalizálja a cx függvényt az R-n (röviden, x^{∗} optimális).

(2) Nem létezik növelő irány, azaz olyan x′ = (x′_{0}, x′_{1}) vektor, amelyre cx′ > 0,

P x_{0} + Ax_{1} = b_{0}, Q_{∗}^{=}x_{0} + B_{∗}^{=}x_{1} ≤ b_{1∗}^{=}  (2.22)

és

x_{1}^{∗}(i) = 0 ⇒ x′_{1}(i) ≥ 0.  (2.23)

(3) Létezik olyan y^{∗} = (y_{0}^{∗}, y_{1}^{∗}) vektor, amely kielégíti az

y_{1}^{∗} ≥ 0, y_{0}^{∗}P + y_{1}^{∗}Q = c_{0}, y_{0}^{∗}A + y_{1}^{∗}B ≥ c_{1}  (2.24)

duális feltételt, és amelyre fennáll az

x_{1}^{∗}(j) > 0 ⇒ y_{0}^{∗}a_{j} + y_{1}^{∗}b_{j} = c_{1}(j)  (2.25)

valamint az

y_{1}^{∗}(i) > 0 ⇒ _{i}qx_{0}^{∗} + _{i}bx_{1} = b_{1}(i),  (2.26)

optimalitási kritérium. (2.24) fennállása esetén az optimalitási kritérium azzal ekvivalens, hogy

cx^{∗} = by^{∗},  (2.27)

és azzal, hogy

y^{∗}(b − Mx^{∗}) = 0,  (2.28)

ahol M = ( \begin{matrix}P & A \\ Q & B \end{matrix} ).

2.4.2 A dualitás tétel

A primál probléma:

max{(c_{0}x_{0} + c_{1}x_{1}) : P x_{0} + Ax_{1} = b_{0}, Qx_{0} + Bx_{1} ≤ b_{1}, x_{1} ≥ 0}.  (2.29)

A duális probléma:

min{(c_{0}y_{0} + c_{1}y_{1}) : y_{0}P + y_{1}Q = c_{0}, y_{0}A + y_{1}B ≥ c_{1}, y_{1} ≥ 0}.  (2.30)

TÉTEL 2.39 (Dualitás tétel, speciális alak) Tegyük fel, hogy az R = {x : Qx ≤ b} primál poliéder nemüres. Tegyük fel továbbá, hogy {cx : x ∈ R} felülről korlátos (ami a 2.31 tétel szerint azzal ekvivalens, hogy a duális R^{∗} = {y : y ≥ 0, yQ = c} poliéder nemüres). Ekkor a primál optimalizálási feladatban a maximum egyenlő a duál feladatban szereplő minimummal, azaz max{cx : Qx ≤ b} = min{by : y ≥ 0, yQ = c}.

A (2.30)-ban szereplő poliédert R^{∗}-gal jelöljük és duális poliédernek hívjuk.

TÉTEL 2.40 (Dualitás tétel) Tegyük fel, hogy a (2.29) rendszer által definiált R primál poliéder nemüres. Tegyük fel továbbá, hogy a cx = c_{0}x_{0} + c_{1}x_{1} célfüggvényre nézve {cx : x ∈ R} felülről korlátos (vagy ekvivalensen a duális R^{∗} poliéder nemüres). Ekkor a (2.29) primál optimalizálási feladatban a maximum egyenlő a (2.30) duál feladatban szereplő minimummal.

Azt mondjuk, hogy egy c′x célfügvény vagy a c′ vektor valamely R poliéderre nézve neutrális (semleges), ha R minden x elemére c′x értéke ugyanaz. Két vektort (célfüggvényt) akkor mondunk ekvivalensnek, ha különbségük neutrális.

2.4.3 Lineáris és logikai következmény

Tekintsük a

P x_{0} + Ax_{1} = b_{0}, Qx_{0} + Bx_{1} ≤ b_{1}, x_{1} ≥ 0  (2.31)

egyenlőtlenség-rendszert, melynek R megoldás-halmazáről tegyük fel, hogy nemüres. Legyen M = ( \begin{matrix}P & A \\ Q & B \end{matrix} ). Legyen

c = (c_{0}, c_{1}) adott vektor. Az (x_{0}, x_{1}) vektort néha röviden x-szel jelöljük, és hasonlóképp a ( \begin{matrix}b_{0} \\ b_{1} \end{matrix} ) vektort b-vel. Azt

mondjuk, hogy a

c_{0}x_{0} + c_{1}x_{1} ≤ γ  (2.32)

egyenlőtlenség logikai következménye a (2.31) rendszernek, ha (2.31) minden megoldása teljesíti (2.32)-t. A (2.32) egyenlőtlenség lineáris következménye (2.31)-nek, ha létezik olyan y := (y_{0}, y_{1}), amelyre

y_{1} ≥ 0, y_{0}P + y_{1}Q = c_{0}, y_{0}A + y_{1}B ≥ c_{1}, yb ≤ γ.  (2.33)

TÉTEL 2.41 Feltéve, hogy R nemüres, (2.32) akkor és csak akkor lineáris következménye (2.31)-nek, ha logikai.

TÉTEL 2.42 (Dualitás tétel, speciális alak) Tegyük fel, hogy mind az R := {Bx ≤ b, x ≥ 0} primál, mind az R^{∗} := {yB ≥ c, y ≥ 0} duál poliéder nemüres. Ekkor cx ≤ by fennáll minden x ∈ R, y ∈ R^{∗} esetén, és van olyan x^{∗} ∈ R, y^{∗} ∈ R^{∗}, melyekre egyenlőség érvényes, azaz max{cx : x ∈ R} = min{by : y ∈ R^{∗}}.

2.4.4 Neumann tétele

Egy vektor tetején értsük a legnagyobb komponensének az értékét. A vektor alja legyen a legkisebb komponensének az értéke.

TÉTEL 2.43 (Neumann János) Tetszőleges nemüres A mátrixra az A oszlopvektorai által feszített politopban lévő elemek tetejének a minimuma egyenlő az A sorvektorai által feszített politopban lévő elemek aljának maximumával. Formálisabban, min{(max Ax) : x ≥ 0, 1x = 1} = max{(min yA) : y ≥ 0, 1y = 1}, ahol az 1x rövidítés a csupa 1 vektor és az x skalárszorzatát jelöli.

2.4.5 Egy játekelméleti alkalmazás

TÉTEL 2.44 (Neumann) Tetszőleges A mátrix által meghatározott mátrixjáték esetén a sorjátékos várható nyereségének maximuma egyenlő az oszlopjátékos várható veszteségének minimumával.

2.5 POLIÉDEREK HATÁROLÓ ALKATRÉSZEI

2.5.1 Csúcsok és extrém irányok

TÉTEL 2.45 Az R csúcsos poliéder egy z elemére a következők ekvivalensek.

(i) z csúcs. (ii) z bázis-megoldás. (iii) Létezik olyan c vektor, amelyre cz > cx fennáll R minden z-től különböző x elemére.

TÉTEL 2.46 Egy R = {x : Qx ≤ b} nemüres poliéderre a következők ekvivalensek.

(1) R csúcsos.

(2) R egyenes-mentes.

(3) Q oszlopai lineárisan függetlenek.

Az R = {x : Qx ≤ b} poliéderhez hozzárendelhetjük az A := {q : Qq = 0} karakterisztikus alteret.

TÉTEL 2.47 Valamely nemnulla q vektorra a következők ekvivalensek.

(1) q eleme a karakterisztikus altérnek (azaz Qq = 0).

(2) R bármely x pontjára x + λq minden valós λ-ra R-ben van (vagyis az x-en átmenő q irányú egyenes R-ben van).

(3) R-nek van olyan z pontja, amelyre z + λq minden valós λ-ra R-ben van.

Következmény 2.48 Egy nemüres poliéder akkor és csak akkor egyenes-mentes, ha a definiáló mátrix oszlopai lineárisan függetlenek. •

Következmény 2.49 Az R poliéder egy z pontját tartalmazó legbővebb, R-ben fekvő affin altér az A karakterisztikus altér z-vel való eltoltja.

Egy poliéder belső dimenzióján a benne fekvő maximális affin altér dimenzióját értettük.

Következmény 2.50 Egy R := {x : Qx ≤ b} ⊆ R^{n} poliéder belső dimenziója n − r(Q).

A q⃗ irány a poliéder iránya, ha R minden x elemére az {x + λq : λ ≥ 0} félegyenes R-ben van.

TÉTEL 2.51 Valamely nemnulla q vektorra a következők ekvivalensek.

(1) q⃗ a poliéder iránya.

(2) R-nek van olyan z pontja, amelyre a {z + λq : λ ≥ 0} félegyenes R-ben van.

(3) Qq ≤ 0.

A poliéder irányai által alkotott kúpot karakterisztikus (néha recessziós) kúpnak nevezik.

Következmény 2.52 Egy poliédernek és karakterisztikus kúpjának extrém irányai ugyanazok. •

TÉTEL 2.53 Minden R egyenes-mentes (azaz csúcsos) poliéder előáll mint a csúcsai által feszített R_{K} politop valamint a poliéder C karakterisztikus kúpjának a vektor-összege.

TÉTEL 2.54 Egy R nemüres poliéderre a következők ekvivalensek.

(1) R korlátos,

(2) R nem tartalmaz félegyenest,

(3) R karakterisztikus kúpja, {x : P x = 0, Qx ≤ 0} triviális.

(4) R a csúcsainak konvex burka.

TÉTEL 2.55 Legyen a C := {x : Mx ≤ 0} nemtriviális kúp egyenes-mentes, és legyen Z := {x : Mx ≤ 0, ax = −1} poliéder, ahol a := 1 · M az M sorainak az összege. Ekkor tetszőleges z ∈ Z esetén z⃗ a kúp iránya. A kúp tetszőleges q⃗ iránya egyetlen z pontban metszi Z-t. Z korlátos. Egy z ∈ Z pont akkor és csak akkor csúcsa Z-nek, ha z⃗ extrém iránya C-nek.

Következmény 2.56 C egyenes-mentes nemtriviális metszet-kúpnak véges sok extrém iránya van, és C ezen irányok generált kúpja. •

Következmény 2.57 A C = {x : Mx ≤ 0} egyenes-mentes kúp egy z nemnulla eleme által meghatározott z⃗ irány akkor és csak akkor extrém iránya C-nek, ha z merőleges az M mátrix r(M) − 1(= n − 1) lineárisan független sorára.

Következmény 2.58 Minden R egyenes-mentes (azaz csúcsos) poliéder előáll mint a csúcsai által feszített politopnak valamint az extremális irányai által generált (csúcsos) kúpnak (vagyis az R karakterisztikus kúpjának) a vektor-összege. •

TÉTEL 2.59 Az R = {x : Qx ≤ b} nemüres poliéder az A := {x : Qx = 0} karakterisztikus altér és az R′ := R ∩ A^{⊥} poliéder vektor-összege, ahol A^{⊥} az A altér ortogonális kiegészítője (vagyis a Q sorai által generált altér). Továbbá, az R′ poliéder egyenes-mentes (=csúcsos).

Következmény 2.60 Egy R := {x : Mx ≤ 0} metszet-kúp az A := {x : Mx = 0} karakterisztikus altér (ami speciális metszet-kúp) és az R′ := R ∩ A^{⊥} csúcsos metszet-kúp vektor-összege.

2.5.2 Oldalak

Egy R nemüres poliéder F oldala (face) R-nek egy

F := {x ∈ R : cx = δ}  (2.34)

alakú nemüres részhalmaza, ahol δ := max{cx : x ∈ R} valamely cx célfüggvényre, melyre a maximum létezik. Egy R-től különböző oldalt valódi oldalnak nevezünk. Valódi oldalon (proper face) olyan oldalt értünk, amely nem az egész poliéder. Poliéder minimális oldalán egy tartalmazásra nézve minimális oldalt értünk. Egy tartalmazásra nézve maximális valódi oldalt lapnak (facet) nevezünk.

TÉTEL 2.61 Az R = {x : Qx ≤ b} poliéder egy nemüres F részhalmaza akkor és csak akkor oldala R-nek, ha létezik a Q bizonyos soraiból álló olyan Q′ Q′ részmátrix, amelyre F = {x ∈ R : Q′x = b′}, ahol b′ a Q′ sorainak megfelelő részvektora b-nek.

P x = b_{0}, Qx ≤ b_{1}  (2.35)

A Qx ≤ b rendszer egy qx ≤ β egyenlőtlenségéről azt mondjuk, hogy implicit egyenlőség, ha R minden eleme egyenlőséggel teljesíti Az implicit egyenlőségek által alkotott egyenlőség-rendszert Q^{=}x = b^{=}-vel jelöljük. Egy nem implicit egyenlőtlenséget valódinak mondunk, és az általuk alkotott rendszert Q^{<}x ≤ b_{1}^{<}-vel jelöljük.

A Qx ≤ b_{1} egyenlőtlenség-rendszer egyik qx ≤ β tagját feleslegesnek nevezzük (a (2.35)-re nézve), ha az elhagyásával keletkező rendszer ugyanazt a poliédert definiálja. Egy nem felesleges egyenlőtlenség neve lényeges. Egy P x = b_{0}-beli egyenlőség lényeges vagy felesleges annak megfelelően, hogy kihagyása R-nél bővebb poliédert eredményez-e vagy R-t változatlanul hagyja.

Nevezzük az R poliéder (2.35) alakú leírását minimálisnak, ha minden egyenlőség és egyenlőtlenség lényeges és minden egyenlőtlenség valódi.

Lemma 2.62 Ha qx ≤ β valódi és lényeges egyenlőtlensége (2.35)-nek, akkor R-nek van olyan z pontja, amelyre qz = β.

TÉTEL 2.63 Tegyük fel, hogy az R poliéder egy minimális (2.35) alakú rendszerrel van adva. A következő állítások ekvivalensek.

(i) R affin altér. (ii) R-nek nincs valódi oldala. (iii) Minden lényeges egyenlőtlenség implicit egyenlőség (azaz Q üres).

Következmény 2.64 Minden minimális oldal affin altér. •

Lemma 2.65 Az R poliédernek van olyan eleme, amely minden valódi egyenlőtlenséget szigorúan teljesít.

TÉTEL 2.66 Tegyük fel, hogy (2.35) minimális leírása R-nek. Az R akkor és csak akkor van benne egy H := {x : ax = β} hipersíkban (másszóval ax = β akkor és csak akkor logikai következménye (2.35)-nek), ha létezik olyan y_{0}, amelyre y_{0}P = a és y_{0}b_{0} = β (azaz, ax = β lineáris következménye P x = b_{0}-nak.)

Lemma 2.67 Tegyük fel, hogy R egy minimális (2.35) rendszerrel van megadva. Legyen F az R-nek egy oldala. Legyen Q′ a Q-nak egy m′ × n-es részmátrixa. A Q′ által meghatározott F′ := {x ∈ R : Q′x = b′_{1}} oldal akkor és csak akkor ugyanaz mint F, ha Q′ része Q_{F}^{=}-nek és r(Q′) = r(Q_{F}^{=}).

TÉTEL 2.68 A Qx ≤ b egyenlőtlenség-rendszer egy megoldása akkor és csak akkor bázis-megoldás, ha eleme az R = {x : Qx ≤ b} poliéder egy minimális oldalának.

2.5.3 Dimenzió, lapok

Egy altér dimenziója a belőle kiválasztható lineárisan független elemek maximális száma.

TÉTEL 2.69 Tegyük fel, hogy a nemüres R poliédert definiáló (2.35) rendszer minimális. Ekkor a legszűkebb R-t tartalmazó affin altér Z := {x : P x = b_{0}}

Következmény 2.70 Az R = {x : Qx ≤ b} nemüres poliédert tartalmazó legszűkebb affin altér Z_{R} := {x : Q^{=}x = b^{=}} , ahol Q^{=} jelöli az implicit egyenlőségeknek megfelelő részmátrixot. A poliéder dimenziója n − r(Q^{=}). •

Következmény 2.71 Az R = {x : Qx ≤ b} poliéder egy F oldalát tartalmazó legszűkebb affin altér {x : Q_{F}^{=}x = b_{F}^{=}}. Az F oldal dimenziója n − r(Q_{F}^{=}). Minimális oldal dimenziója n − r(Q). •

Egy c vektort illetve az általa meghatározott cx célfüggvényt akkor mondjuk semlegesnek (vagy neutrálisnak) az R =: {x : Qx ≤ b} poliéderre nézve, ha R minden x elemére cx értéke ugyanannyi.

TÉTEL 2.72 A semleges vektorok S_{R} altere éppen a Q-t tartalmazó legszűkebb Z_{R} affin altér A_{R} karakterisztikus alterének ortogonális kiegészítője. Egy c vektor akkor és csak akkor semleges, ha benne van Q^{=} sorterében.

Egy poliéder két csúcsát nevezzük szomszédosnak, ha az összekötő szakaszuk a poliéder oldala.

TÉTEL 2.73 Az R = {x : Qx ≤ b} csúcsos poliéder u és v csúcsaira a következők ekvivalensek.

(i) u és v szomszédosak. (ii) A Q azon soraiból alkotott Q_{uv}^{=} részmátrix, melyeknek megfelelő egyenlőtlenségeket mind u, mind v egyenlőséggel teljesíti, n − 1 rangú. (iii) Léteznek Q-nak olyan Q_{u} és Q_{v} n × n-es nemszinguláris részmátrixai, amelyekre u a Q_{u}x = b_{u} rendszer, míg v a Q_{v}x = b_{v} rendszer egyértelmű megoldásai, és amelyeknek n − 1 soruk közös.

TÉTEL 2.74 Tegyük fel, hogy a {P x = b_{0}, Qx ≤ b_{1}} rendszer minimális, és hogy az R megoldás halmaz nemüres. Ekkor az R-t tartalmazó legszűkebb affin altér {x : P x = b_{0}}. Továbbá egy-egy értelmű kapcsolat áll fenn az R lapjai és a Qx ≤ b_{0} egyenlőtlenségei között, azaz {x ∈ R : _{i}qx = b_{1}(i)} lapot alkot, és minden lap előáll ilyen alakban.

Következmény 2.75 Minden valódi oldal lapok metszete. •

2.6 A SZIMPLEX ALGORITMUS

2.6.1 Megengedettség

TÉTEL 2.76 Az {Ax = b, x ≥ 0} rendszernek akkor és csak akkor van olyan megoldása, amelyben az x pozitív változóinak megfelelő A-beli oszlopok lineárisan függetlenek, ha nem létezik olyan y, amelyre yA ≥ 0, yb < 0 és A-nak létezik r(A, b) − r(b) lineárisan független oszlopa, amelyekre y merőleges. •

TÉTEL A szimplex algoritmus a Bland kiválasztási szabállyal véges sok lépésben véget ér. •

2.6.2 Optimalizálás

Lemma 2.77 y_{1} csúcsa R^{∗}-nak.

OPTIMALIZÁLÁS GRÁFOKON

3.1 TELJESEN UNIMODULÁRIS MÁTRIXOK

Az A mátrixot akkor nevezünk teljesen unimodulárisnak, ha minden aldeterminánsa (0, ±1) értékű.

TÉTEL 3.1 (a) Digráf incidencia mátrixa teljesen unimoduláris. (b) Páros gráf incidencia mátrixa teljesen unimoduláris.

Hipergráfon egy (V, F) párt értünk, ahol V adott alaphalmaz, F pedig V részhalmazainak egy rendszere, amelyben ugyanaz a részhalmaz több példányban is szerepelhet. Az F tagjai a hipergráf hiperélei. Egy H hipergráfot akkor nevezzünk teljesen unimodulárisnak, ha H incidencia mátrixa teljesen unimoduláris. Egy hipergráfot laminárisnak mondunk, ha bármely két hiperéle vagy diszjunkt vagy az egyik tartalmazza a másikat.

A hálózati mátrixhoz legyen D olyan irányított gráf, amely irányítatlan értelemben összefüggő és legyen F egy feszítő fa. Az A mátrix sorai az F éleinek felelnek meg, míg az oszlopai az F -en kívüli éleknek. Minden uv nem-fa élre a fában egy egyértelmű (nem biztosan irányított) út vezet v-ből u-ba. ennek egy f elemére a mátrix a_{f,e} elemét definiáljuk 1-nek, ha f iránya megegyezik az útéval és −1-nek, ha azzal ellentétes. A mátrix minden más eleme 0.

Lemma 3.2 Hálózati mátrix részmátrixa is az. Hálózati mátrix sorát vagy oszlopát −1-gyel szorozva hálózati mátrixot kapunk.

TÉTEL 3.3 Az A hálózati mátrix teljesen unimoduláris.

Következmény 3.4 Egy olyan hipergráf, amely egy irányított fa élhalmazán van definiálva és a hiperélek irányított utak, teljesen unimoduláris.

TÉTEL 3.5 M teljesen unimoduláris.

3.2 A FARKAS LEMMA ÉS A DUALITÁS TÉTEL TU-MÁTRIXOKRA

Lemma 3.6 Tetszőleges M TU-mátrixszal megadott egyenlőtlenség-rendszer esetén, ha a jobboldali korlátozó b vektor egész, akkor minden erős bázis-megoldás egész.

Lemma 3.7 Legyen c tetszőleges (nem feltétlenül egészértékű) vektor. Bármely M TU-mátrixszal megadott K metszetkúpnak, ha van olyan x′ eleme, amelyre cx′ > 0, akkor K-nak van ilyen (0, ±1)-értékű eleme is.

TÉTEL 3.8 Tegyük fel, hogy az M = ( \begin{matrix}P \\ Q \end{matrix} ) mátrix teljesen unimoduláris. Ha a (??) primál probléma oldható meg

és a korlátozó b vektor egész, akkor (??)-nek van egész megoldása is. Ha az

y_{1} ≥ 0, yM = 0, yb < 0  (3.1)

duális probléma oldható meg, ahol y = (y_{0}, y_{1}), akkor van (0, ±1)-értékű y megoldás is (függetlenül b egészértékűségétől).

TÉTEL 3.9 Ha a max(cx : P x = b_{0}, Qx ≤ b_{1}) lineáris programozási problémának létezik megoldása, az M = ( \begin{matrix}P \\ Q \end{matrix} )

mátrix teljesen unimoduláris és b egész, akkor az optimum egész vektoron is felvétetik (függetlenül attól, hogy c egészértékű vagy sem).

TÉTEL 3.10 Tegyük fel, hogy R = {x : P x = b_{0}, Qx ≤ b_{1}} nemüres, b egész vektor, és M teljesen unimoduláris. A következők ekvivalensek.

(1) {cx : x ∈ R} felülről korlátos.

(2) Nem létezik olyan (0, ±1)-értékű x′ vektor, amelyre P x′ = 0, Qx′ ≤ 0, és cx′ > 0.

(3) Létezik olyan y = (y_{0}, y_{1}) vektor, amelyre y_{1} ≥ 0 és yM = c, és amely egész, amennyiben c egész. • TÉTEL 3.11 Tegyük fel, hogy az R := \{x : P x = b_{0}, Qx ≤ b_{1})\} poliédernek x^{∗} egy eleme, az M = ( \begin{matrix}P \\ Q \end{matrix} ) mátrix

teljesen unimoduláris és b egész. Jelölje Q_{∗}^{=} azon részmátrixát Q-nak, amely sorainak megfelelő egyenlőtlenségeket x^{∗} egyenlőséggel teljesíti. A következők ekvivalensek.

(1) x^{∗} maximalizálja cx-t R fölött.

(2) Nem létezik olyan (0, ±1)-értékű x′ vektor, amelyre P x′ = 0, Q_{∗}^{=}x′ ≤ 0, és cx′ > 0.

(3) Létezik olyan y = (y_{0}, y_{1}) vektor, amelyre y_{1} ≥ 0 yM = c, y(B − Mx^{∗}) = 0, és y egész, amennyiben c egész. •

TÉTEL 3.12 (Kőnig) Páros gráfban a független élek maximális ν száma egyenlő az éleket lefogó pontok minimális τ számával.

TÉTEL 3.13 (Egerváry) Páros gráfban egy párosítás maximális költsége egyenlő min(∑_{v∈V} π(v) : π ≥ 0, π(u) + π(v) ≥ c(uv) minden uv élre). Ha c egészértékű, az optimális π is választható egészértékűnek. •

3.3 KEREKÍTÉS ÉS EGYENLETES SZÍNEZÉS

Akkor mondjuk, hogy egy z egész szám az x szám kerekítése, ha |x − z| < 1. A z vektor az x vektor kerekítése, ha minden komponense kerekítés. Egy x nem-egész szám ⌊x⌋ alsó egész részén a legnagyobb x-nél kisebb egész számot értjük, míg ⌈x⌉ felső egész részen a legkisebb x-nél nagyob számot.

Lemma 3.14 Legyen A teljesen unimoduláris mátrix és x_{0} egy vektor. Ekkor létezik egy olyan q egészértékű vektor, amelyre ⌊x_{0}⌋ ≤ q ≤ ⌈x_{0}⌉ és ⌊Ax_{0}⌋ ≤ Aq ≤ ⌈Ax_{0}⌉ . Más szóval az x_{0}-nak van olyan q kerekítése, hogy az A minden a sorára aq kerekítése ax_{0}-nak.

TÉTEL 3.15 Tetszőleges m × n-es B mátrixnak van olyan kerekítése, hogy a következő mennyiségek mind egynél kevesebbel változnak: minden sorösszeg, minden oszlopösszeg, az első j sor elemeinek összege (j = 1, 2, …, m), az első i oszlop elemeinek összege (i = 1, 2, …, n).

TÉTEL 3.16 Legyen A TU-mátrix, b egész vektor, k pozitív egész. Legyen z olyan egész vektor, amelyre Az ≤ kb. Ekkor z előáll olyan z_{1}, z_{2}, …, z_{k} egész vektorok összegeként, melyekre Az_{i} ≤ b.

Következmény 3.17 Ha z ≥ 0 olyan egész vektor, amelyre kb_{1} ≤ Az ≤ kb_{2}, akkor z felbomlik olyan z_{1}, z_{2}, …, z_{k} egész vektorok összegére, melyekre z_{i} ≥ 0, és b_{1} ≤ Az_{i} ≤ b_{2}.

Az A oszlopainak egy partícióját (”színezését”) A_{1}, A_{2}, …, A_{k} részre akkor nevezzük egyenletesnek, ha A minden a sorára érvényes, hogy a sornak az egyes A_{i} részekbe eső elemeinek összege minden A_{i}-re lényegében ugyanaz, tehát ⌊1a/k⌋ vagy ⌈1a/k⌉ .

TÉTEL 3.18 Az A TU-mátrix oszlopainak létezik egyenletes k színezése.

Következmény 3.19 Egy páros gráf éleit meg lehet k színnel úgy színezni, hogy minden v csúcsra és mindegyik j színre (j = 1, …, k) a v-be menő d(v) darab él közül ⌊d(v)/k⌋ vagy ⌈d(v)/k⌉ darab színe j. Ha k-t a maximális fokszámnak választjuk, akkor megkapjuk Kőnig élszínezési tételét, amely szerint páros gráf kromatikus indexe (élszínezési száma) a maximális fokszámmal egyenlő. Ha k-t a minimális δ fokszámnak választjuk, akkor Gupta egy tételét kapjuk, amely szerint G páros gráf élhalmaza felbontható δ részre úgy, hogy mindegyik rész fedi az összes pontot. •

Következmény 3.20 Adott egy F irányított fa (speciális esetben irányított út) és F irányított részútjainak egy P := {P_{1}, …, P_{t}} rendszere, ahol minden utat F -élek egy részhalmazának tekintünk. P tagjai megszínezhetők k színnel (minden k pozitív egészre) úgy, hogy F minden e élére az e-t tartalmazó egyszínű utak száma minden színre lényegében ugyanannyi, ahol a ”lényegében ugyanannyi” azt jelenti, hogy bármely két színosztályra az eltérés legfeljebb egy lehet. •

Következmény 3.21 Adott egy F irányított fa és F irányított részútjainak egy P := {P_{1}, …, P_{t}} rendszere, ahol minden utat F -élek egy részhalmazának tekintünk. Az F élei megszínezhetők k színnel (minden k pozitív egészre) úgy, hogy P minden tagjában a színek lényegében egyenletes számban fordulnak elő. •

3.4 ÁRAMOK ÉS FOLYAMOK

Jelöljön D = (V, E) egy irányított gráfot. Legyen f : E → R ∪ {−∞} alsó kapacitás, g : E → R ∪ {+∞} felső kapacitás úgy, hogy f ≤ g. Valamely x : E → R vektorra és S ⊆ V részhalmazra legyen ϱ_{x}(S) := ∑(x(uv) : uv ∈ E, uv belép S-be) és legyen δ_{x}(S) := ϱ_{x}(V − S). Az x vektort áramnak (circulation) nevezzük, ha teljesül a rá megmaradási szabály (conservation rule), azaz ϱ_{x}(v) = δ_{x}(v) fennáll minden v csúcsra. Az x áramot megengedettnek (feasible) mondjuk, ha f ≤ x ≤ g.

TÉTEL 3.22 Tegyük fel, hogy f és g egész. A megengedett áramok halmaza, amennyiben nemüres, egész poliéder.

TÉTEL 3.23 (Alan Hoffman, 1960) Akkor és csak akkor létezik megengedett áram, ha

ϱ_{f} (X) ≤ δ_{g}(X) minden X ⊆ V halmazra.  (3.2)

Továbbá, ha f és g egészértékűek és (3.2) fennáll, akkor létezik egészértékű megengedett áram is.

γ(X) := δ_{g}(X) − ϱ_{f} (X).

Lemma 3.24 γ(X) + γ(Y) = γ(X ∩ Y) + γ(X ∪ Y) + d_{g−f} (X, Y).

TÉTEL 3.25 Akkor és csak akkor létezik olyan π : V → R vektor (amely ráadásul egészértékű, ha f és g is az), amelyre f(uv) ≤ π(v) − π(u) ≤ g(uv) minden e = uv élre, ha a c′-vel élsúlyozott D′ segédgráfban nincsen negatív kör, ahol uv akkor eleme D′-nek, ha vagy uv ∈ E és ekkor c′(uv) := g(uv), vagy vu ∈ E és ekkor c′(uv) := −f(vu).

TÉTEL 3.26 Adott c : E → R költség-függvényre akkor és csak akkor létezik olyan (megengedett potenciálnak nevezett) π : V → R vektor, amelyre π(v)−π(u) ≤ c(uv) minden e = uv élre, ha nem létezik negatív költségű irányított kör. Amennyiben c egészértékű, úgy a potenciál is választható annak.

TÉTEL 3.27 Feltéve, hogy létezik megengedett áram, a következők ekvivalensek.

(a) cx korlátos alulról,

(b) nincs negatív összköltségű irányított kör D′-ben,

(c) létezik egy olyan π : V → R függvény, amelyre

π(v) − π(u) ≤ c(uv), ha uv ∈ E és g(uv) = ∞,

és

π(v) − π(u) ≥ c(uv), ha uv ∈ E és f(uv) = −∞.

Biz. A (b) és (c) feltételek ekvivalenciája következik a 3.25

TÉTEL 3.28 Adott x megengedett áram esetén a következők ekvivalensek.

(a) x optimális megoldása (??)-nak,

(b) D_{x}-ben nem létezik negatív összköltségű irányított kör,

(c) létezik egy olyan π : V → R függvény, amelyre

π(v) − π(u) ≤ c(uv), ha uv ∈ E és x(uv) < g(uv),

és

π(v) − π(u) ≥ c(uv), ha uv ∈ E és x(uv) > f(uv). •

TÉTEL Hálózati mátrixokkal megadott lineáris programok megoldhatók áram problémaként.

TÉTEL 3.29 (Maximális-Folyam Minimális-Vágás) Akkor és csak akkor létezik k nagyságú megengedett folyam, ha minden S st̄-halmazra δ_{g}(S) ≥ k. Ha e feltétel teljesül, és g egészértékű, k pedig egész, úgy a folyam is választható egészértékűnek.

TÉTEL 3.30 A megengedett st-folyamok maximális nagysága egyenlő a δ_{g}(S) értékek minimumával, ahol a minimum az összes st̄-halmazra megy. Ha g egészértékű, úgy a maximum egészértékű folyamon is felvétetik.

Lemma 3.31 (a) Ha x M-nagyságú megengedett st-folyam D′-ben (a g′ kapacitásra vonatkozóan), akkor f + x (az eredeti A-ra megszorítva) megengedett áram.

(b) Ha δ_{g′}(X + s) < M valamely X ⊆ V halmazra, akkor X megsérti a Hoffman féle (3.2) feltételt.

3.5 LEGRÖVIDEBB SÉTÁK ÉS UTAK

Digráfban sétán egy olyan v_{0}, e_{1}, v_{1}, e_{2}, …, e_{k}, v_{k} sorozatot értünk, amelyben felváltva következnek pontok és élek, és mindegyik e_{i} él a v_{i−1} pontból vezet a v_{i} pontba. A séta zárt, ha v_{0} = v_{k}. A szereplő élek száma a séta hossza. Azt mondjuk, hogy v_{0} a séta kezdőpontja, v_{k} a séta végpontja. Amenyiben nincs ismétlődés, útról beszélünk. Egy s-ből v-be vezető utat sv-útnak fogunk hívni.

3.5.1 Nemnegatív költségek: Dijkstra algoritmusa

Legyen c nemnegatív. Egy s gyökerű fenyőn, röviden s-fenyőn egy olyan irányított fát értünk, amelynek minden pontja az s-ből irányított úton elérhető. Amennyiben a fenyő minden v pontjára az s-ből odavezető út a D digráf egy legolcsóbb s-ből v-be vezető útja, úgy legolcsóbb utak egy s-fenyőjéről beszélünk. Jelölje w_{n}(v) az s-ből v be vezető legolcsóbb út költségét.

Lemma 3.32 Legyen T egy legolcsóbb utak s-fenyője és tegyük fel, hogy az m_{T} := min(w_{n}(u) + c(uv) : uv kilép T -ből) minimum valamely a = u_{a}v_{a} élen vétetik fel. Ekkor T′ := T + a is legolcsóbb utak fenyője.

3.5.2 Konzervatív költségek

TÉTEL 3.33 Egy c súlyozás akkor és csak akkor konzervatív, ha létezik olyan π : V → R megengedett potenciálnak nevezett függvény a csúcsokon, amelyre

π(v) − π(u) ≤ c(uv) fennáll minden uv élre.  (3.3)

Továbbá, ha c egészértékű, akkor π is választható annak.

Következmény 3.34 l megengedett potenciál.

Egy uv élt a továbbiakban pontosnak fogunk hívni (π-re nézve), ha (3.3)-et egyenlőséggel teljesíti. Tetszőleges π potenciál által definiált t(uv) := π(v) − π(u) költség-függvényt potenciál-különbségnek vagy tenziónak nevezünk.

TÉTEL 3.35 Konzervatív c súlyozás esetén az s-ből t-be vezető utak súlyának l(t) minimuma egyenlő π(t) − π(s) maximumával, ahol a maximum az összes megengedett π potenciálon veendő.

Következmény 3.36 Ha P olyan st-út, amely valamely megengedett π potenciálra nézve pontos élekből áll, akkor P legolcsóbb st-út. •

3.5.3 Aciklikus digráfok: a kritikus út módszere

3.6 A MAGYAR MÓDSZER

3.6.1 Maximális elemszámú párosítások

TÉTEL 3.37 (Kőnig Dénes) Egy G = (S, T; E) páros gráfban a diszjunkt élek maximális ν = ν(G) száma egyenlő az éleket lefogó pontok minimális τ = τ(G) elemszámával.

TÉTEL 3.38 Egy G = (S, T; E) páros gráfban akkor és csak akkor létezik S-t fedő párosítás, ha teljesül a Hall-féle feltétel:

|Γ(X)| ≥ |X| minden X ⊆ S részhalmazra,  (3.4)

ahol Γ(X) jelöli azon T -beli pontok halmazát, melyeknek van szomszédja X-ben.

Definiáljuk egy X ⊆ S halmaz hiányát a h(X) := (|X| − |Γ(X)|) értékkel és legyen μ = μ(G, S) a maximális hiány, azaz

μ := max_{X⊆S} h(X)  (3.5)

TÉTEL 3.39 Egy G = (S, T; E) páros gráfban egy párosítás által nem fedett S-beli pontok minimális száma egyenlő μ-vel.

Lemma 3.40 F zárt a metszet és unió képzésre.

Lemma 3.41 Legyen K ⊆ S a legszűkebb max-hiányú halmaz G-ben. Ha a gráfból kitöröljük az összes olyan élt, amely Γ(K) és S − K között vezet, akkor a létrejövő G′ gráfban a maximális hiány ugyanaz, mint G-ben. Továbbá G és G′ max-hiányú halmazainak rendszere ugyanaz.

3.6.2 Maximális súlyú párosítások

Nevezzünk egy pontokon értelmezett π függvényt súlyozott lefogásnak, ha minden uv élre π(u)+π(v) ≥ c(uv). Egy élt pontosnak fogunk nevezni (π-re nézve), ha itt egyenlőség áll. A π súlyozott lefogás π(V) súlyán a ∑(π(v) : v ∈ A∪B) összeget értjük.

TÉTEL 3.42 (Egerváry) tegyük fel, hogy a G = (S, T; E) páros gráfnak létezik teljes párosítása. A teljes párosítások maximális ν_{c} súlya egyenlő a súlyozott lefogások minimális τ_{c} súlyával. Amennyiben c egészértékű, az optimális π is választható egészértékűnek.

TÉTEL 3.43 Egy G′ = (S′, T′; E′) páros gráfban nemnegatív c súlyfüggvény esetén a párosítások maximális ν′_{c} súlya egyenlő a nemnegatív (!) súlyozott lefogások minimális τ′_{c} súlyával. Amennyiben c egészértékű, az optimális π′ is választható egészértékűnek.

3.7 A NÖVELŐ UTAK MÓDSZERE

Az optimalitási feltételek:

(a) x(a) = g(a) minden a élre, amely kilép S-ből, és

(b) x(a) = 0 minden a élre, amely belép S-be.

x folyamra legyen D_{x} = (V, A_{x}) a következő. Egy uv él A_{x}-hez tartozik, ha vagy (i) uv ∈ A és x(uv) < g(uv), és ekkor ezen élét D_{x}-nek előre élnek hívjuk, vagy (ii) vu ∈ A és x(vu) > 0, és ekkor uv neve hátra él. Jelölje S az s-ből D_{x}-ben elérhető pontok halmazát.

1. Eset t ∉ S, azaz t nem érhető el s-ből.

2. Eset t ∈ S, azaz t elérhető s-ből.

3.7.1 A skálázási technika 3.7.2 Legrövidebb növelő utak

Jelölje σ_{x}(v) a v távolságát D_{x}-ben s-től. Lemma 3.44 Amikor P mentén végrehajtunk egy növelést, a σ_{x}(v) érték semmilyen v-re sem csökken. Lemma 3.45 Egy fázison belül legfeljebb |A| növelésre kerülhet sor.

3.8 MINIMÁLIS KÖLTSÉGŰ FOLYAMOK

Egy z folyam költségét a cz = ∑(c(e)z(e) : e ∈ A) skaláris szorzattal definiáljuk. A z st-folyam minimális költségű folyam, ha z a legkisebb költségű a z-vel azonos nagyságú megengedett st-folyamok közül.

Legyen π : V → Z_{+} olyan függvény a V -n, amelyre π(s) = 0 ≤ π(v) ≤ π(t) minden v ∈ V -re. Ilyen függvényt potenciálnak hívunk. c̄(uv) = c(uv) − π(v) + π(u). Optimalitási feltételek:

π(v) − π(u) < c(uv) ⇒ z(uv) = 0,  (i)
π(v) − π(u) > c(uv) ⇒ z(uv) = g(uv).  (ii)

ITERATÍV LÉPÉS z folyam és a π potenciálra legyen D′ = (V, A′)-ben egy uv él előre él, ha uv ∈ A, c̄(uv) = 0 és z(uv) < g(uv). Egy uv él hátra él, ha vu ∈ A, c̄(vu) = 0 és z(vu) > 0.

1. Eset t ∉ S, azaz t nem elérhető s-ből. Állítás 3.46 A módosított potenciál és a változatlanul hagyott z folyam kielégíti az optimalitási feltételeket.

2. Eset t ∈ S, vagyis t elérhető s-ből. Állítás 3.47 A módosított folyam és változatlanul hagyott potenciál kielégíti az optimalitási feltételeket.