dnes je 13.11.2024

Input:

Dualita úloh lineárního programování

13.10.2008, , Zdroj: Verlag Dashöfer

17.4.8
Dualita úloh lineárního programování

Doc. Ing. Alois Fiala, CSc.

Dvojice duálně sdružených úloh

S každou úlohou lineárního programování je jistým způsobem úzce spojena jiná úloha, která je rovněž lineární a která je původní úlohou jednoznačně určena. Přitom maximalizační úloze odpovídá úloha minimalizační a naopak. Úlohy lineárního programování se tedy vlastně vyskytují ve dvojicích (hovoříme o dvojicích duálně sdružených úloh). Původní úlohu v této dvojici nazýváme primární, kdežto úlohu s ní sdruženou označujeme jako duální. Mezi duálně sdruženými úlohami existuje řada zajímavých vztahů, které jsou užitečné jak z teoretického, tak i z praktického hlediska. Poznamenejme ještě, že dualita není omezena pouze na lineární programování, ale je obecnějším jevem.

Konstrukce duálního problému k danému problému lineárního programování je formální záležitostí, danou systémem jistých pravidel. Dříve než se s těmito pravidly seznámíme, ukažme si na následujícím příkladu, že tuto konstrukci a vzniklý duální problém lze ekonomicky interpretovat.

Příklad 1

Uvažujme problém optimalizace výrobního programu:

kde
aij spotřeba i-tého zdroje na výrobu jednotky j-tého výrobku,
bi kapacita i-tého zdroje,
cj zisk za jednotku j-tého výrobku,
xj vyrobené množství j-tého výrobku.

Představme si, že bychom místo výroby a prodeje výrobků chtěli pronajímat, resp. prodávat výrobní zdroje. To znamená, že bychom nějaké jiné firmě umožnili vyrábět její výrobky při použití našich výrobních zdrojů. Označme symbolem ui cenu jednotky i-tého zdroje, za niž chceme tento zdroj prodávat. Pak výraz Σm i=1 aij ui představuje cenu zdrojů, které by se při výrobě spotřebovaly na výrobu jednotky j-tého výrobku. Aby byl prodej zdrojů výhodnější než výroba a prodej vlastních výrobků, musejí platit podmínky:

Celkovou cenu prodaných zdrojů pak představuje výraz Σm i=1 bi ui. Zajímá-li nás, jaká může být nejnižší hodnota tohoto výrazu a jaké ceny zdrojů jí odpovídají, musíme řešit následující problém:

Symetricky duálně sdružené úlohy

Úloha (2) se nazývá duální úlohou k úloze (1). Ačkoli jsme ji zde odvodili pro určitou interpretaci primární úlohy, je nutno zdůraznit, že její tvar na této interpretaci vůbec nezávisí. Vidíme, že duální úloha je vytvořena výlučně z koeficientů primární úlohy. V účelové funkci duální úlohy se objevují veličiny bi, pravé strany duálních omezení obsahují veličiny cj a levé strany duálních omezení jsou tvořeny pomocí sloupců matice A. Rovněž si všimněme, že proměnné xj primární úlohy odpovídají omezením duální úlohy a primární omezení odpovídají duálním proměnným. Dále v tomto případě mají primární omezení tvar nerovnic typu ≤, duální omezení jsou nerovnice typu ≥, a primární i duální proměnné jsou vázány podmínkami nezápornosti (jak uvidíme později, vždy tomu tak být nemusí). Úloha (2) je tedy jakýmsi "zrcadlovým obrazem“ úlohy (1), a proto tyto úlohy nazýváme symetricky duálně sdruženými úlohami. Je třeba si uvědomit, že dualita je vztah vzájemný, proto je tedy duální úlohou k úloze (2) úloha (1).

Maticový zápis dvojice symetricky duálně sdružených úloh vypadá takto:

f(x) = cTx → max g(u) = bTu → min
Axb ATuc
x0 u0
Příklad 2

Zkonstruujme duální úlohu k úloze z příkladu 1 v § 17/4.1 (po zanedbání podmínek celočíselnosti):

                   
f(x) = 4 x1 + 6 x2 max
3 x1 + 3 x2 210
x1 + 2 x2 100
x1 60
x2 40
x1 , x2 0
                     
g(u) = 210 u1 + 100 u2 + 60 u3 + 40 u4 min
3 u1 + u2 + u3 4
3 u1 + 2 u2+ u4 6
u1 , u2, u3 , u4 0

Pravidla pro konstrukci duálních úloh

Dvojice symetricky duálně sdružených úloh je pouze speciálním případem primárně-duálních vztahů mezi úlohami LP. Jak již bylo na začátku této podkapitoly uvedeno, duální úlohu je možno zkonstruovat ke každé úloze LP. Bylo by možno postupovat tak, že se výchozí úloha nejprve transformuje do tvaru (1) a odpovídající duální úloha se pak "zrcadlově převrácenými“ zpětnými úpravami zjednoduší do výsledného tvaru. Tímto způsobem byly odvozeny strukturní vztahy mezi duálně sdruženými úlohami, uvedené v následující tabulce, s jejichž pomocí lze snadno zkonstruovat duální úlohu k libovolné úloze lineárního programování.

Maximalizační úloha Minimalizační úloha
primární duální
duální primární
omezení typu ≤ nezáporná proměnná
omezení typu ≥ nekladná proměnná
omezení typu rovnice proměnná neomezená
nezáporná proměnná omezení typu ≥
nekladná proměnná omezení typu ≤
proměnná neomezená omezení typu rovnice
Příklad 3

Zkonstruujme duální úlohu k následující úloze:

           
f(x) = 3 x1 + 2 x2 min
x1 + x2 2
2 x1 x2 = 5
x1 + 3 x2 27
x1 0
                       
g(u) = 2 u1 + 5 u2 + 27 u3 max
u1 + 2 u2 + u3 3
u1 u2 + 3 u3 = 2
u1 0
u3 0

Primární úloha je minimalizační, a tedy úloha k ní duální musí být maximalizační. Proměnná x1 je v primární minimalizační úloze nezáporná, a tedy v duální maximalizační úloze musí být prvé omezení typu ≤ . Proměnná x2 je neomezená co do znaménka, a tudíž druhé omezení v duální úloze musí být tvaru rovnice. Prvé omezení v primární minimalizační úloze je typu ≥, a tedy odpovídající duální proměnná u1 v maximalizační úloze musí být nezáporná. Druhé primární omezení má tvar rovnice, takže příslušná duální proměnná u2 je neomezená co do znaménka. Třetí omezení v primární minimalizační úloze je typu ≤, a tedy duální proměnná u3 musí být nekladná.

Speciálním případem aplikace výše uvedených pravidel je konstrukce duální úlohy k úloze ve standardním tvaru:

 
f(x) = cTx → max g(u) = bTu → min
Ax = b ATuc
x0

Věty o dualitě

Pro dvojice duálně sdružených úloh platí řada užitečných tvrzení, z nichž si zde některá uveďme.

Slabá věta o dualitě

Slabá věta o dualitě: Nechť primární úloha je maximalizační s účelovou funkcí f(x), duální úloha je minimalizační s účelovou funkcí g(u), x0 je libovolné přípustné řešení primární úlohy a u0 je libovolné přípustné řešení duální úlohy. Pak platí:

f(x0) ≤ g(u0)

Tedy hodnota účelové funkce minimalizační úlohy v kterémkoli přípustném řešení je horní mezí hodnot účelové funkce duálně sdružené maximalizační úlohy na množině všech jejích přípustných řešení a obdobně hodnota účelové funkce maximalizační úlohy v kterémkoli přípustném řešení je dolní mezí hodnot účelové funkce duálně sdružené minimalizační úlohy na množině všech jejích přípustných řešení.

Silná věta o dualitě

Silná věta o dualitě: Má-li jedna z duálně sdružených úloh optimální řešení, má optimální řešení i úloha druhá, přičemž optimální hodnoty účelových funkcí jsou si rovny.

Silná a slabá věta o dualitě mají následující důsledky:

  • Platí-li pro přípustné řešení x0 primární úlohy a pro přípustné řešení u0 duální úlohy rovnost f(x0) = g(u0), pak x0 a u0 jsou optimální řešení.

  • Je-li množina přípustných řešení maximalizační úlohy neprázdná a je-li účelová funkce této úlohy shora neomezená, pak duálně sdružená úloha nemá žádné přípustné řešení.

  • Je-li množina přípustných řešení minimalizační úlohy neprázdná a je-li účelová funkce této úlohy zdola neomezená, pak duálně sdružená úloha nemá žádné přípustné řešení.

  • Nemá-li jedna z dvojice duálně sdružených úloh

Nahrávám...
Nahrávám...