MME I - cv. cˇ . 7
15. 11. 2010
Kl´ıcˇ ov´a slova: Dopravn´ı probl´em, Metody k nalezen´ı v´ychoz´ıho rˇ eˇsen´ı, Optim´aln´ı rˇ eˇsen´ı. Dopravn´ı probl´em je jednou z podskupin distribuˇcn´ı u´ lohy (d´ale jeˇstˇe probl´em pˇriˇrazovac´ı a obecn´a distribuˇcn´ı u´ loha).
1
Ilustrativn´ı pˇr´ıklad
Podnik m´a 5 pek´aren P1 , P2 , P3 , P4 a P5 . Pek´arny odeb´ıraj´ı mouku ze 4 ml´yn˚u M1 , M2 , M3 a M4 . Pek´arna P1 poˇzaduje dennˇe 90 t mouky, pek´arna P2 100 t mouky, pek´arna P3 90 t mouky, pek´arna P4 90 t mouky a pek´arna P5 90 t mouky. Ml´yn M1 m´a denn´ı produkci 100 t mouky, ml´yn M2 110 t mouky, ml´yn M3 120 t mouky a ml´yn M4 130 t mouky. Pˇrepravn´ı n´aklady na dod´avku 1 tuny mouky z kaˇzd´eho ml´ynu do kaˇzd´e pek´arny ud´av´a tabulka. C´ılem je stanovit optimalizaˇcn´ı pˇrepravn´ı pl´an – urˇcit mnoˇzstv´ı mouky, kter´e budou dod´avat jednotliv´e ml´yny jednotliv´ym pek´arn´am tak, aby celkov´e pˇrepravn´ı n´aklady byly minim´aln´ı. Tab. 1: Tabulka pˇrepravn´ıch n´aklad˚u M1 M2 M3 M4 poˇzadavky
2
P1 7 14 11 7 90
P2 P3 10 12 3 11 5 12 7 4 100 90
P4 4 5 9 2 90
P5 12 9 2 5 90
kapacity 100 110 120 130
Trochu teorie
Znaˇcen´ı: cij – n´aklady spojen´e s pˇrepravou jednotky i-t´eho n´akladu k j-t´emu spotˇrebiteli, xij – objem pˇrepravovan´e produkce, ai – kapacity dodavatele, bi – poˇzadavky spotˇrebitele. Vyrovnanost: U DP vyˇzadujeme vyrovnanost poˇzadavk˚u spotˇrebitele a kapacit dodavatele. Pokud nen´ı probl´em vyrovnan´y zav´ad´ıme fiktivn´ıho spotˇrebitele nebo dodavatele. Matematick´y model:
1
MME I - cv. cˇ . 7
15. 11. 2010
Z povahy probl´emu plyne, zˇ e u´ cˇ elov´a funkce bude minimalizaˇcn´ı a omezen´ı budou souviset s kapacitami dodavatel˚u a poˇzadavky spotˇrebitel˚u. Dost´av´ame tedy soustavu rovnic: Prim´arn´ı u´ loha m P n P fmin = cij xij
zmax
Du´aln´ı u´ loha m n P P = ai ui + bj vj
i=1 j=1
i=1
j=1
n P
xij = ai ,
ui + vi ≤ cij ,
j=1 m P
xij = bj ,
ui ≥ 0, vi ≥ 0,
i=1
3
Algoritmus rˇ eˇsen´ı
Stejnˇe jako jin´e probl´emy LP je moˇznost i DP ˇreˇsit pomoc´ı simplexn´ı metody. Vzhledem k poˇctu promˇenn´ych a omezen´ı je to n´aroˇcn´e, proto se pro DP pouˇz´ıv´a jin´y algoritmus. Algoritmus se skl´ad´a ze 3 z´akladn´ıch krok˚u: 1. nalezen´ı v´ychoz´ıho ˇreˇsen´ı, 2. test optimality, 3. pˇrechod k optim´aln´ımu ˇreˇsen´ı.
3.1 Nalezen´ı v´ychoz´ıho rˇ eˇsen´ı Pro nalezen´ı v´ychoz´ıho ˇreˇsen´ı pouˇz´ıv´ame 3 z´akladn´ı metody, vˇsechny budeme demonstrovat na ilustrativn´ım pˇr´ıkladu. V´ypoˇcty se dˇelaj´ı v tabulce, kter´a m´a m ˇra´ dk˚u a n sloupc˚u. Do bunˇek zapisujeme t´ımto zp˚usobem: cij xij
3.1.1 Metody k nalezen´ı v´ychoz´ıho rˇ eˇsen´ı Pro nalezen´ı v´ychoz´ıho ˇreˇsen´ı jsme si uvedli 3 z´akladn´ı metody: 1. Metoda severoz´apadn´ıho rohu (SZR) • tabulku vyplˇnujeme od lev´eho horn´ıho rohu, • dosazujeme min(ai , bj ), m´ame tyto moˇznosti: 2
MME I - cv. cˇ . 7
15. 11. 2010
a) xij = ai – vyˇcerpali jsme kapacity i-t´eho ˇra´ dku, – ˇra´ dek i vyˇskrt´ame (nep´ısˇeme nuly, ale –), – oprav´ıme poˇzadavek bj , – posuneme se o ˇra´ dek n´ızˇ e, b) xij = bj – vyˇcerpali jsme poˇzadavky j-t´eho sloupce – sloupec j vyˇskrt´ame, – oprav´ıme poˇzadavek ai , – posuneme se o sloupec doprava, • postup konˇc´ı uspokojen´ım vˇsech poˇzadavk˚u a vyˇcerp´an´ım kapacit. 2. Indexn´ı metoda • pˇresnˇejˇs´ı neˇz SZR – bere v u´ vahu cenov´e sazby, • tabulku obsazujeme od pole s minim´aln´ı hodnotou cij , • dosazujeme, m´ame tyto moˇznosti: a) xij = ai – vyˇcerpali jsme kapacity i-t´eho ˇra´ dku, – ˇra´ dek i vyˇskrt´ame, – oprav´ıme poˇzadavek bj , b′j = bj − ai , – posuneme se o ˇra´ dek n´ızˇ e, b) xij = bj – vyˇcerpali jsme poˇzadavky j-t´eho sloupce – sloupec j vyˇskrt´ame, – oprav´ıme poˇzadavek ai , a′i = ai − bj , – posuneme se o sloupec doprava, • postup konˇc´ı uspokojen´ım vˇsech poˇzadavk˚u a vyˇcerp´an´ım kapacit. 3. Vogelova aproximaˇcn´ı metoda (VAM) • nejpˇresnˇejˇs´ı, ale tak´e nejpracnˇejˇs´ı, • v t´eto metodˇe nerozliˇsujeme mezi ˇra´ dkem a sloupcem – oboj´ı ozn. jako ˇradu, • algoritmus metody prob´ıh´a po neobsazen´ych ˇrad´ach (nevyˇskrtan´e), • kroky algoritmu: 1. Vypoˇcteme diference ˇrad (d) – rozd´ıl mezi nejmenˇs´ı a druhou nejmenˇs´ı ci j. 2. V ˇradˇe s max(d) vybereme buˇnku s min(ci j) a za xi j dosad´ıme . 3. Pˇri existenci v´ıce ˇrad s max(d): 3
MME I - cv. cˇ . 7
15. 11. 2010
a) Nalezneme sedlov´y bod (SB), coˇz je bod, kde je ci j minim´aln´ı v ˇra´ dku i sloupci. Pˇri existenci v´ıce min(ci j) vybereme bod s maxim´aln´ım souˇctem d ˇrad a sloupc˚u. b) Pokud SB neexistuje udˇel´ame na ˇrad´ach s max(d) druh´e diference. Tu tvoˇr´ıme tak, zˇ e bereme rozd´ıl mezi druhou nejmenˇs´ı sazbou zkouman´e ˇrady a nejmenˇs´ı sazbou ˇrady na n´ı kolm´e v bodˇe druh´e nejmenˇs´ı sazby. 4. Dosad´ıme do vybran´e buˇnky m´ame opˇet 3 moˇznosti jako v pˇredchoz´ıch metod´ach. Po vyˇskrt´an´ı ˇra´ dk˚u i sloupc˚u je vˇzdy tˇreba pˇrepoˇc´ıtat diference. 5. Postup konˇc´ı uspokojen´ım vˇsech poˇzadavk˚u a vyˇcerp´an´ım kapacit.
4
Optim´aln´ı rˇ eˇsen´ı
Pˇr´ıklad 2 Pro n´asˇ vzorov´y pˇr´ıklad jsme pomoc´ı VAM dostali toto v´ychoz´ı ˇreˇsen´ı: Tab. 2: V´ychoz´ı rˇeˇsen´ı pˇr´ıkladu metodou VAM P1 7
P2 10 –
M1
90
M2
–
M3
–
M4
–
–
90
100
14
P4 4 10
P5 12 –
11
5 40
–
3 70
11
– 5
30 7
bi
P3 12 –
12 –
7
4 90 90
ai 100
9
9
110 2
–
90
2 40
–
90
90
120 5 130
Pro v´ychoz´ı ˇreˇsen´ı plat´ı, zˇ e m´ame v matici m×n m´ame m+n−1 obsazen´ych pol´ı (pokud tato podm´ınka neplat´ı m´ame tzv. degenerovan´e ˇreˇsen´ı – viz d´ale). Pˇri testov´an´ı optima ˇreˇsen´ı se pouˇz´ıvaj´ı 2 metody. Pˇri obou tˇechto metod´ach se vyuˇz´ıv´a tzv. redukovan´e sazby zij . Metody se liˇs´ı v´ypoˇctem t´eto sazby. V tabulce zapisujeme redukovanou sazbu do lev´eho doln´ıho rohu. Pole tabulky pot´e vypad´a n´asledovnˇe: 4
MME I - cv. cˇ . 7
15. 11. 2010 cij xij zij
I. Distribuˇcn´ı metoda Pˇri distribuˇcn´ı metodˇe tvoˇr´ıme uzavˇren´e okruhy (posloupnost pol´ı – vych´az´ıme z neobsazen´eho pole a stˇr´ıdavˇe postupujeme po ˇra´ dc´ıch a sloupc´ıch obsahuj´ıc´ıch obsazen´a pole). Ke kaˇzd´emu neobsazen´emu poli existuje pr´avˇe jeden okruh. Hodnotu redukovan´e sazby zij zjist´ıme tak, zˇ e postupnˇe odeˇc´ıt´ame a pˇriˇc´ıt´ame sazby cij pol´ı na vrcholech okruh˚u – lich´e vrcholy odeˇc´ıt´ame, sud´e pˇriˇc´ıt´ame. Pokud jsou vˇsechny redukovan´e sazby zij ≤ 0 m´ame optim´aln´ı ˇreˇsen´ı. Pokud je nˇejak´a redukovan´a sazba vˇetˇs´ı neˇz nula mus´ıme prov´est transformaci k dalˇs´ımu ˇreˇsen´ı: 1. vybereme pole s maxim´aln´ım zij , na okruhu pˇr´ısluˇs´ıc´ı tomuto poli budeme pˇresouvat mnoˇzstv´ı, 2. oznaˇc´ıme si vrcholy okruhu stˇr´ıdavˇe + a -, zaˇc´ın´ame + v obsazovan´em poli, 3. na na sud´ych vrcholech (oznaˇcen´ych -) vybereme minim´aln´ı xij – toto mnoˇzstv´ı budeme pˇresouvat, 4. k poli oznaˇcen´emu + toto mnoˇzstv´ı pˇriˇcteme, od pole oznaˇcen´eho budeme mnoˇzstv´ı odeˇc´ıtat, 5. opˇet provedeme test optima. II. Modifikovan´a distribuˇcn´ı metoda (MODI) Pˇri pouˇzit´ı MODI metody vyuˇz´ıv´ame vˇety o rovnov´azˇ nosti du´alnˇe sdruˇzen´ych u´ loh. Z duality plyne, zˇ e pro optim´aln´ı ˇreˇsen´ı plat´ı: – obsazen´e pole plat´ı: ui + vj = cij – pro voln´a pole plat´ı: ui + vj < cij Hodnoty redukovan´e sazby t´eto metodˇe vypoˇcteme pomoc´ı vzorce: zij = ui + vj − cij . Postupujeme tedy takto: 1. nejdˇr´ıve mus´ıme vypoˇc´ıtat hodnotu du´aln´ıch promˇenn´ych (promˇenn´e ui odpov´ıdaj´ı ˇra´ dk˚um, vj sloupc˚um), 2. poloˇz´ıme jednu z promˇenn´ych rovnu 0 (napˇr. u1 ), 3. pomoc´ı v´ysˇe uveden´e podm´ınky pro rovnost souˇctu du´aln´ıch promˇenn´ych a cenov´e sazby dopoˇcteme pˇres obsazen´e pole ostatn´ı promˇenn´e, 5
MME I - cv. cˇ . 7
15. 11. 2010
4. vyuˇzijeme du´aln´ıch promˇenn´ych a pro neobsazen´e pole vypoˇcteme redukovan´e sazby – zij = ui + vj − cij . D´ale postupujeme stejnˇe jako u distribuˇcn´ı metody. Plat´ı tedy, zˇ e pokud jsou vˇsechny zij ≤ 0 dost´av´ame optim´aln´ı ˇreˇsen´ı. V opaˇcn´em pˇr´ıpadˇe prov´ad´ıme transformaci k dalˇs´ımu ˇreˇsen´ı jako u distribuˇcn´ı metody. V tabulce 1 vid´ıme, zˇ e v´ychoz´ım ˇreˇsen´ım metodou VAM dost´av´ame v tomto pˇr´ıpadˇe i optim´aln´ı ˇreˇsen´ı. Pˇr´ıklad 3 Postup transformace si tedy uk´azˇ eme pouˇzit´ım v´ychoz´ıho ˇreˇsen´ı metodou SZR. Tab. 3: V´ychoz´ı rˇeˇsen´ı pˇr´ıkladu metodou SZR P1
P2 7
M1
P3 12 –
10
90
10 6 14
M2
3
–
4 –
11
5
12 70
–
-10
5
bi vi
-13 90 7
0
–
110
-7
120
-6
2 9
2
50
– 10
7 –
100 9
–
-1
M4
ui
6
3 –
ai 12
–
11 20
90
P5
11
-14 M3
P4
7
4
– -10 100 10
2
5
–
40
90
90 18
90 15
90 18
130 -13
1
Z tabulky vid´ıme, zˇ e prvn´ı transformace bude prob´ıhat pˇres okruh pˇr´ısluˇs´ıc´ı poli se souˇradnicemi (1, 3).
6
