Badania operacyjne
dr inż. W. Zalewski
23
ZAGADNIENIE TRANSPORTOWE
Model ogólny zwykłego (klasycznego) zadania transportowego
Danych
jest
m dostawców pewnego jednorodnego produktu. Zasoby
tego produktu znajdujące się u i-tego dostawcy wynoszą a
i
(i = 1, 2, ..., m).
Produkt jest przeznaczony dla n odbiorców, których zapotrzebowanie
wynosi odpowiednio b
j
(j = 1, 2, ..., n). Koszt transportu jednostki
produktu od i-tego dostawcy do j-tego odbiorcy wynosi c
ij
(i = 1, 2, ..., m;
j = 1, 2, ..., n). Należy określić plan przewozów pomiędzy dostawcami
a odbiorcami tak, aby po uwzględnieniu dostępnych zasobów towaru
u dostawców i wymaganego zapotrzebowania odbiorców łączne koszty
transportu były minimalne.
Model matematyczny zadania
Funkcja
celu:
( )
min
x
c
x
f
m
1
i
n
1
j
ij
ij
ij
→
=
∑∑
=
=
przy warunkach ograniczających:
(1)
m
,
,
2
,
1
i
a
x
n
1
j
i
ij
!
=
≤
∑
=
(2)
n
,
,
2
,
1
j
b
x
m
1
i
j
ij
!
=
=
∑
=
(3)
n
,
,
2
,
1
j
;
m
,
,
2
,
1
i
0
x
ij
!
!
=
=
≥
Warunek (1) nosi nazwę warunku bilansującego dostawców.
Warunek (2) nosi nazwę warunku bilansującego odbiorców.
Badania operacyjne
dr inż. W. Zalewski
24
Własności zadania transportowego
Jeżeli
∑
∑
=
=
=
m
1
j
j
n
1
i
i
b
a
to zadanie nazywamy zbilansowanym lub
zamkniętym zadaniem transportowym.
Zbilansowanie zadania niezbilansowanego polega na:
Jeśli
∑
∑
=
=
>
m
1
j
j
n
1
i
i
b
a
wprowadza się fikcyjnego odbiorcę z zapotrzebowaniem wynoszącym
∑
∑
=
=
−
=
m
1
j
j
n
1
i
i
0
b
a
b
oraz przyjmuje się c
i0
= 0. Dostawy do fikcyjnego odbiorcy należy
traktować jako niewykorzystanie zasobów produktu u poszczególnych
dostawców. Formalnie operacja ta oznacza wprowadzenie zmiennych
dodatkowych do warunku (1).
Jeśli
∑
∑
=
=
<
m
1
j
j
n
1
i
i
b
a
wprowadza się fikcyjnego dostawcę z zasobem produktu wynoszącym
∑
∑
=
=
−
=
n
1
i
i
m
1
j
j
0
a
b
a
oraz przyjmuje się c
0j
= 0. Dostawy do fikcyjnego dostawcy reprezentują
niezaspokojone zapotrzebowanie odbiorców.
HACKED BY VIPER :)
Badania operacyjne
dr inż. W. Zalewski
25
Twierdzenia dotyczące zadania transportowego
T1. W każdym zbilansowanym zadaniu transportowym zbiór rozwiązań
dopuszczalnych jest niepusty i ograniczony.
Z powyższego wynika, że każde zbilansowane zadanie transportowe
posiada skończone rozwiązanie optymalne.
T2. Rząd macierzy A warunków ograniczających zadania
transportowego jest równy m + n –1.
Z powyższego wynika, że w rozwiązaniu optymalnym zadania
transportowego co najwyżej m + n –1 zmiennych jest niezerowych.
T3. Jeżeli wszystkie a
i
i b
j
w zadaniu transportowym są liczbami
całkowitymi, to każde rozwiązanie bazowe (również optymalne) jest
utworzone z liczb całkowitych.
T4. Rozwiązanie dopuszczalne zadania transportowego jest
rozwiązaniem bazowym wtedy i tylko wtedy, gdy odpowiadający mu
graf jest grafem spójnym i bez cykli.
T5. Na to aby graf rozwiązania zadania transportowego był grafem
spójnym i bez cykli potrzeba i wystarcza, żeby zawierał dokładnie
m + n –1 wierzchołków.
Badania operacyjne
dr inż. W. Zalewski
26
Metody wyznaczania rozwiązań wstępnych
Metoda kąta północno-zachodniego
j
i
1 2 ...
m
a
i
1
2
...
n
x
11
x
12
... x
1m
x
21
x
22
...
x
2m
... ... ... ...
x
11
x
11
...
x
11
a
1
a
2
...
a
n
b
j
b
1
b
2
... b
m
{
}
1
1
11
b
,
a
min
x
=
{
}
1
p
j
1
p
i
ij
b
,
a
min
x
−
−
=
gdzie
ij
1
p
i
p
i
x
a
a
−
=
−
ij
1
p
j
p
j
x
b
b
−
=
−
,
ponadto:
i
0
i
a
a
=
j
0
j
b
b
=
Metoda minimalnego elementu macierzy kosztów
Reguła wyboru numeru (k,l) zmiennej x
kl
na zmienna bazową:
( )
{
}
J
I
×
∈
=
j
,i
:
c
min
c
ij
kl
gdzie I – zbiór numerów dostawców,
J – zbiór numerów odbiorców.
HACKED BY VIPER :)
Badania operacyjne
dr inż. W. Zalewski
27
Problemy sprowadzalne do zagadnienia transportowego
Zadanie transportowo-produkcyjne i transportowo -magazynowe
Danych
jest
n producentów pewnego jednorodnego produktu P
1
,
P
2
, ..., P
n
. Każdy z nich ma określone zdolności produkcyjne a
1
, a
2
, ..., a
n
.
Odbiorcy, których jest m zgłaszają odpowiednio zapotrzebowanie b
1
,
b
2
, ..., b
m
takie, że
∑
∑
=
=
≥
m
1
j
j
n
1
i
i
b
a
Znane
są ponadto jednostkowe koszty produkcji określone dla
poszczególnych producentów p
1
, p
2
, ..., p
n
oraz tablica jednostkowych
kosztów transportu [c
ij
].
Należy wyznaczyć taki plan transportu i produkcji (transportu
i wykorzystania mocy produkcyjnych poszczególnych producentów) aby
łączny koszt był minimalny.
Powyższe zadanie transportowo-produkcyjne można sprowadzić do
zadania transportowego przez:
1)
wprowadzenie fikcyjnego odbiorcy O
m+1
, który będzie
reprezentować nie wykorzystane moce produkcyjne poszczególnych
producentów i dla którego zapotrzebowanie określamy jako:
∑
∑
=
=
+
−
=
m
1
j
j
n
1
i
i
1
m
b
a
b
2)
skonstruowanie macierzy kosztów transportu i produkcji
w następujący sposób:
c
*
i m+1
= 0
c
*
ij
= c
ij
+ p
i
,
dla j = 1, 2, ..., m oraz i = 1, 2, ..., n.
Badania operacyjne
dr inż. W. Zalewski
28
Uogólnione zadanie transportowe
Niech
będzie dana sieć G = <S, U>, gdzie S jest zbiorem węzłów
sieci, a U zbiorem połączeń między węzłami. W zbiorze S węzłów sieci
wyróżniamy dwa rozłączne podzbiory: D – zbiór dostawców i O – zbiór
odbiorców: D
⊂
S, O
⊂
S i D
∩
O =
∅
.
Dla
każdego z s
i
∈
D określone są wielkości a
i
, które będziemy
interpretować jako wielkość podaży, dla s
i
∈
O – wielkości b
j
,
odzwierciedlające popyt w punkcie S
j
, dla s
k
∈
S – {D
∪
O} – wielkości
p
k
, oznaczające przepustowość. Zbiór P = S – {D
∪
O} jest zbiorem
punktów pośrednich.
Na zbiorze S określona jest pewna relacja R opisująca możliwe
połączenia między punktami, a każde z połączeń scharakteryzowane jest
przez pewną nieujemną liczbę k
ij
oznaczającą przepustowość połączenia.
Relację R można opisać za pomocą funkcji wielowartościowych:
Γ
+
(s
i
) = {s
j
: (s
i
,s
j
)
∈
U} – zbiór poprzedników węzła s
i
,
Γ
-
(s
i
) = {s
k
: (s
k
,s
i
)
∈
U} – zbiór następników węzła s
i
,
Niech
c
ij
oznacza koszt (odległość, czas) przewozu jednostki towaru
z punktu s
i
do s
j
.
Zadanie polega na wyznaczeniu takiego planu przewozu towaru
z punktów należących do zbioru O do punktów ze zbioru D, aby
zaspakajając zapotrzebowanie odbiorców nie przekroczyć możliwości
dostawców, przepustowości połączeń oraz przepustowości punktów
pośrednich a jednocześnie spełnić określone kryterium optymalności
rozwiązania problemu.
HACKED BY VIPER :)
Badania operacyjne
dr inż. W. Zalewski
29
Jeżeli przez x
ij
oznaczymy wielkość przewozu towarów z punktu s
i
do s
j
, to dopuszczalne wartości x
ij
muszą spełniać warunki:
! dopuszczalnej przepustowości połączeń
0
≤
x
ij
≤
k
ij
(1)
! ilości towaru wwiezionego i wywiezionego z węzła
( )
( )
{
}
O
D
S
s
dla
x
x
i
s
s
ij
s
s
ki
i
j
i
k
∪
−
∈
=
∑
∑
+
−
Γ
∈
Γ
∈
(2)
! dopuszczalnej przepustowości węzłów
( )
{
}
O
D
S
s
dla
p
x
i
s
s
i
ki
i
k
∪
−
∈
≤
∑
−
Γ
∈
(3)
! nieprzekroczenia podaży poszczególnych dostawców
( )
D
s
dla
a
x
i
s
s
i
ik
i
k
∈
≤
∑
+
Γ
∈
(4)
! zaspokojenia zapotrzebowania poszczególnych odbiorców
( )
O
s
dla
b
x
j
s
s
j
kj
k
k
∈
=
∑
+
Γ
∈
(5)
Dopuszczalne plany przewozów można ocenić za pomocą
następujących przykładowych kryteriów:
( )
min
c
x
U
s
,
s
ij
ij
j
i
→
∑
∈
( )
min
c
max
r
j
i
L
s
,
s
ij
→
∑
∈
HACKED BY VIPER :)