Doc. Ing. Tomáš Šubrt, Ph.D. PEF ZU v Praze
MODELY OPTIMÁLNÍHO D LENÍ ZAKÁZEK
MODELY OPTIMÁLNÍHO D LENÍ ZAKÁZEK Osnova prezentace Charakteristika problému Matematický model pro lineární problém Matematický model pro nelineární problém Možnosti ešení nelineárního modelu
CHARAKTERISTIKA PROBLÉMU Cílem p ísp vku je odvození a návrh ešení modelu matematického programování pro optimální d lení dodávek v logistické síti. Východiskem modelu je existence logistické sít ve form orientovaného grafu, kde první vrchol reprezentuje dodavatelské st edisko a ostatní vrcholy odbytová centra. Každé centrum vyžaduje ur ité množství zboží, každá spojnice mezi uzly – trasa – je ohodnocena vlastní nákladovou funkcí, ve form jednotkových náklad p epravy.
CHARAKTERISTIKA PROBLÉMU Strukturu sít a požadavk odbytových center vymezuje soustava lineárních omezujících podmínek. V p ípad dopravy s p evažujícími fixními náklady lze p edpokládat lineární nákladovou funkci. V p ípad dopravy s p evažující variabilní složkou náklad se dá p edpokládat konkávní nákladová funkce (s rozsahem p epravy degresivn klesají jednotkové náklady). Cílem je nalézt optimální p epravované množství na konkrétních trasách (s minimálními náklady).
CHARAKTERISTIKA PROBLÉMU Je dána logistická dopravní sí , kde jediný zdroj zásobuje všechny zákazníky (cíle). Zdroj je schopen uspokojit požadavky zákazník .(Požadavky v jednotkách zboží jsou uvedené ve vrcholech). Nosnost dopravních prost edk je neomezená. Zásilky lze libovoln d lit.
CHARAKTERISTIKA PROBLÉMU Vymezení stavového prostoru – soustava omezujících podmínek ve form lineárních rovnic. x5
10
15
íklad 1: x1
x1+x2+x3 x4
x2+x3+x4+x5 = 65
x2 Zdroj
x7 20
x3
= 80
x6
x2+x3+x4+x7 = 55 x3+x6+x7
= 35
35
xi i Ek
a j , k 1, 2,..., n 1 j Vk
xi… množství materiálu p epravovaného po hran i aj… požadavek j-tého zákazníka Ek… množina hran incidujících s uzly vpravo od ezu k Vk… množina uzl vpravo od ezu k
DOPRAVA S P EVAŽUJÍCÍMI FIXNÍMI NÁKLADY Minimaliza ní lineární kriteriální funkce Jednotkové náklady nezávisí na velikosti epravy funkce jednotkových náklad je konstantní funkce celkových náklad je lineární m
z
xi
min
i 1
ešení standardními algoritmy LP
DOPRAVA S P EVAŽUJÍCÍMI VARIABILNÍMI NÁKLADY
Jednotkové náklady klesají s rozsahem epravy Každá hrana (úsek dopravní cesty) charakterizován jinou funkcí jednotkových náklad Funkce jednotkových náklad je konkávní, obvykle ve tvaru r
zi ( xi )
i
si xi
DOPRAVA S P EVAŽUJÍCÍMI VARIABILNÍMI NÁKLADY Funkce celkových náklad má tvar m
z
m
xi zi ( xi ) i 1
i 1
ri xi si xi
min
Funkce celkových náklad po úprav m
z
ri si xi i 1
min
DOPRAVA S P EVAŽUJÍCÍMI VARIABILNÍMI NÁKLADY
ešitelnost úlohy Úloha nelineárního programování s minimaliza ní konkávní funkcí Obecn : heuristika, metaheuristika
Stavový prostor je vymezen lineárními rovnicemi i neomezené minimalizaci prohledáváme celý stavový prostor (pohybujeme se po celém povrchu parabolické kuželu) i omezení lineární rovností se m žeme pohybovat pouze v rámci omezující nadroviny. ešitelnost gradientními metodami – nap . metodami projekce gradientu na omezení (Rosenova metoda).
DOPRAVA S P EVAŽUJÍCÍMI VARIABILNÍMI NÁKLADY
ešitelnost úlohy SW realizace nap . s využitím Solver Frontline Systems - Premium Solver Platform, menší problémy Excel Slover íklad 1 (pokra ování)
Funkce jednotkových náklad díl ích tras: z1 ( x1 )
2 ; z2 ( x2 ) x1
1 ; z3 ( x3 ) 2 x2
3 ; z4 ( x4 ) 4 x3
5 ; z5 ( x5 ) x4
1 ; z6 ( x6 ) 1; z7 ( x7 ) 1; 2 x5
Funkce celkových náklad po úprav z (x)
2
x1
0, 5
2 x2
0, 75
x3
5
x4
0, 5
x5
x6
x7
DOPRAVA S P EVAŽUJÍCÍMI VARIABILNÍMI NÁKLADY
Výsledková zpráva Solver Nastavovaná bu ka (Min) Bu ka $J$13
Název
vodní hodnota
Celk. nakl. Z
15
Kone ná hodnota 0
19,18047654
Název
vodní hodnota
x2
Kone ná hodnota
$C$13
x1
0
25,000001
$C$14
x2
0
20
$C$15
x3
0
35
$C$16
x4
0
0
$C$17
x5
0
10,00000018
$C$18
x6
0
0
$C$19
x7
0
0
Zdroj
Název
Hodnota bu ky
Vzorec
20
x3
35
Omezující podmínky Bu ka
10
x1
né bu ky Bu ka
x5
Stav
Odchylka
$L$5
D1
80,000001 $L$5=$M$5
Neplatí
0
$L$6
D2
65,00000018 $L$6=$M$6
Neplatí
0
$L$7
D3
55 $L$7=$M$7
Neplatí
0
$L$8
D4
35 $L$8=$M$8
Neplatí
0
DOPRAVA S P EVAŽUJÍCÍMI VARIABILNÍMI NÁKLADY
U problém s p evažujícími variabilními náklady se se nikdy nevyplatí d lit zakázky! kaz Zvolme 1 výchozí uzel (zdroj) a 1 cílový uzel (zákazník) Mezi t mito uzly ur eme 2 cesty tak, aby jedna vedla p ímo a druhá nep ímo, tj. p es alespo jeden jiný uzel. Ustanovme prom nnou x vyjad ující podíl zboží dodaného p es jiného zákazníka ku veškerému dodanému zboží do cíle
DOPRAVA S P EVAŽUJÍCÍMI VARIABILNÍMI NÁKLADY Po substituci za jednotlivé prom nné z omezujících podmínek dostáváme jedinou nákladovou funkci, jejíž volný extrém na oboru D(f) = <0;1> hledáme. Funkce má lokální extrém vždy na hranicích D(f), tedy bu pro x=0 nebo x=1 veškeré zboží povezeme bu p ímo, nebo nep ímo (dle tvaru díl ích nákladových funkcí), ale nikdy po ástech!
DOPRAVA S P EVAŽUJÍCÍMI VARIABILNÍMI NÁKLADY 4 x1
x3 x2
Zdroj
4
x1
x2
8
x2
x3
4
z1
x1 1/ 2
z2
3 x2 1/ 2
z3 1
x x3
x3 x2
x3
4x z
x2
4x
4
x2
4(1 x)
x1 4(1 x) 8 x1
4(1 x)
2 (1 x) 6 (1 x) 4 x
DOPRAVA S P EVAŽUJÍCÍMI VARIABILNÍMI NÁKLADY x
z 0
8
0,05
8,097467
0,1
8,189717
0,15
8,276488
0,2
8,357453
10
0,25
8,43222
9
0,3
8,500311
0,35
8,561145
8
0,4
8,614012
7
0,45
8,658038
0,5
8,69213
0,55
8,714902
0,6
8,724555
0,65
8,718694
0,7
8,694016
0,75
8,645751
0,8
8,566563
0,85
8,444084
0,9
8,254176
0,95
7,934489
1
6,828427
z
6 z
5 4 3 2 1 0 0
0,2
0,4
0,6
0,8
1
MODELY OPTIMÁLNÍHO D LENÍ ZAKÁZEK
kuji za pozornost
