Dopravní úloha
Základy operačního výzkumu Přednáška č. 9 Jiří Neubauer Katedra ekonometrie FEM UO Brno
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Distribuční úlohy
Budeme se zabývat 2 typy distribučních úloh dopravní úloha přiřazovací problém
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Dopravní úloha
V dopravním problému se v typickém případě jedná o rozvržení rozvozu nějakého zboží či materiálu z dodavatelských míst k odběratelům tak, aby byly minimalizovány celkové náklady související s tímto rozvozem.
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Dopravní úloha - příklad Od dvou dodavatelů D1 a D2 je třeba přemístit zboží ke 3 spotřebitelům S1 , S2 a S3 . Kapacity dodavatelů jsou D1 : 800 ks D2 : 1200 ks Požadavky spotřebitelů jsou S1 : 600 ks S2 : 900 ks S3 : 500 ks Náklady na přepravu 1 kusu zboží mezi jednotlivými dodavateli a spotřebiteli udávají tzv. přepravní sazby cij (Jedná se o náklady na přepravu 1 ks zboží od dodavatele Di , ke spotřebiteli Sj .) V našem případě c11 = 30, c12 = 10, c13 = 5, c21 = 15, c22 = 20 a c23 = 12.
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Dopravní úloha - příklad
Úkolem je sestavit optimální plán přepravy, tj. rozhodnout, po kterých cestách a v jakém množství se má zboží přepravovat, aby celkové přepravní náklady byly minimální. Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Dopravní úloha - příklad proměnné: xij . . . počet výrobků přepravených od dodavatele Di ke spotřebiteli Sj omezení: jsou dána požadavky spotřebitelů a kapacitami dodavatelů
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Dopravní úloha - příklad proměnné: xij . . . počet výrobků přepravených od dodavatele Di ke spotřebiteli Sj omezení: jsou dána požadavky spotřebitelů a kapacitami dodavatelů D1 : x11 + x12 + x13 = 800
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Dopravní úloha - příklad proměnné: xij . . . počet výrobků přepravených od dodavatele Di ke spotřebiteli Sj omezení: jsou dána požadavky spotřebitelů a kapacitami dodavatelů D1 : x11 + x12 + x13 = 800 D2 : x21 + x22 + x23 = 1200
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Dopravní úloha - příklad proměnné: xij . . . počet výrobků přepravených od dodavatele Di ke spotřebiteli Sj omezení: jsou dána požadavky spotřebitelů a kapacitami dodavatelů D1 : x11 + x12 + x13 = 800 D2 : x21 + x22 + x23 = 1200 S1 : x11 + x21 = 600
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Dopravní úloha - příklad proměnné: xij . . . počet výrobků přepravených od dodavatele Di ke spotřebiteli Sj omezení: jsou dána požadavky spotřebitelů a kapacitami dodavatelů D1 : D2 : S1 : S2 :
x11 x21 x11 x12
+ + + +
x12 + x13 x22 + x23 x21 x22
Jiří Neubauer
= = = =
800 1200 600 900
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Dopravní úloha - příklad proměnné: xij . . . počet výrobků přepravených od dodavatele Di ke spotřebiteli Sj omezení: jsou dána požadavky spotřebitelů a kapacitami dodavatelů D1 : D2 : S1 : S2 : S3 :
x11 x21 x11 x12 x13
+ + + + +
x12 + x13 x22 + x23 x21 x22 x23
Jiří Neubauer
= = = = =
800 1200 600 900 500
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Dopravní úloha - příklad proměnné: xij . . . počet výrobků přepravených od dodavatele Di ke spotřebiteli Sj omezení: jsou dána požadavky spotřebitelů a kapacitami dodavatelů D1 : D2 : S1 : S2 : S3 :
x11 x21 x11 x12 x13
xij ≥ 0,
+ + + + +
x12 + x13 x22 + x23 x21 x22 x23
i = 1, 2
Jiří Neubauer
= = = = =
800 1200 600 900 500
j = 1, 2, 3
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Dopravní úloha - příklad proměnné: xij . . . počet výrobků přepravených od dodavatele Di ke spotřebiteli Sj omezení: jsou dána požadavky spotřebitelů a kapacitami dodavatelů D1 : D2 : S1 : S2 : S3 :
x11 x21 x11 x12 x13
xij ≥ 0,
+ + + + +
x12 + x13 x22 + x23 x21 x22 x23
i = 1, 2
= = = = =
800 1200 600 900 500
j = 1, 2, 3
účelová funkce z = 30x11 + 10x12 + 5x13 + 1521 + 20x22 + 12x23 Jiří Neubauer
Základy operačního výzkumu
→
min
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Dopravní úloha – obecný model Uvažujme m dodavatelů D1 , D2 . . . , Dm s kapacitami a1 , a2 , . . . , am jednotek zboží. Toto zboží se má přepravit k n spotřebitelům S1 , S2 , . . . , Sn , jejichž požadavky jsou b1 , b2 , . . . , bn . Náklady na přepravu jednotky zboží od dodavatele Di ke spotřebiteli Sj označme cij (i = 1, . . . , m j = 1, . . . , n).
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Dopravní úloha – obecný model Uvažujme m dodavatelů D1 , D2 . . . , Dm s kapacitami a1 , a2 , . . . , am jednotek zboží. Toto zboží se má přepravit k n spotřebitelům S1 , S2 , . . . , Sn , jejichž požadavky jsou b1 , b2 , . . . , bn . Náklady na přepravu jednotky zboží od dodavatele Di ke spotřebiteli Sj označme cij (i = 1, . . . , m j = 1, . . . , n). Předpokládejme dále, že úloha je vyrovnaná, tedy platí m X
ai =
i=1
Jiří Neubauer
n X
bj .
j=1
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Dopravní úloha – obecný model Uvažujme m dodavatelů D1 , D2 . . . , Dm s kapacitami a1 , a2 , . . . , am jednotek zboží. Toto zboží se má přepravit k n spotřebitelům S1 , S2 , . . . , Sn , jejichž požadavky jsou b1 , b2 , . . . , bn . Náklady na přepravu jednotky zboží od dodavatele Di ke spotřebiteli Sj označme cij (i = 1, . . . , m j = 1, . . . , n). Předpokládejme dále, že úloha je vyrovnaná, tedy platí m X
ai =
i=1
Pn Di : j=1 xij = ai Pm Sj : i=1 xij = bj
n X
bj .
j=1
i = 1, 2, . . . , m j = 1, 2, . . . , n
Jiří Neubauer
m + n vlastních omezení
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Dopravní úloha – obecný model Uvažujme m dodavatelů D1 , D2 . . . , Dm s kapacitami a1 , a2 , . . . , am jednotek zboží. Toto zboží se má přepravit k n spotřebitelům S1 , S2 , . . . , Sn , jejichž požadavky jsou b1 , b2 , . . . , bn . Náklady na přepravu jednotky zboží od dodavatele Di ke spotřebiteli Sj označme cij (i = 1, . . . , m j = 1, . . . , n). Předpokládejme dále, že úloha je vyrovnaná, tedy platí m X
ai =
i=1
n X
bj .
j=1
Pn Di : j=1 xij = ai Pm Sj : i=1 xij = bj xij ≥ 0
i = 1, 2, . . . , m m + n vlastních omezení j = 1, 2, . . . , n i = 1, . . . , m m · n podmínek nezápornosti j = 1, . . . , n
Jiří Neubauer
Základy operačního výzkumu
Metoda VAM Test optima Zlepšování řešení
Dopravní úloha
Dopravní úloha – obecný model Uvažujme m dodavatelů D1 , D2 . . . , Dm s kapacitami a1 , a2 , . . . , am jednotek zboží. Toto zboží se má přepravit k n spotřebitelům S1 , S2 , . . . , Sn , jejichž požadavky jsou b1 , b2 , . . . , bn . Náklady na přepravu jednotky zboží od dodavatele Di ke spotřebiteli Sj označme cij (i = 1, . . . , m j = 1, . . . , n). Předpokládejme dále, že úloha je vyrovnaná, tedy platí m X
ai =
n X
i=1
bj .
j=1
Pn Di : j=1 xij = ai Pm Sj : i=1 xij = bj xij ≥ 0 z=
m X n X
i = 1, 2, . . . , m m + n vlastních omezení j = 1, 2, . . . , n i = 1, . . . , m m · n podmínek nezápornosti j = 1, . . . , n cij xij
→
min
(celková cena přepravy)
i=1 j=1 Jiří Neubauer
Základy operačního výzkumu
Metoda VAM Test optima Zlepšování řešení
Dopravní úloha
Dopravní úloha Výchozí údaje i vlastní omezení se zapisují do tabulky. Kapacity ai
S1
S2
···
Sn
D1
x11 c11
x12 c12
···
x1n c1n
a1
D2
x21 c21
x22 c22
···
x2n c2n
a2
.. . Dm Požadavky bj
.. .
.. .
xm1 cm1 b1
.. .
xm2 cm2 b2
Jiří Neubauer
··· ···
.. . xmn cmn bn
Základy operačního výzkumu
.. . am celkem
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Dopravní úloha
P Pn Je-li úloha vyrovnaná ( m i=1 ai = j=1 bj ), pak je jedno z m + n vlastních omezení lineárně závislé na ostatních. Základní řešení může mít tedy maximálně m + n − 1 kladných proměnných (tj. obsazených polí). Nedegenerované řešení obsahuje právě m + n − 1 kladných xij .
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Dopravní úloha
P Pn Je-li úloha vyrovnaná ( m i=1 ai = j=1 bj ), pak je jedno z m + n vlastních omezení lineárně závislé na ostatních. Základní řešení může mít tedy maximálně m + n − 1 kladných proměnných (tj. obsazených polí). Nedegenerované řešení obsahuje právě m + n − 1 kladných xij . Spojí-li se obsazená pole u základního řešení vodorovnými a svislými čarami, nesmí vytvořit uzavřený obvod.
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Vogelova aproximační metoda
Vogelova aproximační metoda (VAM) slouží k nalezení výchozího řešení dopravního problému.
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Vogelova aproximační metoda
Vogelova aproximační metoda (VAM) slouží k nalezení výchozího řešení dopravního problému. Určí políčko Di Sj , které obsadíme maximálním množstvím xij přepravovaného množství zboží s ohledem na kapacitu ai a požadavek bj s přihlédnutím na již obsazená políčka v i-tém řádku a j-tém sloupci.
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Vogelova aproximační metoda
Vogelova aproximační metoda (VAM) slouží k nalezení výchozího řešení dopravního problému. Určí políčko Di Sj , které obsadíme maximálním množstvím xij přepravovaného množství zboží s ohledem na kapacitu ai a požadavek bj s přihlédnutím na již obsazená políčka v i-tém řádku a j-tém sloupci. Vyčerpáme-li kapacitu některého dodavatele, proškrtneme daný řádek.
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Vogelova aproximační metoda
Vogelova aproximační metoda (VAM) slouží k nalezení výchozího řešení dopravního problému. Určí políčko Di Sj , které obsadíme maximálním množstvím xij přepravovaného množství zboží s ohledem na kapacitu ai a požadavek bj s přihlédnutím na již obsazená políčka v i-tém řádku a j-tém sloupci. Vyčerpáme-li kapacitu některého dodavatele, proškrtneme daný řádek. Vyčerpáme-li požadavky některého spotřebitele, proškrtneme daný sloupec.
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Vogelova aproximační metoda
Postup VAM 1
V každém řádku resp. sloupci určíme 2 nejnižší přepravní sazby a vypočteme jejich rozdíl (diferenci) a zapíšeme do odpovídajícího řádku resp. sloupce.
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Vogelova aproximační metoda
Postup VAM 1
V každém řádku resp. sloupci určíme 2 nejnižší přepravní sazby a vypočteme jejich rozdíl (diferenci) a zapíšeme do odpovídajícího řádku resp. sloupce.
2
Najdeme řádek či sloupec s největší diferencí a v tomto řádku či sloupci obsadíme políčko s minimální sazbou.
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Vogelova aproximační metoda
Postup VAM 1
V každém řádku resp. sloupci určíme 2 nejnižší přepravní sazby a vypočteme jejich rozdíl (diferenci) a zapíšeme do odpovídajícího řádku resp. sloupce.
2
Najdeme řádek či sloupec s největší diferencí a v tomto řádku či sloupci obsadíme políčko s minimální sazbou.
3
Vyčerpáme-li kapacitu dodavatele, proškrtneme řádek, uspokojíme-li požadavky spotřebitele, proškrtneme sloupec.
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Vogelova aproximační metoda
Postup VAM 1
V každém řádku resp. sloupci určíme 2 nejnižší přepravní sazby a vypočteme jejich rozdíl (diferenci) a zapíšeme do odpovídajícího řádku resp. sloupce.
2
Najdeme řádek či sloupec s největší diferencí a v tomto řádku či sloupci obsadíme políčko s minimální sazbou.
3
Vyčerpáme-li kapacitu dodavatele, proškrtneme řádek, uspokojíme-li požadavky spotřebitele, proškrtneme sloupec.
4
Pokračujeme bodem 2, neuvažujeme proškrtnutá ani obsazená pole.
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Test optima K tabulce přidáme sloupec řádkových čísel ui (i = 1, . . . , m) a řádek sloupcových čísel vj (j = 1, . . . , n). Předpokládejme, že máme obsazeno m + n − 1 políček (nedegerované řešení). Pro obsazená pole platí ui + vj = cij . Protože čísel ui a vj je m + n, ale obsazených polí je m + n − 1, je třeba jedno z čísel ui a vj zvolit (obvykle se volí u1 = 0) a ostatní dopočítat podle uvedeného vztahu.
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Test optima K tabulce přidáme sloupec řádkových čísel ui (i = 1, . . . , m) a řádek sloupcových čísel vj (j = 1, . . . , n). Předpokládejme, že máme obsazeno m + n − 1 políček (nedegerované řešení). Pro obsazená pole platí ui + vj = cij . Protože čísel ui a vj je m + n, ale obsazených polí je m + n − 1, je třeba jedno z čísel ui a vj zvolit (obvykle se volí u1 = 0) a ostatní dopočítat podle uvedeného vztahu. U proškrtnutých polí pomocí známých čísel ui a vj určíme nepřímé sazby cij0 podle vztahu ui + vj = cij0 . (Tyto sazby napíšeme do dolního levého rohu proškrtnutých políček.) Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Test optima
1
Je-li u všech proškrtnutých polí cij0 ≤ cij , pak je dané řešení optimální.
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Test optima
1
2
Je-li u všech proškrtnutých polí cij0 ≤ cij , pak je dané řešení optimální. Existuje-li pole, kde cij0 > cij , pak dané není optimální a lze jej zlepšit.
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Test optima
1
2
Je-li u všech proškrtnutých polí cij0 ≤ cij , pak je dané řešení optimální. Existuje-li pole, kde cij0 > cij , pak dané není optimální a lze jej zlepšit.
Pozn. Máme-li optimální řešení a pro některé políčko platí cij0 = cij , pak existuje jiné optimální – alternativní – řešení.
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Zlepšování řešení Pokud pro některé neobsazené pole platí cij0 > cij , pak řešení není optimální a lze najít lepší řešení.
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Zlepšování řešení Pokud pro některé neobsazené pole platí cij0 > cij , pak řešení není optimální a lze najít lepší řešení. 1 Najdeme políčko, kde c 0 > c . Pokud takových políček více, ij ij zvolíme to, kde je rozdíl cij0 − cij největší (volba vstupující proměnné).
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Zlepšování řešení Pokud pro některé neobsazené pole platí cij0 > cij , pak řešení není optimální a lze najít lepší řešení. 1 Najdeme políčko, kde c 0 > c . Pokud takových políček více, ij ij zvolíme to, kde je rozdíl cij0 − cij největší (volba vstupující proměnné). 2 Vytvoříme tzv. uzavřený okruh (mnohoúhelník se sudým počtem vrcholů, vrcholy mohou být jen obsazená pole a vybrané neobsazené pole, jednotlivé hrany – svislá a vodorovná – se střídají).
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Zlepšování řešení Pokud pro některé neobsazené pole platí cij0 > cij , pak řešení není optimální a lze najít lepší řešení. 1 Najdeme políčko, kde c 0 > c . Pokud takových políček více, ij ij zvolíme to, kde je rozdíl cij0 − cij největší (volba vstupující proměnné). 2 Vytvoříme tzv. uzavřený okruh (mnohoúhelník se sudým počtem vrcholů, vrcholy mohou být jen obsazená pole a vybrané neobsazené pole, jednotlivé hrany – svislá a vodorovná – se střídají). 3 Neobsazené pole v okruhu označíme znaménkem ⊕, v dalších polích potom střídáme znaménka , ⊕, · · · .
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Zlepšování řešení Pokud pro některé neobsazené pole platí cij0 > cij , pak řešení není optimální a lze najít lepší řešení. 1 Najdeme políčko, kde c 0 > c . Pokud takových políček více, ij ij zvolíme to, kde je rozdíl cij0 − cij největší (volba vstupující proměnné). 2 Vytvoříme tzv. uzavřený okruh (mnohoúhelník se sudým počtem vrcholů, vrcholy mohou být jen obsazená pole a vybrané neobsazené pole, jednotlivé hrany – svislá a vodorovná – se střídají). 3 Neobsazené pole v okruhu označíme znaménkem ⊕, v dalších polích potom střídáme znaménka , ⊕, · · · . 4 Najedeme nejmenší hodnotu u polí (volba vystupující proměnné).
Jiří Neubauer
Základy operačního výzkumu
Dopravní úloha
Metoda VAM Test optima Zlepšování řešení
Zlepšování řešení Pokud pro některé neobsazené pole platí cij0 > cij , pak řešení není optimální a lze najít lepší řešení. 1 Najdeme políčko, kde c 0 > c . Pokud takových políček více, ij ij zvolíme to, kde je rozdíl cij0 − cij největší (volba vstupující proměnné). 2 Vytvoříme tzv. uzavřený okruh (mnohoúhelník se sudým počtem vrcholů, vrcholy mohou být jen obsazená pole a vybrané neobsazené pole, jednotlivé hrany – svislá a vodorovná – se střídají). 3 Neobsazené pole v okruhu označíme znaménkem ⊕, v dalších polích potom střídáme znaménka , ⊕, · · · . 4 Najedeme nejmenší hodnotu u polí (volba vystupující proměnné). 5 Tuto hodnotu přičteme k ⊕ polím a odečteme od polí označených znaménkem . Ostatní políčka opíšeme. Jiří Neubauer
Základy operačního výzkumu
