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

17.4.8

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

Doc. Ing. Alois Fiala, CSc.

 NahoruDvojice 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
a_ij spotřeba i-tého zdroje na výrobu jednotky j-tého výrobku,
b_i kapacita i-tého zdroje,
c_j zisk za jednotku j-tého výrobku,
x_j 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 u_i cenu jednotky i-tého zdroje, za niž chceme tento zdroj prodávat. Pak výraz Σ^m _i=1 a_ij u_i 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 b_i u_i. 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:

 NahoruSymetricky 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 b_i, pravé strany duálních omezení obsahují veličiny c_j a levé strany duálních omezení jsou tvořeny pomocí sloupců matice A. Rovněž si všimněme, že proměnné x_j 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:

 NahoruPravidla 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í.

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

 NahoruVě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.

 NahoruSlabá 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), x₀ je libovolné přípustné řešení primární úlohy a u₀ je libovolné přípustné řešení duální úlohy. Pak platí:

f(x₀) ≤ g(u₀)

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

 NahoruSilná 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í x₀ primární úlohy a pro přípustné řešení u₀ duální úlohy rovnost f(x₀) = g(u₀), pak x₀ a u₀ 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…