MA2BP_PDM1 Diskrétní matematika 1 4. Dopravní úloha Lukáš Másilko Středisko pro pomoc studentům se specifickými nároky Masarykova univerzita 24. 10. 2017 24. 10. 2017 1 / 46 Program prezentace □ Představení dopravní úlohy B Řešení dopravního problému ■ Počáteční krok ■ Metoda severozápadního roh ■ Indexová metoda ■ Vogelova aproximační metod ■ Optimalizační krok 3 Použité zdroje Automobilová společnost Automobilová společnost MG má závody v Los Angeles, Detroitu a New Orleans a distribuční střediska v Denveru a Miami. Kapacity výrobních závodů pro plánované období jsou po řadě 1000, 1500 a 1200 ks aut, poptávka středisek je 2300 a 1400 ks. Cena dopravy 1 auta na jednu míli je 8 centu (cent je setina dolaru). Určete optimální rozdělení dopravy od výrobců ke spotřebitelským místům. Vzdálenosti mezi místy (v mílích) jsou uvedeny v tabulce. Denver Miami Los Angeles 1000 2690 Detroit 1250 1350 New Orleans 1275 850 24. 10. 2017 3 / 46 Obecné zadaní dopravní úlohy Mějme konkrétní výrobek, m závodů, které jej vyrábějí, a n spotřebitelských skladů, které jej odebírají. ✓ Úkolem je najít optimální způsob rozvozu výrobků z výrobních závodů do spotřebitelských skladů tak, aby se minimalizovala cena dopravy. Vždy bude dáno: ■ Cjj ... jednotková cena dopravy ze zdroje / na místo určení j ■ a; ... množství zásob ve zdroji /, kde / = 1, 2,..., m ■ bj ... požadavek na počet výrobků od spotřebitele j, kde j = 1,2, ...,n ■v Řešením jsou □ optimální hodnoty proměnných x,y jako množství výrobků dopravovaných ze zdroje / ke spotřebiteli j\ B celková cena dopravy m n ;=i j=i 24. 10. 2017 4 / 46 Automobilová společnost - shrnutí faktů Ze zadání víme hodnoty a;, bj pro / = 1, 2, 3, j = 1, 2: a = (1000,1500,1200) b = (2300,1400) Neznáme jednotkovou cenu dopravy c,y ze zdroje / ke spotřebiteli j, víme však vzdálenost mezi jednotlivými zdroji a spotřebiteli a cenu dopravy 1 auta na jednu míli (8 centů = 0,08 USD). Lze už snadno spočítat cenu dopravy jednoho auta od zdroje / ke spotřebiteli, např. cn = 0,08 • 1000 = 80. Můžeme tak připravit tabulku ceny převozu jednoho auta: Cij Denver Miami Los Angeles 80 215 Detroit 100 108 New Orleans 102 68 24. 10. 2017 5 / 46 Způsob zápisu dat dopravní úlohy Denver Miami Los Angeles 80 215 1000 Detroit 100 108 1500 New Orleans 102 68 1200 2300 1400 1000 + 1500 + 1200 = 2300 + 1400 požadavky spotřebitelů jsou stejné) vyvážená úloha (kapacity výrobců a 24. 10. 2017 6 / 46 Nevyvážená úloha Nevyvážené úlohy se snažíme "vyvážit", abychom mohli použít řešící algoritmus. H Nabídka < Poptávka: např. kapacita výroby v Detroitu je 1300, nikoliv 1500 B Nabídka > Poptávka: např. spotřebitelský sklad v Denveru požaduje pouze 1900, nikoliv 2300 V obou případech přidáváme fiktivního výrobce (resp. spotřebitele) s kapacitou, která je rovna rozdílu nabídky a poptávky, přičemž jednotková cena doprava je stanovena na 0. 24. 10. 2017 7 / 46 Nabídka < Poptávka - vyvážení Denver Miami Los Angeles 80 215 1000 Detroit 100 108 1300 New Orleans 102 68 1200 Fiction 0 0 200 2300 1400 24. 10. 2017 8 / 46 Nabídka > Poptávka - vyvážení Denver Miami Al Capone Los Angeles 80 215 0 1000 Detroit 100 108 0 1500 New Orleans 102 68 0 1200 1900 1400 400 □ [S ► < -E ► 24. 10. 2017 9 / 46 Řešící algoritmus dopravního problému Počáteční krok - nalezení nějakého prípustného řešení. Můžeme použít tři různé metody: a) Metoda severozápadního rohu (SZR) b) Indexová metoda (IM) c) Vogelova aproximační metoda (VAM) Optimalizační kroky - vylepšování počátečního řešení □ 2017 10 / 46 Modelový příklad - vyvážená úloha Tři zdroje Vi, V2, V3 a jejich kapacity a — (15,25,5) ■v —* Čtyři spotřebitelé Si, S2, S3, S4 a jejich požadavky b = (5,15,15,10) Jednotková cena c,y, 0 < / < 3, 0 < j < 4 viz tabulka. s s s s ul J2 ^3 UA v1 10 0 20 11 12 7 9 20 v3 0 14 16 18 15 15 15 25 10 24. 10. 2017 11 / 46 Počáteční krok ■ Počáteční krok - nalezení nějakého přípustného řešení, které nemusí být optimální. ■ Ukážeme si tři různé metody: a) Metoda severozápadního rohu (SZR) b) Indexová metoda (IM) c) Vogelova aproximační metoda (VAM) ■ Pro vysvětlení metod použijeme naši modelovou vyváženou úlohu se 3 výrobci a 4 spotřebiteli. 24. 10. 2017 12 / 46 Počáteční krok metodou severozápadního rohu Začínáme v "severozápadním" rohu a hledáme x\\\ stanovíme maximální možnou hodnotu xn tak, aby byla rovna min(ai,bi) = 5. s1 s2 s3 54 v, 10 0 20 11 12 7 9 20 v3 0 14 16 18 15 25 15 15 10 24. 10. 2017 13 / 46 Počáteční krok metodou severozápadního rohu Nastavíme xn = 5. Zcela jsme vyhověli požadavkům spotřebitele Si, tudíž do dalších buněk 1. sloupce umístíme pomlčku. s2 s3 54 v, 5 10 0 20 11 — 12 7 9 20 v3 — 0 14 16 18 15 25 15 15 10 24. 10. 2017 13 / 46 Počáteční krok metodou severozápadního rohu Pokračujeme v 1. řádku a hledáme X12: kapacita výrobce V\ je již snížena na 10, požadavky spotřebitele S\ jsou v max. množství 15 =4> x\2 — 10. 52 s3 54 v, 5 10 -> 0 20 11 — 12 7 9 20 v3 — 0 14 16 18 15 25 15 15 10 24. 10. 2017 13 / 46 Počáteční krok metodou severozápadního rohu Nastavíme X12 = 10. Zcela jsme vyčerpali kapacitu výrobce V\, tudíž do dalších buněk 1. řádku umístíme pomlčku. s2 s3 54 v, 5 10 -> 10 0 20 11 — 12 7 9 20 v3 — 0 14 16 18 15 25 15 15 10 24. 10. 2017 13 / 46 Počáteční krok metodou severozápadního rohu Pokračujeme v 2. sloupci a hledáme X22: kapacita výrobce V2 je 25, požadavky spotřebitele S2 jsou sníženy na 5 =4> X22 = 5. S S S S ul J2 ^3 UA v, 5 10 s. 10 0 20 11 — 12 * 7 9 20 — 0 14 16 18 5 15 15 10 15 25 24. 10. 2017 13 / 46 Počáteční krok metodou severozápadního rohu Nastavíme X22 = 5. Zcela jsme vyhověli požadavkům spotřebitele S2, tudíž do dalších buněk 2. sloupce umístíme pomlčku. s2 S3 54 v, 5 10 -> 10 1 0 20 11 — 12 5 7 9 20 v3 — 0 — 14 16 18 15 25 15 15 10 24. 10. 2017 13 / 46 Počáteční krok metodou severozápadního rohu Pokračujeme v 2. řádku a hledáme X23: kapacita výrobce V2 je snížena na 20, požadavky spotřebitele S3 jsou stále 15 =4> X23 = 15. S S S S ul J2 ^3 UA v, 10 s. 10 I 0 20 11 D 12 5 7 -> 9 20 v3 0 — 14 16 18 15 25 15 15 10 24. 10. 2017 13 / 46 Počáteční krok metodou severozápadního rohu Nastavíme X23 = 15. Zcela jsme vyhověli požadavkům spotřebitele S3, tudíž do dalších buněk 3. sloupce umístíme pomlčku. S S S S ul J2 ^3 UA v, 5 10 s. 10 I 0 20 11 12 \ 5 7 s. 15 9 20 0 14 16 18 5 15 15 10 15 25 24. 10. 2017 13 / 46 Počáteční krok metodou severozápadního rohu Pokračujeme v 2. řádku a hledáme X24: kapacita výrobce V2 je snížena na 5, požadavky spotřebitele S4 jsou stále 10 =4> X24 = 5. S S S S ul J2 ^3 UA V1 10 » 10 0 20 11 15 12 V, *~7 5 — » 15 20 25 0 14 16 18 V, 15 15 10 24. 10. 2017 13 / 46 Počáteční krok metodou severozápadního rohu Nastavíme X24 = 5. Zcela jsme vyčerpali kapacitu výrobce V2 S S S S ul J2 ^3 UA v1 5 10 s. 10 1 0 20 11 12 \ 5 7 v 15 9 s. 5 20 0 14 16 18 5 15 15 10 15 25 □ g ► < -E ► 24. 10. 2017 13 / 46 Počáteční krok metodou severozápadního rohu Pokračujeme ve 4. sloupci a hledáme X34: kapacita výrobce V3 je stále 5, požadavky spotřebitele S4 jsou sníženy na 5 =4> X34 = 5. 5, V1 10 » 10 0 20 11 15 12 V, *~7 5 — » 15 0 14 16 » 5 -4 20 25 18 V, 15 15 10 24. 10. 2017 13 / 46 Počáteční krok metodou severozápadního rohu Nastavíme X34 = 5. Zcela jsme vyčerpali kapacitu výrobce V3 a vyhověli požadavkům spotřebitele S4. 5, V1 10 » 10 0 20 11 15 12 V, *~7 5 — » 15 0 14 16 » 5 -4 20 25 18 V, 15 15 10 24. 10. 2017 13 / 46 Počáteční krok metodou severozápadního rohu Počáteční krok je dokončen. Vstupní rozdělení je uvedeno níže. Celková cena dopravy 5 • 10 + 10 • 0 + 5 • 7 + 15 • 9 + 5 • 20 + 5 • 18 = 410 peněžních jednotek. v1 v. v, S1 10 12 0 o Ír-? 14 20 » 19 16 11 » 5 20 18 15 25 15 15 10 24. 10. 2017 13 / 46 Důležitá podmínka dopravní úlohy ■ Má-li dopravní tabulka m řádku a n sloupců, pak pomlčka není umístěna v m + n — 1 buňkách tabulky. ■ Tento požadavek musí platit pro počáteční rozdělení i každý optimalizační krok. ■ Nebezpečná situace: po nastavení proměnné x,y jsme současně vyčerpali kapacitu výrobce V/ a naplnili požadavky spotřebitele Sj. O V takovém případě by "nepomlčkových" buněk bylo méně než m + n — 1. Q Řešíme např. tak, že umístíme pomlčky do zbývajících polí řádku /, nastavíme x/+ij = 0 a do dalších polí sloupce j umístíme pomlčky Q Viz příklad "degenerovaného počátečního rozdělení" na dalším slajdu. 24. 10. 2017 14 / 46 Příklad degenerovaného počátečního rozdělení s1 5 1 0 — 2 — 1 12 -> 5 1 5 1 5 v3 — 2 — 4 5 3 10 10 24. 10. 2017 15 / 46 Počáteční krok Indexovou metodou Začínáme buňkou, která má minimální cenu: pole [1,2] s cenou S S S S ul J2 ^3 UA v, 10 0 20 11 12 7 9 20 v3 0 14 16 18 15 25 15 15 10 4 ^ >■ < -E ► 4 24. 10. 2017 16 / 46 Počáteční krok Indexovou metodou Kapacita výrobce V\ je 15, požadavky spotřebitele S2 taktéž. Proto X12 = 15. Ostatní buňky 1. řádku označíme pomlčkami, do pole X22 vložíme 0, do dalších polí 2. sloupce pomlčku. S S S S ul J2 ^3 UA v, 10 15 0 20 11 12 0 7 9 20 0 — 14 16 18 5 15 15 10 15 25 □ g ► < -E ► < = 24. 10. 2017 16 / 46 Počáteční krok Indexovou metodou Další buňka s minimální cenou je pole [3,1] s cenou 0 s2 s3 54 v, 10 15 0 20 11 15 12 0 7 9 20 25 v3 0 — 14 16 18 5 15 15 10 24. 10. 2017 16 / 46 Počáteční krok Indexovou metodou Kapacita výrobce V3 je 5, požadavky spotřebitele Si taktéž. Proto X31 = 5. Ostatní buňky 3. řádku označíme pomlčkami, do pole X21 vložíme 0, do dalších polí 1. sloupce pomlčku. s2 s3 54 v, — 10 15 0 20 11 0 12 0 7 9 20 v3 5 0 — 14 16 18 5 15 15 10 24. 10. 2017 16 / 46 Počáteční krok Indexovou metodou Další buňka s minimální cenou je pole [2, 2] s cenou 7. Požadavky spotřebitele S2 jsou však již naplněny, proto ponecháme buňku beze změny. s2 s3 54 v, — 10 15 0 20 11 0 12 0 7 9 20 v3 5 0 — 14 16 18 5 15 15 10 24. 10. 2017 16 / 46 Počáteční krok Indexovou metodou Pouze 2. řádek obsahuje "nepomlčkové" buňky. Začneme s polem [2,3] a minimální cenou 9. s1 s2 s3 s4 v, — 10 15 0 20 11 0 12 0 7 9 20 v3 5 0 — 14 16 18 5 15 15 10 24. 10. 2017 16 / 46 Počáteční krok Indexovou metodou Kapacita výrobce V2 je 25, požadavky spotřebitele S3 15. Proto X23 S S S S ul J2 ^3 UA v1 — 10 15 0 — 20 11 0 12 0 7 15 9 20 5 0 — 14 — 16 18 5 15 15 10 15 25 □ g ► < -E ► < = 24. 10. 2017 16 / 46 Počáteční krok Indexovou metodou Zbývá jediná "nepomlčková" buňka [2,4]. s2 S3 54 v, — 10 15 0 — 20 11 0 12 0 7 15 9 20 v3 5 0 — 14 — 16 18 5 15 15 10 Počáteční krok Indexovou metodou Zbývající kapacita výrobce V2 je 10, požadavky spotřebitele S4 také 10 X24 = 10. S S S S ul J2 ^3 UA v, — 10 15 0 — 20 — 11 0 12 0 7 15 9 10 20 5 0 — 14 — 16 — 18 5 15 15 10 15 25 24. 10. 2017 16 / 46 Počáteční krok Indexovou metodou Počáteční krok je dokončen. Vstupní rozdělení je uvedeno níže. Celková cena dopravy 15 • 0 + 15 • 9 + 10 • 20 + 5 • 0 = 335 peněžních jednotek. v1 v. v, s1 — 10 15 0 — 20 — íi 0 12 0 7 15 9 20 Hl 0 — 14 — 16 — 18 5 15 15 10 15 25 Indexová metoda zajišťuje nižší celkovou cenu dopravy - Metoda severozápadního rohu nebrala na cenu c,y ohled □ g ► < -e ► < = •fy <\ (y 24. 10. 2017 16 / 46 Počáteční krok Vogelovou aproximační metodou ■ Penalizace - rozdíl mezi druhou nejmenší cenou a nejmenší cenou, který určujeme pro každý řádek a sloupec. Penalizaci vkládáme do hranatých závorek za kapacitu výrobce či požadavky spotřebitele. Postup pomocí Vogelovy aproximační metody □ Nastavení penalizace pro všechny uvažované řádky a sloupce. B Výběr pole k úpravě - uplatňují se dvě podmínky: ■ buňka je na řádku či sloupci s nej větší penalizací, ■ cena buňky na vybraném řádku či sloupci je minimální. B Po výběru konkrétní buňky [ij] nastavíme proměnnou x,y tradičním způsobem včetně vkládání pomlček v případě naplnění kapacity výrobce či splnění požadavků spotřebitele. □ Pokračujeme v krocích 1-3 tak dlouho, dokud zbude pouze jeden řádek či sloupec, u něhož je vyplnění jednoznačně dáno. 24. 10. 2017 17 / 46 Počáteční krok Vogelovou aproximační metodou Nejdříve si pro každý řádek a sloupec zapíšeme penalizaci S S S S ul J2 ^3 ^4 v, 10 0 20 11 v2 12 7 9 20 V3 0 14 16 18 15 [10] 25 [2] 5 [14] 5 [10] 15 [7] 15 [7] 10 [7] □ [S ► < E ► 24. 10. 2017 18 / 46 Počáteční krok Vogelovou aproximační metodou Největší penalizaci má 3. řádek - buňka na 3. řádku s nejmenší cenou 0 je na pozici [3,1]. v, v. v, s1 10 0 20 11 12 7 9 20 0 14 16 18 5 [10] 15 [7] 15 [7] 10 [7] 15 [10] 25 [2] 5 [14] 24. 10. 2017 18 / 46 Počáteční krok Vogelovou aproximační metodou Kapacita výrobce V3 je 5, požadavky spotřebitele Si taktéž. Proto X31 = 5. Ostatní buňky 3. řádku označíme pomlčkami, do pole X21 vložíme 0, do dalších polí 1. sloupce pomlčku. s1 s2 53 54 10 0 20 11 15 [10] v2 12 0 7 9 20 25 [2] V3 0 5 14 16 18 5 [14] 5 [10] 15 [7] 15 [7] 10 [7] 24. 10. 2017 18 / 46 Počáteční krok Vogelovou aproximační metodou Přepočítáme penalizaci pro uvažované řádky a sloupce. S S S S ul J2 ^3 ^4 v, 10 0 20 11 v2 12 0 7 9 20 0 5 14 16 18 5 15 [7] 15 [11] 10 [9] 15 [11] 25 [2] 24. 10. 2017 18 / 46 Počáteční krok Vogelovou aproximační metodou Největší penalizaci má 3. sloupec - buňka na 2. řádku s nejmenší cenou 9 je na pozici [2, 3]. v, v. v, s1 52 s3 54 10 0 20 11 15 [11] 12 0 7 9 20 25 [2] 0 5 14 16 18 5 5 15 [7] 15 [11] 10 [9] < □ ► 24. 10. 2017 18 / 46 Počáteční krok Vogelovou aproximační metodou Kapacita výrobce V2 je 25, požadavky spotřebitele S3 jsou 15. Proto X23 — 15. Ostatní buňky 3. sloupce označíme pomlčkami. s1 52 s3 54 — 10 0 — 20 11 v2 0 12 7 15 9 20 V3 5 0 14 — 16 18 15 [11] 25 [2] 15 [7] 15 [11] 10 [9] 24. 10. 2017 18 / 46 Počáteční krok Vogelovou aproximační metodou Přepočítáme penalizaci pro uvažované řádky a sloupce. S S S S ul J2 ^3 ^4 v, — 10 0 20 11 v2 0 12 7 9 15 20 V3 5 0 14 16 18 15 [11] 25 [13] 15 [7] 15 10 [9] □ [S ► < -E ► 24. 10. 2017 18 / 46 Počáteční krok Vogelovou aproximační metodou Největší penalizaci má 2. řádek - buňka ve 2. sloupci s nejmenší cenou 7 je na pozici [2, 2]. Si 52 s3 54 — 10 0 — 20 11 v2 0 12 7 15 9 20 V3 5 0 14 — 16 18 15 [11] 25 [13] 15 [7] 15 10 [9] 24. 10. 2017 18 / 46 Počáteční krok Vogelovou aproximační metodou Kapacita výrobce V2 je snížená na 10, požadavky spotřebitele S2 jsou 15 Proto X22 = 10. Ostatní buňky 2. řádku označíme pomlčkami. Si 52 s3 s4 — 10 0 — 20 11 v2 0 12 10 7 15 9 20 V3 5 0 — 14 — 16 18 15 [11] 25 [13] 15 [7] 15 10 [9] 24. 10. 2017 18 / 46 Počáteční krok Vogelovou aproximační metodou Zbývá nám už jen poslední řádek. s2 s3 54 — 10 0 — 20 11 0 12 10 7 15 9 20 v3 5 0 — 14 — 16 18 5 15 15 10 □ i3i Počáteční krok Vogelovou aproximační metodou Vybereme nejdříve buňku [1,2]. Kapacita výrobce V\ je 15, požadavky spotřebitele S2 jsou snížené na 5. Proto x\2 — 5. s2 s3 54 v, — 10 5 0 — 20 11 0 12 10 15 9 20 v3 5 0 — 14 — 16 18 5 15 15 10 24. 10. 2017 18 / 46 Počáteční krok Vogelovou aproximační metodou Nakonec vybereme buňku [1,4]. Kapacita výrobce V\ je snížená na 10, požadavky spotřebitele S4 jsou snížené na 10. Proto X14 = 10. s2 s3 54 v, — 10 5 0 — 20 10 11 0 12 10 7 15 9 — 20 v3 5 0 — 14 — 16 — 18 5 15 15 10 24. 10. 2017 18 / 46 Počáteční krok Vogelovou aproximační metodou Počáteční krok je dokončen. Vstupní rozdělení je uvedeno níže. Celková cena dopravy 5-0 + 10-11+ 10- 7 +15- 9 + 5- 0 = 315 peněžních jednotek. s2 s3 54 v, — 10 0 — 20 ii 0 12 7 15 9 — 20 v3 El 0 — 14 — 16 — 18 5 15 15 10 24. 10. 2017 18 / 46 Shrnutí tri metod ■ Nejlepší výsledek v našem příkladu dala poslední metoda - Vogelova aproximační metoda, přesto nemusí být získané rozdělení nejlepší. ■ Počáteční rozdělení dále zlepšujeme pomocí optimalizačních kroků. ■ Rozdělení dopravy nesmí obsahovat uzavřený okruh! Příklady viz následující slajd. 24. 10. 2017 19 / 46 Příklad uzavřeného okruhu Uzavřený okruh [1,2] - [1,3] - [2,3] - [2,2] — 5 10 — — 10 10 5 5 — — — 24. 10. 2017 20 / 46 Příklad uzavřeného okruhu Uzavřený okruh [1,1] - [1,3] - [3,3] - [3,1] 0 15 — — 15 — 10 — 5 — 0 24. 10. 2017 20 / 46 Optimalizační krok Vezmeme počáteční rozdělení dopravy získané některou ze tří metod a budeme opakovaně provádět tři kroky: H určení vstupní proměnné (=vstupního pole) ze všech pomlčkových (nebázických) buněk B určení výstupní proměnné (=výstupní pole, které se v dalším kroku stane pomlčkovým) B provedení optimalizačního kroku (=přepočítání nového bázického reseni) Předvedeme si optimalizační kroky na počátečním rozdělení získaném Metodou severozápadního rohu. 24. 10. 2017 21 / 46 1. Určení vstupní proměnné - nalezení multiplikátorů Pro každý řádek a sloupec nalezneme tzv. multiplikátory u; (pro řádky) a vj (pro sloupce). Využijeme k tomu rovnice u i + Vj = Qj pro ceny na nepomlčkových (bázických) polích. Protože pro m řádků a n sloupců je nepomlčkových polije m + n — 1, můžeme si jeden multiplikátor zvolit - nejčastěji jej nastavujeme na hodnotu 0. 24. 10. 2017 22 / 46 1. Určení vstupní proměnné - nalezení multiplikátorů Nastavíme u\ — 0 a vyznačíme si nepomlčková pole. Vi v2 v3 u1 = 0 5 10 10 0 — 20 — 11 15 u2 — 5 7 15 g 5 20 25 u3 — 0 — — 5 18 5 15 15 10 □ g ► < -E ► < = 24. 10. 2017 23 / 46 1. Určení vstupní proměnné - nalezení multiplikátorů Protože ui = 0 A en = 10, platí v\ — 10 ^ = 10 v2 v3 v4 uľ = 0 10 5 10 0 — 20 — 11 15 12 5 7 15 g 5 20 25 "3 0 — — 5 18 5 15 15 10 □ g ► < -E ► < = 24. 10. 2017 23 / 46 1. Určení vstupní proměnné - nalezení multiplikátorů Protože l/i = 0 A c12 = 0, platí V2 = 0 v, = 10 "2 = 0 v3 "4 uľ = 0 10 5 10 0 — 20 — 11 15 5 7 15 g 5 20 25 "3 0 — — 5 18 5 15 15 10 24. 10. 2017 23 / 46 1. Určení vstupní proměnné - nalezení multiplikátorů Protože V2 = 0 A c22 = 7, platí U2 = 7. v, = 10 "2 = 0 "4 L/1 = 0 10 5 10 0 — 20 — 11 15 u2 = 7 5 7 15 g 5 20 25 u3 0 — 14 — 5 18 5 15 15 10 24. 10. 2017 23 / 46 1. Určení vstupní proměnné - nalezení multiplikátorů Protože U2 = 7 A c23 = 9, platí v$ = 2 ^ = 10 v2 = 0 "b = 2 v4 u1 = 0 10 5 10 0 20 — 11 15 u2 = 7 5 7 g 15 5 20 25 0 — 16 5 18 5 5 15 15 10 < □ ► < 5 ► 24. 10. 2017 23 / 46 1. Určení vstupní proměnné - nalezení multiplikátorů Protože l/2 = 7 A c24 = 20, platí = 13 ^ = 10 v2 = 0 v3 = 2 i/4 = 13 u1 = 0 10 5 0 10 20 11 u2 = 7 7 5 g 15 20 5 0 18 5 5 15 15 10 15 25 24. 10. 2017 23 / 46 1. Určení vstupní proměnné - nalezení multiplikátorů Protože V4 = 13 A c34 = 18, platí U3 = 5 v, = 10 v2 = 0 v3 = 2 i/4 = 13 U1 = 0 10 5 0 10 20 11 u2 = 7 7 5 g 15 20 5 0 18 u3 = 5 5 5 15 15 10 15 25 24. 10. 2017 23 / 46 1. Určení vstupní proměnné - prepočítaní ceny pomlčkových polí Po určení multiplikátorů provedeme přepočítání ceny c,y pro pomlčková pole. Pro novou cenu č,y platí vzorec č,y = u\ + vj — c;j. Zapíšeme jí do pole vlevo dole. Např. č21 = U2 + v\ — c21 = 7 + 10 — 12 = 5. 1^ = 10 v2 = 0 v3 = 2 v4 = 13 ut = 0 10 5 10 0 20 1 1 — 11 u2 = 7 5 12 5 7 15 5 u3 = 5 0 — 14 16 5 18 5 15 15 10 24. 10. 2017 24 / 46 1. Určení vstupní proměnné - závěr Přepočítáme ceny všech pomlčkových polí, viz níže. v, = 10 v2 = 0 i/3 = 2 v4 = 13 = 0 10 5 10 0 20 1 -18 1 1 11 1 2 u2 = 7 12 5 5 7 15 5 u3 = 5 0 15 -9 14 16 -9 18 5 5 15 15 10 □ [31 1. Určení vstupní proměnné - závěr Vstupním polem je buňka [ij'] s maximální kladnou cenou c,y, tedy pole [3,1]. v± = 10 v2 = 0 i/3 = 2 i/4 = 13 l/j = 0 5 10 10 0 -18 20 1 2 — 11 u2 = 7 5 12 5 7 15 5 u3 = S 15 0 -9 — 14 -9 16 5 18 15 25 15 15 10 24. 10. 2017 25 / 46 2. Určení výstupní proměnné Ve 2. části optimalizačního kroku určujeme výstupní pole. ■ Uvažujeme vstupní pole společně se všemi nepomlčkovými poli. ■ Společně vytvářejí uzavřený okruh (pole [2,3] není vrcholem okruhu) l/1 = 0 u2 = 7 u3 = 5 v, = 10 v2 = 0 v3 = 2 i/4 = 13 10 5 A 12 15 0 0 » 10 "+-7 20 -18 11 •15- 14 16 -9 -9 » 5 20 18 15 15 10 15 25 24. 10. 2017 26 / 46 2. Určení výstupní proměnné Vstupní pole označíme symbolem ©, ostatní buňky uzavřeného okruhu pak střídavě značíme symboly 0. ^ = 10 v2 = 0 v3 = 2 v4=13 u, = 0 10 u2 = 7 12 u3 = 5 0 15 » 10 o (A 20 -18 11 •15- 14 -9 16 -9 » 5 20 18 15 25 15 15 10 24. 10. 2017 27 / 46 2. Určení výstupní proměnné Výstupní pole vybereme mezi buňkami uzavřeného okruhu, které jsou označeny symbolem 0 a mají minimální počet jednotek dopravy. ^ = 10 v2 = 0 v3 = 2 v4=13 u1 = 0 10 ■ -> 10 1 0 li -18 20 11 u2 = 7 12 5 9 v 20 5 X F u3 = S 0 14 16 v 18 5 15 -9 -9 15 15 10 15 25 Splňuje-li tyto podmínky více polí, vybereme jedno z nich, např. buňku [3,4]. 24. 10. 2017 28 / 46 3. Provedení optimalizačního kroku Do proměnných x,y označených © přičteme hodnotu výstupní proměnně. Od proměnných x,y označených 0 odečteme hodnotu výstupní proměnné. Do výstupního pole vložíme pomlčku. u, = 0 u2 = 7 u3 = 5 v, = 10 v2 = 0 i/3 = 2 i/4 = 13 10 0 - A P 12 15 0 » 15 0 20 -18 11 15 ■15- 14 16 -9 -9 10 20 18 25 15 15 %0 24. 10. 2017 29 / 46 Ukončení optimalizace Optimalizační kroky provádíme tak dlouho, dokud je u některého pomlčkového pole pomocná cena c\\ kladná. ^ = 10 v2 = 0 v3 = 2 v4 = 13 = 0 0 10 15 0 -18 — 20 2 — 11 u2 = 7 5 — 12 0 7 15 9 10 20 u3 = 5 15 5 0 -9 — 14 -9 — 16 — 18 5 15 15 10 Je vidět, že pomlčková pole [1,4] a [2,1] mají kladné pomocné ceny. 24. 10. 2017 30 / 46 Optimalizační krok č. 2 Po předchozím optimalizačním kroku máme tuto dopravní tabulku: 10 0 0 15 20 11 12 7 0 9 15 20 10 0 5 14 16 18 5 15 15 10 □ rS ► < -E ► < = 24. 10. 2017 31 / 46 Optimalizační krok č. 2 - multiplikátory Určíme znovu multiplikátory: v, = 10 v2 = 0 i/3 = 2 i/4 = 13 1^ = 0 10 0 15 0 20 11 u2 = 7 12 0 7 9 15 20 10 t/3 = -10 0 5 — 14 16 18 5 15 15 10 □ [3 Optimalizační krok č. 2 - pomocné ceny a vstupní proměnná U pomlčkových polí určíme pomocné ceny dle vzorce c,y = u\ + vj — qj v, = 10 v2 = 0 v3 = 2 \/4 = 13 uľ = 0 0 10 15 0 -18 20 2 11 u2 = 7 5 — 12 0 7 15 9 10 20 u3 = -10 5 0 -24 14 -24 16 -15 18 5 15 15 10 15 25 Vstupním polem je pomlčkové pole s maximální kladnou pomocnou cenou, tj. buňka [3,1]. □ g ► < -e ► < = •fy <\ (y 24. 10. 2017 33 / 46 Optimalizační krok č. 2 - nalezení uzavřeného okruhu Mezi nepomlčkovými poli a vstupním polem najdeme uzavřený okruh. Doplníme střídavě znaménka ©, 0, přičemž u vstupního pole musí být uľ = 0 u2 = 7 u3 = -10 ^=10 v2 = 0 v3 = 2 v4=13 10 0 a (= 0 -> 15 1 a 1 12 - - 2 . en 10 20 £ 14 16 18 -19 -19 -10 15 25 15 15 10 24. 10. 2017 39 / 46 Optimalizační krok č. 3 - výstupní pole Výstupní pole vybereme mezi bunkami uzavřeného okruhu, které jsou označeny symbolem 0 a mají minimální počet jednotek dopravy. Výstupním polem je buňka [2,4]. Její hodnotu odečteme od polí označených 0 a naopak přičteme k polím označeným 0. Na závěr vložíme do výstupního pole pomlčku. u± = 0 u2 = 7 us = -S v, = S 10 -5 12 0 0 5 v2 = 0 v3 = 2 i/4 = 13 0 10 <■ _£ 14 20 -18 •15- 11 » 10 2 . en 20 16 18 -19 -19 -10 15 25 15 15 10 □ g ► < -E ► < = •fy <\ (y 24. 10. 2017 40 / 46 Optimalizační krok č. 4 Po předchozím optimalizačním kroku máme tuto dopravní tabulku: 10 0 5 20 11 10 12 0 7 10 9 15 20 0 5 14 16 18 5 15 15 10 □ g ► < -E ► < = 24. 10. 2017 41 / 46 Optimalizační krok č. 4 - multiplikátory Určíme znovu multiplikátory: 5 v2 = 0 i/3 = 2 v4= 11 uľ = 0 — 10 5 0 20 11 10 u2 = 7 0 12 10 7 9 15 20 u3 = -5 5 0 — 14 16 18 5 15 15 10 □ i3i Optimalizační krok č. 4 - pomocné ceny a vstupní proměnná U pomlčkových polí určíme pomocné ceny dle vzorce c,y = u\ + vj Vl = 5 v2 = 0 1/3 = 2 v4 = 11 uľ = 0 -5 10 5 0 -18 20 10 11 u2 = 7 0 12 10 7 15 9 -2 20 u3 = -5 5 0 -19 14 -19 16 -12 18 5 15 15 10 15 25 U všech pomlčkových polije záporná pomocná cena, algoritmus tedy končí. □ g ► < -E ► < = 24. 10. 2017 43 / 46 Výsledek optimalizace Protože všechny c,y < 0, je níže uvedené rozdělení dopravy ideální. Jeho cena je 5 • 0 + 10 • 11 + 10 • 7 + 15 • 9 + 5 • 0 = 315. s2 s3 54 v, — 10 0 — 20 M ii 0 12 7 15 9 — 20 v3 El 0 — 14 — 16 — 18 5 15 15 10 24. 10. 2017 44 / 46 Výsledek optimalizace Najděte počáteční řešení v následující dopravní úloze a) metodou severozápadního rohu b) indexovou metodou c) Vogelovou aproximační metodou Užitím nejlepšího počátečního řešení vypočtěte optimální řešení. 5, 52 53 54 23 27 16 18 12 17 20 51 v3 22 28 12 32 30 40 53 22 35 25 41 24. 10. 2017 45 / 46 Použité zdroje FAJMON, Břetislav, KOLÁČEK, Jan. Pravděpodobnost, statistika operační výzkum. Brno: VUT Brno, 2005. 314 s.