Návod na výpočty příkladů

vky
88
0
0
22
306
 
∆s
2=7-5
1=8-7
 
Hony
objekty
1
2
3
4
kapacity
∆r
1
9
8
9
50 4
0
2
7
6
5
8
76
1=8-7
3
12 7
7
84 4
8
12
1=8-7
4
22 5
62 4
9
7
0
požadavky
66
0
0
22
306
 
∆s
0=7-7
0=8-8
 
V tomto kroku máme dvě možnosti, kterou sedmičku zvolit, pro výsledek je to jedno, obě možnosti vyjdou stejně . Volil jsem možnost jako v DÚ.
Hony
objekty
1
2
3
4
kapacity
∆r
1
9
8
9
50 4
0
2
54 7
6
5
22 8
0
3
12 7
7
84 4
8
0
4
22 5
62 4
9
7
0
požadavky
0
0
0
0
306
 
∆s
 
V tomto kroku je již možné tabulku doplnit.
3) Ověříme si důležité údaje a spočítáme z.
Kapacity: 50 + 76 + 96 + 84 = 306
Požadavky: 88 + 62 + 84 + 72 = 306
Spojů: m + n – 1 = 4 + 4 -1 = 7
z = 54*7 + 12*7 + 22*5 + 62*4 + 84*4 + 50*4 + 22*8 = 1532
Metoda MODI
Objekty
Náklady na přepravu 1t
Kapacity
Pekárny
1.
2.
3.
4.
1.
4
9
6
7
78
2.
8
9
6
4
82
3.
9
4
5
9
38
Požadavky
78
60
70
72
 
1)Provedeme test zda se kapacity rovnají požadavkům
Kapacity = 78 + 82 + 38 = 198
Požadavky= 78 + 60 + 70 + 72 = 280
Jelikož si neodpovídají kapacity a požadavky musíme zavést fiktivní objekt, který bude mít 0 ceny a jeho kapacita se bude rovnat rozdílu mezi požadavky a kapacitami. V našem případě 280 – 198 = 82.Ceny (Cij) doplníme do pravého horního rohu červená čísla.Tabulku vyplníme pomocí indexové metody (protože máme v prvním sloupci a prvním řádku 78 a vypadl by nám sloupec i řádek, musíme k jednomu číslu přičíst velmi malé ε , tím zajistíme, že nám v 1 řádku zbyde hodnota ε a nevyškrtneme ho .Rozšíříme jí o sloupec Ui a řádek Vi. Zvolíme si jedno Ui nebo Vi rovno nule. V našem případě jde o U2. Poté dopočítáme ostatní Ui a Vi tak že u bazických proměnných (zelených čísel) spočteme podle vzorce Ui + Vi = Cij v našem případě U2 + V3 = C23 tzn. 0 + V3 = 6 –> V3 = 6 pak U2 + V4 = C24 tzn. 0 + V4 = 4 –> V4 = 4 . Takto doplníme všechny čísla.
2) provádíme test optima.
V nebazických (nejsou v nich zelená čísla) buňkách doplníme do levého dolního rohu (modrá čísla) součet Ui + Vi .Pak doplníme do levého horního rohu (hnědá čísla) Ui + Vi - Cij
Prodejny
sklady
1
2
3
4
Kapacity
Ui
1
0
4
-5
9
-2
6
-5
7
78 + ε
-2
 
78
 
 
 
 
   4  4  4  2  2-2 8-3 90 60 4820     10  72 6  6  6  4  3-5 90 4-1 5-7 938-2   38     4  4  4  2  4 - fiktivní0 00 00 0-2 082-6   22  60   0  0  0  -2  Požadavky
78
60
70
72
280
Vi
6
6
6
4
3) aby bylo řešení správné musí být Ui + Vi - Cij < 0. Neplatí pro fiktivní sklad, protože ve skutečnosti neexistuje a nic nerozváží.V našem případě jsou všechna hnědá čísla záporná což značí výsledek úlohy.Pokud by se tak nestalo, řešení není optimální a dá se ještě zlepšit, jak se postupuje v tomto případě si ukážeme v následujícím příkladě.
dopravní úloha z mezisklady
Od čtyř dodavatelů o kapacitách 600, 480, 430 a 290 se má provést rozvoz produktů přes tři mezisklady o kapacitách 640, 610 a 550 k pěti spotřebitelům, jejichž požadavky činí 220, 300, 270, 435 a 575 tak, aby rozvoz byl proveden s minimálními náklady. Sazby za přepravu mezi jednotlivými stanicemi jsou známé a jsou uvedeny v následujících tabulkách.
 
M1
M2
M3
 
M1
M2
M3
D1
12
18
32
S1
24
26
28
D2
15
14
28
S2
25
24
35
D3
22
29
20
S3
27
35
38
D4
36
20
14
S4
32
32
22
S5
36
34
22
1) spočteme přepravované množství
Kapacita dodavatelů D: 1800
Kapacita meziskladů M: 1800
Kapacita spotřebitelů S: 1800
Jelikož se součty rovnají nemusíme zavádět fiktivní pole.
2) Podle metody MODI vyplníme tabulku a řešíme jako dvě oddělené úlohy
mezisklady
dodavatelé
M1
M2
M3
Kapacity
Ui
D1
0
12
-7
18
-27
32
600
0
 
600
 
 
 
 
 
12
 
 11  5  D20 150 14-20 284803 40  440   15- 14+ 8  D35 22-3 290 2043015     430 27+ 26  20- D4-15 360 200 142909   170  120 21  20- 14+ Požadavky
640
610
550
1800
Vj
12
11
5
mezisklady
spotřebitelé
M1
M2
M3
Kapacity
wi
S1
0
24
-2
26
-16
28
220
0
 
220
 
 
 
 
 
24
 
 
24
 
 
12
 
 
S2
-1
 
25
0
 
24
-23
 
35
300
0
 
 
 
300
 
 
 
24
 
 
24
 
 
12
 
 
S3
0
 
27
-8
 
35
-23
 
38
270
3
 
270
 
 
 
 
 
27
 
 
27
 
 
15
 
 
S4
0
 
32
0
 
32
-2
 
22
435
8
 
150
 
 
285
 
 
 
32
 
 
32
 
 
20
 
 
S5
-26
 
36
-24
 
34
-12
 
22
575
10
 
 
 
25
 
 
550
 
10
 
 
10
 
 
10
 
 
Požadavky
640
610
550
1800
Vj'
24
24
12
2) u první tabulky jsme v testu optima zjistili, že M1D3 = 5 což není záporné číslo. Proto použijeme Datzingovy uzavřené obvody, abychom 40 přesunuly o jeden řádek dolů jak je naznačeno v tabulce .Po úpravách dostaneme výslednou tabulku.









meziskladydodavateléM1M2M3KapacityUiD1012-218-22326000 600     12  16  10  D2-5 150 14-20 28480-2   480   10  14  8  D30 22-3 290 2043010 40    390 22  26  20  D4-20 360 200 142904   130  160 16  20  14  Požadavky
640
610
550
1800
Vj
12
16
10
mezisklady
spotřebitelé
M1
M2
M3
Kapacity
wi
S1
0
24
-2
26
-16
28
220
0
 
220
 
 
 
 
 
24
 
 
24
 
 
12
 
 
S2
-1
 
25
0
 
24
-23
 
35
300
0
 
 
 
300
 
 
 
24
 
 
24
 
 
12
 
 
S3
0
 
27
-8
 
35
-23
 
38
270
3
 
270
 
 
 
 
 
27
 
 
27
 
 
15
 
 
S4
0
 
32
0
 
32
-2
 
22
435
8
 
150
 
 
285
 
 
 
32
 
 
32
 
 
20
 
 
S5
-26
 
36
-24
 
34
-12
 
22
575
10
 
 
 
25
 
 
550
 
10
 
 
10
 
 
10
 
 
Požadavky
640
610
550
1800
Vj'
24
24
12
Přiřazovací úloha
Druh
Linky na zpracování
zeleniny
1.
2.
3.
4.
5.
1.
8
4
2
5
6
2.
3
5
4
7
9
3.
2
8
7
4
3
4.
6
4
1
3
5
5.
7
3
5
4
5
základní tabulka
Druh zeleniny
Linky na zpracování
1.
2.
3.
4.
5.
1.
8
4
2
5
6
2.
3
5
4
7
9
3.
2
8
7
4
3
4.
6
4
1
3
5
5.
7
3
5
4
5
1)Data přepíšeme do tabulky a uděláme řádkovou redukci cen tak, že v každém řádku vybereme nejmenší číslo a to pak odečteme od všech ostatních v řádku. V našem případě v prvním řádku 2 ve druhém 3 atd. (červená čísla)
redukce matice cen v řádcích (2,3,2,1,3)
Druh zeleniny
Linky na zpracování
1.
2.
3.
4.
5.
1.
6
2
0
3
4
2.
0
2
1
4
6
3.
0
6
5
2
1
4.
5
3
0
2
4
5.
4
0
2
1
2
2)Uděláme sloupcovou redukci cen, v prvním, druhém a třetím sloupci 0 ve čtvrtém a pátém 1

redukce matice cen ve sloupcích (0,0,0,1,1)
Druh zeleniny
Linky na zpracování
1.
2.
3.
4.
5.
1.
6
2
0
2
3
2.
0
2
1
3
5
3.
0
6
5
1
0
4.
5
3
0
1
3
5.
4
0
2
0
1
3)Výběr nezávislých nul
Nejdříve vybereme silně nezávislé 0 tj. nuly které jsou sami v řádku i sloupci , tento řádek a sloupec vyškrtneme z dalších úvah. V našem případě žádná taková nula neexistuje. Poté se vybírá mírně nezávislá 0, ta má buď v řádce nebo ve sloupci nulu. Vybírám 0 v prvním řádku. 1 řádek a třetí sloupec vyškrtnu, pokračuji s nulou v druhém řádku.Výběr končí když není v tabulce žádná nula, v řádku ani sloupci , který jsme nevyškrtli.
Druh zeleniny
Linky na zpracování
1.
2.
3.
4.
5.
1.
6
2
0
2
3
2.
0
2
1
3
5
3.
0
6
5
1
0
4.
5
3
0
1
3
5.
4
0
2
0
1
4) Kontrola správnosti výběru nezávislých 0,vybereme závislou nulu (není růžová), která je v v řadě bez nezávislé nuly a škrtneme ji kolmo na řádek resp.sloupec. V našem případě 0 v čtvrtém řádku škrtlá kolmo je sloupec tři ,0 v čtvrtém sloupci škrtlá kolmo je řádek pět, zbývající nuly pokryjeme libovolně, 0 v prvním sloupci škrtlá kolmo je řádek tři a 0 v druhém řádku škrtlá kolmo je první sloupec.po vyškrtání provedeme kontrolu, počet řádků m a počet sloupců n se musí rovnat počtu nezávislých nul a počet nezávislých nul je roven minimálnímu počtu čar.První podmínka slněna není.
Druh zeleniny
Linky na zpracování
1.
2.
3.
4.
5.
1.
6
2
0
2
3
2.
0
2
1
3
5
3.
0
6
5
1
0
4.
5
3
0
1
3
5.
4
0
2
0
1
5)Protože nebyla splněna podmínka z bodu čtyři musíme udělat redukci matice cen tak, že ve zbývajících polích (bílá barva) vezmeme nejmenší číslo a to odečteme od všech čísel (pouze bílá pole)
Druh zeleniny
Linky na zpracování
1.
2.
3.
4.
5.
1.
6
1
0
1
2
2.
0
1
1
2
4
3.
1
6
6
1
0
4.
5
2
0
0
2
5.
5
0
3
0
1
6) Provedeme kontrolu výběru nezávislých nul a zjistíme, že podmínky jsou splněny.
Druh zeleniny
Linky na zpracování
1.
2.
3.
4.
5.
1.
6
1
0
1
2
2.
0
1
1
2
4
3.
1
6
6
1
0
4.
5
2
0
0
2
5.
5
0
3
0
1
7) Vrátíme se do základní tabulky a spočítáme z.To se spočte tak, že na místě kde jsme měli nezávislé nuly sečteme čísla (růžová)
Druh zeleniny
Linky na zpracování
1.
2.
3.
4.
5.
1.
8
4
2
5
6
2.
3
5
4
7
9
3.
2
8
7
4
3
4.
6
4
1
3
5
5.
7
3
5
4
5
z= 2*1 + 3*1 + 3*1 + 3*1 + 3*1 = 14
Teorie grafů
a) Upravený Ford-Fulkersonův algoritmus
 
 
 
 
Jindřichův
 
 
 
 
Tábor
Veselí
Pelhřimov
Hradec
Jihlava
Telč
Třebíč
Tábor
 
22
19
 
 
 
 
Veselí
 
 
24
 
 
 
Pelhřimov
 
41
30
 
 
Jindřichův
 
70
41
 
Hradec
 
 
 
 
Jihlava
 
29
35
Telč
 
36
Třebíč
 
 
 
 
 
 
 
1)Data z tabulky si převedeme do grafu, na spojnice dáme vzdálenosti.
2)Data si přepíšeme do tabulky tak, že modrá čísla nám v druhém řádku nám udávají startovací bod, červená čísla nám udávají koncový bod a zelená čísla nám udávají vzdálenost.
Z jedničky jedeme do dvojky za 22 a do trojky za 19, dvojky jedeme do jedničky za 22 a do čtyřky za 24, do tabulek se píší i zpáteční cesty. Dále do tabulky napíšeme v řádku vi pod první město 0
Města
Tábor
Veselí
Pelhřimov
Jindřichův Hradec
Jihlava
Telč
Třebíč
 
1
2
3
4
5
6
7
vi
0
j(hij)
2(22)
1(22)
1(19)
2(24)
3(30)
4(41)
5(35)
3(19)
4(24)
4(41)
3(41)
4(70)
5(29)
6(36)
 
 
5(30)
5(70)
6(29)
7(36)
 
 
 
 
6(41)
7(35)
 
 
3) Vezmeme první město a vzdálenost, kterou ujedeme zapíšeme do příslušného sloupce k parametru vi .Z tábora do Veselí za 22 a v tomto kroku ještě vyškrtneme všechna čísla začínající jedničkou a 2(22) dáme do rámečku.
Města
Tábor
Veselí
Pelhřimov
Jindřichův Hradec
Jihlava
Telč
Třebíč
 
1
2
3
4
5
6
7
vi
0
22
19
j(hij)
2(22)
1(22)
1(19)
2(24)
3(30)
4(41)
5(35)
3(19)
4(24)
4(41)
3(41)
4(70)
5(29)
6(36)
 
 
5(30)
5(70)
6(29)
7(36)
 
 
 
 
6(41)
7(35)
 
 
4) V dalším kroku hledáme nejkratší cestu do 3. Hledáme min z prvního a druhého sloupce, přičemž škrtnutá čísla a čísla v šedivém rámečku vynecháváme. Hledané hodnoty jsou součtem červených čísel a zelených čísel. V našem případě min( 19 + 0 ; 22 + 24 ) minimální hodnota je 19 tu proto zapíšeme pod Pelhřimov a min hodnotu dáme do rámečku a škrtneme všechna čísla začínající 2
Města
Tábor
Veselí
Pelhřimov
Jindřichův Hradec
Jihlava
Telč
Třebíč
 
1
2
3
4
5
6
7
vi
0
22
19
46
j(hij)
2(22)
1(22)
1(19)
2(24)
3(30)
4(41)
5(35)
3(19)
4(24)
4(41)
3(41)
4(70)
5(29)
6(36)
 
 
5(30)
5(70)
6(29)
7(36)
 
 
 
 
6(41)
7(35)
 
 
5)Pokračujeme stejně jako v bodě čtyři. min( 24 + 22; 41 + 19; 30 + 19 ) = 46
Města
Tábor
Veselí
Pelhřimov
Jindřichův Hradec
Jihlava
Telč
Třebíč
 
1
2
3
4
5
6
7
vi
0
22
19
46
j(hij)
2(22)
1(22)
1(19)
2(24)
3(30)
4(41)
5(35)
3(19)
4(24)
4(41)
3(41)
4(70)
5(29)
6(36)
 
 
5(30)
5(70)
6(29)
7(36)
 
 
 
 
6(41)
7(35)
 
 
6) Tabulku dopočítáme a v řádku Vi čteme nejkratší cesty do jednotlivých měst.
Města
Tábor
Vesel