5 Dualita úloh LP V návaznosti na předchozí teoretickou lekci nyní zavedeme užitečný pojem duality úloh LP, který nám mimo jiné poskytne dobrou charakterizaci optimálních řešení LP. Platí totiž, že původní (primární) i duální úloha mají zároveň optimální řešení stejné účelové hodnoty. Zjednodušeně řečeno, duální úloha k úloze v základním tvaru se získá transpozicí matice úlohy a záměnou účelového vektory s vektorem pravých stran, při současné změně směru nerovností. Stručný přehled lekce ˇ Dualita úloh LP v základním tvaru, slabá věta o dualitě. ˇ Dobrá charakterizace, silná věta o dualitě. ˇ Obecný tvar duální úlohy LP. Petr Hliněný, FI MU 1 IA102 "OU": Dualita úloh LP 5.1 Základní tvar duality Běžná (a snadno zapamatovatelná) definice duální úlohy LP se vztahuje k formulaci původní úlohy (zvané primární úloha) v základním tvaru, ale později si ukážeme, jak lze převést na duální i úlohu LP v obecném tvaru. Definice 5.1. Duální úlohou LP k úloze v základním tvaru max c x pro A x b, x 0 je úloha min b y pro y A c, y 0 . Složky vektoru y jsou tzv. duální proměnné. Jinými slovy, při formulaci duální úlohy přiřadíme nové (duální) proměnné yj jednotlivým nerovnicím primární úlohy, matici A transponujeme a vektory účelový c a pravých stran b vzájemně zaměníme. Nově získané duální nerovnosti budou v opačném směru a duální účelová funkce b y se bude minimalizovat. I duální proměnné budou všechny nezáporné. Příklad 3.1 o hranolkách a lupíncích vede na níže zapsanou duální úlohu LP. max 80x1 + 50x2 : 2x1 + 1.5x2 100 0.4x1 + 0.2x2 16 x1, x2 0 min 100y1 + 16y2 : 2y1 + 0.4y2 80 1.5y1 + 0.2y2 50 y1, y2 0 Petr Hliněný, FI MU 2 IA102 "OU": Dualita úloh LP V obecnějším zápise (pro názornější pochopení a zapamatování) vypadá dualita úloh v základ- ním tvaru takto: Primární úloha: max c1x1 + c2x2 + . . . + cnxn : a11 a12 . . . a1n ... ... am1 am2 . . . amn x1 x2 ... xn b1 ... bm x1, x2, . . . , xn 0 Duální úloha: min b1y1 + b2y2 + . . . + bmym : [ y1 . . . ym ] a11 . . . am1 a12 . . . am2 ... ... a1n . . . amn c1 ... cn y1, y2, . . . , ym 0 Rozeberte si sami pro sebe, proč dvojí aplikací duality získáme zpět původní úlohu! Petr Hliněný, FI MU 3 IA102 "OU": Dualita úloh LP Důležitost duální úlohy při dobré charakterizaci optimálních řešení úloh LP vyplývá z následujících tvrzení o dualitě. Věta 5.2. (Slabá věta o dualitě LP) Nechť xo je přípustným řešením (maximalizační) primární úlohy A x b, x 0 a yo je přípustným řešením (minimalizační) duální úlohy y A c, y 0. Pak c xo b yo . Důkaz: c xo (yo A) xo = yo (A xo ) yo b = b yo . 2 Důsledek 5.3. Máme-li přípustná řešení xo , yo jako ve Větě 5.2 a navíc c xo = b yo , pak xo je primárním optimálním řešením a yo duálním optimem. Důkaz sporem: Nechť existuje lepší řešení x1 , tj. cx1 > cxo . Pak ale cx1 > cxo = b yo , z čehož plyne spor s c x1 b yo podle Věty 5.2. 2 Petr Hliněný, FI MU 4 IA102 "OU": Dualita úloh LP 5.2 Silná dualita V souvislosti s užitečným Důsledkem 5.3 se přirozeně nabízí otázka, zda vždy nalezneme přípustná řešení primární a duální úlohy o stejných účelových hodnotách. Pochopitelně, pokud primární úloha nemá optimální řešení, ať už z důvodu nepřípustnosti nebo neomezenosti, tak odpovídající duální řešení nenajdeme. Ve všech ostatních případech však ano: Věta 5.4. (Silná věta o dualitě LP) Nechť xo je optimálním řešením primární úlohy max c x pro A x b, x 0 . Pak existuje přípustné řešení yo příslušné duální úlohy takové, že c xo = b yo . Poznámka: Důsledek 5.3 spolu s Větou 5.4 dává dobrou charakterizaci pro všechny řešitelné úlohy LP ­ pro důkaz optimality našeho řešení vždy najdeme přípustné duální řešení stejné účelové hodnoty. Petr Hliněný, FI MU 5 IA102 "OU": Dualita úloh LP Důkaz: Fakt, že přípustný vektor xo je optimálním řešením dané primární úlohy lze jinak vyjádřit tvrzením, že neexistuje její přípustné řešení s hodnotou c x c xo + pro žádné > 0, tedy že rozšířená úloha A -c x b -c xo - , x 0 nemá žádné přípustné řešení. Nyní aplikujeme (Farkasovo lema) Důsledek 4.8. Podle něj existuje nezáporná kombinace nerovností rozšířené úlohy, která je sporná. Formálně, existuje y 0 takový, že y A -c 0, y b -c xo - < 0 . (1) V prvé řadě si uvědomme, že poslední souřadnice y musí být kladná, neboť teprve poslední nerovnost rozšířené soustavy způsobuje její neřešitelnost. Takže lze (po nor- malizaci) psát y = (yo , 1). Rozepsáním vztahů (1) pak dostáváme yo A c, yo b < c xo + . Jelikož poslední vztah platí pro libovolně malé > 0, limitním přechodem 0 získáme yo A c, yo 0, yo b c xo . Vidíme tedy, že yo je přípustným řešením příslušné duální úlohy a navíc podle Dů- sledku 5.3 je yo b = c xo . 2 Petr Hliněný, FI MU 6 IA102 "OU": Dualita úloh LP 5.3 Obecný tvar duality LP Duální úlohu LP lze pochopitelně sestavit i k úloze LP v obecném tvaru. Pro toto můžeme nakonec použít základní Definici 5.1 a přidat postup podle důkazu Věty 3.5 (nahrazovat vztahy a proměnné dvakrát ­ před i po duální konstrukci). Fakt: Pro obecný tvar úlohy LP je duální úloha schematicky naznačena takto: max c x + d x : A B C D x x = a b x 0 min a y + b y : AT CT BT DT y y = c d y 0 Jinými slovy, při formulaci obecné duální úlohy přiřadíme nové (duální) proměnné yj jednot- livým nerovnicím i rovnicím primární úlohy. Přitom duální proměnná odpovídající nerovnosti bude nezáporná, kdežto ta odpovídající rovnosti bude neomezená. Analogicky duální vztahy odpovídající sloupcům nezáporných primárních proměnných budou nerovnostmi, kdežto ty odpovídající neomezeným primárním proměnným budou vyjádřeny jako duální rovnosti. Opět vektory účelový a pravých stran vzájemně zaměníme. Nově získané duální nerovnosti budou v opačném směru a duální účelová funkce se bude minimalizovat. Petr Hliněný, FI MU 7 IA102 "OU": Dualita úloh LP