Zagadnienia transportowe
Klasyczne zadanie transportowe  definicja (1)
Klasyczne zadanie transportowe  problem najtańszego przewozu
jednorodnego dobra pomiędzy punktami nadania (dostawcy) a punktami
odbioru (odbiorcy).
punkty punkty
nadania odbioru
(i) (j)
poda\
popyt
x11 c11
a1 D1 O1 b1
x12 c12 x21 c21
x1n c1n
a2 D2 x22 c22 O2 b2
x2n c2n


xm1 cm1 xm2 cm2

am Dm xmn cmn On bn
Klasyczne zadanie transportowe  definicja (2)
Zało\
enia klasycznego zadania transportowego:
xij - zmienne decyzyjne; ilość przewo\
onego jednorodnego dobra
na trasie pomiędzy i-tym dostawcą a j-tym odbiorcą [i=1,2,& ,m;
j=1,2,& ,n;]
ai - parametr problemu; zasób dobra u i-tego dostawcy (poda\
)
[i=1,2,& ,m] a = [a1,a2,& ,am]
bj - parametr problemu; zapotrzebowanie na dobro j-tego odbiorcy
(popyt) [j=1,2,& ,n] b = [b1,b2,& ,bn]
cij - parametr problemu; koszt przewozu jednostki dobra na trasie
pomiędzy i-tym dostawcą a j-tym odbiorcą [i=1,2,& ,m;
j=1,2,& ,n;]
c11 c12 L c1n
îÅ‚ Å‚Å‚
ïÅ‚c c22 L c2n śł
m n
21
ïÅ‚ śł
C =
ai e" bj
" "
ïÅ‚ M M O M śł
i=1 j =1
ïÅ‚c cm2 L cmnśł
ðÅ‚ m1 ûÅ‚
1
Klasyczne zadanie transportowe  definicja (3)
Klasyfikacja zadań transportowych:
1. Zamknięte
m n
ai = bj
" "
i=1 j=1
2. Otwarte
m n
ai > bj
" "
i=1 j=1
Otwarte Ò! ZamkniÄ™te:
a) dodać n+1 punkt odbioru
b) zapotrzebowanie bn+1 dodanego punktu odbioru  ró\
nica między
całkowitą poda\
ą a całkowitym popytem:
m n
bn+1 = ai - "
bj
"
i=1 j=1
Klasyczne zadanie transportowe  model decyzyjny
Funkcja celu: (Å‚Ä…czny koszt transportu)
m n
F (x) = cijxij min
" "
i=1 j =1
Ograniczenia:
n
xij = ai i = 1,2,& ,m (bilanse dla punktów nadania)
"
i=1
m
xij = bj j = 1,2,& ,n (bilanse dla punktów odbioru)
"
i=1
Warunki brzegowe:
xij e" 0 i = 1,2,& ,m j = 1,2,& ,n
Klasyczne zadanie transportowe  przykład (1)
jednostkowe koszty transportu
poda\

dostawców
O1 O2 O3 O4
D1 2 2 3 5 140
D2 3 1 1 2 80
D3 2 4 4 4 130
zapotrzebowanie
50 110 70 120 350
odbiorców
2
Klasyczne zadanie transportowe  przykład (2)
F(Ç) =
Ç
Ç 2x11 +2x12 +3x13 +5x14 +3x21 +x22 +x23 +2x24 +2x31 +4x32 +4x33 +4x34
Ç
min
x11 +x12 +x13 +x14 = 140
+x21 +x22 +x23 +x24 = 80
+x31 +x32 +x33 +x34 = 130
x11 +x21 +x31 = 50
x12 +x22 +x32 = 110
x13 +x23 +x33 = 70
x14 +x24 +x34 = 120
x11e"0 x12e"0 x13e"0 x14e"0 x21e"0 x22e"0 x23e"0 x24e"0 x31e"0 x32e"0 x33e"0 x34e"0
Klasyczne zadanie transportowe  algorytm transportowy (1)
6
1 PoczÄ…tkowy Skoryguj program
program przewozowy przewozowy
5
Ustal maksymalny
przewóz na trasie
Program ustalonej w [3]
NIE
2
optymalny?
4
Zbuduj cykl
TAK korygujÄ…cy przewozy
KONIEC
3
Wybierz trasÄ™ dajÄ…cÄ…
największą obni\
kę kosztów
Klasyczne zadanie transportowe  algorytm transportowy (2)
PoczÄ…tkowy program przewozowy
Metoda kąta północno-zachodniego
1. wprowadz
maksymalny przewóz na trasie (i,j): xij = min(ai,bj)
2. skoryguj poda\
w i-tym punkcie nadania: ai = ai  xij i popyt w j-tym
punkcie odbioru: bi = bi  xij
3
popyt
poda
\

Klasyczne zadanie transportowe  algorytm transportowy (3)
Początkowy program przewozowy  Metoda kąta północno-zachodniego
O1 O2 O3 O4 poda\

D1 140
50 90 90 0
D2 20 60 80 60 0
D3 10 120 130 120 0
popyt 50 110 70 120 350
0 20 10 0
0 0
Koszt = 2× ×90 + 1× ×60 + 4× ×120 = 880
×50 + 2× ×20 + 1× ×10 + 4×
× × × × × ×
× × × × × ×
Klasyczne zadanie transportowe  algorytm transportowy (4)
Sprawdzenie optymalności programu przewozowego
Tabela wskaz
ników optymalności
1. pola tabeli wskaz
ników optymalności, dla których xij>0 zawierają jedną
liczbÄ™: jednostkowy koszt transportu cij
2. pozostałe pola tabeli wskaz
ników optymalności zawierają dwie liczby:
(ui+vj) oraz wskaz
nik optymalności "ij = cij (ui+vj)
3. program przewozowy jest optymalny, je\
eli wszystkie "ije"0
4. wyznaczenie trasy dającej największą obni\
kę kosztów (je\
eli uzyskany
program przewozowy nie jest optymalny):
dla wszystkich "ij<0 "kl = min{"ij}
Klasyczne zadanie transportowe  algorytm transportowy (5)
Sprawdzenie optymalności programu przewozowego
O1 O2 O3 O4 ui
2 2
D1 0
2 2
1 3
1 1
D2 1 1 -1
2 1
4 4
D3 4 4 2
-2 0
vj 2 2 2 2
×
×
×
×
4
Klasyczne zadanie transportowe  algorytm transportowy (6)
Korekta programu przewozowego
1. postaw znak  + na wytypowanej trasie dającej największą obni\
kÄ™
kosztów
2. w rozpatrywanym programie przewozowym znakuj trasy o przewozie
niezerowym znakami  + i  - w taki sposób, aby w ka\
dym wierszu i
ka\
dej kolumnie była para  +  - lub nie było ich w ogóle
3. wyznacz wielkość korekty ´ poprzez wybór wartoÅ›ci najmniejszej oznaczonej
´
´
´
znakiem  - : ´ = min(xij - )
´
´
´
4. skoryguj rozpatrywany program przewozowy poprzez:
xij* = xij + ´ dla tras oznaczonych znakiem  +
xij* = xij + ´ dla tras oznaczonych znakiem  -
xij* = xij dla tras nieoznaczonych
Klasyczne zadanie transportowe  algorytm transportowy (7)
Korekta programu przewozowego
O1 O2 O3 O4 poda\

D1 140
50 90
 -10 +10
+
D2 20 60 80
 -10 + +10
D3 10 120 130
+ +10  -10
popyt 50 110 70 120 350
min{50,20,10} = 10
Klasyczne zadanie transportowe  algorytm transportowy (8)
Poprawiony program przewozowy
O1 O2 O3 O4 poda\

D1 140
40 100
D2 10 70 80
D3 10 120 130
popyt 50 110 70 120 350
Koszt = 2× ×100 + 1× ×70 + 2× ×120 = 860
×40 + 2× ×10 + 1× ×10 + 4×
× × × × × ×
× × × × × ×
lub
Koszt = 880 + 10× 20 = 860
×( 2) = 880 
×
×
5
Klasyczne zadanie transportowe  algorytm transportowy (9)
Sprawdzenie optymalności programu przewozowego  iteracja 2
O1 O2 O3 O4 ui
2 4
D1 0
2 2
1 1
1 1
D2 1 1 -1
2 -1
2 2
D3 2 4 0
2 2
vj 2 2 2 4
×
×
×
×
Klasyczne zadanie transportowe  algorytm transportowy (10)
Korekta programu przewozowego
O1 O2 O3 O4 poda\

D1 140
40 100+10
 -10 +
D2 10 70 80
 -10 + +10
D3 10 120 130
+ +10  -10
popyt 50 110 70 120 350
min{40,10,120} = 10
Klasyczne zadanie transportowe  algorytm transportowy (11)
Poprawiony program przewozowy
O1 O2 O3 O4 poda\

D1 140
30 110
D2 70 10 80
D3 20 110 130
popyt 50 110 70 120 350
Koszt = 2× ×110 + 1× ×10 + 2× ×110 = 850
×30 + 2× ×70 + 2× ×20 + 4×
× × × × × ×
× × × × × ×
lub
Koszt = 860 + 10× 10 = 850
×( 1) = 860 
×
×
6
Klasyczne zadanie transportowe  algorytm transportowy (12)
Sprawdzenie optymalności programu przewozowego  iteracja 3
O1 O2 O3 O4 ui
3 4
D1 0
2 2
0 1
0 0
D2 1 2 -2
3 1
2 3
D3 2 4 0
2 1
vj 2 2 3 4
×
×
×
×
RozwiÄ…zanie optymalne
Klasyczne zadanie transportowe  zadanie otwarte
O1 O2 O3 O4 poda\

D1 2 2 3 5 140
400
D2 3 1 1 2 130
D3 2 4 4 4 130
popyt 50 110 70 120
350
O1 O2 O3 O4 M poda\

D1 2 2 3 5 0 140
D2 3 1 1 2 0 130
D3 2 4 4 4 0 130
popyt 50 110 70 120 50 400
Klasyczne zadanie transportowe  całkowita blokada trasy lub tras
O1 O2 O3 O4 poda\

D1 2 2 3 5 140
D2 3 1 1 2 80
D3 2 4 4 4 130
popyt 50 110 70 120 350
O1 O2 O3 O4 poda\

D1 2 2 3 5 140
T "
D2 3 1 T 2 80
D3 T 4 4 4 130
popyt 50 110 70 120 350
7
Klasyczne zadanie transportowe  częściowa blokada trasy
O1 O2 O3 O4 poda\

D1 2 2 3 5 140
D2 3 1 1 (max. 50) 2 80
D3 2 4 4 4 130
popyt 50 110 70 120 350
O1 O2 O3(a) O3(b) O4 poda\

D1 2 2 3 3 5 140
D2 3 1 1 T 2 80
D3 2 4 4 4 4 130
popyt 50 110 50 20 120 350
Zadanie transportowe  kryterium czasu I rodzaju
Funkcja celu: (Å‚Ä…czny czas transportu)
m n
tij
F (x) = tij xij min  czas transportu jednostki dobra
" "
i=1 j =1
Ograniczenia:
n
xij = ai i = 1,2,& ,m (bilanse dla punktów nadania)
"
i=1
m
xij = bj j = 1,2,& ,n (bilanse dla punktów odbioru)
"
i=1
Warunki brzegowe:
xij e" 0 i = 1,2,& ,m j = 1,2,& ,n
Zadanie transportowe  kryterium czasu II rodzaju
Funkcja celu: (najdłu\
szy czas przewozu w optymalnym programie
przewozowym jest najkrótszy spośród wszystkich
dopuszczalnych programów przewozowych  program
przewozu zakończy się najszybciej)
F(x) = min max{tij} tij  czas przejazdu pomiędzy punktem
x"X x >0
nadania i a punktem odbioru j
ij
Ograniczenia:
n
xij = ai i = 1,2,& ,m (bilanse dla punktów nadania)
"
i=1
m
xij = bj j = 1,2,& ,n (bilanse dla punktów odbioru)
"
i=1
Warunki brzegowe:
xij e" 0 i = 1,2,& ,m j = 1,2,& ,n
8
Zagadnienie przydziału
Zadanie przydziału  definicja (1)
Zadanie optymalnego przydziału  problem najkorzystniejszego
skojarzenia n środków z m celami, przy czym ka\
dy środek mo\
e być
u\
yty tylko jeden raz.
Zało\
enia klasycznego zadania transportowego:
n - liczba środków
m - liczba celów
xij - zmienne decyzyjne; xij =1 je\
eli i-ty cel jest realizowany przez
j-ty środek; xij =0 je\
eli i-ty cel nie jest realizowany przez
j-ty środek; [i=1,2,& ,m; j=1,2,& ,n;]
cij - parametr problemu; korzyść związana z realizacją i-tego celu
przez j-ty środek [i=1,2,& ,m; j=1,2,& ,n;]
Zadanie przydziału  model decyzyjny (n = m)
Liczba celów = liczba środków = n
Funkcja celu: (łączna korzyść)
n n
U (x) = cijxij max (min)
" "
i=1 j=1
Ograniczenia:
n
xij =1 i = 1,2,& ,n (bilanse dla celów)
"
i=1
n
xij =1 j = 1,2,& ,n (bilanse dla środków)
"
i=1
Warunki brzegowe:
xij "{0,1} i = 1,2,& ,n j = 1,2,& ,n
9
Zadanie przydziału  model decyzyjny (n > m)
Nadwy\
ka środków nad celami
Funkcja celu: (łączna korzyść)
m n
U (x) = cijxij max (min)
" "
i=1 j=1
Ograniczenia:
n
xij =1 i = 1,2,& ,m (bilanse dla celów)
"
i=1
m
xij d" 1 j = 1,2,& ,n (bilanse dla środków)
"
i=1
Warunki brzegowe:
xij "{0,1} i = 1,2,& ,m j = 1,2,& ,n
Zadanie przydziału  model decyzyjny (n < m)
Nadwy\
ka celów nad środkami
Funkcja celu: (łączna korzyść)
m n
U (x) = cijxij max (min)
" "
i=1 j=1
Ograniczenia:
n
xij d" 1 i = 1,2,& ,m (bilanse dla celów)
"
i=1
m
xij =1 j = 1,2,& ,n (bilanse dla środków)
"
i=1
Warunki brzegowe:
xij "{0,1} i = 1,2,& ,m j = 1,2,& ,n
Zadanie przydziału  przykład
Kooperant (środki)
I II III IV V VI VII VIII
A 10 8 8 12 6 8 10 12
B 12 15 6 12 15 9 12 9
C 10 10 9 9 8 8 9 9
D 15 14 12 15 13 13 15 15
E 16 12 14 16 10 10 16 20
F 10 8 10 11 7 7 12 12
U min
I II III IV V VI VII VIII
A 0 0 0 0 1 0 0 0
B 0 0 1 0 0 0 0 0
C 0 0 0 0 0 0 1 0
D 0 0 0 0 0 0 0 1
E 0 0 0 0 0 1 0 0
Umin = 54
F 0 1 0 0 0 0 0 0
10
Układ (cele)