Jegyzet Operációkutatás I cím¶ tantárgyhoz Fábián Csaba el®adásai alapján készítette Papp Olga
2009 január 26
1
Tartalomjegyzék 1. Bevezetés
3
2. A szimplex módszer
5
2.1. A szimplex módszer elméleti vs. gyakorlati megfontolásai . . .
9
3. Dualitás
16
4. Farkas lemma
24
5. Hálózati folyam feladat
26
6. Speciális esetek hálózati folyam feladatra
37
7. König-Egerváry eljárás
38
8. Magyar módszer
41
6.1. Szállítási feladat . . . . . . . . . . . . . . . . . . . . . . . . . . 37 6.2. Hozzárendelési feladat . . . . . . . . . . . . . . . . . . . . . . 37 6.3. Párosítási feladat . . . . . . . . . . . . . . . . . . . . . . . . . 38
2
1. Bevezetés Lineáris programozási feladat (LP) kanonikus alakja. £
¤
xT
£
=b
A
¤
cT
Ahol A ∈ Rmxn , m ≤ n , c, x ∈ Rn , b ∈ Rm .
Ax = b x≥0 maxcT x Tegyük fel, hogy az A mátrix teljesrangú - azaz van m darab független oszlopvektora.
1.1. De nició (Megoldás). Azt mondjuk, hogy x ∈ Rn vektor megoldás,
ha Ax = b a fenti LP feladatra.
1.2. De nició (Megengedett megoldás). Azt mondjuk, hogy x ∈ Rn vektor megengedett megoldás, ha Ax = b ∧ x ≥ 0 a fenti LP feladatra.
1.3. De nició (Optimális megoldás). Azt mondjuk, hogy x ∈ Rn vektor
optimális megoldás, ha x megengedett megoldás és tetsz®leges x¯ megengedett megoldás esetén cT x ≥ cT x¯
1.1. Megjegyzés. Biztos, hogy van megoldás, mert A teljesrangú. A független
oszlopai kifeszítik az Rm teret, így b el®állítható ezen független vektorok lineáris kombinációjaként.
1.4. De nició (Bázis). Bázisnak nevezünk egy olyan B leképezést a sorok
halmazából az oszlopok halmazába, amelyre az aB1 , aB2 , ..., aBm oszlopvektorok lineárisan függetlenek.
1.2. Megjegyzés. A lineáris algebrától eltér®en itt nem halmazt, hanem rendezett halmazt tekintünk bázisnak.
3
1 2 m
...
aB1 aBm aB2 ...
1.5. De nició (Bázishoz tartozó bázismátrix).
aBm =: B
aB1 aB2 ...
1.3. Megjegyzés. A B mátrix invertálható, mert teljesrangú. A továbbiakban tegyük fel, hogy adott a B bázis. Tegyük fel azt is, hogy A-ban a bázisoszlopok egymás után következnek.
A =
... B ...
1.1. Jelölés. Jelöljük xB -vel az x vektor bázishoz tartozó részét. (xB )i := xBi Jelöljük cB -vel az c vektor bázishoz tartozó részét.
(cB )i := cBi
1.6. De nició (B bázishoz tartozó bázismegoldás). Ha az x vektorra teljesül, hogy a bázison kívüli komponensei 0-ák, a bázishoz tartozó komponensekre pedig teljesül, hogy BxB = b, akkor x-et B bázishoz tartozó bázismegoldásnak nevezzük. 4
1.4. Megjegyzés. Ilyen bázismegoldás létezik és egyértelm¶: xB = B −1 b. Ez a vektor a feladat megoldása, ugyanis Ax = BxB = b. Azt viszont nem tudjuk, hogy ez a megoldás megengedett vagy sem.
1.5. Megjegyzés. Minden bázishoz egyetlen bázismegoldás tartozik, de el®fordulhat, hogy¤ két különböz® bázishoz tartozó bázismegoldás ugyanaz: £ ·1 0 1 ¸ · ¸ 0 1 0 1 = 1 0 1 1 A fenti példában két különböz® bázishoz is (1,2 és 2,3 oszlopok) ugyanaz a bázismegoldás tartozik. A továbbiakban tegyük fel, hogy olyan B bázisunk van, amihez tartozó bázismegoldás megengedett (azaz xB komponensei ≥ 0-k). Továbbá tegyük fel, hogy az A mátrixunkat úgy transzformáltuk, hogy a bázismátrix az egységmátrix legyen (az egyenletrendszer rendezésével ez elérhet®).
A =
... I ...
A továbbiakban ezt a transzformált mátrixot fogjuk A-val jelölni, a transzformált jobboldalt pedig b-vel (az x és a c vektorok nem változnak).
2. A szimplex módszer A szimplex módszer alaplépése. Vegyünk egy tetsz®leges j oszlopot,
ami nem tartozik a bázishoz (ekkor xj = 0, mert j ∈ / B ). Kezdjük el növelni xj -t, és a báziskomponenseket igazítsuk úgy, hogy az Ax = b egyenl®ség megmaradjon. Meg fogjuk mutatni, hogy igazíthatunk, és hogy ez az igazítás egyértelm¶ lesz.
Kezdeti megoldás. ∅aj +
m X
xBi aBi = b
i=1
Mivel B = I , ezért aBi = ei és xBi = bi , így
∅aj +
m X i=1
5
bi ei = b
Növeljük xj -t 0-ról ϑ-ra.
ϑaj +
m X
(bi − ϑaij )ei = b
i=1
Láthatjuk, hogy az utánaigazítás lehetséges és egyértelm¶. Ha xj -t ϑ-ra növeljük, akkor x¯Bi := xBi − ϑaij (= bi − ϑaij ) Javítunk ezzel a lépéssel a célfüggvényen? Változó célfüggvény megoldás i. báziskomponense ehhez tartozó célfüggényérték megoldás célfüggvény
Eredeti érték
Új érték
bi cBi xBi
bi − ϑaij cBi (bi − ϑaij )
változás +ϑcj
−ϑaij −ϑcBi aij
Pm Pm T Összegezve a változást: i=1 −ϑcBi aij = −ϑ( i=1 cBi aij ) = −ϑcB aj Tehát akkor érdemes az alaplépést elvégezni, ha ϑcj − ϑcTB aj = ϑ(cj − cTB aj ), (ϑ > 0), azaz amikor cj − cTB aj > 0
2.1. Megjegyzés. Ezt könny¶ végigvenni az egyes nembázisbeli oszlopokkal:
ha az eredmény > 0, akkor javító oszlopvektort találtunk.
2.1. De nició (Javító-oszlop). Azt mondjuk, hogy a j -edik oszlopvektor
javító-oszlop, ha cTB aj < cj .
Ha olyan állapotba érünk, hogy nincs javító oszlopvektor, akkor az eljárás leáll. Meg fogjuk mutatni, hogy ebben az esetben optimális megoldást találunk. A továbbiakban tegyük fel, hogy a p-edik oszlopvektor javítóoszlop. Meddig lehet növelni a ϑ-t? P Az alaplépésben ϑap + m i=1 (xBi − ϑaip ) = b, ahol xBi = bi és aBi = ei . A célfüggvény növekedés pedig: ϑ(cp − cTB ap ). ϑ tehát addig növelhet®, amíg (xBi − ϑaip ) (= bi − ϑaip ) sehol sem válik negatívvá, azaz a megoldás megengedett marad.
• Ha aip ≤ 0 valamely i. sorindexre, akkor a (bi −ϑaip ) nem fog csökkenni. Az ilyen i-k nem jelentenek korlátot. • Ha aip > 0, akkor ϑ ≤
bi aip
A legnagyobb megengedett ϑ így: ϑ = minaip >0 6
bi aip
2.2. Megjegyzés. Ha aip ≤ 0∀i = 1..m, akkor ϑ minden határon túl növelhet®. Ezért a célfüggvény is minden határon túl növelhet® lesz. Az eljárás leáll. A továbbiakban feltesszük, hogy az ap oszlopvektornak vannak pozitiv komponensei. bq ≤ abipi minden olyan i Legyen 1 ≤ q ≤ n olyan sorindex, amelyre aqp sorindexre, ahol aip > 0. bq Válasszuk ϑ-t a lehet® legnagyobbra: ϑ¯ = aqp . Nézzük meg az alaplépés hatását az adott p, q -ra. A megoldás változása:
¯ p+ ϑa
m X
¯ ip )ei (bi − ϑa
i=1
2.3. Megjegyzés. A fenti szummában a q -ik sorhoz tartozó tag: bq −
bq aqp = 0 aqp p
kezdeti megoldás
∅
ϑ¯-hoz tartozó megoldás
ϑ¯
B
∅ Bq -hoz tartozó oszlopindex új
kezdeti mátrix
q
+
Az új bázis:
½ B¯i =
ha i 6= q ha i = q
Bi p
Ez valóban bázis. 7
  ?? ??   ?? ??   ??   ?? ??   I ?? ??   ??  ??   ? ?   ??
Az alábbi oszlopok lineárisan függetlenek:
aB¯1 , . . . , aB¯q , . . . , aB¯m azaz
aB1 , . . . , ap , . . . , aBm
Bizonyítás Legyenek λ1 , . . . , λq , . . . λm olyan súlyok, hogy
P
λi aB¯i = 0. Az aB1 , . . . , ap , . . . , aBm -b®l csak a q . egységvektor hiányzik (eq ) - ehelyett vettük be ap -t. A q sorban a vektorok poziciói mind 0-k, kivéve aqp > 0. Ebb®l következik, hogy λq = 0. A többi vektor együtthatója is 0, hiszen azok eleve lineárisan függetlenek voltak. ¤ Az új B¯ bázishoz tartozó bázismegoldás megengedett. Transzformáljuk a feladatot (sorkivonogatással) úgy, hogy a bázisban lev® oszlopok egységvektorokká váljanak. Így a feladat formálisan ugyanolyan állapotban van, mint az alaplépés el®tt: a bázismegoldás megengedett, a bázismátrix az identitásmátrix. Az ¯ p − cT ap ). eredetihez képest a különbség csak az, hogy a célfüggvény n®tt: ϑ(c B
Ismételjük az eljárást.
Hogyan állhat meg az eljárás?. • Nincs javítóvektor. Stop. Nincs megengedett megoldás. • A javítóoszlopban nincs > 0 komponens. Stop. A megoldás nem
korlátos.
A szimplex µ ¶módszer megengedett bázisokon lépked. A bázisok száma n véges: ≤ m Tegyük fel, hogy minden lépésben ϑ > 0 adódik. Ekkor minden lépésben határozottan javul a célfüggvény érték. Ezért ilyenkor nem térhetünk vissza olyan bázisba,amelybe már jártunk. A fenti feltétel mellett a szimplex módszer véges sok lépésben leáll.
Mikor lehet ϑ¯ = 0?. Akkor, ha bi = 0 valamely i = 1..m. bi = 0 azt
jelenti, hogy a b jobboldalvektor benne van az aB1 , . . . , aBi−1 , aBi+1 , . . . , aBm bázisoszlopok által kifeszített altérben.
2.4. Megjegyzés. Ha a jobboldalt véletlenszer¶en választom folytonos eloszlás szerint, akkor ennek az esetnek 0 a valószín¶sége. 8
2.2. De nició (Általános helyzet¶ jobboldal). Ha a jobboldal egyetlen altérben sincs benne, akkor azt mondjuk, hogy a jobboldal általános helyzet¶.
Tegyük fel, hogy a szimplex módszer azzal állt le, hogy nem találunk javítóoszlopot, azaz cTB aj ≥ cj minden nem bázisbeli oszlopindexre.
B
cB
B=I
=
≥
≥
cTB Bázisoszlopokra pedig: cTB aBi = cBi teljesül.
Megállási feltétel. cTB A ≥ cT
Meg fogjuk mutatni, hogy ebben az esetben az aktuális megoldásra (x) (a B bázishoz tartozó bázismegoldás) teljesül a következ®: Minden x¯ megengedett megoldásra (A¯ x = b, x¯ ≥ 0) cT x¯ ≤ cT x azaz x optimális megoldás.
2.1. A szimplex módszer elméleti vs. gyakorlati megfontolásai Elméletileg. Van olyan feladat, amelyre ha elég ügyetlenül választjuk a báziscseréket - a szimplex módszer ciklizál. Tekintsük a kétdimenziós teret. Ebben a térben az
Ax ≤ b x≥0 maxcT x
9
feladatban minden ai x ≤ bi feltételnek megfelel a következ® ábra:
x2 O II ªªªªIªIII ª ªª ª II ª ªª ªIII ª ªª ª II ª ªª ª II ª ªª ªIII ª ªª ª II ª ªª ªIII / ª ªª ª II ª ªª ª II ª ªª ªIII ª ªª ª ª ªª
x1
El®fordulhat degenerált feladat - ilyenkor egy adott csúcs (bázismegoldás) több bázishoz is tartozik( lásd az x csúcsot, amely a (2,3), (3,4) és (2,4) bázisokhoz egyaránt tartozik)
x2 O
II I
ggggg
(1)gggggIgIgIgI 9 I 9 ggggg
I 9
ggg ggggg
II 9 (2) III99I9 x I¼9I
¼ 99 ¼¼ ¼ 999 99(3) ¼ ¼¼ ¼ (4) 999 99 ¼ ¼t¼ ¼ tt tt (5) tt ¼¼¼ t t tt /
x1 A szimplex a megengedett tartomány szomszédos csúcsain lépked. Ha a feladat degenerált, el®fordulhat, hogy a fent említett x csúcshoz érve, a szimplex ciklizál - báziscsere van, de nem tud kilépni a csúcsból.
Gyakorlatilag. ez nem fordulhat el®, mivel a numerikus hibák miatt a síkok kicsit elmozdulnak.
10
Megoldás. csúsztassuk el a redundáns feltételt: ?? ? S ¶¶ S¶ S¶ SSSS ??? ¶ ¶ ¶¶ ¶ ¶ SSS?? ¶ ¶ ¶¶ ¶ ¶ SS?S?S ¶ ¶ _¶_¶ ?SSS __ ?? __ ?? __ ?? __ __ __ __ __ __ __
?? S ? ±± ±SSSS?S??S ± ±± ± ± ?S?SS ± ± ± ± ? SSS ± ± Äı ?? SSS ±ÄÄÄ ? S ÄÄ_Ä_Ä?? / ? Ä __ ?? __ __ __ __ __ __ __
Ez a jobboldal perturbálásának felel meg. w
x
A
b1 + ε . . . b m + ε ?? ?? b1 + ε ?? ?? ?? ?? ? = I??? ?? ?? ?? ?? ?? bm + εm
Könny¶ megmutatni, hogy ha ε elég kicsi, akkor a degeneráció megsz¶nik. Eredeti feladat B megengedett kezd®bázis nem tudjuk, hogy a jobboldal általános helyzet¶-e
Perturbált feladat B megengedett kezd®bázis van olyan pozitiv ε, hogy a jobboldal általános helyzet¶
2.1. Állítás. Ha ε-t elég kicsire választjuk, akkor teljesül a következ® állítás:
Legyen B¯ a perturbált feladatnak megengedett bázisa ( azaz a hozzá tartozó bázismegoldás megengedett). Akkor B¯ az eredeti feladatban is megengedett bázis.
Bizonyítás A de nicióból következik. Megmutattuk tehát, hogy lehet úgy perturbálni a feladatot, hogy azon végighaladva a szimplex módszerrel, és ezeket a lépéseket megfeleltetve az eredeti feladatnak - szabályos lépések sorozatát kapjuk. Kijelenthetjük a következ®t:
2.2. Állítás. A szimplex módszer bázisba lép® és az onnan kilép® vektorok megválaszthatók úgy, hogy az eljárás véges sok lépésben leálljon. 11
Elméletileg. ha x ∈ Rn , akkor tudok olyan LP feladatot szerkeszteni,
amelynek 2n megengedett bázismegoldása van. Például: (0 . . . 0) ≤ x ≤ (1 . . . 1) - nek a megengedett tartománya az n-dimenziós kocka. A megengedett bázismegoldások száma pedig: 2n . Nézzük a következ® táblázatot:
n pontok bejárásának ideje
10
1 1000
sec
20 1 sec
30 18 min
40 12 nap
50 35 év
60 36.000 év
Ha a számítógépek 1024-szer gyorsabbak, akkor is csak eggyel tolódik jobbra az alsó oszlop. Ez azt jelentené, hogy még a kis feladatokat sem tudnánk megoldani a szimplex módszerrel valós id®ben.
Gyakorlatban. általában 2m lépésre van szüksége a szimplex módszernek,
ha jól van implementálva.
Hogyan lehet megengedett kezd®bázist keresni?. Legyen A teljes-
rangú mátrix, b megfelel® dimenziós vektor.
Ax = b x≥0 Nincs szükségünk célfüggvényre, mivel csak megengedett bázismegoldást akarunk keresni. Tegyük fel, hogy b ≥ 0. (Ha b-nek negatív komponensei lennének, a megfelel® sort (-1)-el kell szorozni.) A kib®vített feladat: (A, I)(x, u) = b, (x, u) ≥ 0. A feladat megengedett bázismegoldása: (x, u) = (0, b). Legyen a célfüggvény: min(0,1)T (x, u).
2.5. Megjegyzés. A kib®vített feladatban minden megengedett megoldáshoz nemnegatív célfüggvényérték tartozik, mivel (0,1) ≥ 0 és (x, u) ≥ 0. Ha van megengedett kezd®megoldásunk, alkalmazhatjuk a szimplex módszert. Mivel a célfüggvény korlátos ( nem javítható minden határon túl) - a szimplex módszer optimális megoldást fog találni. Két eset fordulhat el®:
• az optimális célfüggvényérték > 0 • az optimális célfüggyvényérték = 0 12
Tegyük fel, hogy az els® eset áll fenn. Ekkor:
2.3. Állítás. Az eredeti feladatnak nincs megengedett megoldása. Bizonyítás Indirekt Legyen x¯ megengedett megoldása az eredeti feladatnak. Ekkor (¯ x, 0) a kib®vített feladatnak olyan megengedett megoldása, amelynek 0 a célfüggvényértéke. Ez nyilvánvalóan ellentmondás, mivel az optimális célfüggvényérték pozitiv. Tegyük fel, hogy a második eset áll fenn. Ekkor a bázisunk kétféleképpen nézhet ki:
B Â
        Â
0
Â
Â
Â
A Â
u ...
Â
Â
     Â
0
?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??
vagy
u
B Â
Â
∅ Â
Â
??  ?? ??  ??  ?? ??  ??  ??? ??  ?? ??  ??  ?     Â
AÂ Â Â Â
Jelölje (x∗ , u∗ ) az optimális megoldást. Mivel (0,1)T (x∗ , u∗ ) = 0T x∗ +1T u∗ = ∅, így x∗ megengedett megoldása az eredeti feladatnak.
Implementációs megfontolások. Nézzük a következ® textilipari felada-
tot:
13
F onA F onB SzovA SzovB AllF on AllSzov b = 18 3 2 10 4 1 0 1 3 0 0 2 0 1 2 Jelöljük a kezdeti mátrixot A0 -val, a kezdeti jobboldalt pedig b0 -val. Végezzük el a következ® transzformációkat:
• Kerüljön SzovA a bázisba. A transzformált mátrixot jelöljük A1 -el, az új jobboldalt pedig b1 -el. ·
3 2 0 0 0 1
3 2 1 4
1 −5 1 0 2
·
¸ =
3
¸
3 2
Ez a transzformáció megfelel annak, hogy az A0 mátrixot balról az E1 mátrixszal beszorozzuk: · ¸ 1 −5 E1 = 1 0 2
·
1 −5 1 0 2
¸·
3 2 0 0 0 1
3 2 1 4
1 −5 1 0 2
¸
· =
3
¸
3 2
A1 = E1 A0 b1 = E1 b0 • Vigyük SzovB -t a bázisba. Az új mátrix legyen A2 , az új jobboldal legyen b2 , a transzformációs mátrix pedig E2 : ·
2 3 − 16
0 1
¸·
2 − 12
4 3 − 13
2 0 1 − 10 3 3 4 1 0 − 61 3
¸
· =
2 1
¸
A2 = E2 A1 b2 = E2 b1 A ritka mátrix nemnulla elemekkel való feltöltése illetve a numerikus hibák felhalmozódása ellen az implementációs trükk az eredeti mátrix és az E -mátrixok tárolása lesz. Ily módon egy adott oszlop transzformáltját 14
úgy kapjuk meg, hogy az eredeti oszlopot megszorozzuk a transzformációs mátrixszal.
A2 = E2 E1 A0 b2 = E2 E1 b0 A kérdés az, hogy meg lehet úgy oldani a szimplex módszer implementálását, hogy csak ezeket az adatokat tároljuk? Ha igen, az így kapott megoldás optimális lesz?
Javítóvektor keresése. Hasonlítsuk össze cTB A2 -t cT -al. Ha teljesül a ≥
reláció, akkor optimális megoldásunk van. Különben keressünk olyan indexet, ahol a komponensek között van < reláció. Hogyan számítható cTB A2 ?
cTB A2 = cTB (E2 E1 A1 ) = (cTB E2 E1 )A0 A javítóvektor kereséséhez elég az A0 , E2 , E1 , . . . mátrixok ismerete.
Általános eset. Tegyük fel, hogy a j -edik oszlopvektor javító. Ekkor szükségünk lesz az eredeti j oszlopvektor transzformált alakjára.
·
BK
A0
¸
E1 .. .
· EK
¸
I
£
cTBK
AK ¤
E K . . . E 1 BK = I | {z } −1 BK
A szimplex módszer így sokkal tömörebben tárolható - lényegében az E transzformációs mátrixnak is elég, ha csak egy-egy oszlopát tároljuk. 15
Hasonlítsuk tehát össze cTBK (EK EK−1 . . . E1 )A0 -t és a cT vektorokat. Ehhez | {z } −1 cTBK BK -et.
−1 BK
számítsuk ki: Ha találunk javítóvektort, akkor azt transzformálni −1 kell az új bázisba, azaz szorozzuk balról a BK = EK EK−1 . . . E1 mátrixszal.
2.3. De nició. Árnyékár vektor A cTBK BK−1 -et az adott bázishoz tartozó árnyékár vektornak nevezzük.
Az árnyékár vektor azt mutatja meg, hogy hogyan változik a célfüggvényérték ha a jobboldal változik.
3. Dualitás A feladatunk:
Ax = b x≥0 maxcT x , ahol A teljes sorrangú mátrix.
3.1. De nició. Megengedett bázis A B bázis megengedett, ha a hozzá tartozó bázismegoldás megengedett: xB = B −1 b ≥ 0.
3.2. De nició. Optimális bázis A B bázis optimális, ha megengedett és tel-
jesül a szimplex módszer megállási feltétele (azaz nincs javítóvektor): −1 cTB ≥ cT B | {z A} transzformált mátrix
cTB B −1 A ≥ cT | {z } árnyékár vektor
3.1. Jelölés. Jelöljük yBT = cTB B −1 a B bázishoz tartozó árnyékár vektort. 3.1. Megjegyzés. Ha van egy optimális bázismegoldásunk, akkor nem biz-
tos, hogy a bázis optimális - ilyen a degenerált feladat. (Azt tudjuk, hogy ha van egy optimális bázisunk, akkor a hozzá tartozó bázismegoldás optimális.)
3.3. De nició. Duál-megengedett bázis Egy B bázis duál-megengedett, ha a
hozzá tartozó árnyékár vektorra teljesül, hogy: yBT A ≥ cT .
3.1. Állítás. Ha egy bázis megengedett és duál-megengedett, akkor optimális. 16
Térjünk vissza a textilipari feladatra. O szöv®gép kapacitás
C ¤C¤ C ¤ ¤ C¤C ¤C¤ C ¤ C¤ ¤C¤ C ¤ ¤C¤C ¤C¤ C ¤ ¤C ¤C¤C ¤ C C¤ ¤C¤megengedett C ¤ C¤¤C tartomány ¤C¤ C ¤ ¤C -¤¤C C - m- m- mm ¤ C ¤ m ¤C - - mm -m-mm- mmm C¤¤C ¤ C ¤C¤ - - m- mmm - m-m-mmm ¤C¤C ¤ C¤C - - mm ¤C¤- - m- m- mmmm ¤ C ¤¤C- mmmm ¤m¤mm
/
fonógép kapacitás
Melyek azok a pontok, ahol ugyancsak (SzovA, SzovB) az optimális bázis? A jobboldalt változtatva csak a megengedettség változhat(romolhat). A megengedettség csak azokra a jobboldalakra marad meg, amelyekre teljesül a B −1 b ≥ 0 homogén lineáris egyenl®tlenségrendszer. Most nézzük ugyanezt a textilipari feladatot másik szempontból: A textilgyár ki akarja adni a fonó- és szöv®gépekre a gépid®t. Erre kell ajánlatokat beküldeni. Minden ajánlat a fonógépid®ért y1 pénzegységet ajánl, a szöv®gépid®ért pedig y2 pénzegységet. Tegyük fel, hogy az ajánlattev® a teljes gyártókapacitást meg szeretné szerezni. Teljesülnie kell tehát a következ®knek:
3y1 + 0y2 ≥ 8 , különben a tulajdonos azt mondaná, hogy inkább A fonalat gyárt.
2y1 + 0y2 ≥ 9 , különben a tulajdonos azt mondaná, hogy inkább B fonalat gyárt.
10y1 + 2y2 ≥ 50 , különben a tulajdonos azt mondaná, hogy inkább A szövetetgyárt.
1 4y1 + y2 ≥ 19 2 17
, különben a tulajdonos azt mondaná, hogy inkább B szövetet gyárt.
y1 ≥ 0 , különben a tulajdonos azt mondaná, hogy inkább áll a fonógép.
y2 ≥ 0 , különben a tulajdonos azt mondaná, hogy inkább áll a szöv®gép.
min(18y1 + 3y2 ) a teljes kapacitás bérleti díja.
3.2. Megjegyzés. Mindkét megfogalmazás ugyanazt a feladatot írja le, csak egyszer a gyártulajdonos szempontjából, egyszer pedig az ajánlattev® szempontjából. Az utóbbi feladatot az eredeti feladat duál feladatának nevezzük. Minden LP feladathoz felírható a párja - a duál feladat, ami ugyanazt írja le mint az eredeti LP feladat, csak más szemszögb®l.
Általánosan. Legyen a primál feladat a következ®: Ax = b (P ) x ≥ 0 maxcT x A (P ) feladatnak megfelel® duál feladat pedig:
AT y ≥ c (D) y− minbT y ,ami ekvivalens a következ®vel:
y T A ≥ cT y− miny T b
3.1. Tétel. Gyenge dualitási tétel Legyen x a (P ) feladatnak, és y a (D) feladatnak megengedett megoldása. Ekkor teljesül az, hogy cT x ≤ y T b
18
O
célfüggvényérték
(D) feladat megengedett megoldásai
optimális megoldás
• y
_ _ _ _ _ _ _+ _ _ _ _ _ _ _ _ _ _ _ _ _ _+ _ _ _ _ _ _
optimális megoldás
• x (P) feladat megengedett megoldásai
Bizonyítás Az y (D)-megengedettség miatt: y T A ≥ cT , azaz y T A − cT ≥ 0. Mivel x pedig (P )-megengedett, ezért x ≥ 0. Ekkor (y T A − cT )x ≥ 0, azaz y T |{z} Ax −cT x ≥ 0. Mivel x (P )-megengedett, emiatt y T b ≥ cT x, és kész a b
bizonyítás.
3.2. Tétel. Er®s dualitási tétel Tegyük fel, hogy mind a (P ) mind a (D) feladatnak van megengedett megoldása. Ekkor mindkett®nek van optimális megoldása is, és az optimális célfüggvényértékek megegyeznek.
Bizonyítás Oldjuk meg a (P ) feladatot szimplex módszerrel. • Ha nem állna rendelkezésünkre kezd® megengedett bázismegoldás, akkor az ismertetett els®fázissal tudunk ilyet keresni. Ez az eljárás is szimplex módszeren alapszik. Amint láttuk, a szimplex módszerrel a ki- és belép® vektorokat meg lehet úgy választani, hogy az eljárás véges sok lépésben leálljon. Mivel feltettük, hogy a (P ) feladatnak van megengedett megoldása, ezért az els® fázis megengedett kezd® bázismegoldással fog leállni. A megengedett kezd®bázis megoldásból kiindulva, szimplex módszerrel oldjuk meg a (P ) feladatot. A be- és kilép® vektorok megválaszthatók úgy, hogy az eljárás véges sok lépésben véget érjen. A szimplex módszer általában kétféleképpen érhet véget: 1. kiderül, hogy a célfüggvény minden határon túl növelhet® 2. optimális bázist kapunk 19
Az els® eset nem fordulhat el®, mert a (D) feladatnak a feltevésünk szerint van y megengedett megoldása, amihez tartozó célfüggvényérték fels® korlátja a (P ) feladat megengedett megoldásaihoz tartozó célfüggvényértékeknek a gyenge dualitási tétel miatt. Tehát a szimplex módszer a második eset szerint egy B ∗ optimális bázissal áll le. Jelölje x∗ a B ∗ bázishoz tartozó bázismegoldást.
£
0 ... 0
∗ y £
T
x∗B∗
B
0 ... 0
¤
b
∗
A
¤
cTB∗ x∗ ≥ 0 Ax∗ = b ⇐⇒ B ∗ x∗B∗ = b
Jelölje y ∗ a B ∗ bázishoz tartozó árnyékár vektort. Ekkor T
T
y ∗ B ∗ = cTB∗ ⇐⇒ y ∗ = cTB∗ B ∗ −1 Mivel B ∗ optimális bázis, teljesül a szimplex módszer megállási feltétele (azaz nincs javítóvektor): y ∗ T A ≥ cT . Tehát az optimális bázishoz tartozó y ∗ árnyékár vektor megengedett megoldása a (D) feladatnak.(x∗ pedig megoldása a (P ) feladatnak.) Megmutatjuk, hogy az x∗ vektorhoz tartozó (P ) célfüggvényérték megegyezik az y ∗ vektorhoz tartozó (D) célfüggvényértékkel: cT x∗ = cTB∗ x∗B∗ = (y ∗ T B ∗ )x∗B∗ = y ∗ T (B ∗ x∗B∗ ) = y ∗ T b | {z } b
3.2. Állítás. Tegyük fel, hogy a (P ) feladatnak van megengedett megoldása, de a (D) feladatnak nincs. Ekkor a (P ) feladat célfüggvényértéke minden határon túl javítható. Bizonyítás A bizonyítás menete az er®s dualitási tétel bizonyításához ha-
sonló. A (P ) feladatra alkalmazzuk a szimplex módszert. Meg lehet úgy választani a be- és kilép® vektorokat, hgoy véges sok lépésben leálljon. Általában két eset lehetséges: 20
1. kiderül, hogy nem korlátos a célfüggvény 2. optimális bázist találunk. A második eset nem fordulhat el®, mert az optimális bázishoz tartozó árnyékár vektor a (D) feladatban megengedett megoldás volna, ami a feltételezés szerint nem létezik. Marad az els® eset. Legyen most a feladatunk a következ® formájú:
Ax ≤ b (P ) x ≥ 0 maxcT x
£
xT
y £
¤
uT
A
b
I
cT
0 ... 0
¤
(A, I)(x, u) = b (P ) ≡ (P ) (x, u) ≥ 0 max(c, 0)T (x, u) 0
Írjuk fel (P 0 ) feladathoz tartozó duál feladatot:
y T (A, I) ≥ (c, 0)T (D0 ) y− ≡ miny T b
y T A ≥ cT yT ≥ 0 miny T b
Tehát
Ax ≤ b y T A ≥ cT AT y ≥ c (P ) x ≥ 0 (D) y T ≥ 0 ≡ (D) y T ≥ 0 maxcT x miny T b minbT y 21
is.
A fenti gyenge és er®s dualitási tétel örökl®dik erre a (P )-(D) feladatpárra
Most megmutatjuk, hogy a (D) feladat duálisa a (P ) feladat(ekvivalens átalakításokkal).
AT y ≥ c y≥0 ≡ minbT y
AT y ≥ c (−A)T y ≤ (−c) y≥0 ≡ (P ) y ≥ 0 −max(−b)T y −max(−b)T y
Ennek a feladatnak írjuk fel a duálisát:
xT (−A) ≥ (−b) AT x ≤ b (D) x ≥ 0 ≡ (D) x ≥ 0 T −minx (−c) maxcT x
3.3. Állítás. A fenti szimmetrikus (P )-(D) feladatokra a következ® esetek
lehetségesek:
1. ha mindkett®nek van mgengedett megoldássa, akkor mindkett®nek van optimális megoldása, és az optimális célfüggvényértékek megegyeznek 2. ha a (P ) feladatnak van megengedett megoldása, de a (D) feladatnak nincs, akkor a (P ) célfüggvényérték minden határon túl javítható 3. ha a (D) feladatnak van megengedett megoldása, de a (P ) feladatnak nincs, akkor a (D) célfüggvényérték minden határon túl javítható 4. el®fordulhat, hogy sem a (P ), sem a (D) feladatnak nincs megengedett megoldása. Hogyan kezeljük az olyan feladatokat, amelyeknél nincs megkötés a változókra? Nézzük például az alábbi feladatot: (I) Ax ≤ b, maxcT x
£ £
¤
xT
≤ b
A
¤
cT
22
Alakítsuk át a feladatot úgy, hogy a változókra nemnegativitási feltételünk legyen. Legyen x = x+ − x− , x+ , x− ≥ 0. Ekkor a feladat az alábbi alakban írható fel:
£
x+
£
¤
x−
A
−A
cT
−cT
≤ b ¤
(II) (A, −A)(x+ , x− ) ≤ b (x+ , x− ) ≥ 0 max(c, −c)T (x+ , x− ) Mennyire ekvivalens ez a feladat az el®z®vel?
3.4. Állítás. Ha (x+ , x− ) a (II) feladat megengedett megoldása, akkor x+ −
x− az (I) feladat megengedett megoldása és a megfelel® célfüggvény értékek azonosak.
Bizonyítás (c, −c)T (x+ , x− ) = cT x+ − cT x− = cT (x+ − x− ) 3.5. Állítás. Ha x az (I) feladat megengedett megoldása, akkor x+ = [x]+ , x− = [x]− választással (x+ , x− ) a (II) feladat megengedett megoldása. Írjuk fel a (II) feladat duálisát:
y £
A
−A
cT
−cT
≤ b ¤
y T a ≥ cT és y T (−A) ≥ (−c)T {z } | y T (A, −A) ≥ (c, −c)T y T A=cT y≥0 Ã y≥0 T −miny b miny T b
23
Láthattuk tehát, hogy ha a primál feladatban egyenl®ség van, akkor a duál feladatban nincs nemnegativitási feltétel a változóra és fordítva, ha a primál feladatban van nemnegativitási feltétel, akkor a duál feladatban egyenl®tlenség van. Most nézzük meg, hogy lehet (viszonylag) automatikusan felírni egy feladat duálisát: 0≤ − ¤ £ xT2 xT1
− y 1 0≤ y2
£
A11
A12
A21
A22
≥
=
cT1
cT2
= b1 ≤ b2
¤
A11 x1 + A12 x2 = b1 y1T A11 + y2T A21 ≥ cT1 A21 x1 + A22 x2 ≤ b2 y1T A12 + y2T A22 = cT2 (P ) x1 ≥ 0 (D) y1 − x2 − y2 ≥ 0 T T maxc1 x1 + c2 x2 miny1T b1 + y2T b2
4. Farkas lemma 4.1. Lemma. Az alábbi egyenl®tlenségrendszerek közül pontosan az egyik megoldható:
(I) Ax = b (II) y T A ≥ 0 x≥0 yT b < 0
Bizonyítás Könnyen látható, hogy egyszerre nem oldhatók meg: x = y T (Ax) = y T b < 0 0 ≤ (y T A) |{z} | {z } ≥0
≥0
24
Írjuk fel a (I) feladatot a következ® ekvivalens formába, és írjuk fel a hozzá tartozó duál feladatot:
yT A ≥ 0 Ax = b (P ) x ≥ 0 (D) y− T max0 x miny T b A fenti (D) feladatnak az y = (0, . . . , 0) vektor mindig megengedett megoldása. A dualitási tételben felsorolt négy eset közül kett® következhet csak be:
• Ha a (P ) feladatnak van megengedett megoldása, akkor van optimális megoldása is, és az optimális célfüggvényérték 0, mivel minden primál célfüggvényérték 0. Ekkor a (D) feladat célfüggvényértéke nem csökkenthet® 0 alá, azaz y T b ≥ 0 minden megengedett megoldásra (azaz minden olyan y -ra, amire y T a ≥ 0). Tehát a (II) feladat nem megoldható, miközben az (I) feladat megoldható.
• Ha a (P ) feladatnak nincs megengedett megoldása, azaz (I) nem megoldható, akkor a dualitási tételb®l következik, hogy a duál célfüggvényérték minden határon túl csökkenthet® ( nevezetesen 0 alá is). Tehát a (II) feladat megoldható, miközben az (I) feladat nem megoldható.
Szemléltetés - szeparációs tétel.
A a1 a2
...
an = b
Az, hogy (I) megoldható, azt jelenti, hogy b el®állítható az ai -kb®l nemnegatív súlyokkal, azaz b ∈ Cone(a1 , . . . , an ). O a1
: tt a2 tt t t tt tt t YtJtJYYYYY JJ YYYYYY JJ YYYYYY JJ Y, JJ b JJ J$ a n
25
y a1 a2
...
an b
Az, hogy (II) megoldható, azt jelenti, hogy az y minden ai vektorral hegyes szöget zár be. Azaz az y -ra mer®leges altérnek az összes ai az y oldalán van, a b viszont a hipersík másik oldalán lesz. O a1
? t: a ÄÄ?? tt 2 ? t ÄÄ?? tt ÄÄ?? tt t t ? ÄÄ? tt IJÄ?tYJ?JY?JYYYYYY Y ²² ² ÄÄ?J?J?JJ YYYYYYYYYY Ä , y J ? ² ÄÄ? JJ ²² ² ÄÄ??? JJJ ² ÄÄ?? $ an ²² ² ÄÄ ¨²
b
5. Hálózati folyam feladat Nézzük meg a következ® feladatot. Van
• egy termel® (1), aki 1 egységnyi olajat termel • egy fogyasztó (4), aki 1 egységnyi olajat fogyaszt • két csomópont (2), (3) És van egy cs®rendszer, ami továbbítja az olajat. A továbbítási költséget 1 egységnyi olajra tekintjük. A cs® kapacitása nem lehet korlátolt.
(2) 7O ooo OOOOO o o OOO oo OOO ooo 10 o1 OOO o o o OO'7 o (1)oOoOOOO 1 oo(4) o o OOO o o o OO oo ooo 1 10 OOOOO OO'²ooooo (3)
26
Milyen útvonalon lehet a legolcsóbban továbbítani az olajat a termel®t®l a fogyasztóig? A fenti feladat felírható LP feladatként: A döntési változók: az egyes éleken továbbítandó olajmennyiség. A korlátozó feltételek: az egyes csúcsok egyenlegeire(be- és kifolyó olaj egyenlege) vonatkoznak.
£
x12 x13 x23 x24 x34
¤
−1 −1 −1 amit megtermel, azt elszállítja 1 0 ami bejön, az kimegy −1 −1 = 1 1 −1 0 ami bejön, az kimegy 1 1 1 minden bejöv®t elfogyaszt ¤ £ 1 10 1 10 1 További feltétel: a változók nemnegatívak. A mátrix speciális szerkezet¶: minden oszlopban csak egy 1-es és egy −1-es van. Ha erre a feladatra szeretnénk a szimplex módszert alkalmazni, nem lehetne, hiszen a mátrix nem teljes sorrangú (ha összeadjuk a sorokat, 0-át kapunk eredményül). Javítsunk: vezessünk be egy mesterséges élt, ami a termel®b®l vezetne ki, de az él súlya legyen 0.
0 o
(2) oo7OOOOO o o OOO ooo OOO ooo 1 10 OOO o o OOO (1) oooo '7 oOOO o(4) 1 OOO ooo o OOO o O ooo ooo 1 10 OOOOO o o OO'²ooo (3)
£
x1. x12 x13 x23 x24 x34
¤
−1 −1 −1 −1 0 1 −1 −1 = 1 1 −1 0 1 1 1 £ ¤ 0 1 10 1 10 1 A fenti feladat megoldható szimplex módszerrel. De mivel ez egy speciális feladat - a szimplex módszer is szemléletes - a módszer lépései a gráfon követhet®ek. Nézzük meg el®ször, hogy mi a kapcsolat a két megközelítés között: 27
(i) élek ←→ oszlopvektorok (ii) élek halmaza ←→ oszlopok halmaza (iii) élek olyan halmaza, ami tartalmaz irányított kört ←→ oszlopok lineárisan összefügg® halmaza
Bizonyítás Nézzünk el®ször egy irányított kört: B2 ¦¦ ¦ ¦ ¦¦ ¦ 1 hR¦RRRRR RRR R
/ 3 55 55 55 55 5 l½ l ll 4 l l ll 5 lv l
Ekkor az oszlopvektorok felírhatók a következ®képpen: −1 1 1 −1 1 −1 . . .
−1 Az oszlopokat összeadva 0-t kapunk. Ha valamelyik él visszafele van irányítva, akkor a megfelel® oszlopvektor (−1)-szeresét kell venni az oszlopok összegzésénél. (iv) élek olyan halmaza, amely nem tartalmaz irányítatlan kört ←→ lineárisan független oszlopok halmaza
Bizonyítás Teljes indukció. Olyan élek halmaza, amely nem tartal-
maz irányítatlan kört irányítatlan erd®t alkot. Tudjuk, hogy egy fának mindig van 1 fokú pontja. Legyen ez a pont i. Mivel i 1-fokú, ezért pontosan egy él illeszkedik rá. Ez az él lehet (j, i) vagy (i, j). Szimmetria okok miatt maradjunk az (i, j) jelölésnél. Nézzük meg azon oszlopok halmazát, amelyek az adott élhalmazhoz tartoznak:
(i, j)
i 0 . . . 0 ±1 0 . . . 0 ∓1 j
28
Ha a kijelölt oszlopok lineáris kombinációjaként a 0 vektort el®állítjuk, akkor az (i, j) oszlophoz 0 súly tartozik. Ha ehhez az oszlophoz 0 súly tartozik, akkor ezt az oszlopot elhagyhatjuk, vele együtt a gráfból is a hozzá tartozó élt. Így újabb 1 fokú csúcs keletkezik. Indukcióval könnyen belátható, hogy minden súly 0 kell, hogy legyen. (v) bázis (oszlopok olyan rendszere, ami lineárisan független, és erre a tulajdonságra nézve maximális - azaz bármely más vektort hozzávéve a rendszer már lineárisan összefügg® lesz) ←→ feszít®fa. Ä ÄÄ Ä Ä ÄÄ G²Ä?ÄÄ? ? ²² ??? ?? ²²² ? ²² ²² ²² /²/² // // gggggOOOOO /W/dsgº gggggggg OO: //d$ d$ tt tt // d$ d$ t tt // d$ d$ d$ tdJttt JJ JJ JJ JJ JJ
El®fordulhat, hogy van olyan csúcs, amibe a gyökérb®l nem lehetne eljutnia kijelölt éleken keresztül? - Ha a gráf összefügg®, akkor minden élhez eljuthatunk. A fenti gráf tulajdonságai (a) a gyökérb®l minden csúcs elérhet® irányítatlan úton, és az az út egyértelm¶ (b) ha egy küls® élt hozzáveszünk a kijelölt élek halmazához, akkor pontosan egy kört kapunk Most nézzük meg, hogyan követhet®ek a szimplex módszer lépései a gráfon. Tegyük fel, hogy van egy kezdeti bázisunk.
29
c1,2
c1,2 + c2,4
2 ®/ 4 === == = O ® z z == z ® == zz z ® == ® c1,. = 0 zzzz == z ® == zz = @Á 6 z ® 1 == ® == ® == == ® == ® == == ¦® / 5 Á 3 o
c1,3
c1,2 + c2,4 + c4,6
c1,3 + c3,5
Legyen a bázisunk: x1,. , x1,2 , x2,4 , x4,6 , x1,3 , x3,5 . Írjuk fel a bázishoz tartozó y árnyékár vektort (y T B = cTB ). Értelmezése: a lehetséges szállítási útvonalakon belül van egy hivatalos útvonal - ezekhez a szállítási útvonalakhoz vannak az egyes városokban az olajárak igazítva.
£
y 0
c1,2 c + c2,4 1,2 c1,2 + c2,4 + c4,6 c1,3 c1,3 + c3,5
xT x1,. x1,2 x2,4 x4,6 x1,3 x3,5 x4,3 x5,4 x5,6
−1 −1 1
£
= =
−1
B
−1 1 −1 1
...
= >
1 ...
c1,. c1,2 c2,4 c4,6 c1,3 c3,5 c4,3 c5,4 c5,6
>
¤
Mikor lesz egy ap oszlop javítóoszlop? - ha y T ap > cp . Speciálisan: mikor lesz a (4, 3) oszlop javító? - ha −y4 + y3 > c4,3 , azaz y3 > y4 + c4,3 . Azaz a 3 városbeli hivatalos olajár kisebb, mint a 4 városbeli hivatalos olajár + a szállítási költség a 4 városból a 3 városba. Legyen a (4, 3) él javítóél. Nézzük a szimplex módszert. Ha a (4, 3) élt hozzávesszük a feszít®fához, akkor pontosan egy kör keletkezik. Vegyünk egy h vektort, amelyben a (4, 3) élnél 1 érték van, minden nem körbeli él esetében 0 érték van, és minden körbeli él esetében: ha az él irányítása megfelel a kör körüljárási iránynak, amit az új él irányítása határoz meg, akkor 1 érték, különben −1 érték van. 30
= b
−1 1 −1 1
¤
x1,. x1,2 x2,4 x4,6 x1,3 x3,5 x4,3 x5,4 x5,6 hT [0 1 1 0 −1 0 1 0 0] Tudjuk, hogy Ah = 0, Ax = b, tehát A(x + ϑh) = b h-ból látható, hogyan kell az x-eket megváltoztatni, hogy az egyenl®ség megmaradjon.
x1,. x1,2 x2,4 x4,6 x1,3 x3,5 x4,3 x5,4 x5,6 (x + ϑh)T [x1,. + 0 x1,2 + ϑ x2,4 + ϑ x4,6 + 0 x1,3 − ϑ x3,5 + 0 x4,3 +ϑ 0 0] |{z} =0
Így az egyenleg sehol sem fog változni, miközben a szállítási költség csökken. Meddig növelhetjük ϑ-t? - amíg az egyik változó nem fog 0 alá csökkenni.
Általános eset. Ha nem lenne olyan él, ami 0 alá csökkenthet®, akkor a
célfüggvény minden határon túl növelhet®, ami azt jelenti, hogy az eredeti gráfban van olyan kör, amelyben a szállítási költségek összege negatív. Ha találunk egy javítóélt, akkor azt hozzávesszük a bázishoz. Így keletkezik egy kör. A keletkezett kör mentén a folyamértékeket változtatjuk az új él irányításának megfelel®en. Ennek hatására minden pont egyensúlya változatlan. Mivel az hozzávett él javító volt, a szállítási költség csökkenni fog. Ha a ϑ növeléssel valamelyik él 0 lesz, akkor azt az élt elhagyjuk a bázisból. Két eset lehetséges:
• a célfüggvény minden határon túl növelhet® • valamelyik régi bázisélen a folyam 0-vá válik. Ebben az esetben báziscserét hajtunk végre: az új (javító)élt a bázisba vesszük, és egy 0vá vált élt kiveszünk. Könny¶ meggondolni, hogy így továbbra is bázisunk(feszít®fánk) lesz - és folytathatjuk a szimplex módszert. Tekintsük a következ® feladatot:
o
0
1
/ 4 == == == ®® O z 3 ® z == 33 ® ® == 10 1zzzz 10 1 3 ® 33 ®® == zz z == 33 ®® z z =@Á z 3®3® 1 =z== 10 10 ® 33 ¢¢ 6 ® == ¢ ® 33 ¢ == ¢¢ 33 ®® == ¢ ® 33 ® ¢¢ 10 === 33 ®® ¢¢ 1 ® == ¢ ¼ ¦® ¢ =Á / 5 ¢¢ 3
23 z= O 33
1
31
Legyen 1 a forrás, ami 1 egységet termel, 6 a nyel®, ami 1 egységet fogyaszt. Az élek kapacitása legyen ∞. Nézzünk egy kezd® megengedett bázismegoldást - ez a gráfban egy feszít®fa lesz, azonfelül pedig út is. Az éleken jelöljük a folyamértéket (mennyit szállítunk), a csúcsokon pedig a szállítási költségeket.
40 === == O 33 O == 33 ==1 331 == 33 == 33 == 33 = Á 50 0 == 1 1 3 33 == == 33 == 33 33 1 === 3¼ == =Á 10 30 20 3
0 o
Keressünk egy javítóélt: legyen ez az 1 → 2 él.
40 === == O O 33 == 33 ==1 331 ϑ == 33 == 33 == 33 Á 50 1−ϑ 0 === 1 33 == 33 == 33 == 33 1 − ϑ === 33 == ¼ =Á 10 30 =
0 o
20 3
Vegyük észre, hogy ϑ 1-ig növelhet®. az új bázis:
13 z= O 33
zz
1zzzz
o
0
zz zz z z 0 z
0
−9 ϑ itt is 1-ig növelhet®. Az új bázis:
32
ϑ
/ 21 == == O == == =1 == == == Á 31 1−ϑ
33 133 − ϑ 33 33 33 33 33 33 33 33 ¼
11
1
1
0 o
/ 2 == == O == == 1==− ϑ == == =@Á 0−ϑ 12
= O zz z 1 zzz zz z zz zz z 0 0
ϑ −9 −8 Jelen esetben ϑ-t nem növelhetjük 0-n túl, degenerált lépést hajtunk végre. Az új bázis: 1−ϑ / 2 === =
1
0 o
0
z= O zz z 1zzz zz z zz zz
0−ϑ
−9
ϑ Újabb degenerált lépés: ϑ = 0. Az új bázis:
o
0
= zz zz z 1zz zz z z zz 0 z
1
1
10
¦
Itt már ϑ 1-ig növelhet®, az új bázis:
33
== == 1==− ϑ == == =@Á ¢¢ 12 ¢ ¢ ¢¢ ¢ ¢¢ ¢¢ 0 + ϑ ¢ ¢ / 11 ¢¢
/ 2 == == == == 1==− ϑ == == ϑ =@Á ¢ 12 ¢ ¢ ¢ ¢¢ ¢¢ ¢ ¢0 + ϑ ¢¢ ¢ / 11 ¢¢
0+ϑ
o
= zz z 1 zzz zz z zz zz z 0
0
1
/ 2 ® ®® ® ® 1 ®® ® ® ®® 1 @ ® ® ¢¢ 5 ® ¢ ® ¢¢ ®® ¢¢ ® ¢ ® ¢ ®® ¢¢ 1 ® ¢ ¢ ®¦ / 4 ¢¢ 3
1
1 Itt már nem találunk javítóélt, így ez az optimális megoldás.
5.1. Megjegyzés. A fenti módszer a szimplex módszer egy specializálása: itt nem kell osztani vagy szorozni, csak összeadni és kivonni. Így, ha a kiindulási értékek egészek, és van optimális megoldás, akkor az optimális megoldás is egészérték¶ lesz, mivel sehol sem kell osztani. Most nézzünk egy olyan feladatot, ahol vannak élkapacitások:
o 0
2 Ä? O ??? Ä ?? ÄÄ ?? ÄÄ ??10 Ä 2ÄÄ ?? Ä ?? ÄÄ ?? Ä Äkap = 1 ?? Ä Ä Ä Â 1? 4 10 ? ?? Ä Ä ?? ÄÄ ?? ÄÄ ?? Ä ?? ÄÄ ÄÄ 1 10 ??? Ä ?? ÄÄ ? ÄÄÄ 3
Legyen 1 a termel®, ami 2 egységet termel, 4 a fogyasztó, ami 2 egységet fogyaszt, és az 1 → 2 él kapacitása legyen 1.
5.2. Megjegyzés. A fenti feladat megoldható úgy is, hogy felírjuk az általános szimplex változatot, és azt specializáljuk, de az nehézkes - helyette kezeljük a fels® korlátot. Nézzük a kezdeti bázist:
34
O ?? ? 20 ?? ?? ?? ??2 ?? ?? ?? ?Â
ϑ o 0
0? ?
?? ?? ?? ?? 2 − ϑ???? ?? ?Â
2−ϑ
30
10 ϑ itt 2-ig növelhet® lenne, de a fels® korlát miatt csak 1-ig növelhet®. Így az új bázis: 20 Ä? O ??? ?? ?? Ä Ä 2???− ϑ 1Ä ?? Ä ?? Ä ?? Ä ?Â Ä 1 − ϑ 0? ? 30 ?? ?? ?? ?? ?? 1 ??? ϑ ?? ? Ä
o 0
10
ϑ 1-ig növelhet®.
o 0
1 Ä? ??? ?? Ä ?? Ä 1???− ϑ 1 −Ä Äϑ ?? Ä ?? Ä ?? Ä ?Â Ä 0? 11 ?? Ä? Ä ?? ÄÄ ?? ÄÄ ?? Ä ? ÄÄ Ä1Ä + ϑ 1 + ϑ???? Ä ?? ÄÄ ? ÄÄÄ
10 Itt a fels® korlátos élnél csökkenteni kell a folyamértékeket. ϑ 1-ig növelhet®. 35
1? ?
o
0
0? ?
?? ?? ?? ?? ? 2 ??? ?? ?Â
10
?? ?? ?? ??0 ?? ?? ?? ? ? 11 ÄÄ Ä ÄÄ ÄÄ Ä Ä ÄÄ 2 Ä Ä ÄÄ ÄÄ
5.3. Megjegyzés. Osztani, szorozni ebben az esetben sem kell. 5.4. Megjegyzés. Ha vannak kezdeti kapacitáskorlátok, nem könny¶ kezdeti
bázist találni. A kezdeti bázis keresése hasonló a szimplex módszernél ismertetett els® fázis módszerhez. Írjunk fel egy új feladatot: tekintsünk el a továbbítási költségekt®l(legyenek a továbbítási költségek 0-k), és vezessünk be egy új mesterséges élt a forrásból a nyel®be. Ennek a kapacitása legyen nagyobb, mint a továbbítandó olaj mennyisége. Így keressünk minimális továbbítási költséget. A kib®vített feladatra már könny¶ kezd®bázist találni.
• ha a továbbítási költséget le lehet 0-ra csökkenteni, akkor kezd®bázist találtunk. • ha nem, akkor az eredeti feladatnak nincs megengedett megoldása. 0
TJ/ TT 0 ·· TTTTTTT · ?*L ? o 0·· ooo ¼¼ ??? o · o ¼ ?Zo? Z Z Z ??0 Z Z Z Z ··· ?? ?? 0 ¼¼ ?? ·· Z Z Z Z Z ¼¼ ? Z ?? ¼ Z Z Z Z??Z? ¼¼ ?? ··· 1 oÂ7, ¼ · ooo 0 ??? o ¼ · o o ?? · ¼¼ oooo0 ??·· ·Â /o¼¼ oo o7
0oooooo
0
5.5. Megjegyzés. Ha több forrás vagy nyel® van, akkor vezessünk be egy új
forrást, és egy új nyel®t a következ®képpen:
36
fogyasztók
termel®k tD ªª 1
...
ª ªª ª kap = t1ªª ... ª ªª ª ª ªª ª ª YYY = ti s YBªBYBYkap BB YYYYYt, i BB .. BB BB . kap = tn BB B!
..
f1 ===
== == == kap = f 1 == .. == . == == == = fj kap = fj uuu/:Á t u u uu uu u .. . uuuuu kap = fm fmuu
.
... tn Legyen a mesterséges éleken a továbbítási költség 0. Ekkor az új feladat megoldása megfelel az eredeti feladat megoldásának. A célfüggvény értéke is megfelel az eredeti feladat célfüggvényértékének.
6. Speciális esetek hálózati folyam feladatra 6.1. Szállítási feladat Vannak termel®k, fogyasztók, útvonalhálózat, de nincsenek csomópontok. fogyasztók
termel®k t1
/: uuf1 uu u u uu .. uu u . .. uu uu . u u u uu u u uu a0 uu u aaaaaaaaaaaaaa fj t.i]auu]a]a]a]a]a]a]a]a]]]]]]]]]]]]]]] . .
.
.. . /fm
tn
6.2. Hozzárendelési feladat Vannak feladatok, és vannak vállalkozók. Minden vállalkozónak pontosan egy feladatot kell kapnia. Minden vállalkozó rendelkezésre bocsát egy listát, hogy milyen feladatokra vállalkozik, és azokat milyen összegért végezné el. Adott tehát egy (n x n)-es táblázat: a sorokban a feladatok, az oszlopokban a vállalkozók találhatók. Legyen a táblázat egy eleme cij az a költség, amiért a j . vállalkozó az i. feladatot elvállalja. Keressük a maximális párosítást. 37
Mivel az eljárás egészérték¶ optimális megoldást ad, a feladat visszavezethet® a szállítási feladatra. Legyenek a vállalkozók a termel®k, a fogyasztók pedig a feladatok. Minden ti -b®l fj -be vezet® él kapacitása legyen 1, és legyen a folyamérték cij . Mit®l lesz a két feladat ekvivalens? - Mivel egy-egy termel®nél maximálisan 1 lehet a termelés, lesz egy kijelölt él, ahol a folyamérték 1, a többi folyamérték pedig 0. - A fogyasztóknál ugyanez mondható el. A feladat a Magyar módszerrel oldható meg hatékonyan (lásd a [8] fejezetet).
6.3. Párosítási feladat Bált szervezünk. Vannak úk, és vannak lányok, akik részt vesznek a bálon. Adott, hogy ki kivel hajlandó táncolni. Célunk az, hogy minél többen táncoljanak - ha lehet, teljes párosítást keresünk, ha nem, maximális párosítást. A feladat a König-Egerváry eljárással oldható meg hatékonyan (lásd a [7] fejezetet).
7. König-Egerváry eljárás A König-Egerváry eljárás a párosítási feladatra nyújt megoldómódszert. A párosítási feladatot szemléltethetjük gráal vagy mátrixszal.
aF b
c
1
3
a b c 1 x x x 2 x x 3
 ½ FFF©© ©©Â © © F ½ ©© FF ©©  ½ ©© ©©FFFF © © ½© ©
2
7.1. De nició (Független élrendszer). Bármely két kiválasztott élnek nincs közös végpontja (nincs két olyan x, ami azonos sorban vagy oszlopban van).
Keressük a maximális független élrendszert (a maximális független x-ek rendszerét).
7.2. De nició (Lefogó pontrendszer). Pontok olyan halmaza, amelyhez bármely élnek legalább az egyik végpontja hozzátartozik. Keressük a minimális lefogó pontrendszert. 38
7.3. De nició (Lefogó vonalrendszer). Minden x rajta van egy kiválasztott vonalon.
7.1. Megjegyzés. Könnyen látható, hogy tetsz®leges független rendszer elemszáma kisebb tetsz®leges lefogó pontrendszer elemszámánál.
Algoritmus 0. lépés Amíg lehet, valamiképpen párosítunk. Alaplépés Keressünk alternáló utat. Az alternáló út mentén változtassuk meg a kiválasztottságot(a kiválasztott élek legyenek kiválasztatlanok, a nem kiválasztottak pedig legyenek kiválasztottak). A kapott független élrendszer elemszáma eggyel nagyobb, mint az eredetié. 7.4. De nició (Alternáló út). Párosítatlan fels® halmazbeli pontot összeköt
egy párosítatlan alsó halmazbeli ponttal.
7.2. Megjegyzés. Alternáló út nem kezd®dhet és nem végz®dhet kiválasztott éllel (azaz a nem kiválasztott élek száma 1-el nagyobb, mint a kiválasztottaké). Nézzük a következ® példát:
•OOOO
o• Ä• ÄÄ• OOO ÄÄ ooo Ä o o Ä Ä OÄO Ä oo ÄÄ OOOOO ÄÄÄ ooooo Ä O o ÄÄ ÄÄOOoo ÄÄ ÄoÄoooOOOOO Ä Ä o •Ä •Äo • •
Keressünk egy párosítást:
•
•
•
•
•
•
•
•
•O O Ä• Ä• O O Ä Ä Ä ÄO O Ä O OÄ Ä Ä Ä O O Ä O• Ä Ä • •
•
Keressünk egy alternáló utat:
Módosítsuk a kijelöltséget: 39
•
•OÂ OOO
Ä•Â Ä• OOO ÄÄ Â ÄÄ Ä OÄÄOO Ä Â ÄÄ OOÂ OO ÄÄÄ Ä O Ä Ä Â ÄOOO Â Ä Ä Ä OOO Â ÄÄ ÂÄÄÄ O• • •Ä
•
Â
•
Kaptunk egy eggyel nagyobb párosítást.
7.1. Tétel (Gyenge dualitás tétel). Legyen F egy független élrendszer és L egy lefogó pontrendszer. Ekkor |F | ≤ |L |.
Bizonyítás •? ??
•Â??? Â Â Â Â
•
•Â ?? Â ?? Â ?? ?? Â ?? ?Â
Ä• ?? ÄÄ Ä ?? ÄÄ Â Ä? Â ÄÄÄ ??? ?? Ä Â ÄÄ ? •Ä •
•Â
Ä• ÄÄ Ä Ä Â ÄÄ Ä Â ÄÄ Ä Â ÄÄ •Ä •
Â
•
Â
...
A szaggatott élek függetlenek (F ). Az F -beli élek mindegyikének lefogásához egy-egy külön lefogó pontra van szükségünk. Ezzel kész is a bizonyítás. Nézzük meg az er®s dualitást.
7.2. Tétel (Er®s dualitás tétel). Legyen F ∗ egy maximális elemszámú független
élrendszer, és legyen L ∗ egy minimális elemszámú lefogó pontrendszer. Ekkor |F ∗ | = |L ∗ |. Továbbá
7.3. Tétel. Adott egy F független élrendszer. Ha nincs alternáló út a párosítatlan fels® pontokból a párosítatlan alsó pontokba, akkor F maximális. A fenti két tételt egyszerre bizonyítjuk:
Bizonyítás Ha F olyan, mint a második tételben megadott, akkor találni
fogunk olyan L lefogó pontrendszert, amelyre |L | = |F |. A gyenge dualitás tétel miatt ilyenkor F maximális, és L minimális - ez lesz a második tétel bizonyítása. Keressünk egy lefogó pontrendszert:
A •···•
•.
•
.
• .
.
.
¯ X
.
•
...
•
•
•
...
•
•
•
X
Y¯
Y
Legyen 40
...
•
...
•
•···• B
A a párosítatlan fels® pontok halmaza B a párosítatlan alsó pontok halmaza X azon alsó pontok halmaza, amelyek A-ból elérhet®k alternáló úton Y azon fels® pontok halmaza, amelyek A-ból nem érhet®k el alternáló úton
7.1. Állítás. X
S
Y lefogó pontrendszer.
Bizonyítás Csak meg kell nézni, hogy hol vannak még élek. Legyen ¯ az X -beli pontok párosítás menti fels® párjai X Y az Y -beli pontok párosítás menti alsó párjai
A-ból nem mehet él Y-ba, különben A-ból vezetne alternáló út Y -ba. A-ból nem mehet él B -ba, különben A-ból vezetne alternáló út B -be. X -b®l nem mehet él Y-ba, mert A → X alternáló utak meghosszabbíthatóak lennének Y -ba. Ezzel kész is a bizonyítás.
7.3. Megjegyzés. Az A-ból X -be vezet® alternáló utak keresése hatékonyan implementálható egyszer¶ b®vítéssel.
8. Magyar módszer Mint már említettük, a magyar módszer a hozzárendelési feladathoz ad megoldó algoritmust. Tekintsük tehát a hozzárendelési feladatot: adott n db munka, és ugyanennyi vállalkozó. A feladathoz tartozó n x n-es mátrixban cij jelenti azt, hogy a j . vállalkozó mennyiért végezné el az i. munkát. Továbbá tegyük fel, hogy minden vállalkozó minden munkára ajánlatot tesz - ezek mind pozitív egész számok. cij ≥ 0, cij ∈ Z, i = 1 . . . n, j = 1 . . . n. A hozzárendelési feladat ábrázolható páros gráal is. Ebben a páros gráfban keresünk minimális súlyú teljes párosítást.
8.1. Észrevétel. Legyen ε ∈ R, és legyen j ∈ 1 . . . n oszlopindex. Az eredetivel ekvivalens feladatot kapunk, ha a j . oszlop minden eleméb®l kivonunk ε-t.
41
Bizonyítás Eredeti feladat
Módosított feladat
j c1j
j c1j − ε
cnj
cnj − ε
A fenti ábrán a körök jelölik az egyes párosításokat. A párosításnak az felel meg, hogy minden sorban és minden oszlopban egyetlen kiválasztott elem lehet. Látjuk, hogy a két feladat megengedett megoldásai azonosak. Legyen az adott párosítás ára C az eredeti feladatban. Ekkor ugyanannak a párosításnak az ára a módosított feladatban C − ε lesz. (a j . oszlopban pontosan egy kiválasztott elem lesz mindkét feladatban.)
8.2. Észrevétel. Legyen ε ∈ R, és legyen j ∈ 1 . . . n sorindex. Az eredetivel ekvivalens feladatot kapunk, ha a j . sor minden eleméb®l kivonunk ε-t.
Bizonyítás A bizonyítás ugyanaz, mint az el®bbi észrevétel esetében. 8.1. De nició (0-kból álló független rendszer). A táblázatból úgy vannak kiválasztva 0-k, hogy semelyik kett® nincs azonos oszlopban vagy azonos sorban.
0
0 0 0 0
0 0
42
8.1. Megjegyzés. A 0-kból álló maximális független rendszer keresése megfelel a párosítási feladatnak, ahol a fels® pontok az oszlopok, az alsó pontok pedig a sorok, él pedig akkor van, ha az illet® sor/oszlop metszerben 0 van. A 0-k független rendszere megfelel az élek független rendszerének. 8.2. De nició (0-kból álló teljesen független rendszer). Ha minden sorban és minden oszlopban van kijelölt 0.
8.3. Észrevétel. Tegyük fel, hogy van a táblázatunkban 0-kból álló teljesen független rendszer. Ha ezen rendszer mentén párosítjuk össze a vállalkozókat a feladatokkal, akkor az optimális hozzárendelést kapjuk. Bizonyítás A fenti hozzárendelés költsége 0 lesz. A feltevésünk szerint min-
den cij nemnegatív, emiatt minden összerendelés költsége ≥ 0. Ekkor egy 0 költség¶ összerendelés optimális lesz. Tekintsük a táblázatbeli 0-kat. Két eset lehetséges: (i) van 0-kból álló teljesen független rendszer. Ekkor kész vagyunk, optimális megoldást kaptunk (lásd a harmadik észrevételt). (ii) találunk egy n-nél kisebb elemszámú lefogó vonalrendszert. A keresést König-Egerváry módszerével végezzük. Tudjuk, hogy a 0-kból álló maximális független rendszer elemszáma megegyezik a minimális lefogó vonalrendszer elemszámával.
Algoritmus Minden lefogó oszlop minden eleméhez adjunk ε-t(megengedett lépés lásd els® észrevétel). Minden lefogatlan sor minden eleméb®l vonjunk ki ε-t. A végeredmény: a duplán lefogott elemek n®nek ε-nal, míg a lefogatlan elemek csökkennek ε-nal. Válasszuk ε-nak a lefogatlan elemek minimumát.
8.1. Állítás. A fenti m¶velettel az elemek összege csökken. Bizonyítás l + k < n, tehát a csökkentett részben több mez® van, mint a
megnövelt részben. Tekintsük a következ® feladatot:
43
2 2 6 11 3 8 7 17 4 2 5 11 4 3 1 9 Vonjuk ki minden sorból a sorbeli legkisebb elemet: 0 0 6 11 0 5 4 14 2 0 3 9 3 2 0 8 Vonjuk ki minden oszlopból az oszlopbeli legkisebb elemet: 0 0 6 3 0 5 4 6 2 0 3 1 3 2 0 0 Nézzük meg, hogyan tudjuk lefedni az összes nullát a táblázatban: az els® két oszloppal és az utolsó sorral. Most minden lefedett oszlop elemeihez adjunk hozzá ε-t és minden lefedetlen sorból vonjunk ki ε-t: 0+ε-ε 0+ε-ε 6-ε 3-ε 0+ε-ε 5+ε-ε 4-ε 6-ε 2+ε-ε 0+ε-ε 3-ε 1-ε 3+ε 2+ε 0 0 A legnagyobb ε amit alkalmazhatunk: ε = 1. 0 0 5 2 0 5 3 5 2 0 2 0 4 3 0 0 Most viszont négy vonalat kell használnunk, hogy minden 0-t lefedjünk a táblázatban. Tehát a megoldásunk optimális. Olvassuk le a megoldást: a második sorban egyetlen nulla van, így a második munkát az els® vállalkozóra osztjuk; a harmadik oszlopban is egyetlen nulla van, így a harmadik vállalkozó kapja a negyedik munkát; mivel az els® vállalkozó már kapott munkát, így az els® munkát a második vállalkozó kapja meg; a megmaradt harmadik munkát pedig a negyedik vállalkozónak adjuk.
44
