E. Michlowicz: Zagadnienia transportowe E. Michlowicz: Zagadnienia transportowe E. Michlowicz: Zagadnienia transportowe
Zadania programowania liniowego w postaci macierzowej Ax = b jest niesprzeczny oraz n>m,
12
to ten ma
cx max(min)
bazowych.
ZAGADNIENIA (zadania) TRANSPORTOWE Ax b
x 0 n!
1.Zagadnienia programowania liniowego
m! ( n m )
gdzie:
a11 a12 a1n
a21 a22 a2n
A ,
-
matematycznym ma na celu sprowadzenie problemu wyboru najlepszej decyzji do
am1 am 2 amn
decyzji przy 2. Zadania (Zagadnienia) transportowe
b1
),
b2
b -
),
tzw. zadania transportowe.
dla danych zmiennych decyzyjnych,
bm
funkc
w 1934 r. przez L.
x1
Kantorowicza
x2
liniowego.
x
- wektor zmiennych decyzyjnych,
funkcja celu: problemu Hitchcoca od nazwiska angielskiego badacza,
x
n n
c x max(min) klasycznego zadania transportowego.
j j
j 1
c c1 c2 cn - wektor wag funkcji celu.
klasycznego zagadnienia transportowego ilustruje rysunek 1.
ograniczenia:
n
aij x bi (i=1,2,...,m)
j
punkt punkt
j 1
liniowego jest metoda Simpleks nadania i trasach (i, j) odbioru j
n
popyt
aij x bi (i=m+1,...,p)
j a1 b1
j 1 Metoda Simpleks
n
programowania liniowego w postaci:
aij x bi (i=p+1,...,p) a2 b2
j
j 1 cx max
. .
Ax b
x 0 (j = 1,2,...,n1) gdzie: n1 n
j
. .
x 0
. .
wektor zmiennych decyzyjnych : an bm
Przez B oznaczamy m- m liniowo
x = ( x1, x2 ,... ,x n)
A.
Macierz B nazywamy , jej kolumny
Rys.1. Schemat klasycznego zadania transportowego
rozw . kolumny macierzy A kolumnami niebazowymi.
Zmienne
nazywamy
niebazowymi.
:
.
1 2 3
E. Michlowicz: Zagadnienia transportowe E. Michlowicz: Zagadnienia transportowe E. Michlowicz: Zagadnienia transportowe
-n- ai - -W)
jednostkami produktu (i=....n) zbilansowanej:
xij dla trasy (1,1).
oraz -m- Przypadek 1 xij wyznaczamy wg wzoru:
bj jednostek produktu (j=1 .. m). ):
xij = min{a1, b1}
ponadto: m n
ai bj
a1, b1 odejmujemy x11 i otrzymane wyniki wstawiamy odpowiednio
i 1 j 1
zamiast a1, b1
koszty jednostkowe cij
wynosi 0. W kolejnym kroku przechodzimy do elementu xij o-
am+1 :
dostawcy i do odbiorcy j.
n m
xij (zmienne decyzyjne) i-tego dostawcy do j-tego
am 1 b a
j i wierszy i kolumn.
odbiorcy,
j 1 i 1
cm+1,1=0,...,cm+1,n=0 .
n
xij d
x b ,
i j j j 1,2,..., m
i 1
Przypadek 2
m
xij.
magazynowe
x a
ij i , i 1,2,...,n oraz:
m n Dla wybranego wiersza
j 1
ai b
j
i 1 j 1
xij 0 , xij = min {ai ,bj }
i 1,2,...,n; j 1,2,...,m
W celu uzyskania postaci zbilansowanej, wprowadzamy
bn+1 : -zachodniego, od
m n
ai, bj odejmujemy xij ai, bj.
b ai bj
n 1
m n
i 1 j 1
xij i powtarzamy operacje.
z c x
ij ij Dodatkowo do macierzy ko zynniki:
min
i 1 j 1
cn+1,1=0,...,cn+1,m= 0
kolumny.
: etapy:
I.
tzw. pierwsze bazowe
(ZZT) .
rozwi
m n
ai b xij.
j
-zachodniego;
i 1 j 1
ai lub bj a xij wynosi 0.
,
ej xij
.
II.
optymalne.
zadaniu niezbilansowanym :
Otwartym Zadaniem Transportowym (OZT).
metoda MODI (Modified Distribution Methode).
4 5 6
E. Michlowicz: Zagadnienia transportowe E. Michlowicz: Zagadnienia transportowe E. Michlowicz: Zagadnienia transportowe
, czyli:
Liczba zmiennych decyzyjnych: 3 * 4 = 12.
z ( xij ) = 40x11 + 30x12 + 40x13 + 10x14 +
30x21 + 70x22 + 60x23 + 20x24 +
50x31 + 30x32 + 60x33 + 70x34 min
ZADANIE TRANSPORTOWE
4
x x x x x1 j 350 (dostawca D1)
11 12 13 14
i 1
D1, D2, D3
tzn.:
zaopatruje w odpady 4 spalarnie: S1, S2, S3 i S4.
suma od dostawcy D1 do wszystkich spalarni powinna x11
Dane: 12 13 14
dostawcy;
- x21
- dostaw Ai (w tonach),
- zapotrzebowanie spalarni Bj (w tonach) 4
x31
x x x x x2 j 250 (dostawca D2) 34
21 23 24
22
i 1
Dane zawarto w tablicy 1.
4
x31 x32 x33 x34 x3 j 400 (dostawca D3)
kilka metod do wyboru !
i 1
Tab. 1. Jednostkowe koszty transportu
3
Spalarnie
x x x xi 1 200 (odbiorca S1)
11 21 31
Dostawcy
i 1
S1 S2 S3 S4 Ai [ton] tzn. 1 od wszystkich trzech
D1 40 30 40 10 350 ;
D2 30 70 60 20 250
D3 50 30 60 70 400
popyt
3
Bj [ton] 200 300 250 250 1000 x x x32 xi 2 300
12 22 (odbiorca S2)
i 1
cji: 3
z (xij). x x x xi 3 250
13 23 33 (odbiorca S3)
i 1
3
x x x xi 4 250 (odbiorca S4)
14 24 34
i 1
3 4
Ai B 10 00 [ton]
j
i 1 j 1
xij 0 dla (i = 1,2,3; j = 1,2,3,4),
Zmienne decyzyjne xij
dostarczona:
od i-tego dostawcy (i=1,2,3) do j-tej spalarni (j=1,2,3,4)
7 8 9