Dualit´ as
Dualit´ asi t´ etelek
´ anos LP feladat Altal´
Oper´aci´okutat´as I. 2015/2016-2.
Szegedi Tudom´ anyegyetem Informatikai Tansz´ ekcsoport Sz´ am´ıt´ og´ epes Optimaliz´ al´ as Tansz´ ek
6. El˝ oad´as
Komplement´ aris lazas´ ag
Dualit´ as
´ anos LP feladat Altal´
Dualit´ asi t´ etelek
Komplement´ aris lazas´ ag
´ asi interpret´aci´o Araz´ Tekints¨ uk u ´jra az er˝oforr´as allok´aci´ os probl´em´at (vonat ´es katona gy´art´asa, fa ´es fest´ek kell) Max z = 3x1 x1 2x1
+2x2
[profit]
+x2 ≤ 80 [fa] +x2 ≤ 100 [fest´ek] x1 , x2 ≥ 0
Legyen egy egys´eg fa piaci ´ ara y1 ($), egy egys´eg fest´ek ´ara y2 ($). Mit tehet a gy´art´o? Eladhatja az er˝oforr´asait (fa, fest´ek) piaci ´aron Vehet tov´abbi f´at ´es fest´eket Gy´art a rendelkez´esre ´all´ o er˝ oforr´asokb´ ol ´es eladja a j´at´ekokat Mi a legjobb strat´egia (felt´eve, hogy mindent t´enyleg el tud adni)?
Dualit´ as
Dualit´ asi t´ etelek
´ anos LP feladat Altal´
Komplement´ aris lazas´ ag
´ asi interpret´aci´o Araz´
Ha eladja a k´eszlet´et 80y1 + 100y2 profitra tesz szert Ha egy katona (piaci) el˝ o´ all´ıt´ asi ´ ara kisebb, mint az elad´ asi ´ ara, azaz y1 + 2y2 < 3($) akkor a gy´art´o korl´ atlan hasznot el tud ´ erni. Mi´ ert? 1 db katona gy´art´asi k¨ olts´ege y1 + 2y2 =⇒ x1 db katona eset´en: x1 (y1 + 2y2 ) Mivel y1 + 2y2 < 3, legyen pl. y1 + 2y2 = 2.9$ (k¨olts´eg), az elad´asi ´ar pedig 3$ =⇒ 1db katona eset´en a profit 0.1$ =⇒ x1 db katona eset´en: 0.1x1 $ (ami tetsz˝olegesen nagy lehet)
Dualit´ as
Dualit´ asi t´ etelek
´ anos LP feladat Altal´
Komplement´ aris lazas´ ag
´ asi interpret´aci´o Araz´
Hasonl´oan megy a dolog a vonatokra is: Ha egy vonat (piaci) el˝ o´ all´ıt´ asi ´ ara kisebb, mint az elad´ asi ´ ara, azaz y1 + y2 < 2($) akkor a gy´art´o korl´ atlan hasznot el tud ´ erni. De hogyan m˝ uk¨odik a piac? A piac nem engedi, hogy a gy´ art´ o korl´ atlan haszonra tegyen szert. Ellenkez˝oleg, u ´gy ´all´ıtja be” az ´arakat, hogy a gy´art´o a lehet˝o legkisebb ” profitot realiz´alja.
Dualit´ as
´ anos LP feladat Altal´
Dualit´ asi t´ etelek
´ asi interpret´aci´o: a piac ´ar k´epz´ese Araz´
A piac a k¨ovetkez˝ o optimaliz´al´asi feladatot oldja meg”: ” Min 80y1 +100y2 y1 y1
+2y2 ≥ 3 [katon´ak] +y2 ≥ 2 [vonatok] y1 , y2 ≥ 0
Ezt h´ıvjuk az eredeti feladat du´ alis´ anak Az eredeti feladatot ez alapj´an prim´ al feladatnak h´ıvjuk.
Komplement´ aris lazas´ ag
Dualit´ as
´ anos LP feladat Altal´
Dualit´ asi t´ etelek
Prim´al-du´al feladatp´ar
A prim´ al feladat: Max z = 3x1 x1 2x1
+2x2 +x2 ≤ 80 +x2 ≤ 100 x1 , x2 ≥ 0
A du´ al feladat: Min 80y1 +100y2 y1 y1
+2y2 ≥ 3 +y2 ≥ 2 y1 , y2 ≥ 0
Komplement´ aris lazas´ ag
Dualit´ as
´ anos LP feladat Altal´
Dualit´ asi t´ etelek
Komplement´ aris lazas´ ag
Prim´al-du´al feladatp´ar A prim´ al-du´ al feladatp´ ar ´ altal´ anosan: n X
aij xj ≤ bi
i = 1, 2, . . . m
xj ≥ 0
j = 1, 2, . . . n
j=1
Prim´al feladat
max
n X
ci xi = z
i=1 m X
aij yi ≥ cj
j = 1, 2, . . . n
yi ≥ 0
i = 1, 2, . . . m
i=1
Du´al feladat
min
m X i=1
bi yi = w
Dualit´ as
´ anos LP feladat Altal´
Dualit´ asi t´ etelek
Prim´al-du´al feladatp´ar A prim´ al-du´ al feladatp´ ar ´ altal´ anosan, m´ atrix form´ aban: A prim´ al feladat: Max cT x Ax ≤ b x ≥ 0 A du´ al feladat: Min
bT y AT y ≥ c y ≥ 0
A du´al a (standard alak´ u) prim´ab´ ol egyszer˝ uen megkaphat´o: transzpon´aljuk A m´atrixot cser´elj¨ uk fel” b ´es c vektorok szerep´et ” cser´elj¨ uk az egyenl˝ otlens´egeket ≥-ra Max helyett Min feladat
Komplement´ aris lazas´ ag
Dualit´ as
´ anos LP feladat Altal´
Dualit´ asi t´ etelek
Komplement´ aris lazas´ ag
Gyenge dualit´as t´etel T´ etel. (Gyenge dualit´ as) Ha x = (x1 , . . . , xn ) lehets´eges megold´asa a prim´al feladatnak ´es y = (y1 , . . . , ym ) lehets´eges megold´asa a du´al feladatnak, akkor cT x ≤ bT y, azaz n X j=1
cj xj ≤
m X
bi yi .
i=1
Vagyis a du´alis feladat b´armely lehets´eges megold´asa fels˝o korl´atot ad a prim´al b´armely lehets´eges megold´as´ara (azaz az optim´alis megold´asra is). Bizony´ıt´ as. Egyszer˝ u helyettes´ıt´es becsl´essel: ! n n m m n m X X X X X X cj xj ≤ yi aij xj = xj aij yi ≤ bi yi , j=1
j=1
i=1
i=1
j=1
i=1
vagy m´atrixosan: cT x ≤ (AT y)T x = (y T A)x = y T (Ax) ≤ y T b = bT y
Dualit´ as
Dualit´ asi t´ etelek
´ anos LP feladat Altal´
Komplement´ aris lazas´ ag
Gyenge dualit´as
L´atjuk, hogy a korl´atoss´ag ´es a megoldhat´ os´ag nem f¨ uggetlenek egym´ast´ol Ha a prim´al nem korl´atos, akkor a du´alnak nincs lehets´eges megold´asa Hasonl´oan, ha a du´al nem korl´atos, akkor a prim´alnak nincs lehets´eges megold´asa Lehets´eges, hogy egyiknek sincs lehets´eges megold´asa De ha mindkett˝onek van, akkor mindkett˝ o korl´atos Tov´abb´a a prim´al ´es a du´al feladat egyidej˝ u optimalit´asa ellen˝orizhet˝o
Dualit´ as
Dualit´ asi t´ etelek
Prim´al-du´al esetek
´ anos LP feladat Altal´
Komplement´ aris lazas´ ag
Dualit´ as
´ anos LP feladat Altal´
Dualit´ asi t´ etelek
Komplement´ aris lazas´ ag
Er˝os dualit´as t´etel T´ etel. (Er˝ os dualit´ as) Ha x∗ = (x1 , . . . , xn ) egy optim´alis megold´asa a prim´al feladatnak ´es y ∗ = (y1 , . . . , ym ) optim´alis megold´asa a du´al feladatnak, akkor cT x = bT y, azaz n X j=1
cj xj =
m X
bi yi .
i=1
Tov´abb´a az is igaz, hogy y T (b − Ax) = 0 ´es xT (AT y − c) = 0. Egyszer˝ uen, ha valamely i-edik felt´ etel egyenlet nem ´ eles (azaz nincs egyenl˝os´eg) a prim´al optimumban, akkor a du´ al kapcsol´ od´ o yi v´ altoz´ o0 kell legyen. Visszafel´e, ha egy prim´al xi v´altoz´ o szigor´ uan pozit´ıv, akkor a kapcsol´od´o du´alis felt´etel egyenlet ´eles kell legyen. Ezt komplement´ aris lazas´ agnak h´ıvjuk.
Dualit´ as
Dualit´ asi t´ etelek
´ anos LP feladat Altal´
Komplement´ aris lazas´ ag
Er˝os dualit´as t´etel
A m´asodik r´esz bizony´ıt´ asa: 0 ≤ y T (b − Ax) = y T b − y T Ax = bT y − (AT y)T x ≤ bT y − cT x = 0, illetve 0 ≤ xT (AT y−c) = (y T A−cT )x = y T (Ax)−cT x ≤ y T b−cT x = bT y−cT x ≤ 0.
Dualit´ as
´ anos LP feladat Altal´
Dualit´ asi t´ etelek
Komplement´ aris lazas´ ag
Er˝os dualit´as t´etel A els˝o r´esz bizony´ıt´ as v´ azlata: P´ elda. Adott a k¨ovetkez˝ o prim´al feladat: x1 5x1 −x1 x1 max 4x1
− x2 + x2 + 2x2 , x2 + x2
− x3 + 3x3 + 3x3 , x3 + 5x3
+ + − , +
3x4 8x4 5x4 x4 3x4
≤ 1 ≤ 55 ≤ 3 ≥ 0 = z
A feladat megold´as´anak utols´ o sz´ ot´ara x4 x6 x2 z
= 5 − x1 = 1 + 5x1 = 14 − 2x1 = 29 − 2x1
− x3 + 9x3 − 4x3 − 2x3
− x5 + 21x5 − 5x5 − 11x5
− x7 + 11x7 − 3x7 − 6x7
Dualit´ as
Dualit´ asi t´ etelek
´ anos LP feladat Altal´
Komplement´ aris lazas´ ag
A du´alis feladat: y1 −y1 −y1 3y1 y1 min y1
+ 5y2 + y2 + 3y2 + 8y2 , y2 + 55y2
− + + − , +
y3 2y3 3y3 5y3 y3 3y3
≥ 4 ≥ 1 ≥ 5 ≥ 3 ≥ 0 = w
A du´alis egy optim´alis megold´asa: y ∗ = (11, 0, 6) A prim´al feladat utols´ o sz´ ot´ar´aban a mesters´eges v´altoz´ok c´elf¨ uggv´eny egy¨ utthat´oi: c5 = −11, c6 = 0, c7 = −6 (Mit vesz¨ unk ´eszre? )
Dualit´ as
Dualit´ asi t´ etelek
´ anos LP feladat Altal´
Komplement´ aris lazas´ ag
Er˝os dualit´as t´etel A gyenge dualit´asi t´etel miatt el´eg, P ha tal´alunk egy (y1∗ , y1∗ , y3∗ ) Polyan 4 3 ∗ du´al lehets´eges megold´ast, amelyre j=1 cj xj = i=1 bi yi∗ Az eredeti feladat utols´ o sz´ ot´ar´ab´ ol kiolvashat´o a du´alis feladat megold´asa. A p´eld´aban x4 x6 x2 z
= 5 − x1 = 1 + 5x1 = 14 − 2x1 = 29 − 2x1
− x3 − x5 + 9x3 + 21x5 − 4x3 − 5x5 − 2x3 −11x5
− + − +0x6
x7 11x7 3x7 −6x7
A du´alis v´altoz´ok az eredeti feladat mesters´eges v´altoz´oihoz rendelhet˝ok: x5 ←→ y1 , x6 ←→ y2 , x7 ←→ y3 ⇒ y1 = 11, y2 = 0, y3 = 6 Az ´altal´anos esetben az utols´ o sz´ ot´arhoz ´erve ezt kell sz´amol´assal ellen˝orizni az optimumok egyenl˝ os´eg´et.
Dualit´ as
Dualit´ asi t´ etelek
´ anos LP feladat Altal´
Komplement´ aris lazas´ ag
Dualit´asi t´etelb˝ol ad´od´o lehet˝os´egek
A dualit´ as fogalma rendk´ıv¨ ul hasznos, mert rugalmas hozz´ a´ all´ ast teszt lehet˝ ov´ e az LP feladatok megold´as´an´al. 1
A szimplex algoritmus iter´aci´ osz´ama k¨ ozel´ıt˝ oleg a sorok sz´am´aval ar´anyos −→ sok felt´etel, kev´es v´altoz´ o eset´en ´erdemes ´att´erni a du´alisra
2
Ha az els˝o esetben sz¨ uks´eg van 2 f´azisra, m´ıg a du´alisn´al nincs, ´erdemes ´att´erni
3
Ha menet k¨ozben kell u ´j felt´eteleket hozz´avenni az LP-hez −→ a du´al feladattal dolgozva az u ´j felt´etel csak egy u ´j, nemb´azis v´altoz´ok´ent jelenik meg → hozz´avessz¨ uk az aktu´alis sz´ ot´arhoz, ´es folytatjuk a feladatmegold´ast
Dualit´ as
Dualit´ asi t´ etelek
´ anos LP feladat Altal´
Komplement´ aris lazas´ ag
´ anos LP feladat Altal´
Mi a helyzet akkor, ha az LP feladatunk tartalmaz egyenl˝ os´ eget vagy nem korl´ atozott v´ altoz´ ot (ami felvehet negat´ıv ´ert´eket is)? A j´o h´ır, hogy ez kezelhet˝ o, ugyanis az egyenl˝ os´ eg felt´ etel egy nem korl´ atozott v´ altoz´ ohoz tartozik egy nem korl´atozott v´altoz´ o eset´en egy egyenl˝os´eg felt´etel kell legyen
Mi´ert? P´eld´aul tegy¨ uk fel, hogy x1 + x2 = 80 [fa] 3x1 + 2x2 ≤ 5x1 + 2x2 = (−1) (x1 + x2 ) +3 (2x1 + x2 ) ≤ | {z } | {z } =80
≤ −80 + 3 × 100 = 220$ Azaz y1 nem korl´atozott (itt −1).
≤100
Dualit´ as
Dualit´ asi t´ etelek
´ anos LP feladat Altal´
´ anos LP feladat Altal´
¨ Osszegezve: az ≥” felt´etel egy nem-pozit´ıv v´altoz´ ohoz tartozik ” nem-pozit´ıv v´altoz´ ohoz egy ≥” felt´etel tartozik ” Prim´al (Max) i-edik felt´etel ≤ i-edik felt´etel ≥ i-edik felt´etel = xi ≥ 0 xi ≤ 0 xi nem korl´atozott
Du´al (Min) yi ≥ 0 yi ≤ 0 yi nem korl´atozott i-edik felt´etel ≤ i-edik felt´etel ≥ i-edik felt´etel =
Komplement´ aris lazas´ ag
Dualit´ as
´ anos LP feladat Altal´
Dualit´ asi t´ etelek
Komplement´ aris lazas´ ag
´ anos LP feladat Altal´ P´ elda. Prim´al Max z = 3x1 + 2x2 x1 + x2 2x1 + x2 x1
+ x3 + 0.5x3 + x3 + x3 x1 x2 x3
≤ 80 = 100 ≥ 40 nem korl´atozott ≤0 ≥0
Du´al Min w =
80y1 y1 y1 0.5y1
+ 100y2 + 40y3 + 2y2 + y3 + y2 + y2 + y3 y1 y2 y3
=3 ≤2 ≥1 y1 ≥ 0 nem korl´atozott ≤0
Dualit´ as
Dualit´ asi t´ etelek
´ anos LP feladat Altal´
Komplement´ aris lazas´ ag
LP feladatok megoldhat´os´aga Inkonzisztencia: egyenletek ´es egyenl˝ otlens´egek egy m elem˝ u n X
aij xj ≤ bi
i∈I
aij xj = bi
i∈E
j=1 n X j=1
rendszere inkonzisztens, ha l´eteznek olyan y1 , y2 , . . . , ym val´os sz´amok, amelyekre teljes¨ ul, hogy m X
aij yi = 0
i=1 m X
j = 1, 2, . . . , n
bi yi < 0
i=1
yi ≥ 0
i∈I
Dualit´ as
Dualit´ asi t´ etelek
´ anos LP feladat Altal´
Komplement´ aris lazas´ ag
LP feladatok megoldhat´os´aga
Tucker lehetetlens´ egi t´ etele egyenlet ´es egyenl˝ otlens´eg rendszerekre: egyenletek ´es egyenl˝otlens´egek egy rendszere akkor ´ es csak akkor megoldhatatlan, ha inkonzisztens Nem bizony´ıtjuk A t´etel bizony´ıthat´ o a line´aris programoz´as alapt´etel´enek ´es az er˝os dualit´as t´etel´enek ´altal´anos LP feladatokra vonatkoz´o form´aj´ara t´amaszkodva
Dualit´ as
´ anos LP feladat Altal´
Dualit´ asi t´ etelek
Komplement´ aris lazas´ ag
Komplement´aris lazas´ag
Tekints¨ uk a k¨ovetkez˝o feladatot: Max z = 6x1 + x2 x1 + 2x2 3x1 + x2 x2
− + − +
− x4 + x4 ≤ 5 ≤8 + x4 = 1 x1 nem korl´atos x2 , x 3 , x 4 ≥ 0 x3 x3 x3 x3
Azt szeretn´enk ellen˝orizni, hogy vajon a k¨ ovetkez˝ ok egyike optim´alis megold´as-e: x1 = 2, x2 = 1, x3 = 0, x4 = 0 x1 = 3, x2 = 0, x3 = 1, x4 = 0 Gondoljuk ´at, mi´ert pont ezeket v´alasztottuk?
Dualit´ as
´ anos LP feladat Altal´
Dualit´ asi t´ etelek
Komplement´ aris lazas´ ag
Komplement´aris lazas´ag Ha a prim´al-du´al feladatp´ar Max cT x Ax ≤ b x ≥ 0 Min
bT y AT y ≤ c y ≥ 0
akkor azt mondjuk, hogy x = (x1 , . . . xn ) ´es y1 = (y1 , . . . , ym ) komplement´ arisak, ha y T (b − Ax) = 0 ´es xT (AT y − c) = 0. Vagyis ha yi > 0, akkor x-et az i-edik egyenletbe helyettes´ıtve =-et kapunk ( a felt´etel ´ eles”) ” ha xi > 0, akkor y-t a du´alis feladat i-edik egyenlet´ebe helyettes´ıtve az = teljes¨ ul
Dualit´ as
Dualit´ asi t´ etelek
´ anos LP feladat Altal´
Komplement´ aris lazas´ ag
Komplement´aris lazas´ag t´etel
Az er˝os dualit´as t´eteln´el t¨ obb is tudunk mondani: T´ etel. (Komplement´ aris lazas´ ag) Tegy¨ uk fel, hogy x a prim´al feladat optim´alis megold´asa. Ekkor Ha y a du´ al optim´ alis megold´asa, akkor x ´es y komplement´ aris Ha y lehets´ eges megold´asa a du´alisnak ´es komplement´ aris x-szel, akkor y optim´ alis megold´asa a du´alnak L´ etezik olyan lehets´ eges y megold´asa a du´alnak, hogy x ´es y komplement´ aris.
Dualit´ as
´ anos LP feladat Altal´
Dualit´ asi t´ etelek
Komplement´ aris lazas´ ag
Komplement´aris lazas´ag: p´elda Visszat´erve a p´eld´ahoz, annak ellen˝ orz´es´ehez, hogy a javasolt megold´asok valamelyik optim´alis-e, kelleni fog a du´alis feladat: Max z = 6x1 + x2 x1 + 2x2 3x1 + x2 x2
− + − +
− x4 + x4 ≤ 5 ≤8 + x4 = 1 x1 nem korl´atos x2 , x 3 , x 4 ≥ 0 x3 x3 x3 x3
Du´al: Min w = 5y1 y1 2y1 y1 y1
+ 8y2 + 3y2 + y2 − y2
+ y3 + + + y1 ,
y3 y3 y3 y2 y3
=6 ≥1 ≥ −1 ≥ −1 ≥0 nem korl´atos
Dualit´ as
Dualit´ asi t´ etelek
´ anos LP feladat Altal´
Komplement´ aris lazas´ ag
Komplement´aris lazas´ag: p´elda
Az els˝ o javaslat: x1 = 2, x2 = 1, x3 = 0, x4 = 0; tegy¨ uk fel, hogy ez optim´alis Ekkor l´etezik y = (y1 , y2 , y3 ) lehets´eges megold´asa a du´alisnak ami komplement´aris x-szel Az els˝ o prim´al felt´etel: x1 + 2x2 + x3 + x4 = 2 + 2 + 0 + 0 = 4 < 5 nem ´ eles → y1 = 0 kell legyen a komplementarit´as miatt A m´asodik prim´al felt´etel: 3x1 + x2 − x3 = 6 + 1 − 0 = 7 < 8 nem ´ eles → y2 = 0 kell legyen a komplementarit´as miatt Ezek alapj´an az els˝ o du´al felt´etel: y1 + 3y2 = 0 + 0 = 0 6= 6 → azaz (y1 , y2 , y3 ) nem lehets´ eges megold´asa a du´alnak, de feltett¨ uk, hogy az ⇒ x nem optim´ alis megold´asa a prim´alnak
Dualit´ as
Dualit´ asi t´ etelek
´ anos LP feladat Altal´
Komplement´ aris lazas´ ag
Komplement´aris lazas´ag: p´elda
Az m´ asodik javaslat: x1 = 3, x2 = 0, x3 = 1, x4 = 0; tegy¨ uk fel, hogy ez optim´alis Ekkor l´etezik y = (y1 , y2 , y3 ) lehets´eges megold´asa a du´alisnak ami komplement´aris x-szel Az els˝ o prim´al felt´etel: x1 + 2x2 + x3 + x4 = 3 + 0 + 1 + 0 = 4 < 5 nem ´ eles → y1 = 0 kell legyen a komplementarit´as miatt A m´asodik prim´al felt´etel: 3x1 + x2 − x3 = 9 + 0 − 1 = 8 ´ eles A harmadik prim´al felt´etel: x2 + x3 + x4 = 0 + 1 + 0 = 1 ´ eles El˝ ojel felt´etelek is teljes¨ ulnek (x1 , x2 , x3 , x4 ≥ 0) ⇒ x lehets´ eges megold´asa a prim´alnak
Dualit´ as
´ anos LP feladat Altal´
Dualit´ asi t´ etelek
Komplement´ aris lazas´ ag
Komplemet´aris lazas´ag: p´elda N´ezz¨ unk meg a x ´ert´ekeit a du´alra vonatkoz´ oan x1 nem korl´atos → els˝ o du´al felt´etel y1 + 3y2 = 6 ´ eles (sz¨ uks´egszer˝ uen) x3 > 0 → a harmadik du´al felt´etelnek ´ elesnek kell legyen: y1 − y2 + y3 = −1
¨ Osszegezve az eddigieket: y1 =0 y1 + 3y2 + y3 = 6 y1 − y2 + y3 = −1 Ennek az egy´ertelm˝ u megold´asa: y1 = 0, x2 = 2, y3 = 1. A konstrukci´ ob´ ol ad´ od´ oan ez komplement´aris x-szel.
Az utols´o l´ep´es annak ellen˝ orz´ese, hogy y lehets´eges megold´asa-e a du´alnak. Igen ⇒ x optim´ alis megold´asa a prim´alnak.
Dualit´ as
Dualit´ asi t´ etelek
´ anos LP feladat Altal´
Komplement´ aris lazas´ ag
Komplement´aris lazas´ag: ¨osszegz´es
¨ Osszefoglalva: 1
Adott x (javasolt prim´al megold´as), ellen˝ orizz¨ uk, hogy lehets´eges-e
2
N´ezz¨ uk meg mely yi v´altoz´ oknak kell 0-nak lennie
3
N´ezz¨ uk meg mely du´al felt´eteleknek kell ´elesnek lennie → egyenletrendszert kapunk
4
Oldjuk meg ezt a rendszert
5
Ellen˝orizz¨ uk, hogy a kapott megold´as lehets´eges megold´asa-e a du´alnak
Ha minden l´ep´es sikeres volt, akkor az adott x optim´alis, k¨ ul¨onben nem. K´ erd´ es: mi van akkor, ha x lehets´eges, de nem b´azismegold´as?
