1. Fejezet

LINEÁRIS ALGEBRA ÉS POLIÉDEREK

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

Az alábbiakban áttekintjük a V Euklideszi vektortér néhány alaptulajdonságát. Az alaptest mindig a valós (R) vagy a racionális (Q) számok teste. Amikor Euklideszi vektortérről beszélünk, a valós szám n-esek R^{n} terére (vagy a racionális szám n-esek Q^{n} terére) gondolunk. (Lineáris algebrában bebizonyítják, hogy bármely két n dimenziós Euklideszi vektortér egymással izomorf.) Mindig az R-t használjuk alaptestként, de valamennyi állítás érvényes a Q esetén is. Remélhetőleg nem okoz majd zavart, hogy jelölésben nem teszünk különbséget a 0 szám és a vektortér nulleleme között. A vektortér elemeit néha vektoroknak, néha pontoknak tekintjük.

Legyen x és y két azonos dimenziós vektor. 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 nemnegatí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. Az x_{1}, …, x_{k} vektorok kört alkotnak, ha lineárisan összefüggnek, de bármely valódi részük már lineárisan független. (Az elnevezés a gráfelmélet kör-fogalmából jön és nincs köze a geometria kör-fogalmához.) Könnyű ellenőrizni, hogy egy kör bármely eleme lineárisan függ a kör többi elemétől. (Ha csak azt tesszük fel, hogy az x_{1}, …, x_{k} elemek lineárisan összefüggnek, akkor nem feltétlenül igaz az, hogy mindegyik x_{i} elem lineárisan függ a többitől. Például, az (1, 0), (2, 0), (0, 1) kétdimenziós vektorok lineárisan összefüggnek, de a (0,1) vektor nem állítható elő az (1, 0) és (2, 0) vektorok lineáris kombinációjaként.)

Egy (a_{1}, a_{2}, …, a_{n}) egymás mellé leírt szám n-est sorvektornak tekintünk, míg ha ezeket az elemeket egymás alá írjuk, oszlopvektorról beszélünk. Ha a sor-vektor, akkor a^{t} az a transzponáltja, azaz az a-nak megfelelő oszlopvektor.

Legyen X és Y két vektor-halmaz R^{n}-ben. Ekkor a vektor-összegükön vagy 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,

2. x, y ∈ A ⇒ x + y ∈ A.

Nyilván az egyetlen nulla elemből álló halmaz altér, az ún. triviális altér. Maga az egész V is altér. A definícióból következik, hogy a vektortér 0 eleme minden altérben benne van. Továbbá az altér véges sok elemének bármilyen lineáris kombinációja is az altérben van. Érvényes, hogy alterek metszete is altér. Könnyen ellenőrizhető, hogy két altér összege is altér, éspedig a mindkettőt magában foglaló legszűkebb altér. Egy altér dimenziója az altérből kiválasztható lineárisan független elemek maximális száma. Speciálisan a triviális altér dimenziója 0.

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. (Ebben az értelemben tehát a háromdimenziós tér egy vízszintes és egy függőleges síkja nem ortogonális egymásra!) Könnyen látszik, hogy ha egy y vektor ortogonális az x_{1}, …, x_{k} vektorok mindegyikére, akkor ortogonális ezek bármely lineáris kombinációjára is.

A definícióból rögtön adódik, hogy 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, vagyis a legszűkebb X-t magában foglaló altér.

Altereket más módon is előállíthatunk. Legyen a ∈ R^{n} nem-nulla vektor. Az a-ra ortogonális elemek {x ∈ R^{n} : ax = 0} halmazát origón átmenő hipersíknak nevezzük, melynek (egyik) normálisa vagy normál vektora a. Könnyen látszik, hogy egy origón átmenő hipersík alteret alkot. Ebből adódik, hogy az ilyen hipersíkok metszete is altér. Másszóval, adott x_{1}, …, x_{k} vektorok mindegyikére ortogonális vektorok halmaza alteret alkot, melyet az x_{1}, …, x_{k} ortogonális kiegeszítő alterének nevezünk.

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

Könnyen ellenőrizhető, hogy 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. Hasonlóképpen egyszerű azt belátni, hogy 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.

Mese. Egy x = (x_{1}, …, x_{n}) szám n-esen néha az R^{n} (x_{1}, …, x_{n}) koordinátájú pontját értjük, néha az origóból az x pontba mutató vektort. Az affin függetlenség a pontok függetlenségét akarja megragadni, a lineáris függetlenség a vektorok függetlenségét. (Két pont éppen akkor affin független, ha különbözőek, három különböző pont affin függetlensége azzal ekvivalens, hogy nincsenek egy egyenesen.) Pontok egy k elemű halmaza pontosan akkor affin független, ha az egyikből a többibe mutató k − 1 vektor lineárisan független. Ez azzal ekvivalens, hogy az eggyel magasabb dimenziós, az új koordinátában egy 1-essel kiegészített vektorok lineárisan függetlenek.

1.2 MÁTRIXOK, EGYENLETRENDSZEREK

Legyen A m × n-es mátrix, azaz A-nak m sora és n oszlopa van. A mátrix i-dik oszlopát a_{i}-vel jelöljük, a j-dik sorát pedig _{j}a-val. Az A 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).

Mostantól fogva azzal a jelölési egyszerűsítéssel élünk, hogy nem különböztetjük meg az oszlop és sor vektorokat. Ennek megfelelően, ha az Az szorzatot tekintjük, akkor a z-t oszlopvektornak képzeljük, míg az yA szorzat esetén az y-t sorvektornak. Hasonlóképp, két vektor skalárszorzata esetén sem tesszük ki a transzponálási jelet, vagyis az a és b n-dimenziós vektorok skalárszorzatát abvel vagy ba-val jelöljük. (Ez az egyszerűsítési megállapodás zavart okozhatna, ha az a vektort n × 1-es mátrixként, a b vektort pedig 1 × n-es mátrixként tekintenénk, mert akkor az ab mátrix szorzat egy n × n-es mátrixot jelöl. Szerencsére az a, b vektorok ilyen típusú szorzatára az alábbiakban nem lesz szükségünk, így az említett zavar sem fordulhat elő.)

Valamely n-dimenziós z vektor esetén az Az vektor tekinthető úgy, mint az A oszlopainak egy lineáris kombinációja, ahol az i-dik oszlop együtthatója a z i-dik komponense. Hasonlóképp, egy m-dimenziós y vektorra az yA tekinthető, mint az A sorainak egy lineáris kombinációja.

Futólag már említettük, hogy ha egy z ∈ R^{n} vektor ortogonális az A soraira, vagyis ha Az = 0, akkor z ortogonális az A sorainak bármely yA lineáris kombinációjára is, azaz (yA)z = 0. Valóban, (yA)z = y(Az) = y0 = 0.

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

Biz. Tegyük fel indirekt, hogy z előáll az A sorainak lineáris kombinációjaként, azaz z = yA valamely y ∈ R^{m}-re. Ekkor 0 < zz = (yA)z = y(Az) = 0, ami ellentmondás. •

Megjegyzendő, hogy a lemmában lényeges feltétel, hogy a valós vagy a racionális test felett vagyunk (legalábbis annyiban, hogy rendezett test felett). A GF(2) (vagyis a kételemű) test felett például az (1, 1) vektor ortogonális saját magára.

Figyeljük meg, hogy a sortér és a nulltér az R^{n} egymásra merőleges alterei. (Ugyanis, ha egy vektor merőleges a mátrix soraira, akkor merőleges a sorokból készült lineáris kombinációkra is, vagyis a sortér minden elemére). Az 1.1 lemma alapján a sortérnek és a nulltérnek a közös része az egy szem nulla vektorból áll. Analóg módon az oszloptér és a bal nulltér az R^{m}-nek egymásra merőleges alterei, melyek metszete a triviális altér.

Az A mátrix segítségével megadható egy φ_{A} : R^{n} → R^{m} leképezés a φ_{A}(z) := Az képzési szabállyal. Könnyen látszik, hogy φ_{A} lineáris transzformáció, amelynek képtere az A oszloptere, míg magtere az A nulltere. Hasonlóképp bevezethetünk egy _{A}φ : R^{m} → R^{n} lineáris transzformációt a _{A}φ(y) := yA képzési szabállyal. Ennek képtere az A sortere, míg magtere az A bal nulltere.

Az a kérdés, hogy az Az = 0 (homogén lineáris) egyenletrendszernek van-e nem-triviális megoldása azzal ekvivalens, hogy az A oszlopai lineárisan összefüggőek-e vagy sem. Egy másik interpretáció szerint az Az = 0 azt jelenti, hogy z ortogonális az A soraira, vagyis az Az = 0 nem-triviális megoldhatóságának kérdése azzal ekvivalens, hogy az A nulltere (azaz a φ_{A} leképezés magtere) nem-triviális-e.

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

Biz. m szerinti indukciót használunk. Amennyiben m = 1, a tétel triviális. Legyen tehát m > 1 és tételezzük fel, hogy a tétel érvényes minden olyan mátrixra, amelynek m-nél kevesebb sora van.

A tétel állítása triviális, ha A-nak van egy csupa 0-ból álló oszlopa, így feltesszük, hogy nem ez a helyzet. Figyeljük meg, hogy ha az A egyik sorát helyettesítjük a sor λ-szorosával valamilyen λ ≠ 0 számra, akkor a mátrix nulltere, vagyis az Az = 0 rendszer megoldásainak halmaza változatlan marad. Hasonló kijelentés érvényes, ha a mátrix egyik sorát hozzáadjuk egy másik sorához, vagy ha két sort felcserélünk. Ezen műveletek ismételt alkalmazásával egy olyan A_{1} mátrix nyerhető, amelynek nulltere ugyanaz, mint az A mátrixé, és amelynek első oszlopa az (1, 0, 0, …, 0)^{t} m-dimenziós egység-vektor. Legyen A′ az a mátrix, amely az A_{1}-ből keletkezik az első sor és az első oszlop eltörlésével. Az A′-re az indukciós feltevés szerint érvényes a tétel, azaz létezik egy (n − 1)-dimenziós z′ nem-nulla vektor, amelyre A′z′ = 0.

Jelölje a′ azt a vektort, amely az A_{1} első sorából keletkezik az első (1-es) komponens eltörlésével és legyen α = −a′z′. Ekkor a z := (α, z′) vektor nem-nulla vektor, amelyre A_{1}z = 0, tehát Az = A_{1}z miatt Az = 0. •

Megjegyzendő, hogy a fenti bizonyítás könnyen algoritmussá alakítható az Az = 0 egy nem-triviális megoldásának megkeresésére. Ez a Gauss-elimináció speciális esete homogén lineáris egyenlőség rendszer egy nemtriviális megoldásának megtalálására.

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

Biz. Valóban, ha például több oszlop volna, mint sor, akkor az 1.2 tétel szerint az oszlopok lineárisan összefüggnének. •

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.

Biz. Válasszunk ki maximálisan sok lineárisan független sort és jelölje a mátrixukat A. Az 1.2 tétel szerint Az = 0-nak van nem-triviális megoldása. Ez az eredeti A′z = 0-nak is megoldása, hiszen A′ minden sora lineárisan függ A soraitól. •

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.

Biz. Szimmetria miatt elég kimutatni, hogy az A_{1} oszlopai lineárisan függetlenek. Töröljük el az a_{r+1}, …, a_{n} oszlopokat. Továbbra is érvényes, hogy mindegyik sorvektor lineárisan függ az első s sortól. Így ha egy vektor ortogonális az első s sorra, akkor ortogonális a többi sorra is, vagyis ha az A_{1} oszlopai lineárisan összefüggnének, akkor az A mátrix első r oszlopa is lineárisan összefüggne, ellentmondásban a feltevéssel. •

Az 1.3 következmény és az 1.5 lemma kombinációjából kapjuk a következőt.

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.

Ezen meggondolásokból még egy fontos tulajdonság kiolvasható. Tegyük fel, hogy a mátrixból egymás után választunk sorokat, csak arra ügyelve, hogy a kiválasztott sorok lineárisan függetlenek legyenek. Ezt egészen addig tesszük, amíg már több sor nem választható ki, azaz amikor már a nem kiválasztott sorok mindegyike lineárisan függ a kiválasztott soroktól. Ekkor, függetlenül a közbenső választási döntéseinktől, a kiválasztott lineárisan független sorok száma mindig ugyanaz lesz, nevezetesen az A mátrix rangja. (Másszóval a mohó algoritmus mindig maximális sok lineárisan független sort fog megtalálni.) Ennek igazolásához tegyük fel, hogy az algoritmus mondjuk az első s sort választotta ki és legyen indirekt s < r := r(A). Feltehetjük, hogy az A első r oszlopa lineárisan független. De ekkor ellentmondásban vagyunk az 1.5 lemmával. Ebből az is következik, hogy az A sorterének a dimenziója egyenlő a mátrix rangjával (ami egyenlő a mátrix oszlopterének dimenziójá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ű.

Biz. Ha b = 0, akkor x = 0 megoldás, így feltesszük, hogy b ≠ 0. Az 1.6 tétel miatt A-nak van m lineárisan független oszlopa. Tegyük fel, hogy az első m oszlop lineárisan független. Láttuk, hogy m-nél több m dimenziós vektor lineárisan összefüggő, így az a_{1}, …, a_{m}, b vektorok lineárisan összefüggőek. Egy ilyen nem-triviális lineáris összefüggésben a b együtthatója nem lehet 0, mert ez azt jelentené, hogy az a_{1}, …, a_{m} vektorok lineárisan összefüggőek, ellentétben a feltevéssel. Ha viszont a b együtthatója nem nulla, akkor b kifejezhető az a_{i} vektorok lineáris kombinációjaként.

Az m = n esetben az egyértelműség bizonyításához tegyük indirekt fel, hogy létezik két megoldás is. Ekkor ezek z különbsége nem-nulla és Az = 0, vagyis az A oszlopai lineárisan összefüggőek, de ekkor a sorai is, ellentétben a feltevéssel. •

Egy négyzetes mátrixot szingulárisnak neveznek, ha sorai (illetve ezzel ekvivalensen, oszlopai) lineárisan összefüggnek.

Az 1.8 tétel általánosításához tegyük ismét fel, hogy az A mátrixnak m sora és n oszlopa van (lehet m = n), de a sorok lineáris függetlenségét nem tételezzük fel.

TÉTEL 1.9 A következők ekvivalensek. (A) Az Ax = b egyenletrendszernek létezik megoldása (szemléletesen, a b oszlopvektor benne van az A oszlopainak terében, másszóval b lineárisan függ A oszlopaitól), (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 (szemléletesen, nincs olyan [y normálisú] origón átmenő hipersík, amelyben A minden oszlopa benne van, de b nincsen.)

Biz. (B)→(A). Tekintsünk A-nak r(A) lineárisan független oszlopát. r(A) = r([A, b]) azt jelenti, hogy b lineárisan függ ezektől, tehát függ az A oszlopaitól, vagyis (A) fennáll.

(A)→(C). Ha létezik olyan x és y, amelyekre Ax = b és yA = 0, akkor 0 = (yA)x = y(Ax) = yb. (C)→(B). Tegyük fel indirekt, hogy r(A) < r([A, b]). Válasszunk ki [A, b]-nek r(A) + 1 lineárisan

független sorát és legyen [A_{1}, b_{1}] az általuk alkotott részmátrix. A_{1} sorai már lineárisan összefüggnek, hiszen A-nak nincsen r(A) + 1 darab lineárisan független sora. De ekkor létezik olyan y_{1} ≠ 0 vektor, amelyre y_{1}A_{1} = 0. [A_{1}, b_{1}] sorainak lineáris függetlensége miatt y_{1}[A_{1}, b_{1}] ≠ 0, azaz y_{1}b_{1} ≠ 0. Egészítsük ki y_{1}-t 0 komponensekkel egy y m-dimenziós vektorrá. Erre yA = 0, yb ≠ 0, ellentmondásban (C)-vel. •

Az 1.9 tételben az (A) feltétel azt jelenti, hogy a b oszlopvektor benne van az A oszlopainak terében. A (C) feltétel pedig azt, hogy nem létezik olyan vektor, amely A minden oszlopára merőleges, de b-re nem, másszóval nem létezik olyan hipersík (melynek egy normálisa y), amely tartalmazza A minden oszlopát, de b-t nem. Röviden, egy vektor vagy benne van egy altérben vagy elválasztható tőle hipersíkkal abban az értelemben, hogy a hipersík tartalmazza az alteret, de a vektort nem. Ennek alapján hívhatjuk ezt az eredményt (egy) szeparációs tételnek. Később látni fogjuk, hogy jóval általánosabb szeparációs tételek is léteznek.

Feladat 1.1 A Gauss-elimináció segítségével igazoljuk közvetlenül a (C)→(A) irányt!

Feladat 1.2 Igazoljuk, hogy r(Y · A) ≤ r(A)!

Feladat 1.3 Igaz-e, hogy az Ax = 0 egyenletrendszernek akkor és csak akkor létezik semelyik koordinátájában sem nulla megoldása, ha A minden oszlopa lineárisan függ a többitől?

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

Biz. Mivel az állítás második fele az elsőből következik az A_{1} és A_{2} szerepének felcserélésével, csupán az első rész bizonyítására szorítkozunk. A feltevés szerint A_{1} minden sora ortogonális A_{2} minden sorára, így A_{1} sorainak lineáris kombinációja is ortogonális az A_{2} soraira, azaz A_{1} sortere része A_{2} nullterének. A fordított irányú tartalmazás igazolásához legyen z ∈ N (A_{2}), azaz A_{2}z = 0. Mivel A nem-szinguláris, az 1.8 tétel alapján létezik y = (y_{1}, y_{2}), amelyre yA = z.

Most tehát yA = z ortogonális A_{2} soraira, és y_{1}A_{1} is ortogonális A_{2} soraira, ezért y_{2}A_{2} = yA−y_{1}A_{1} is ortogonális A_{2} soraira. Az 1.1 lemma alapján az A_{2} sorainak egy nemnulla lineáris kombinációja nem lehet ortogonális A_{2} minden sorára, így y_{2}A_{2} szükségképpen 0, azaz z = y_{1}A_{1}, vagyis z benne van A_{1} sorterében. •

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

Biz. Az 1.2 tétel szerint van olyan z_{1} ∈ R^{n} nemnulla vektor, amely ortogonális az A_{1} soraira (magyarul az A_{1}z = 0 rendszernek van nem-triviális megoldása.) Természetesen ekkor z_{1} lineárisan független A_{1} soraitól. Egészítsük ki az A_{1} mátrixot a z_{1} sorvektorral. Miután z_{1} lineárisan független az A_{1} soraitól, a megnövelt A′_{1} mátrix sorai is lineárisan függetlenek. Amennyiben A′_{1}-nek még mindig kevesebb, mint n sora van, az 1.2 tétel alapján ismét létezik egy olyan z_{2} vektort, amely ortogonális az A′_{1} soraira.

Ezt az eljárást (n − m)-szer alkalmazva olyan z_{1}, …, z_{n−m} vektorokat kapunk, melyek mindegyike ortogonális az A_{1} valamennyi sorára valamint egymásra is, továbbá a végül kapott n × n-es mátrix sorai lineárisan függetlenek. Ezen konstrukció alapján z_{i} (i = 1, …, n − m) sorvektorokból álló A_{2} mátrix teljesíti a tétel kívánalmait. •

A két tétel összevetéséből adódik, hogy az A_{1}x = 0 homogén lineáris egyenletrendszer megoldáshalmaza pontosan a z_{1}, z_{2}, …, z_{n−m} vektorok lineáris kombinációinak halmaza. Az is következik, hogy az n-dimenziós tér tetszőleges Q m-dimenziós alterének létezik egy egyértelműen meghatározott Q^{⊥} n − m-dimenziós ortogonális kiegészítő altere. R^{n} minden eleme egyértelműen áll elő egy Q és egy Q^{∗}-beli elem összegeként.

Feladat 1.4 Tegyük fel, hogy az 1.11 tételbeli A_{1} mátrix (I_{m}, B) alakú, ahol I_{m} az m × m-es egységmátrixot jelöli, míg B tetszőleges m × (n − m)-es mátrix. Igazoljuk, hogy az A_{2} := [B^{T} , −I_{n−m}] kielégíti a tétel kívánságait, azaz A_{2} sortere az A_{1} sorterének ortogonális kiegészítője.

1.3 ALTEREK, AFFIN ALTEREK

Az 1.2 tételből következően az R^{n} térben legfeljebb csak n vektor választható ki lineárisan függetlenül. Miután az n egységvektor lineárisan független, az R^{n} dimenziója n. Az is következik, hogy tetszőleges A altér véges sok elem generált altereként áll elő: válasszunk ki maximálisan sok lineárisan független elemét A-nak (ezek száma legfeljebb n), minden elem ezektől lineárisan függ, azaz A a kiválasztott elemek által generált altér.

Az 1.10 és 1.11 tételekből látjuk, hogy minden altér nemcsak generált altérként áll elő, hanem vektorok ortogonális altereként is. (Ez annak a szemléletes geometriai ténynek az általánosítása, hogy a síkban egy origón átmenő egyenest egyrészt meg lehet adni ax + by = 0 alakban, másrészt α(−b, a) ”paraméteres” alakban.) Az is következik, hogy k darab lineárisan független vektorra ortogonális altér rangja n − k. Speciálisan, ha A n − 1 rangú mátrix, akkor az Az = 0 megoldás-halmaza egy-dimenziós altér, másnéven egy origón átmenő egyenes, amelynek pontjai valamely a vektorra {λa : λ ∈ R} alakban adhatók meg (ahol a az A soraira merőleges nem-nulla vektor)

Az 1.9 tétel választ ad arra a kérdésre, hogy egy egyenletrendszernek mikor van megoldása. Feltéve, hogy létezik megoldás, mi mondható a megoldás-halmazról?

Affin altéren vagy eltolt altéren (vagy affin halmazon) egy altér eltoltját értjük. Vagyis C affin altér, ha létezik olyan A altér és a vektor, amelyekre C = {x : x = z + a valamilyen z ∈ A vektorra }, vagyis C = A + {a}. Ilyenkor könnyen látható, hogy C bármely c elemére C − {c} = A, vagyis az altér, amelynek eltolásából a C keletkezik, egyértelműen meghatározott. A C affin altér dimenzióján a definiáló A altér dimenzióját értjük.

Gyakorlat 1.5 Igazoljuk, hogy affin alterek (a) nemüres metszete és (b) összege is affin altér!

Véges sok pont affin kombinációinak halmaza affin alteret alkot, ez nem más, mint a véges sok pontot tartalmazó legszűkebb affin altér. 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.

Könnyen látszik, hogy egy C halmaz akkor és csak akkor affin altér, ha van olyan c eleme, amelyre C −{c} altér. A C halmaz akkor és csak akkor affin altér, ha bármely két elemének affin kombinációja C-ben van, ami azzal ekvivalens, hogy bármely véges sok elemének affin kombinációja C-ben van.

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

(Figyeljük meg, hogy az 1.9 tételben az Ax = b megoldhatóságának az oszlopok terét magában foglaló R^{m} térben volt szemléletes jelentése, a megoldások halmazát viszont sorteret magában foglaló R^{n} térben szemléltetjük affin altérként.)

Biz. Legyen z ∈ N (A), azaz Az = 0. Ekkor nyilván A(z +x_{0}) = b, vagyis N (A)+{x_{0}} ⊆ M. Legyen most x_{1} ∈ M. Ekkor z := x_{1} − x_{0}-ra fennáll Az = 0, tehát x_{1} előáll mint az x_{0} és az N (A)-beli z elem összege. Ezzel a tétel első felét igazoltuk.

Tekintsünk most egy C affin alteret, amely valamely _{1}a, …,_{m} a vektorok által generált altér x_{0} vektorral történő eltolásával áll elő, vagyis az {yA + x_{0} : y ∈ R^{m}} alakú vektorok halmaza, ahol A jelöli az _{1}a, …,_{m} a sorokból álló mátrixot. Az 1.11 tétel szerint van olyan Z mátrix, amelynek nulltere éppen az A sortere. Legyen b := Zx_{0}. Ekkor C éppen a Zx = b egyenletrendszer megoldás-halmaza. •

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

Biz. Az előbbi tétel szerint M az A nullterének az eltoltja. Álljon A_{1} az A-nak r(A) lineárisan független sorából. Nyilván A-nak és A_{1}-nek ugyanaz a nulltere. Az 1.10 és 1.11 tételek alapján A_{1} nullterének rangja n − r(A_{1}) = n − r(A). •

1.4 BÁZIS-MEGOLDÁSOK

A lineáris algebra egyik kiinduló pontja (lineáris) egyenlet-rendszerek vizsgálata volt. A lineáris programozás egyenlet-rendszerek helyett egyenlőtlenség-rendszerekkel foglalkozik. A legelső kérdés az, hogy egy egyenlőtlenség-rendszernek mikor létezik megoldása, vagy másképp fogalmazva, egy egyenlőtlenség-rendszer R-rel jelölt megoldás halmaza mikor nemüres. Amennyiben az, a következő feladat annak eldöntése, hogy valamely c vektorra a cx lineáris célfüggvény korlátos-e vajon R-en (mondjuk) felülről. Ha korlátos, úgy harmadik célunk meghatározni a cx függvény maximumát (vagy ha alulról korlátos, úgy minimumát) R-en. (Persze most még azt a később majd bizonyításra kerülő tényt sem tudjuk, hogy a szóbanforgó maximum vajon létezik-e: Weierstrass általános tétele szerint egy korlátos zárt halmazon folytonos függvény felveszi maximumát, így miután cx folytonos és egy egyenlőtlenség-rendszer R megoldás-halmaza bizonyosan zárt, R korlátossága esetén, már most is bizonyosak lehetünk a maximum létezésében. Nemsokára ezt is és a nem-korlátos esetet is igazoljuk, Weierstrass nélkül.)

Annak érdekében, hogy megállapításaink formálisan is az egyenlőség-rendszerekre vonatkozó tulajdonságok általánosításai legyenek, olyan rendszert tekintünk, amely egyenlőségeket és egyenlőtlenségeket

egyaránt magában foglalhat. Legyen az M = ( \begin{matrix}P \\ Q \end{matrix} ) nem-nulla mátrixnak n oszlopa, legyen R a

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

lineáris rendszer megoldásainak halmaza. A későbbiekben a ( \begin{matrix}b_{0} \\ b_{1} \end{matrix} ) vektort néha röviden b-vel jelöljük

(és azt mindig feltesszük, hogy M nem-nulla). Az R halmazt persze könnyű csupa egyenlőtlenséggel megadni: P x ≤ b_{0}, −P x ≤ −b_{0}, Qx ≤ b_{1}, de később például vizsgáljuk, hogy két rendszernek mikor ugyanaz a megoldás-halmaza, és ehhez jobb a formálisan általánosabb felírás. Az alábbiakban feltesszük, hogy a szóbanforgó R halmaz nemüres. Külön fejezet tárgyalja majd azt a kérdést, hogy (1.1)-nek mikor van megoldása.

Legyen most z az (1.1) rendszer egy megoldása. Jelölje M_{z}^{=} az M azon soraiból álló részmátrixot, amelyek által meghatározott egyenlőtlenséget a z egyenlőséggel teljesíti. Az ennek megfelelő jobb-oldal legyen b_{z}^{=}. (A P definíció szerint része M_{z}^{=}-nek). Az M maradék részét jelölje M_{z}^{<}. A z-t bázismegoldásnak nevezzük, ha r(M) = r(M_{z}^{=}). Rögtön látszik, hogy a P x = b egyenlőség-rendszernek minden megoldása bázis megoldás. Egy bázis-megoldás erős bázis-megoldás, ha a z nem-nulla komponenseihez tartozó M-beli oszlopok lineárisan függetlenek. A definícióból adódik, hogy ha M oszlopai lineárisan függetlenek, úgy minden bázis-megoldás automatikusan erős bázis-megoldás! Ez a helyzet például abban a speciális esetben, amikor az x ≥ 0 nem-negativitási kikötés szerepel az egyenlőtlenségek között (azaz minden változó nem-negatív).

Ki fogjuk mutatni, hogy mindig létezik erős bázis-megoldás, legfeljebb véges sok van belőlük, továbbá minden olyan c vektorra, amelyre cx az R halmazon felülről korlátos a sup(cx : x ∈ R) érték egy erős bázis-megoldáson felvétetik, azaz a maximum létezik. Túl ezen jellemezzük azon c vektorokat, melyekre cx felülről korlátos R-n. Először lássuk be, hogy csak véges sok erős bázis-megoldás létezhez.

TÉTEL 1.14 Az (1.1) egy z megoldása akkor és csak akkor erős bázis-megoldás, ha létezik M-nek egy r(M) sorból és r(M) oszlopból álló nem-szinguláris M′ részmátrixa, amelyre z az M′x′ = b′ egyértelmű x′ megoldásából áll elő 0-komponensek hozzávételével (ahol b′ a b jobb-oldal azon részét jelöli, amely az M′ sorainak felel meg.)

Biz. Ha z a megadott módon áll elő, úgy M_{z}^{=} tartalmazza M′-t, így rangja r(M). Továbbá a z nemnulla komponenseinek megfelelő M-beli oszlopvektorok lineárisan függetlenek, hiszen ezek mindegyike M′ egy oszlopának kibővítése, márpedig M′ a feltevés szerint nem-szinguláris, így oszlopvektorai lineárisan függetlenek. Vagyis ilyenkor z valóban erős bázis-megoldás.

Megfordítva, legyen z erős bázis-megoldás. Ekkor r(M_{z}^{=}) = r(M). Válasszuk ki M_{z}^{=}-nek r(M) lineárisan független sorát, majd a z nem-nulla komponenseinek megfelelő lineárisan független oszlopokat tetszés szerint egészítsük ki az M oszlopai közül r(M) darab lineárisan független oszloppá. Az így kapott r(M) sor és r(M) oszlop által meghatározott M′ részmátrix az 1.5 lemma miatt nemszinguláris, és éppen z-t definiálja a kívánt módon. • Következmény 1.15 Tetszőleges egyenlőtlenség-rendszernek legfeljebb véges sok erős bázis-megoldá-sa van. •

Gyakorlat 1.6 Igazoljuk, hogy az (1.1) rendszer és az (P x ≤ b_{0}, −P x ≤ −b_{0}, Qx ≤ b_{1}) rendszer bázis-megoldásai ugyanazok.

Gyakorlat 1.7 Igazoljuk, hogy az Ax = b, x ≥ 0 rendszer egy megoldása akkor és csak akkor bázismegoldás, ha a pozitív elemekhez tartozó A-beli oszlopok lineárisan függetlenek.

Gyakorlat 1.8 Igazoljuk, hogy az P x_{0} + Ax_{1} = b, x_{1} ≥ 0 rendszer egy megoldása akkor és csak akkor bázis-megoldás, ha az x_{1} nem-nulla elemeihez tartozó P -beli oszlopokat az A-ból kiválasztott maximálisan sok lineárisan független oszloppal kiegészítve még mindig lineárisan független rendszert kapunk.

Gyakorlat 1.9 Legyen f ≪ g, (azaz f minden komponensében kisebb, mint g), ahol f, g ∈ R^{n}. Igazoljuk, hogy az Ax = b, f ≤ x ≤ g rendszer egy z megoldása pontosan akkor bázis-megoldás, ha az A azon a_{i} oszlopai lineárisan függetlenek, melyekre f(i) < z(i) < g(i). Mik az erős bázis-megoldások? Mik a bázis- és az erős bázis-megoldások, ha f ≪ g helyett csak f ≤ g-t tesszük fel?

Gyakorlat 1.10 Igazoljuk, hogy az Bx ≤ b, x ≥ 0 rendszer egy z megoldása akkor és csak akkor bázis-megoldás, ha a B valamely B′ nemszinguláris négyzetes részmátrixára z az B′x′ = b′ egyértelmű megoldásából áll elő nullák hozzávételével.

Természetesen a bázis-megoldásokra vonatkozó kijelentéseink értelmesek (és érvényesek), ha az egyenlőtlenség-rendszert transzponált alakban (azaz ”balról szorozva”) írjuk fel. A későbbiekben szükségünk lesz az alábbi eredményre.

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

Biz. Jelölje A_{0} az A azon a_{i} oszlopaiból álló részmátrixot, melyekre y_{0} merőleges, azaz a_{i}y_{0} = 0. Definíció szerint y_{0} akkor bázis-megoldás, ha r(A_{0}, b) = r(A, b). A tétel állítása pedig azzal ekvivalens, hogy y_{0} pontosan akkor bázis-megoldás, ha r(A_{0}) = r(A, b) − 1. Azt kell tehát csak belátnunk, hogy r(A_{0}) = r(A_{0}, b) − 1. De ez rögtön látszik, hiszen y_{0}A_{0} = 0 és y_{0}b = −1 miatt a b vektor nem függ lineárisan A_{0} oszlopaitól. •

Következő célunk azt megmutatni, hogy (1.1)-nek, ha van egyáltalán megoldása, úgy létezik erős bázis-megoldása is. Valójában ennél még többet is belátunk. Az ideális az lenne, ha igazolni tudnánk, hogy tetszőleges c vektorra és z ∈ R megoldásra mindig létezik olyan x^{∗} bázis-megoldás, amelyre cx^{∗} ≥ cz, vagyis x^{∗} a max cx célfüggvény szempontjából legalább olyan jó, mint z. Sajnos ez az állítás már egy dimenzióban sem igaz. Tekintsük ugyanis az x ≥ 0 egyenlőtlenséget (ahol x most egyetlen változót jelöl). Ennek egyetlen bázis megoldása van, az x = 0. Így a c = 1 (egydimenziós) vektor esetén az x = 1 ponthoz nincs nála jobb bázis-megoldás.

A bajt az okozza, hogy cx nem korlátos felülről az R-en. Ezért érdemes megvizsgálni, hogy ez miként fordulhat elő. Könnyű megfigyelni, hogy a nem korlátosságnak egy lehetséges oka az, ha létezik olyan q vektor, amelyre cq > 0, P q = 0, Qq ≤ 0. Ekkor cx valóban nem korlátos felülről R-en, hiszen bármely pozitív λ számra z + λq is eleme R-nek, és cq > 0 miatt c(z + λq) bármilyen nagy lehet. A következő lemma tartalma az, hogy ha az ilyen q vektorok létezését kizárjuk, akkor az előbbi példával illusztrált baj már nem fordulhat elő.

Lemma 1.17 Legyen z az (1.1) rendszernek egy megoldása, és c egy n-dimenziós vektor. Ha nem létezik olyan q vektor, amelyre cq > 0, P q = 0, Qq ≤ 0, akkor (1.1)-nek létezik olyan x^{∗} bázismegoldása, amelyre cx^{∗} ≥ cz.

(Megjegyzés. A lemma megfordítása nem igaz, vagyis előfordulhat, hogy mind q, mind x^{∗} létezik. Ha például R = {(z_{1}, z_{2}) : z_{2} = 0} a sík vízszintes tengelye (itt tehát Q üres), úgy minden megoldás egyúttal bázis-megoldás is, és ezért x^{∗} := z választással cx^{∗} = cz teljesül. Ugyanakkor z := (0, 0), q = (1, 0), c = (1, 0) esetén cq = 1 és P q = 0).

Biz. Az M_{z}^{<} sorai száma szerinti indukció. Ha ez a szám nulla, úgy z maga bázis-megoldás, tehát jó lesz x^{∗}-nak. Tegyük fel, hogy z nem bázis-megoldás. Ez azt jelenti, hogy M_{z}^{<}-nek van olyan sora, amely lineárisan független az M_{z}^{=} soraitól, és emiatt az 1.9 tételből adódóan létezik olyan q, amelyre M_{z}^{=}q = 0, M_{z}^{<}q ≠ 0. Tekintsük az x_{λ} := z + λq vektort (λ ≥ 0).

1. eset cq = 0. Feltehető, hogy M_{z}^{<}-nek van olyan _{i}a sora, amelyre _{i}aq > 0, mert különben q-t a negatívjával helyettesíthetjük. Kicsiny λ-ra x_{λ} benne van R-ben, míg nagy λ-ra, _{i}aq > 0 miatt, nincsen. Így van olyan λ′ érték, amelyre x_{λ′} ∈ R és x_{λ′} több egyenlőtlenséget teljesít egyenlőséggel, mint z. [Nevezetesen λ′ a maximális olyan λ érték, amelyre M_{z}^{<}x_{λ} ≤ b_{z}^{<} teljesül, vagyis λ′ = min((b_{z}(i) − _{i}az)/ _{i}aq : _{i}a az M_{z}^{<} olyan sora, amelyre _{i}aq > 0).] Miután M_{x_{λ′}}^{<} -nek kevesebb sora van, mint M_{z}^{<}-nek, az indukciós feltevést alkalmazhatjuk x_{λ′}-re. Így létezik egy olyan x^{∗} bázis-megoldás, amelyre cx^{∗} ≥ cx_{λ′} = cz + c(λq) = cz.

2. eset cq ≠ 0. Feltehető, hogy cq > 0, mert ha nem, q-t a negatívjával helyettesítjük. Amennyiben M_{z}^{<}q ≤ 0, úgy q léte ellentmond a lemma feltevésének. Ha viszont van olyan _{i}a sora M_{z}^{<}-nak, amelyre _{i}aq > 0, akkor ugyanúgy járunk el, mint az első esetben: indukció alapján létezik olyan x^{∗} bázis-megoldás, amelyre cx^{∗} ≥ cx_{λ′} = cz + c(λq) > cz. (Az utolsó egyenlőtlenség érdekében kellett q-t úgy választanunk, hogy cq pozitív legyen.) •

Hasznos tudatosítani, hogy a bizonyítás algoritmikus abban az értelemben, hogy egy szóbanforgó x^{∗}-t a Gauss-elimináció segítségével polinom időben kiszámíthatunk. A lemmát c = 0-ra alkalmazva rögtön kapjuk:

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

A fő eredmény a következő.

TÉTEL 1.19 Tegyük fel, hogy az (1.1) rendszer R megoldás-halmaza nemüres, és legyen c egy ndimenziós vektor. A következők ekvivalensek.

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

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

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

Biz. Mivel csak véges sok erős bázis-megoldás van, (1) implikálja (2)-t. (2)-ből rögtön következik (3). Igazoljuk most a (3) → (1) irányt. Az előző lemmából tudjuk, hogy létezik olyan x^{∗} bázismegoldás, amelyre cx^{∗} ≥ cz. Válasszuk x^{∗}-t olyannak, amelynek maximálisan sok 0 komponense van. Állítjuk, hogy x^{∗} erős bázis-megoldás. Tegyük fel indirekt, hogy ez nem igaz, vagyis az x^{∗} nemnulla elemeinek megfelelő M-beli oszlopok lineárisan összefüggőek. Ez azt jelenti, hogy létezik egy olyan q ≠ 0 vektor, amelyre Mq = 0 és x^{∗}(i) = 0 esetén q(i) = 0. Feltehetjük, hogy cq ≥ 0, különben q-t a mínusz egyszeresével helyettesítjük. A (3)-ból következik, hogy valójában cq = 0. Most alkalmas λ-ra x_{λ}^{∗} := x^{∗} + λq-nak több nulla komponense lesz, mint x^{∗}-nak, továbbá x_{λ}^{∗} is bázis-megoldás, amely cx^{∗} = cx_{λ}^{∗} miatt ellentmond x^{∗} választásának. •

Következmény 1.20 Ha (1.1)-nek van megoldása, akkor van erős bázis-megoldása is. Speciálisan, ha az {Ax = b, x ≥ 0} rendszernek van megoldása, akkor van bázis-megoldása is, azaz egy olyan x megoldás, amelyben az x nem-nulla komponenseinek megfelelő A-beli oszlopok lineárisan függetlenek.

Biz. Az előző tételben c = 0-ra (2) fennáll, így a tétel alapján (1) is. •

Az irodalomban gyakran a következmény (speciális) második részét Caratheodory tételnek hívják.

Következmény 1.21 Ha (1.1)-nek van megoldása, és {cx} a megoldások R halmazán felülről korlátos, úgy max(cx : x ∈ R) létezik (azaz létezik olyan z ∈ R, amelyre cz = sup{cx : x ∈ R}).

Biz. Az 1.15 tétel szerint véges sok erős bázis megoldás van. Az 1.19 tételből adódóan a maximum ezek egyikén felvétetik. • Következmény 1.22 (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.

Biz. Készítsünk el egy mátrixot, amelynek p oszlopa van és az egyes oszlopok a p pont helyvektorait tartalmazzák, majd egészítsük ki a mátrixot még egy csupa egyesből álló sorral. A keletkező (d+1)×pes mátrixot jelölje A. Az, hogy z előáll a megadott pontok konvex kombinációjaként azt jelenti, hogy az Ax = (z, 1)-nek létezik nemnegatív megoldása. De akkor létezik bázis-megoldása is, ami azt jelenti (az 1.7 gyakorlat nyomán), hogy az előállításban legfeljebb annyi együttható nemnulla, mint ahány sora van az A mátrixnak, vagyis d + 1. •

A bázis-megoldás definíciója az (M, b) mátrixtól függött. Ugyanakkor érvényes (és később igazolni is fogjuk), hogy ha két egyenlőtlenség-rendszernek a megoldás-halmaza megegyezik, akkor bázismegoldásaik halmaza is megegyezik.

A fejezetet a bázis-megoldások létezésének egy fontos alkalmazásával zárjuk. Ehhez szükségünk van a kövekező közismert és könnyen igazolható lemmára.

Lemma 1.23 Az Euklideszi tér lineáris leképezései folytonosak, azaz ha R^{n}-beli vektorok egy b_{1}, b_{2}, …, sorozata konvergál b-hez, akkor bármely B m × n-es mátrixra a z_{1} := Bb_{1}, z_{2} := Bb_{2}, … sorozat konvergál Bb-hez. •

Lemma 1.24 Tegyük fel, hogy az A′ m′×n-es mátrix oszlopai lineárisan függetlenek és a z_{i_{1}}, z_{i_{2}}, …, R^{n}-beli vektorok olyanok, hogy a b_{i_{1}} := A′z_{i_{1}}, b_{i_{2}} := Az_{i_{2}}, … sorozat egy b vektorhoz konvergál. Ekkor a z_{i_{1}}, z_{i_{2}}, … sorozat konvergál, éspedig egy olyan z vektorhoz, amelyre A′z = b.

Biz. Elég belátni, hogy a z_{i_{1}}, z_{i_{2}}, … sorozat konvergens, hiszen ha mondjuk z-hez tart, akkor az {A′z_{i_{j}}} sorozat az 1.23 lemma miatt Az-hez tart, azaz b = Az. Legyen A_{0} az A′-nek egy n × n-es nemszinguláris részmátrixa és jelölje b_{0} a b vektor A_{0}-nak megfelelő részét. Legyen továbbá B az A_{0} mátrix inverze. Az előző lemmából a z_{i_{1}}, z_{i_{2}}, … sorozat konvergenciája következik. •

TÉTEL 1.25 Bármely n oszlopú A mátrixra a K := AR_{+}^{n} := {b : b = Az, z ≥ 0} halmaz zárt.

Biz. Tekintsük a K halmaz elemeinek egy b_{1}, b_{2}, .. sorozatát, amely valamely b vektorhoz konvergál. Azt kell kimutatnunk, hogy b is a K halmazhoz tartozik.

A feltevés szerint mindegyik b_{i}-re az {Ax = b_{i}, x ≥ 0} rendszernek létezik megoldása. De akkor az 1.20 következmény szerint létezik bázis-megoldása is, amely tehát azt jelenti, hogy a pozitív komponensekhez tartozó oszlopok lineárisan függetlenek. Miután az A oszlopai közül csak véges sok féleképpen lehet lineárisan függetleneket kiválasztani, ezért a {b_{i}} sorozatnak létezik egy olyan {b_{i_{j}}} végtelen részsorozata (ami persze szintén b-hez tart) valamint az A mátrixnak egy lineárisan független oszlopokból álló A′ részmátrixa, hogy az A′x = b_{i_{j}}x ≥ 0 rendszernek van z_{i_{j}} megoldása minden j = 1, 2, …-re. Az 1.24 lemma szerint a z_{j} vektorok konvergálnak valamely z vektorhoz, amely a z_{j}-k nemnegativitása miatt nemnegatív. Miután A′z_{1}, A′z_{2}, … sorozat b határértéke ugyanaz, mint a z_{j} sorozat határértékének A-szorosa, vagyis b = Az, kapjuk, hogy b valóban K-ban van. •

December 28, 2001

1.5 KÚPOK, POLIÉDEREK

A lineáris egyenlőség-rendszerek vizsgálatában alapvető volt az a gondolat, hogy a problémához intuitív geometriai képet tudtunk rendelni; ez vezetett a vektortér, altér, affin altér fogalmához és vizsgálatához. Nem meglepő, hogy a geometriai szemléltetés a lineáris egyenlőtlenség-rendszereknek az előző szakaszban elkezdett vizsgálatához is lényeges segítséget jelent. Ezek előkészítésére bevezetünk néhány fontos fogalmat.

Könnyen látszik, hogy az alterek (illetve az affin halmazok) éppen azok a halmazok, melyek zártak a lineáris (ill. affin) kombináció képzésre. Pontok egy halmazát akkor nevezzük konvexnek, ha zárt a konvex kombináció képzésre, vagyis akárhogy véve a halmaznak véges sok elemét, ezek konvex kombinációja is a halmazhoz tartozik. Hasznos kis gyakorlat belátni, hogy egy halmaz akkor és csak akkor konvex, ha bármely két elemének bármely konvex kombinációja a halmazhoz tartozik. Könnyen ellenőrizhető, hogy konvex halmazok metszete is konvex. Mivel R^{n} konvex, tetszőleges C halmaz benne van egy őt tartalmazó legszűkebb konvex halmazban, nevezetesen a C-t tartalmazó konvex halmazok metszetében. Ezt a C konvex burkának (convex hull) nevezzük és konv(C)-vel jelöljük. Könnyű ellenőrizni, hogy konv(C) nem más, mint 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 = β egyenlet megoldás-halmazát hipersíknak (hyperplane) nevezzük. Ez az {x ∈ R^{n} : ax = 0} origón átmenő hipersík eltoltja. A fentiek alapján a hipersík dimenziója n − 1 (innen az elnevezés). Következik, hogy az affin altér hipersíkok metszetének tekinthető. Az {x : ax ≤ β} halmazt (zárt) féltérnek (closed halfspace) hívjuk. (Ha szigorú egyenlőtlenség van, nyílt féltérről beszélünk).

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ére annak nem-negatív számszorosa is C-hez tartozik. Ebből adódik, hogy az origó mindig a kúpban van. 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. Ez könnyen láthatóan valóban konvex. Miután a továbbiakban csak konvex kúpokról lesz szó, kúpon automatikusan konvex kúpot fogunk érteni. Egy altér például mindig kúp. (Ez a definíció egyrészt általánosabb annál, mint amit szokásos geometriai kúp fogalmunk diktálna, hiszen megenged olyan alakzatokat is, melyeket síkok határolnak. Például a síkban a nemnegatív síknegyed kúp. Másrészt szűkebb, mert kúp eltoltja nem kúp). Két tipikus példa origót tartalmazó kúpra:

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}) := {x : x = ∑_{i} λ_{i}a_{i}, λ_{i} ≥ 0}.

Metszet-kúp (másnéven poliéder-kúp): Véges sok origón átmenő hipersík által határolt féltér metszete; {x : b_{1}x ≤ 0, …, b_{m}x ≤ 0}.

A későbbiekben megválaszoljuk azt a természetes kérdést, hogy egy metszet-kúp vajon mindig előáll-e generált kúpként és egy generált kúp metszet-kúpként. A kiváncsiak kedvéért eláruljuk, hogy a válasz mindkét esetben igen. De ez nem nyilvánvaló: például egy metszet-kúp zártsága rögtön látszik abból, hogy a félterek zártak és zárt halmazok metszete is zárt; ugyanakkor egy generált kúp zártságának az igazolása (1.25 tétel) némileg komolyabb megfontolást igényelt. Azt mindenesetre már most is tudjuk, hogy egy altér az metszet-kúp is és generált kúp is.

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. A generált kúp tekinthető véges sok irány nemnegatív kombinációi halmazának. Egy z pontból induló q⃗ irányú félegyenesen a z + q⃗ := {x : x = z + λq, λ ∈ R_{+}} halmazt értjük. Tehát az irány egy origóból kiinduló félegyenes. További két alapvető fogalom:

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. Másszóval a poliéder egy lineáris egyenlőtlenség-rendszer megoldás-halmaza. Természetesen a formailag általánosabb, egyenlőségeket és egyenlőtlenségeket egyaránt tartalmazó {P x = b_{0}, Qx ≤ b_{1}} rendszer megoldás-halmaza is poliéder hiszen egy px = β egyenlet megoldás-halmaza felfogható úgy, mint az px ≤ β és a −px ≤ −β egyenlőtlenségek közös megoldás-halmaza.

Figyeljük meg, hogy a fenti definícióból adódóan egy poliéder mindig konvex. 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.

Politop (polytope): Véges sok pont konvex burka.

Feladat 1.11 Igazoljuk, hogy egy politop mindig zárt. (Használhatjuk az 1.25 tételt.)

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. Nem nehéz ellenőrizni, hogy ez avval ekvivalens, hogy z nem felezőpontja egy poliéderben lévő szakasznak. A poliédert csúcsosnak vagy hegyesnek (pointed) mondjuk, ha van csúcsa. Egy altér vagy egy végtelen hasáb például olyan poliéder, amelynek egyáltalán nincsen csúcsa. Ha egy poliéder nem tartalmaz teljes egyenest (félegyenest) akkor azt mondjuk, hogy egyenesmentes (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 nevezünk, ha nem áll elő a poliéder más irányainak nemnegatív kombinációjaként. Könnyen láthatóan ez azzal ekvivalens, hogy q⃗ nem áll a poliéder két másik irányának nemnegatív kombinációjaként.

Három dimenzióban egy korlátos (nemüres) poliéder határoló ”alkatrészei” a lapok, az élek és a csúcsok. Ezeket a szemléletes fogalmakat egységesen oldal néven fogjuk általánosítani (angolban a face szót használják). Az R := {x : Mx ≤ b} poliéder oldalán (face) az {x : Mx ≤ b, M_{1}x = b_{1}} poliédert értjük, feltéve, hogy ez nem üres(!), ahol M_{1}x ≤ b_{1} az eredeti Mx ≤ b rendszer egy (esetleg üres) részrendszere. Az oldalt tehát úgy kapjuk, hogy az R-t definiáló egyenlőtlenségek közül néhányat egyenlőséggel megkötünk. Ebben az értelemben a poliéder maga is oldal. Jegyezzük meg, hogy az oldal definíció szerint nemüres. Valódi oldalon (proper face) olyan oldalt értünk, amely nem az egész poliéder. Egy affin altér például olyan poliéder, amelynek nincs valódi oldala. Poliéder minimális oldalán egy tartalmazásra nézve minimális oldalt értünk. Figyeljük meg, hogy az oldalnak a most megadott definíciója nem igazán kielégítő, legalábbis abban az értelemben nem, hogy az oldal fogalma a poliédert leíró egyenlőtlenség-rendszertől függ és nem magától az R poliédertől. Elvileg még az is előfordulhatna, hogy két egyenlőtlenség-rendszer ugyanazt a poliédert definiálja, ugyanakkor az egyikben előálló oldal a másikban nem az. Szerencsére azonban ki fog derülni, hogy ez a helyzet nem fordulhat elő, és sikerül majd az oldalnak egy olyan ekvivalens definícióját adni, amely csak a poliédertől függ és nem annak megadásától (nevezetesen bebizonyítjuk majd, hogy az oldal a poliéder azon pontjainak részhalmaza, melyek valamely lineáris cx célfüggvényt maximalizálják a poliéder felett.)

Gyakorlat 1.12 Amennyiben R := {x : Mx ≤ b} nemüres, úgy R akkor és csak akkor az egész tér, ha r(M) = 0 (azaz M a csupa-nulla mátrix) és b ≥ 0.

Gyakorlat 1.13 Két poliéder metszete is poliéder. Két politop vektor-összege is politop.

Gyakorlat 1.14 Két metszet-kúp metszete metszet-kúp. Két generált kúp vektor-összege generált kúp.

Gyakorlat 1.15 Az R poliéder egy z pontja akkor és csak akkor csúcs, ha nincs olyan x′ ≠ 0 vektor, amelyre z + x′ és z − x′ is R-ben van. (Azaz z nincs R-hez tartozó szakasz belsejében).

Gyakorlat 1.16 Igazoljuk, hogy ha az R poliéder kúp, akkor metszet-kúp.

Álljon itt néhány természetes kérdés, amelyekre választ várunk: Két egyenlőtlenség-rendszer megoldás-halmaza mikor ugyanaz (magyarán, mikor definiálják ugyanazt a poliédert)? Mikor üres egy poliéder? Mi a poliédert tartalmazó legszűkebb affin altér? Mi a poliéderben lévő legbővebb affin altér? Két nemüres poliéder összege mindig poliéder-e? Két politop metszete, ha nemüres, vajon mindig politop-e? Mikor csúcsos egy poliéder? Mikor tartalmaz teljes egyenest és mikor félegyenest? Minden metszet-kúp generált kúp? Minden generált kúp metszet-kúp? Minden politop poliéder? Minden korlátos nemüres poliéder politop? Két diszjunkt poliéder mindig elválasztható hipersíkkal?

Térjünk most rá a lineáris egyenlőtlenség-rendszerek és a geometriai háttér kapcsolatának vizsgálatára, és tekintsük ismét az (1.1) rendszert és megoldás-halmazát az R poliédert, amelyről feltesszük, hogy nemüres.

Az (1.1) rendszerhez hozzárendeljük az A := {q : Mq = 0} alteret valamint a C := {q : P q = 0, Qq ≤ 0} metszet-kúpot, és ezeket rendre karakterisztikus altérnek illetve karakterisztikus (néha recessziós) kúpnak nevezzük. Először is megmutatjuk ezen fogalmak geometriai jelentését, majd belátjuk róluk, hogy valójában csak az R poliédertől függenek és nem az R-t definiáló (1.1) rendszertől.

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

(1) q eleme a karakterisztikus kúpnak, azaz P q = 0, Qq ≤ 0.

(2) Az R-nek mindegyik x pontjára az x + λq pont minden pozitív λ-ra R-ben van.

(3) q⃗ az R poliéder végtelen iránya (azaz definíció szerint R-nek van olyan z pontja, amelyre a z + λq pont minden pozitív λ számra R-ben van).

Biz. (1) → (2) A poliéder tetszőleges x elemére és tetszőleges pozitív λ számra P (x + λq) = P x + λP q = b_{0} + 0 = b_{0}, és Q(x + λq) = Qx + λQq ≤ b_{1} + 0 = b_{1}, azaz x + λq R-ben van. A (2) → (3) következtetés triviális. A (3) → (1) irány igazolásához látható, hogy (3) implikálja P q = 0-t. Tegyük most fel indirekt, hogy Qq ≰ 0 azaz Q-nak létezik olyan _{i}a sora, amelyre _{i}aq > 0. Ekkor alkalmasan nagy λ számra _{i}a(z + λq) nagyobb lesz, mint b_{1}(i), vagyis z + λq nincs a poliéderben, ellentétben a feltevéssel. •

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

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

(1) q eleme a karakterisztikus altérnek (azaz Mq = 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.

Biz. Az (1) → (2) irány triviális. A (2) → (3) irány semmitmondó. Tegyük most fel (3)-t. Az 1.26 tételből adódóan mind q, mind −q benne van a karakterisztikus kúpban, ezért Mq = 0. •

Következmény 1.29 Az (1.1)-ben definiált R poliéder akkor és csak akkor egyenes-mentes, ha M oszlopai lineárisan függetlenek. •

Feladat 1.17 Igazoljuk, hogy az R poliéder egy z pontját tartalmazó legbővebb, R-ben fekvő affin altér a karakterisztikus altér z-vel való eltoltja.

A fenti tételekből adódik, hogy a karakterisztikus altér és karakterisztikus kúp csak a poliédertől függ és nem az azt leíró rendszertől, így ezentúl joggal beszélhetünk az R poliéder karakterisztikus alteréről és kúpjáról.

Később általánosságban is be fogjuk bizonyítani, hogy a bázis-megoldások éppen az R poliéder minimális oldalainak az elemei, most azonban ezt csak abban a speciális esetben igazoljuk, amikor M oszlopai lineárisan függetlenek, azaz R egyenes-mentes.

TÉTEL 1.30 Tegyük fel, hogy M oszlopai lineárisan függetlenek vagy ekvivalensen, hogy R egyenesmentes. Ekkor R egy z eleme akkor és csak akkor csúcsa R-nek, ha z bázis-megoldása (1.1)-nek.

Biz. Tegyük fel először, hogy z csúcs. Ha nem volna bázis megoldás, akkor az M_{z}^{=} mátrix rangja kisebb volna M rangjánál, vagyis n-nél. Ekkor létezik olyan q nemnulla vektor, amelyre M_{z}^{=}q = 0. Miután M_{z}^{<}z ≪ b_{z}^{<}, következik, hogy van olyan kis pozitív λ érték, amelyre z+λq és z−λq mindegyike R-hez tartozik, ellentétben azzal, hogy z csúcs.

Tegyük most fel, hogy z bázis-megoldás. Ekkor M_{z}^{=} rangja n, azaz oszlopai lineárisan függetlenek. Ha z nem volna csúcs, úgy létezne olyan q nemnulla vektor és λ > 0 szám, hogy z + λq és z − λq mindegyike R-hez tartozna. De ekkor szükségképpen M_{z}^{=}q = 0 volna, ellentmondásban M_{z}^{=} oszlopainak lineáris függetlenségével. •

TÉTEL 1.31 Az (1.1)-ben definiált R (nemüres) poliéderre a következők ekvivalensek.

(1) R csúcsos,

(2) R egyenes-mentes,

(3) M oszlopai lineárisan függetlenek (másszóval R karakterisztikus altere triviális).

Biz. A (2) és (3) feltételek ekvivalenciáját az 1.29 következményben már megfogalmaztuk. (1) → (3) igazolásához indirekt tegyük fel, hogy (3) nem teljesül, azaz a karakterisztikus altérnek létezik nemnulla z eleme. Ekkor az 1.28 tétel szerint R minden pontja rajta van egy R-hez tartozó egyenesen, tehát R-nek nem lehetne csúcsa, (1) nem állna fenn. A (3) → (1) irányhoz az 1.20 tétel miatt létezik (1.1)-nek bázis-megoldása, ami az 1.30 tétel miatt csúcs. •

Következmény 1.32 Minden (nemüres) poliédernek véges sok csúcsa van. •

Biz. Ha R-nek van egyáltalán csúcsa, akkor M oszlopai lineárisan függetlenek. Ekkor minden csúcs erős bázis-megoldásnak felel meg, amiből véges sok van. •

1.5.1 POLIÉDEREK OSZTÁLYOZÁSA

Következő célunk poliédereknek egyfajta osztályozását megadni. Először is belátjuk, hogy minden poliéder egy csúcsos poliéder és egy altér összege.

TÉTEL 1.33 Az (1.1) által definiált R (nemüres) poliéder az A := {x : Mx = 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 az M sorai által generált altér). Továbbá, az R′ poliéder egyenes-mentes.

Biz. Először belátjuk, hogy R ⊆ A + R′, azaz hogy bármely z ∈ R elem előáll egy A-beli és egy R′-beli elem összegeként. Valóban, minden z elem egyértelműen előáll egy A-beli z_{1} és egy A^{⊥}-beli z_{2} elem összegeként. Belátjuk, hogy z_{2} ∈ R′. Ha nem ez volna a helyzet, akkor z ∈ A^{⊥} miatt z_{2} nem volna R-ben, azaz z_{2} megsértené (1.1) valamelyik sorát. De akkor Az_{1} = 0 miatt z = z_{1} + z_{2} is megsértené ugyanazt a sort, ellentétben a z ∈ R feltevéssel. Így valóban R ⊆ A + R′. Másrészt a definíciókból világos, hogy A + R′ ⊆ R, amiből A + R′ = R.

Végül belátjuk, hogy R′ egyenes-mentes. Az M^{⊥} mátrix sorai alkossák az A altér egy bázisát.

Ekkor tehát M sorai és M^{⊥} sorai egymásra merőlegesek, együtt kifeszítik az egész teret, azaz ( \begin{matrix}M \\ M^{⊥} \end{matrix} )

teljes oszlop-rangú. Miután R′ az {M^{⊥}x = 0, P x = b_{0}, Qx ≤ b_{1}} rendszer megoldás-halmaza, az 1.29 következményből adódik, hogy R′ egyenes-mentes. •

Az alábbi következmény tartalma az, hogy az 1.33 tételben, ha R kúp, úgy R′ is kúp lesz.

Következmény 1.34 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^{⊥} egyenes-mentes metszet-kúp vektor-összege, ahol A^{⊥} az A altér ortogonális kiegészítője.

Biz. Az előbbi tétel nyomán csak azt kell látnunk, hogy R′ metszet-kúp, de ez világos, hiszen egy altér metszet-kúp. •

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

Biz. Legyen z a poliéder egy pontja. Legyen M_{z}^{=} az M mátrixnak az a része, amelynek sorai által meghatározott egyenlőtlenségeket z egyenlőséggel teljesíti, míg a Q mátrix maradék részét jelölje M_{z}^{<}. (A P automatikusan része M_{z}^{=}-nek.) A z pont szintjét definiáljuk az s(z) := r(M) − r(M_{z}^{=}) különbséggel. Az 1.31 tétel alapján R csúcsai éppen a 0 szintű pontok. (Általánosabban is kimutatható, bár erre most nincs szükségünk, hogy a z szintje nem más, mint a pontot tartalmazó legszűkebb oldal dimenziója).

A szint szerinti indukcióval fogjuk kimutatni, hogy a poliéder minden z pontja előáll egy R_{K}-beli és egy C-beli pont összegeként. Ha a szint nulla, akkor tehát z csúcs, így eleme R_{K}-nak. Tegyük most fel, hogy s(z) > 0 és azt, hogy minden alacsonyabb szintű pontra a szóbanforgó előállítás létezik.

Mivel r(M) > r(M_{z}^{=}), létezik olyan q, amelyre M_{z}^{=}q = 0 és M_{z}^{<}q ≠ 0. Feltehető, hogy M_{z}^{<}q-nak van negatív komponense, különben q-t helyettesíthetjük a negatívjával.

Tegyük először fel, hogy M_{z}^{<}q-nak nincsen pozitív komponense, azaz M_{z}^{<}q < 0 (vagyis q ∈ C). Ekkor létezik olyan λ_{1} > 0 szám, amelyre x_{1} := z − λ_{1}q az R-ben van és s(x_{1}) < s(z). (Nevezetesen, λ_{1} := min((b_{1}(i) − _{i}az)/(−_{i}aq) ahol a minimum az Q azon _{i}a soraira megy, amelyekre _{i}aq < 0. Az x_{1} szintje valóban kisebb, mint z szintje, hiszen egyrészt M_{z}^{=}x_{1} = b_{z}^{=}, másrészt M_{z}^{<} egyik _{i}a sorára iax_{1} = b(i) és ez a sor _{i}aq ≠ 0 és M_{z}^{=}q = 0 miatt lineárisan független M_{z}^{=} soraitól.) Indukció alapján x_{1} előáll x_{1} = y_{1} + y′_{1} alakban, ahol y_{1} ∈ R_{K} és y′_{1} ∈ C. De most z = x_{1} + λ_{1}q = y_{1} + y′_{1} + λ_{1}q és y′_{1} + λ_{1}q ∈ C, így z is előáll az R_{K}-beli y_{1} és egy C-beli elem összegeként.

Tegyük most fel, hogy M_{z}^{<}q-nak létezik pozitív komponense is, és legyen _{1}a és _{2}a az M_{z}^{<} mátrixnak két olyan sora, amelyre _{1}aq < 0 és _{2}aq > 0. Ekkor léteznek pozitív λ_{1} és λ_{2} számok, melyekre x_{1} = z − λ_{1}q ∈ R és x_{2} = z + λ_{2}q ∈ R, és mind az x_{1}, mind az x_{2} szintje kisebb, mint a z-é.

Indukcióval x_{i} = y_{i} +y′_{i} (i = 1, 2), ahol y_{i} ∈ R_{K} és y′_{i} ∈ C. De ekkor z = (λ_{2}x_{1} +λ_{1}x_{2})/(λ_{1} +λ_{2}) = (λ_{2}y_{1} +λ_{1}y_{2})/(λ_{1} +λ_{2})+(λ_{2}y′_{1} +λ_{1}y′_{2})/(λ_{1} +λ_{2}). Itt az összeg első tagja R_{K}-ban van, míg a második tagja C-ben. •

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

Biz. (1) → (2) triviális. (2) → (3) Ha a karakterisztikus kúpnak volna q nemnulla eleme, akkor, amint már az 1.26 tételben is láttuk, R tartalmazná a z + q⃗ félegyenest minden z ∈ R pontra. (3) → (4) Az 1.35 tétel szerint, ha a karakterisztikus kúp triviális, úgy R a csúcsai által feszített politop. (4) → (1) Mivel véges sok csúcs van, ezek konvex burka korlátos. •

Hogy teljes legyen a kép, megadjuk az egyenes-mentes metszet-kúpok egyfajta előállítását. Az idea az, hogy a kúpot elmetszük egy alkalmas hipersíkkal, a metszet korlátos poliéder lesz, amelynek csúcsai a kiindulási kúp extrém irányainak felelnek meg. A következő tétel megmondja, hogyan kell a hipersíkot ”alkalmasan” választani, hogy az tényleg messe a kúpot.

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

Biz. Miután C egyenes-mentes, M oszlopai lineárisan függetlenek, így Mq = 0-ból q = 0 következik. Ezért C-nek tetszőleges q nemnulla elemére Mq ≠ 0, azaz van olyan i index, amelyre _{i}aq < 0 fennáll. De ekkor aq < 0 is áll, és így létezik egy egyértelmű λ > 0 szám, amelyre z := λq ∈ M. Vagyis a kúp q⃗ iránya előáll z⃗ alakban, ahol z ∈ Z. Fordítva, tetszőleges z ∈ Z elem esetén Mz ≤ 0, ezért z⃗ a kúp iránya.

Z korlátosságához az 1.36 tétel alapján azt kell belátni, hogy karakterisztikus kúpja triviális, vagyis az {Mx ≤ 0, ax = 0} rendszernek nincs nemnulla megoldása. Ezt viszont már a bizonyítás elején láttuk.

Végül legyen z ∈ Z, azaz Mz ≤ 0, az = −1. Ha z nem csúcs, akkor előáll (z_{1} + z_{2})/2 alakban ahol z_{i} ∈ Z, z_{i} ≠ z, (i = 1, 2). De ekkor z⃗ a z⃗_{1} és z⃗_{2} C-beli irányok nemnegatív kombinációja. Vagyis ha z⃗ extrém iránya C-nek, akkor z csúcsa Z-nek. Legyen most z csúcsa Q-nak. Ha z⃗ nem éle C-nek, akkor van C-nek két olyan x′, y′ eleme, amelyek nincsenek z⃗-ben, de x′ + y′ z⃗-ben van. Ekkor viszont z az x′ ∩ Q pontot és az y′ ∩ Q pontot összekötő szakasz belsejében van, azaz z nem csúcsa Q-nak. •

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

Azt már láttuk, hogy egyenes-mentes poliéder esetén csúcs és bázis-megoldás ugyanaz. Érdemes megállapítani egy egyenes-mentes kúp extrém irányának algebrai jelentését is.

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

Biz. Az 1.37 tétel jelöléseit használva, az egyenes-mentesség miatt Mz < 0, és így az < 0. Miután z bármely pozitív számszorosa ugyanazt az irányt definiálja, feltehetjük, hogy az = −1, azaz z ∈ Q. Az 1.16 tételben bebizonyítottuk (egy ekvivalens alakra), hogy az {Mx ≤ 0, ax = −1} rendszer egy z megoldása akkor és csak akkor bázis-megoldás (azaz Q-nak egy csúcsa), ha z merőleges M-nek r(M) − 1 lineárisan független sorára. Az 1.37 tétel szerint viszont egy-egy értelmű kapcsolat van a Q poliéder csúcsai és a C kúp extrém irányai között. •

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

Miután láttuk, hogy egy poliéder előáll mint egy csúcsos poliéder és egy altér vektor-összege, továbbá tudjuk, hogy egy altér generált kúp, kapjuk:

Következmény 1.41 Minden R poliéder előáll mint egy Q politop és egy K generált kúp vektorösszege.

Következmény 1.42 Minden C metszet-kúp generált kúp.

Biz. Triviális C kúpra a tétel igaz. Ha C tartalmaz teljes egyenest, akkor az 1.34 következmény alapján előáll egy egyenes-mentes kúp és egy altér vektor-összegeként. Miután egy altér generált kúp, továbbá az 1.38 következmény alapján egy egyenes-mentes kúp is generált kúp, ezek vektor-összege, vagyis C is generált kúp. •

December 28, 2001

FARKAS LEMMA ÉS DUALITÁS

2.1 EGYENLŐTLENSÉG-RENDSZEREK MEGOLDHATÓSÁGA

A Gauss-elimináció segítségével elvi és algoritmikus választ kaptunk arra a kérdésre, hogy egy lineáris egyenlőség-rendszernek mikor van megoldása. A Farkas lemma azzal a kérdéssel foglalkozik, hogy egy egyenlőtlenség-rendszer mikor oldható meg, vagyis, hogy egy poliéder mikor nem üres. Ennek különböző ekvivalens alakjai vannak, annak megfelelően, hogy az egyenlőtlenség rendszer milyen alakban van adva. A Farkas lemma a lineáris programozás egyik alapkövének tekinthető. Az alábbiakban több különböző bizonyítást is bemutatunk, melyek közül kettő, a szimplex módszer és a Fourier-Motzkin elimináció konstruktív. Van azonban egy döntő különbség az eddigi fejezetek eredményeihez képest (akár a Gauss-eliminációt nézzük, akár a Caratheodory tételt és vidékét), éspedig az, hogy e két módszer egyike sem polinomiális futásidejű! Bár léteznek polinomiális futásidejű algoritmusok is (melyek mindegyike valamiféle közelítő megoldást keres), mind a mai napig nem ismeretes erősen polinomiális algoritmus egyenlőtlenség rendszer megoldására!!!

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

Az {Ax = b, x ≥ 0} rendszert primál feladatnak, míg az {yA ≥ 0, yb < 0} rendszert duál vagy duális feldatnak nevezik. Megjegyzendő, hogy ha a szóbanforgó y létezik, akkor az úgy is megválasztható, hogy yb = −1 teljesüljön, így néha azt hívjuk duális feladatnak, amikor az yb < 0 helyett yb = −1-t követelünk.

A tételnek az oszloptérben szép geometriai jelentése van. Azt mondja ki, hogy valamely b vektor pontosan akkor nincsen benne az A oszlopvektorai által generált kúpban, ha van olyan zárt féltér (amelynek y normálisú határoló hipersíkja tartalmazza az origót), amely tartalmazza az oszlopvektorok mindegyikét, de nem tartalmazza b-t. Tömören, egy vektor vagy benne van egy kúpban vagy van olyan hipersík, amely elválasztja a vektort a kúptól.

Érdekes, hogy a 2.1 tételnek a sortérben is szemléletes jelentése van. Ugyanis a primál probléma megoldása azzal ekviavalens, hogy létezik olyan nemnegatív (x, 1) vektor, amely ortogonális az A′ := (A, −b) mátrix soraira, ami viszont azzal ekvivalens, hogy az A′ mátrix nullterében létezik egy olyan x′ nemnegatív vektor, amelynek utolsó komponense szigorúan pozitív. A duál problémában yb < 0 helyett y(−b) > 0-t írva, a duál probléma megoldhatósága azt jelenti, hogy van olyan y vektor, amelyre yA′ ≥ 0 és yA′ utolsó komponense szigorúan pozitív; magyarán azt, hogy az A′ mátrix sorterében van olyan nemnegatív vektor, amelynek utolsó komponense szigorúan pozitív. Miután egy tetszőleges mátrix nulltere és sortere egymás ortogonális kiegészítő alterei, továbbá tetszőleges altér és ortogonális kiegészítő altere megadható egy mátrix nulltereként illetve sortereként, a Farkas lemma ekvivalens megfogalmazása a következő. Tetszőleges altér és ortogonális kiegészítő altere közül pontosan az egyik tartalmaz olyan nemnegatív vektort, amelynek utolsó komponense pozitív. (Két ilyen vektor skaláris szorzata pozitív, azaz nem lehetnek merőlegesek egymásra, tehát két ortogonális altér közül legfeljebb csak az egyik tartalmazhat ilyen vektort.)

A tételt kényelmesebb lesz kicsit általánosabb alakban igazolni. (Nem ritka jelenség, hogy egy jól eltalált általánosításra az indukciós bizonyítás gördülékenyebben működik.)

TÉTEL 2.2 A

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

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

yP = 0, yA ≥ 0, yb < 0  (2.2)

duális feladatnak van.

(Figyeljük meg, hogy (2.2) megoldhatósága nyilván ekvivalens az {yP = 0, yA ≥ 0, yb = −1} rendszer megoldhatóságával.)

Biz. A primál és a duál feladat nyilván nem oldható meg egyszerre, mert akkor 0 + 0 ≤ 0 + (yA)x_{1} = (yP)x_{0} + (yA)x_{1} = y[(P, A)x] = yb < 0, azaz 0 < 0 következne.

Annak bizonyítására, hogy a primál és a duál feladatok egyike biztosan megoldható az A oszlopai száma szerinti indukciót alkalmazunk. Amennyiben ez az n_{1}-gyel jelölt szám nulla, azaz A üres, úgy a tétel következik az 1.9 tétel (C) részéből (amikor tehát csak arról van szó, hogy egy egyenlőségrendszer mikor oldható meg). Tegyük tehát fel, hogy n_{1} pozitív és indukció alapján azt, hogy n_{1}-nél kisebb oszlop-számra a tétel érvényes!

Legyen a_{1} az A mátrix első oszlopa. Jelölje A′ azt a mátrixot, amely A-ból keletkezik az a_{1} kihagyásával. Amennyiben a

P x_{0} + A′x′_{1} = b, x′_{1} ≥ 0  (2.3)

rendszernek létezik megoldása, úgy az x′_{1}-t egy nulla komponenssel kiegészítve (2.1) megoldásához jutunk. Ha (2.3)-nak nincs megoldása, úgy az

yP = 0, yA′ ≥ 0, yb < 0  (2.4)

rendszernek létezik y′ megoldása (az indukciós feltevés miatt). Ha most y′a_{1} ≥ 0, úgy y′ a (2.2)-nek is megoldása, és ekkor készen vagyunk.

Tegyük fel tehát, hogy y′a_{1} < 0, azaz most y′A első komponense negatív, a többi nemnegatív. Jelölje P′ azt a mátrixot, amelyet P -ből az a_{1} oszlop hozzávételével nyerünk. Ha most az

yP′ = 0, yA′ ≥ 0, yb < 0  (2.5)

problémának van megoldása, az nyilván megoldása (2.2)-nek is, és ekkor ismét csak készen vagyunk. Ha (2.5)-nek nincs megoldása, úgy a

P′x′_{0} + A′x′_{1} = b, x′_{1} ≥ 0  (2.6)

rendszernek van (indukció miatt). Jelölje (x_{0}, x_{1}) azt a vektort, amely úgy keletkezik (x′_{0}, x′_{1})-ből, hogy az a_{1}-nak megfelelő komponenst x′_{0}-ből x′_{1}-be helyezzük (ami persze azt jelenti, hogy (x′_{0}, x′_{1}) ugyanazt az n_{0} + n_{1} dimenziós vektort jelöli, mint (x_{0}, x_{1})).

Állítjuk, hogy (x_{0}, x_{1}) megoldása (2.1)-nek. Ehhez csak azt kell igazolnunk, hogy x_{1}(1) (az a_{1}-nek megfelelő komponens) nemnegatív. Valóban, ha ez negatív lenne, akkor x_{1} is és y′A is olyan, hogy első komponensük negatív, a többi pedig nem az. Emiatt (y′A)x_{1} > 0 és így 0 + 0 < 0 + (y′A)x_{1} = (y′P)x_{0} + (y′A)x_{1} = y′[(P, A)x] = y′b < 0, ami lehetelen. •

Egyszerű technikai fogással a 2.2 tételt még általánosabb alakra hozhatjuk.

TÉTEL 2.3

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

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} < 0  (2.8)

duális rendszernek van.

Biz. Jelölje az x_{0}, x_{1}, y_{0}, y_{1} dimenzióját rendre n_{0}, n_{1}, m_{0}, m_{1}. Új, nemnegatív változók bevezetésével az egyenlőtlenség-rendszert egyenlőség-rendszerré alakítjuk. Legyen B′ := (B, I), A′ := (A, 0) (ahol az I egy m_{1} × m_{1}-os egység-mátrixot, a 0 pedig egy m_{0} × m_{1}-os nulla mátrixot jelöl). Most (2.7) (x_{0}, x_{1}) megoldásai és

P x_{0} + A′x′_{1} = b_{0}, Qx_{0} + B′x′_{1} = b_{1}, x′_{1} ≥ 0  (2.9)

(x_{0}, x′_{1}) megoldásai között egy-egy értelmű kapcsolat áll fenn. Nevezetesen (x_{0}, x_{1}) az (x_{0}, x′_{1})-ből keletkezik az utolsó m_{1} komponens kihagyásával, míg (x_{0}, x_{1})-ből úgy kapjuk (x_{0}, x′_{1})-t, hogy x_{1}-t helyettesítjük az x′_{1} := (x_{1}, b_{1} − (Qx_{0} + Bx_{1})) vektorral.

A (2.9)-hez tartozó

y_{0}P + y_{1}Q = 0, y_{0}A′ + y_{1}B′ ≥ 0, yb < 0  (2.10)

duál probléma és (2.8) ekvivalensek, hiszen csak arról van szó, hogy a (2.8)-ban explicit szereplő y_{1} ≥ 0 előjel megkötést (2.10)-ben az y_{0}A′ +y_{1}B′ ≥ 0 egyenlőtlenség-rendszerben rejtettük el. A (2.9) primál feladatra felírva a 2.2 tételt az abban szereplő (2.2) duál feladat éppen a (2.10) alakot ölti. •

Megjegyezzük, hogy a Farkas lemmát még általánosabb alakban is fel lehetne írni. Például a primál feladatban lehetnek fordított irányú egyenlőtlenségek, vagy nempozitív változók. De a megfelelő egyenlőtlenség negálásával és feltételi mátrix megfelő oszlopának negálásával könnyen a (2.1)-es alakra juthatunk.

Gyakorlat 2.1 Írjuk fel a Farkas lemmát az alábbi speciális alakokra: (i) Bx ≤ b, (ii) Qx ≤ b, x ≥ 0.

További kézenfekvő megjegyzés, hogy a Farkas lemmát olyan alakban is használhatjuk, amikor a rendszer balról szorzással van adva. (Egy későbbi alkalmazás miatt néhány vektort és mátrixot vesszős betűvel jelölünk.)

TÉTEL 2.4

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

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

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

duális rendszernek van megoldása. •

Gyakorlat 2.2 Az {yA ≤ c} rendszernek akkor és csak akkor van megoldása, ha nincs olyan x ≥ 0, amelyre Ax = 0, cx < 0.

Feladat 2.3 Tekintsük a (2.2)-ben előforduló {yP = 0, yA ≥ 0, yb = −1} rendszert, mint primál problémát és fogalmazzuk meg erre a Farkas lemmát. Mutassuk meg, hogy a felírt duális ekvivalens (2.1)-gyel.

Feladat 2.4 Tegyük fel van egy szubrutinunk, amely vagy az {Ax = b, x ≥ 0} rendszernek vagy a duális {yA ≥ 0, yb = −1} rendszernek kiszámít egy megoldását. Hogyan használhatjuk fel ezt a (2.1) vagy (2.2) rendszer megoldására?

Feladat 2.5 Tegyük fel van egy szubrutinunk a {Bx ≤ b, x ≥ 0} rendszer megoldására. Hogyan használhatjuk fel ezt a {Qx ≤ b} rendszer megoldására?

A bázis-megoldásról tanultakat ötvözhetjük a Farkas lemmával. Csak példaként említjük az alábbit.

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

2.2 A DUALITÁS TÉTEL

Rátérünk a lineáris programozás alapkérdésének tárgyalására: Adott c vektorra határozzuk meg, hogy egy nemüres R poliédernek mely pontja (illetve pontjai) maximalizálják a cx lineáris célfüggvényt. Röviden, maximalizáljuk cx-t R felett. Geometriailag ez avval ekvivelens, hogy a c vektor irányában keressük az R legtávolabbi pontját, vagyis egy olyant, ahol egy c normálisú hipersíkot kívülről a poliédernek tolva, az megérinti. Tegyük fel, hogy R a

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

egyenlőtlenség-rendszer megoldás-halmaza

2.2.1 Korlátosság

Kiindulásul két kérdést kell tisztáznunk. Az elsőre, hogy az R poliéder mikor nemüres, a Farkas lemma már meg is adta a választ. A második kérdésre, hogy cx mikor korlátos felülről, az 1.19 tétel szintén adott már egyfajta választ. Ennek alapján tudjuk, hogy ha cx nem korlátos felülről, akkor erre létezik egyszerű tanúsítvány, nevezetesen a karakterisztikus kúpnak egy olyan q eleme, amelyre cq > 0. Másrészt, ha cx felülről korlátos, akkor legnagyobb értékét egy erős bázis-megoldáson eléri, vagyis létezik maximum. Ez ugyan igen lényeges tulajdonság, de jó lenne, ha cx korlátosságának volna egy ahhoz hasonló jellegű tömör bizonyítéka is, mint amilyen bizonyíték az előbb említett q volt a cx nem-korlátosságára. Ezt adja meg az alábbi tétel, az 1.19 tétel megismétlése mellett.

TÉTEL 2.6 Tegyük fel, hogy a (2.13) rendszer R megoldás-halmaza nemüres, és legyen c egy ndimenziós vektor. A következők ekvivalensek.

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

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

(3) Nem létezik olyan x vektor, amelyre cx > 0, és P x = 0, Qx ≤ 0.

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

y_{0}P + y_{1}Q = c, y_{1} ≥ 0.  (2.14)

Biz. Az első három állítás ekvivalenciáját mondta ki az 1.19 tétel. Ha most (4) igaz, akkor tetszőleges x ∈ R esetén cx = (y_{0}P)x + (y_{1}Q)x = y_{0}(P x) + y_{1}(Qx) ≤ y_{0}b_{0} + y_{1}b_{1}, vagyis a jobboldal felső korlát cx-re, így (2) teljesül. Megfordítva, ha (4) nem teljesül, akkor a Farkas lemma (2.4 tételbeli alakja) szerint létezik olyan x vektor, amelyre P x = 0, Qx ≤ 0, cx > 0, vagyis ilyenkor (3) nem teljesül. •

Egy egyszerű fogással a 2.6 tételt kiterjeszthetjük arra az esetre, amikor R a

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

egyenlőtlenség-rendszer megoldás-halmazát jelöli.

TÉTEL 2.7 Tegyük fel, hogy R nemüres, és legyen c = (c_{0}, c_{1}) adott vektor. A következők ekvivalensek.

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

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

(3) Nem létezik olyan x = (x_{0}, x_{1}) vektor, amelyre cx > 0, és P x_{0} + Ax_{1} = 0, Qx_{0} + Bx_{1} ≤ 0.

(4) 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)

Biz. Az x_{1} ≥ 0 kívánalmat explicit beírhatjuk az egyenlőtlenségek közé 0x_{0} + (−I)x_{1} ≤ 0 alakban. Erre alkalmazva a 2.6 tételt, az ottani feltételek éppen az itteniekbe mennek át. •

2.2.2 Optimalitási feltételek

Tegyük most fel, hogy R nemüres és cx felülről korlátos R felett. A fő kérdésünk mindezek után az, hogy mennyi max{cx : x ∈ R}, illetve, hogy miként lehetne az optimum helyeket jellemezni. Az utóbbi kérdéssel kezdjük.

TÉTEL 2.8 Tegyük fel, hogy az R := {x : P x = b_{0}, Qx ≤ b_{1}} poliéder nemüres, {cx : x ∈ R} felülről korlátos, és x^{∗} az R egy eleme. Jelölje Q_{∗}^{=} a Q mátrix azon sorai által alkotott részmátrixot,

amelyeknek megfelelő egyenlőtlenségeket x^{∗} egyenlőséggel teljesíti. Legyen M = ( \begin{matrix}P \\ Q \end{matrix} ). 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.

(2) Nem létezik olyan x′ elem, 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 és y(b − Mx^{∗}) = 0. (Miután mind y_{1}, mind b_{1} − Qx^{∗} nemnegatív, az utolsó egyenlőség azt jelenti, hogy ha y_{1} valamely komponense pozitív, akkor a neki megfelelő primál egyenlőtlenség egyenlőséggel teljesül, és így cx^{∗} = by).

Biz. (1) ⇒ (2) Ha létezik a szóbanforgó x′, akkor kicsiny pozitív λ-ra a x^{∗} + λx′ vektor R-ben van, ami cx′ pozitívsága miatt ellentmond x^{∗} maximalitásának.

(2) ⇒ (3) Ha az (y_{0}, y_{∗}^{=}) ( \begin{matrix}P \\ Q_{∗}^{=} \end{matrix} ) = c rendszernek létezik olyan megoldása, amelyben y_{∗}^{=} ≥ 0, akkor

ezt nullákkal kiegészítve az előírt (y_{0}, y_{1})-t kapjuk. Ha nem létezik ilyen (y_{0}, y_{∗}^{=}), akkor a Farkas lemma szerint létezik olyan x′, amelyre P x′ = 0, Q_{∗}^{=}x′ ≤ 0, cx′ > 0, ellentétben (2)-vel.

(3) ⇒ (1) Tetszőleges x ∈ R esetén cx = (yM)x = y(Mx) ≤ yb. Másrészt (3) szerint y(b − Mx^{∗}) = 0, azaz y(Mx^{∗}) = yb és így cx^{∗} = (yM)x^{∗} = y(Mx^{∗}) = yb ≥ cx, vagyis x^{∗} valóban maximalizálja cx-t R felett. •

Ismét csak kiterjeszthetjük a tételt az általános alakra.

TÉTEL 2.9 Tegyük fel, hogy a

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

rendszerrel definiált R poliéder nemüres, {cx = c_{0}x_{0} + c_{1}x_{1} : x ∈ R} felülről korlátos, és legyen x^{∗} = (x_{0}^{∗}, x_{1}^{∗}) az R egy eleme. Jelölje (Q_{∗}^{=}, B_{∗}^{=}) a (Q, B) mátrix azon sorai által alkotott részmátrixot, amelyeknek megfelelő egyenlőtlenségeket x^{∗} egyenlőséggel teljesíti. 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.

(2) Nem létezik olyan x′ = (x′_{0}, x′_{1}), amelyre x′_{1} ≥ 0, P x_{0} + Ax_{1} = b_{0}, Q_{∗}^{=}x_{0} + B_{∗}^{=}x_{1} ≤ b_{∗}^{=} és cx′ > 0.

(3) Létezik olyan y = (y_{0}, y_{1}) vektor, amelyre y_{1} ≥ 0, y_{0}P +y_{1}Q = c_{0}, y_{0}A+y_{1}B ≥ c_{1}, az y_{1} valamely komponense csak akkor lehet pozitív, ha a neki megfelelő primál egyenlőtlenség egyenlőséggel teljesül továbbá az x_{1} valamely komponense csak akkor lehet pozitív, ha a neki megfelelő duál egyenlőtlenség egyenlőséggel teljesül (és így cx^{∗} = by). •

2.2.3 Dualitás tétel

Miután jellemeztük az optimum helyeket tekintsük a lineáris programozási optimalizálási probléma legáltalánosabb alakját. A primál probléma a következő:

{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.18)

A 2.7 tételben láttuk, hogy a maximumra a (2.16) poliédernek tetszőleges y = (y_{0}, y_{1}) eleme egy felső korlátot biztosít, melynek értéke cy = c_{0}y_{0} + c_{1}y_{1}. A legerősebb (azaz legkisebb) felső korlátot persze úgy kapjuk, ha ezt a cy-t minimalizáljuk. Célszerű tehát a primál optimalizálási problémához hozzárendelni egy úgynevezett duális optimalizálási feladatot:

{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.19)

A (2.19)-ban szereplő poliédert R^{∗}-gal jelöljük és duális poliédernek hívjuk. (Figyelem: R^{∗} az m := m_{1} + m_{2} dimenziós térben van, míg R az n := n_{1} + n_{2} dimenziósban. Az R^{∗} nem csak az R primál poliédertől függ, hanem a c-től is, sőt az R megadásától is.)

TÉTEL 2.10 (Dualitás tétel) Tegyük fel, hogy a (2.18) 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 primál optimalizálási feladatban a maximum egyenlő a duál feladatban szereplő minimummal.

A korábban látott redukció szerint elég a tételt a következő speciális esetére igazolni.

TÉTEL 2.11 (Dualitás tétel speciális alak) Tegyük fel, hogy az R := {x : P x = b_{0}, Qx ≤ b_{1}} primál poliéder nemüres és hogy az R^{∗} := {y = (y_{0}, y_{1}) : yM = c, y_{1} ≥ 0} duális poliéder nemüres

(ami avval ekvivalens, hogy \{cx : x ∈ R\} felülről korlátos), ahol M ismét a ( \begin{matrix}P \\ Q \end{matrix} ) mátrixot jelöli.

Ekkor max(cx : x ∈ R) = min(by : y ∈ R^{∗}).

Biz. Tetszőleges x ∈ R és y ∈ R^{∗} elemekre cx = (yM)x = y(Mx) ≤ y_{0}b_{0} + y_{1}b_{1} = yb. Így max ≤ min . Az egyenlőség igazolásához egy olyan x^{∗} ∈ R és y^{∗} ∈ R^{∗} primál és duál megoldás-párt kell találnunk, amelyekre cx^{∗} = by^{∗}. Az 1.21 következmény szerint, ha {cx : x ∈ R} felülről korlátos, akkor a maximum egy x^{∗} erős bázis-megoldáson felvétetik. A 2.8 tétel szerint létezik olyan y^{∗} ∈ R^{∗} vektor, amelyre y^{∗}(b − Mx^{∗}) = 0, amiből y^{∗}b = cx^{∗} következik. •

Feladat 2.6 Irjuk fel a min{α : Ax − αb = b, (x, α) ≥ 0} lineáris program duálisát, igazoljuk mind a primál, mind a duál rendszer megoldhatóságát, és a dualitás tételből vezessük le a Farkas lemmát (2.1 tétel).

Feladat 2.7 Tegyük fel, hogy az {x : Ax = b, x ≥ 0} poliéder nem üres. Az A egy a_{i} oszlopát érdektelennek mondjuk, ha a poliéder minden x elemére x(i) = 0. Igazoljuk, hogy van olyan y vektor, amelyre yb = 0, yA ≥ 0 és ya_{i} pontosan akkor pozitív, ha a_{i} érdektelen!

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.

Feladat 2.8 Tekintsük az {min cx : Ax = b, x ≥ 0} lineáris programot. Legyen A′ az A érdekes oszlopai által alkotott részmátrix és jelölje c′ a c megfelelő részét. Igazoljuk hogy c akkor és csak akkor neutrális, ha létezik olyan y, amelyre yA′ = c′.

Feladat 2.9 Az R := {Ax = b, x ≥ 0} poliéder valamely x_{0} eleme akkor és csak akkor minimalizálja cx-t R-n, ha létezik egy olyan c-vel ekvivalens nemnegatív vektor, amely merőleges x_{0}-ra.

Feladat 2.10 Tekintsük az R := {x : Ax ≤ b, x ≥ 0} primál és R^{∗} = {y : yA ≥ c, y ≥ 0} duál poliédereken definiált max{cx : x ∈ R} és min{by : y ∈ R^{∗}} primál-duál lineáris program párt, és tegyük fel, hogy R és R^{∗} nem üres. Igazoljuk, hogy az A-nak van olyan A′ nemszinguláris részmátrixa (mindegy milyen méretű), amelyre az A′x′ = b′ egyértelmű x′ megoldásából nullák hozzávételével keletkező x_{1} eleme R-nek (ahol b′ azon része b-nek, amely az A′ sorainak felel meg) továbbá az y′A′ = c′ egyértelmű y′ megoldásából nullák hozzávételével keletkező y_{1} eleme R^{∗}-nak. Mutassuk meg, hogy x_{1} primál optimum, y_{1} duál optimum.

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

Vizsgáljuk meg, hogy egy (nemüres) poliéder mikor fekszik teljesen egy adott zárt féltérben. Tekintsük a (2.15) rendszer által definiált R poliédert, és tegyük fel, hogy R nemüres. 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.20)

egyenlőtlenség logikai következménye a (2.15) rendszernek, ha (2.15) minden megoldása teljesíti (2.20)-t. Ez nyilván avval egyenértékű, hogy az R poliéder benne van az {x : cx ≤ γ} féltérben. A (2.20) egyenlőtlenség lineáris következménye (2.15)-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.21)

Abban a speciális esetben, amikor A és B üres, az R-t definiáló rendszer a

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

alakra egyszerűsödik, és ilyenkor a cx ≤ γ egyenlőtlenség definíció szerint akkor lineáris következmény, ha létezik olyan y := (y_{0}, y_{1}), amelyre

y_{1} ≥ 0, y_{0}P + y_{1}Q = c, yb ≤ γ.  (2.23)

TÉTEL 2.12 Feltéve, hogy R nemüres, (2.20) akkor és csak akkor lineáris következménye (2.15)-nek, ha logikai. Speciálisan, cx ≤ γ akkor és csak akkor lineáris következménye (2.22)-nek, ha logikai.

Biz. Először a speciális esetet bizonyítjuk, és ebből majd egyszerű fogással következik az általános. Tegyük fel először, hogy cx ≤ γ lineáris következmény, azaz létezik a szóbanforgó y. Ekkor (2.22)

bármely x megoldására cx = [(y_{0}, y_{1}) ( \begin{matrix}P \\ Q \end{matrix} )]x = y_{0}(P x) + y_{1}(Qx) ≤ y_{0}b_{0} + y_{1}b_{1} = yb ≤ γ, azaz cx ≤ γ

valóban logikai következmény.

Megfordítva, tegyük fel, hogy cx ≤ γ logikai következmény. Jelölje A′ azt az m_{0} × 1-es mátrixot, melynek egyetlen oszlopa a −b_{0} vektor, míg B′ azt az m_{1} × 1-es mátrixot, amelynek egyetlen oszlopa a −b_{1} vektor. Legyen c′ := (c, −γ) és x′ := (x, α) (itt tehát γ a tételben megadott szám, míg α egy új változó, amellyel az x vektort kiegészítettük).

Tekintsük a (2.23) rendszert. Ha ennek van y megoldása, akkor az teljesíti a tétel által (a speciális esetben) megkívánt tulajdonságokat. Tegyük fel indirekt, hogy nem létezik ilyen y. Ekkor a 2.4 tétel szerint létezik olyan x′ = (x, α), amelyre

α ≥ 0, P x − αb_{0} = 0, Qx − αb_{1} ≤ 0, cx − αγ > 0.  (2.24)

Ha most α = 0, akkor ez a következő alakot ölti:

P x = 0, Qx ≤ 0, cx > 0.  (2.25)

Ebből következik, hogy az R poliéder egy z elemére bármilyen pozitív λ esetén z+λx benne van R-ben, ugyanakkor c(z + λx) bármilyen nagy lehet, ha λ nő, vagyis (2.23) nem volna logikai következmény.

Amennyiben α pozitív, úgy feltehető, hogy α = 1, mert α-val végigoszthatunk. Most (2.24) azzal ekvivalens, hogy

P x = b_{0}, Qx ≤ b_{1}, cx > γ,  (2.26)

vagyis az x létezése cáfolja, hogy cx ≤ γ logikai következmény volna.

Az általános eset bizonyításához legyen B^{∗} := ( \begin{matrix}B \\ −I \end{matrix} ) , Q^{∗} := ( \begin{matrix}Q \\ 0 \end{matrix} ), ahol I egy n_{2} × n_{2}-es

egységmátrix, míg 0 egy n_{2} × n_{1}-es nulla-mátrix. Legyen b_{1}^{∗} := ( \begin{matrix}b_{1} \\ 0 \end{matrix} ), ahol 0 most egy n_{2} dimenziós

0-vektor. Könnyen ellenőrizhető, hogy a tétel speciális esete, a P, Q^{∗}, A, B^{∗} mátrixokra felírva a ( \begin{matrix}b_{0} \\ b_{1}^{∗} \end{matrix} )

jobboldallal, éppen az általános alakkal ekvivalens. •

A megelőző szakaszban megmutattuk, hogy a dualitás tétel miképp vezethető le a Farkas lemmából és abból a tételből, hogy a maximum (erős bázis-megoldáson) felvétetik. A 2.12 tétel bizonyítása csak a Farkas lemmáre támaszkodott. Most megmutatjuk, hogy a dualitás tétel könnyen levezethető a 2.12 tételből.

TÉTEL 2.13 (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^{∗}).

Biz. Az x és y nem-negatívitása miatt x ∈ R, y ∈ R^{∗} esetén cx ≤ (yA)x = y(Ax) ≤ yb, így mindenesetre cx felülről korlátos R-n, by pedig alulról R^{∗}-n. Legyen γ_{s} := sup(cx : x ∈ R) és γ_{i} := inf(by : y ∈ R^{∗}). Ekkor tetszőleges x ∈ R, y ∈ R^{∗} esetén cx ≤ γ_{s} ≤ γ_{i} ≤ by. A tételhez azt kell belátnunk, hogy létezik x^{∗} ∈ R, amelyre cx^{∗} = γ_{i} és létezik y^{∗} ∈ R^{∗}, amelyre by^{∗} = γ_{s}. Szimmetria miatt elég y^{∗} létezését belátnunk, x^{∗}-é analóg módon következik.

Most tehát a cx ≤ γ_{i} egyenlőtlenség logikai következménye a Bx ≤ b, x ≥ 0 egyenlőtlenségrendszernek, így a 2.12 tétel szerint létezik olyan y^{∗} ≥ 0, amelyre y^{∗}B ≥ c és y^{∗}b ≤ γ_{i}. De itt a γ_{i} definíciója miatt nem szerepelhet szigorú egynelőtlenség, azaz y^{∗}b = γ_{i}. •

2.2.5 Neumann tétele

A játékelméletben fontos alkalmazásra lel a következő tétel. Egy vektor tetején értsük a legnagyobb koordinátájának az értékét. A vektor alja legyen a legkisebb koordinátájának az értéke.

TÉTEL 2.14 (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].

Biz. A primál feladat egy olyan minimális w szám keresésével ekvivalens, amelyre létezik x ≥ 0 vektor úgy, hogy 1x = 1 és Ax ≤ (w, w, …, w) érvényes. Ez viszont éppen a

{min w : −Ax + (w, w, …, w) ≥ 0, x ≥ 0, 1x = 1}  (2.27)

lineáris programmal egyenértékű.

A duális feladat egy olyan maximális z szám keresésével ekvivalens, amelyre létezik y ≥ 0 vektor úgy, hogy 1y = 1 és yA ≥ (z, z, …, z) érvényes. Ez viszont éppen a

{max z : y(−A) + (z, z, …, z) ≤ 0, y ≥ 0, 1y = 1}  (2.28)

lineáris programmal egyenértékű. Miután a (2.28) program duálisa éppen a (2.27) program, így a dualitás tételből adódik, hogy a w minimális értéke egyenlő a z maximális értékével. •

December 28, 2001

2.3 JÁTÉKELMÉLETI ALKALMAZÁS

Sári és Oszi a következő játékot játsszák. Egyszerre elrejtenek a kezükben egy vagy két forintot és egyúttal tippelnek, hogy a másik egy vagy két forintot rejtett-e el. Amennyiben mindkettejük tippje helyes, avagy mindkettejük tippje hibás, úgy a játék döntetlen. Ha viszont pontosan az egyikük tippje helyes, úgy a jól tippelő elnyeri a kettejük által elrejtett pénz összegét (ami tehát 2,3 vagy 4 forint). Ez a játék egy fordulója. Kérdés, hogy ha N fordulót játszanak, milyen stratégiát érdemes követni.

Mindkét játékos egy lehetséges fordulóbeli játékát egy számpárral lehet megadni, amelynek első tagja azt jelenti, hogy hány forintot rejtett, a második tagja pedig azt, hogy hány forintot tippelt. Vagyis egy fordulóban mindkét játékos előtt négy lehetséges választás van: [1, 1], [1, 2], [2, 1], [2, 2]. Nevezzük ezeket elemi vagy tiszta stratégiának. A későbbiekben ezen sorrend szerint fogunk rájuk hivatkozni (tehát pl. a 3-dik elemi stratégia [2, 1]).

Ha Sári például mindig az [1, 1] párt választja, akkor könnyen rosszul járhat, mert ezt ellenfele hamar kifigyelheti, és akkor a [2, 1] válasszal mindig nyer. Sári persze ravaszabbul is eljárhat, például mindig ugyanúgy rejt és tippel, mint ahogy Oszi tette a megelőző fordulóban, de ennek a stratégiának is az a hátulütője, hogy Oszi előbb-utóbb rájöhet az alkalmazott szabályra és akkor már könnyen nyer. Ez a veszély minden determinisztikusan meghatározott választási szabály esetén fennáll. Ezt elkerülendő Sári minden fordulóban a véletlentől teszi függővé a választását. Természetesen az a kérdés, hogy milyen valószínűséggel válasszon a négy lehetőség közül.

Tételezzük fel, hogy a lejátszott N forduló során Oszi c_{i}-szer játszotta meg az i-dik elemi stratégiát (i = 1, …, 4), azaz ∑ c_{i} = N. Tegyük fel, hogy Sári a következő stratégiát alkalmazta: mindig az ellenkezőjét mondja annak, mint amit tippel és ezen belül 1/2 valószínűséggel rejt 1 vagy 2 forintot. Másként szólva a (0, 1/2, 1/2, 0) valószínűségek szerint választ minden fordulóban a négy elemi stratégiából. Várható értékben mekkora nyereségre számíthat?

Oszi c_{1}-szer játszott [1, 1]-t. Átlagosan ezen c_{1} eset felében Sári [1, 2]-t játszik, amikoris Sári 2 forintot veszít, a másik c_{1}/2 esetben Sári [2, 1]-t játszik, és ekkor 3 forintot nyer. Tehát Sári várható nyeresége 3c_{1}/2 − 2c_{1}/2 = c_{1}/2.

c_{2} + c_{3} esetben Oszi mást tippel, mint rejt, ezek a fordulók tehát mind döntetlenek.

Végül Oszi c_{4} esetben játszik [2, 2]-t. Ezeknek átlagosan a felében Sári [1, 2]-t játszik és nyer 3 forintot, míg a másik felében Sári [2, 1]-t játszik és veszít 4 forintot. Ezen c_{4} esetben tehát Sári várható össz-nyeresége 3c_{4}/2 − 4c_{4}/2 = −c_{4}/2.

Megállapíthatjuk tehát, hogy az N forduló során Sári várható össz-nyeresége (c_{1} − c_{4})/2 forint, ami persze veszteség, ha c_{4} > c_{1}. Vagyis a fent választott y = (0, 1/2, 1/2, 0) valószínűségi választás mellett Sári akkor jár a legrosszabbul, ha c_{4} = N és c_{1} = c_{2} = c_{3} = 0. Ekkor Sári teljes vesztesége várhatólag N/2 forint, azaz fordulónként átlagosan 1/2 Ft. Azaz Sári ezzel a stratégiával azt tudja biztosítani magának, hogy átlagos vesztesége Oszi bármilyen játéka esetén se haladja meg az 1/2 forintos fordulónkénti átlagot.

Az y = (0, 1/2, 1/2, 0) valószínűségek helyett természetesen választhatunk más eloszlást is. Nevezzünk egy y vektort sztochasztikusnak, ha nem-negatív és 1 · y = 1. Minden sztochasztikus vektor egy kevert stratégiát definiál. Természetesen a fentiek mintájára tetszőleges kevert stratégiára rögzített c := (c_{1}, …, c_{4}) gyakoriságok esetén kiszámíthatjuk Sári várható nyereségét. Könnyű ellenőrizni, hogy ez éppen az (yA)c szám lesz, ahol A az úgynevezett kifizetési mátrix (Sári szempontjából). Azaz A egy 4 · 4-s mátrix, amelynek a_{ij} eleme Sári nyereségét (másszóval Oszi veszteségét) jelzi, ha Sári az i-dik, míg Oszi a j-dik elemi stratégiát játssza.

Sári akkor fogja egy másik kevert stratégiáját jobbnak tekinteni, mint a (0, 1/2, 1/2, 0) kevert stratégia, ha a fordulónkénti átlagos nyeresége nagyobb, mint az előbb adódott −1/2 forint. Van-e ilyen jobb stratégia és hogyan lehet a legjobbat megtalálni?

Általánosabban fogalmazva legyen adva egy A n×m-es mátrix. A sorjátékos Sári és az oszlopjátékos Oszi azt játsszák, hogy minden fordulóban Sári kiválasztja A-nak egy i sorát, míg Oszi A-nak egy j oszlopát, és ennek megfelelően Oszi fizet Sárinak a_{ij} forintot (ami persze azt jelenti, hogy ténylegesen Sári fizet, amennyiben a_{ij} negatív.) Az előbbi játékhoz például a következő mátrix tartozik.

( \begin{matrix}& [1, 1] & [1, 2] & [2, 1] & [2, 2] \\ [1, 1] & 0 & 2 & −3 & 0 \\ [1, 2] & −2 & 0 & 0 & 3 \\ [2, 1] & 3 & 0 & 0 & −4 \\ [2, 2] & 0 & −3 & 4 & 0 \end{matrix} )

Sári egy kevert stratégiáját egy y (m-dimenziós) sztochasztikus vektor definiálja éspedig úgy, hogy Sári minden fordulóban y(i) valószínűséggel választja az i-dik sort.

Tegyük fel, hogy N forduló során Oszi c_{j}-szer játszotta meg a j-dik oszlopot (∑ c_{j} = N). Ekkor a j-dik oszlop gyakorisága x_{j} := c_{j}/N. Nyilván a gyakoriságok x := (x_{1}, …, x_{n}) vektora sztochasztikus.

Mennyire jó Sárinak egy rögzített y sztochasztikus vektor mint kevert stratégia? Adott x gyakoriság esetén Sári össz-nyeresége várható értékben (yA)c, vagyis fordulónkénti átlagos nyeresége (yA)x. Ez azon x gyakoriság mellett a legrosszabb Sárinak, amelyre (yA)x legkisebb. Vagyis egy y kevert stratégia f(y) jóságát az f(y) := min((yA)x : x sztochasztikus) érték méri. Sárinak tehát az az y a legjobb, amelyre f(y) maximális.

Rögzített y esetén nagyon könnyű f(y)-t megállapítani, hiszen ez az min(a_{y}x : x ≥ 0, 1 · x = 1) lineáris programnak az optimuma, ahol a_{y} := yA. Mivel az optimum csúcsokban vétetik fel és az {x : x ≥ 0, 1 · x = 1} poliéder csúcsai épp a (0, …, 0, 1, 0, …, 0) alakú egységvektorok (n darab), ezért f(y) nem más, mint az yA vektor legkisebb komponense.

Sári optimális kevert stratégiájának megkeresése tehát egy olyan sztochasztikus y vektor megkeresésével egyenértékű, amelyre az yA vektor legkisebb komponense a lehető legnagyobb. Tehát egy olyan maximális z számot kell keresnünk, amelyre létezik y ≥ 0 úgy, hogy 1·y = 1 és yA ≥ (z, z, …, z). Ez viszont éppen a következő lineáris programozási feladat.

max(z : y(−A) + (z, …, z) ≤ 0, y ≥ 0, 1 · y = 1)  (P)

A duális lineáris program

min(w : −Ax + (w, w, …, w) ≥ 0, x ≥ 0, 1 · x = 1).  (D)

Ez az előbbiek mintájára azzal ekvivalens, hogy keressünk olyan sztochasztikus x vektort, amelyre az Ax vektor legnagyobb komponense a lehető legkisebb. Egy ilyen x vektor nem csak a sorjátékos, Sári szempontjából elképzelhető leghátrányosabb gyakoriságként értelmezhető (ahogy eddig tettük), hanem az oszlopjátékos, Oszi optimális kevert stratégiájaként is. Tekintettel arra, hogy mind a primál, mind a duál lineáris programnak van megoldása, a szóbanforgó minimum és maximum létezik és a dualitás tétel szerint egymással egyenlők. Ebből kapjuk a következő tételt.

TÉTEL 2.15 (Neumann János) 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.

Visszatérve a kiindulási mátrixjátékhoz, kiszámítható (például a szimplex módszer segítségével), hogy a legjobb kevert stratégia [0, 3/5, 2/5, 0]. Ennek alkalmazásával Sári biztosíthatja, hogy várható értékben nem veszít.

Ha ténylegesen játszani akarjuk a játékot, meg kell állapodni abban, hogy egy fordulóban ki mondja ki először a tippjét. Oszi nagyvonalú akar lenni és felajánlja, hogy mindig ő mondja ki először. Tehát mindketten rejtenek, majd Oszi kimondja a tippjét, utána Sári is kimondja a tippjét. Feltéve, hogy Sári gondolkodhat Oszi tippjének ismeretében (de persze azon már nem változtathat, amennyit rejtett), ki tudja-e aknázni Sári ezt a látszólagos előnyt? Ránézésre azt gondolhatnánk, hogy ez nem jelenthet valódi előnyt, hiszen az elrejtett forintok száma minden fordulóban azelőtt kerül meghatározásra mielőtt akármelyik tipp elhangzik. Mindenesetre a fenti általános model segítségével a kérdést precízen meg lehet válaszolni. Az eredeti mátrixot még kiegészítjük négy sorral, mivel Sárinak négy új tiszta stratégiája adódott. Nevezetesen: A: Sári 1-t rejt és ugyanazt tippeli, mint Oszi, B: Sári 1-t rejt és az ellenkezőjét tippeli, mint Oszi, C: 2-t rejt és ugyanazt tippeli, mint Oszi, D: 2-t rejt és az ellenkezőjét tippeli, mint Oszi. A szimplex módszer segítségével ki lehet számítani, hogy Sári optimális kevert stratágiáját a következő sztochasztikus vektor adja meg: [0, 56/99, 40/99, 0, 0, 2/99, 0, 1/99].

Ennek alkalmazásával Sári (Oszi bármilyen játéka esetén is) átlagosan 4/99 forint nyereségre számolhat fordulónként.

Végül külön is megfogalmazzuk Neumann fenti min-max tételét, immár játékelméleti fogalmak nélkül. Tetszőleges z vektorra jelölje min z illetve max z a z vektor komponenseinek minimumát illetve maximumát.

NEUMANN TÉTELE Tetszőleges A mátrix esetén max(min(yA) : y ≥ 0, 1·y = 1) = min(max(Ax) : x ≥ 0, 1 · x = 1).

Biz. A baloldal optimuma épp a fenti (P) primál program optimuma, a jobboldalé pedig a (D) duál program optimuma. •

December 28, 2001

2.3.1 ELIMINÁCIÓS ELJÁRÁS

Az alábbiakban megadunk egy eléggé kézenfekvő eliminációs eljárást a

Bx ≤ b  (2.29)

egyenlőtlenség-rendszer megoldására. A módszer Fouriertől származik, amelyet később Motzkin újra felfedezett, így az irodalomban Fourier-Motzkin eliminációként hivatkozzák. Egyúttal megadjuk a megoldhatóság szükséges és elegendő feltételét.

TÉTEL 2.16 (Farkas lemma, változat) (2.29)-nek akkor és csak akkor létezik megoldása, ha nincs megoldása az

yB = 0, y ≥ 0, yb < 0  (2.30)

rendszernek.

Biz. Nyilván (2.29) és (2.30) mindegyike nem oldható meg, mert akkor 0 = (yB)x = y(Bx) ≤ yb < 0.

Annak kimutatására, hogy a két rendszer egyike megoldható az oszlopok n száma szerinti indukciót alkalmazunk. n = 1-re a tétel könnyen ellenőrizhető. Rögzített oszlopszám esetén az első oszlopban szereplő nemnulla elemek száma szerinti indukciót használunk. Amennyiben ez a szám nulla, azaz b_{1} = 0, úgy az első oszlopot eltörölve mind a primál, mind a duál feladat megoldhatósága szempontjából ekvivalens feladatot kapunk, és így indukcióval készen vagyunk.

Legyen most b_{1} ≠ 0 és tegyük fel először, hogy b_{1}-nek van pozitív és negatív komponense is. Mivel egy egyenlőtlenség-rendszer egy sorát pozitív számmal szorozva ekvivalens rendszert kapunk, feltehetjük, hogy b_{1} minden eleme (0, ±1)-értékű. Legyen mondjuk b_{1,1} = 1. Minden olyan i sorra, amelyre b_{1}(i) = −1, vegyük az egyenlőtlenség-rendszerhez a _{i′}bx′ ≤ b(i′) egyenlőtlenséget, ahol _{i′}b := (_{1}b +_{i} b) és b(i′) := b(1) + b(i), majd töröljük el az első sort. Jelölje a kapott rendszert B′x′ ≤ b′. A B′ első oszlopában kevesebb nemnulla elem van, mint b_{1} -ben, hiszen minden új sor első eleme nulla és a kitörölt első sor első eleme nemnulla volt. Így B′x′ ≤ b′-re indukció miatt érvényes a tétel.

Amennyiben B′x′ ≤ b-nek létezik megoldása, úgy ezt válasszuk olyannak, amelyben x′(1) a lehető legkisebb. Ekkor létezik egy olyan i index, amelyre b_{1}(i) = −1 és _{i}bx′ = b(i). Miután (_{1}b +_{i} b)x′ ≤ b(1) + b(i), következik, hogy _{1}bx′ ≤ b(1), azaz x′ automatikusan kielégíti (2.29)-t. Ha B′x′ ≤ b-nek nincs megoldása, akkor indukció miatt létezik olyan y′ ≥ 0, amelyre az y′B′ = 0 és y′b′ < 0. Legyen most y(1) := ∑{y(i′) : b_{1}(i) = −1}, y(i) := y′(i) ha i ≥ 2, b_{1}(i) ≥ 0 és y(i) := y′(i) + y′(i′), ha b_{1}(i) = −1. Könnyen látszik, hogy az így definiált y kielégíti (2.30)-t.

Az az eset marad hátra, amikor b_{1} nemnegatív, de nem nulla. (Ha b_{1} nem-pozitív, helyettesíthetjük a negatívjával). Amennyiben b_{1} minden komponensében pozitív, úgy kellően kicsiny λ számra λb_{1} ≤ b, és így az n-dimenziós x = (λ, 0, 0, …, 0) vektorra Bx ≤ b. Ha b_{1}-nek vannak 0 komponensei, úgy jelölje B′ a B azon részmátrixát, amely b_{1} oszlop valamint a b_{1} pozitív komponenseinek megfelelő sorok eltörlésével áll elő. Amennyiben B′x′ ≤ b′-nek létezik megoldása, akkor ezt egy alkalmasan kicsiny λ komponenssel kibővítve a Bx ≤ b egy megoldását kapjuk. Ha B′x′ ≤ b-nek nincs megoldása, akkor indukció alapján létezik y′ ≥ 0, amelyre y′B′ = 0 és y′b′ < 0. Ekkor az y′-t 0 komponensekkel kiegészítve (2.30)-nek kapjuk egy megoldását. •

A bizonyítást induktívan mondtuk el, de valójában ez egy véges algoritmust eredményez. Nevezetesen, a leírt eljárás ismétlésével meg tudunk szabadulni az első oszloptól, másszóval elimináljuk az első változót (persze azon az áron, hogy számos új egyenlőtlenséget a rendszerhez veszünk). Majd ezt ismételgetve egymás után elimináljuk a változókat, amíg egyetlen változónk marad. Ha az erre kapott (”igen sok”) egyenlőtlenségnek van megoldása (ezt egy változó esetén triviális eldönteni), akkor a fentiek alapján visszafelé haladva meg tudjuk határozni (2.29)-nek egy megoldását.

Az eljárás hátránya, hogy egyetlen változó eliminálása sok új egyenlőtlenséget hoz be, vagyis menet közben az egyenlőtlenségek száma nagyon felszaporodhat. Sajnos ez nem csak elvi lehetőség, amint a következő példa mutatja. Legyen p pozitív egész és n := 2^{p} +p+2. n darab változónk lesz: x_{1}, …, x_{n}. 8\binom{n}{3} egyenlőtlenségünk van, mindegyik ±x_{i} ± x_{j} ± x_{k} ≤ b_{ijk} alakú, ahol b_{ijk} adott számok. t szerinti indukcióval látható, hogy t változó kiejtése után az új egyenlőtlenségek között szerepelni fog az összes ±x_{j_{1}} ± x_{j_{2}}, …, ±x_{j_{s}} ≤ b_{j_{1},...,j_{s}} alakú, ahol s = 2^{t} + 2 és t + 1 ≤ j_{1} < j_{2} … < j_{s} ≤ n. Így p lépés után a megmaradt változók száma n′ = n−p = 2^{p} +2 míg az egyenlőtlenségek száma legalább 2^{2^{p}+2} = 2^{n′}.

Tapasztalat szerint a FM elimináció legfeljebb csak kis példákon használható, nagyobbakon tipikusan ténylegesen kezelhetetlenül sok egyenlőtlenség keletkezik.

A példában olyan egyenlőtlenség rendszer szerepelt, amelynek minden sorában három 1 abszolút értékű együttható volt. Érdekes, hogy ha csak két 1 abszolút értékű együttható van minden sorban, akkor a Fourier-Motzkin eljárás polinomiális futásidejű. Egy (sor)vektort nevezzünk szimplának, ha vagy egy nemnulla eleme van (és erről feltehető, hogy 1 abszolút értékű), vagy kettő, melyek mindegyike 1 abszolút értékű. Könnyű megfigyelni, hogy ha a kiindulási mátrix minden sora szimpla, akkor a fentebb leírt FM eljárás során keletkező új sorok is szimplák lesznek. Miután szimpla vektor csak kevés lehet, ilyen esetben az FM eljárás polinomiális. (Természetesen menetközben a redundáns egyenlőtlenségeket ki kell dobni: ha például az x_{1} +x_{2} ≤ 3 és az x_{1} +x_{2} ≤ 4 egyenlőtlenségek adódnak ki, akkor az utóbbi felesleges.)

Szimpla sorokból álló mátrixokra, egészértékű b esetén azt is el lehet dönteni, hogy a Bx ≤ b rendszernek létezik-e egész értékű megoldása. Az az egyetlen különbség, hogy ha menetközben keletkezik mondjuk egy 2x_{i} ≤ β alakú egyenlőtlenség, akkor ezt az x_{i} ≤ ⌊β/2⌋ egyenlőtlenséggel kell helyettesíteni.

Gyakorlat 2.11 Tekintsük négy változóban az x_{i} ≥ 0, x_{i} +x_{j} = 1 (1 ≤ i < j ≤ 4) rendszert. Döntsük el az FM eliminációval, hogy van-e megoldása és hogy van-e egész megoldása.

Feladat 2.12 Legyen M a G irányítatlan gráf egy teljes párosítása. Fejlesszünk ki (polinomiális futásidejű) algoritmust annak eldöntésére, hogy létezik-e olyan Z stabil ponthalmaz, amely minden párosítás él egyik végpontját tartalmazza.

Abban a speciális esetben, amikor a mátrix minden sorában vagy egyetlen nemnulla elem szerepel és ennek az abszolút értéke 1, vagy pedig egy +1-es és egy −1-es, akkor az FM elimináció automatikusan fenntartja ezt az alakot. Következik, hogy ha a jobboldali b vektor egészértékű, és a Bx ≤ b rendszernek van megoldása, akkor van egész megoldása is (és az FM egy ilyet meg is talál).

Feladat 2.13 Igazoljuk, hogy egy élsúlyozott irányított gráfban akkor és csak akkor van negatív összsúlyú irányított kör, ha nincsen olyan π := V → R függvény, amelyre π(v) − π(u) ≤ c(uv) fennáll minden uv élre. Továbbá, ha a c súlyfüggvény egészértékű, akkor π is választható annak.

2.4 KÚPOK ÉS POLIÉDEREK ELŐÁLLÍTÁSAI

A 1.5 szakaszban láttuk (a Farkas lemma vagy a dualitás tétel használata nélkül), hogy tetszőleges metszet-kúp előáll generált kúpként (1.42 tétel). Most megmutatjuk ezen eredmény megfordítását. Egy (m sorú) A mátrix esetén jelölje M_{A} az {y : yA ≤ 0} metszet-kúpot és G_{A} az {Ax : x ≥ 0} generált kúpot.

TÉTEL 2.17 Minden K := G_{A} generált kúp metszet-kúp.

Biz. Először a tételt abban a speciális esetben látjuk be, amikor A sorai lineárisan függetlenek. Tekintsük azon y_{i} ≠ 0 m-dimenziós vektorokat, amelyekre y_{i}A ≤ 0 és y_{i} ortogonális A-nak m − 1 lineárisan független oszlopára. Ezen oszlopok konstans szorzó erejéig egyértelműen meghatározzák y_{i}-t. Tehát ha y_{i} egység hosszú, akkor az m − 1 oszlop által feszített hipersík normálisa. Ezért ilyen y_{i} vektorból csak véges sok van. Az ezekből, mint oszlopvektorokból készített mátrixot jelölje B. A definíció szerint A minden a oszlopára aB ≤ 0 és így az A oszlopai által G_{A} kúp minden z elemére zB ≤ 0, azaz G_{A} ⊆ M_{B}.

Tegyük most fel indirekt, hogy itt nem egyenlőség áll, azaz létezik egy b ∈ M_{B} vektor, amely nincs G_{A}-ban. Ez azt jelenti, hogy az {Ax = b, x ≥ 0} rendszer nem oldható meg, és így a Farkas lemma 2.5 tételben kimondott erősebb változata szerint a B-nek az egyik y oszlop olyan, hogy yA ≤ 0 és yb > 0, tehát b nem volna M_{B}-ben, ellentmondás.

Az általános esetre térve válasszunk ki m_{1} := r(A) darab lineárisan független sorát A-nak, és jelölje A_{1} az ezek által alkotott részmátrixot. Ekkor A maradéka előáll ZA_{1} alakban (ami azt fejezi ki, hogy az A_{1}-ben nem lévő A-beli sorok mindegyike az A_{1} sorainak lineáris kombinációja). Amint már beláttuk, a K_{1} := G_{A_{1}} kúp előáll M_{B_{1}} alakban valamely m_{1} sorú B_{1} mátrix segítségével. Jelölje B azt az m sorú mátrixot, amely B_{1}-ből és az aláírt ZB_{1}-ből áll. Könnyű ellenőrizni, hogy egy q_{1} vektor egyrészt akkor és csak akkor van K_{1}-ben, ha q := (q_{1}, Zq_{1}) K-ban van, továbbá, hogy q_{1} akkor és csak akkor van M_{B_{1}}-ben, ha q M_{B}-ben van. Így azután K_{1} = M_{B_{1}}-ből következik, hogy K = M_{B}. •

Érdekességként megjegyezzük, hogy az 2.17 tételből levezethető a 1.42 következmény, a következőképpen. Legyen A és B két m-sorú mátrix. B oszlopainak index halmazát jelölje I, míg A oszlopaiét J.

Lemma 2.18 Ha G_{A} ⊆ M_{B}, akkor G_{B} ⊆ M_{A}.

Biz. G_{A} ⊆ M_{B}-ből következik, hogy A minden oszlopa M_{B}-ben van, azaz b_{i}a_{j} ≤ 0 minden i ∈ I, j ∈ J indexre. Vagyis B minden oszlopa M_{A}-ban van. Így a B oszlopai által generált G_{B} kúp is teljesen M_{A}-hoz tartozik. •

Lemma 2.19 Ha G_{A} ⊇ M_{B}, akkor G_{B} ⊇ M_{A}.

Biz. Legyen a ∈ M_{A}, azaz aA ≤ 0. A G_{A} ⊇ M_{B} feltevés miatt tetszőleges y ∈ M_{B} vektorhoz van olyan x̄ ≥ 0, amelyre y = Ax̄. De ekkor ay = a(Ax̄) = (aA)x̄ ≤ 0, vagyis minden olyan y-ra, amelyre yB ≤ 0 fennáll, hogy ya ≤ 0, és így a Farkas lemma miatt a Bx = a, x ≥ 0 rendszer megoldható, azaz a ∈ G_{B}. •

Következmény 2.20 Ha G_{A} = M_{B}, akkor M_{A} = G_{B}.

(Az A és B szerepének felcserélésével látható, hogy itt az ”akkor” helyett ”akkor és csak akkor” is írható.) Az alábbi tétel tehát a 1.42 tétel ismétlése.

TÉTEL 2.21 Minden M_{A} metszet-kúp generált kúp.

Biz. Tekintsük a G_{A} generált kúpot. Az előbbi tétel szerint ez előáll M_{B} metszet-kúpként valamely B mátrixra. A 2.20 következmény miatt M_{A} = G_{B}. •

Láttuk már korábban (1.41 következmény), hogy minden poliéder előáll mint egy politop és egy generált kúp vektor-összege. Ennek is igaz a megfordítása:

TÉTEL 2.22 Egy Q politop és egy K generált kúp összege poliéder.

Biz. Tegyük fel, hogy a Q az x_{1}, …, x_{k} elemek konvex burka, míg K az y_{1}, …, y_{l} által generált kúp. Tekintsük az eggyel magasabb dimenziós térben a {∑_{i} λ_{i}(x_{i}, 1) + ∑_{j} μ_{j}(y_{j}, 0) : λ_{i} ≥ 0, μ_{j} ≥ 0} generált kúpot. Ez a 2.17 tétel szerint előáll metszet-kúpként, azaz egy {Ax − λb ≤ 0, λ ≥ 0} rendszer megoldás halmazaként. De ekkor K + Q nem más, mint az {x : Ax ≤ b} poliéder. •

Következmény 2.23 Vektorok egy halmaza akkor és csak akkor politop, ha korlátos poliéder.

Tetszőleges K kúpra definiálhatjuk a K^{∗} := {x : xy ≤ 0, minden y ∈ K-ra} poláris kúpot.

TÉTEL 2.24 Ha K generált vagy metszet-kúp, akkor K^{∗∗} = K.

Biz. Tegyük fel K G_{A} alakban van adva. Akkor definíció szerint K^{∗} = M_{A}. Ez előáll K^{∗} = G_{B} alakban. Ekkor K^{∗∗} = M_{B}. De ha M_{A} = G_{B}, akkor M_{B} = G_{A}, azaz K^{∗∗} = K. • Megjegyzés. Tetszőleges K kúpra könnyen igazolható, hogy K^{∗∗} ⊇ K, de ha K nem zárt, akkor itt nem állhat egyenlőség, mert egy kúp polárisa bizonyíthatóan mindig zárt. Érvényes, hogy tetszőleges zárt kúp polárisának polárisa zárt.

Feladat 2.14 Ha egy kúp bővebb egy másiknál, akkor a polárisa szűkebb a másik polárisánál. Két kúp összegének polárisa a polárisaik metszete.

A teljesség kedvéért a 1.41 következményt újra megfogalmazzuk, és egy új bizonyítást adunk rá:

TÉTEL 2.25 Egy P := {x : Ax ≤ b} nemüres poliéder előáll egy Q politop és egy K generált kúp vektor-összegeként.

Biz. Tekintsük az eggyel magasabb (azaz n + 1) dimenziós térben az M := {Ax − λb ≤ 0, λ ≥ 0} metszet-kúpot. Ez előáll generált kúpként is. Feltehető, hogy a generáló elemek utolsó (λ-nak megfelelő) koordinátáinak mindegyike 1 vagy 0. Legyenek a generáló elemek eszerint szétválasztva: (x_{1}, 1), …, (x_{k}, 1), (y_{1}, 0), …, (y_{l}, 0). Tekintsük R^{n}-ben ax x_{i}-k konvex burkaként definiált Q politopot valamint az y_{j} vektorok által generált K kúpot.

Azt állítjuk, hogy P = Q + K. Valóban, legyen először z ∈ P. Ekkor (z, 1) = ∑_{i} λ_{i}(x_{i}, 1) + ∑_{j} μ_{j}(y_{j}, 0), ahol λ_{i} ≥ 0, μ_{j} ≥ 0. Most tehát ∑_{i} λ_{i} = 1 és ezért z_{1} := ∑_{i} λ_{i}x_{i} benne van Q-ban és z_{2} := ∑_{j} μ_{j}y_{j} benne van K-ban. Így z valóban előáll egy Q-beli z_{1} és egy K-beli z_{2} elem összegeként.

Megfordítva, legyen most z_{1} ∈ Q, z_{2} ∈ K. Ekkor (z, 1) = (z_{1}, 1) + (z_{2}, 0) benne van M-ben, azaz Az − 1 · b ≤ 0 vagyis z benne van P -ben. •

2.5 POLIÉDEREK OLDALAI

Egy háromdimenziós poliédert lapok, élek illetve csúcsok határolnak. Ezeket a fogalmakat szeretnénk magasabb dimenzióra általánosítani. A megfelelő fogalmat oldalnak fogjuk nevezni. (Valójában a csúcs fogalmát korábban már bevezettük a csúcsot a poliéder olyan pontjaként definiálva, amely nincs a poliéderhez tartozó szakasz belsejében, vagy ekvivalensen, nem áll elő tőle különböző poliéderbeli pontok konvex kombinációjaként).

Egy R = {x : Qx ≤ b} (nemüres) poliéder F oldala (face) R-nek egy

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

alakú nemüres részhalmaza, ahol δ := max{cx : x ∈ R} valamely cx célfüggvényre, melyre a maximum létezik. Vagyis a poliéder oldala az optimum helyek halmaza valamely célfüggvényre nézve, másként szólva a poliédernek az a része, amely egy hipersíkkal érintkezik, amikor azt kívülről a poliéderhez toljuk.

Az oldal definiálására egy másik természetes lehetőség az lehet, hogy az oldal az R poliédernek egy olyan nemüres (!) része, amelyet akkor kapunk, ha az R-t definiáló egyenlőtlenségek közül bizonyosakra (megengedve, hogy egyre sem vagy esetleg az összesre) egyenlőséget követelünk meg. Az első definíció előnye, hogy független a poliéder megadásától. A második definíció előnye, hogy rögtön mutatja, hogy egy R poliéder oldalának oldala R-nek is oldala vagy azt, hogy két oldal metszete, ha nem üres, akkor oldal. Hiányossága viszont, hogy látszólag függ a poliéder megadásától (azaz Q-tól és b-től). Szerencsére az előnyök egyesíthetők:

TÉTEL 2.26 Poliéder oldalának fenti két definíciója ekvivalens.

Biz. Legyen először F a (2.31) által definiált halmaz. Tekintsük a min{yb : yQ = c, y ≥ 0} duális lineáris programnak egy y′ optimális megoldását. cx = (y′Q)x = y′(Qx) ≤ y′b, amiből következik, hogy egy x′ ∈ R vektor akkor és csak akkor primál optimum (azaz eleme F -nek), ha az y′ minden pozitív komponensére a neki megfelelő primál feltétel egyenlőséggel teljesül (azaz y′(i) > 0-ból _{i}qx = b(i) következik.) Így tehát, ha Q′ illetve b′-vel jelöljük a Q ill. b azon részét, amely az y′ pozitív komponenseinek felel meg, akkor F = {x ∈ R : Q′x = b′}.

Fordítva, legyen Q′ a Q bizonyos sorai által alkotott mátrix, és b′ a b megfelelő része. Jelölje c a Q′ sorainak összegét (azaz c = 1 · Q′), míg δ a b′ komponenseinek összegét (δ := 1 · b′). Most cx = (1 · Q′)x = 1(Q′x) ≤ 1b′ = δ. Ebből adódóan valamely x vektorra x ∈ R, Q′x = b′ akkor és csak akkor teljesül, ha x ∈ R, cx = δ, amiből a tétel következik. •

Az R poliéder maga is oldal (pl. c = 0 célfüggvényre az R minden pontja maximalizálja cx-t, vagy másként, amikor semmilyen egyenlőtlenséget nem kötünk meg egyenlőségként.) A poliédernek egy önmagától különböző oldalát valódi oldalnak nevezzük. Egy tartalmazásra nézve maximális valódi oldalt lapnak hívunk. Fontos szerepet játszanak a (tartalmazásra nézve) minimális oldalak, vagyis az olyan oldalak, melyek valódi részhalmazként már nem tartalmaznak más oldalt.

Tekintsük az R := {x : P x = b_{0}, Qx ≤ b_{1}} nemüres poliédert. Az alábbiakban megvizsgáljuk az R néhány tulajdonságát a

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

leíró rendszer függvényében. Fontos lesz azt is megtudni, hogy két egyenlőtlenség-rendszer mikor határozza meg ugyanazt a poliédert. Az eredményeket a jobb áttekinthetőség kedvéért néha csak arra az alakra fogalmazzuk meg, amikor R az {x : Qx ≤ b} alakban van adva.

A Q mátrix i-dik oszlopát q_{i}-vel, j-dik sorát pedig _{j}q-vel jelöljük. A Qx ≤ b_{1} rendszer egy qx ≤ β egyenlőtlenségéről azt mondjuk, hogy implicit egyenlőség, ha R minden eleme egyenlőséggel teljesíti (azaz, ha a fordított qx ≥ β egyenlőtlenség logikai következménye az R-t meghatározó rendszernek, másszóval, ha az R poliéder teljesen az {x : qx = β hipersíkban fekszik.) 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. (Az explicit P x = b_{1} egyenlőségrendszer tagjait automatikusan implicit egyenlőségeknek tekintjük.)

A Qx ≤ b_{1} egyenlőtlenség-rendszer egyik qx ≤ β tagját feleslegesnek vagy lényegtelennek nevezzük (a (2.32)-re nézve), ha az elhagyásával keletkező rendszer ugyanazt a poliédert definiálja. (Másszóval, qx ≤ β logikai következménye annak a rendszernek, amelyet (2.32-ből kapunk qx ≤ β kihagyásával.) Egy nem felesleges egyenlőtlenség neve lényeges. Hasonlóképpen beszélhetünk arról, hogy 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.

Egy poliéder leírásából egymás után kihagyva az (aktuálisan) felesleges egyenlőtlenségeket és egyenlőségeket olyan leírást kapunk, amelyben már minden egyenlőség és egyenlőtlenség lényeges. Ez persze függhet az elhagyás sorrendjétől, hiszen egy eredetileg felesleges egyenlőtlenség egy másik felesleges egyenlőtlenség elhagyásakor lényegessé válhat. Például, ha a poliéder a három dimenziós tér egy e egyenese, amely három (különböző) e-t tartalmazó sík metszeteként van adva, akkor e ezek közül bármelyik kettő metszeteként is megadható. Azt is feltehetjük, hogy minden szereplő qx ≤ β egyenlőtlenség valódi, mert különben helyettesíthetjük az yx = β explicit egyenlőséggel. Nevezzük az R (2.32) 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. Az kaptuk tehát, hogy létezik minimális leírás.

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

Biz. Miután qx ≤ β valódi, létezik olyan x′ ∈ R, amelyre qx′ < β. Miután qx ≤ β lényeges, létezik olyan x′′, amely (2.32)-ből a qx ≤ β egyenlőtlenség kivételével mindent kielégít. Az x′x′′ szakasz egyik vége R-ben van, másik nincs, így a szakasznak van olyan z pontja, amely R-ben van és qz = β. •

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

(i) R affin altér. (ii) R-nek nincs valódi oldala. (iii) Q üres (azaz 0 sora van).

Biz. Tegyük fel, hogy R affin altér. Ekkor van {x : Ax = d} alakú leírása. A 2.26 tétel szerint az oldal fogalma nem függ a poliéder leíró rendszerétől. Mivel itt csak egyenlőségek szerepelnek, R-nek nem lehet valódi oldala.

Tegyük most fel, hogy (ii) teljesül. Ha indirekt (iii) nem állna, akkor a (2.32)-ben létezne egy qx ≤ β valódi, lényeges egyenlőtlenség. Ehhez R-nek van olyan x′ pontja, amelyre qx′ < β, és a 2.27 lemma szerint olyan z pontja is, amelyre qz = β. De ekkor {x ∈ R : qx = β valódi (nemüres) oldala lenne R-nek.

A (iii) → (i) irány triviális. •

Miután minimális oldalnak nincsen valódi oldala, az előző tételből kapjuk:

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

Hasznos a következő lemma.

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

Biz. Minden valódi egyenlőtlenséghez van R-nek olyan eleme, amely azt szigorúan teljesíti. Ezen elemek számtani közepe (vagy bármely pozitív együtthatós konvex kombinációja) R-ben van és valamennyi valódi egyenlőtlenséget szigorúan teljesíti. •

TÉTEL 2.31 Tegyük fel, hogy (2.32) 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.32)-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.

Biz. Ha létezik y_{0}, akkor persze R minden x elemére ax = β, azaz R benne van a H hipersíkban. Tegyük most fel, hogy R benne van H-ban, azaz mind az ax ≤ β, mind az ax ≥ β egyenlőlenség logikai következménye a (2.32) rendszernek. Korábban láttuk (2.12 tétel), hogy ha ax ≤ β logikai következmény, akkor létezik olyan y = (y_{0}y, y_{1}), amelyre y_{1} ≥ 0, y_{0}P + y_{1}Q = a, és yb ≤ β. Itt nem állhat szigorú egyenlőtlenség, hiszen akkor ax < β is következne (2.32)-ből, holott ax ≥ β következik. Tehát yb = β.

Belátjuk, hogy y_{1} = 0. Valóban, a 2.30 lemma szerint R-nek van olyan x_{0} eleme, amelyre Qx_{0} ≪ b_{1}. Mivel x_{0} ∈ R ⊆ H, így β = qx_{0} = (y_{0}P + y_{1}Q)x0 = y_{0}(P x_{0}) + y_{1}(P x_{0}) ≤ y_{0}b_{0} + y_{1}b_{1} = yb = β. Szükségképpen az egyenlőtlenség egyenlőséggel teljesül, ami Qx_{0} ≪ b_{1} miatt azt jelenti, hogy y_{1} = 0. •

Feladat 2.15 Igazoljuk, hogy ha egy nemüres poliéder minimális leírásában lévő px = β egyenlőséget helyettesítjük a px ≤ β, −px ≤ −β egyenlőtlenségekkel, akkor ezek lényegesek.

Jelölje Q_{F}^{=} a Q azon sorai által alkotott részmátrixot, amelyeknek megfelelő egyenlőtlenséget az F minden eleme egyenlőséggel teljesíti. Ezeket hívjuk implicit F -egyenlőségeknek.

Lemma 2.32 Tegyük fel, hogy R egy minimális (2.32) 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}^{=}).

Biz. Tegyük fel először, hogy F = F′. Miután F -nek a 2.30 lemma alapján van olyan eleme, amely minden valódi F -egyenlőtlenséget szigorúan teljesít, a Q′x ≤ b′_{1} minden sora implicit F -egyenlőség, azaz Q′ része Q_{F}^{=}-nek. Ha indirekt r(Q′) < r(Q_{F}^{=}), akkor van olyan x′, amelyre Q′x′ = 0, és a Q_{F}^{=} valamely _{i}q sorára _{i}qx′ < 0. Ekkor kicsiny pozitív ε-ra és az F′ valamely z elemére a z + εx′ pont F′-ben van, de szigorúan teljesíti a _{i}qx ≤ b(i) egyenlőtlenséget, ellentmondásban ennek implicit F -egyenlőség voltával.

A fordított irányhoz tegyük fel, hogy Q′ részmátrixa Q_{F}^{=}-nek és r(Q′) = r(Q_{F}^{=}). Mivel Q′x = b′ egyenletei implicit egyenlőségek, ezért F minden eleme kielégíti őket és így F ⊆ F′. A fordított tartalmazás igazolásához legyen x′ ∈ F′. Az r(Q′) = r(Q_{F}^{=}) feltevés miatt Q_{F}^{=}x′ = b_{F}^{=}, amiből speciálisan Q_{F}^{=}x′ = b_{F}^{=} adódik, azaz x′ ∈ F. •

Most már abban a helyzetben vagyunk, hogy pontosan megmondjuk a bázis-megoldások geometriai jelentését.

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

Biz. Tekintsük az R = {x : Qx ≤ b} poliéder egy minimális F oldalát. Miután az előbb láttuk, hogy F affin altér, ezért F = {x : Q_{F}^{=}x = b_{F}^{=}}. Az F minimalitásából következik, hogy F minden x elemére Q_{F}^{<}x ≪ b_{F}^{<}. Tehát F tetszőleges z elemére éppen a Q_{F}^{=}x ≤ b_{F}^{=} rendszer az, amelynek tagjait a z egyenlőséggel teljesíti.

Állítjuk, hogy r(Q) = r(Q_{F}^{=}). Valóban, ha a _{j}q sor lineárisan független volna Q_{F}^{=} soraitól, akkor volna olyan x′, amelyre Q_{F}^{=}x′ = 0, _{j}qx′ = 1. De ekkor egyrészt f + λx′ tetszőleges λ-ra teljesíti a Q_{F}^{=}x = b_{F}^{=} egyenlőséget, azaz benne van F -ben, és így R-ben is, másrészt viszont alkalmas λ-ra f +λx′ nem teljesíti az _{j}qx ≤ b(j) egyenlőtlenséget, azaz még sincs R-ben. Ez az ellentmondás mutatja, hogy r(Q) = r(Q_{F}^{=}), tehát az F minden eleme valóban bázis-megoldás.

Legyen most z bázis-megoldás és tekintsük a Qx ≤ b rendszernek a z által egyenlőséggel teljesített Q_{z}^{=}x ≤ b_{z}^{=} részét. Tekintsük az F_{z} := {x : Qx ≤ b, Q_{z}^{=}x = b_{z}^{=}} oldalát R-nek. Belátjuk, hogy ez minimális oldal. Ha indirekt létezne valódi oldala, akkor az Qx ≤ b rendszerben volna olyan qx ≤ β egyenlőtlenség, amelyre qz < β, de F_{z} valamely x′ elemére qx′ = β. Miután z bázis-megoldás, r(Q) = r(Q_{z}^{=}), és így létezik egy y′, amelyre q = y′Q_{z}^{=}. De akkor 0 = β − β > qx′ − qz = q(x′ − z) = (y′Q_{z}^{=})(x − z) = y′(Q_{z}^{=}x) − y′(Q_{z}^{=}z) = y′b′ − y′b′ = 0, amely ellentmondás mutatja, hogy F_{z}-nek nem lehet valódi oldala. •

2.6 DIMENZIÓ, CSÚCSOK, LAPOK

Egy altér dimenziója a belőle kiválasztható lineárisan független elemek maximális száma. A Z affin altér, definíció szerint, egy altér eltoltja. Az első fejezetben szerepelt, hogy az affin altér előállítható Z = {x : Qx = b} alakban és az altér, amelynek eltolásából Z keletkezett egyértelmű, éspedig {x : Qx = 0} (ami tehát Z karakterisztikus altere). A Z affin altér dimenziója az őt meghatározó altér dimenziója. Például a pont nulla dimenziós, az egyenes egy dimenziós, stb. Affin alterek metszete is affin altér, feltéve, hogy nem üres. Az is rögtön látszik, hogy minden affin altér hipersíkok metszete (egy hipersík valamely qx = β egyenlet megoldás halmaza.)

Az {x : Qx = 0} altér tekinthető a Q sorai által generált altér ortogonális kiegészítő alterének, így ennek dimenziója n − r(Q). Ebből kapjuk, hogy az {x : Qx = b} affin altér dimenziója n − r(Q). Egy tetszőleges R^{n}-beli R nemüres halmaz dimenzióján az R-t tartalmazó legszűkebb affin altér dimenzióját értjük. (A legszűkebb affin altér nem más, mint az R-t tartalmazó affin elterek metszete.)

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

Biz. Nyilvánvaló, hogy R ⊆ Z_{R}. Tegyük fel indirekt, hogy létezik egy Z_{R}-nél szűkebb affin altér, amely tartalmazza R-t. Ekkor van olyan H := {x : qx = β} hipersík, amelyre R ⊆ H, Z_{R} ⊈ H. A 2.31 tétel szerint R ⊆ H azt jelenti, hogy létezik y_{0}, amelyre q = y_{0}P és β = y_{0}b_{0}, amiből következik, hogy bármely olyan x′-re, amelyre Q^{=}x′ = b^{=} teljesül, fennáll qx′ = β, azaz Z_{R} ⊆ H, ellentmondás. •

Következmény 2.35 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^{=}). •

A tételt alkalmazhatjuk a poliéder egy F oldalára.

Következmény 2.36 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 emghatá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. A semleges vektorok nyilván alteret alkotnak, melyet jelöljünk S_{R}-rel.

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

Biz. A 2.35 tétel szerint A_{R} = {x : Q^{=}x = 0}. Mivel Q^{=} sortere {x : Q^{=}x = 0} altér ortogonális kiegészítője, a tétel két állítása egymással ekvivalens.

Ha c = yQ^{=} valamilyen y-ra, azaz c benne van A_{R}-ben, akkor nyilván R minden x elemére cx = (yQ^{=})x = y(Q^{=}x) = yb^{=}. Mivel a jobboldal független x-től, c valóban semleges. Fordítva, ha c nincs benne Q^{=} sorterében, akkor létezik egy olyan x′, amelyre Q^{=}x′ = 0 és cx′ ≠ 0. Az R egy x_{0} elemére és kicsiny λ > 0 számra x_{0} + λx′ benne van R-ben. Mivel cx′ ≠ 0, kapjuk, hogy cx_{0} ≠ c(x_{0} + λx′), azaz c nem semleges. •

Korábban beláttuk, hogy az R = {x : Qx ≤ b} poliédernek akkor van csúcsa, ha Q oszlopai lineárisan függetlenek (azaz r(Q) = n), és a csúcsoknak megadtuk egy jellemzését. Ezt megismételjük és egy újjal egészítjük ki:

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

Biz. Az első két tulajdonság ekvivalenciáját már láttuk a 1.30 tételben. Ha (iii) fennáll, akkor {z} egy egyelemű oldal, ami persze minimális, és így z a 2.33 tétel szerint bázis-megoldás, tehát (ii) következik. Ha most z bázis-megoldás (azaz csúcs), akkor {x : Qx ≤ b, Q_{z}^{=}x = b_{z}^{=}} a poliédernek egy oldala, amelynek egyetlen eleme van, z. A 2.26 tétel szerint van olyan c, amelyre {cx : x ∈ R} maximuma éppen az adott oldal elemein vétetnek fel, tehát az egyértelmű z-n. •

Egy poliéder két csúcsát nevezzük szomszédosnak, ha az összekötő szakaszuk a poliéder oldala. (Három dimenzióban ez annak felel meg, hogy az összekötő szakaszuk a poliédernek éle.)

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

Biz. (i) → (ii) Legyenek u és v szomszédosak, vagyis az összekötő F szakaszuk oldal. Ekkor F előáll F = {x : Qx ≤ b, Q_{F}^{=}x = b_{F} } alakban. Mivel szakasz dimenziója 1, a 2.36 következményből kapjuk, hogy r(Q_{F}^{=}) = n − 1. Mivel u, v benne vannak F -ben, így Q_{uv}^{=} tartalmazza Q_{F}^{=}-t, tehát r(Q_{uv}^{=}) ≥ n − 1. Itt egyenlőségnek kell állnia, mert ha r(Q_{uv}^{=}) = n volna, akkor a Q_{uv}^{=}x = b_{uv} = rendszernek nem lehetne két különböző megoldása (mármint u és v.) (ii) → (iii) Válasszunk ki a Q_{uv}^{=} mátrixnak n − 1 lineárisan független sorát, majd ezt egészítsük ki a Q_{u}^{=} egy sorával egy nemszinguláris Q_{u} mátrixszá, illetve a Q_{v}^{=} egy sorával egy nemszinguláris Q_{v} mátrixszá. A Q_{u}x = b_{u} rendszernek ekkor létezik egyértelmű megoldása és u megoldása, és ugyanígy Q_{v}x = b_{v}-nek v a megoldása. (iii) → (i) Az n − 1 közös sor által alkotott mátrixot jelöljük Q′-vel. Ekkor az F := {x : Qx ≤ b, Q′x = b′} poliéderben u is, v is benne van, tehát F oldala R-nek, melynek dimenziója 1, vagyis F az u-t és v-t összekötő szakasz. •

Fentebb láttuk, hogy az implicit egyenlőségek éppen az R-t tartalmazó legszűkebb affin alteret határozzák meg. Mi a valódi egyenlőtlenségek geometriai tartalma?

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

Biz. Először tegyük fel, hogy F lapja R-nek. Ekkor F = {x ∈ R : Q_{F}^{=}x = b_{F}^{=}}. Mivel F ⊂ R, létezik egy x_{0} ∈ R − F pont. Ez az Q_{F}^{=}x ≤ b_{F}^{=} rendszer egyik qx ≤ β egyenlőtlenségét szigorúan teljesíti: qx_{0} < β. Tehát qx ≤ β a Qx ≤ b rendszernek valódi egyenlőtlensége, így F′ := {x ∈ R : qx = β} valódi oldala R-nek, amely tartalmazza F -t, és miután F tartalmazásra nézve maximális oldal, F = F′ következik. Tehát R lapja előáll a kívánt alakban.

Megfordítva, tegyük fel, hogy qx ≤ β a Qx ≤ b rendszernek valódi egyenlőtlensége. Jelölje Q′x ≤ b′ azt a részét Q^{<}x ≤ b^{<}-nak, amelyet az qx ≤ β kihagyásával kapunk. A feltevés szerint qx ≤ β lényeges, így létezik x_{2} ∈ R, amelyre Q′x_{2} ≤ b′ és qx_{2} > β. Másrészt láttuk már, hogy létezik olyan x_{1} ∈ R, amelyre Q^{<}x_{1} ≪ b^{<}. Az x_{1} és x_{2} alkalmas konvex kombinációját véve kapjuk, hogy létezik olyan x_{0} ∈ R, amelyre Q′x_{0} < b′ és qx_{0} = β. Ebből következik, hogy F := {x ∈ R : qx = β} valódi oldal. Mivel pedig egyetlen olyan eredetileg valódi egyenlőtlenség van, amely implicit F -egyenlőség, F maximális valódi oldal. •

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

Következmény 2.42 Tegyük fel, hogy mind a {P x = b_{0}, Qx ≤ b_{1}} 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 ≤ b_{1} és Q′x ≤ b′_{1} rendszer egyenlőtlenségei között egy-egy értelmű kapcsolat van, amelyben az egymának megfelelő qx ≤ β és q′x ≤ β′ egyenlőtlenségekre fennáll, hogy a (q, β) − (q′, β′) vektor benne van a (P, b_{0}) mátrix sorterében (ami ugyanaz, mint a (P′, b′_{0}) mátrix sortere). •

Feladat 2.16 Egy poliéder minden lapjának dimenziója eggyel kisebb, mint a poliéder dimenziója.

Feladat 2.17 Igazoljuk, hogy ha két rendszer ugyanazt a poliédert definiálja, akkor erős bázis-megoldásaik halmaza ugyanaz.

2.7 A SZIMPLEX ALGORITMUS

2.7.1 MEGENGEDETTSÉG

Ebben a szakaszban megismerkedünk a Farkas lemma illetve a dualitás tétellel kapcsolatos fő algoritmikus eredményekkel. Azt már korábban láttuk, hogy egy lineáris célfüggvény metszet-poliéder feletti optimalizálására van véges algoritmus, hiszen ha cx felülről korlátos, akkor a maximum erős bázis-megoldáson is felvétetik, és ezekből csak véges sok van. Ezzel a megközelítéssel az a baj, hogy erős bázis-megoldásból igen sok lehet (exponenciálisan sok). Például, ha a poliéder, amely felett a cx célfüggvényt akarjuk maximalizálni, egy n-dimenziós egységkocka kocka, azaz {x : 0 ≤ x ≤ 1}, akkor ezt a feladatot mind a 2^{n} csúcs cx szerinti sorbarendezésével már a nem túlságosan nagy n = 100-as méretnél sincs semmilyen esélyünk megoldani, a legjobb számítógépet használva sem, ugyanakkor a problémát ránézésre rögtön meg lehet oldani.

A szimplex algoritmus George Dantzigtól származik. Az a lényege, hogy a poliéder csúcsait szisztematikusan, javuló sorrendben tekinti át. Óriási felhalmozott tapasztalat mutatja, hogy a szimplex algoritmus a gyakorlatban nagyon hatékony, tipikusan lineáris számú csúcs átvizsgálása után megtalálja az optimumot. Annál szomorúbb, hogy konstruáltak olyan példa sorozatot, ahol a szimplex algoritmus végiglátogatja az összes, exponenciálisan sok csúcsot, mielőtt az optimálisat megtalálná. Ez azt jelenti, hogy matematikai szempontból a szimplex algoritmus nem tekinthető hatékonyabbnak, mint a durva, összes csúcsot számba vevő algoritmus. (Kimutatták azonban, hogy ha nem a legrosszabb előforduló esettel akarjuk az algoritmus hatékonyságát mérni, hanem az átlagos lépésszámot tekintjük, akkor a szimplex algoritmus polinomiális futás idejű.)

Kezdjük a Farkas lemmával, annak a 2.5 tételben megfogalmazott erősebb változatával, amely tehát azt mondja ki, hogy az {Ax = b, x ≥ 0} primál és az {yA ≥ 0, yb = −1} duál feladatok közül pontosan az egyiknek van bázis-megoldása:

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

Bizonyítás a szimplex algoritmussal. Már a Farkas lemma bizonyításánál láttuk, hogy a két lehetőség kizárja egymást. Azt látjuk be algoritmikusan, hogy legalább az egyik lehetőség fennáll. A Gausseliminációval először eldöntjük, hogy az Ax = b rendszernek van-e egyáltalán megoldása. Ha nincs, akkor a Gauss-elimináció egy olyan y vektort szolgáltat, amelyre yA = 0 és yb ≠ 0. Itt −1-gyel történő esetleges szorzás után feltehetjük, hogy yb < 0 azaz a (b) alternatívára jutottunk. (Most t = r(A, b) = r(A) + 1).

Tegyük fel tehát, hogy Ax = b megoldható. Feltehetjük, hogy A sorai lineárisan függetlenek, mert ha nem, akkor az A soraiból kiválasztunk r(A) lineárisan lineárisan független sort (ezt valójában a Gauss-elimináció már meg is tette) és csak az ezek által alkotott részmátrixszal dolgozunk tovább. Válasszunk ki az A oszlopaiból egy B_{1} bázist (ami tehát egy m × m-es részmátrix) és tekintsük a B_{1}x = b egyértelmű x_{1} megoldását (ezeket tehát az előbbi Gauss-elimináció meghatározta.) Ha x_{1} nemnegatív, akkor ez a primál feladat bázis-megoldása.

Tegyük fel most, hogy x_{1}-nek van negatív komponense. Az alapalgoritmus itt egy tetszőleges negatív komponenst választ. Példával kimutatható, hogy ilyenkor az algoritmus végtelen ciklusba eshet, ezért ennek elkerülésére indokolt valamilyen megkötést tenni. Jelölje i_{1} a legkisebb indexet, amelyre x_{1}(i_{1}) < 0. (Ez a Bland féle legkisebb index szabály). Legyen y_{1} olyan vektor, amely B minden oszlopára merőleges, kivéve, hogy y_{1}a_{i_{1}} = 1. (Az yB_{1} = d minden m-dimenziós d-re egyértelműen megoldható.) Most q = 1-re

y_{q}b = y_{q}(B_{q}x_{q}) = (y_{q}B_{q})x_{q} = x_{q}(i_{q}) < 0.  (2.33)

Amennyiben minden a_{i}-re y_{1}a_{i} ≥ 0, úgy a duális feladat bázis-megoldását kaptuk.

Tegyük fel tehát, hogy valamely j_{1} indexre y_{1}a_{j_{1}} < 0 és válasszuk j_{1}-t a lehető legkisebbnek. (Ismét a legkisebb index szabályt alkalmazzuk). Természetesen ekkor a_{j_{1}} nincs a B_{1} bázisban, és az is látható, hogy B_{1}-ben a_{i_{1}}-t a_{j_{1}}-re cserélve egy másik bázist kapunk, amit jelöljünk B_{2}-vel. (Valóban, az a_{j_{1}} vektor nem függhet lineárisan a B_{1}-nek a_{i_{1}}-től különböző oszlopaitól, hiszen az y_{1} vektor ezen utóbbiak mindegyikére merőleges, míg a_{j_{1}}-re nem.) Iteráljuk az eljárást most a B_{2} bázissal kezdve, ameddig csak lehet.

Igazolnunk kell, hogy az eljárás véges sok lépésben véget ér. Tegyük indirekt fel, hogy nem ez a helyzet. Mivel csak véges sok bázis-megoldás van, lesznek olyan oszlopvektorok, melyek időről időre ki- majd újra bekerülnek a bázisba. Legyen a_{r} a legnagyobb ilyen indexű. Tehát az r-nél nagyobb indexű oszlopok egy bizonyos időponttól fogva már nem változtatják helyzetüket: vagy egyszer és mindenkorra benn vannak a bázisban, vagy kívül. Legyen egy ezutáni pillanatban B_{p} egy olyan előforduló bázis, amelyben a_{r} benne van, de B_{p+1}-ben nincs. Legyen B_{q} (q > p) egy olyan későbbi bázis, amelyben a_{r} nincs benne, de B_{q+1}-ben benne van. Ekkor tudjuk, hogy y_{q} a B_{q+1} minden oszlopára merőleges, kivéve a_{r}-t, amelyre y_{q}a_{r} < 0. A második választási szabályból az is következik minden a_{r} előtti a_{i} oszlopra, hogy y_{q}a_{i} ≥ 0.

Az első választási szabály miatt x_{p} minden r-nél kisebb indexű komponense nem-negatív. Így tehát az 1 ≤ i < r indexekre (y_{q}a_{i})x_{p}(i) ≥ 0 és (y_{q}a_{r})x_{p}(r) > 0. A B_{q} mátrixnak egyetlen olyan a_{j} oszlopa van, amelyre y_{q} nem merőleges, de mivel éppen ez az oszlop esik ki a B_{q} bázisból, az a_{j} szükségképpen megelőzi a_{r}-t. Tehát y_{q} merőleges a B_{q}-nak a_{r} utáni oszlopaira, de mivel az r-nél nagyobb indexű oszlopokon a B_{q} és a B_{p} bázis megegyezik (itt használva r maximális választását), y_{q} merőleges B_{p} minden r-nél nagyobb indexű oszlopára. Így felhasználva (2.33)-t, kapjuk, hogy 0 > y_{q}b = y_{q}(B_{p}x_{p}) = (y_{q}B_{p})x_{p} ≥ 0, és ez az ellentmondás a tételt és egyúttal az algoritmus végességét is bizonyítja. •

Az algoritmus kissé általánosabb alakban is használható. Például, ha a {P x_{0} + Ax_{1} = b, x_{1} ≥ 0} rendszer megoldhatóságát akarjuk eldönteni, akkor az előző eljárást a következőképpen kell módosítani. A kezdeti B_{1} bázist úgy határozzuk meg, hogy a P maximálisan sok lineárisan független oszlopát egészítjuk ki A oszlopaiból r(P, A) darab lineárisan független oszloppá. Az eljárást úgy módosítjuk, hogy csak az A-beli bázis elemeket cserélhetjük, a kezdeti B_{1} bázis P -ből kiválasztott elemei végig fixen maradnak. Rögtön látható, hogy az így módosított eljárás új bizonyítást ad a 2.2 tételre. A még általánosabb 2.3 alakra is kiterjeszthető az algoritmus, ha a tétel bizonyításában leírt visszavezetést alkalmazzuk. Megállapíthatjuk tehát, hogy a fenti eljárás bármely alakban adott lineáris egyenlőtlenség-rendszer megoldására alkalmas.

Miért hívják a fenti algoritmust szimplex algoritmusnak? Az m-dimenziós térben, ha veszünk úgy m + 1 pontot, hogy ezek egyike sincs benne a többi konvex burkában, akkor az m + 1 pont konvex burka definíció szerint egy szimplex-et alkot. Egy dimenzióban ez egy szakasz, két dimenzióban háromszög, három dimenzióban tetraéder.

Tegyük fel, hogy a síkban adottak a p_{1}, …, p_{n} pontok, és el akarjuk dönteni, hogy ezek konvex burkában benne van-e egy megadott b′ pont. Egyszerűség kedvéért tegyük fel, hogy nincs három pont egy egyenesen. Készítsünk el egy 2 × n-es A′ mátrixot, melynek i-edik oszlopa a p_{i} pont koordinátáit tartalmazza. Legyen A az a mátrix, amely A′-ből keletkezik egy csupa egyesből álló harmadik sor hozzávételével. A b′-t is egészítsük ki egy egyessel egy három dimenziós b vektorrá. Ekkor a feladat azzal ekvivalens, hogy az {Ax = b, x ≥ 0} rendszernek van-e megoldása. Egy bázis-megoldáshoz tatozó három oszlopvektor három olyan p_{i} pontnak felel meg, amelyek egy b′-t tartalmazó háromszöget alkotnak. Egy duális bázis-megoldás egy olyan egyenesnek felel meg (miért?), amely két p_{i} ponton átmegy, és az általa meghatározott egyik zárt félsik tartalmazza az összes p_{i} pontot, de nem tartalmazza b′-t. Mármost a szimplex algoritmus ezen a geometriai nyelven a következőképpen fut. Induljunk ki egy tetszőleges B_{1}-gyel jelölt háromszögből, melynek csúcsai mondjuk p_{1}, p_{2}, p_{3}. Állapítsuk, meg, hogy b′ benne van-e B_{1}-ben. Ha benne van akkor készen vagyunk: b′ benne van a p_{i} pontok konvex burokában. Ha b′ nincs benne a háromszögben, akkor a háromszögnek az egyik e_{1} oldalegyenese, mondjuk p_{2}p_{3}, elválasztja b′-t p_{1}-től. (A háromszögnek egy vagy két ilyen elválasztó oldalegyenese lehet, a b′ elhelyezkedésétől függően: az általános algoritmus ezek egyikét választja, a Bland féle szabály pontosan előírja, hogy melyiket kell választani.) Amennyiben az e′ egyenes által határolt, a b′-t tartalmazó nyílt félsíkban nincsen p_{i} pont, akkor készen vagyunk; megkaptuk az elválasztó egyenest. Ha van, mondjuk a p_{4} pont, akkor p_{1}-t becseréljük p_{4}-re és a keletkező {p_{2}, p_{3}, p_{4}} háromszöggel folytatva iteráljuk az eljárást.

A fenti algoritmus szemléletesesn tehát azt jelenti, hogy a p_{i} pontok által alkotott háromszögek segítségével mintegy letapogatjuk a sík egy darabját, és eközben vagy ráakadunk a b′ pontra vagy megtalálunk egy elválasztó egyenest. Magasabb dimenzióban ez azt jelenti, hogy a p_{i} pontjaiból készített szimplexekkel tapogatjuk a teret, hogy megtaláljuk a b′ pontot. Innen tehát az elnevezés.

A következő példa mutatja, hogy ha a futás során nem alkalmazzuk a Bland féle szabályt, akkor az algoritmus ciklizálhat. Legyen b′ az origó és n = 6. Az origó középpontú egységkörön legyen p_{1}, p_{3}, p_{5} egy egyenlő oldalú háromszög három csúcsa. E pontokat az origóval összekötő szakaszok felező pontjait az origó körül az óramutató járása szerint csöppnyit elforgatva kapjuk rendre a p_{2}, p_{4}, p_{6} pontokat. Ha most B_{i} jelöli a p_{i}, p_{i+1}, p_{i+2} pontok által alkotott háromszöget (modulo 6 tekintve), akkor a szimplex algoritmus egymás után ezen háromszögeket választhatja (ezt ellenőrizzük le!), míg vissza nem ér a kiindulási B_{1}-be.

Feladat 2.18 Hol tér el először az előbbi példában a szimplex algoritmus, ha ugyanazzal a B_{1} háromszöggel kezdünk és alkalmazzuk a Bland féle legkisebb index szabályt?

Feladat 2.19 Tegyük fel, hogy csak a bázisba bekerülő új oszlop kiválasztásánál alkalmazzuk a legkisebb index szabályt, a bázisból kikerülő oszlop meghatározásánál nem. Ciklizálhat-e ilyenkor az algoritmus vagy már ilyenkor is bizonyíthatóan mindig véges lesz?

Feladat 2.20 Tekintsük a Farkas lemma következő alakját: Az yA ≤ c rendszernek pontosan akkor nincs megoldása, ha létezik olyan x ≥ 0, amelyre Ax = 0 és cx < 0. Tegyük fel, hogy A sorai lineárisan függetlenek. Igazoljuk, hogy a következő algoritmus véges. (A bizonyításban vagy a fenti bizonyítás lépéseit imitáljuk, vagy pedig azt mutassuk ki, hogy az alábbi algoritmus nem más, mint a fenti algoritmus adaptációja):

Legyen B_{1} az A egy m × m-es nemszinguláris részmátrixa és legyen y_{1} az yB_{1} = c_{B_{1}} egyértelmű megoldása. Amennyiben y_{1}A ≤ c, akkor készen vagyunk, megtaláltuk a kívánt y-t. Ha y_{1}A ≰ c, úgy legyen a_{j} az A mátrix legkisebb indexű oszlopa, amelyre y_{1}a_{j} < c(j). Tekintsük a B_{j}x = −a_{j} egyértelmű x′_{1} megoldását, és jelölje x_{1} azt a vektort, amely x′_{1}-ből keletkezik az x_{1}(j) helyen 1-gyel, a többin pedig 0-val kiegészítve. Ekkor Ax_{1} = 0 és cx_{1} = c_{B_{1}}x′_{1} + c(j) = (y_{1}B_{1})x′_{1} + c(j) < (y_{1}B_{1})x′_{1} + y_{1}a_{j} = (y_{1}A)x_{1} = 0. Így ha x_{1} ≥ 0, akkor x_{1} teljesíti a Farkas lemma második alternatíváját. Amennyiben x_{1} ≱ 0, úgy legyen i a legkisebb index, amelyre x_{1}(i) < 0, és cseréljük ki a B_{1}-beli a_{i} oszlopot az a_{j} oszlopra. A keletkező B_{2} mátrixszal folytava iteráljuk az eljárást.

Feladat 2.21 Terjesszük ki a fenti algoritmust a Farkas lemma következő változatára. Az {yP = c_{0}, yA ≤ c_{1}} rendszernek pontosan akkor nincs megoldása, ha létezik olyan x = (x_{0}, x_{1}), amelyre (P, A)x = 0, x_{1} ≥ 0 és cx < 0.

2.7.2 OPTIMALIZÁLÁS

Térjünk rá arra, hogy a fenti eljárás hogyan használható a min{cx : Ax = b, x ≥ 0} primál lineáris program és max{by : yA ≤ c} duális lineráris program megoldására. Jelölje R := {x : Ax = b, x ≥ 0) a primál, R^{∗} := {y : yA ≤ c} pedig a duál poliédert. Feltesszük, hogy A sorai lineárisan függetlenek, ami azt jelenti, hogy R^{∗} csúcsos.

A megengedettségre vonatkozó szimplex algoritmussal először megkeresünk R^{∗}-nak egy y_{0} csúcsát (azaz yA ≤ c egy bázis-megoldását). Amennyiben R^{∗} üres, úgy az eljárás egy olyan x′ ≥ 0 vektort szolgáltat, amelyre Ax′ = 0, cx′ < 0, és ilyenkor vagy a primál poliéder is üres, vagy ha van is egy x_{0} pontja, akkor x_{0} + λx′ minden pozitív λ-ra R-ben van, így cx nem korlátos alulról. Ekkor tehát az algoritmus futása befejeződik.

Tegyük fel tehát, hogy rendelkezésünkre áll y_{0}. Jelölje A_{0}^{=} az A-nak azon a_{i} oszlopai által alkotott részmátrixát, amelyekre y_{0}a_{i} = c(i), míg a maradék oszlopok részmátrixa legyen A_{0}^{<}. A fenti eljárással döntsük el, hogy az {A_{0}^{=}x′ = b, x′ ≥ 0} rendszernek létezik-e megoldása. Amennyiben létezik, úgy x′-t nulla komponensekkel kiegészítve R-nek egy olyan x_{0} elemét kapjuk, amely teljesíti az optimalitási feltételeket (azaz, ha valamely i-re x_{0}(i) szigorúan pozitív, akkor y_{0}a_{i} = c(i)). Ekkor x_{0} primál optimum, y_{0} duál optimum és az eljárás véget ér.

Ha a szóbanforgó x′ nem létezik, akkor a fenti eljárás megtalálja A_{0}^{=}-nak egy m − 1 lineárisan független oszlopból álló A′_{0} részmátrixát valamint egy olyan y′ vektort, amelyekre y′A_{0}^{=} ≤ 0, y′A′_{0} = 0 és y′b > 0.

(Figyelem! Az {y′A_{0}^{=} ≤ 0, y′b ≥ 1} rendszer egy bázis-megoldása azt jelenti, hogy y′ az A_{0}^{=} mátrixnak m − 1 lineárisan független oszlopára merőleges. Az yA ≤ c rendszer egy bázis megoldása azt jelenti, hogy A-nak van m lineárisan független a_{i} oszlopa, amelyre ya_{i} = c(i).)

Amennyiben y′A_{0}^{<} ≤ 0, úgy az adódik, hogy y′A ≤ 0, y′b > 0 és így (a Farkas lemma triviális irányát alkalmazva) a primál feladat nem megoldható, vagy ekvivalensen a duál feladat nem korlátos. Ilyenkor az algoritmus véget ér.

Tegyük most fel, hogy y′A_{0}^{<} ≰ 0. Válasszuk λ-t a legnagyobb olyan számnak, amelyre (y_{0}+λy′)A ≤ c teljesül, azaz (y_{0} + λy′)a_{i} ≤ c(i) fennáll az A_{0}^{<} mindegyik a_{i} oszlopára. Vagyis λ a legnagyobb szám, amelyre λy′a_{i} ≤ c(i)−y_{0}a_{i} teljesül az A_{0}^{<} valamennyi olyan a_{i} oszlopára, amelyre a_{i}y′ > 0. Egyszóval legyen λ_{0} := min(c(i) − y_{0}a_{i})/y′a_{i}), ahol a minimum az A_{0}^{<} olyan a_{i} oszlopaira megy, melyekre a_{i}y′ > 0.

Legyen y_{1} := y_{0} + λ_{0}y′. A λ_{0} választásából adódóan y_{1} eleme R^{∗}-nak.

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

Biz. Azt kell látni, hogy A-nak van m lineárisan független oszlopa, melyekre y_{1}a_{i} = c(i). Mindenesetre y′A′_{0} = 0 miatt A′_{0}-nak az m − 1 oszlopa ilyen. Legyen a_{j} egy olyan oszlop, ahol a λ_{0} definíciójában szereplő minimum felvétetik. Ekkor nyilván y_{1}a_{j} = c(j), így csak azt kell látnunk, hogy a_{j} lineárisan független az A′_{0} oszlopaitól. De ez valóban így van, hiszen y′A′_{0} = 0 és y′a_{j} ≠ 0. •

Az y_{1} tehát valóban csúcsa R^{∗}-nak, és ráadásul y_{0}-nál jobb csúcsa, hiszen y′b > 0 miatt y_{1}b > y_{0}b. Miután R^{∗}-nak véges sok csúcsa van, az eljárás véges sok iteráció után befejeződik.

A algoritmusban a Farkas lemmára vonatkozó algoritmust szubrutinként használtuk, aminek belsejében persze alkalmazzuk a Bland féle legkisebb index szabályt. A fenti algoritmusban azonban, amikor az y_{0}-ról áttértünk y_{1}-re, a szóban forgó a_{j} oszlop meghatározásánál nem volt szükség a Bland-szabályra.

OPTIMALIZÁLÁS GRÁFOKON

3.1 TELJESEN UNIMODULÁRIS MÁTRIXOK

Az alábbiakban egy mátrixot vagy egy vektort akkor nevezünk egésznek vagy egészértékűnek, ha minden elemük (komponensük) egész szám. Gyakran előfordul, hogy egy lineáris egyenlőtlenségrendszernek egész megoldására vagy egy lineáris programnak egész optimális megoldására van szükségünk. Bebizonyították, hogy mindkét feladat NP-teljes, így általánosságban olyan típusú megoldást nem várhatunk, mint amilyent a Farkas lemma vagy a dualitás tétel nyújt. Speciális feltételi mátrixok esetén azonban szavatolható egészértékű megoldás vagy optimum létezése.

Valamely A mátrixot akkor nevezünk teljesen unimodulárisnak (TU: totally unimodular), ha minden aldeterminánsa (0, ±1) értékű. Speciálisan, ilyen mátrix minden eleme 0, +1 vagy −1. Világos, hogy TU-mátrix transzponáltja is az. Sorokat vagy oszlopokat −1-gyel szorozva vagy elhagyva ismét TU-mátrixot kapunk. Továbbá, egységvektorokat sorként vagy oszlopként egy TU-mátrixhoz illesztve TU-mátrixot kapunk. Így, ha az A TU-mátrixot kiegészítjük egy I egység-mátrixszal, akkor a keletkező (A, I) mátrix is TU-mátrix. Ha A TU-mátrix, úgy (A, −A) is az. (De ha mondjuk egy csupa 1 oszloppal egészítjük ki A-t, akkor nem feltétlenül kapunk TU-mátrixot: legyen A az {1, 2, 3, 4} pontokon az {12, 13, 14} élekből álló gráf 4 ∗ 3-as incidencia mátrixa.)

Példaképp, legyen A egy D = (V, E) irányított gráf incidencia mátrixa, azaz A sorai a V -nek, oszlopai E-nek felelnek meg, és az a_{v,e} elem akkor +1 illetve −1, ha az e él belép illetve kilép v-ből (egyébként 0).

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

Biz. (a) Vegyünk egy A′ négyzetes részmátrixot, amelyről be akarjuk látni, hogy determinánsa 0, ±1. Amennyiben ennek van olyan oszlopa, amelyben legfeljebb csak egy nem-nulla elem van, akkor ezen oszlop szerint kifejtve a determinánst, indukcióval kész vagyunk. Így feltehetjük, hogy minden oszlopban pontosan két nem-nulla van (merthogy több nem lehet). Ezek közül az egyik +1, a másik −1, vagyis a sorokat összeadva 0-t kapunk, azaz A′ sorai lineárisan függőek, így a determináns 0.

(b) Szorozzuk meg −1-gyel a mátrix azon sorait, amelyek a páros gráf egyik osztályában lévő pontoknak felelnek meg. Ekkor egy irányított gráf incidencia mátrixát kapjuk, amiről az előbb láttuk, hogy TU. •

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. Ez egy olyan 0−1 értékű mátrix, amelyben a soroknak a V elemei felelnek meg, az oszlopoknak az F elemei, és a mátrix egy eleme pontosan akkor egy, ha az oszlopának megfelelő hiperél tartalmazza a mátrix-elem sorának megfelelő V -beli elemet. A gráfok speciális hipergráfok, ahol minden hiperél kételemű. Ezek közül már láttuk, hogy a páros gráfok teljesen unimodulárisak. Más gráfok viszont sohasem azok, hiszen egy páratlan kör incidencia mátrixának determinánsa ±2.

Mint láttuk, minden D digráf ±1-es incidencia mátrixa TU. Ezt általánosítja a hálózati mátrix. 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 nemfa é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.

Biz. Egy oszlop eltörlése annak felel meg, hogy a megfelelő nem-fa élt a digráfból kihagyjuk. Egy sor törlése annak felel meg, hogy a megfelelő fa-élt a digráfban összehúzzuk. Egy sor vagy oszlop −1-gyel való szorzása annak felel meg, hogy a megfelelő élt (akár fa-él, akár nem-fa él) átirányítjuk. •

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

Biz. A lemma alapján elég belátni, hogy egy négyzetes hálózati mátrix determinánsa 0, 1 vagy −1. Tekintsük a fának egy v végpontját. Ha az F fa v-vel szomszédos éléhez tartozó sorban lévő nemnulla elemek α száma legfeljebb 1, akkor a determináns kifejtési szabály alapján indukcióval készen vagyunk. Tegyük fel, hogy α > 1, vagyis v szomszédos legalább két nem-fa éllel. Átirányítás miatt feltehető, hogy ezek közül pontosan egy van v felé irányítva. Legyen ez sv és legyen vt egy másik nem-fa él. Ha az sv-nek megfelelő oszlopot, hozzáadjuk a vt-nek megfelelő oszlophoz, akkor egyrészt persze a determináns értéke nem változik, másrészt ismét hálózati mátrixot kapunk, éspedig azé a gráfét, amelyben a vt él helyett az st él szerepel.

Ilyen átalakításokkal egy olyan gráfot kaphatunk, amelyben az F feszítő fa változatlan, egyetlen nem-fa él (nevezetesen sv) szomszédos v-vel, vagyis a hozzátartozó hálózati mátrix v-nek megfelelő sorában egy nem-nulla elem van. Ilyen hálózati mátrixról pedig már láttuk, hogy a determinánsa 0, ±1, ugyanakkor a fenti operációk nem változatták a determináns abszolút értékét. •

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.

Egy hipergráfot laminárisnak mondunk, ha bármely két hiperéle vagy diszjunkt vagy az egyik tartalmazza a másikat. Például, ha F = (V, E) egy s gyökerű fenyő és minden e = uv éléhez tekintjük a v-ből a fenyőben elérhető pontok halmazát, akkor ezen halmazok lamináris rendszert alkotnak. Valójában nem nehéz bebizonyítani ezen állítás megfordítását is, mely szerint minden lamináris halmazrendszer lényegében ilyen alakban áll elő.

Legyen F_{1} és F_{2} két lamináris hipergráf az S alaphalmazon. Jelölje A_{i} (i = 1, 2) az incidencia mátrixukat, amelyben az oszlopok S elemeinek felelnek meg, míg a sorok F_{i} elemeinek, és legyen

M := ( \begin{matrix}A_{1} \\ A_{2} \end{matrix} ).

TÉTEL 3.5 M teljesen unimoduláris.

Biz. Vegyük M-nek egy négyzetes részmátrixát. Az ebben lévő egyesek száma szerinti indukcióval ennek determinánsáról kimutatjuk, hogy 0 vagy ±1. Mivel A_{i} bármely részmátrixa is egy lamináris rendszer incidencia mátrixa (miért?!), így feltehetjük, hogy a vizsgált részmátrix maga M. Ha Mben minden elem nulla, akkor persze a determináns is nulla. Ha M-nek van olyan sora vagy oszlopa, amelyben legfeljebb egy nem-nulla elem van, akkor indukcióval (és kifejtési szabállyal) készen vagyunk.

Ha F_{1} is és F_{2} is partíció, akkor A_{1} sorösszege is és A_{2} sorösszege is a csupa 1 vektor, tehát A sorai lineárisan függőek, így det(M) = 0. Tegyük, most fel, hogy mondjuk F_{1} nem partíció. Ekkor van egy olyan minimális Z tagja, amely része F_{1} egy másik tagjának. Ha most F_{1}-nek valamennyi Z-tartalmazó tagjából kivonjuk Z-t, ami azzal ekvivalens (a laminaritás miatt), hogy a megfelelő sorokból kivonjuk Z sorát, akkor a determináns értéke nem változik. Viszont a keletkező mátrixban kevesebb egyes szerepel, így indukcióval készen vagyunk. •

Feladat 3.1 Igazoljuk, hogy a 3.5 tételben szereplő M mátrix hálózati mátrix!

Feladat 3.2 Igazoljuk, hogy az alábbi mátrix teljesen unimoduláris, de sem ő, sem a transzponáltja nem az:

( \begin{matrix}1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 \end{matrix} ).

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

Az erős bázis-megoldás fogalma már eddig is hasznos volt (mert csak véges sok volt belőlük, és mert minden, a poliéderen felülről korlátos cx célfüggvény esetén max cx erős bázis-megoldáson felvétetett.) E fogalom most újabb fontos szerephez jut.

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.

Biz. Legyen M = ( \begin{matrix}P \\ Q \end{matrix} ) és tekintsük a

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

rendszert. A Bázis-megoldások című szakaszban megfigyeltük, hogy minden erős bázis-megoldás előáll valamely M′x′ = b′ egyenletrendszer egyértelmű megoldásának nulla komponensekkel való kiegészítéseként, ahol M′ az M egy [(r(M) × (r(M)]-es nem-szinguláris részmátrixa és b′ jelöli a b azon részét, amely az M′ sorainak felel meg. Mármost, ha M TU-mátrix, akkor a nem-szinguláris M′ determinánsa +1 vagy −1. A Cramer szabály szerint, miután b′ egész, az egyértelmű x′ megoldás is az. •

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

Biz. Legyen M = ( \begin{matrix}P \\ Q \end{matrix} ) és tegyük fel, hogy a K kúp a P x = 0, Qx ≤ 0 rendszer megoldás-halmaza.

Mivel x′ pozitív számszorosa is K-ban van, feltehető, hogy x′ maga olyan, hogy minden komponense a [−1, +1] zárt intervallumba esik. Vagyis a

(−1, …, −1) ≤ x ≤ (1, …, 1), P x = 0, Qx ≤ 0  (3.2)

rendszer által meghatározott korlátos poliédernek x′ olyan eleme, amelyre cx′ > 0. Ekkor az 1.19 tétel szerint van olyan x^{∗} erős bázis-megoldása (3.2)-nek, amelyre cx^{∗} ≥ cx′. A 3.6 lemma miatt x^{∗} egészértékű, azaz minden komponense 0, ±1. •

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

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

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

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

Biz. A tétel első fele következik a 3.6 lemmából, és abból korábbi eredményből, hogy ha létezik megoldás, akkor létezik erős bázis-megoldás is. A tétel második fele pedig a 3.7 lemma közvetlen folyománya. •

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

Biz. Miután az optimum erős bázis-megoldáson is felvétetik, a 3.6 lemmából az eredmény következik. •

Az alábbi tételek ugyanígy következnek a 1.36 és 2.8 tételekből a 3.6 és 3.7 lemmák segítségével.

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. •

Alkalmazásként levezetjük Kőnig Dénes tételét:

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.

Biz. Nyilván minden gráfra ν ≤ τ. Az egyenlőség igazolásához azt kell kimutatnunk, hogy páros gráfban létezik olyan párosítás és olyan lefogó pontrendszer, melyek elemszáma megegyezik.

A páros gráf incidencia mátrixát jelölje A, amelyben a soroknak a gráf pontjai, az oszlopoknak a gráf élei felelnek meg. Tekinsük a következő primál-duál lineáris program párt:

max(1x : Ax ≤ 1, x ≥ 0),  (3.4)
min(1y : yA ≥ 1, y ≥ 0).  (3.5)

A 3.9 tétel szerint mindkét programnak az optimuma egészen felvétetik. Jelöljük ezeket rendre x_{0}-lal és y_{0}-lal. (3.4) minden egészértékű megoldása 0 − 1 értékű, és rögtön látszik, hogy (3.5) minden optimális egészértékű megoldása is 0 − 1 értékű. Legyen M azon élek halmaza, melyeken x_{0} az 1 értéket vesz fel, és legyen T azon pontok halmaza, amelyeken y_{0} egyet vesz fel. Az Ax ≤ 1 feltétel azt jelenti, hogy M párosítás a gráfban, míg az yA ≥ 1 feltétel azt jelenti, hogy T az éleket lefogó pontrendszer. A primál és duál optimum értékek egyenlősége pedig azt jelenti, hogy |M| = |T |, ami a célunk volt. •

Természetesen a primál programban az azonosan 1 célfüggvény helyett választhatunk tetszőleges c célfüggvényt. Ekkor a fenti módszer a Kőnig tétel Egerváry Jenőtől származó általánosítását adja:

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. •

További általánosításokat kaphatunk, ha a primál feladatban a jobboldalt valamilyen (nem-negatív) b vektornak választjuk. Ennek az a kombinatorikus jelentése, hogy maximális költségű fokszámkorlátozott részgráfot keresünk. Természetesen alsó korlátokat is kitűzhetünk a fokszámokra, mint ahogy korlátozhatjuk alulról és felülről azt, hogy egy élt hány példányban vehetünk be a keresett részgráfba. Valójában nem is érdemes megfogalmazni a különböző lehetőségekre vonatkozó min-max tételeket, mert a dualitás tétel és a páros gráf incidencia mátrixának teljes unimodularitása már magában hordozza a szükséges információt.

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. (Tehát az 1, 01-nek az 11 és a 2 is kerekítése.) Ez speciálisan azt jelenti, hogy ha x egész, akkor x = z. 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. Egész x-re ⌊x⌋ := ⌈x⌉ := x. Amennyiben x egy vektort jelöl, úgy ⌊x⌋ azt a vektort jelöli, amelyet x-ből nyerünk a komponenseinek alsó egész részét véve. Az x vektor ⌈x⌉ felső egész részét analóg módon definiáljuk.

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.

Biz. A feltevés szerint az ⌊x_{0}⌋ ≤ z ≤ ⌈x_{0}⌉ és ⌊Ax_{0}⌋ ≤ Az ≤ ⌈Ax_{0}⌉ rendszernek van megoldása, így a 3.8 tétel szerint van egész megoldása is. •

Érdemes megfogalmazni az alábbi következményt: Ha (S, F) teljesen unimoduláris hipergráf, úgy bármely x_{0} : S → R függvénynek létezik olyan q kerekítése, hogy minden A ∈ F hiperélre a (∑ q(v) : v ∈ A) szám kerekítése (∑ x_{0}(v) : v ∈ A)-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).

Biz. Legyen S a B mátrix mezőinek halmaza. B minden sorához legyen a sorban lévő mezők halmaza tagja F_{1}-nek valamint minden i-re (2 ≤ i ≤ m) az első i sor mezőinek halmaza legyen tagja F_{1}-nek (összesen tehát 2m − 1 tagja van F_{1}-ben). F_{2} analóg módon van definiálva az oszlopok segítségével. Ekkor F_{i} lamináris, így a 3.5 tétel és a 3.14 lemma alapján készen vagyunk. •

A teljesen unimoduláris mátrixok egy másik érdekes alkalmazása hipergráfok egyenletes színezésével foglalkozik.

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.

Biz. k szerinti indukció alapján elég egy olyan egész z_{1} egész vektort találni, amelyre Az_{1} ≤ b és A(z − z_{1}) ≤ (k − 1)b. Ugyanis ilyen z_{1} létezése esetén z′ := z − z_{1} olyan, amelyre Az′ ≤ (k − 1)b és az indukciós feltevés alkalmazható (k − 1)-re.

A fenti z_{1} létezéséhez csak azt kell látni, hogy az Az − (k − 1)b ≤ Ax ≤ b poliédernek van egész pontja. A poliéder mindenesetre nemüres, hiszen z/k benne van. Továbbá a feltételek egy TUmátrixszal adhatók meg, így létezik a kívánt egész pont is. •

A fenti tétel kiterjeszthető arra az esetre, amikor z nemnegativitását is megköveteljük, és az Ax-re nemcsak felső korlát van, hanem alsó is. Valóban, ha A TU-mátrix, akkor az (A, −A, I) mátrix is teljesen unimoduláris. Kapjuk a következőt.

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}.

Ezt felhasználhatjuk TU-mátrixok oszlopainak egyenletes k-színezésére. 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.

Biz. Legyen d az A oszlopainak az összege. Legyen b_{1} := ⌊d/k⌋ , b_{2} := ⌈d/k⌉ . Ekkor a z :≡ 1 benne van a {kb_{1} ≤ Ax ≤ kb_{2}, x ≥ 0} poliéderben. Az előbbi következmény szerint z felbomlik z_{1}, z_{2}, …, z_{k} egész vektorok összegére, melyekre z_{i} ≥ 0, és b_{1} ≤ Az_{i} ≤ b_{2}. Világos, hogy a z_{i}-k 0 − 1 vektorok. Legyen A_{i} az oszlopoknak azon halmaza, melyeknek megfelelő komponense z_{i}-nek 1. Ezek éppen a kívánt egyenletes színezést adják. •

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 kt 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. •

Ha a hálózati mátrix transzponáltjára alkalmazzuk a színezési tételt, akkor a következőt kapjuk.

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ő. •

Feladat 3.3 Egy egyszerű mohó algoritmus megadásával közvetlenül bizonyítsuk be a 3.21 következményt.

3.4 ÁRAMOK ÉS FOLYAMOK

A teljesen unimoduláris mátrixok szép tulajdonságainak legfontosabb felhasználási területe a hálózati folyamok (network flows) elmélete. Ez olyan lineáris programozási feladatok megoldásával és alkalmazásaival foglalkozik, amelyekben a feltételi mátrix egy irányított gráf incidencia mátrixa avagy annak transzponáltja. Mostani célunk azt megmutatni, hogy az alapvető megengedettségi és optimalitási tételek, hogyan következnek a TU-mátrixok tulajdonságaiból. Egy R poliédert egésznek nevezünk, ha minden c célfügvényre, amelyre cx felülről korlátos R-en a max(cx : x ∈ R) egész vektoron (is) felvétetik.

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. (Figyelem: az f-ben megengedünk −∞ komponenst, ami persze csak annyit jelent, hogy az illető élen az áram értéke nincs alulról korlátozva. Ez azt is jelenti, hogy csak az olyan e élen rendelünk majd az f(e) ≤ x(e) egyenlőtlenséghez duál változót, amelyen az f(e) korlát véges. Analóg módon a g-nek lehetnek +∞ komponensei, de az x áram komponensei mindig valósak. Az f alsó korlátban +∞-t, a g felső korlátban pedig −∞-t nem engedünk meg. Néha előírjuk, hogy az f vagy a g komponensei egészértékűek legyenek; ebbe beleértjük a ±∞-t is.)

Gyakorlat 3.4 (a) Igazoljuk, hogy x akkor és csak akkor áram, ha ϱ_{x}(v) ≤ δ_{x}(v) fennáll minden v csúcsra. (b) Ha x áram, akkor ϱ_{x}(Z) = δ_{x}(Z) minden Z ⊆ V részhalmazra is fennáll.

Az x áramot megengedettnek (feasible) mondjuk, ha

f ≤ x ≤ g.  (3.6)

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

Biz. Miután irányított gráf incidencia mátrixa teljesen unimoduláris, a 3.9 tételből az állítás következik. •

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

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

Biz. A szükségesség igazolásához, tegyük fel, hogy x megengedett áram. Ekkor δ_{g}(X) − ϱ_{f}(X) ≥ δ_{x}(X) − ϱ_{x}(X) = 0, amiből (3.7) következik.

Az elegendőséghez tekintsük az Ax ≤ 0, x ≤ g, −x ≤ −f rendszert. Figyeljük meg, hogy a jelen esetben egy x vektorra akkor és csak akkor teljesül az Ax ≤ 0 egyenlőtlenség, ha Ax = 0. (Ezt kellett bizonyítani a 3.4 gyakorlat (a) részében.) A 3.8 tételt alkalmazva kapjuk, hogy ha a fenti rendszernek nincs megoldása, akkor van olyan (y, u, v) (0, 1)-értékű vektor amelyre (∗) yA+u−v = 0 és (∗∗) ug − vf < 0. Mivel f ≤ g, így minden élre feltehető, hogy u(e) és v(e) közül legalább az egyik nulla (ha ugyanis mindkettő 1, akkor mindkettőt helyettesíthetjük nullával.)

Jelölje Z azon z pontok halmazát, ahol az y(z) = 1. Ekkor (∗) miatt minden olyan e élre, amelynek mindkét vége vagy Z-ben vagy V − Z-ben van, u(e) = v(e) = 0. Továbbá minden Z-be belépő e élre v(e) = 1, u(e) = 0 és minden z-ből kilépő élre v(e) = 0, u(e) = 1. Miután ug = δ_{g}(Z) és vf = ϱ_{f}(Z), így (∗∗) ellentmond a (3.7) feltételnek. •

Az általános elméletből szépen kiadódott Hoffman tétele. Természetes azonban az igény, hogy egy rövid, direkt bizonyítás is rendelkezésünkre álljon. Íme:

Direkt bizonyítás (a (3.7) feltétel elegendőségére). Tekintsük a következő függvényt. γ(X) := δ_{g}(X) − ϱ_{f}(X). Most (3.7) azzal ekvivalens, hogy γ nem-negatív. Az X, Y ⊆ V halmazokra jelölje d_{x}(X, Y) az x(e) értékek összegét mindazon e élekre, melyek X − Y és Y − X egy-egy pontját kötik össze (mindegy melyik irányban). A bizonyítás kulcsa a következő lemma.

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

Biz. Könnyen ellenőrizhetjük, hogy minden lehetséges él hozzájárulása a két oldalhoz ugyanannyi. •

A Hoffman tétel bizonyításához visszatérve nevezzünk egy olyan e élt pontosnak, amelyre f(e) = g(e). Nevezzünk pontosnak csúcsok egy Z részhalmazát, amelyre γ(Z) = 0. Tegyük fel indirekt, hogy a D digráfra nem igaz a tétel, és válasszunk egy olyan ellenpéldát (adott D), amelyben a pontos élek és a pontos halmazok együttes száma maximális. Az nem lehet, hogy minden él pontos, mert akkor x := f(= g), a (3.7) miatt, megengedett áram volna. Legyen a = st olyan él, amelyre f(a) < g(a).

Állítjuk, hogy a belép egy pontos T halmazba. Valóban, ha nem lépne be, akkor f(a)-t meg tudnánk úgy növelni, hogy a módosított f′ alsó korlátra továbbra is fennállna f′ ≤ g és ϱ_{f′}(Z) ≤ δ_{g}(Z) minden Z ⊆ V -re, továbbá vagy az a él válna pontossá, vagy pedig egy olyan halmaz, amelybe az a él belép. Ez a lehetőség azonban ellentmondana a pontos élek és halmazok maximális együttes számára tett feltevésünknek. Tehát az a él valóban belép egy T pontos halmazba. Analóg módon látható, hogy a kilép egy S pontos halmazból.

Az a él létezése folytán tudjuk, hogy a d_{g−f}(S, T) érték szigorúan pozitív. A lemmát és (3.7)-t alkalmazva kapjuk, hogy 0 + 0 = γ(S) + γ(T) > γ(S ∩ T) + γ(S ∪ T) ≥ 0 + 0, amely ellentmondás mutatja, hogy nem létezhet ellenpélda, és így a tétel következik. Ugyanez a gondolatmenet azt is mutatja, hogy ha f és g egészértékű, akkor van egészértékű megengedett áram is. • •

Miután egy TU-mátrix transzponáltja is TU, érvényes a Hoffman tétel alábbi ellenpárja.

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

A tétel következik az alább megfogalmazott speciális alakjából, amikor csak felső korlátok vannak adva a π(v) − π(u) különbségekre. Valóban,, az e = uv élre adott f(uv) ≤ π(u) − π(v) alsó korlát ekvivalens egy újonnan behúzott vu élre vonatkozó π(u) − π(v) ≤ −f(vu) felső korláttal.

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.

Biz. Legyen A a digráf incidencia mátrixa. A 3.8 tétel miatt vagy létezik a πA ≤ c rendszernek megoldása (amely egész, ha c az) vagy létezik a duális Ax = 0, x ≥ 0, cx < 0 rendszernek egy (0, ±1)- es megoldása. Az első eset épp egy megengedett potenciál létezését jelenti, míg a második esetben, x ≥ 0 miatt, x egy (0, 1) értékű, negatív költségű áram, amely élidegen körökre bomlik és így e körök egyike is negatív. •

Tekintsük most a költséges áram problémát, azaz adott c : E → R költségfüggvény esetén keressünk minimális költségű megengedett áramot, más szóval oldjuk meg a

min(cx : Ax = 0, f ≤ x ≤ g)  (3.8)

lineáris programot. (Természetesen az x ≤ g egyenlőtlenség itt azt jelenti, hogy x(e) ≤ g(e) az olyan élekre, ahol g(e) véges. Duális változó tehát csak ilyen egyenlőtlenségekhez tartozik.)

Először vizsgáljuk meg, hogy cx mikor korlátos alulról. Készítsünk el egy D′ = (V, E′) digráfot, és élein definiáljuk a c′ költségfüggvényt a következőképpen. D′-ben uv akkor él, ha vagy vu ∈ E, f(vu) = −∞, és ekkor c′(uv) = −c(vu), vagy pedig uv ∈ E, g(uv) = ∞, és ekkor c′(uv) = c(uv).

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ételből

Tekintsük a megengedett áramok P := {x : Ax ≤ 0, f ≤ x ≤ g} poliéderét és alkalmazzuk a 3.10 tételt. Eszerint {cx : x ∈ P } akkor és csak akkor korlátos alulról, ha nem létezik olyan (0, ±1) értékű x áram, amelyre cx < 0, x(e) ≤ 0, ha g(e) véges, és x(e) ≥ 0, ha f(e) véges. Ilyen x létezése pedig épp a D′-beli negatív kör létezésével ekvivalens. •

Tegyük most fel, hogy x megengedett áram. Készítsünk el egy D_{x} = (V, E_{x}) digráfot és az élhalmazán egy c_{x} költségfüggvényt a következőképpen. Az uv él akkor tartozzék E_{x}-hez, ha vagy uv ∈ E, x(uv) < g(uv), és ekkor legyen c_{x}(uv) := c(uv), vagy pedig vu ∈ E, x(vu) > f(vu), és ekkor legyen c_{x}(uv) := −c(vu). A 3.11 tételt specializálva kapjuk a következőt.

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

(a) x optimális megoldása (3.8)-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). •

Feladat 3.5 Fogalmazzuk meg és bizonyítsuk be a 3.27 és a 3.28 tételek megengedett potenciálokra vonatkozó ellenpárját.

Feladat 3.6 Fogalmazzuk meg a 3.25 tétel általánosítását, ha minden v pontban a π(v)-re alsó és felső korlát is ki van tűzve.

Fontos megjegyezni, hogy a hálózati mátrixokkal megadott lineáris programok megoldhatók áram problémaként. Legyen D = (V, E) irányított gráf, F feszítő fa és legyen N := E − F a nem-fa élek halmaza. Legyen adott f = (f_{F} , f_{N}) és g = (g_{F} , g_{N}) korlát, melyekre f ≤ g. Legyen továbbá c = (c_{F} , c_{N}) egy olyan vektor, amelyre c_{F} = 0. Jelölje az F -hez tartozó (0, ±1)-es hálózati mátrixot A, míg a D digráf (0, ±1)-es pont-él incidencia mátrixát B. Legyen továbbá x = (x_{F} , x_{N}). Tekintsük a max(c_{N}x_{N} : f_{F} ≤ Ax_{N} ≤ g_{F} , f_{N} ≤ x_{N} ≤ g_{N}) lineáris programot. Belátjuk, hogy ez ekvivalens a max(cx : Bx = 0, f ≤ x ≤ g) maximális költségű áram feladattal.

Amennyiben x = (x_{F} , x_{N}) áram (azaz Bx = 0), úgy könnyen látszik, hogy x_{F} = Ax_{N}, és persze cx = c_{N}x_{N}. Emiatt f ≤ x ≤ g ekvivalens a f_{F} ≤ Ax_{N} ≤ g_{F} , f_{N} ≤ x_{N} ≤ g_{N} feltételekkel. Fordítva, tegyük fel, hogy x_{N} kielégíti ezen utóbbi egyenlőtlenségeket. Minden e ∈ N nem-fa élhez legyen χ_{e} az (1, a_{e}) vektor, ahol a_{e} az A mátrix e-hez tartozó oszlopa. (Másszóval χ_{e} az e élhez tartozó C_{e} alapkör 0, ±1-es incidencia vektora.) Ekkor persze χ_{e} áram, és így az x := ∑(x_{N}(e)χ_{e} : e ∈ N) is áram, méghozzá olyan, hogy x(e) = x_{N}(e), ha e ∈ N. Látható, hogy f_{F} ≤ Ax ≤ g_{F} azzal ekvivalens, hogy f_{F} (e) ≤ z(e) ≤ g_{F} (e) minden e ∈ F élre fennáll. •

Gyakran az áramnál általánosabb fogalmat tekintenek. Például az x vektorra azt írjuk elő, hogy minden v pontra ϱ_{x}(v) − δ_{x}(v) = b(v), ahol b : V → R előre adott vektor. Vagy még általánosabban, adott p : V → R ∪ {−∞}, b : V → R ∪ {∞} esetén (p ≤ b) minden v csúcsra legyen

p(v) ≤ ϱ_{x}(v) − δ_{x}(v) ≤ b(v).  (3.9)

Egy egyszerű fogással azonban ez a feladat áram problémává alakítható. Nevezetesen, vegyünk fel egy új s csúcsot, és D valamennyi pontjából vezessünk egy-egy élt s-be. Egy új vs élen legyen f(vs) := p(v), g(vs) := b(v). Jelölje a kibővített élek halmazát E′. Tetszőleges x : E → R vektorhoz legyen x′ : E′ → R a következőképpen definiálva: x′(e) := x(e) ha e ∈ E, és x′(e) := ϱ_{x}(v) − δ_{x}(v) ha e′ = vs (v ∈ V). Hasonlóképp terjesszük ki f-t és g-t az új élekre: f(us) := p(u), g(us) := b(u). Könnyen látszik, hogy x akkor és csak akkor teljesíti (3.6)-t és (3.7)-t, ha x′ megengedett áram.

Feladat 3.7 Hoffman tételének általánosításaként igazoljuk, hogy akkor és csak akkor létezik a (3.6)-t és (3.9)-t kielégítő x vektor, ha ϱ_{f}(X) − δ_{g}(X) ≤ min(p(X), b(V − X)) fennáll minden X ⊆ V -re.

Legyen adott egy s forráspont és egy t nyelőpont úgy, hogy s-be nem lép be él és t-ből nem lép ki él. Ha az előbbi általánosított áram fogalmat arra az esetre specializáljuk, amikor p(v) = b(v) = 0 ha v ∈ V − {s, t}, f ≡ 0, p(s) = 0, akkor st-folyamról, vagy röviden folyamról beszélünk. Másszóval, folyamon egy olyan nemnegatív x : E → R_{+} vektort értünk, amely minden, s-től és t-től különböző pontra teljesíti a megmaradási szabályt. Amennyiben még az x ≤ g feltétel is teljesül, megengedett folyamról beszélünk. Egy s-t tartalmazó, de t-t nem tartalmazó X halmazt nevezzünk st̄-halmaznak.

Tetszőleges S st̄-halmaz és x folyam esetén δϱ_{x}(S) − ϱ_{x}(S) = ∑(δ_{x}(v) − ϱ_{x}(v) : v ∈ S) = δ_{x}(s) − ϱ_{x}(s) = δ_{x}(s). Vagyis minden S st̄-halmazra a δ_{x}(S) − ϱ_{x}(S) értékkel definiált tiszta kiáramlás független S választásától. Ezt a közös, δ_{x}(s)-sel egyenlő értéket nevezzük az x folyam nagyságának. Az x(uv) szám a folyam értéke az uv ∈ A élen. Az x folyamot út-folyamnak (kör-folyamnak) nevezzük, ha x csak egy s-ből t-be vezető út (irányított kör) mentén pozitív.

Gyakorlat 3.8 Igazoljuk, hogy minden nem-negatív folyam kör- és út-folyamok nem-negatív kombinációja.

Alapvető az alábbi, L.R. Fordtól és D.R. Fulkersontól származó Maximális-Folyam Minimális-Vágás tétel (Max Flow Min Cut; MFMC).

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.

A tételt néha az alábbi ekvivalens alakban említik.

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.

Biz. Legyen x megengedett st-folyam és S st̄-halmaz. Ekkor δ_{x}(s) = δ_{x}(S) − ϱ_{x}(S) ≤ δ_{g}(S), amiből max ≤ min következik.

A fordított irány igazolásához jelölje m_{g} a szóbanforgó minimum értékét. (Ez a minimum nyilvánvalóan létezik, merthogy véges sok szám minimumáról van szó. Az viszont még ezen a ponton nem világos, hogy létezik maximális nagyságú folyam.) Adjunk D-hez egy új e = ts élt és definiáljuk f(e) = m_{g}, g(e) := {∞}. Az eredeti éleken legyen f mindenhol nulla.

Könnyen látszik, hogy most (3.7) fennáll, és így a 3.23 tétel szerint létezik megengedett áram (amely ráadásul egészértékű, ha g az). Kihagyva a hozzávett e élt, m_{g} nagyságú folyamot kapunk. •

A fenti bizonyítás előnye, hogy nem csupán egész vagy racionális kapacitásokra működik. Hátránya viszont, hogy nem konstruktív.

Feladat 3.9 Az MFMC tételből vezessük le Menger tételének irányított élidegen változatát. (Azaz egy irányított gráfban akkor és csak akkor van egy s pontból egy t pontba k élidegen út, ha minden st̄-halmazból lép ki legalább k él.)

Nemcsak a maximális folyam feladat vezethető vissza megengedett áramokra, hanem megfordítva, a Hoffman tétel is levezethető az MFMC tételből. Ennek érdekében minden v ∈ V csúcsra legyen λ(v) := ϱ_{f}(v) − δ_{f}(v). (Az itt következő levezetésben feltesszük, hogy f, g véges értékű: kis gyakorló feladat az általános eset kezelése.) Ha λ mindenhol nulla, akkor f megengedett áram, és készen vagyunk.

Ha λ nem azonosan nulla, akkor az S = (v : λ(v) > 0) és T = (v : λ(v) < 0) halmazok nem-üresek. Készítsük el a D′ = (V′, A′) digráfot úgy, hogy V′ = V ∪{s, t} és A′ = A∪(s, v) : v ∈ S∪((v, t) : v ∈ T). Definiáljuk a g′ kapacitás függvényt a következőképpen. g′(sv) := λ(v) ha v ∈ S, g′(vt) := −λ(v) ha v ∈ T, és g′(a) := g(a) − f(a) ha a ∈ A. Legyen M = ∑(λ(v) : v ∈ S). A következő lemma a kapcsolatot írja le egyrészt D megengedett áramai és D′ megengedett st folyamai között, másrészt D′ M-nél kisebb vágásai és D (5.1)-et megsértő halmazai között.

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.7) feltételt.

Biz. (a) A megengedettség, azaz f ≤ f +x ≤ g, következik a konstrukcióból. A megmaradási szabály nyilván fennáll V −(S ∪T) pontjaiban. Mivel x nagysága M, minden s-ből kilépő él telített. Így S-nek bármely v pontjára az eredeti gráfban érvényes, hogy x(sv)+ϱ_{x}(v) = δ_{x}(v), azaz ϱ_{f}(v)−δ_{f}(v)+ϱ_{x}(v) = δ_{x}(v), és így ϱ_{f+x}(v) = δ_{f+x}(v), vagyis a megmaradási szabály érvényes S pontjaiban is. A bizonyítás T pontjaira analóg módon végezhető el.

(b) λ(S) = M > δ_{g′}(X +s) = δ_{g−f}(X)+λ(S −X)−λ(T ∩X), amibe λ(S −X) = λ(S)−λ(S ∩X)-t helyettesítve kapjuk, hogy 0 > δ_{g−f}(X) − λ(S ∩ X) − λ(T ∩ X) = δ_{g−f}(X) − λ(X) = δ_{g−f}(X) + δ_{f}(X) − ϱ_{f}(X), vagyis δ_{g}(X) < ϱ_{f}(X). •

Feladat 3.10 Vezessük le Hoffman tételét az MFMC tételből, ha f-nek lehetnek {−∞}, g-nek pedig {+∞} komponensei.

A fenti redukció azt is mutatja, hogy egy maximális folyam illetve minimális vágás meghatározására szolgáló algoritmus segítségével el lehet dönteni, hogy teljesül-e (3.7), és ha igen, akkor tudunk találni megengedett áramot.

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

Adott a D = (V, E) n pontú, m élű irányított gráf élein egy c : E → R költség- (vagy másnéven súly-) függvény. 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. Rövidség kedvéért egy s-ből v-be vezető utat sv-útnak fogunk hívni.

Fő célunk minimális össz-költségű, másnéven legolcsóbb sv-utat találni. Ha a költség negatív is lehet, akkor a feladat már az azonosan −1 súlyozás esetén is NP-teljes, ugyanis ekkor a legrövidebb út feladat magában foglalja a Hamilton út problémának az előírt végpontú változatát, ami a tetszőleges végpontú Hamilton út problémához hasonlóan NP-teljes.

3.5.1 NEMNEGATÍV KÖLTSÉGEK: DIJKSTRA ALGORITMUSA

Tegyük fel először, hogy a c súlyozás 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.

Biz. Nyilván csak az s-ből v_{a}-ba vezető T′ beli P′ útról kell belátnunk, hogy D-ben legolcsóbb. Legyen P tetszőleges sv út D-ben, és jelölje ennek (s felől indulva) első V (T)-ből kilépő e = u_{e}v_{e} élét. P -nek az s-től u_{e}-ig tartó P′′ részútjára érvényes, hogy c(P′′) ≤ c(P), hiszen c nemnegatív. Az a minimális választása miatt, c(P′) ≤ c(P′′) és a lemma következik. •

A 3.32 lemmán alapuló Dijkstra módszer n − 1 fázisból áll. s-ből kiindulva, élek egyenkénti hozzávételével felépítünk legolcsóbb utaknak egy T s-fenyőjét. Ennek érdekében fenntartunk egy k_{T} címkét, amely azt mondja meg, hogy az aktuális T -hez tartozó m_{T} érték mely v ∈ V − V (T) pontban vétetik fel. Minden fenyőn kívüli v ∈ V −V (T) pontra fenntartunk egy l(v) := min(w_{n}(u)+c(uv) : uv kilép T -ből) címkét. Ezen kívül fenntartunk még egy a(v) címkét is, amely azt mondja meg, hogy az l(v)-t meghatározó minimum mely uv élen vétetik fel. Az l(v) szemléletesen azt jelenti, hogy mekkora az s-ből v-be vezető, csak V (T) pontjait használó utak költségének minimuma. Evvel a jelöléssel tehát k_{T} az l(v) minimum helye.

Ezen címkék segítségével meg tudjuk mondani, hogy melyik a élt kell a soron következő lépésben T -hez venni. Nevezetesen, vesszük a k_{T} -ban lévő a_{v} pontot és az a(a_{v})-ben lévő a = a_{u}a_{v} élt vesszük az aktuális T fenyőhöz.

Egyszerű módosításokkal kapjuk meg a keletkező T′ fenyőhöz tartozó címkéket. Az l(v) értékeket a következő szabály szerint módosítjuk. l(v) := min(l(v), l(v_{a}) + c(v_{a}v)). Amennyiben a minimum a második tagon éretik el, az a(v) címke tartalmát v_{a}v-re cseréljük. Ebben az esetben még azt is megnézzük, hogy a csökkentett l(v) nem kisebb-e m_{T} -nél, és ha igen, akkor k_{T} tartalmát az aktuális v pontra cseréljük, m_{T} -t pedig l(v)-re.

Így az összes módosítás kiszámítása O(n) lépést igényel, és a teljes algoritmus bonyolultsága O(n^{2}). •

3.5.2 KONZERVATÍV KÖLTSÉGEK

A legolcsóbb út problémája tehát viszonylag egyszerűen megoldható, ha a költségek nemnegatívok, de létezik egy még mindig jól kezelhető általánosabb eset is, amikor negatív élek ugyan előfordulhatnak, de nincsen olyan irányított kör, amelynek össz-költsége negatív (röviden: negatív kör). Az ilyen súlyozást konzervatívnak nevezzük. Egy nemnegatív költség-függvény például nyilvánvalóan konzervatív, éppúgy mint egy aciklikus digráf tetszőleges költség-függvénye.

Hogyan lehet hatékonyan eldönteni, hogy egy adott súlyozás konzervatív-e, és ha igen, miként határozzunk meg egy legolcsóbb utat?

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.10)

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

1. Biz. Ha létezik megengedett potenciál, akkor bármely C irányított körre fennáll, hogy c(C) = ∑_{i=1}^{k} c(v_{i}v_{i+1}) ≥ ∑(π(v_{i+1}) − π(v_{i})) = 0, ami azt jelenti, hogy c konzervatív. (Itt v_{1}, …, v_{k} a kör pontjait jelöli, és a v_{k+1} = v_{1} jelölési konvencióval éltünk.)

Megfordítva, tegyük fel, hogy c konzervatív. Be akarjuk látni, hogy létezik megengedett potenciál. Jelölje π_{j}(v) a v-ben végződő legfeljebb j élű séták költségének a minimumát. A definícióból adódik, hogy tetszőleges uv élre

π_{j}(v) ≤ π_{j−1}(u) + c(uv)  (3.11)

Állítjuk, hogy ha c konzervatív, akkor π_{n}(v) = π_{n−1}(v) minden csúcsra (ahol n a pontszám). Ez nyilván igaz, ha egy legolcsóbb legfeljebb n élű séta legfeljebb n − 1 élű. Ha viszont pontosan n élű, akkor biztosan tartalmaz egy C kört, amit kihagyva egy legfeljebb n − 1 élű sétát kapunk, melynek költsége c(C) ≥ 0-val kisebb, mint π_{n}(v). Persze kisebb nem lehet, így c(C) szükségképpen 0, azaz van egy π_{n}(v) költségű legfeljebb n − 1 élű séta, és így valóban π_{n}(v) = π_{n−1}(v).

(3.11)-t használva kapjuk, hogy π_{n}(v) ≤ π_{n−1}(u) + c(uv) = π_{n}(v) + c(uv), azaz π_{n} megengedett potenciál, amely ráadásul egészértékű, amennyiben c az volt. •

2. Biz. Jelölje A az irányított gráf incidencia mátrixát. π pontosan akkor megengedett potenciál, ha πA ≤ c. A TU márixokra vonatkozó Farkas lemma szerint, ennek akkor és csak akkor nincs egész megoldása, ha létezik olyan 0 − 1 értékű x vektor, amelyre Ax = 0 és cx < 0. Legyen F := {e : s(e) = 1}. Az Ax = 0 feltétel azzal ekvivalens, hogy ϱ_{F} (v) = δ_{F} (v) minden v ∈ V. Ezért F felbontható élidegen irányított körök egyesítésére, melyek közül az egyik c(F) < 0 miatt szükségképpen negatív. •

A π_{n}(v) értékeket igen könnyű kiszámítani, az alábbi rekurzió segítségével. Legyen π_{0}(v) ≡ 0 és π_{i+1}(v) = min[π_{i}(v), min(π_{i}(u) + c(uv) : uv ∈ E)]. Ha most a π_{n}(v) megengedett potenciál immár rendelkezésünkre áll, akkor alkalmazhatjuk Dijkstra algoritmusát minimális költségű P út megkeresésére a c̄(uv) := c(uv) − π_{n}(v) + π_{n}(u) (nemnegatív!) költség-függvényre nézve. Ekkor P automatikusan minimális c-költségű út lesz, hiszen bármely s-ből t-be vezető út c-költségének és c̄-költségének az eltérése ugyanaz az úttól független π_{n}(t) − π_{n}(s) szám.

Feladat 3.11 Adjunk a 3.33 tételre még egy bizonyítást, amely pontszám szerinti indukciót használ az alábbi vázlat alapján. Válasszunk ki egy tetszőleges z pontot, minden uz és zv élpárra vegyünk egy új élt u-ból z-be, amelynek költsége legyen c(uz) + c(zu), majd töröljük a z pontot. A keletkező kisebb pontszámú gráfra alkalmazzunk indukciót.

Tegyük fel, hogy az s pontból a digráf valamennyi pontja elérhető irányított úton. Jelölje l(v) az s-ből v-be vezető legolcsóbb út költségét egy c konzervatív súlyozásra nézve.

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

Biz. Adjunk a digráfhoz egy új s′ pontot és egy új s′s élt, melynek költsége legyen egy alkalmasan nagy M szám negatívja. Ekkor minden v-re a v-ben végződő legolcsóbb út s′-ben fog kezdődni. A 3.33 tétel bizonyításában láttuk, hogy ezen utak költsége megengedett potenciál. Ez viszont éppen az l függvény M-mel való eltoltja, tehát l is megengedett potenciál. •

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

Feladat 3.12 Igazoljuk, hogy egy éleken értelmezett költség-függvény akkor és csak akkor tenzió, ha minden kör összköltsége 0.

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ő.

Biz. Legyen π megengedett potenciál és P tetszőleges út s-ből t-be, melynek pontjai v_{1} = s, v_{2}, …, v_{k} = t. Ekkor c(P) = ∑ c(v_{i+1}v_{i}) ≥ ∑(π(v_{i+1}) − π(v_{i})) = π(t) − π(s), vagyis a tételben a min ≥ max irány következik.

A fordított irányú egyenlőtlenség igazolásához kell találnunk egy P st-utat és egy π megengedett potenciált, amelyekre c(P) = π(t) − π(s). E célra viszont egy tetszőleges P legolcsóbb st-út és az l megengedett potenciál megfelel. •

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. •

Feladat 3.13 Adott az éleken egy tetszőleges költség-függvény. Határozzunk meg egy olyan s-ből t-be vezető utat, amelyen a legnagyobb súly a lehető legkisebb.

Feladat 3.14 Tegyük fel, hogy az éleken két konzervatív költség-függvényünk adott: c_{1} és c_{2}. Készítsünk algoritmust olyan st út megkeresésére, amely a c_{1}-re nézve minimális költségű és ezen belül c_{2}-re nézve minimális költségű.

Feladat 3.15 Igazoljuk, hogy ha egy s-ből t-be vezető P út minden éle benne van egy legolcsóbb útban, akkor P maga is legolcsóbb út.

3.5.3 ACIKLIKUS DIGRÁFOK: A KRITIKUS UTAK MÓDSZERE

Tegyük most fel, hogy a D digráf aciklikus (azaz nem tartalmaz irányított kört) és az s pontból mindegyik másik pontba vezet út. Legyen a c súlyozás tetszőleges: ez automatikusan konzervatív. Aciklikus digráfnak mindig van olyan pontja, amelyből nem vezet ki él és ezért a pontokat olyan v_{1} = s, v_{2}, …, v_{n} sorba lehet rendezni, hogy minden él korábbi pontból későbbibe vezessen. Egy ilyen sorrendet mélységi kereséssel lineáris időben meg tudunk találni.

A legrövidebb utak fenyőjét aciklikus digráfban még a Dijkstra algoritmusnál is egyszerűbben fel tudunk építeni, mert a pontoknak a fenyőbe kerülési sorrendje nem menetközben derül ki, hanem az előre adott sorrend lesz. Tegyük fel, hogy az első j − 1 pont által feszített részgráfban már meghatároztuk a legolcsóbb utak egy F_{j−1} fenyőjét az l(v_{i}) költségekkel egyetemben (1 ≤ i ≤ j − 1). A sorrendben következő v_{j} pontra legyen l(v_{j}) := min(l(v_{i}) + c(v_{i}v_{j}) : v_{i}v_{j} ∈ E) és legyen F_{j} := F_{j−1} + v_{i}v_{j}, ahol a v_{i}v_{j} egy olyan él, amelyen a minimum felvétetik.

Alkalmazásokban gyakori, hogy aciklikus digráfban maximális súlyú utat kell keresni. Az is előfordul, hogy nem annyira az optimális útra vagyunk kiváncsiak, mint inkább az optimális potenciálra. Tekintsük páldául a következő feladatot. Egy projekt különféle részfeladatok elvégzéséből áll, melyeknek előre adott a végrehajtási ideje. Tudjuk továbbá, hogy bizonyos részfeladatoknak meg kell előzni másokat (házépítésnél az alapozás megelőzi a fürdőszoba csempézést), azaz a részfeladatok halmazán adott egy részbenrendezés. Kérdés, hogy mi az a legrövidebb idő, amely alatt a teljes projekt elvégezhető. További elvárás megadni az egyes részfeladatok kezdési időpontját úgy, hogy minden feladat kezdésére az őt a részbenrendezésben megelőzők már elkészüljenek.

A megoldáshoz készítsünk el egy D irányított gráfot a következőképpen. Reprezentáljunk mindegyik z részfeladatot egy u_{z}v_{z} irányított éllel, amelynek súlya legyen a z végrehajtási ideje. Amennyiben a z feladat megelőzi az y feladatot, úgy vegyünk be D-be egy v_{z}u_{y} élt 0 súllyal. Végül adjunk a digráfhoz egy s forráspontot, amelyből minden u_{x} pontba vezessünk 0 súlyú élt, és adjunk egy t pontot, amelybe minden v_{x} pontból vezessünk 0 súlyú élt. Feladatunk olyan π(v) időpontok kijelölésével ekvivalens, amelyekre π(s) = 0, π(t) minimális és minden uv élre a π(v) − π(u) időpontkülönbség legalább akkora, mint az él súlya. Ha most mindent negálunk, akkor aciklikus irányított gráfról lévén szó konzervatív súlyozást kapunk. Így a 3.35 tétel alkalmazásával rögtön kapjuk, hogy a projekt végrehajtásának minimális ideje egyenlő a legsúlyosabb út súlyával. Egy ilyen utat szoktak néha kritikus útnak nevezni, és az előzőekben leírt minimális út problémának az itteni feladatra adaptált változatát kritikus út módszernek (angolul PERT: project evaluation and review technique).

Tudunk tehát részbenrendezett halmazban maximális súlyú láncot keresni. Ezt alkalmazhatjuk a következő feladatokban.

Gyakorlat 3.16 Adott egy út bizonyos részútjainak F rendszere. Válasszunk ki F-nek diszjunkt tagjait úgy, hogy az összhosszuk maximális legyen.

Feladat 3.17 Adott két betűkből álló sorozat. Válasszunk ki algoritmikusan egy maximális sok tagból álló közös részsorozatot. A feladat még akkor is megoldható, ha az egyes betűknek különböző súlya van és a kiválasztott közös részsorozatban lévő betűk súlyösszegét akarjuk maximalizálni.

Feladat 3.18 Igazoljuk algoritmikusan, hogy egy P részbenrendezett halmazban a leghosszabb lánc elemszáma egyenlő a P -t fedő antiláncok minimális számával!

Feladat 3.19 Határozzuk meg algoritmikusan egy véges sorozat legtöbb tagból álló monoton növekvő részsorozatát!

Feladat 3.20 Igazoljuk, hogy egy nm + 1 különböző tagokból álló számsorozatnak vagy van n + 1 tagú monoton növő vagy egy m + 1 tagú monoton csökkenő részsorozata! Létezhet mind a két fajta részsorozat?

3.6 A MAGYAR MÓDSZER

A 3. fejezetben megmutattuk, hogy a lineáris programozás dualitás tételének teljesen unimoduláris feltételi mátrixok esetén miként vezet el Kőnig tételéhez és annak általánosításaihoz. Jelen célunk a Kőnig tételre és súlyozott kiterjesztésére algoritmikus bizonyítást adni.

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

Biz. Minden gráfra érvényes, hogy ν ≤ τ, hiszen k darab független élt nem lehet k-nál kevesebb ponttal lefogni. (Mellékesen megjegyezzük, hogy nem-páros gráfokra az egyenlőség nem feltétlenül teljesül, amint azt a háromszög vagy bármely páratlan kör példája mutatja.)

Páros gráf esetén az egyenlőség igazolásához konstruálunk egy M párosítást és egy L lefogást, melyek elemszáma ugyanaz. Az eljárás tetszőleges M párosításból indul ki, ami kezdetben az üres halmaz is lehet. Az általános lépésben vagy találunk egy nagyobb párosítást és ekkor a nagyobb párosításra vonatkozóan újra kezdjük az eljárást, vagypedig egy |M|-mel megegyező elemszámú lefogást, amikoris az algoritmus végetér.

Irányítsuk meg M éleit A-ból B felé, míg az összes többi élt fordítva. Jelölje S illetve T a B-ben illetve A-ban M által fedetlen pontok halmazát. Jelölje Z az S pontjaiból a kapott irányított gráfban elérhető pontok halmazát. Amennyiben T -nek esik pontja Z-be, akkor megkaptunk egy olyan S-t és T -t összekötő P utat, amely M-ben alternál. Most M és P szimmetrikus differenciája egy Mnél eggyel több élből álló M′ párosítás. (Technikailag az eljárást nagyon egyszerű végrehajtani: a megtalált út éleinek irányítását egyszerűen megfordítjuk. Az így kapott irányított gráf éppen az, amit G-ből kapunk az M′ éleinek A-ból B felé, és a többi élnek B-ből A felé történő irányításával.)

Tegyük most fel, hogy T diszjunkt Z-től. Z definíciója folytán Z-ből nem vezet ki irányított él. Érvényes továbbá, hogy Z-be nem lép be megirányított uv ∈ M párosítás él, mert hiszen v csak u-n keresztül érhető el, így v csak akkor lehetett irányított úton elérhető S-ből, ha u is az volt.

Következik, hogy az L := (A ∩ Z) ∪ (B − Z) halmaz lefogja az összes élt, továbbá minden M-beli élnek pontosan az egyik végpontját tartalmazza, tehát |M| = |L|. •

A fenti bizonyítás egyúttal hatékony algoritmust is jelent a szóbanforgó optimumok meghatározására. A lépésszám megbecsléséhez figyeljük meg, hogy legfeljebb n/2 alkalommal kell utat keresnünk. Miután egyetlen út megkeresése az élszámmal arányos időben történhet az össz-lépésszám nem nagyobb, mint O(nm) (ahol n a gráf pontszáma, míg m az élszáma).

TÉTEL 3.38 (M. Hall) Egy G = (A, B; E) páros gráfban akkor és csak akkor létezik A-t fedő párosítás, ha minden X ⊆ A részhalmazra teljesül a Hall féle |Γ(X)| ≥ |X| feltétel, ahol Γ(X) jelöli azon B-beli pontok halmazát, melyeknek van szomszédja X-ben.

Biz. Nyilván ν ≤ |A|. Ha ν = |A|, akkor egy ν elemű párosítás fedi A minden pontját. Ha ν < |A|, akkor Kőnig tétele nyomán létezik egy L lefogás, melynek |A|-nál kevesebb eleme van. De ekkor X := A − L-nek minden szomszédja B ∩ L-ben van, és |A − L| < |B ∩ L|, vagyis X megsérti a Hall féle feltételt. •

Tételezzük most fel, hogy a páros gráf élein adott egy c ≥ 0 (nem feltétlenül egészértékű) súlyfüggvény. Súlyozott párosításokra vonatkozóan több kérdést is feltehetünk. Például keressünk maximális súlyú párosítást, adott k-ra maximális súlyú k élű párosítást, maximális súlyú teljes párosítást, minimális súlyú teljes párosítást. Most ezek közül a maximális súlyú teljes párosítás kérdését vizsgáljuk meg és ehhez feltesszük, hogy G-nek van teljes (azaz minden pontot fedő) párosítása. A lefogás általánosításaként 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. (Itt V = A ∪ B).

Amennyiben Q jelöli a gráf pont-él incidencia mátrixát, úgy a max{cx : Qx = 1, x ≥ 0} lineáris program egészértékű megoldásai automatikusan 0 − 1 értékűek, azaz éppen a teljes párosítások incidencia vektorai. A {π : πA ≥ c} duális poliéder egy eleme éppen egy súlyozott lefogás. Az alábbi tétel, (amely nem más, mint a 3.13 tétel) tartalma az, hogy a primál optimum mindig egészen vektoron felvétetik (c egészértékűségétől függetlenül), míg a duál optimum egészértékű c esetén egész vektoron felvétetik.

TÉTEL 3.39 (Egerváry) 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.

Biz. Legyen M := {u_{1}v_{1}, u_{2}v_{2}, …, u_{n}v_{n}} tetszőleges teljes párosítás G-ben, és π egy súlyozott lefogás. Ekkor c(M) := ∑ c(u_{i}v_{i}) ≤ ∑(π(u_{i}) + π(v_{i}) : i = 1, …, n) = π(V), amiből ν_{c} ≤ π_{c} következik. Itt egyenlőség pontosan akkor áll, ha M minden éle pontos.

A fordított irányú egyenlőtlenség bizonyításához tehát kell találnunk egy π súlyozott lefogást úgy, hogy a π-re vonatkozó pontos élekből álló részgráf tartalmazzon teljes párosítást. Ennek érdekében kiindulunk egy tetszőleges π súlyozott lefogásból (amely egészértékű, amennyiben c az). Például legyen π a B pontjaiban 0, míg bármely A-ban levő v pontra π(v) legyen a v-be futó élek súlyának maximuma.

Az általános lépésben tekintjük a pontos élek által (a V ponthalmazon) alkotott G_{π} részgráfot. Az előzőekben leírt algoritmus segítségével határozzunk meg G_{π}-nek egy maximális elemszámú M párosítását. A fent bevezetett jelölést használjuk: S illetve T a B-beli illetve az A-beli (M által) fedetlen pontok halmazát jelöli, míg Z a szóbanforgó irányított gráfban az S-ből elérhető pontok halmazát.

Amennyiben M teljes párosítás, úgy célunkat elértük, mert megkaptunk egy pontos élekből álló teljes párosítást. Ekkor tehát az algoritmus végetér (és a tétel bizonyítása is). Tegyük fel, hogy M nem teljes párosítás. A π értékeit csökkentsük A − Z elemein egy bizonyos Δ pozitív számmal, és növeljük B −Z elemein ugyanazzal a Δ-val, ahol Δ := min(π(u)+π(v)−c(uv) : uv ∈ E, u ∈ A−Z, v ∈ B ∩Z). Amennyiben G-nek nincs olyan uv éle, amelyre u ∈ A − Z, v ∈ B ∩ Z, azaz a minimumot az üres halmazon vesszük, úgy G-nek nincs teljes párosítása, hiszen az A − Z halmaz megsérti a Hall féle feltételt.

A konstrukció miatt Δ pozitív (merthogy nincs pontos él A−Z és B ∩Z között), és a módosított π′ is súlyozott lefogást alkot. Érvényes továbbá, hogy a G_{π′} és M-hez tartozó irányított gráfban (:M-beli élek B felé irányítva, a többi él A felé) Z minden eleme továbbra is elérhető és még legalább egy új pont is A-ban, nevezetesen egy olyan élnek a végpontja, amelyen a Δ-t definiáló minimum felvétetik (merthogy ez az él a módosított π′-re nézve már pontos lesz).

Ezen meggondolásból következik, hogy π-nek legfeljebb n változtatása után az aktuális pontos élek gráfjában a ν megnő. Legfeljebb n ilyen növekedés után kapunk egy pontos élekből álló teljes párosítást, ami a célunk volt. Az algoritmus lépésszáma O(n^{2}m). •

Feladat 3.21 Igazoljuk, hogy ha egy M párosítás valamely π súlyozott lefogásra nézve pontos élekből áll, akkor M az összes vele megegyező elemszámú párosítások közül maximális súlyú!

3.7 A NÖVELŐ UTAK MÓDSZERE

Korábban a Hoffman tételre támaszkodva bebizonyítottuk a Maximális-folyam Minimális-vágás (3.29) tételt. A bizonyítás első feléből kiolvasható, hogy egy x folyam maximális nagyságú, amennyiben létezik egy olyan S st̄-halmaz, amelyre teljesülnek az alábbi 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.

Jelen célunk egy ilyen x folyam és S halmaz algoritmikus megkeresése. Ezt először csak egészértékű (illetve racionális) g kapacitás függvény esetén tesszük meg, majd tetszőleges g-re. Az eljárás egyúttal új bizonyítást ad a 3.29 tételre.

A Fordtól és Fulkersontól származó algoritmus tetszőleges x megengedett st-folyamból indul ki (például x ≡ 0), és azt iteratívan javítja. Készítsünk el egy D_{x} = (V, A_{x}) digráfot a következőképp. 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. Mivel D_{x} semelyik éle sem lép ki S-ből, az (a) és (b) optimalitási feltételek teljesülnek és az algoritmus végetér: az adott x folyam nagysága egyenlő δ_{g}(S)-sel.

2. Eset t ∈ S, azaz t elérhető s-ből. Legyen P tetszőleges s-ből t-be vezető irányított út D_{x}-ben.

Legyen Δ_{1} := min(g(uv) − x(uv) : uv előre éle P -nek) és Δ_{2} = min(x(v, u) : uv hátra éle P -nek). Legyen Δ = min(Δ_{1}, Δ_{2}). Ekkor Δ pozitív. Nevezzük P egy élét kritikusnak, ha Δ ezen az élen éretik el.

Módosítsuk x-t a következőképp. Ha uv előre éle P -nek, növeljük x(uv)-t Δ-val. Ha uv hátra éle P -nek, csökkentsük x(vu)-t Δ-val. Könnyen látható, hogy a módosított x′ megengedett folyam lesz, amelynek nagysága Δ-val nagyobb, mint x-é. Következésképp, ha g egészértékű, akkor a 2. eset csak véges sokszor fordulhat elő, vagyis véges sok növelés után az 1. eset következik be, amikor is az algoritmus véget ér. Tehát egész kapacitások esetén új bizonyítást kaptunk az MFMC tételre. •

Amennyiben g racionális, a nevezők legkisebb közös többszörösével a kapacitásokat végigszorozva visszajutunk az egész kapacitású esethez. Ha viszont g irracionális, akkor a fenti eljárás nem biztosan ér véget véges sok lépésben (amint az példával demonstrálható). Másik hátrány, hogy még egész kapacitások esetén is az iterációk száma arányos lehet az előforduló legnagyobb kapacitás nagyságával. Így az algoritmus bonyolultsága az input méretének exponenciális függvényével arányos, azaz nem polinomiális. (Egy szám nagysága a jegyei számának exponenciális függvénye.)

3.7.1 SKÁLÁZÁSI TECHNIKA

Az alábbiakban bemutatunk egy igen ügyes fogást, amelynek segítségével bizonyos eljárásokat polinomiális futásidejűvé lehet tenni. Használatát a maximális folyam problémán szemléltetjük, mert ott igen egyszerű, de számos alkalommal bonyolultabb körülmények között is használható.

Tételezzük fel, hogy a kapacitások egész számok és kettes számrendszerben vannak megadva. A legnagyobb kapacitás álljon M jegyből. Összesen M darab folyam problémát fogunk megoldani, mindegyikben a megelőzően megkapott maximális folyamot használjuk kiindulási folyamként. Jelölje g_{i} azt a kapcitás függvényt, amely úgy áll elő, hogy minden élen az eredeti kapacitásnak (balról) az első i jegyét tekintjük, míg a többit eltöröljük. Tegyük fel, hogy a g_{i} kapacitás függvényre nézve már meghatároztuk az x_{i} maximális folyamot. Ekkor 2x_{i} megengedett folyam a g_{i+1}-re nézve. A 2x_{i}-ből kiindulva alkalmazzuk a fent leírt növelő út módszert a g_{i+1} kapacitás függvényre vonatkozólag.

Miután minden e élre g_{i+1}(e) értéke vagy 2g_{i}(e) vagy 2g_{i}(e) + 1, legfeljebb élszámnyi növelés után megkapjuk az x_{i+1} maximális folyamot (a g_{i+1}-re nézve). Összesen tehát legfeljebb M|A| növelés segítségével megkonstruáltunk egy eredeti kapacitásokra vonatkozó maximális folyamot.

3.7.2 LEGRÖVIDEBB NÖVELŐ UTAK

A fenti eljárás hátránya, hogy csak egész (és így racionális) kapacitásokra működik. Vagyis általános kapacitások esetén még mindig nincs konstruktív bizonyításunk az MFMC tételre. Ezen nehézség leküzdésére J. Edmonds and R. Karp [1972] és E.A. Dinitz [1970] javasolták, hogy minden iterációban a legkisebb élszámú növelő utat válasszuk. Ez az egyszerű megszorítás lehetővé teszi, hogy a Ford-Fulkerson algoritmus bonyolultságát |V | és |A| polinomjával korlátozzuk, függetlenül a kapacitások nagyságától. (Ezt persze úgy értve, hogy a számokkal végzett alapműveleteket egyetlen lépésnek tekintjük.)

Jelölje σ_{x}(v) a v távolságát D_{x}-ben s-től. (Ha nincs egyáltalán s-ből v-be út, akkor σ_{x}(v) = ∞). Legyen P egy legrövidebb út D_{x}-ben s-ből t-be. Ekkor P mindegyik uv élére, σ_{x}(v) = σ_{x}(u) + 1.

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

Biz. Nézzük meg milyen hatással van a növelés a D_{x} segédgráfra. Mivel a folyamot D-nek csak olyan élein változtattuk, melyek P éleinek felelnek meg, D_{x} csupán P éleinél változhat. Éspedig, D′_{x} lehetséges új élei P élei megfordítva, ugyanakkor P kritikus élei (ahol Δ felvétetik) eltűnnek D_{x}-ből. A v pont s-től való távolsága csak akkor csökkenhetne, ha olyan uw éleket adnánk a segédgráfhoz, melyekre σ_{x}(w) > σ_{x}(u) + 1, amiből a lemma következik. •

A növelések sorozatát fázisokra bontjuk. Egy fázis során σ_{x}(t) ugyanaz marad. A lemma szerint legfeljebb |V | − 1 fázis lehetséges.

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

Biz. Jelölje σ_{i}(v) a v pont távolságát s-től az i fázis kezdetén az aktuális segédgráfban. Nevezzünk egy uv élt i-szorosnak, ha σ_{i}(v) = σ_{i}(u) + 1. Az i-dik fázis során csupán i-szoros éleket használunk. Tudjuk, hogy egy növelés legalább egy i-szoros élt eltüntet az aktuális segédgráfból és nem hoz be új i-szoros élt. Mivel a segédgráfnak legfeljebb |A| darab i-szoros éle van, a lemma következik. •

Mindezeket összetéve kapjuk, hogy legfeljebb |V ||A| növelésre van szükségünk. Egyetlen növelés O(|A|) lépést igényel, így az algoritmus össz-bonyolultsága O(|V ||A|^{2}).

Miután a fenti algoritmusban választási lehetőségünk lehet a legrövidebb növelő út meghatározásában, a végül kapott maximális folyam függhet ezen választásoktól. Nem így a végső S!

Feladat 3.22 (a) A végül kapott minimális δ^{+}(S) vágás független az algoritmus futásától. (b) Ha X és Y minimalizálja az δ_{g}(Z) értéket az összes st̄-halmazra, akkor X ∩ Y és X ∪ Y is minimalizáló st̄-halmazok. (c) A minimalizáló halmazok metszete S.

Feladat 3.23 Adott e élre hogyan lehet eldönteni, hogy (a) létezik-e olyan maximális folyam, amely telíti e-t, (b) minden maximális folyam telíti e-t.

Feladat 3.24 Algoritmikusan határozzuk meg az összes {x, y} rendezett csúcspárt, amelyre létezik olyan X halmaz, hogy s, x ∈ X, y ∈ V − X és X minimális vágást határoz meg.

3.8 MINIMÁLIS KÖLTSÉGŰ FOLYAMOK

Legyen adva D = (V, A) irányított gráf az s forrás- és a t nyelőponttal. Adott még az éleken a g nemnegatív kapacitás függvény és a c nemnegatív költségfüggvény. Feltesszük, hogy g egészértékű. Korábban már láttuk, hogy miként lehet egy maximális M nagyságú s-ből t-be vezető folyamot polinom időben kiszámítani. Most minden 0 és M közé eső k egészre szeretnénk találni egy olyan k nagyságú folyamot, melynek költsége minimális. Egy z folyam költségét a cz = ∑(c(e)z(e) : e ∈ A) skaláris szorzattal definiáljuk. Azt mondjuk, hogy a z st-folyam minimális költségű folyam, ha z a legkisebb költségű a megengedett, z-vel azonos nagyságú st-folyamok közül.

Az alábbiakban ismertetjük Ford és Fulkerson [1962] algoritmusát. 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. Használni fogjuk a következő jelölést. c̄(uv) = c(uv) − π(v) + π(u), ahol uv ∈ A. Potenciálok segítségével egy z folyam cz költségére az alábbi alsó korlátot nyerhetjük.

∑ c(uv)z(uv) = ∑(π(v) − π(u))z(uv) + ∑ c̄(uv)z(uv) = π(t)k + ∑(c̄(uv)z(uv) : c̄(uv) < 0) + ∑(c̄(uv)z(uv) : c̄(uv) > 0) ≥ π(t)k + ∑ c̄(uv)g(uv) + 0.

Ebből következik, hogy egy z folyam bizonyosan minimális költségű, amennyiben létezik olyan π potenciál, amelyre az egyenlőtlenség egyenlőséggel teljesül. Ez pontosan akkor van így, ha fennáll a következő két optimalitási feltétel.

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

[Tetszőleges π potenciálra a π(v) − π(u) potenciál különbség egy semleges költségfüggvényt definiál az élhalmazon abban az értelemben, hogy minden k nagyságú folyamnak ugyanaz a költsége, éspedig k(π(t) − π(s)). Így, ha a c költségfüggvényt egy potenciál különbséggel eltoljuk, akkor a kapott c̄(uv) := c(uv)−(π(v)−π(u)) költségfüggvény ekvivalens az eredetivel. Ennek alapján az optimalitási feltételeket úgy is lehet interpretálni, hogy egy z folyam akkor és csak akkor minimális költségű, ha létezik egy olyan c̄ ekvivalens költségfüggvény, amely ha egy uv élen pozitív, úgy a folyam a minimumon van, azaz z(uv) = 0, míg ha c̄(uv) negatív, úgy a folyam a maximumon van, azaz z(uv) = g(uv).]

Ford és Fulkerson módszere a maximális folyam kiszámítására vonatkozó Ford-Fulkerson algoritmus finomításának tekinthető. Minden lehetséges egész k értékre megkonstruálunk egy minimális költségű k nagyságú folyamot. Az eljárás az azonosan nulla folyammal és az azonosan nulla potenciállal indul. Ezután a folyam nagyságát növeljük egyenként, illetve menetközben néha a potenciált növeljük úgy, hogy az optimalitási feltételek végig fennállnak. Az algoritmus akkor ér véget, amikor maximális nagyságú folyamot illetve egy minimális vágást kaptunk.

ITERATÍV LÉPÉS Az általános helyzetben adott a z folyam és a π potenciál, és ezek kielégítik az (i) és (ii) feltételeket. Megkonstruálunk egy D′ = (V, A′) segédgráfot a következőképpen. D′-nek kétféle éle van: előre és hátra. 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.

Legyen S az s-ből D′-ben irányított úton elérhető pontok halmaza. Két eset lehet.

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

Legyen ε_{1} = min(c̄(uv) : uv ∈ δ^{+}(S), z(uv) < g(uv)) és ε_{2} = min(−c̄(uv) : uv ∈ δ^{+}(V −S), z(uv) > 0), ahol az üres halmazon vett minimumot ∞-nek definiáljuk. Legyen ε = min(ε_{1}, ε_{2}). Az optimalitási feltételek és az S definíciója miatt ε pozitív.

Amennyiben ε = ∞, akkor az algoritmus végetér. Ebben az esetben az S-ből kilépő eredeti élek mind telítettek, míg az S-be belépő eredeti élek mindegyikén a folyam nulla. Így tehát δ_{g}^{+}(S) = val(z), az aktuális z folyam maximális nagyságú és az S-ből kilépő élek halmaza minimális vágást határoz meg.

Legyen most ε < ∞, és módosítsuk π-t úgy, hogy minden v ∈ V − S-re növeljük π(v)-t ε-nal. Az S és az ε definíciójából rögtön kapjuk:

Állítás 3.42 A módosított potenciál és a változatlanul hagyott z folyam kielégíti az optimalitási feltételeket.

Készítsük el az új segédgráfot és ismételjük meg az eljárást. Figyeljük meg, hogy a segédgráfban a régi S által feszített élek változatlanok maradnak és ezért az s-ből elért pontok halmaza szigorúan bővebb lesz, mint S. Ezért az 1. eset legfeljebb |V |−1-szeri előfordulása után biztosan vagy az ε = ∞ következik be, vagypedig az alábbi 2. eset.

2. Eset t ∈ S, vagyis t elérhető s-ből. Legyen P a D′-ben egy s-ből t-be vezető irányított út. Módosítsuk z-t a következőképpen. Legyen z′(uv) = z(uv) + 1, ha uv a P -nek előre éle és legyen z′(uv) = z(uv) − 1, vu a P -nek hátra éle.

A módosításból adódik:

Állítás 3.43 A módosított folyam és változatlanul hagyott potenciál kielégíti az optimalitási feltételeket.

Ezzel az algoritmus leírását be is fejeztük. Mi mondható az eljárás futásidejéről? Lényegében M darab növelésre van szükségünk (2. eset), így az eljárás polinomimális, amennyiben mind az M minimális költségű folyamot meg kell határoznunk.

Elképzelhető persze olyan helyzet is, amikor például csak egy maximális nagyságú minimális költségű folyamot kell kiszámítanunk. Ebben az esetben az algoritmus természetesen nem biztosan polinomiális, hiszen lépésszáma az M nagyságával arányos. De még ebben az esetben is két fontos speciális eset kezelhető.

Ha a legnagyobb kapacitás nem túlságosan nagy (nevezetesen, ha |V | polinomjával korlátozható), akkor a fenti eljárás nyilván polinomiális, függetlenül attól, hogy a c költség-függvény egészértékű-e vagy sem.

Tegyük most fel, hogy a kapacitások tetszőlegesek, a költség-függvény egészértékű és ”kicsi”. Ekkor az algoritmus következő módosítása erősen polinomiális algoritmust eredményez. Tekintsük az algoritmus egy közbenső helyzetét, amikor egy π potenciál rendelkezésre áll. A szoros élek digráfjában (egy uv él szoros, ha c̄(uv) = 0) számítsunk ki (a Max-flow Min-cut algoritmusssal) egy maximális nagyságú z folyamot és egy S minimális ki-kapacitású st̄-halmazt. Ha D-ben minden S-be belépő és S-ből kilépő él szoros, akkor S minimális vágást határoz meg és az aktuális z folyam maximális nagyságú, amely kielégíti az optimalitási feltételeket. Ebben az esetben az algoritmus véget ér.

Amennyiben D-nek létezik nem-szoros éle, amely S-be be- vagy kilép, akkor ε, ahogy azt fentebb az 1. esetnél kiszámítottuk, véges lesz. Módosítsuk π-t úgy, mint az előbb, azaz minden v ∈ V − S-re növeljük π(v)-t ε-nal.

Azt állítjuk, hogy a π(t) érték a D digráf valamely (irányítatlan értelemben vett) s-ből t-be vezető útjának a költsége. Valóban, minden folyam-növeléskor a segédgráfban van olyan st út, amely szoros élekből áll.

Következik, hogy a különböző π(t) értékek száma (vagyis az 1. eset előfordulásainak száma) felülről korlátozható az élek össz-költségével. Tehát az eljárás polinomiális, ha a c egészértékű és legnagyobb értéke |V | polinomjával korlátozható.

Van olyan példa (sorozat), amely azt mutatja, hogy ha c-nek csak az egészértékűségét tesszük fel, akkor az algoritmus nem polinomiális.

Feladat 3.25 Igazoljuk, hogy tetszőleges c esetén a fenti algoritmus véges sok lépésben véget ér.