1
Badania
operacyjne
(#5)
dr inż. Marek Rabiński
Wyższa Szkoła Działalności Gospodarczej
2
Badania operacyjne (część 5)
z
Zagadnienie transportowe
3
Zagadnienie transportowe
z
Zagadnienie transportowe jest przykładem programowania liniowego, w
szczególności bardzo często zagadnienia optymalizacji w liczbach
całkowitych.
z
Rozpatrywana jest ustalona liczba dostawców i odbiorców określonego
towaru. Znana jest podaż każdego dostawcy i zapotrzebowanie
każdego odbiorcy (zwykle w zadanym odcinku czasu) oraz niezależne
od wielkości przewozu jednostkowe koszty transportu między
poszczególnymi dostawcami a odbiorcami. Rozwiązaniem zagadnienia
jest plan przewozów, który minimalizuje łączny koszt przewozów.
z
Zagadnienie transportowe może być zbilansowane (popyt równy jest
podaży) lub niezbilansowane gdy nie jest spełniony ten wymóg.
4
Elementy definiujące zagadnienie
z
Transportowane dobro x
ij
≥ 0, przy czym:
z
i – indeks dostawcy,
z
j – indeks odbiorcy.
z
Wektor wielkości dostaw i-tego dostawcy (i=1, … m):
a = [a
1
, a
2
, … a
m
]
T
z
Wektor popytu j-tego odbiorcy (j=1, … n):
b = [b
1
, b
2
, … b
n
]
T
5
Elementy definiujące zagadnienie
(c.d.)
z
Macierz przewozów określonego dobra od i-tego dostawcy do j-tego
odbiorcy:
|x
11
x
12
…
x
1n
|
X=[x
ij
]=
|x
21
x
22
…
x
2n
|
|…
…
…
… |
|x
m1
x
m2
…
x
mn
|
z
Macierz parametrów transportu (odległości przejazdów, kosztu
jednostkowego) określonego dobra od i-tego dostawcy do j-tego odbiorcy:
|c
11
c
12
…
c
1n
|
C=[c
ij
]=
|c
21
c
22
…
c
2n
|
|…
…
…
… |
|c
m1
c
m2
…
c
mn
|
z
Minimalizowany koszt przewozów:
f(x) = c
11
x
11
+c
12
x
12
+ … +c
mn
x
mn
–> min
6
Zagadnienie #1
f(x)= 3x
11
+4x
12
+5x
21
+6x
22
–> min
x
11
+x
12
= 150
+x
21
+x
22
= 200
x
11
+x
21
= 300
+x
12
+x
22
= 50
x
11
, x
12
, x
21
, x
22
≥ 0
2
7
Zagadnienie #1
8
Zagadnienie #2
f(x)= 3x
11
+4x
12
+5x
21
+6x
22
–> min
x
11
+x
12
= 150
+x
21
+x
22
= 200
x
11
+x
21
≤ 300
+x
12
+x
22
≤ 200
x
11
, x
12
, x
21
, x
22
≥ 0
9
Zagadnienie #2
f(x)= 3x
11
+4x
12
+5x
21
+6x
22
+c
31
x
31
+c
32
x
32
–> min
x
11
+x
12
= 150
+x
21
+x
22
= 200
+x
31
+x
32
= 150
x
11
+x
21
+x
31
= 300
+x
12
+x
22
+x
32
= 200
x
11
, x
12
, x
21
, x
22
, x
31
, x
32
≥ 0
10
Zagadnienie #2
11
Zagadnienie #3
f(x)= 3x
11
+4x
12
+5x
21
+6x
22
–> min
x
11
+x
12
≤ 250
+x
21
+x
22
≤ 200
x
11
+x
21
= 300
+x
12
+x
22
= 50
x
11
, x
12
, x
21
, x
22
≥ 0
12
Zagadnienie #3
f(x)= 3x
11
+4x
12
+c
13
x
13
+5x
21
+6x
22
+c
23
x
23
–> min
x
11
+x
12
+x
13
= 250
+x
21
+x
22
+x
23
= 200
x
11
+x
21
= 300
+x
12
+x
22
= 50
+x
13
+x
23
= 100
x
11
, x
12
, x
13
, x
21
, x
22
, x
23
≥ 0
3
13
Zagadnienie #3
14
Metody rozwiązywania zagadnień
z
Opierają się na liczbie węzłów bazowych – równej łącznej liczbie
dostawców i odbiorców pomniejszonej o jeden.
z
Metoda kąta północno–zachodniego za węzeł bazowy przyjmuje najdalej
wysunięty górny lewy.
z
Metoda minimalnego elementu przyjmuje za bazowy węzeł, dla którego
wartość kosztu jest najniższa.
z
Metoda VAM oblicza różnice w wierszach i kolumnach, znajduje
bezwzględną wartość różnicy między najmniejszymi elementami macierzy
kosztów w danej linii, w linii o największej wartości bezwzględnej wybiera
węzeł o najniższym koszcie jednostkowym.
15
Wyszukiwarka
Podobne podstrony:
BO 05 06 Kontrakt
BO 05 06 ZW12
BO 05 06 LWK46A
BO 05 06 LWK3
BO 05 06 LWK11
BO 05 06 ZW72
BO 05 06 ZW4[1]
BO 05 06 LWK4
BO 05 06 Komunikat 31 01 2006
BO 05 06 LWK2
BO 05 06 ZW52
BO 05 06 Wyklad Termin 2 Wymagania
BO 05 06 WTOP11 11
BO 05 06 Dobre rady
bo 05 20014
BO 05 06 Kontrakt
więcej podobnych podstron