2
Spojité modely rozhodování Jak již víme z přednášky, diskrétní model rozhodování lze zapsat ve tvaru
úlohy hodnocení variant: f (ai ) −→ max, ai ∈ A = {a1 , a2 , . . . ap }, kde f je kriteriální funkce a A je rozhodovací množina variant. Pro spojité modely rozhodování budeme používat následující zápis: f (x) −→ max, x = (x1 , x2 , . . . xn ), x ∈ X, kde X = {x ∈ Rn , gi (x) ≤ bi , x ≥ 0}, je rozhodovací množina variant a f kriteriální funkce. Přípustným řešením nazveme každý vektor x rozhodovací množiny X, tedy vektor, který splňuje omezující podmínky a podmínky nezápornosti. Optimálním řešením nazveme takový vektor x z množiny přípustných řešení, který maximalizuje hodnotu kriteriálníí funkce f (x). Pozn.: Pokud jsou funkce f a gi (x) lineární, mluvíme o úloze lineárního programování.
2.1
Model lineárního programování
Model lineárního programování lze obecně zapsat ve tvaru: max z = c1 x1 + c2 x2 + . . . + cn xn . . . maximalizace kriteriální funkce za podmínek: a11 x1 + a12 x2 + . . . + a1n xn ≤ b1 a21 x1 + a22 x2 + . . . + a2n xn ≤ b2 .. . am1 x1 + am2 x2 + . . . + amn xn ≤ bm . . . omezující podmínky x1 , x2 , . . . , xn ≥ 0 . . . podmínky nezápornosti
Tento zápis je sice sndno pochopitelný ale bohužel zlouhavý a tak pro model lineárního programování častěji používáme zkrácený zápis pomocí symbolů sumy: max z =
n P
cj xj . . . maximalizace kriteriální funkce
j=1
1
za podmínek: n X
aij xj ≤ bi . . . omezující podmínky
j=1
xj ≥ 0 . . . podmínky nezápornosti
nebo maticový zápis: max z = cT x . . . maximalizace kriteriální funkce za podmínek: Ax ≤ b . . . omezující podmínky x ≥ 0 . . . podmínky nezápornosti
Pro maticový zápis platí: matice strukturních koeficientů a a12 11 a21 a22 A= . .. .. . am1 am2 vektor řešení
x1
. . . a1n . . . a2n .. .. . . . . . amn
x=
xn
b1
x2 .. .
vektor pravých stran b=
bm
c1
b2 .. .
vektor cenových koeficientů
c= 2
c2 .. . cn
Základní věta lineárního programování nám říká, že má-li úloha lineárního programování optimální řešení, pak existuje také základní optimální řešení. Jinými slovy, projdeme-li všechna základní řešení (kterých je konečně mnoho) a nenajdeme-li přípustné řešení, pak optimální řešení neexistuje. Navíc platí, že má-li úloha jedno optimální řešení, pak je základní. Má-li nekonečně mnoho řešení, pak je alespoň jedno řešení základní. Pokud mezi základními řešeními najdeme přípustné řešení, ale ne optimální, pak optimální řešení neexistuje. Základním řešením se rozumí vrcholy konvexního polygonu tvořícího množinu přípustných řešení.
2.2
Jednofázová simplexová metoda
Krok 1 – převod na soustavu rovnic Uvažujme maximalizační úlohu popsanou v předchozí kapitole. Nejprve soustavu omezujících podmínek převedeme na soustavu rovnic. Získáme tak kanonický tvar soustavy rovnic. Pro každou nerovnici (podmínku) použijeme jednu přídatnou proměnnou, která bude nezáporná. V soustavě máme původně x1 , . . . , xn a nyní přidáme obecně dalších m proměnných xn+1 , . . . , xn+m . Pokud jsou nerovnosti tvaru „≤ÿ, je třeba proměnné přičíst, pro nerovnosti opačného směru je třeba přídatné proměnné odečíst. Pro maximalizační úlohu z předchozí kapitoly získáme tedy kanonický tvar soustavy rovnic:
a11 x1
+a12 x2
+ . . . +a1n xn
a21 x1 .. .
+a22 x2
+ . . . +a2n xn .. .
+xn+1
= b1 +xn+2
am1 x1 +am2 x2 + . . . +amn xn
..
.
= b2 .. . +xn+m = bm
Z této soustavy snadno sestavíme matici strukturních koeficientů. Matice má rozměr m×(n+m) a obsahuje submatici rozměru m×m, která je jednotková (v případě nerovností typu „≤ÿ):
3
a11
a12
. . . a1n
1 0 ... 0
a21 a22 . . . a2n 0 1 . . . 0 A= . .. .. .. .. . . . am1 am2 . . . amn 0 0 . . . 1
Krok 2 – nalezení výchozího řešení Pokud je soustava podmínek v kanonickém tvaru, tzn. že obsahuje jednotkovou submatici, je výchozím řešením vektor x = 0, je-li přípustný (neboli pokud na pravé straně jsou hodnoty nezáporné). V případě, že soustava není v kanonickém tvaru, řeší se úloha dvoufázovou simplexovou metodou, kde prvním krokem je najít přípustné výchozí řešení za pomoci pomocné účelové funkce. Krok 3 – sestavení výchozí simplexové tabulky • Do prvního řádku napíšeme do jednotlivých sloupců seznam všech proměnných, včetně přídatných proměnných. • Dopředu přidáme další sloupec, do kterého budeme psát základní (bazické) proměnné. • Pro snazší výpočty se doporučuje přidat ještě jeden sloupec, do kterého vypíšeme cenové koeficienty pro bazické proměnné. • Do posledního sloupce budeme zapisovat vektor pravých stran a tam také nalezneme řešení. • Do řádků pak zapíšeme bazické proměnné, pro kanonický tvar budou prvními bazickými proměnnými proměnné přídatné. • Pak vpíšeme do tabulky strukturní koeficienty, první řádek odpovídá první podmínce, druhý řádek druhé podmínce atd. Sloupce odpovídají jednotlivým proměnným. • Nakonec budeme uvádět řádek účelové funkce, kam pro začátek napíšeme opačné hodnoty cenových koeficientů (pr přídatné proměnné nuly) a do sloupce pro pravou stranu budeme psát hodnotu účelové funkce, která je na začátku rovna nule. 4
• Pokud si hodnoty cenových koeficientů nepamatujeme, připíšeme si je do hlavičky tabulky, neboť je budeme potřebovat. Pro maximalizační úlohu, která má dvě proměnné a dvě podmínky ve tvaru „≤ÿ, bude vypadat výchozí simplexová tabulka následovně: ceny cB
zákl.prom.
c1
c2
0
0
x1
x2
x3
x4
βi
0
x3
a11
a12
1
0
b1
0
x4
a21
a22
0
1
b2
zj1
−c1
−c2
0
0
0
Poznamenejme ale nakonec, že řádek a sloupec s cenami se většinou v tabulkách neuvádí. Krok 4 – ověření optimality Pro maximalizační úlohu platí, že řešení je optimální, pokud v řádku účelové funkce jsou nezáporná čísla (mluvíme pohopitelně o redukovaných a stínových cenách). Pro minimalizační úlohy je řešení optimální, pokud jsou všechny redukované a stínové ceny nekladné. V případě, že je podmínka optimality splněna, výpočet ukončíme, pokud ne, provedeme transformaci simplexové tabulky popsanou v kroku 5. Optimální řešení pak nalezneme v posledním sloupci, kde jsou hodnoty jednotlivých proměnných. Krok 5 – transformace simplexové tabulky Řešení v simplexové tabulce není optimální, pro maximalizační úlohu je některá z cen v řádku účelové funkce záporná. Jako klíčový sloupec vybereme ten, ve kterém je v řádku účelové funkce záporná hodnota v absolutní hodnotě nejvyšší (neboli nejmenší záporné číslo). Proměnná, které odpovídá tento sloupec bude proměnnou vstupující do báze (stane se základní proměnnou). Pro minimalizaci bude klíčovým sloupcem ten, který má v řádku účelové funkce nejvyšší kladnou hodnotu. Připomeňme, že kladné ceny uvedené v řádku účelové funkce nám říkají, o kolik se sníží hodnota účelové funkce přidáním jedné jednotky odpovídající proměnné, záporné hodnoty naopak říkají, o kolik se hodnota účelové funkce zvýší. 5
Máme-li klíčový sloupec, zvolíme klíčový řádek. Pro všechny řádky i, která mají v klíčovém sloupci j kladnou hodnotu příslušného strukturního koeficientu αij > 0 spočítáme hodnotu ti = bi /αij . Řádek, který má tuto hodnotu nejnižší zvolíme jako klíčový a příslušná základní proměnná se stane nezákladní, neboli vystupující z báze. Také v případě minimalizace se volí klíčový řádek jako ten, který má výše uvedený poměr minimální. Důvod, proč volíme klíčový řádek takto je jednoduchý. Snažíme se hledat taková řešení, která jsou přípustná a nezpůsobí zápornost pravé strany. V případě, že zvolíme špatně klíčový řádek, docílíme toho, že v posledním sloupci se objeví záporné hodnoty a řešení nebude přípustné. Prvek, který je v klíčovém sloupci i klíčovém řádku se nazývá klíčový prvek. Nejprve transformujeme klíčový řádek tak, že všechny hodnoty v řádku vydělíme klíčovým prvkem a do legendy (sloupce se základními proměnnými) tohoto řádku napíšeme vstupující proměnnou. Pak transformujeme ostatní řádky tak, že vezmeme hodnotu v klíčovém sloupci a přenásobíme číslem (−1). Takto získanou hodnotou přenásobíme každý prvek v řádku nové (vstupující) proměnné – to je ten, která jsme před chvílí vydělili klíčovým prvkem. Tyto nově získané hodnoty přiteme k původnímu řádku ve staré simplexové tabulce a napíšeme do té nové. V praxi tedy platí, že pokud klíčový sloupec označíme j a klíčový řádek i, simplexovou tabulku (kromě klíčového řádku) transformujeme tak, že: S S S S aN kl = akl − akj (ail /aij ).
Horní index N označuje hodnotu v nové simplexové tabulce, index S ve staré. S S Pro klíčový řádek je transformace: aN il = ail /aij .
Zbývá dopočítat řádek účelové funkce. Pokud míme tabulku rozšířenou o sloupec a řádek s cenami, bude výpočet jednodušší. Předpokládejme, že počítáme hodnotu pro j-tý sloupec, tedy proměnnou xj . Hodnota zj je pak počítána následovně: Prvek ve sloupci znásobíme cenovým koeficientem příslušné bazické proměnné (to je cena v prvním sloupci), tyto součiny nasčítáme pro všechny řádky a odečteme cenu proměnné ve sloupci (cenu v prvním řádku). Důležité je, že pro základní proměnné je v řádku účelové funkce nula. Hodnota účelové funkce (pravý dolní roh tabulky) je pak součinem cen základních proměnných (první sloupec) a množstvím těchto základních proměnných (pravé strany, poslední sloupec) nasčítaných přeš všechny řádky. 6
Pozn.: Pokud by v případě maximalizace hodnota účelové funkce nevzrostla, v případě minimalizace neklesla, je něco v nepořádku. Po této transformaci se vrátíme ke kroku 4 a ověříme optimalitu. Pro další studium Pro další studium simplexové metody a její praktické použití je důležité zvládnout: • Dvoufázovou simplexovou metodu – nalezení přípustného výchozího řešení pomocí pomocných proměnných a pomocné účelové funkce. • Zamyslet se nad výpočtem minimalizace. • Rozmyslet si počty optimálních řešení, alternativní řešení apod. • Zamyslet se, co se stane pokud nerovnosti nemají očekávaný směr. • Jak počítat v případě, že omezující podmínka je ve tvaru rovnosti. • Interperataci redukovaných a stínových cen. Znalosti je možno čerpat z Lagová, Lineární modely, VŠE 1999, Lagová, Lineární modely v příkladech, VŠE 2002 a Jablonský, Operační výzkum, Professional Publishing 2002.
2.3
Řešené příklady
Příklad 1 Zadání:
max z = 10x1 + 5x2 za podmínek: 5x1 + 3x2 ≤ 60 4x1 − 2x2 ≤ 26 x1 , x2 ≥ 0
7
a) Nalezněte graficky řešení této úlohy. b) Vypočtěte simplexovou metodou řešení úlohy. Řešení: a) Účelová funkce je funkcí dvou proměnných, grafické řešení tedy nebude těžké najít, neboť množinu přípustných řešení lze zobrazit v rovině. Nejprve si tedy nakreslíme jednotlivá omezení.
V obrázku můžeme vidět: – Modrou barvou vyobrazenou polorovinu odpovídající první podmínce 5x1 + 3x2 ≤ 60 – Červenou barvou vyobrazenou polorovinu odpovídající druhé podmínce 4x1 − 2x2 ≤ 26 – Béžovou barvou podmínku nezápornosti pro x1 – Zelenou barvou podmínku nezápornosti pro x2 – Žlutě je pak vyznačen průnik těchto polorovin, tedy množina přípustných řešení – Černé rovnoběžky ukazují jednotlivé hladiny pro účelovou funkci. Hodota účelové funkce roste směrem k severovýchodnímu (pravému hornímu) rohu (jak naznačuje černá šipka). – Účelová funkce tedy nabývá na množině přípustných řešení (žlutý čtyřúhelník) svého maxima v bodě xopt . 8
xopt lze snadno spočítat jako průsečík modré a červené přímky. Tyto přímky jsou grafickým vyjádřením první a druhé podmínky (se znamením rovnosti). Stačí tedy řešit soustavu dvou rovnic o dvou neznámých:
5x1 + 3x2 = 60 4x1 − 2x2 = 26
Tato soustava má jediné řešení xopt = (x1 , x2 ) = (9, 5). b) Pomocí přídatných proměnných převedeme soustavu na ekvivalentní soustavu rovnic:
5x1
+3x2
4x1
−2x2
+x3 +x4
=
60
=
26
Dále převedeme účelovou funkci do anulovaného tvaru: z − 10x1 − 5x2 = 0 Nyní sestavíme výchozí simplexovou tabulku: zákl.prom.
x1
x2
x3
x4
βi
x3
5
3
1
0
60
x4
4
−2
0
1
26
zj1
−10
−5
0
0
0
Teď bychom měli zvolit klíčový sloupec – protože funkci maximalizujeme, hledáme v řádku účelové funkce nejmenší záporný koeficient. V našem případě −10 a vstupující proměnnou tedy bude x1 . Dále musíme určit proměnnou vystupující, a tak spočítáme pro každý řádek, kde αik > 0, hodnotu t = βi /αik . Klíčovým řádkem, na kterém najdeme vystupující proměnnou, bude ten, který bude mít tuto hodnotu nejmenší. zákl.prom.
x1
x2
x3
x4
t = βi /αik
βi
x3
5
3
1
0
60
12
x4
4
−2
0
1
26
13/2
zj1
−10
−5
0
0
0
9
Z tabulky vidíme, že vystupující proměnnou bude x4 . V dalším kroku nahradíme vystupující proměnnou proměnnou vstupující a řádek vydělíme řídícím prvkem. Ostatní řádky upravíme tak, abychom v sloupci s vstupující proměnnou získali jednotkový vektor. Tak získáme novou simplexovou tabulku. zákl.prom.
x1
x2
x3
x4
βi
x3
0
11/2
1
−5/4
55/2
x1
1
−1/2
0
1/4
13/2
zj2
0
−10
0
5/2
65
Vzhledem k tomu, že v řádku účelové funkce je stále alespoň jedna záporná hodnota, celý postup opakujeme. zákl.prom.
x1
x2
x3
x4
βi
t = βi /αik
x3
0
11/2
1
−5/4
55/2
5
x1
1
−1/2
0
1/4
13/2
xxx
zj2
0
−10
0
5/2
65
zákl.prom.
x1
x2
x3
x4
βi
x2
0
1
2/11
−5/22
5
x1
1
0
1/11
3/22
9
zj3
0
0
20/11 5/22
115
Nyní jsme našli optimální řešení, neboť v řádku účelové funkce již není žádný koeficient záporný. Koeficienty jsou nulové pouze pro základní proměnné, což znamená, že neexistuje alternativní řešení a nalezené řešení je jediným optimálním řešením. Hledané řešení tedy je x = (x1 , x2 , x3 , x4 ) = (9, 5, 0, 0), hodnota účelové funkce (v simplexové tabulce vpravo dole) je rovna 115. Příklad 2 Zadání:
max z = x1 + x2
10
za podmínek: 5x1 + 5x2 ≤ 25 2x1 + 4x2 ≤ 16 x1 ≤ 5 x1 , x2 ≥ 0
a) Nalezněte graficky řešení této úlohy. b) Vypočtěte simplexovou metodou řešení úlohy. Řešení: a) Účelová funkce je funkcí dvou proměnných, grafické řešení tedy nebude těžké najít, neboť množinu přípustných řešení lze zobrazit v rovině. Nejprve si tedy nakreslíme jednotlivá omezení.
V obrázku můžeme vidět: – Modrou barvou vyobrazenou polorovinu odpovídající první podmínce 5x1 + 5x2 ≤ 25 – Červenou barvou vyobrazenou polorovinu odpovídající druhé podmínce 2x1 + 4x2 ≤ 16 – Růžovou barvou vyobrazenou polorovinu odpovídající třetí podmínce x1 ≤ 5 11
– Béžovou barvou podmínku nezápornosti pro x1 – Zelenou barvou podmínku nezápornosti pro x2 – Žlutě je pak vyznačen průnik těchto polorovin, tedy množina přípustných řešení (povšimněme si, že třetí podmínka množinu nijak neomezuje, kdybychom tuto podmínku vypustili, získali bychom zcela stejné řešení – při řešení simplexovou metodou by tedy nebylo nutné tuto podmínku uvažovat, my ji však při výpočtech budeme pro ukázku stejně brát v úvahu). – Černé rovnoběžky ukazují jednotlivé hladiny pro účelovou funkci. Hodota účelové funkce roste směrem k severovýchodnímu (pravému hornímu) rohu (jak naznačuje černá šipka). – Účelová funkce tedy nabývá na množině přípustných řešení (žlutý čtyřúhelník) svého maxima na celé černé úsečce začínající v bodě xopt a končící v bodě (5,0). Simplexovou metodou bychom měli získat oba tyto body. Optimálním řešením pak bude jakákoliv konvexní kombinace těchto dvou bodů (tedy výše zmiňovaná úsečka). xopt lze snadno spočítat jako průsečík modré a červené přímky. Tyto přímky jsou grafickým vyjádřením první a druhé podmínky (se znamením rovnosti). Stačí tedy řešit soustavu dvou rovnic o dvou neznámých:
5x1 + 5x2 = 25 2x1 + 4x2 = 16
Tato soustava má jediné řešení xopt = (x1 , x2 ) = (2, 3). Druhým optimálním základním řešením je průsečík modré, zelené a růžové přímky, tedy bod xN = (x1 , x2 ) = (5, 0). Konvexní kombinaci těchto dvou bodů lze zapsat jako x = kxopt + (1 − k)xN , k ∈< 0, 1 >. Jinými slovy, pro každé optimální řešení platí: x1 = k · 2 + (1 − k) · 5 = 2k + 5 − 5k = 5 − 3k, x2 = k · 3 + (1 − k) · 0 = 3k − 0 = 3k, 12
k ∈< 0, 1 > . b) Pomocí přídatných proměnných převedeme soustavu na ekvivalentní soustavu rovnic:
5x1
+5x2
2x1
+4x2
+x3
= 25 +x4
= 16 +x5
x1
=
5
Dále převedeme účelovou funkci do anulovaného tvaru: z − x 1 − x2 = 0 Nyní sestavíme výchozí simplexovou tabulku: zákl.prom.
x1
x2
x3
x4
x5
βi
x3
5
5
1
0
0
25
x4
2
4
0
1
0
16
x5
1
0
0
0
1
5
zj1
−1
−1
0
0
0
0
Teď bychom měli zvolit klíčový sloupec – protože funkci maximalizujeme, hledáme v řádku účelové funkce nejmenší záporný koeficient. V našem případě −1 a vstupující proměnnou tedy bude x1 nebo x2 (je zcela jedno, který sloupec si vybereme). Dále musíme určit proměnnou vystupující, a tak spočítáme pro každý řádek, kde αik ≥ 0, hodnotu t = βi /αik . Klíčovým řádkem, na kterém najdeme vystupující proměnnou, bude ten, který bude mít tuto hodnotu nejmenší (pokud by řádků s touto nejnižší hodnotou bylo více, vybereme kterýkoliv z nich). zákl.prom.
x1
x2
x3
x4
x5
t = βi /αik
βi
x3
5
5
1
0
0
25
5
x4
2
4
0
1
0
16
8
x5
1
0
0
0
1
5
5
zj1
−1
−1
0
0
0
0
V dalším kroku nahradíme vystupující proměnnou proměnnou vstupující a řádek vydělíme řídícím prvkem. Ostatní řádky upravíme tak, abychom v sloupci s vstupující proměnnou získali jednotkový vektor. Tak získáme novou simplexovou tabulku. 13
zákl.prom.
x1
x2
x3
x4
x5
βi
x1
1
1
1/5
0
0
5
x4
0
2
−2/5
1
0
6
x5
0
−1
−1/5
0
1
0
zj2
0
0
1/5
0
0
5
Nyní jsme našli optimální řešení, neboť v řádku účelové funkce již není žádný koeficient záporný: x1 = (x1 , x2 , x3 , x4 , x5 ) = (5, 0, 0, 6, 0), hodnota účelové funkce (v simplexové tabulce vpravo dole) je rovna 5. Koeficienty však nejsou nulové pouze pro základní proměnné, nýbrž i pro jednu proměnnou nezákladní, což znamená, že existuje alternativní řešení. Podívejme se, co by se stalo, kdybychom v předchozím kroku zvolili jako vstupující proměnnou x2 . zákl.prom.
x1
x2
x3
x4
x5
t = βi /αik
βi
x3
5
5
1
0
0
25
5
x4
2
4
0
1
0
16
4
x5
1
0
0
0
1
5
xxx
zj1
−1
−1
0
0
0
0
x1
x2
zákl.prom.
x3
x4
x5
t = βi /αik
βi
x3
5/2
0
1
−5/4
0
5
2
x2
1/2
1
0
1/4
0
4
16
x5
1
0
0
0
1
5
5
0
0
1/4
0
4
zj2 zákl.prom.
−1/2 x1
x2
x3
x4
x5
βi
x1
1
0
2/5
−1/2
0
2
x2
0
1
−1/5
1/2
0
3
x5
0
0
−2/5
1/2
1
3
zj3
0
0
1/5
0
0
5
Nalezené alternativní řešení x2 = (x1 , x2 , x3 , x4 , x5 ) = (2, 3, 0, 0, 3) má stejnou hodnotu účelové funkce (=5). Po nalezení prvního řešení jsme však k alternativnímu řešení mohli dojít i mnohem rychlejší metodou: Nezákladní proměnnou, která má nulový 14
koeficient v řádku účelové funkce, zvolíme jako proměnnou vstupující a zcela běžnou metodou najdeme proměnnou vystupující. Sestavíme novou simplexovou tabulku a okamžitě získáme alternativní řešení: zákl.prom.
x1
x2
x3
x4
x5
t = βi /αik
βi
x1
1
1
1/5
0
0
5
5
x4
0
2
−2/5
1
0
6
3
x5
0
−1
−1/5
0
1
0
xxx
zj2
0
0
1/5
0
0
5
zákl.prom.
x1
x2
x3
x4
x5
βi
x1
1
0
2/5
−1/2
0
2
x2
0
1
−1/5
1/2
0
3
x5
0
0
−2/5
1/2
1
3
zj3
0
0
1/5
0
0
5
Výpočet této konečné simplexové tabulky je výrazně jednodušší, než postupný výpočet předvedený v předchozí fázi, ale vede k identickému řešení. Nyní jsme tedy nalezli dva optimální body (a žádný další mezi základními řešeními nenalezneme). Optimálním řešením je tedy každý bod, který je konvexní kombinací těchto dvou nalezených bodů (včetně krajních bodů): x = kx1 + (1 − k)x2 , k ∈< 0, 1 >.
2.4
Dualita v úlohách lineárního programování
Ve všech přechozích kapitolách jsme pracovali s maximalizační úlohou, kterou lze zapsat různými způsoby. My teď budeme používat maticový zápis, ale pokud by to někomu dělalo problémy, může si vztahy snadno přepsat do jakékoliv formy. Maximalizační úlohu lineárního programování lze tedy zapsat následovně: max z = cT x . . . maximalizace kriteriální funkce za podmínek: Ax ≤ b . . . omezující podmínky x ≥ 0 . . . podmínky nezápornosti V teorii duality se tato úloha nazývá primární úlohou. 15
Ke každé primární úloze je možno velmi snadno sestavit úlohu duální. K výše uvedené primární úloze má duální úloha tvar: min f = bT y . . . minimalizace kriteriální funkce za podmínek: AT y ≥ c . . . omezující podmínky y ≥ 0 . . . podmínky nezápornosti Ukažme si nyní na příkladu, co to znamená prakticky: Příklad – duální úloha Předpokládejme, že máme zadanou primární úlohu jako maximalizační funkci za daných podmínek. Naším úkolem je k primární úloze sestavit duální úlohu.
Primární úloha: max z = 5x1 + 3x2 + 2x3 za podmínek: x1 + 2x2 − x3 ≤ 8 2x1 − x2 + 3x3 ≤ 6 x1 + x 2 − x 3 ≤ 7 x1 , x2 , x3 ≥ 0
Duální úloha: min f = 8y1 + 6y2 + 7y3 za podmínek: y1 + 2y2 + y3 ≥ 5 2y1 − y2 + y3 ≥ 3 −y1 + 3y2 − y3 ≥ 2 y1 , y2 , y3 ≥ 0
16
Podívejme se nyní pořádně, jak jsme duální úlohu sestavili. K maximalizaci je duální minimalizační problém. Koeficienty v účelové funkci duální úlohy tvoří vektor pravých stran z úlohy primární. Naopak vektor pravých stran v úloze duální je tvořen vektorem cenových koeficientů z primární úlohy. Směr nerovností v omezujících podmínkách je opačný a matice strukturních koeficientů je transformovaná. Tzn. že sloupcové vektory primární úlohy nyní tvoří řádkové vektory duální úlohy a naopak. Nyní se již nabízí jediná otázka: K čemu to je? V praxi má dualita velké využití, neboť primární a duální úloha mají velmi úzký vztah. V simplexové tabulce primární úlohy najdeme řešení na pravé straně. Nalezneme tam ale také řešení duální úlohy a to konkrétně v řádku účelové funkce pod přídatnými proměnnými. Odtud je již patrné využití. Pokud máme minimalizační úlohu, je její duální úloha maximalizační a patrně se vyhneme nepřípustnému výchozímu řešení. Není tedy běžně potřeba využívat dvoufázovéo simplexu (Pozor: ne vždy se tímto způsobem dvoufázovému simplexu vyhneme). Maximalizační úlohy již umíme řešit, takže není problém úlohu vyřešit a ceny pod přídatnými proměnnými interpretovat jako optimální řešení primární úlohy. Další výhodou je, že počet podmínek v primární úloze se rovná počtu proměnných v úloze duální. Máme-li tedy v primární úloze jen dvě podmínky (bez ohledu na počet proměnných), duální úloha bude sestavena za pomoci jen dvou proměnných. Všichni dobře víme, že úlohy se 2 proměnnými se velmi snadno řeší graficky. Poznamenejme ještě, že primární a duální úloha se nazývají symetricky sdružené duální úlohy. Ze symetrie úloh je již snadno pochopitelné, že přídatné proměnné se nazývají proměnnými duálními. Hodnoty duálních proměnných udávají, o kolik se zvýší hodnota účelové funkce primární úlohy, pokud se disponibilní množství daného zdroje (podmínka) zvýší o jednotku. Tyto hodnoty se často nazývají stínovými cenami. Hodnoty primárních proměnných se nazývají redukovanými cenami a říkají, o kolik se zvýší hodnota účelové funkce, pokud přidáme jednotku primární proměnné. Poslední poznámka se týká skutečnosti, že v případě, že podmínky nemají správný směr, je před sestavením duální úlohy třeba příslušné nerovnice přená17
sobit (−1), aby nerovnost měla správný směr. Pak je možné již snadno duální úlohu sestavit.
18
