OSTRAVSKÁ UNIVERZITA PŘÍRODOVĚDECKÁ FAKULTA
[ MOPV ] METODY OPERAČNÍHO VÝZKUMU Distanční opora
RNDr. Miroslav Liška, CSc.
OSTRAVA 2002
1
Simplexová metoda je iterační výpočetní postup pro nalezení optimálního řešení úlohy lineárního programování (pokud takové řešení existuje). Výchozím bodem tohoto algoritmu je nalezení výchozího základního řešení úlohy lineárního programování. Pokud je již takové řešení k dispozici, potom simplexová metoda v jednotlivých krocích vypočte vždy nové základní řešení s lepší nebo alespoň stejnou – v případě maximalizace vyšší – hodnotou účelové funkce. Po konečném počtu kroků musí tedy tento výpočetní postup vést k nalezení základního řešení s nejlepší hodnotou účelové funkce nebo ke zjištění, že takové řešení neexistuje. Při jeho nalezení se musí podle základní věty LP jednat o řešení optimální. Postup výpočtu pomocí simplexové metody se dělí na dvě fáze: ¾ I.fáze: nalezení výchozího základního řešení ¾ II. fáze: iterační postup vedoucí k optimalizaci účelové funkce V některých speciálních případech je nalezení výchozího základního řešení natolik snadné, že I. fáze výpočtu vlastně odpadá. V takovém případě se celý postup označuje jako jednofázová simplexová metoda. V obecném případě nemusí být však nalezení výchozího základního řešení úlohy LP jednoduché. Potom mluvíme o dvoufázové simplexové metodě.
2
Jednofázová simplexová metoda Lze ji použít pouze v případě, že všechna vlastní omezení úlohy LP jsou definována jako nerovnice typu "≤". Po převedení takovéto soustavy nerovnic na ekvivalentní soustavu rovnic pomocí přídatných proměnných dostáváme totiž soustavu rovnic v kanonickém tvaru.
Kanonický tvar soustavy m lineárních rovnic o (m+n) proměnných je takový tvar, ve kterém matice strukturních koeficientů obsahuje soustavu m jednotkových vektorů, ze kterých lze vytvořit jednotkovou matici. Pokud máme soustavu m lineárních rovnic o (m+n) proměnných v kanonickém tvaru, potom z něj lze snadno odvodit základní řešení této soustavy. V kanonickém tvaru jsou dva druhy proměnných : ¾ m základních proměnných – to jsou proměnné, kterým odpovídají jednotkové vektory a jejichž hodnoty jsou v příslušném základním řešení rovny hodnotám pravé strany ¾ n nezákladních proměnných - to jsou všechny ostatní proměnné, jejichž hodnoty jsou v základním řešení rovny 0.
Příklad: Balírny pražírny kávy plánují výrobu dvou směsí kávy Super a Standard . Pro výrobu obou směsí mají k dispozici tři druhy kávových bobů – K1, K2 a K3 postupně v kapacitě 40, 60 a 25 tun lišících se kvalitou a nákupní cenou. Následující tabulka ukazuje skladbu obou směsí (v tunách komponenty na 1 tunu směsi):
Na základě přímých a nepřímých nákladů souvisejících s výrobou a vzhledem k předpokládaná ceně obou směsí byl vykalkulovaný zisk, který činí 20 000 Kč resp. 14 000 Kč na jednu tunu směsi Super resp. Standard. Management firmy chce samozřejmě naplánovat produkci firmy tak, aby byl její celkový zisk maximální. Po doplnění přídatných proměnných získáváme snadno soustavu tří rovnic, které obsahují pět proměnných: 0,5x1+
0,25x2
+ x3
= 40
3
0,5x1+
0,5x2
+ x4
= 60 + x5
0,25x2
= 25
Matice strukturních koeficientů:
Výchozí základní řešení Základní proměnné jsou tedy x3, x4 a x5. Nezákladní proměnné jsou x1 a x2 . Pokud položíme tyto nezákladní proměnné rovny 0, potom z dané soustavy rovnic snadno získáme hodnoty základních proměnných x3 = 40 , x4 = 60 , x5 = 25 . Řešení získané uvedeným způsobem je, vzhledem k nezápornosti, základním řešením dané úlohy. Po získání výchozího základního řešení lze okamžitě přistoupit v jednotlivých iteracích k testu optimality a ke zlepšování řešení. Celý výpočet je organizován v tzv. simplexové tabulce.
Výchozí simplexová tabulka
Tabulka obsahuje: seznam základních proměnných, matici strukturních koeficientů, vektor pravých stran a v posledním řádku koeficienty účelové funkce v anulovaném tvaru, tj. tvaru, ve kterém jsou všechny proměnné převedeny na levou stranu a na pravé straně je absolutní člen, který udává počáteční hodnotu účelové funkce. Anulovaný tvar účelové funkce je obecně z – c1x1 – c2x2 - … - cnxn = 0 a konkrétně pro náš příklad z - 20000 x1 - 14000 x2 = 0
4
Test optimality Uvažujme simplexovou tabulku v libovolné s-tém kroku výpočtu. Předpokládejme, že tato tabulka obsahuje (m+n) proměnných a m omezujících podmínek s tím, že prvních n proměnných jsou nezákladní proměnné a zbývajících m proměnných jsou základní proměnné. Hodnoty všech základních proměnných včetně hodnoty účelové funkce potom můžeme vyjádřit obecně následovně: Xn+1 = β1 – α11 x1 - α12 x2 - … - α1n xn , Xn+2 = β2 – α21 x1 – α22 x2 - … - α2n xn , …
Xn+m = βm – αm1 x1 – αm2 x2 - … - αmn xn , zs
= β0 – z1 x1 - z2 x2 - … - zn xn .
Vzhledem k tomu, že nezákladní proměnné x1, x2 , …, xn mají nulovou hodnotu, potom jsou vektor řešení v s-tém kroku výpočtu xs hodnota účelové funkce zs xs = (0, 0, …, 0, β1, β2, …, βm) , zs = β0 Předpokládejme, že v (s+1) kroku výpočtu se proměnná xk , k є {1, 2, …, n} stane proměnnou základní. Tuto proměnnou budeme označovat jako proměnnou vstupující. Vzhledem k tomu, že počet základních proměnných je konstantní, musí tato proměnná nahradit některou z původních základních proměnných. Tato proměnné se označuje jako proměnná vystupující. Podívejme se tedy nyní, jak se změní hodnota účelové funkce, pokud bude mít vstupující proměnná v (s+1) kroku nezápornou hodnotu t : xk = t ≥0. Nová hodnota účelové funkce bude po dosazení Zs+1 = β0 –t zk. Změna hodnoty účelové funkce, pokud se proměnná Xk základní proměnnou je tedy
stane
∆ z (xk) = zs+1 – zs = -t* zk . V jednotlivý krocích výpočtu je třeba dosáhnout v případě maximalizace přírůstku hodnoty účel. funkce tzn. ∆ z (xk) ≥ 0 (při minimalizaci ∆ z (xk) ≤ 0 )
5
Vzhledem k nezápornosti nové hodnoty vstupující proměnné t závisí tedy znaménko hodnoty ∆ z (xk) pouze na hodnotě redukované ceny zk Mohou nastat tři možnosti: 1. ∆ z (xk) >0 ↔ zk < 0 - ke zvýšení hodnoty účel. funkce dojde v případě, že je redukovaný cenový koeficient u vstupující proměnné záporný 2. ∆ z (xk) < 0 ↔ zk > 0 – ke snížení hodnoty dojde v případě, že je redukovaný cenový koeficient u vstupující proměnné kladný 3. ∆ z (xk) = 0 ↔ zk = 0 nebo t = 0 – hodnota funkce se nezmění , jestliže je reduk. cen. koeficient roven 0 nebo hodnota vstupující proměnné rovna 0 . Pokud nelze nalézt v daném kroku vstupující proměnnou, která by vedla ke zvýšení (v případě maximalizace) nebo snížení (minimalizace) hodnoty účelové funkce, potom základní řešení obsažené v tomto kroku je řešením optimálním.
Výpočet nového základního řešení Pokud je v nějakém kroku výpočtu porušen test optimality, znamená to, že lze nalézt nové základní řešení, které bude mít lepší hodnotu účelové funkce. Vlastní realizace výpočtu probíhá ve třech krocích: 1. volba vstupující proměnné 2. volba vystupující proměnné 3. přepočet simplexové tabulky tak, aby se vstupující proměnná stala základní a vystupující proměnná nezákladní proměnnou. 1. Volba vstupující proměnné Změna hodnoty účelové funkce v případě, že je proměnná xk proměnnou vstupující, je určena vztahem ∆ z (xk) = -t* zk , kde t je nová hodnota vstupující proměnné. Při výpočtu je samozřejmě snaha o to, aby byla změna účelové funkce co nejvyšší, tzn. aby celý iterační postup směřoval k optimálnímu řešení co nejrychleji. Nejjednodušším postupem je zvolit vstupující proměnnou podle jednotkové změny hodnoty účelové funkce, tzn. podle redukovaných cenových koeficientů zj. Čím vyšší bude v absolutní hodnotě koeficient zj, tím vyšší změnu hodnoty účel. funkce lze očekávat. Při volbě vstupující proměnné je třeba mít na paměti, že ¾ záporné hodnoty zj signalizují možnost zvýšení hodnoty funkce 6
¾ kladné hodnoty zj signalizují možnost snížení hodnoty funkce 2. Volba vystupující proměnné Vystupující proměnnou najdeme tak, že vypočteme minimální podíl transformovaných hodnot pravé strany (βi) a kladných strukturních koeficientů u vstupující proměnné (αik). Tento minimální podíl určuje vystupující proměnnou. Ve výchozí simplexové tabulce bude vstupující proměnnou proměnná x1, u které je redukovaná cena z1 = -20 - na jednu jednotku této proměnné dosáhneme tedy přírůstku hodnoty účel. funkce 20 tis. Kč (u proměnné x2 by byl přírůstek pouze 14 tis. Kč). Pokud bude x1 = t, potom budou nové hodnoty proměnných x3, x4, x5 rovny x3 = 40 - 0,5t ≥ 0 x4 = 60 - 0,5t ≥ 0 x5 = 25
≥0
Zvolíme-li t= min [40/0,5, 60/0,5] = min [80, 120], potom x3 = 0, x4 = 20, x5 = 25 a vystupující proměnnou bude x3. 3. Přepočet simplexové tabulky Vstupující proměnná určuje v simplexové tabulce tzv. klíčový sloupec, vstupující proměnná tzv. klíčový řádek. Průsečíkem klíčového sloupce a řádku je potom klíčový prvek. Výchozí simplexová tabulka našeho příkladu: Přípustné řešení obsažené v této tabulce je charakterizováno vektorem x1 = (0, 0, 40, 60, 25) a hodnota účelové funkce tohoto řešení je z1 = 0.
tabulka 1
V tabulce 1 je vstupující proměnná x1 a vystupující proměnná x3. Pro přepočet simplexové tabulky se použije standardní Gaussova eliminační metoda. Vlastní přepočet je možné realizovat následujícím způsobem: 1.
Transformace klíčového řádku se provede tak, že celý řádek vydělíme klíčovým prvkem a tím získáme na místě klíčového prvku hodnotu 1.
7
2.
Transformace i-tého řádku simplexové tabulky (včetně řádku účelové funkce). Transformovaný klíčový řádek, tj. ten který obsahuje už hodnotu 1 na místě klíčového prvku, vynásobíme hodnotou (-ajk) resp. (-zk) a přičteme k i-tému řádku resp. k řádku účelové funkce. První krok výpočtu simplexovou metodou: klíčový řádek: 1.řádek (tab.2) = 1.řádek (tab.1) / 0,5 = 1.řádek ( tab.1) * 2 2.ř. (tab.2) = 2.ř. (tab.1) +1.ř. (tab.2)*(-0,5) 3.ř. (tab.2) = 3.ř. (tab.1) + 1.ř.(tab. 2) * 0 = 3.ř. (tab1) řádek účelové funkce: 4.ř. (tab.2) = 4.ř. (tab.1) + 1.ř. (tab.2) *20
tabulka 2
Tabulka 2 obsahuje přípustné řešení x2 = (80, 0, 0, 20, 25), které má hodnotu účelové funkce z2 = 1600 [tis. Kč]. Přírůstek účelové funkce vychází skutečně ∆ z (x1) = z2 – z1 = -t* z1 = -80 (-20) = 1600. Řešení x2 není však ještě optimálním řešením úlohy LP. Redukovaná cena z2 = -4 signalizuje, že dojde ke zvýšení účelové funkce, pokud se proměnná x2 stane proměnnou vstupující. Vystupující proměnnou je potom proměnná x4 , u které je minimální podíl βi / αik = 20/0,25 = 80. Přepočet tabulky 2 podle nového klíčového prvku 0,25. klíčový řádek: 2.řádek (tab.3) = 2.řádek (tab.2) / 0,25 = 2.řádek (tab.2) * 4 1.ř. (tab.3) = 1.ř. (tab.2) + 2.ř. (tab.3) * (-0,5) 3.ř. (tab.3) = 3.ř.(tab.2) + 2.ř. (tab.3) * (-0,25) řádek účelové funkce 4.ř. (tab.3) = 4.ř. (tab.2) + 2.ř. (tab. 3) * 4
8
tabulka 3
Tabulka 3 obsahuje řešení x3 = (40, 80, 0, 5) s hodnotou účelové funkce z3 = 1920 [tis. Kč]. Přírůstek hodnoty účelové funkce je zde skutečně ∆ z (x2) = z3 – z2 = -t* z2 = -80 (-4) = 320. Řešení obsažené v tab.3 je již řešením optimálním. Redukované ceny u nezákladních proměnných jsou všechny kladné, tzn. nelze dosáhnout dalšího zvýšení hodnoty účelové funkce. Optimální výrobní program představuje tedy produkci 40 tun směsi Super a 80 tun směsi Standard. Tento program přináší zisk 1 920 000 Kč.
9
Dvoufázová simplexová metoda Tato metoda se používá, jestliže nejsou v úloze lineárního programování všechny omezující podmínky ve tvaru nerovnic „≤“. Potom není získání výchozího základního řešení této úlohy tak snadné a představuje vlastně celou I. fázi výpočtu. Teprve II. fáze výpočtu se potom zabývá optimalizací účelové funkce. Tato fáze je již naprosto shodná s postupem, který byl popsán u jednofázové simplexové metody. Postup výpočtu dvoufázovou simplexovou metodou si ukážeme na jednoduchém numerickém příkladu, ve kterém jsou úmyslně definovány všechny tři možné typy omezujících podmínek.
Příklad: Máme maximalizovat účelovou funkci z = 2x1 + x2 za podmínek 3x1 – x2 ≤ 12 x1 + x2 ≥ 6
(1)
-x1 + 2x2 = 9 x1, x2 ≥ 0 Převedeme-li soustavu omezujících podmínek pomocí přídatných proměnných na ekvivalentní soustavu rovnic, dostáváme v tomto případě soustavu tří rovnic o čtyřech neznámých: 3x1 – x2 + x3 x1 + x2 -x1 + 2x2
= 12 – x4
=6
(2)
=9
Všimněte si způsobu doplňování přídatných proměnných: •
U nerovnic typu „≤“ přídatnou proměnnou k levé straně nerovnice přičítáme. Tato proměnná potom vyjadřuje rozdíl mezi pravou a levou stranou nerovnice – je-li tedy například pravá strana nerovnice kapacita suroviny, která je k dispozici při plánování výrobního programu a levá strana je spotřeba této suroviny, potom přídatná proměnná vyjadřuje nespotřebovanou kapacitu, tj. rozdíl mezi kapacitou a spotřebou. 10
•
U nerovnic typu „≥“ přídatnou proměnnou od levé strany nerovnice odečítáme. V tomto případě vyjadřuje přídatná proměnná rozdíl mezi levou a pravou stranou nerovnice (levá strana nerovnice má být větší nebo rovna pravé straně, musíme tedy od ní přídatnou proměnnou odečíst). Vyjadřuje-li například omezení s nerovnicí „≥“ požadavek na minimální produkci nějakého výrobku, potom hodnota přídatné proměnné představuje, o kolik je v daném výrobním programu uvedený požadavek překročen.
•
Pokud je nějaké omezení zadáno přímo ve tvaru rovnice „=“, potom se přídatná proměnná k modelu samozřejmě nedoplňuje, neboť přídatné proměnné nemají jinou roli než převést soustavu nerovnic a soustavu rovnic. Po doplnění přídatných proměnných do smíšených typů omezujících podmínek však není získaná soustava rovnic v kanonickém tvaru. Z této soustavy tedy nelze přímo získat její základní řešení. Pro získání kanonického tvaru se proto tato soustava rovnic uměle rozšiřuje o další proměnné, které budeme označovat jako pomocné (umělé) proměnné. Ekvivalentní soustavu rovnic rozšířenou o pomocné proměnné budeme označovat jako rozšířenou soustavu rovnic. V našem příkladu má rozšířená soustava rovnic po doplnění pomocných proměnných následující podobu (pomocné proměnné zde označujeme y1, y2): 3 x1 – x1 +
=
9
x2 + x3 x2
= 12 – x4 + y1
=
- x1 + 2 x2
6
(3)
+ y2
Jaká jsou tedy pravidla pro doplňování pomocnýchproměnných U nerovnic typu „≤“ pomocnou proměnnou nedoplňujeme, protože přídatná proměnná přičtená při převodu této nerovnice na rovnici sama o sobě zabezpečuje získání jednotkového vektoru v matici strukturních koeficientů a může se tedy stát v této rovnici základní proměnnou. U omezujících podmínek typu „≥“ a „=“ je třeba pomocnou proměnnou k levé straně nerovnice případně rovnice přičíst. Pomocné proměnné budou v takto získané soustavě rovnic základními proměnnými.
11
Shrnutí způsobu doplňování přídatných a pomocných proměnných pro všechny typy omezujících podmínek přináší tabulka 1.
Tabulka 1 – Doplňování přídatných a pomocných proměnných
Rozšířená soustava rovnic je soustavou v kanonickém tvaru, základní proměnné jsou zde postupně proměnné x3, y1 a y2. Základní řešení této soustavy je dáno vektory x1 = (0, 0, 12, 0) a y1 = (6, 9) – vektor x1 je vektor hodnot strukturních přídatných proměnných, vektor y1 je vektorem hodnot uměle doplněných pomocných proměnných. Dosadíme-li prvky vektoru x1 do soustavy (1) nebo (2), zjistíme však, že řešení rozšířené soustavy rovnic není přípustným řešením dané úlohy LP. Tuto skutečnost dokumentuje tabulka 2.
Tabulka 2 – Hodnoty přídatných a pomocných proměnných
Z tabulky 2 je patrné, že první omezující podmínka je pro řešení x1 splněn. Rozdíl mezi pravou a levou stranou je 12 a to je v tomto případě hodnota přídatné proměnné x3. Druhé omezení splněno není – rozdíl, který zde udává, o kolik toto omezení splněno není, je roven 6. Všimněte si, že se tento rozdíl shoduje s hodnotou pomocné proměnné y1. Podobně je to s omezením posledním – rozdíl udávající míru nesplnění je 9 a to je hodnota pomocné proměnné y2. Přípustné řešení úlohy LP tedy získáme pouze tehdy, budou-li hodnoty všech pomocných proměnných rovny 0. Obsahem I. fáze výpočtu dvoufázovou simplexovou metodou je proto vynulování všech pomocných proměnných rozšířené soustavy rovnic. I. fáze výpočtu může být zakončena dvěma způsoby: Podařilo se vynulovat všechny pomocné proměnné a tím bylo získáno výchozí přípustné řešení (je současně i řešením základním) dané úlohy LP. Výpočet může dále pokračovat optimalizací účelové funkce, tedy II. fází. Pomocné proměnné ve druhé fázi výpočtu už neuvažujeme. Nepodařilo se vynulovat všechny pomocné proměnné. Potom neexistuje řešení, které by vyhovovalo všem omezujícím podmínkám. Úloha LP nemá tedy žádné přípustné řešení a ve výpočtu nemá smysl dále pokračovat. 12
Technicky se může zabezpečit vynulování pomocných proměnných dvěma základními způsoby: 1. Minimalizací pomocné účelové funkce, která je vhodnějším postupem při „ručním“ výpočtu malých úloh LP. 2. Použitím prohibitních cenových koeficientů – tento postup je zpravidla používán v programových systémech pro řešení úloh LP.
Minimalizace pomocné účelové funkce Minimalizaci hodnot pomocných proměnných lze zabezpečit tak, že zkonstruujeme pomocnou účelovou funkci z’, která bude definována jako součet všech pomocných proměnných. Tuto pomocnou účelovou funkce budeme minimalizovat: z’ = Σiyi → min Pokud se podaří získat minimální hodnotu z’ = 0, potom musí být, vzhledem k nezápornosti všech proměnných, všechny pomocné proměnné rovny 0. Tím je získáno výchozí přípustné řešení úlohy LP. Je-li minimum z’ > 0, potom nelze získat řešení, ve kterém by byly všechny pomocné proměnné rovny 0. Úloha LP nemá potom vůbec přípustné řešení.
Příklad: V našem ilustračním příkladu obsahuje rozšířená soustava rovnic dvě pomocné proměnné. Pomocná účelová funkce bude tedy z’ = y1 + y2 → min Ze soustavy (3) je y1 = 6 – x1 – x2 + x4,
y2 = 9 + x1 – 2x2,
takže z’ = y1 + y2 = 6 – x1 – x2 + x4 + 9 + x1 – 2x2 = 15 – 3x2 + x4 V anulovaném tvaru má potom pomocná účelová funkce tuto konečnou podobu z’ + 3x2 – x4 = 15 Výchozí simplexová tabulka rozšířená o pomocné proměnné a o řádek pomocné účelové funkce bude mít následující podobu:
13
Tabulka 3 – Výchozí simplex. tabulka pro dvoufázovou simplex. metodu
V tab. 3 si všimněte, že koeficienty pomocné účelové funkce lze snadno získat i tak, že sečteme řádky, ve kterých jsou pomocné proměnné základními proměnnými (v našem případě 2. 3. řádek tabulky). Ve sloupcích pomocných proměnných jsou však tyto koeficienty vždy rovny 0 (viz předchozí úprava pomocné účelové funkce z’). Při řešení rozšířené úlohy je třeba si uvědomit především: Vstupující proměnná se volí podle redukovaných cenových koeficientů pomocné účelové funkce, kterou vždy minimalizujeme. Klíčový sloupec je tedy určen maximálním kladným koeficientem v řádku z’ – v tab. 3 je proto vstupující proměnná x2. Volba klíčového řádku i přepočet simplexové tabulky se provádí standardním způsobem popsaným v části o jednofázové simplexové metodě – v tab. 3 je vystupující proměnná y2. Řádek původní funkce z se pouze přepočítává jako kterýkoliv jiný řádek v tabulce. V tabulce 4 je dokončena minimalizace pomocné účelové funkce. Ve dvou iteracích je nejprve vypočteno řešení x2 = (0, 9/2, 35/2, 0), y2 = (3/2, 0) s hodnotou funkce z2 = 9/2 a z’2 = 3/2 a potom řešení x3 = (1, 5, 14, 0), y3 = (0, 0) s hodnotou funkce z3 = 7 a z’3 = 0. Řešení x3, y3 je již optimálním řešením rozšířené úlohy. Vzhledem k tomu, že je v tomto řešení hodnota pomocné účelové funkce rovna 0, je řešení x3 současně výchozím základním řešením původní úlohy lineárního programování.
14
Tabulka 4 – I. fáze – minimalizace pomocné účelové funkce z‘
Nalezením výchozího přípustného řešení končí I. fáze výpočtu dvoufázovou simplexovou metodou. Ve výpočtu se poté pokračuj II. fází, která spočívá v optimalizaci původní účelové funkce z. II. fáze výpočtu našeho příkladu je ilustrována v tabulce 5. Všimněte si, že v této tabulce již nejsou obsaženy pomocné proměnné, které lze po jejich vynulování z modelu vyloučit, ani pomocná účelová funkce. Vzhledem k maximalizaci funkce z není řešení x3 = (1, 5, 14, 0) s hodnotou účelové funkce z3 = 7 řešením optimálním. Hodnotu účelové funkce lze zlepšit tak, že zvolíme jako vstupující proměnnou x4 – vystupující proměnná je potom x3 (viz tab. 5). Po přepočtu simplexové tabulky podle klíčového prvku (5/3) získáme řešení x4 = (33/5, 39/5, 0, 42/5) s hodnotou účelové funkce z4 = 21. Nalezením řešení x4 končí II. fáze výpočtu, neboť toto řešení je již hledaným optimálním řešením dané úlohy LP.
Tabulka 5 – II. fáze – optimalizace účelové funkce z
Celý postup výpočtu, který je obsažený v tabulkách 3 – 5, je ilustrován graficky na obrázku. Na tomto obrázku je zvýrazněn množina přípustných řešení – je to v tomto případě pouze jedna hrana mezi body x3 a x4. V I. fázi výpočtu (tab. 4) jsme vycházeli z řešení x1 a ve dvou iteracích jsme přešli přes řešení x2, které také není 15
přípustné, k řešení x3. Tím skončila I. fáze, neboť řešení x3 je již řešením přípustným. Ve II. fázi se v jedné iteraci vypočte optimální řešení x4.
Obrázek – Množina přípustných řešení
16
Použití prohibitních cenových koeficientů Místo zavedení pomocné účelové funkce lze dosáhnout efektu minimalizace hodnot pomocných proměnných i jiným, relativně jednodušším způsobem. Účelová funkce z se doplní o pomocné proměnné, kterým se však přiřadí maximálně nevýhodné cenové koeficienty ±M: +M v případě minimalizace a –M při maximalizaci funkce z, kde M je ve srovnání s ostatními cenovými koeficienty dostatečně velké kladné číslo. Vzhledem k nevýhodnosti prohibitních cen u pomocných proměnných budou tyto proměnné prioritně zvoleny jako vystupující a bude tedy dosaženo podobného efektu jako při použití pomocné účelové funkce. Použití prohibitních sazeb není, ve srovnání s pomocnou účelovou funkcí, z hlediska „ručního“ výpočtu výhodnější. Tento postup je však používán v většině programových produktů.
Příklad: Pro ilustraci uvedeného postupu zapíšeme výchozí simplex. tabulku s účelovou funkcí upravenou pomocí prohibitních saze. V našem příkladu bude vypadat tato funkce následovně: z = 2x1 +x2 –My1 – My2 Pokud však zapíšeme funkci do simplexové tabulky, budou u pomocných proměnných (které jsou proměnnými základními) porušeny jednotkové vektory (v řádku z nejsou nulové koeficienty ale sazby M). Z tohoto důvodu je třeba dále tuto tabulku upravit tak, že řádky obsahující pomocné proměnné vynásobíme hodnotou (-M) a přičteme k řádku z. Výchozí simplexová tabulka pro náš příklad je v tabulce 6. Další výpočet se realizuje už standardním způsobem s tím, že se počítá samozřejmě pouze s upravenou účelovou funkcí. Podle této funkce se zvolí klíčový sloupec (z2 = -3M – 1) – vystupující proměnná určená klíčovým řádkem je potom y2. Tuto proměnnou lze tedy vyloučit a v dalším průběhu výpočtu nemusí být už uvažována.
Tabulka 6 – použití prohibitních sazeb
17
Duální úloha Teorie duality Dualitou v úlohách lineárního programování se rozumí vzájemný vztah dvojice přesně d e f i n o v a n ý c h ú l o h l i n e á r n í h o p r o g r a m o v á n í . Ke každé úloze lineárního programování lze zformulovat podle definice, kterou uvedeme dále, jinou úlohu lineárního programování. První z nich budeme označovat jako ú l o h u p r i m á r n í , druhou potom jako ú l o h u d u á l n í .
Uvedené označení však svádí k tomu, že duální úloha je v jakémsi podřízeném stavu k úloze primární, neboť je z ní odvozena. Takové chápání duality by nebylo správné . Je třeba se uvědomit, že d u a l i t a je vzájemným symetrickým vztahem obou úloh. Pokud tedy budeme aplikovat proces transformace jedné úlohy na druhou dvakrát po sobě, potom dostáváme zpět původní primární úlohu:
primární úloha transformace duální úloha transformace primární úloha Místo označení primární a duální úloha lze použít termín d v o j i c e duálně sdružených úloh.
Praktický význam duality spočívá v tom, že vlastnosti duálních modelů a vztahy mezi duálně sdruženými úlohami se využívá při
18
speciálních algoritmech pro řešení úloh LP. Velký význam má dualita i v etapě ekonomické interpretace výsledků řešení.
Úlohy souměrně duálně sdružené (souměrná dualita)
Principy konstrukce duálních úloh
Mějme úlohu lineárního programování ve tvaru I
I Za podmínek a11x1 + a12x2 + ................ + a1nxn ≤ b1 a21x1 + a22x2 + ................ + a2nxn ≤ b2 ............................................................. am1x1 + am2x2 + ................ + a mnxn ≤ bm xj ≥ 0, j = 1,2, ...., n
, , , (1) ,
nalézt maximum funkce z = c1x1 + c2x2 + ................ + cnxn ,
Tuto úlohu nazveme p r i m á r n í .
Když každému omezení primární úlohy (1) přiřadíme jednu duální proměnnou ui i =1,2, ...,m,
můžeme formulovat d u á l n í ú l o h u ve tvaru II
II 19
Za podmínek a11u1 + a21u2 + ................ + am1um ≥ c1 a12u1 + a22u2 + ................ + a2mum ≥ c2 ............................................................. a1nu1 + a2nu2 + ................ + amnum ≥ cn ui ≥ 0, i =1,2, ..., m
, , , (2) ,
nalézt minimum funkce w = u1b1 + u2b2 + ................ + umbm ,
Úlohy (1) a (2). jsou tzv. symetrické duální úlohy. Vztah duality je vztahem vzájemným, neboť kterákoliv z těchto úloh může být vzata jako primární a naopak. Duální úloha má n omezení,k tedy tolik, kolik má primární úlohy proměnných, a m proměnných, tedy tolik, kolik má primární úloha omezení.
Definice:
V maticovém vyjádření mají symetrické duální úlohy tento tvar:
I. Primární model
II. Duální model
z = cTx Æ max.,
w = uTb Æ min.,
za podmínek Ax ≤ b, x ≥ 0.
za podmínek ATu ≥ c, u ≥ 0.
20
kde: cT = (c1, c2, . . . . c n) je n-složkový řádkový vektor cenových koeficientů x = (x1, x2, . . . . x n) T strukturních proměnných
je n-složkový sloupcový vektor modelu
b = (b1, b2, . . . . b m) T koeficientů pravé strany
je m-složkový sloupcový vektor
A
matice strukturních koef. o rozměru m n
W modelu
hodnota účelové funkce duálního
u = (u1, u2, . . . . u m) T proměnných duálního
je m-složkový sloupcový vektor modelu
Při zápisu pomocí sumací v matematickém modelu duálně sdružených úloh vypadá definice souměrné duality následovně: n
∑
=
z
c
j
j = 1
n
∑
a
j = 1
x
j
ij
x
≤
j
x
b
≥ 0 , j = 1 , 2 ,...,
→
j
i
, i =
max
1 , 2 ,...,
m
n
Primární model: Duální model: Z obou zápisu je naprosto zřejmé, že v duálním modelu jsou obsaženy stejné koeficienty jako v modelu primárním - samozřejmě s výjimkou vektorů x a u, které označují vektor proměnných primárního a duálního modelu. u m
∑
i = 1
i
≥ 0 , i = 1 , 2 ,...,
a
ij
u
i
≤ c
j
m
, j = 1 , 2 ,...,
n .
Při formulaci duálního modelu je třeba vycházet z výše uvedené definice.
21
Prvním důležitým krokem při této formulaci je převod primárního matematického modelu na tvar, který je uveden v definice, tzn.: při maximalizaci účelové funkce z je třeba převést všechna vlastní omezení úlohy na typ „ ≤ “ . při minimalizaci účelového funkce z je třeba všechna vlastní omezení úlohy na typ „≥“. Po této úpravě je už vlastní formulace duální úlohy velmi jednoduchá: ke každému vlastnímu omezení primární úlohy přiřadíme jednu duální proměnnou ui, i=1,2,..,m - každé z těchto proměnných je přiřazena podmínka nezápornosti. ke každé proměnné xj, j=1,2,...,n primární úlohy přiřadíme vlastní omezení duální úlohy - koeficienty tohoto omezení jsou určeny j-tým sloupcem matice A, typ všech omezení musí opět korespondovat s extrémem účelové funkce w („≤“ v případě maximalizace a „≥“ v případě minimalizace), koeficienty pravé stany v duální úloze jsou shodné s koeficienty účelové funkce primární úlohy a naopak koeficienty účelové funkce duální úlohy jsou shodné s koeficienty pravé strany primární úlohy, extrém účelové funkce se mění z maximalizace na minimalizaci, případně naopak.
Příklad: Formulace souměrně sdruženého duálního modelu: 0,5 x1 + 0,25 x2 ≤ 40 0,5 x1 + 0,5 x2 ≤ 60 0,25 x2 ≤ 25 z = 20 x1 + 14 x2 Příslušný duální model bude mít tři duální proměnné a dvě duální vlastní omezení.
22
Formulace uvedena v tabulce - 1:
Primární model z = 20 x1 + 14 x2
→
Duální model max
W = 40 u1 + 60 u2 + 25 u3 min
0,5 x1 + 0,25 x2 ≤ 40
u1 ≥ 0
0,5 x1 + 0,5 x2 ≤ 60
u2 ≥ 0
0,25 x2 ≤ 25
u3 ≥ 0
x1 ≥ 0
0,5 u1 +0,5 u2 ≥ 20
x2 ≥ 0
0,25 u1 + 0,5 u2 +0,25u3 ≥ 14
→
Tabulka 1 - Formulace souměrného duálního modelu
Z tabulky je patrné, že je každému vlastnímu omezení jedné úlohy přiřazena podmínka nezápornosti úlohy druhé a naopak každé proměnné s podmínkou nezápornosti je přiřazeno v druhé úloze vlastní omezení. Dostáváme tak tedy v našem příkladu pět řádků (kromě řádku obsahujícího účelové funkce obou úloh (1. řádek)), z nichž každý obsahuje vlastní omezení jedné úlohy a podmínku nezápornosti úlohy druhé. V každém řádku je tedy dvojice omezujících podmínek - vlastní omezení jedné úlohy a podmínka nezápornosti úlohy druhé. Tyto dvojice budeme dále označovat jako dvojice duálně sdružených omezení.
Mezi řešeními sdružených úloh platí zajímavé vztahy. Hodnota účelové funkce libovolného řešení primární úlohy nemůže být větší než hodnota účelové funkce libovolného řešení duální úlohy. Hodnota účelové funkce duální úlohy (minimalizační) je tedy horní mezí pro hodnotu účelové funkce primární úlohy (maximalizační). Jestliže nalezneme taková přípustná řešení obou úloh, jejichž hodnoty účelových funkcí se rovnají, pak jsou to řešení optimální.
23
Věty o dualitě:
Věta 1. Je-li x libovolné přípustné řešení primární úlohy a u libovolné přípustné řešení duální úlohy, platí, cTx ≤ bTu. Důkaz: Vynásobíme vlastní omezení primární úlohy vektorem u a vlastní omezení duální úlohy vektorem x: uTAx ≤ uTb
⇒c x≤u b T
T
uTAx ≥ cTx
Věta 2. Je-li x přípustné řešení primární úlohy a u přípustné řešení duální úlohy, pro něž
cTx = bTu, pak x a u jsou optimální řešeními obou úloh. Důkaz: Označíme přípustná řešení sdružených úloh, jejichž hodnoty účelových funkcí se rovnají, x0 a u0. T
T
Platí-li c x0 = b u0, potom z věty plyne pro libovolné přípustné T T řešení primární úlohy c x ≤ u 0 b, tj. cTx = cTx0 a pro libovolné T T T T přípustné řešení duální úlohy u b ≥ c x0, tj. u b ≥ b u0. Je tedy x0 optimálním řešením primární úlohy a u0 optimálním řešením duální úlohy. Kromě těchto dokázaných vztahů, platí mezi řešeními sdružených úloh i další vztahy.
24
Věta 3. Mají-li obě sdružené úlohy optimální řešení, pak se optimální hodnoty účelových funkcí obou úloh sobě rovnají.
25
Úlohy nesouměrně duálně sdružené (nesouměrná dualita) Při definici souměrné duality jsme uvažovali pouze vlastní omezení ve tvaru nerovnic " ≥ " nebo " ≤ ". V úlohách lineárního programování se však vyskytují i vlastní omezení ve tvaru rovnic. Jakým způsobem modifikuje výskyt takových omezení formulaci duální úlohy bude ukázáno nyní: V následujícím příkladu jsou v soustavě vlastních omezení obsaženy všechny tři možné typy omezení - tj. jedna nerovnice " ≤ " a druhá " ≥ " a jedna rovnice:
Příklad: 3 x1 -
x2 ≤ 12 x1 + x2 ≥
6
-x1 + 2x2 = 9 z = 2x1 + x2 Vzhledem k maximalizaci účelové funkce z = 2x1 + x2 je třeba převést nejprve všechna vlastní omezení na typ " ≤ ". Nerovnici x1 + x2 ≥ 6 stačí vynásobit (- 1). Rovnici -x1 + x2 = 9 je možné nahradit dvěma nerovnicemi: -x1 + 2x2 ≤ x1 -2 x2
9
≥ -9
Původní soustava tří vlastních omezení se tak rozšiřuje o jedno další omezení s tím , že původní rovnici přísluší dvě vlastní omezení v rozšířené soustavě. Duální proměnné příslušející těmto dvěma vlastním omezením označíme u3´ a u3´´, protože obě přísluší shodnému původnímu vlastnímu omezení (rovnici). Formulace duálního modelu příslušejícího této rozšířené soustavě vlastních omezení je uvedena v tabulce -2 - v tomto případě se jedná o s o u m ě r n o u d u a l i t u.
26
Primární model z = 2 x1 + x 2
→
Duální model
max
W = 12 u1 - 6 u2 + 9*( u3 ´- u3 ´´) min
3 x1 -
x2
≤ 12
u1 ≥ 0
- x1
x2
≤-6
u2 ≥ 0
- x 1 + 2 x2
≤ 9
u3 ´ ≥ 0
x1 + 2 x2
≤ -9
u3 ´ ≥ 0
-
x1 ≥ 0
3 u1 - u2 -
x2 ≥ 0
- u1 - u2 +2* (u3 ´- u3 ´´) ≥ 1
→
(u3 ´- u3 ´´) ≥ 2
Tabulka 2 -Formulace souměrného duálního modelu
Nyní budeme formulovat duální úlohu k nerozšířenému modelu, tj. k modelu, ve kterém ponecháme třetí omezující podmínku ve tvaru rovnice. Této rovnici přiřadíme duální proměnnou u3 . Vzhledem k extrému účelové funkce musíme i zde vynásobit druhou nerovnici hodnotou (-1), abychom toto omezení převedli na typ " ≤ ". Formulace opět uvedena v tabulce:
Primární model = 2 x1 + x2
Duální model max
3 x1 -
x2
≤ 12
- x1
x2
≤-6
- x 1 + 2 x2
= 9
-
W = 12 u1 - 6 u2 min
+ 9 u3
u1 ≥ 0 u2 ≥ 0 u3 - libovolné
27
x1 ≥ 0
u3
≥ 2
- u 1 - u 2 + 2 u3
≥ 1
3 u1 - u2 x2 ≥ 0
Tabulka 3 -Formulace nesouměrného duálního modelu Duální modely v tabulce 2 a 3 jsou téměř shodné - hlavní rozdíl spočívá v tom, že je proměnná u3 z tabulky 3 nahrazena v tabulce 2 ( v souměrném modelu) rozdílem dvou proměnných (u3´ - u3´´). Duální proměnná u3 byla přiřazena vlastnímu omezení - x1 + 2 x2 = 9 a proměnné u3´ a u3´´ příslušely dvojici omezujících podmínek odvozených z uvedené rovnice. Pro všechny podmínky v souměrné dualitě - tedy i pro proměnné u3´ a u3´´ platí podmínky n e z á p o r n o s t i . Pro proměnnou u3 = u3´ - u3´´, která je definována jako rozdíl dvou nezáporných hodnot však z pochopitelných důvodů podmínka nezápornosti platit nemůže - rozdíl dvou nezáporných hodnot může být stejně tak kladný, záporný nebo nulový. Z tohoto důvodu platí, že duální proměnné příslušející vlastním omezením ve tvaru rovnice nejsou omezeny podmínkami nezápornosti.
Obecná definice nesouměrné duality I. Maximalizovat funkci funkci
II. Minimalizovat
z = cTx,
w = uTb ,
za podmínek
za podmínek ATu ≥ c,
Ax = b, X≥0
u - libovolné
Nesouměrnost spočívá v tom , že dvojice duálně sdružených omezení nejsou v tomto případě "kompletní". V souměrné dualitě tyto dvojice obsahovaly vždy vlastní omezení ve tvaru nerovnice v jedné úloze a podmínku nezápornosti v úloze druhé. V nesouměrné dualitě nepřísluší vlastnímu omezení ve tvaru rovnice v jedné úloze žádná omezující podmínka v úloze druhé (příslušná proměnná může být libovolná).
28
Řešení duálně sdružených úloh Pro nalezení optimálního řešení dvojice duálně sdružených úloh lze použít, vzhledem k tomu, že se v obou případech jedná o standardní úlohy lineárního programování, simplexovou metodou. Každou z obou duálně sdružených úloh lze tedy řešit samostatně simplexovou metodou
Příklad: Optimální řešení duálně sdružených úloh V kožedělném závodě se vyrábějí 3 druhy výrobků, na než se spotřebovávají 2 druhy surovin (kůží), jejichž disponibilní množství nelze zvýšit na udanou mez. Je třeba určit výrobní program maximální výši zisku. Potřebné údaje jsou v tabulce 4. Formulace primární úlohy: 0,2x3 ≤ 3000
0,2 x1 +
0,25 x2 + 0,3x3 ≤ 4200 xj ≥ 0 (j = 1, 2, 3 ) z = 12 x1 + 11 x2 +26 x3
→
MAX.
Formulace duální úlohy k primární úloze: ≥12
0,2 u1
0,25 u2 ≥11 0,2 u1 +
0,3 u2
≥26
ui ≥ 0 (i = 1, 2) w = 3000 u1 + 4200 u2
→
MIN.
Obě úlohy převedeme na standardní tvar pomocí přídatných proměnných. U duální úlohy přidáme kromě přídatných proměnných i proměnné pomocné (yi))
Pozn.: U omezujících podmínek typu „≥“ a "=" je třeba pomocnou proměnnou k levé straně nerovnice případně rovnice přičíst. Pomocné
29
proměnné budou v takto získané soustavě rovnic základními proměnnými.
Řešíme simplexovou metodou: V části simplexové tabulky obsahující poslední iteraci výpočtu jedné ze sdružených úloh je i řešení druhé úlohy. Z tabulky 5 (3. Iterace) lze tedy vyčíst i optimální řešení duální úlohy uT= [60, 140/3] ( je v posledním řádku tabulky pod přídatnými proměnnými, jejichž koeficienty vytvořily jednotkovou matici 1. Iterace). Hodnoty přídatných proměnných lze zjistit rovněž z posledního řádku tabulky 3. Iterace. Jsou zapsány ve sloupcích původních strukturních proměnných u3 = 0, u4 = 2/3, u5 = 0. I obráceně lze z tabulky řešení duální úlohy zjistit řešení úlohy sdružené (tj. primární). Tedy optimální řešení primární úlohy z tabulky 6 (duální řešení) je xT = [1000, 0, 14000, 0, 0] z = 12 x1 + 11 x2 +26 x3 z = 12*1000+26*14000 = 376 000 w = 3000 u1 + 4200 u2 w = 3000*60 + 4200*140/3 = 376 000
Strukturní duální proměnné můžeme interpretovat jako ocenění jedné jednotky kapacity ve vztahu k hodnotě účelové fce. Jedná se tedy o marginální ocenění kapacit. Někdy se strukturní duální proměnné označují jako stínové ceny. Hodnoty duálních proměnných je třeba uvažovat pouze v rámci určitých intervalů stability pro hodnoty pravé strany b. Vlastní výpočet intervalů stability: b1 + ∆b1 Bs-1
b2
≥0
: : bm Bs-1
je inverzní matice báze v s-tém kroku výpočtu,
30
bi i = 1, 2, ….,m jsou prvky vektoru pravých stran ∆bi je hledaná přípustná změna pro hodnotu bi
31
Celočíselné programování Mezi speciální úlohy lineárního programování (LP) lze zařadit i úlohy celočíselného (lineárního) programování. Jedná se o standardní úlohy LP, které jsou však doplněny o tzv. podmínky celočíselnosti, (zabezpečují, aby všechny nebo některé proměnné nabývaly pouze celočíselných hodnot). Tyto podmínky vyplývají ze zadaného problému. Kromě obecných celočíselných podmínek se mohou v úlohách LP vyskytovat podmínky, aby proměnné nabývaly pouze hodnot 0 nebo 1, takové proměnné se označují jako bivalentní proměnná.Tyto proměnné se používají i při formulaci přiřazovacího a okružního dopravního problému, což jsou úlohy celočíselného programování. Úlohy celočíselného programování, které obsahují pouze bivalentní proměnné se označují jako úlohy bivalentního programování. Úlohy celočíselného programování je možné klasifikovat podle různých hledisek. Jeden způsob klasifikace rozděluje tyto úlohy na úlohy s obecnými podmínkami celočíselnosti a na bivalentní úlohy tak, jak bylo uvedeno výše. Jiná klasifikace vychází z toho, zda jsou kladeny podmínky celočíselnosti na všechny proměnné modelu nebo pouze na jejich podmnožinu – v prvním případě se hovoří o ryze celočíselných, ve druhém o smíšeně celočíselných úlohách LP. (Řešení těchto úloh je většinou velmi náročné, nejenom na výpočet, ale i z časového hlediska.)
32
Metody řešení úloh celočíselného programování se dělí do několika skupin podle jejich charakteru: 1. Metody řezných (sečných) nadrovin jsou vhodné pro řešení ryze i smíšené celočíselných úloh, ve kterých jsou uvažovány obecné podmínky celočíselnosti. Nejsou vhodné pro řešení bivalentních úloh. Tyto metody vychází z množiny přípustných řešení úlohy bez podmínek celočíselnosti. Pro tuto množinu je vypočteno běžnou simplexovou metodou optimální řešení. Pro takto zúženou množinu je opět vypočteno optimální řešení. Po konečném počtu kroků vede tento postup k získání řešení. 2. Kombinatorické metody jsou univerzálním nástrojem pro řešení většiny typů úloh. Podstatou těchto metod je jejich efektivní prohledávání. Bližší obecný popis metod typu není možný, protože výpočetní realizace je u jednotlivých metod poměrně odlišná. 3. Speciální metody obsahují např. maďarskou metodu (pro výpočet optimálního řešení přiřazovacího problému nebo speciální přibližné algoritmy pro řešení okružního dopravního problému).
Množinu přípustných řešení a postup výpočtu optima budeme ilustrovat na příkladu. Máme tedy úlohu maximalizovat z = 2x1 + 3x2
za podmínek
Grafické znázornění:
4x1 + 3x2 ≤ 13 x1 + 2x2 ≤ 6 x1, x2 ≥ 0 x1, x2 - celé
:
Obr. 1.1 – množina přípustných řešení úlohy celočíselného LP
Grafické znázornění množiny přípustných řešení této úlohy je na obr. 1.1. Stínování vyjadřuje množinu přípustných řešeni bez podmínek celočíselnosti. Mřížka diskrétních bodů reprezentuje celočíselné řešení, těchto bodů je v tomto případě 10. Je zřejmé, že optimální řešení neceločíselné úlohy je dáno vektorem xopt = (8/5, 11/5),
33
hodnota účelové funkce tohoto řešení je zopt = 49/5. Jakékoli zaokrouhlení, což je často první myšlenka, která vzniká při pokusu získat celočíselné řešení, nevede k uspokojivým výsledkům. Jakýmkoliv zaokrouhlením vektoru xopt nelze získat optimální řešení. Toto řešení (jak po chvíli zjistíme) je xopt = (0,3) s hodnotou účelové funkce zopt = 9. V profesionálních programových systémech se pro řešení celočíselných úloh LP používají nejčastěji tzv. metody větvení a mezí. Tento princip je dostatečně obecný, takže jej lze použít na mnoho úloh. Těchto metod je ovšem docela dost, proto se zmíníme konkrétně o jedné - je to metoda autorek Land a Doig. Lze ji použít pro řešení jak ryze, tak i smíšeně celočíselných úloh LP, ale předpokládejme zde, že koeficienty účelové funkce jsou vždy celá čísla. Prvním krokem uvedené metody je, že se standardním postupem vypočte optimální řešení bez podmínek celočíselnosti. Označme si vektor tohoto řešení x° = (x1°, x2°, ...x n°) a jeho hodnotu účelové funkce z°. Pokud takto vypočtené řešení vyhovuje podmínkám celočíselnosti, pak je to optimální řešení a výpočet končí. V opačném případě se z množiny X° vytvoří dvě podmnožiny - X1, X2 ( což označujeme jako větvení velké množiny na dvě podmnožiny), z vektoru x° se vybere libovolně jedna proměnná, která porušuje podmínku celočíselnosti (nechť se jedná o proměnnou xk , jejíž hodnota je ve vektoru x° rovna xk0). MnožinaX1 je charakterizována rozšířením o podmínku [xk0] + l, množina X2 je vytvořena z množiny X° rozšířením o podmínku ≤ [xk0]
xk ≥
xk ,
kde [xk0] představuje celou část z hodnoty xk0. Je-li tedy složka xk0 = 8/5, pak je množina X1 určena podmínkou xk ≥ [8/5] + 1 = 2 a množina X2 podmínkou xk ≤ [8/5] = l. V každé z obou větví je vypočteno optimální řešení bez uvažování podmínek celočíselnosti a proces větvení v případě potřeby pokračuje dále podobné jako u množiny X0. Součástí uvedeného algoritmu dále je, že je v každé větvi odvozována horní mez pro hodnotu účelové funkce celočíselného řešení. Např. na naší množině X° je optimální řešení určeno vektorem x° s hodnotou účelové funkce z° = 49/5. Protože je to jediné optimální, řešení na množině X°, je zřejmé, že ryze celočíselné řešení nemůže mít hodnotu účelové funkce vyšší než [49/5] = 9. Horní mez na množině X0 je tedy rovna 9. U ryze celočíselných úloh lze získat horní mez pro hodnotu celočíselného řešení na množině Xk jako [zk - ε ], kde zk je optimální hodnota neceločíselného optima na množině Xk a ε je dostatečné
34
malé ( 10-9) kladné číslo. U smíšeně celočíselných úloh je však horní mez v dané větvi rovna přímo vypočtené hodnotě účelové funkce. Celý tento proces se provádí tak dlouho, pokud všechny vytvořené větve nejsou uzavřeny jedním z následujících způsobů: 1. 2. 3.
Ve větvi je nalezeno řešení, které vyhovuje podmínkám celočíselnosti Ve větvi neexistuje žádné přípustné řešení Ve větvi je nalezeno neceločíselné řešení a horní mez pro hodnotu účelové funkce, odvozená z tohoto řešení, je nižší než hodnota účelové funkce nějakého řešení, nalezeného již dříve v některé z ostatních větví. Po uzavření všech větví je nejlepší nalezené celočíselné řešení současně hledaným optimálním řešením celočíselné úlohy.
Příklad: Postup výpočtu celočíselného optima metodou Land a Doig budeme ilustrovat na výše uvedeném numerickém příkladu. K lepšímu pochopení algoritmu uvádíme na obr. 1.2 a 1.3. jednak grafické znázornění způsobu dělení původní množiny přípustných řešení X0 na podmnožiny v jednotlivých větvích a optimální řešení získané na těchto podmnožinách (x0,x1,...,x4) a jednak graf řešení, která schématicky znázorňuje postup výpočtu.
Obr. 1.2 - Výpočet celočíselného optima metodou větvení a mezí
Prvním krokem výpočtu je nalezení optimálního řešení na množině X0. To je na celé množině přípustných řešení bez podmínek celočíselnosti. Toto řešení je dáno vektorem x0 = (8/5 , 11/5) s hodnotou účelové funkce z0 = 49/5. Horní mez je = 9. Pro větvení vybereme např. první neceločíselnou složku vektoru x0 a z původní množiny X0 vytvoříme dvě podmnožiny X1 a X2 tak, že soustavu omezujících podmínek rozšíříme o x1 ≥ [8/5]+1 = 2 a o x1 ≤ [8/5] = 1 viz obr 1.3. Množiny X1 a X2 jsou na obr 1.2. zvýrazněny stínováním.Na obou těchto množinách je vypočteno optimální řešení. Tato řešení jsou určena vektory x1 = (2, 5/3) a x1 = (1, 5/2). Jejich hodnoty z1 = 9 a z2 = 19/2. Na podmnožinách odvozených z X1 nelze 35
tedy získat celočíselné řešení, které bude mít hodnotu účelové funkce vyšší než 8 (horní mez je 8). Na množině X2 je horní mez rovna [19/2] = 9.
x0
x0 = (8/5; 49/5) Z0 = 49/5
x1; x1 ≥ 2
8
x2; x2 ≤ 1
9
x2 = (1, 5/2) z2 = 19/2
x1 = (2; 5/3) x1= 9
x4; x2 ≥ 3
x3; x2 ≤ 2
x4 = (0,3) Z4 = 9
x3 = (1,2) z3 = 8
STOP
STOP
Obr. 1.3 – Graf řešení metodou větvení a mezí
Ani jedno řešení x1 a x2 není celočíselné, pro další větvení vybereme větev X2, protože hodnota horní meze je větší než na X1, proto lze očekávat získání řešení s vyšší hodnotou účelové funkce. Z X2 vytvoříme podmnožiny X3 a X4 tak, že doplníme o podmínky x2 < [5/2] = 2 a x2 ≥ [5/2] + 1 = 3. Na obou podmnožinách získáváme již 36
celočíselné řešení, konkrétně se jedná o řešeni x3 = (1,2) s hodnotou účelové funkce z3 = 8 a x4 = (0,3) s hodnotou účelové funkce z4 = 9. Tímto lze větvení ukončit (viz pravidlo l). Tedy nejlepší nalezené řešení je x4 = (0,3) s hodnotou z4 = 9. Pro doplnění uvedeme Gomoryho metodu, která patří do skupiny metod řezných nadrovin, ale pouze v nejjednodušší verzi určenou pro řešení ryze celočíselných úloh. První vypočteme simplexovou metodou řešení bez podmínek celočíselnosti. Pokud splňuje toto řešení podmínky celočíselnosti, je to optimální řešení celočíselné úlohy a výpočet může skončit. V opačném případě se k soustavě podmínek doplňuje nové omezeni - řezná nadrovina. Předpokládejme, že základní proměnná v i-tém řádku simplexové tabulky porušuje podmínku celočíselnosti. Nové omezení bude mít následující podobu:
∑ (-rij)xj + xn+1 = -ri0 kde j = 0, 1,...,n rij – jsou celočíselné zbytky strukturních koeficientů i-tého řádku simplexové tabulky, ri0 – je celočíselný zbytek hodnoty prvé strany v i-tém řádku tabulky , tj. hodnoty základní proměnné, která porušuje podmínky celočíselnosti xn+1 – ji přídatná proměnná doplněná k tomuto novému omezení Celočíselný zbytek je vždy číslo z intervalu <0,1). Pro ilustraci celočíselný. zbytek 8/5 je 3/5, protože 8/5 = 1+3/5 a celočís. zbytek čísla -8/5 je 2/5, protože 8/5= -2+2/5. Po doplnění řezné nadroviny do simplexové tabulky dostáváme v této tabulce primárně nepřípustné řešení. Ve výpočtu pokračujeme duálně simplexovou metodou. Po nalezení optima se situace opakuje - buď je celočíselné, nebo se k soustavě omezení doplní další řezná nadrovina stejným způsobem. Po konečném počtu kroků konverguje tento postup k optimálnímu řešení. Ovšem v každém kroku se rozšiřuje soustava o jedno nové omezení (řádek) a novou proměnnou (sloupec). Vzhledem k tomu, že počet kroků může být i u malých úloh značný, může se i do značných rozměrů rozrůst původní problém. S tím souvisí i potenciální výpočetní problémy.
37
Příklady • Celočíselné optimum • Graf řešení • Optimální řešení neceločíselné úlohy • Gomoryho metoda • Optimální řešení
38
Celočíselné optimum Výpočet celočíselného optima metodou větvení a mezí m
Graf rešení Grafické řešení metodou větvení a mezí x0
x0 = (8/5; 49/5) Z0 = 49/5
x1; x1 ≥ 2
8
x2; x2 ≤ 1
9
x2 = (1, 5/2) z2 = 19/2
x1 = (2; 5/3) x1 = 9
x3; x2 ≤ 2
x4; x2 ≥ 3
39
x3 = z3 = 8
x4 = (0,3) Z4 = 9
(1,2)
STOP
STOP
Postup výpočtu celočíselného optima budeme ilustrovat na stejném numerickém příkladu jako předchozí metodu větvení a mezí. Předpokladem pro použití Gomoryho metody je znalost optimálního neceločíselného řešení.
Optimální řešení neceločíselné úlohy Toto řešení pro náš příklad je uvedeno v tabulce: Základní proměnná X1 X2 X3
X4
Bi
X1
1
0
2/5 -3/5 8/5
X2
0
1 -1/5 4/5 11/5
Zj
0
0
1/5 6/5 49/5
Toto řešení nesplňuje podmínky celočíselnosti. Vybereme řádek s první neceločíselnou hodnotou základní proměnné (x1 = 8/5) a podle něj zkonstruujeme nové omezení – řeznou nadrovinu: 0*x1 – 0*x2 – 2/5x3 – 2/5x4 + x5 = - 3/5, kde x5 je přidaná proměnná příslušející tomuto novému omezení. O nové omezení rozšíříme předchozí tabulku a ve výpočtu budeme pokračovat jedním krokem duálně simplexové metody. Tento krok je uveden zde:
Gomoryho metoda První krok výpočtu Gomoryho metody
40
X1
X2
X3
X4
X5
Bi
X1
1
0
2/5
-3/5
0
8/5
X2
0
1
-1/5
4/5
0
11/5
X5
0
0
-2/5
-2/5
1
-3/5
Yj
0
0
1/5
6/5
0
49/5
X1
1
0
0
-1
1
1
X2
0
1
0
1
-1/2
5/2
X3
0
0
1
1
-5/2
3/2
Zj
0
0
0
1
1/2
19/2
Toto řešení není celočíselné. Pokračujeme dále. Vybereme opět řádek s první neceločíselnou hodnotou základní proměnné (x2 = 5/2) a podle něj vytvoříme nové omezení: -1/2x5 + x6 = -1/2, kde x6 je další přidaná proměnná. Po doplnění tohoto omezení do tabulky a po provedení výpočtu jedním krokem duálně simplexové metody dostáváme již celočíselné řešení. Optimální celočíselné řešení je tedy charakterizované vektorem xc = (0, 3, 4, 1) a hodnotou účelové funkce xc = 9. Ve vektoru xc jsme neuvedli hodnoty proměnných x5, x6 tj. přidaných proměnných dvou nově doplněných omezení (řezných nadrovin). Tyto proměnné totiž nemají ve vztahu k původnímu modelu žádnou interpretaci.
Optimální řešení
X1
X2
X3
X4
X5
X6
Bi
X1
1
0
0
-1
1
0
1
X2
0
1
0
1
-1/2
0
5/2
41
X3
0
0
1
1
-5/2
0
3/2
X6
0
0
0
0
-1/2
1
-1/2
Zj
0
0
0
1
½
0
19/2
X1
1
0
0
-1
0
2
0
X2
0
1
0
1
0
-1
3
X3
0
0
1
1
0
-5
4
X5
0
0
0
0
1
-2
1
Yj
0
0
0
1
0
1
9
42
Dopravní problém (Speciální úlohy lineárního programování) Mezi nejtypičtější úlohy lineárního programování patří tzv. distribuční úlohy lineárního programování. Z distribučních úloh v této kapitole podrobněji rozebereme dopravní problém a z formulačního hlediska se zmíníme o dalších úlohách jako je přiřazovací problém, okružní dopravní problém a obecný distribuční problém.
Dopravní problém – formulace ekonomického a matematického modelu V dopravním problému se typickém případě jedná o rozvržení rozvozu nějakého zboží či materiálu z dodavatelských míst (zdroje) odběratelům (cílová místa) tak, aby byly minimalizovány celkové náklady související s tímto rozvozem. V dopravním problému je definováno m-zdrojů (dodavatelů) D1, D2, …, Dm s omezenými kapacitami a1, a2, …, am (množství, které je dodavatel schopen v uvažovaném období dodat ) a ncílových míst (odběratelů) O1, O2, …, On se stanovenými požadavky b1, b2, …, bn (množství, které odběratel v uvažovaném období požaduje). Vztah každé dvojice zdroj-cílové místo je nějakým způsobem oceněn. Tímto oceněním mohou být například vykalkulované náklady na přepravu jedné jednotky zboží mezi zdrojem a cílovým místem nebo kilometrová vzdálenost mezi zdrojem a cílovým místem. Kvantifikované ocenění vztahu zdrojů a cílových míst označím cij, i = 1, 2, …, m, j = 1, 2, …, n. Cílem řešení dopravního problému je naplánovat přepravu mezi zdroji a cílovými místy, tzn. stanovit objem přepravy mezi každou dvojici zdroj-cílové místo tak, aby nebyly překročeny kapacity zdrojů a aby byly uspokojeny požadavky cílových míst. Z hlediska matematického modelu je tedy třeba stanovit hodnoty proměnných xij, i = 1, 2, …, m, j = 1, 2, …, n, které vyjadřují objem přepravy mezi i-tým zdrojem a jtým cílovým místem. Výše uvedený popis lze považovat za typickou formulaci ekonomického modelu dopravního problému. Tuto formulaci lze přehledně vyjádřit ve formě tabulky (tabulka 1).
Zdroje
D1
D2
Cílová místa O1
O2
c11
c12
x11
x12
c21
c22
x21
x22
…
On
Kapacity zdrojů
c1a …
x1a
a1
c2n …
43
x2n
a2
…
…
…
…
…
. . . Dm
Požadavky cíl. míst
cm1
cm2
xm1
xm2
cmn …
xmn
am
∑ i ai b1
b2
…
bn
∑ j bj
Tab. 1 – Formulace ekonomického modelu dopravního problému. Při řešení dopravního problému je třeba uvažovat vztah celkové kapacity všech zdrojů ∑i ai (součet všech dílčích kapacit) a všech požadavků cílových míst ∑j bj (součet požadavků). Pouze ve speciálním případě bude patrně platit ∑i ai = ∑j bj . Takový dopravní problém budeme označovat jako vyrovnaný dopravní problém. V tomto případě platí, že všechny požadavky budou přesně uspokojeny a všechny kapacity budou vyčerpány. Dopravní problém, ve kterém ∑i ai ≠ ∑j bj budeme označovat jako nevyrovnaný dopravní problém. Při převisu na straně nabídky zůstane část kapacity nevyužita a podobně při převisu na straně poptávky nebudou uspokojeny všechny požadavky. My se v dalším textu budeme zabývat pouze vyrovnaným dopravním problémem, neboť nevyrovnaný problém lze na vyrovnaný snadno převést. Tento převod se realizuje tak, že při převisu nabídky k modelu doplníme tzv. fiktivní cílové místo OF (fiktivní odběratel), jehož požadavek bude roven ∑i ai - ∑j bj , tj. rozdílu mezi celkovými kapacitami a požadavky – tabulka 1 bude tedy rozšířena o nový sloupec, při převisu poptávky k modelu doplníme tzv. fiktivní zdroj DF (fiktivní dodavatel), jehož kapacita bude rovna ∑j bj - ∑i ai , tj. rozdílu mezi sumou požadavků a kapacit – tabulka 1 bude tedy rozšířena o nový řádek. Zbývá poznamenat, že ocenění vztahu mezi zdroji a cílovými místy cij je u fiktivních činitelů nulové.
44
Při formulaci matematického modelu vyrovnaného dopravního problému si je třeba uvědomit, že model bude obsahovat m.n proměnných xij vyjadřujících objem přepravy mezi i-tým zdrojem a j-tým cílovým místem a dále bude obsahovat (m+n) vlastních omezení. Omezení jsou přitom dvojího druhu. Prvních m představuje bilanci pro jednotlivé zdroje – součet dodávek ze zdrojů cílovým místům nesmí přesáhnout kapacitu jednotlivých zdrojů (vzhledem k vyrovnanosti dopravního problému bude roven této kapacitě). Řádkové součty proměnných v tabulce 1 se tedy rovnají příslušným kapacitám. Zbývajících n omezení přísluší jednotlivým cílovým místům. Součet dodávek do jednotlivých cílových míst by se měl rovnat, opět vzhledem k vyrovnanosti dopravního problému, jednotlivým požadavkům. Matematický model vyrovnaného dopravního problému vypadá proto následovně: minimalizovat z = c11x11 + c12x12 + … + c1nx1n + … + cm1xm1 + cm2xm2 + … +cmnxmn za podmínek x11 + x12 + … + x1n
= a1
x21 + x22 + … + x2n
u1 = a2
u2
.
.
.
.
.
..
.
.
xm1 + xm2 + … + xmn = am x11
+ x21 x12 .
. . . + xm1
= b1
+ x21 . . .
+ xm2 = b2
v2
.
.
.
.
.
.
.
.
.
.
.
.
. . + x1n + x2n . . .
+ xmn = bn
um
v1
vn
xij ≥ 0, i = 1, 2, … , m, j = 1, 2, …, n. Koeficienty cij budeme v matematickém modelu označovat jako cenové koeficienty. Současně s formulaci matematického modelu budeme formulovat i model k němu duálně sdružený. Ve výše uvedené formulaci jsme označili symboly u1, u2, …, um duální proměnné příslušející kapacitnímu omezením a pro odlišení symboly v1, v2, …, vn duální proměnné pro omezení jednotlivých požadavků. Duální model bude vypadat následovně: maximalizovat 45
f = a1u1 + a2u2 + … + amum + b1v1 + b2v2 + …+ bnvn za podmínek u1 + v1 ≤ c11, u2 + v2 ≤ c12, . . um + vn ≤ cmn. Vlastní omezení duální úlohy lze přehledně zapsat v následující podobě: xij ≥ 0 ui + vj ≤ ci j., i = 1, 2, …, m, j = 1, 2, …, n. Nebo lze zapsat takto: minimalizovat z=
m
n
i =1
j =1
∑ ∑
cijxij
za podmínek n
∑
xij = ai,
i = 1, 2, …, m,
xij = bj,
j = 1, 2, …, n,
j =1 m
∑ i =1
xij ≥ 0,
i = 1, 2, …, m, j = 1, 2, …, n.
Množina přípustných řešení vyrovnaného dopravního problému je určená soustavou (m+n) lineárních rovnic, které obsahují m.n proměnných, a podmínkami nezápornosti. Je však možné poměrně snadno ukázat, že hodnost rozšířené matice uvedené soustavy lineárních rovnic
1 1
1
...
1 1
1
...
1 1 1
1 1
1
1
...
1
1
1
1
46
1
a1 a2 am b1 b2 bn
není zrovna m+n, ale pouze m+n-1, že libovolný řádek uvedené matice lze získat jako lineární kombinaci všech řádků ostatních. Důsledkem toho je, že v základním řešení vyrovnaného dopravního problému je pouze m+n-1 základních proměnných.
Příklad: Společnost Multicomp, s.r.o. má v ČR 3 střediska (Plzeň, Pardubice, Olomouc), ve kterých montuje osobní počítače. Kapacita těchto středisek je 330, 150 a 220 ks počítačů měsíčně. Tyto počítače jsou distribuovány smluvním odběratelům v Brně, Praze, Ostravě a Liberci. Podle smluv dodá Multicomp jednotlivým odběratelům postupně 180, 250, 160 a 110 ks počítačů. Distribuční náklady mezi středisky a odběrateli byly vykalkulovány na 1 ks počítače ve výši, která je zřejmá z tabulky 2 – údaj v pravém horním rohu každého pole (uvedené hodnoty jsou ve stovkách Kč).
Brno
Praha
Ostrava
Liberec
Plzeň
11
4
17
9
Pardubice
6
7
10
8
Olomouc
3
9
5
12
Kapacity
Požadavky Tab. 2 – Dopravní problém – formulace ekonomického modelu.
Formulace matematický modelu našeho vyrovnaného dopravního problému následnovně: minimalizovat z = 11x11 + 4x12 + 17x13 + 9x14 + 6x21 + 7x22 + 10x23 + 8x24 + 3x31 + 9x32 + 5x33 + 12x34 za podmínek x11 + x12 + x13 + x14 = 330 Je-li počet kladných základních proměnných nižší než m+n-1, jedná se o degenerované základní řešení. x21 + x22 + x23 + x24 = 150 x31 + x32 + x33 + x34 = 220 x11
+ x21 + x31 = 180 x12
+ x22 + x32 = 250
47
x13
+ x23 + x33 = 160
x14
+ x24 + x34 = 110
xij ≥ 0, i = 1, 2, 3, j = 1, 2, 3, 4.
Řešení dopravního problému Dopravní problém je možné řešit standardní simplexovou metodou. Metoda má tyto kroky: výpočet výchozího základního řešení test optimality (v případě, že je řešení už optimální, ukončení výpočtu) výpočet nového základního řešení s lepší (nižší) hodnotou účelové funkce – tento krok zahrnuje podobně jako u simplexové metody: volbu vstupující proměnné, volbu vystupující proměnné, přepočet tabulky, ve které je výpočet realizován. 1. Výpočet výchozího základního řešení Při výpočtu základního řešení se zde vlastně jedná pouze o to, doplnit do tabulky 1 hodnoty proměnných tak, aby jejich řádkové součty byly rovny kapacitám a sloupcové součty byly rovny požadavkům, a aby počet nenulových proměnných nebyl vyšší než m+n-1. Pro výpočet je možno použít tří metod: metoda severozápadního rohu, indexní metoda (metoda maticového minima) a metoda VAM. Metoda severozápadního rohu
Příklad: Tato metoda umístí v prvním kroku přepravu do pole s proměnnou x11, které je v tabulce vlevo nahoře tedy na „severozápadě“. V našem případě představuje toto pole přepravu mezi Brnem a Plzní, která bude ve výši 180 ks a tím je požadavek Brna plně uspokojen a je třeba zredukovat kapacitu Plzně z původních 330 ks na 330 – 180 = 150 ks. Dále pokračujeme stejným způsobem.
Brno
Praha
Ostrava
Liberec
Plzeň
11
4
17
9
Pardubice
6
7
10
8
Olomouc
3
9
5
12
48
Kapacity
Požadavky
Tab. 3 – Dopravní problém – metoda severozápadního rohu.
Základní proměnná
Objem
Jednotkové
Podíl na
x11 (Plzeň – Brno)
180
1 100
198 000
x12 (Plzeň – Ostrava)
150
400
60 000
x21 (Pardubice – Praha)
100
700
70 000
x22 (Pardubice – Ostrava)
50
1 000
50 000
x33 (Olomouc – Ostrava)
110
500
55 000
x34 (Olomouc – Liberec)
110
1 200
132 000
Náklady celkem
xxx
xxx
565 000
Tab. 4 – Výpočet hodnoty účelové funkce. Z tabulky 4 je vidět, že celkové náklady přepravy pro řešení získané metodou severozápadního roku jsou 565 000 Kč. Pozn.: Tato metoda poskytuje v typickém případě velmi špatné řešení, nebere totiž při obsazování přepravy v úvahu vůbec náklady přepravy. Proto se tato metoda nedoporučuje používat. Indexní metoda (metoda maticového minima)
Příklad: Tato metoda jako první umístí přepravu do pole s minimálními jednotkovými přepravními náklady, v našem případě jde o pole Olomouc-Brno. Umisťujeme stejně jako v předešlé metodě.
Brno Plzeň
Praha
Ostrava
4
17
Pardubice
10
49
Liberec
8
Kapacity
Olomouc
3
5
Požadavky
Tab. 4.8 – Dopravní problém – indexní metoda Hodnota účelové funkce tohoto řešení je 438 000 Kč, což je lepší výsledek než v předchozí metodě.
Základní proměnná
Objem
Jednotkové
Podíl na
(přeprava odkud – kam)
přepravy
náklady
celk. náklady
x11 (Plzeň – Praha)
250
400
100000
x12 (Plzeň – Ostrava)
80
1700
136000
x21 (Pardubice – Ostrava)
40
1000
40000
x22 (Pardubice – Liberec)
110
800
88000
x33 (Olomouc – Brno)
180
300
54000
x34 (Olomouc – Ostrava)
40
500
20000
Náklady celkem
xxx
Xxx
438000
Indexní metoda poskytuje v typickém případě lepší řešení než metoda severozápadního rohu. Tuto skutečnost však nelze brát jako pravidlo. Negativním rysem indexní metody je, že sice zpočátku obsazuje přepravu do nejvýhodnějších polí, ale může se snadno stát, ze nakonec je třeba obsadit pole s nejméně výhodnými cenovými koeficienty. Metoda VAM (Vogelova aproximační metoda)
Příklad: Výpočet metodou VAM budeme ilustrovat na stejném příkladu. Tabulka 6 obsahuje 5 kroků výpočtu optimálního řešení. Tato metoda vychází z toho, že se pro každý řádek a sloupec dopravního problému vypočítají tzv. DIFERENCE, což je rozdíl mezi nejmenšími cenovými koeficienty v daném řádku či sloupci.. Vybere se pole, které má nejnižší cenový koeficient v řádku nebo sloupci s maximální diferencí. Může nastat situace, kdy existuje více řádků a sloupců se stejnou maximální diferencí. Pak vybereme pole, které má nejnižší sazbu z těch polí, které leží v řádcích a sloupcích
50
s těmito maximálními diferencemi.Po obsazení pole dojde k vyloučení řádku a sloupce. Přepočítáme diference a postup zopakujeme.
1 krok
Brno
Plzeň
Praha
Ostrava
4
17
Pardubice Olomouc
10 3
Liberec
Kapacity
Diference
Kapacity
Diference
Kapacity
Diference
Kapacity
Diference
8
5
Požadavky Diference
2 krok
Brno
Plzeň
Praha
Ostrava
4
17
Pardubice Olomouc
10 3
Liberec
8
5
Požadavky Diference
3 krok
Brno
Plzeň
Praha
Ostrava
4
17
Pardubice Olomouc
10 3
Liberec
8
5
Požadavky Diference
4 krok
Brno
Praha
Ostrava
Liberec
Plzeň
11
4
17
9
51
Pardubice
6
7
10
8
Olomouc
3
9
5
12
5 krok
Brno
Praha
Ostrava
Liberec
Plzeň
11
4
17
9
Pardubice
6
7
10
8
Olomouc
3
9
5
12
Požadavky Diference
Kapacity
Diference
Požadavky Diference Tab. 6 – Dopravní problém – metoda VAM (1. – 5. krok).
Hodnota účelové funkce tohoto řešení je 366000 Kč a je tedy výrazně lepší než řešení získané předchozími metodami. Základní proměnná
Objem
Jednotkové
Podíl na
(přeprava odkud – kam)
přepravy
náklady
celk. náklady
x11 (Plzeň – Praha)
250
400
100000
x12 (Plzeň – Liberec)
80
900
72000
x21 (Pardubice – Brno)
120
600
72000
x22 (Pardubice – Liberec)
30
800
24000
x33 (Olomouc – Brno)
60
300
18000
x34 (Olomouc – Ostrava)
160
500
80000
Náklady celkem
xxx
xxx
366000
Metoda VAM poskytuje v typickém případě nejlepší řešení.
Test optimality 52
Po nalezení výchozího základního řešení je třeba provést test optimality, který spočívá ve výpočtu redukovaných cenových koeficientů zij zij = ui + vj – cij, i = 1, 2, …, m, j = 1, 2, …, n. Pro každou základní proměnnou xij, která je v typickém případě kladná, platí podle této věty zij = ui + vj – cij = 0, tedy ui + vj = cij. Aby řešení, jehož optimalitu testujeme, bylo řešením optimálním, musí platit pro všechny nezákladní proměnné, že jsou jejich redukované ceny nekladné. Dostáváme tedy dvě podmínky optimality: Výpočetní realizace testu optimality: Pro každé obsazené pole sestavíme rovnici ui + vj = cij. Dostáváme tedy soustavu m+n-1 rovnic pro m+n neznámých. Tato soustava má jeden stupeň volnosti a proto libovolně jednu z neznámých položíme rovnu nule a ostatní dopočítáme. Duální proměnné vypočtené v prvním kroku použijeme pro ověření druhé podmínky optimality, která udává, že redukované ceny zij pro nezákladní proměnné musí být nekladné. Pokud tomu tak je, je testované základní řešení řešením optimálním.
Příklad: Test optimality ukážeme na výchozím základním řešení našeho příkladu, tabulka 5. Základní proměnné s jejich hodnotou a jim odpovídající rovnice ui + vj = cij uvádíme Test optimality 1.
pro základní proměnné (typicky xij > 0) musí platit
zij = ui + vj – cij = 0, 2 přehledu: v následujícím
ákl d í
ě
é(
x12 = 250
⇒
u1 + v2 = 4
x12 = 80
⇒
u1 + v3 = 17 ,
x12 = 40
⇒
u2 + v3 = 10 ,
x12 = 110
⇒
u2 + v4 = 8
,
x12 = 180
⇒
u3 + v1 = 3
,
x12 = 40
⇒
u3 + v3 = 5
.
0)
í l tit
,
Položíme-li například neznámou v3 = 0, potom pro ostatní duální proměnné dostáváme již snadno – u1 = 17, u2 = 10, u3 = 5, v1 = -2, v2 = - 13 a v4 = -2. Pro nezákladní proměnné vypočteme redukované ceny: x11 = 0 ⇒
z11 = u1 + v1 – c11 = 17 – 2 – 11 = 4
53
,
x14 = 0 ⇒
z14 = u1 + v4 – c14 = 17 – 2 – 9 = 6
,
x21 = 0 ⇒
z21 = u2 + v1 – c21 = 10 – 2 – 6 = 2
,
x22 = 0 ⇒
z22 = u2 + v2 – c22 = 10 – 13 – 7 = -10 ,
x32 = 0 ⇒
z32 = u3 + v2 – c32 = 5 – 13 – 9 = -17
,
x34 = 0 ⇒
z34 = u3 + v4 – c34 = 5 – 2 – 12 = -9
.
Z uvedeného přitom plyne, že testované řešení není optimální, protože je zde test optimality porušen u proměnných x11, x14 a x21, u kterých jsou redukované ceny kladné. 3. Výpočet nového základního řešení
Volba vstupující proměnné Provádí se stejně jako u simplexovy metody. Zvolí se ta proměnná, která nejvíce porušuje test optimality. Volí se tedy podle maximálního kladného redukovaného cenového koeficientu. Zrs = max (zij ) zij > 0 Pokud toto určení není jednoznačné, zvolí se vstupující proměnná libovolně z proměnných, které přicházejí v úvahu. Vstupující proměnná určuje klíčové pole. V našem případě je vstupující proměnná x14 , protože redukovaná cena u této proměnné je 6, a porušuje tak nejvíce test optimality.
Volba vystupující proměnné Je třeba nejdříve zkonstruovat tzv. uzavřený kruh. Je to posloupnost obsazených polí, která začíná a současně končí v klíčovém poli. Tento kruh je určen jednoznačně. Po určení uzavřeného kruhu označíme jeho prvky střídavě symbolem +t a –t. V klíčovém poli je přitom symbol +t. Vystupující proměnná je určená minimální hodnotou xij , které jsou označeny symbolem –t. Pokud je polí s touto minimální hodnotou více, zvolí se vstupující proměnná libovolně z nich. Hodnota t určuje současně hodnotu nově vstupující proměnné. V našem případě vychází jako vystupující proměnná x13 a hodnota t =80.
Přepočet tabulky dopravního problému K polím označeným +t se jednoduše hodnota t přičte a naopak od polí označených –t se odečte. Ostatní pole zůstanou beze změny. V každém kroku výpočtu musí zůstat zachován počet základních proměnných m+n-1. Změnu hodnoty účelové funkce pro vstupující proměnnou xrs lze vypočítat podle vztahu ∆z(xrs) = -t* Zrs . V našem případě dostáváme ∆z(x14 ) = -80*6 = -480 – hodnota účelové funkce se sníží o 48000 Kč. 54
V našem případě je vstupující proměnou tedy x14 . Klíčové pole a prvky uzavřeného kruhu jsou v tabulce zvýrazněny. Vystupující proměnná je zřejmě x13 –hodnota t = min (80,110) = 80. Hodnota účelové funkce se v prvním kroku snížila z hodnoty 438000 Kč o 48000 Kč a její nová hodnota je 390000 Kč. V novém řešení opět realizujeme test optimality. V našem případě je porušen pouze u proměnné x21 , jejíž cenový koeficient je roven 2 (má být záporný). Je to teda nová vstupující proměnná. Vystupující proměnnou je x23 – hodnota t = min(120,180) = 120. Změna hodnoty účelové funkce nového řešení je rovna ∆z(x21 )= -120*2 = -240 – nová výše nákladů je tedy 390000 – 24000 = 366000 Kč. Přepočteme-li znovu tabulku dosáhneme již optimálního řešení, protože všechny nezákladní proměnné již budou záporné. Všimněte si, že se jedná o řešení, které je shodné s výchozím základním řešením vypočteným metodou VAM.
Brno
Praha
Ostrava
Liberec
Plzeň
4
4
17
6
Pardubice
2
-10
10
8
Olomouc
3
-17
5
-9
Brno
Praha
Ostrava
Liberec
-2 11
4
-6 17
9
Kapacity
ui
Kapacity
ui
Požadavky vj
Plzeň Pardubice
250 -4 7
2 6
Olomouc
3
10 120 5
-11 9
180
40 +
80 8
330
30 -9 12
150
1
220
6
Požadavky 180
250
160
110
9
4
11
9
vj
55
700
0
Brno Plzeň
-4 11
Pardubice 6 Olomouc
3 60
Praha 4 250 -4 7 -9 9
Ostrava -8 17 -2 10 5 160
Liberec 9
Kapacity
330
ui
0
8 30 -7 12
150
1
220
4
700
Požadavky 180
250
160
110
7
4
9
9
vj
Vyrovnaný dopravní problém má vždy optimální řešení. Optimální řešení může být přitom buď jediné nebo alternativní. Jediné řešení má dopravní problém v případě, že jsou všechny redukované cenové koeficienty u nezákladních proměnných záporné. Pokud je alespoň jeden z těchto koeficientů roven nule má dopravní problém alternativní řešení.
56
