Obsah přednášky • • • •
Optimalizace
Nederivační metody Metody 1D optimalizace Derivační metody Optimalizace s omezeními – Metody lineární optimalizace • • • •
Lineární programování Distribuční úlohy Okružní problém
Mgr. Květuše Sýkorová
Grafická metoda Přímá metoda Simplexová metoda Distribuční úlohy – – – –
Dopravní problém Okružní problém Přiřazovací problém Obecný distribuční problém
2
KI PřF UJEP Ústí nad Labem
Lineární optimalizace
DÚ LP - Okružní problém
• Distribuční úlohy LP:
• příklad:
– Dopravní problém: – Okružní problém:
– Turista vyjíždí z Prahy a chce postupně navštívit všechna města v tabulce a nakonec se vrátit zpět do Prahy. – Naplánujte trasu tak, aby ujel co nejméně kilometrů. – Vzdálenosti mezi městy jsou dány v následující tabulce:
• označované také jako „problém obchodního cestujícího“ nebo „problém listonoše“ • iterační metoda ⇒ vhodná programová implementace • Ekonomická interpretace:
Praha Teplice Příbram Cheb Klatovy Plzeň
– Je potřeba naplánovat trasu, která prochází několika místy. Každým místem je potřeba projít právě jednou. Je potřeba optimalizovat tuto trasu.
– Přiřazovací problém – Obecný distribuční problém
3
Praha
-
94
60
175
136
94
Teplice
94
-
154
145
169
127
Příbram
60
154
-
161
102
60
Cheb
175
145
161
-
130
101
Klatovy
136
169
102
130
-
42
Plzeň
94
127
60
101
42
-
DÚ LP - Okružní problém
4
DÚ LP - Okružní problém
• kategorie:
• zadání:
– okružní problém
– dáno n míst
• Problém obchodního cestujícího (Travelling Salesman Problem)
• všechna místa je potřeba projet právě jednou a vrátit se do výchozího místa
– rozvozní problém (Vehicle Routing Problem)
– tabulkou dáno ohodnocení spojení
– statické úlohy
– dodatečné podmínky
• vzdálenost, náklady na přepravu, čas • všechna místa a zákazníci jsou předem známá
• každé místo má jistý požadavek na kapacitu okruhu • dána celková kapacita okruhu
– dynamické úlohy
– pokud celková kapacita požadavků jednotlivých míst > celková kapacita okruhu ⇒ nutné mít více okruhů
• v průběhu realizace úlohy přicházejí další požadavky
– jednookruhový problém
– obecný algoritmus pro nalezení optima neexistuje – NP úplná úloha
• nalezení nejkratší cesty, která obsahuje všechna místa
– víceokruhový problém
• s rostoucím n roste exponenciálně složitost (počet omezujících podmínek)
• z jednoho výchozího místa vytváříme více okruhů • z několika výchozích míst vytváříme více samostatných okruhů
– existuje řada aproximačních metod 5
• jejich řešení lze považovat za optimální
6
1
DÚ LP - Okružní problém m
• obecná formulace DÚ LP: • Hledáme minimum F(x):
DÚ LP - Okružní problém m
• řešení:
min ∑∑ cij ⋅ xij
• c = cenové koeficienty (ocenění) • x = objem přepravy (proměnná)
• za omezujících podmínek gi(x):
m
∑x
– kapacitní (řádkové) • místo projedu jen jednou
(i = 1,..., m)
ij
=1
( j = 1,..., m)
x11 , K, xmm ≥ 0
• a podmínek nezápornosti:
– přidáváme postupně do grafu místa (vrcholy) a hrany tak, aby nevytvořili kružnici – kružnici vytvoříme až přidáním posledního místa (vrcholu) a hrany – hrany volíme podle ohodnocení z tabulky • výhodné ohodnocení jedné trasy však může přinést nevýhodné ohodnocení v následujících krocích
+ další podmínky
∑x i =1
=1
ij
j =1
m
– požadavkové (sloupcové) • místo projedu jen jednou
– vycházíme z teorie grafů
i =1 j =1
• plynou z ekonomické interpretace ÚLP
– existuje několik metod řešení: • Metoda nejbližšího souseda • Vogelova aproximační metoda
0 xij = 1 7
8
DÚ LP - Okružní problém •
DÚ LP - Okružní problém
algoritmus (VAM):
• příklad: – VAM
1. výpočet diferencí
– ze zadání príkladu
2. výběr nejkratší trasy •
Praha Teplice Příbram Cheb Klatovy Plzeň difer.
v řadě s největší diferencí
3. vyřazení trasy, která předčasně uzavírá okruh •
pokud nemáme v okruhu všechna místa
– opakujeme krok 1.-3., dokud nemáme v okruhu všechna místa – optimální řešení: • •
nalezen okruh procházející všemi místy spočteme účelovou funkci
Praha
-
94
60
175
136
94
Teplice
94
-
154
145
169
127
Příbram
60
154
-
161
102
60
Cheb
175
145
161
-
130
101
Klatovy
136
169
102
130
-
42
Plzeň
94
127
60
101
42
-
difer. 9
10
DÚ LP - Okružní problém
DÚ LP - Okružní problém
• příklad: – VAM – částečný výsledek
• příklad: – VAM
Teplice
– spočteme diference • zajímá nás největší diference
Praha Teplice Příbram Cheb Klatovy Plzeň difer.
Cheb
Praha Plzeň Příbram
Klatovy
11
Praha
-
94
60
175
136
94
34
Teplice
94
-
154
145
169
127
33
Příbram
60
154
-
161
102
60
0
Cheb
175
145
161
-
130
101
29
Klatovy
136
169
102
130
-
42
60
Plzeň
94
127
60
101
42
-
18
difer.
34
33
0
29
60
18 12
2
DÚ LP - Okružní problém
DÚ LP - Okružní problém
• příklad: – VAM
• příklad: – VAM
– zvolíme místo s nejkratší trasou
– vyškrtneme v daném řádku a sloupci všechny trasy
Praha Teplice Příbram Cheb Klatovy Plzeň difer.
Praha Teplice Příbram Cheb Klatovy Plzeň difer.
Praha
-
94
60
175
136
94
34
Praha
-
94
60
175
136
94
34
Teplice
94
-
154
145
169
127
33
Teplice
94
-
154
145
169
127
33
Příbram
60
154
-
161
102
60
0
Příbram
60
154
-
161
102
60
0
Cheb
175
145
161
-
130
101
29
Cheb
175
145
161
-
130
101
29
Klatovy
136
169
102
130
-
42
60
Klatovy
136
169
102
130
-
42
60
Plzeň
94
127
60
101
42
-
18
Plzeň
94
127
60
101
42
-
18
difer.
34
33
0
29
60
18
difer.
34
33
0
29
60
18
13
14
DÚ LP - Okružní problém
DÚ LP - Okružní problém
• příklad: – VAM
• příklad: – VAM
– vyškrtneme i předčasně uzavírající trasu
Teplice
– částečný výsledek
Praha Teplice Příbram Cheb Klatovy Plzeň difer. Praha
-
94
60
175
136
94
34
Teplice
94
-
154
145
169
127
33
Příbram
60
154
-
161
102
60
0
Cheb
175
145
161
-
130
101
29
Klatovy
136
169
102
130
-
42
60
Plzeň
94
127
60
101
42
-
18
difer.
34
33
0
29
60
18
Cheb
Praha Plzeň Příbram 42
Klatovy
15
DÚ LP - Okružní problém
16
DÚ LP - Okružní problém
• příklad: – VAM
• příklad: – VAM
– částečný výsledek
– spočteme diference • zajímá nás největší diference
Praha Teplice Příbram Cheb Klatovy Plzeň difer.
Praha Teplice Příbram Cheb Klatovy Plzeň difer.
Praha
-
94
60
175
136
94
Praha
-
94
60
175
136
94
34
Teplice
94
-
154
145
169
127
Teplice
94
-
154
145
169
127
51
Příbram
60
154
-
161
102
60
Příbram
60
154
-
161
102
60
42
Cheb
175
145
161
-
130
101
Cheb
175
145
161
-
130
101
15
Klatovy
136
169
102
130
-
42
Klatovy
136
169
102
130
-
42
-
Plzeň
94
127
60
101
42
-
Plzeň
94
127
60
101
42
-
34
difer.
34
33
0
44
28
-
difer.
-
17
18
3
DÚ LP - Okružní problém
DÚ LP - Okružní problém
• příklad: – VAM
• příklad: – VAM
– zvolíme místo s nejkratší trasou
– vyškrtneme v daném řádku a sloupci všechny trasy
Praha Teplice Příbram Cheb Klatovy Plzeň difer.
Praha Teplice Příbram Cheb Klatovy Plzeň difer.
Praha
-
94
60
175
136
94
34
Praha
-
94
60
175
136
94
34
Teplice
94
-
154
145
169
127
51
Teplice
94
-
154
145
169
127
51
Příbram
60
154
-
161
102
60
42
Příbram
60
154
-
161
102
60
42
Cheb
175
145
161
-
130
101
15
Cheb
175
145
161
-
130
101
15
Klatovy
136
169
102
130
-
42
-
Klatovy
136
169
102
130
-
42
-
Plzeň
94
127
60
101
42
-
34
Plzeň
94
127
60
101
42
-
34
difer.
34
33
0
44
28
-
difer.
34
33
0
44
28
-
19
20
DÚ LP - Okružní problém
DÚ LP - Okružní problém
• příklad: – VAM
• příklad: – VAM
– vyškrtneme i předčasně uzavírající trasu
Teplice
– částečný výsledek
94
Praha Teplice Příbram Cheb Klatovy Plzeň difer. Praha
-
94
60
175
Teplice Příbram
136
94
34
94
-
154
60
154
-
145
169
127
51
161
102
60
42
Cheb
175
145
Klatovy
136
169
161
-
130
101
15
102
130
-
42
-
Plzeň
94
127
60
101
42
-
34
difer.
34
33
0
44
28
-
Cheb
Praha Plzeň Příbram 42
Klatovy
21
DÚ LP - Okružní problém
22
DÚ LP - Okružní problém
• příklad: – VAM
• příklad: – VAM
– částečný výsledek
– spočteme diference • zajímá nás největší diference
Praha Teplice Příbram Cheb Klatovy Plzeň difer. Praha
-
94
60
175
136
94
Teplice
94
-
154
145
169
127
Příbram
60
154
-
161
102
60
Cheb
175
145
161
-
130
101
Klatovy
136
169
102
130
-
42
Plzeň
94
127
60
101
42
-
difer.
-
Praha Teplice Příbram Cheb Klatovy Plzeň difer.
-
-
23
Praha
-
94
60
175
136
94
Teplice
94
-
154
145
169
127
76 -
Příbram
60
154
-
161
102
60
52
Cheb
175
145
161
-
130
101
15
Klatovy
136
169
102
130
-
42
-
Plzeň
94
127
60
101
42
-
41
difer.
-
18
0
60
28
24
4
DÚ LP - Okružní problém
DÚ LP - Okružní problém
• příklad: – VAM
• příklad: – VAM
– zvolíme místo s nejkratší trasou
– vyškrtneme v daném řádku a sloupci všechny trasy
Praha Teplice Příbram Cheb Klatovy Plzeň difer.
Praha Teplice Příbram Cheb Klatovy Plzeň difer.
Praha
-
94
60
175
136
94
76
Praha
-
94
60
175
136
94
Teplice
94
-
154
145
169
127
-
Teplice
94
-
154
145
169
127
76 -
Příbram
60
154
-
161
102
60
52
Příbram
60
154
-
161
102
60
52
Cheb
175
145
161
-
130
101
15
Cheb
175
145
161
-
130
101
15
Klatovy
136
169
102
130
-
42
-
Klatovy
136
169
102
130
-
42
-
Plzeň
94
127
60
101
42
-
41
Plzeň
94
127
60
101
42
-
41
difer.
-
18
0
60
28
-
difer.
-
18
0
60
28
-
25
26
DÚ LP - Okružní problém
DÚ LP - Okružní problém
• příklad: – VAM
• příklad: – VAM
– vyškrtneme i předčasně uzavírající trasu
Teplice
– částečný výsledek
94
Praha Teplice Příbram Cheb Klatovy Plzeň difer. Praha
-
94
60
175
Teplice Příbram
136
94
94
-
154
60
154
-
Cheb
175
145
Klatovy
136
169
Plzeň
94
difer.
-
76
145
169
127
-
161
102
60
52
161
-
130
101
15
102
130
-
42
-
127
60
101
42
-
41
18
0
60
28
-
Cheb
Praha 60
Plzeň
Příbram 42
Klatovy
27
DÚ LP - Okružní problém
28
DÚ LP - Okružní problém
• příklad: – VAM
• příklad: – VAM
– částečný výsledek
– spočteme diference • zajímá nás největší diference
Praha Teplice Příbram Cheb Klatovy Plzeň difer.
Praha Teplice Příbram Cheb Klatovy Plzeň difer.
Praha
-
94
60
175
136
94
-
Praha
-
94
60
175
136
94
Teplice
94
-
154
145
169
127
-
Teplice
94
-
154
145
169
127
-
Příbram
60
154
-
161
102
60
Příbram
60
154
-
161
102
60
59
Cheb
175
145
161
-
130
101
Cheb
175
145
161
-
130
101
15
Klatovy
136
169
102
130
-
42
Klatovy
136
169
102
130
-
42
-
Plzeň
94
127
60
101
42
-
Plzeň
94
127
60
101
42
-
26
difer.
-
difer.
-
18
-
60
28
-
-
-
29
-
30
5
DÚ LP - Okružní problém
DÚ LP - Okružní problém
• příklad: – VAM
• příklad: – VAM
– zvolíme místo s nejkratší trasou
– vyškrtneme v daném řádku a sloupci všechny trasy
Praha Teplice Příbram Cheb Klatovy Plzeň difer.
Praha Teplice Příbram Cheb Klatovy Plzeň difer.
Praha
-
94
60
175
136
94
-
Praha
-
94
60
175
136
94
Teplice
94
-
154
145
169
127
-
Teplice
94
-
154
145
169
127
-
Příbram
60
154
-
161
102
60
59
Příbram
60
154
-
161
102
60
59
Cheb
175
145
161
-
130
101
15
Cheb
175
145
161
-
130
101
15
Klatovy
136
169
102
130
-
42
-
Klatovy
136
169
102
130
-
42
-
Plzeň
94
127
60
101
42
-
26
Plzeň
94
127
60
101
42
-
26
difer.
-
18
-
60
28
-
difer.
-
18
-
60
28
-
31
32
DÚ LP - Okružní problém
DÚ LP - Okružní problém
• příklad: – VAM
• příklad: – VAM
– vyškrtneme i předčasně uzavírající trasu
Teplice
– částečný výsledek
94
Praha Teplice Příbram Cheb Klatovy Plzeň difer. Praha
-
94
60
175
Teplice Příbram
136
94
94
-
154
60
154
-
Cheb
175
145
Klatovy
136
169
Plzeň
94
difer.
-
-
145
169
127
-
161
102
60
59
161
-
130
101
15
102
130
-
42
-
127
60
101
42
-
26
18
-
60
28
-
Cheb
Praha 101
60
Plzeň
Příbram 42
Klatovy
33
DÚ LP - Okružní problém
34
DÚ LP - Okružní problém
• příklad: – VAM
• příklad: – VAM
– částečný výsledek
– spočteme diference • zajímá nás největší diference
Praha Teplice Příbram Cheb Klatovy Plzeň difer.
Praha Teplice Příbram Cheb Klatovy Plzeň difer.
Praha
-
94
60
175
136
94
-
Praha
-
94
60
175
136
94
Teplice
94
-
154
145
169
127
-
Teplice
94
-
154
145
169
127
-
Příbram
60
154
-
161
102
60
Příbram
60
154
-
161
102
60
0
Cheb
175
145
161
-
130
101
Cheb
175
145
161
-
130
101
0
Klatovy
136
169
102
130
-
42
-
Klatovy
136
169
102
130
-
42
-
Plzeň
94
127
60
101
42
-
-
Plzeň
94
127
60
101
42
-
-
difer.
-
-
-
difer.
-
0
-
-
0
-
35
-
36
6
DÚ LP - Okružní problém
DÚ LP - Okružní problém
• příklad: – VAM
• příklad: – VAM
– doplníme poslední trasy a uzavřeme okruh
-
94
60
175
Teplice Příbram
136
94
94
-
154
60
154
-
145
169
127
-
161
102
60
0
Cheb
175
145
Klatovy
136
169
161
-
130
101
0
102
130
-
42
-
Plzeň
94
difer.
-
127
60
101
42
-
-
0
-
-
0
-
-
Cheb
Příbram 42 102
Klatovy F (x ) = 94 + 145 + 60 + 101 + 102 + 42 = 544
• příklad: – VAM
– konečný výsledek
– konečný výsledek
-
94
60
175
136
94
-
Teplice
94
-
154
145
169
127
-
Příbram
60
154
-
161
102
60
-
Cheb
175
145
161
-
130
101
-
Klatovy
136
169
102
130
-
42
-
Plzeň
94
127
60
101
42
-
-
difer.
-
-
-
-
-
-
F (x ) = 94 + 145 + 60 + 101 + 102 + 42 = 544
94
Praha
Cheb
60
101
Příbram
Plzeň 102
42
Klatovy
F (x ) = 94 + 145 + 60 + 101 + 102 + 42 = 544
39
DÚ LP - Okružní problém
40
DÚ LP - Okružní problém
algoritmus (Metoda nejbližšího souseda):
• příklad: – MNS
1. zvolíme výchozí místo
– ze zadání príkladu
postupně volíme všechna místa
Praha Teplice Příbram Cheb Klatovy Plzeň
2. výběr nejbližšího sousedního místa cílové místo (soused) s nejkratší trasou
3. vyřazení trasy, která předčasně uzavírá okruh pokud nemáme v okruhu všechna místa
– opakujeme krok 2.-3., dokud nemáme v okruhu všechna místa – optimální řešení: • •
Teplice
145
Praha Teplice Příbram Cheb Klatovy Plzeň difer. Praha
•
38
DÚ LP - Okružní problém
• příklad: – VAM
•
60
Plzeň
DÚ LP - Okružní problém
•
Praha 101
37
•
94
145
Praha Teplice Příbram Cheb Klatovy Plzeň difer. Praha
Teplice
– konečný výsledek
spočteme účelovou funkci pro všechny možné druhy okruhů vybereme nejlepší okruh
41
Praha
-
94
60
175
136
94
Teplice
94
-
154
145
169
127
Příbram
60
154
-
161
102
60
Cheb
175
145
161
-
130
101
Klatovy
136
169
102
130
-
42
Plzeň
94
127
60
101
42
42
7
DÚ LP - Okružní problém •
DÚ LP - Okružní problém
příklad: – MNS
•
1. Praha – Příbram
příklad: – MNS 1. Praha – Příbram – Plzeň
Praha Teplice Příbram Cheb Klatovy Plzeň
Praha Teplice Příbram Cheb Klatovy Plzeň
Praha
-
94
60
175
136
94
Praha
-
94
60
175
136
94
Teplice
94
-
154
145
169
127
Teplice
94
-
154
145
169
127
Příbram
60
154
-
161
102
60
Příbram
60
154
-
161
102
60
Cheb
175
145
161
-
130
101
Cheb
175
145
161
-
130
101
Klatovy
136
169
102
130
-
42
Klatovy
136
169
102
130
-
42
Plzeň
94
127
60
101
42
-
Plzeň
94
127
60
101
42
-
43
44
DÚ LP - Okružní problém •
DÚ LP - Okružní problém
příklad: – MNS
•
1. Praha – Příbram – Plzeň – Klatovy
příklad: – MNS 1. Praha – Příbram – Plzeň – Klatovy – Cheb
Praha Teplice Příbram Cheb Klatovy Plzeň
Praha Teplice Příbram Cheb Klatovy Plzeň
Praha
-
94
60
175
136
94
Praha
-
94
60
175
136
94
Teplice
94
-
154
145
169
127
Teplice
94
-
154
145
169
127
Příbram
60
154
-
161
102
60
Příbram
60
154
-
161
102
60
Cheb
175
145
161
-
130
101
Cheb
175
145
161
-
130
101
Klatovy
136
169
102
130
-
42
Klatovy
136
169
102
130
-
42
Plzeň
94
127
60
101
42
-
Plzeň
94
127
60
101
42
-
45
46
DÚ LP - Okružní problém •
DÚ LP - Okružní problém
příklad: – MNS
•
1. Praha – Příbram – Plzeň – Klatovy – Cheb – Teplice
příklad: – MNS 1. Praha – Příbram – Plzeň – Klatovy – Cheb – Teplice – Praha
Praha Teplice Příbram Cheb Klatovy Plzeň
Praha Teplice Příbram Cheb Klatovy Plzeň
Praha
-
94
60
175
136
94
Praha
-
94
60
175
136
94
Teplice
94
-
154
145
169
127
Teplice
94
-
154
145
169
127
Příbram
60
154
-
161
102
60
Příbram
60
154
-
161
102
60
Cheb
175
145
161
-
130
101
Cheb
175
145
161
-
130
101
Klatovy
136
169
102
130
-
42
Klatovy
136
169
102
130
-
42
Plzeň
94
127
60
101
42
-
Plzeň
94
127
60
101
42
-
47
F (x ) = 94 + 145 + 60 + 130 + 42 + 60 = 531
48
8
DÚ LP - Okružní problém •
DÚ LP - Okružní problém
příklad: – MNS
•
2. Teplice – Praha – Příbram – Plzeň – Klatovy – Cheb – Teplice
příklad: – MNS 3. Příbram – Praha – Plzeň – Klatovy – Cheb – Teplice – Příbram
Praha Teplice Příbram Cheb Klatovy Plzeň
Praha Teplice Příbram Cheb Klatovy Plzeň
Praha
-
94
60
175
136
94
Praha
-
94
60
175
136
94
Teplice
94
-
154
145
169
127
Teplice
94
-
154
145
169
127
Příbram
60
154
-
161
102
60
Příbram
60
154
-
161
102
60
Cheb
175
145
161
-
130
101
Cheb
175
145
161
-
130
101
Klatovy
136
169
102
130
-
42
Klatovy
136
169
102
130
-
42
Plzeň
94
127
60
101
42
-
Plzeň
94
127
60
101
42
-
F (x ) = 94 + 145 + 60 + 130 + 42 + 60 = 531
F (x ) = 60 + 145 + 154 + 130 + 42 + 94 = 625
49
DÚ LP - Okružní problém •
DÚ LP - Okružní problém
příklad: – MNS
•
4. Cheb – Plzeň – Klatovy – Příbram – Praha – Teplice – Cheb
příklad: – MNS 5. Klatovy – Plzeň – Příbram – Praha – Teplice – Cheb – Klatovy
Praha Teplice Příbram Cheb Klatovy Plzeň
Praha Teplice Příbram Cheb Klatovy Plzeň
Praha
-
94
60
175
136
94
Praha
-
94
60
175
136
94
Teplice
94
-
154
145
169
127
Teplice
94
-
154
145
169
127
Příbram
60
154
-
161
102
60
Příbram
60
154
-
161
102
60
Cheb
175
145
161
-
130
101
Cheb
175
145
161
-
130
101
Klatovy
136
169
102
130
-
42
Klatovy
136
169
102
130
-
42
Plzeň
94
127
60
101
42
-
Plzeň
94
127
60
101
42
-
F (x ) = 60 + 94 + 102 + 145 + 42 + 101 = 544
F (x ) = 60 + 94 + 60 + 145 + 130 + 42 = 531
51
DÚ LP - Okružní problém •
50
52
DÚ LP - Okružní problém
příklad: – MNS
•
6. Plzeň – Klatovy – Příbram – Praha – Teplice – Cheb - Plzeň
příklad: – MNS 1. Praha – Příbram – Plzeň – Klatovy – Cheb – Teplice – Praha
F (x ) = 94 + 145 + 60 + 130 + 42 + 60 = 531
2. Teplice – Praha – Příbram – Plzeň – Klatovy – Cheb – Teplice
F (x ) = 94 + 145 + 60 + 130 + 42 + 60 = 531
Praha Teplice Příbram Cheb Klatovy Plzeň Praha
-
94
60
175
136
94
3. Příbram – Praha – Plzeň – Klatovy – Cheb – Teplice – Příbram
Teplice
94
-
154
145
169
127
4. Cheb – Plzeň – Klatovy – Příbram – Praha – Teplice – Cheb
Příbram
60
154
-
161
102
60
Cheb
175
145
161
-
130
101
5. Klatovy – Plzeň – Příbram – Praha – Teplice – Cheb – Klatovy
Klatovy
136
169
102
130
-
42
6. Plzeň – Klatovy – Příbram – Praha – Teplice – Cheb - Plzeň
Plzeň
94
127
60
101
42
-
F (x ) = 60 + 94 + 102 + 145 + 42 + 101 = 544
F (x ) = 60 + 145 + 154 + 130 + 42 + 94 = 625 F (x ) = 60 + 94 + 102 + 145 + 42 + 101 = 544 F (x ) = 60 + 94 + 60 + 145 + 130 + 42 = 531
F (x ) = 60 + 94 + 102 + 145 + 42 + 101 = 544
53
54
9
DÚ LP - Okružní problém
DÚ LP - Okružní problém
• příklad: – MNS
• příklad: – MNS
Teplice
– nejkratší okruh
– nejkratší okruh
94
145
Teplice
145
94
Praha
Cheb Cheb
Praha 60
Plzeň 130
60
130
Příbram
Klatovy 60
Příbram 42
42
Klatovy F (x ) = 94 + 145 + 60 + 130 + 60 + 42 = 531
60
Plzeň
F (x ) = 94 + 145 + 60 + 101 + 102 + 42 = 544
55
DÚ LP - Okružní problém
56
DÚ LP - Okružní problém
• příklad 1:
• příklad 2:
– Turista podniká okružní trasu po Itálii. – Vyjíždí z Catanzara a chce postupně navštívit všechna města uvedená v tabulce. – Naplánujte trasu tak, aby ujel co nejméně kilometrů. 3 body – Vzdálenosti míst jsou uvedeny v následující tabulce:
– Pražská firma XY se zabývá výrobou kojeneckého oblečení. Toto zboží pak dále rozváží do 5 obchodů ve městech: Kladno, Brno, Poděbrady, Tábor, Liberec. – Naplánujte nejkratší cestu mezi obchody (vzdálenosti v tabulce) 3 body
Praha Kladno Brno Poděbrady Tábor Liberec
Catanzaro Cosenza Crotone Reggio Scalea Tropea Catanzaro
-
76
97
158
152
94
Cosenza
97
-
116
187
95
124
Crotone
76
116
-
221
202
157
Reggio
158
187
221
-
242
104
Scalea
152
95
202
242
-
178
Tropea
94
124
157
104
178
-
57
Praha
-
32
204
53
82
105
Kladno
32
-
236
87
112
136
Brno
204
236
-
182
167
241
Poděbrady
53
87
182
-
138
84
Tábor
82
112
167
138
-
189
Liberec
105
136
241
84
189
-
DÚ LP - Okružní problém
58
DÚ LP - Okružní problém
• příklad 3:
• příklad 4:
– Je dána tabulka vzdáleností mezi osmi městy. – Najděte nejkratší okruh obsahující všechna města:
– Firma sídlící v Brně má pobočky v 7 jiných městech (km v tabulce). – Zaměstnanec má navštívit všechny pobočky: 3 body
A
B
C
D
E
F
G
H
A
-
81
99
72
71
66
93
60
Viz. Olo.
Str.
Svi.
Brno
B
81
-
185
158
157
98
179
C
99
185
-
81
48
159
D
72
158
81
-
90
E
71
157
48
90
-
F
66
98
159
73
142
G
93
179
18
58
H
60
70
158
137
Brno Jih. -
85
103
74
72
65
91
70
Jihlava
85
-
168
147
132
94
159
72
18
158
Vizovice
103
168
-
83
47
139
24
136
73
58
137
Olomouc
74
147
83
-
91
70
45
127
142
47
110
Strážnice
72
132
47
91
-
131
37
108
-
136
131
Svitavy
65
94
139
70
131
-
124
129
47
136
-
157
Zlín
91
159
24
45
37
124
-
142
110
131
157
-
Znojmo
63
72
136
127
108
129
142
-
3 body
59
Zlín Zno. 63
60
10
