DOPRAVNÍ ÚLOHA
(klasický dopravní problém)
PRIMÁRNÍ A DUÁLNÍ ÚLOHA
Máme 𝑚 skladišť (dodavatelů) číslo 𝑖 = 1, 2, … , 𝑚 s jedním druhem zboží. Skladiště číslo 𝑖
obsahuje 𝑎𝑖 jednotek zboží pro 𝑖 = 1, 2, … , 𝑚. Dále máme 𝑛 spotřebitelů (zákazníků,
odběratelů) číslo 𝑗 = 1, 2, … , 𝑛. Spotřebitel číslo 𝑗 požaduje dodat 𝑏𝑗 jednotek zboží pro 𝑗 =
1, 2, … , 𝑛. Cena přepravy jedné jednotky zboží od dodavatele 𝑖 ke spotřebiteli 𝑗 činí 𝑐𝑖𝑗 peněz
pro 𝑖 = 1, 2, … , 𝑚 a pro 𝑗 = 1, 2, … , 𝑛. Úkolem je stanovit plán přepravy zboží od dodavatelů
ke spotřebitelům tak, aby kapacity skladišť nebyly překročeny, požadavky zákazníků byly
uspokojeny a celkové přepravní náklady byly minimální.
Úlohu formulujeme jako úlohu lineárního programování. Účelem je stanovit optimální plán
přepravy. Jako 𝑥𝑖𝑗 označme plánované množství zboží, které bude přepraveno od dodavatele 𝑖
ke spotřebiteli 𝑗 pro 𝑖 = 1, 2, … , 𝑚 a pro 𝑗 = 1, 2, … , 𝑛. Primární úloha, která vyjadřuje
(tj. modeluje) zadanou dopravní úlohu, je následující:
minimalizovat  ∑ ∑ 𝑐𝑖𝑗 𝑥𝑖𝑗
𝑛
𝑗=1
𝑚
𝑖=1
za podmínek
∑ 𝑥𝑖𝑗
𝑛
𝑗=1
= 𝑎𝑖  pro 𝑖 = 1, 2, … , 𝑚
∑ 𝑥𝑖𝑗
𝑚
𝑖=1
= 𝑏𝑗  pro 𝑗 = 1, 2, … , 𝑛
𝑥𝑖𝑗 ≥ 0  pro 𝑖 = 1, 2, … , 𝑚 a pro 𝑗 = 1, 2, … , 𝑛
Duální úloha je následující:
maximalizovat  ∑ 𝑎𝑖 𝑢𝑖
𝑚
𝑖=1
+ ∑ 𝑏𝑗 𝑣𝑗
𝑛
𝑗=1
za podmínek
𝑢𝑖 + 𝑣𝑗 ≤ 𝑐𝑖𝑗  pro 𝑖 = 1, 2, … , 𝑚 a pro 𝑗 = 1, 2, … , 𝑛
kde 𝑢1, 𝑢2, … , 𝑢 𝑚 ∈ ℝ a 𝑣1, 𝑣2, … , 𝑣 𝑛 ∈ ℝ jsou proměnné.
Příklad: Následující tabulka shrnuje zadání klasické dopravní úlohy s 𝑚 = 2 dodavateli a
𝑛 = 3 odběrateli. Levý sloupeček zachycuje kapacity skladišť (𝑎1, 𝑎2), první řádek zachycuje
požadavky zákazníků (𝑏1, 𝑏2, 𝑏3) a ostatní buňky tabulky zachycují jednotkové přepravní
náklady (𝑐𝑖𝑗):
𝑏1 = 2 𝑏2 = 4 𝑏3 = 6
𝑎1 = 4 𝑐11 = 1 𝑐12 = 2 𝑐13 = 3
𝑎2 = 8 𝑐21 = 4 𝑐22 = 5 𝑐23 = 6
Primární úloha vypadá v tomto případě následovně:
minimalizovat  ∑ ∑ 𝑐𝑖𝑗 𝑥𝑖𝑗
3
𝑗=1
2
𝑖=1
za podmínek
∑ 𝑥𝑖𝑗
3
𝑗=1
= 𝑎𝑖  pro 𝑖 = 1, 2
∑ 𝑥𝑖𝑗
2
𝑖=1
= 𝑏𝑗  pro 𝑗 = 1, 2, 3
𝑥𝑖𝑗 ≥ 0  pro 𝑖 = 1, 2 a pro 𝑗 = 1, 2, 3
Ekvivalentně lze primární úlohu zapsat následovně:
1𝑥11 + 2𝑥12 + 3𝑥13 + 4𝑥21 + 5𝑥22 + 6𝑥23  ⟶  min
za podmínek
1𝑥11 + 1𝑥12 + 1𝑥13 + 1𝑥21 + 1𝑥22 + 1𝑥23 = 4   
1𝑥11 + 1𝑥12 + 1𝑥13 + 1𝑥21 + 1𝑥22 + 1𝑥23 = 8   
1𝑥11 + 1𝑥12 + 1𝑥13 + 1𝑥21 + 1𝑥22 + 1𝑥23 = 2   
1𝑥11 + 1𝑥12 + 1𝑥13 + 1𝑥21 + 1𝑥22 + 1𝑥23 = 4   
1𝑥11 + 1𝑥12 + 1𝑥13 + 1𝑥21 + 1𝑥22 + 1𝑥23 = 6   
a
𝑥11, 𝑥12, 𝑥13, 𝑥21, 𝑥22, 𝑥23 ≥ 0
Duální úloha vypadá tudíž následovně:
4𝑢1 + 8𝑢2 + 2𝑣1 + 4𝑣2 + 6𝑣3  ⟶  max
za podmínek
1𝑢1 + 1𝑢2 + 1𝑣1 + 1𝑣2 + 1𝑣3 ≤ 1    
1𝑢1 + 1𝑢2 + 1𝑣1 + 1𝑣2 + 1𝑣3 ≤ 2    
1𝑢1 + 1𝑢2 + 1𝑣1 + 1𝑣2 + 1𝑣3 ≤ 3    
1𝑢1 + 1𝑢2 + 1𝑣1 + 1𝑣2 + 1𝑣3 ≤ 4    
1𝑢1 + 1𝑢2 + 1𝑣1 + 1𝑣2 + 1𝑣3 ≤ 5    
1𝑢1 + 1𝑢2 + 1𝑣1 + 1𝑣2 + 1𝑣3 ≤ 6    
a
𝑢1, 𝑢2, 𝑣1, 𝑣2, 𝑣3 ∈ ℝ
Ekvivalentní, stručný zápis duální úlohy je zřejmý:
maximalizovat  ∑ 𝑎𝑖 𝑢𝑖
2
𝑖=1
+ ∑ 𝑏𝑗 𝑣𝑗
3
𝑗=1
za podmínek
𝑢𝑖 + 𝑣𝑗 ≤ 𝑐𝑖𝑗  pro 𝑖 = 1, 2 a pro 𝑗 = 1, 2, 3
a
𝑢1, 𝑢2, 𝑣1, 𝑣2, 𝑣3 ∈ ℝ
PŘÍKLAD
DOPRAVNÍ ÚLOHA
TERÉNNÍ ÚPRAVY – VYROVNÁNÍ TERÉNU
úroveň terénu stávající
úroveň terénu požadovaná
kopec = terén nad požadovanou úrovní = „dodavatel / zdroj“ 𝑖
údolí = terén pod požadovanou úrovní = „odběratel / spotřebitel“ 𝑗
𝑐𝑖𝑗 = cena za přepravu jedné jednotky zeminy z 𝑖 do 𝑗 = podle vzdálenosti