1. Fejezet

LINEÁRIS ALGEBRA ÉS LINEÁRIS EGYENLETRENDSZEREK

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

1.2 MÁTRIXOK, EGYENLETRENDSZEREK MEGOLD-HATÓSÁGA

Lemma 1.1 Ha a z ∈ Rn 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 A1 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.

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.

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.

1.3 EGYENLETRENDSZER MEGOLDÁS-HALMAZA, AF-FIN ALTEREK

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 A1, míg a maradékot A2. Tegyük fel, hogy az A1 minden sora ortogonális A2 minden sorára. Ekkor A1 sortere éppen az A2 nulltere és A1 nulltere éppen az A2 sortere.

TÉTEL 1.12 Legyen A1 olyan m × n-es mátrix (m < n), amelynek sorai lineárisan függetlenek. Ekkor létezik olyan (n − m) × n méretű A2 mátrix, amelynek sorai ortogonálisak az A1 soraira és amely az A1-gyel együtt egy n × n-es nem-szinguláris mátrixot alkot. Az A1 sortere az A2 nulltere, és A1 nulltere az A2 sortere.

TÉTEL 1.13 Tegyük fel, hogy az Ax = b egyenletrendszernek x0 megoldása. Ekkor a megoldások M := {x : Ax = b} halmaza az Rn 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 x0-hoz adva megoldást kapunk, és M minden tagja így áll elő. Megfordítva, minden affin altér előáll egy lineáris egyenletrendszer megoldás-halmazaként.

Következmény 1.14 Amennyiben az Ax = b egyenletrendszernek x0 egy megoldása, úgy a megoldások halmaza előáll mint véges sok vektor

lineáris kombinációi halmazának x0-lal történő eltolásával, azaz {yB + x0 : y ∈ Rn} alakban. •

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

LINEÁRIS EGYENLŐTLENSÉG-RENDSZEREK

2.1 BEVEZETÉS

2.1.1 Megjegyzések az intuícióról

2.2 KÚPOK, POLIÉDEREK, POLITOPOK

2.2.1 Kúpok 2.2.2 Poliéderek és politopok

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

2.3 A FOURIER-MOTZKIN ELIMINÁCIÓ

2.3.1 Oszlop elimináció

TÉTEL 2.2 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.3 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 a (2.4) rendszernek 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.4 Metszetkúp  tengelymenti  (külső  vagy  belső)  vetülete  metszetkúp.  Poliéder

tengelymenti vetülete poliéder.

TÉTEL 2.5 Egy politop és egy generált kúp összege poliéder. Speciálisan, minden politop korlátos poliéder és minden generált kúp előáll metszetkúpként.

TÉTEL 2.6 (Farkas lemma, geometriai alak) Ha egy C ⊆ Rk generált kúp nem tartalmaz valamely b ∈ Rk elemet, akkor létezik olyan (zárt) homogén féltér, amely magában foglalja C-t, de nem tartalmazza b-t. Ha egy P politop nem tartalmazza b-t, akkor létezik olyan féltér, amely magában foglalja P -t, de nem tartalmazza b-t.

2.3.2 Az FM eljárás hatékonysága 2.3.3 A 2-SAT probléma 2.3.4 Egy ütemezési feladat

2.4 POLIÉDEREK SZERKEZETE ÉS ELŐÁLLÍTÁSA

2.4.1 A poliéder egyenesei

TÉTEL 2.7 Valamely q ≠ 0 vektorra a következők ekvivalensek:

(1) Qq = 0.

(2) q karakterisztikus vektora R-nek.

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

Következmény 2.8 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.

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

2.4.2 Bázis-megoldások

TÉTEL 2.10 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.11 Egy z ∈ R elem szintje csak a poliédertől függ és nem a poliédert meghatározó egyenlőtlenség-rendszer konkrét alakjától. Speciálisan, a bázis-megoldás fogalma is csak a poliédertől függ.

TÉTEL 2.12 Minden nemüres poliédernek létezik bázis-megoldása, nevezetesen bármely minimális szintű elem bázis-megoldás.

TÉTEL 2.13 (i) Egy M = (\begin{matrix}P \\ Q \end{matrix}) nem-nulla mátrix esetén a

P x = b0, Qx ≤ b1  (2.5)

lineáris rendszernek egy z megoldása akkor bázis-megoldás, ha r(M) = r(M= z).

(ii) 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.

(iii) Az {yA ≥ 0, yb = −1} rendszer egy y0 megoldása akkor és csak akkor bázis-megoldás, ha az A-ból lineárisan függetlenül kiválasztható, az y0-ra merőleges oszlopok maximális száma r(A, b) − 1.

2.4.3 Csúcsos poliéderek

TÉTEL 2.14 Az R = {x : Qx ≤ b} poliéder egy z elemére a következők ekvivalensek:

(0) Q oszlopai lineárisan függetlenek és z bázis-megoldás.

(1) Q= z oszlopai lineárisan függetlenek, azaz Q-nak van n lineárisan független z-aktív sora.

(2) z csúcs.

(3) z extrém pont.

Következmény 2.15 Egy poliédernek legfeljebb véges sok csúcsa van.

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

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

(2) R egyenes-mentes.

(3) Az R karakterisztikus altere triviális.

(4) R csúcsos.

TÉTEL 2.17 Az R = {x : Qx ≤ b} nemüres poliéder az A := {x : Qx = 0} karakterisztikus altér és az R′ := R ∩ A⊥ poliéder ö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.18 Egy R := {x : Mx ≤ 0} metszetkúp az A := {x : Mx = 0} karakterisztikus altér (ami speciális metszetkúp) és az R′ := R ∩ A⊥ csúcsos metszetkúp vektor-összege.

2.4.4 Korlátos poliéderek

TÉTEL 2.19 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.

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

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

(1) R nem tartalmaz félegyenest.

(2) R-nek véges sok csúcsa van, melyek konvex burka R.

(3) R korlátos.

(4) R karakterisztikus kúpja triviális.

TÉTEL 2.22 (**) Legyen a C := {x : Qx ≤ 0} nemtriviális kúp egyenes-mentes (=csúcsos), és legyen Z := {x : Qx ≤ 0, cx = −1} poliéder, ahol c a Q sorainak az összege. Ekkor tetszőleges z ∈ Z esetén z⃗ a kúp iránya, és a kúp tetszőleges q⃗ iránya egyetlen z pontban metszi Z-t. Z korlátos és egy z ∈ Z pont akkor és csak akkor csúcsa Z-nek, ha z⃗ extrém iránya C-nek.

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

TÉTEL 2.24 (*) A C = {x : Qx ≤ 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 a Q mátrix r(Q) − 1(= n − 1) lineárisan független sorára, azaz ha r(Q= z) = n − 2.

2.4.5 Poliéderek előállítása

Lemma 2.25 Amennyiben az A mátrix sorai által generált kúp megegyezik a B mátrix sorai által definiált metszetkúppal, azaz GA = MB, úgy MA = GB.

TÉTEL 2.26 Minden metszetkúp előáll generált kúpként.

TÉTEL 2.27 Minden nemüres poliéder előáll mint egy politop és egy generált kúp összege. Speciálisan, minden korlátos poliéder politop.

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

Következmény 2.29 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. •

2.5 MEGOLDHATÓSÁG: A FARKAS LEMMA

TÉTEL 2.30 (Farkas lemma, standard alak) Az {Ax = b, x ≥ 0} rendszernek pontosan akkor van megoldása, ha az {yA ≥ 0, yb < 0} rendszernek nincs. TÉTEL 2.31 (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.32 (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.33 A

{P x = b0, Qx ≤ b1}  (2.6)

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

{y0P + y1Q = 0, y1 ≥ 0, yb = −1}  (2.7)

duális nem, ahol y = (y0, y1,), b = (b0, b1). TÉTEL 2.34 (Farkas lemma, általános alak) A

P x0 + Ax1 = b0, Qx0 + Bx1 ≤ b1, x1 ≥ 0  (2.8)

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

y0P + y1Q = 0, y0A + y1B ≥ 0, y1 ≥ 0, yb := y0b0 + y1b1 = −1  (2.9)

duális rendszernek van. 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) − 1 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). •

2.5.1 Direkt bizonyítás

TÉTEL 2.36 A

P x0 + Ax1 = b, x1 ≥ 0  (2.10)

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

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

duális feladatnak van. TÉTEL 2.37

y0P ′ + y1Q′ = c′0, y0A′ + y1B′ ≥ c′1, y1 ≥ 0  (2.12)

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

P ′x0 + A′x′1 = 0, Q′x0 + B′x′1 ≤ 0, x′1 ≥ 0, c′0x0 + c′1x′1 > 0  (2.13)

duális rendszernek van. •

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

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

2.5.3 Alkalmazások

TÉTEL 2.39 Ha egy n-változós lineáris egyenlőtlenség-rendszernek nincsen megoldása, akkor van egy legfeljebb n + 1 egyenlőtlenségből álló részrendszer úgy, hogy már annak sincsen megoldása. TÉTEL 2.40 (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. TÉTEL 2.41 Ha R és R′ két nemüres poliéder, melyek metszete üres, akkor van őket szigorúan elválasztó {x : cx = α} hipersík, azaz cx < α < cx′ fennáll az R minden x és az R′ minden x′ elemére. TÉTEL 2.42 (Helly) Az n-dimenziós térben adottak a C1, …, Ck konvex halmazok, melyek metszete üres. Ekkor ezen halmazok között létezik már legfeljebb n + 1 olyan is, amelyek metszete üres. TÉTEL 2.43 (Kirchberger) Az n dimenziós térben adott k piros és l zöld pont, ahol k + l ≥ n + 2. Amennyiben a piros pontokat nem lehet a zöld pontoktól egy hipersíkkal elválasztani, úgy a pontok között létezik legfeljebb n + 2 úgy, hogy már ezeket sem lehet hipersíkkal elválasztani. TÉTEL 2.44 (*) Ha az A n×n-es nemnegatív mátrix minden oszlopában az elemek összege 1, akkor az {Ax = x, enx = 1, x ≥ 0} rendszernek létezik megoldása, ahol en = (1, …, 1).

2.6 IRÁNYMENTI KORLÁTOSSÁG

2.6.1 Erős bázis-megoldások

TÉTEL 2.45 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.46 Az erős bázis-megoldás fogalma csak a poliédertől függ és nem a poliédert meghatározó egyenlőtlenség-rendszertől. • Következmény 2.47 A {P x = b0, Qx ≤ b1} 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.48 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.49 Tetszőleges egyenlőtlenség-rendszernek legfeljebb csak véges sok erős bázis-megoldása van. •

2.6.2 Az iránymenti korlátosság feltétele

Lemma 2.50 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.

TÉTEL 2.51 (Az iránymenti korlátossági tétele, 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.52 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.53 Ha egy egyenlőtlenség-rendszer megoldható, akkor van erős bázis-megoldása is.

TÉTEL 2.54 (Az iránymenti korlátossági tétele) Tegyük fel, hogy az R poliéder nemüres, és legyen c = (c0, c1) 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 (??)-nek olyan x∗ erős bázis-megoldása, amelyre cx∗ ≥ cz.

(2) Nem létezik olyan q = (q0, q1) vektor, amelyre cq > 0, és q1 ≥ 0, P q0 + Aq1 = 0, Qq0 + Bq1 ≤ 0.

(3) Létezik olyan y = (y0, y1) vektor, amelyre

y0P + y1Q = c0, y0A + y1B ≥ c1, y1 ≥ 0. •  (2.14)

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

2.7.1 Optimalitási feltételek

TÉTEL 2.55 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{= \atop x∗} x′ ≤ 0 és cx′ > 0.

(3) A c vektor benne van x∗ aktív sorainak kúpjában. Más szóval, van olyan y∗ vektor, amely kielégíti az

y∗ ≥ 0, y∗Q = c  (2.15)

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

y∗(i) > 0 ⇒ iqx∗ = b(i)  (2.16)

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.15) fennállása esetén (2.16) azzal ekvivalens, hogy

cx∗ = by∗,  (2.17)

továbbá azzal, hogy

y∗(b − Qx∗) = 0.  (2.18)

TÉTEL 2.56 Tegyük fel, hogy a

P x0 + Ax1 = b0, Qx0 + Bx1 ≤ b1, x1 ≥ 0  (2.19)

rendszerrel definiált R poliéder nemüres és {cx = c0x0 + c1x1 : x ∈ R} felülről korlátos. Legyen x∗ = (x∗ 0, x∗ 1) az R egy eleme, és jelölje

(Q{= \atop x∗} , B{= \atop x∗}) 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{= \atop 1∗} jelölje a b1 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 x0 + Ax1 = b0, Q{= \atop x∗} x0 + B{= \atop x∗} x1 ≤ b{= \atop 1∗}  (2.20)

és

x∗ 1(i) = 0 ⇒ x′1(i) ≥ 0.  (2.21)

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

y∗ 1 ≥ 0, y∗ 0P + y∗ 1Q = c0, y∗ 0A + y∗ 1B ≥ c1  (2.22)

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

x∗ 1(j) > 0 ⇒ y∗ 0aj + y∗ 1bj = c1(j)  (2.23)

valamint az

y∗ 1(i) > 0 ⇒ iqx∗ 0 + ibx1 = b1(i),  (2.24)

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

cx∗ = by∗,  (2.25)

és azzal, hogy

y∗(b − Mx∗) = 0,  (2.26)

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

2.7.2 A dualitás tétel

TÉTEL 2.57 (Dualitás tétel, szimmetrikus 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.51 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}.

TÉTEL 2.58 (Dualitás tétel) Tegyük fel, hogy a (??) rendszer által definiált R primál poliéder nemüres. Tegyük fel továbbá, hogy a cx = c0x0 +c1x1 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 (??) primál optimalizálási feladatban a maximum egyenlő a (??) duál feladatban szereplő minimummal.

TÉTEL 2.59 (Dualitás tétel, szimmetrikus alak) Tegyük fel, hogy mind az R := {x : Bx ≤ b, x ≥ 0} primál, mind az R∗ := {y : 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.7.3 Következmények

TÉTEL 2.60 (Neumann) Tetszőleges m × n-es (m, n ≥ 1) 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, enx = 1} = max{(min yA) : y ≥ 0, emy = 1}, ahol ei az i-dimenziós csupa egyesből álló vektort jelenti.

TÉTEL 2.61 (Clark) Tekintsük a max{cx : x ≥ 0, Bx ≤ b} és min{by : y ≥ 0, yB ≤ c} primál-duál program párt, és tegyük fel, hogy mindegyik megoldható. Ekkor az R primál és az R∗ duál poliéderek közül az egyik nem korlátos.

2.8 POLIÉDEREK ELŐÁLLÍTÁSA

2.8.1 Oldalak

TÉTEL 2.62 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′ részmátrix, amelyre F = {x ∈ R : Q′x = b′}, ahol b′ a Q′ sorainak megfelelő részvektora b-nek.

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

TÉTEL 2.64 Tegyük fel, hogy az R poliéder egy minimális (??) 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.65 Minden minimális oldal affin altér. •

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

TÉTEL 2.67 (**) Tegyük fel, hogy (??) 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 (??)-nek), ha létezik olyan y0, amelyre y0P = a és y0b0 = β (azaz, ax = β lineáris következménye P x = b0-nak.)

Lemma 2.68 (**) Tegyük fel, hogy R egy minimális (??) 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{= \atop F}-nek és

r(Q′) = r(Q{= \atop F}).

TÉTEL 2.69 (*) 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.8.2 Dimenzió, lapok

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

Következmény 2.71 (**) Az R = {x : Qx ≤ b} nemüres poliédert tartalmazó legszűkebb affin altér ZR := {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.72 (**) Az R = \{x : Qx ≤ b\} poliéder egy F oldalát tartalmazó legszűkebb affin altér \{x : Q{= \atop F}x = b{= \atop F}\}. Az F oldal dimenziója

n − r(Q{= \atop F}). Minimális oldal dimenziója n − r(Q). •

TÉTEL 2.73 (**) A semleges vektorok SR altere éppen a Q-t tartalmazó legszűkebb ZR affin altér AR karakterisztikus alterének ortogonális kiegészítője. Egy c vektor akkor és csak akkor semleges, ha benne van Q= sorterében.

TÉTEL 2.74 (*) 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{= \atop 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 Qu és Qv n × n-es nemszinguláris részmátrixai, amelyekre u a Qux = bu rendszer, míg v a Qv x = bv rendszer egyértelmű megoldásai, és amelyeknek n − 1 soruk közös.

TÉTEL 2.75 (*) Tegyük fel, hogy a {P x = b0, Qx ≤ b1} 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 = b0}. Továbbá egy-egy értelmű kapcsolat áll fenn az R lapjai és a Qx ≤ b0 egyenlőtlenségei között, azaz {x ∈ R : iqx = b1(i)} lapot alkot, és minden lap előáll ilyen alakban.

Következmény 2.76 (*) Minden valódi oldal lapok metszete. •

Következmény 2.77 (*) Tegyük fel, hogy mind a {P x = b0, Qx ≤ b1} rendszer, mind a {P ′x = b′0, Q′x ≤ b′1} rendszer minimális. Az ezek

által definiált nemüres R és R′ poliéderek akkor és csak akkor egyenlők, ha P és P ′ sortere ugyanaz, továbbá a Qx ≤ b1 és Q′x ≤ b′1 rendszer

egyenlőtlenségei között egy-egy értelmű kapcsolat van, amelyben az egymásnak megfelelő qx ≤ β és q′x ≤ β′ egyenlőtlenségekre fennáll, hogy a (q, β) − (q′, β′) vektor benne van a (P, b0) mátrix sorterében (ami ugyanaz, mint a (P ′, b′0) mátrix sortere). •

2.9 A SZIMPLEX ALGORITMUS

2.9.1 Megengedettség

TÉTEL 2.78 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) − 1 lineárisan független oszlopa, amelyekre y merőleges. (Tömören, vagy a primál vagy a duál feladatnak létezik bázis-megoldása). •

2.9.2 Optimalizálás

Lemma 2.79 y1 csúcsa R∗-nak.

OPTIMALIZÁLÁS GRÁFOKON

3.1 A MAGYAR MÓDSZER

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

TÉTEL 3.1 (Kőnig) 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.

3.1.2 A Kőnig tétel ekvivalens alakja

Lemma 3.2 Egy-egy értelmű kapcsolat áll fenn az élek minimális elemszámú lefogásai és a max-hiányú S-beli halmazok között: ha L ⊆ S ∪ T minimális lefogás, akkor S − L max-hiányú halmaz, míg ha H ⊆ S max-hiányú halmaz, akkor Γ(H) ∪ (S − H) minimális lefogás.

TÉTEL 3.3 (Kőnig-Hall) G = (S, T; E) páros gráfban φ = μ, azaz egy párosítás által fedetlenül hagyott S-beli pontok minimális száma egyenlő az S részhalmazainak maximális hiányával. Speciálisan, akkor és csak akkor létezik S-t fedő párosítás, ha nincs hiányos halmaz, azaz teljesül a Hall-féle feltétel:

|Γ(X)| ≥ |X| minden X ⊆ S részhalmazra. •  (3.1)

Max-hiányú halmazok

Lemma 3.4 (*) Az S halmaz részhalmazain értelmezett γ(X) := |Γ(X)| függvény szubmoduláris, azaz az S bármely két X, Y részhalmazára fennáll a szubmodularitási egyenlőtlenség:

γ(X) + γ(Y ) ≥ γ(X ∩ Y ) + γ(X ∪ Y ).

Lemma 3.5 (*) A max-hiányú halmazok F rendszere zárt a metszet és unió képzésre.

TÉTEL 3.6 Kőnig alternáló utas algoritmusa által szolgáltatott (??)-beli H max-hiányú halmaz az egyértelmű legszűkebb max-hiányú halmaz (és így nem függ az algoritmus futása közben tett választásoktól).

Lemma 3.7 (**) Legyen H ⊆ S a legszűkebb max-hiányú halmaz G-ben. Ha a gráfból kitöröljük az összes olyan élt, amely H szomszédai és S − H 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.1.3 Maximális súlyú párosítások

TÉTEL 3.8 (Egerváry) A G = (S, T; E) teljes párosítással rendelkező páros gráfban a c ≥ 0 egészértékű súlyfüggvényre vonatkozó maximális súlyú teljes párosítás νc súlya egyenlő az egészértékű súlyozott lefogások minimális τc összértékével. Amennyiben G teljes páros gráf, úgy az optimális súlyozott lefogás választható nemnegatívnak is.

3.1.4 Egerváry algoritmusa

TÉTEL 3.9 (*) Amennyiben az Egerváry algoritmus futtatásakor a szóbanforgó π súlyozott lefogás javítására a Kőnig algoritmus által szolgáltatott egyértelmű legszűkebb max-hiányú X halmazt használjuk, úgy az algoritmus polinomiális futásidejű.

3.1.5 Kuhn Magyar Módszere 3.1.6 Maximális súlyú párosítások

TÉTEL 3.10 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 π′c is választható egészértékűnek.

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

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

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

3.2.2 Konzervatív költségek, megengedett potenciálok

TÉTEL 3.12 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.2)

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

TÉTEL 3.13 A D = (V, A) digráf élhalmazán adott két korlátozó függvény f ≤ g. 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 ∈ A és ekkor c′(uv) := g(uv), vagy vu ∈ A és ekkor c′(uv) := −f(vu).

Következmény 3.14 lc megengedett potenciál.

TÉTEL 3.15 Konzervatív c költségfüggvény esetén az s-ből t-be vezető utak költségének lc(t) minimuma egyenlő a π(t)−π(s) érték maximumával, ahol a maximum az összes megengedett π potenciálon veendő.

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

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

TÉTEL 3.17 Legyen c′ : A′ → R a D = (V, A′) aciklikus irányított gráf élhalmazán egy tetszőleges súlyfüggvény, és tegyük fel, hogy az s′ pontból vezet irányított út t′-be. Ekkor

min{π′(s′) − π′(t′) : π′(v) − π′(u) ≥ c′(uv), uv ∈ A} = max{c′(P) : P út s′-ből t′-be}.  (3.3)

3.3 ÁRAMOK ÉS FOLYAMOK HÁLÓZATOKBAN

3.3.1 Fogalmak

Áramok Folyamok

3.3.2 Motivációk

A szállítási probléma Egy teszt feladat Élidegen utak

3.3.3 Megengedett áramok

TÉTEL 3.18 (Hoffman, 1960) A D = (V, A) digráfban adott f ≤ g kapacitásfüggvényekre vonatkozólag akkor és csak akkor létezik megengedett áram, ha

ϱf (X) ≤ δg (X) minden X ⊆ V halmazra.  (3.4)

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

Lemma 3.19 γ(X) + γ(Y ) = γ(X ∩ Y ) + γ(X ∪ Y ) + dg−f (X, Y ).

3.3.4 Áramok és folyamok kapcsolata

TÉTEL 3.20 (Maximális-Folyam Minimális-Vágás) A D = (V, A) irányított gráfban akkor és csak akkor létezik a g kapacitásra vontakozó k nagyságú megengedett folyam, ha minden S st̄-halmazra δg (S) ≥ k. Ha e feltétel teljesül, g egészértékű és k egész, úgy a folyam is választható egészértékűnek.

TÉTEL 3.21 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.

Hoffman tétele az MFMC tételből

Lemma 3.22 (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.4) feltételt.

3.4 MAXIMÁLIS FOLYAM ALGORITMUSOK

3.4.1 A növelő utak módszere 3.4.2 Skálázási technika 3.4.3 Legrövidebb növelő utak

TÉTEL 3.23 Ha a Ford-Fulkerson féle növelő utas algoritmusban mindig a legrövidebb növelő utat használjuk, úgy az eljárás tetszőleges g kapacitásfüggvény esetén legfeljebb O(|V ||A|) növelés után véget ér.

Lemma 3.24 Amikor P mentén végrehajtunk egy növelést, a σx(v) érték semmilyen v-re sem csökken.

Lemma 3.25 Egy fázison belül legfeljebb |A| növelésre kerülhet sor.

3.5 MINIMÁLIS KÖLTSÉGŰ FOLYAMOK

Lemma 3.26 A Δπ pontindukált költségfüggvényre vonatkozólag minden k nagyságú megengedett folyamnak ugyanaz a költsége, éspedig kπ(t). TÉTEL 3.27 A D = (V, A) irányított gráf élhalmazán adott a g : A → Z+ egészértékű kapacitásfüggvény és a c : A → R+ költségfüggvény. A k nagyságú egészértékű megengedett folyamok költségének minimuma egyenlő a

kπ(t) + ∑[cπ (uv)g(uv) : uv ∈ A, cπ (uv) > 0]  (3.5)

érték maximumával, ahol a maximum az összes π potenciálra megy. Egy k nagyságú megengedett z folyam akkor és csak akkor minimális költségű a k nagyságú megengedett folyamok között, ha létezik olyan π potenciál, amelyre fennállnak a következő optimalitási feltételek:

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

Amennyiben c egészértékű, az optimális π is választható egészértékűnek. Állítás 3.28 A módosított potenciál és a változatlanul hagyott z folyam kielégíti az optimalitási feltételeket. Állítás 3.29 A módosított folyam és változatlanul hagyott potenciál kielégíti az optimalitási feltételeket.

3.6 TELJESEN UNIMODULÁRIS MÁTRIXOK

3.6.1 Definíciók és példák

TÉTEL 3.30 (a) Digráf incidencia mátrixa teljesen unimoduláris. (b) Páros gráf incidencia mátrixa teljesen unimoduláris. Lemma 3.31 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.32 Az A hálózati mátrix teljesen unimoduláris. Következmény 3.33 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.34 M teljesen unimoduláris. Lemma 3.35 Tetszőleges M TU-mátrixszal megadott egyenlőtlenség-rendszer esetén, ha a b jobboldali korlátozó vektor egész, akkor minden erős bázis-megoldás egész. Lemma 3.36 Legyen c tetszőleges (nem feltétlenül egészértékű) vektor. Bármely M TU-mátrixszal megadott K metszet-kúpnak, ha van olyan x′ eleme, amelyre cx′ > 0, akkor K-nak van ilyen (0, ±1)-értékű eleme is. TÉTEL 3.37 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

y1 ≥ 0, yM = 0, yb < 0  (3.6)

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

Az alábbi három tételben az M = (\begin{matrix}P \\ Q \end{matrix}) mátrix teljesen unimoduláris és b egész vektor. TÉTEL 3.38 Ha a max{cx : P x = b0, Qx ≤ b1} lineáris programozási problémának létezik megoldása, akkor az optimum egész vektoron is felvétetik (függetlenül attól, hogy c egészértékű vagy sem). Ekvivalens alakban: minden TU-mátrix és egész korlátozó vektor által megadott poliéder egész. TÉTEL 3.39 Tegyük fel, hogy R = {x : P x = b0, Qx ≤ b1} nemüres. 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 = (y0, y1) vektor, amelyre y1 ≥ 0 és yM = c, és amely egész, amennyiben c egész. • TÉTEL 3.40 Legyen x∗ az R := \{x : P x = b0, Qx ≤ b1)\} poliéder egy eleme. Jelölje Q{= \atop x∗} a Q aktív részmátrixát. 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{= \atop x∗} x′ ≤ 0, és cx′ > 0.

(3) Létezik olyan y = (y0, y1) vektor, amelyre y1 ≥ 0 yM = c, y(B − Mx∗) = 0, és y egész, amennyiben c egész. •

3.6.2 Kerekítés és egyenletes színezés

Kerekítés

Lemma 3.41 Legyen A teljesen unimoduláris mátrix és x0 egy vektor. Ekkor létezik egy olyan q egészértékű vektor, amelyre ⌊x0⌋ ≤ q ≤ ⌈x0⌉ és ⌊Ax0⌋ ≤ Aq ≤ ⌈Ax0⌉. Más szóval az x0-nak van olyan q kerekítése, hogy az A minden a sorára aq kerekítése ax0-nak. TÉTEL 3.42 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.43 Egy x1, … xn sorozat elemeinek létezik olyan z1, …, zn kerekítése, hogy minden 1 ≤ i ≤ j ≤ n indexre a zi + … + zj összeg kerekítése az xi + … + xj összegnek.

Egyenletes színezések

TÉTEL 3.44 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 z1, z2, …, zk egész vektorok összegeként, melyekre Azi ≤ b. Következmény 3.45 Ha z ≥ 0 olyan egész vektor, amelyre kb1 ≤ Az ≤ kb2, akkor z felbomlik olyan z1, z2, …, zk egész vektorok összegére, melyekre zi ≥ 0, és b1 ≤ Azi ≤ b2. TÉTEL 3.46 Az A TU-mátrix oszlopainak létezik egyenletes k-színezése.

Egy alkalmazás

Következmény 3.47 Adott egy F irányított fa (speciális esetben irányított út) és F irányított részútjainak egy P := {P1, …, Pt} 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.48 Adott egy F irányított fa és F irányított részútjainak egy P := {P1, …, Pt} 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ő. •

TU-mátrixok jellemzése

TÉTEL 3.49 (*) [Ghouila-Houri] (ejtsd: Gujla-úri) Egy Q mátrix akkor és csak akkor teljesen unimoduláris, ha oszlapainak bármely részhalmaza egyenletesen 2-színezhető.

3.7 HÁLÓZATI OPTIMALIZÁLÁS ÉS LINEÁRIS PRO-GRAMOZÁS

3.7.1 Páros gráfok

Optimális párosítások

TÉTEL 3.50 (Kőnig) A G = (S, T; E) 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.51 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. •

TÉTEL 3.52 A G páros gráf A incidencia mátrixával felírt

{x : Ax ≤ ep, x ≥ 0}  (3.7)

poliéder egész, amelynek csúcsai pontosan a gráf párosításainak incidencia vektorai. •

TÉTEL 3.53 (Birkhoff és Neumann) Egy mátrix akkor és csak akkor bisztochasztikus, ha permutáció mátrixok konvex kombinációja.

TÉTEL 3.54 (Egerváry) A G = (S, T; E) teljes párosítással rendelkező páros gráfban a c ≥ 0 súlyfüggvényre vonatkozó maximális súlyú teljes párosítás νc súlya egyenlő a súlyozott lefogások minimális τc összértékével. Amennyiben G teljes páros gráf, úgy az optimális súlyozott lefogás választható nemnegatívnak is. Amennyiben c egészértékű az optimális súlyozott lefogás is választható annak.

Páros gráf fokszámkorlátozott részgráfjai: a szállítási probléma

3.7.2 Élszínezések

TÉTEL 3.55 Egy G = (S, T; E) 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. Ráadásul még azt is megkövetelhetjük, hogy minden színosztály mérete közel ugyanakkora legyen, vagyis ⌊|E|/k⌋ vagy ⌈|E|/k⌉. 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. •

TÉTEL 3.56 (**) [Folkman és Fulkerson] Egy G = (S, T; E) páros gráfban akkor és csak akkor létezik l darab élidegen k élű párosítás, ha

iG(Z) ≥ l(k + |Z| − |U|)  (3.8)

fennáll U := S ∪ T minden Z részhalmazára, ahol iG(Z) jelöli a Z által feszített élek számát.

3.7.3 Megengedett potenciálok, legolcsóbb utak

TÉTEL 3.57 Adott c : A → R költség-függvényre akkor és csak akkor létezik olyan π : V → R vektor, amelyre π(v) − π(u) ≤ c(uv) minden e = uv ∈ A élre, ha c konzervatív, azaz 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.58 Konzervatív c költségfüggvény esetén az s-ből t-be vezető utak költségének lc(t) minimuma egyenlő π(t) − π(s) maximumával, ahol a maximum az összes megengedett π potenciálon veendő.

3.7.4 Megengedett áramok és folyamok

TÉTEL 3.59 Ha f ≤ g egészértékű, akkor a megengedett áramok {x : Qx ≤ 0, f ≤ x ≤ g} poliédere, amennyiben nemüres, egész poliéder.

TÉTEL 3.60 A D = (V, A) digráf élhalmazán adott a g ≥ 0 egész kapacitásfüggvény. Legyen s és t két kijelölt csúcs, melyekre ϱ(s) = 0 = δ(t).

A k nagyságú megengedett folyamok {x ∈ RA : 0 ≤ x ≤ g, ϱx(v) = δx(v) minden v ∈ V − {s, t}-re, δx(s) = k} poliédere, amennyiben nemüres, egész poliéder. •

TÉTEL 3.61 (Hoffman, 1960) A D = (V, A) digráfban adott f ≤ g kapacitásfüggvényekre vonatkozólag akkor és csak akkor létezik megengedett áram, ha

ϱf (X) ≤ δg (X) minden X ⊆ V halmazra.  (3.9)

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

3.7.5 Minimális költségű áramok

Korlátosság és optimalitás

TÉTEL 3.62 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 ∈ A és g(uv) = ∞,
π(v) − π(u) ≥ c(uv), ha uv ∈ A és f(uv) = −∞.

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

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

(b) Dx-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 ∈ A és x(uv) < g(uv),
π(v) − π(u) ≥ c(uv), ha uv ∈ A és x(uv) > f(uv). •

3.7.6 Minimális költségű folyamok

TÉTEL 3.64 A D = (V, A) irányított gráf élhalmazán adott a g : A → Z+ kapacitásfüggvény és a c : A → R+ költségfüggvény. A k nagyságú egészértékű megengedett folyamok költségének minimuma egyenlő a

kπ(t) + ∑[cπ (uv)g(uv) : uv ∈ A, cπ (uv) > 0]  (3.10)

érték maximumával, ahol a maximum az összes π potenciálra megy. Amennyiben g egészértékű, az optimális folyam választható egésznek. Egy k nagyságú megengedett z folyam akkor és csak akkor minimális költségű a k nagyságú megengedett folyamok között, ha létezik olyan π potenciál, amelyre fennállnak a következő optimalitási feltételek:

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

Amennyiben c egészértékű, az optimális π is választható egészértékűnek.

3.7.7 Hálózati mátrixokkal adott lineáris programok