Zagadnienie transportowe
Gliwice
1
Zadanie zbilansowane
Gliwice
2
Zadanie zbilansowane
Przykład 10
Firma posiada zakłady wytwórcze w miastach A, B i C, oraz
centra dystrybucyjne w miastach D, E, F i G.
Możliwości produkcyjne zakładów wynoszą odpowiednio: 120, 20
i 60 jednostek, natomiast zapotrzebowanie w poszczególnych
centrach dystrybucyjnych odpowiednio: 80, 30, 40 i 50
jednostek.
Jednostkowe koszty transportu przedstawione są w tabeli.
Określić taki plan przewozów, aby koszty dostaw z zakładów
wytwórczych do centrów dystrybucyjnych były minimalne.
Gliwice
3
Zadanie zbilansowane
Tabela kosztów jednostkowych:
A
5382
B
4642
C
923 11
dostawcy
DEFG
odbiorcy
Gliwice
4
Model matematyczny
Gliwice
5
Model matematyczny
Produkcja zakładów (PODAŻ):
Zapotrzebowanie w centrach dystrybucyjnych (POPYT):
Produkcja = Zapotrzebowanie lub PODAŻ = POPYT
Zadanie jest zbilansowane
Gliwice
6
Model matematyczny
mn
"a = "b
ij
i=1 j=1
gdzie:
ai  zasoby i  tego dostawcy
bj  zapotrzebowanie j  tego odbiorcy
m  ilość dostawców
n  ilość odbiorców
cij  koszt transportu od i  tego dostawcy do j  tego odbiorcy
Gliwice
7
Model matematyczny
Zmienne decyzyjne:
xij  ilość towaru przewożonego od i  tego dostawcy do
j  tego odbiorcy
i =1...m j =1...n
m = 3 n = 4
np.:
x24  ilość towaru przewożonego od drugiego dostawcy
(miasto B) do czwartego odbiorcy (miasto G)
Gliwice
8
Model matematyczny
Funkcja celu:
Z x11, x12, x13, x14, x21, x22, x23, x24, x31, x32, x33, x34 =
()
m n
Z xij =
( )
""c xij MIN
ij
i=1 j=1
Gliwice
9
Model matematyczny
Ograniczenia:
DOSTAWCY:
A :
B :
C :
Gliwice
10
Model matematyczny
Ograniczenia c.d.:
ODBIORCY:
D :
E :
F :
G :
Gliwice
11
Model matematyczny
Warunki brzegowe:
xij e" 0, i =1...m, j =1...n
Gliwice
12
Pierwsze rozwiązanie
dopuszczalne
Gliwice
13
Metoda kąta
północno  zachodniego
Gliwice
14
Pierwsze rozwiązanie dopuszczalne  metoda kąta PZ
(1, 1) (1, 2) (1, 3) (1, 4)
(2, 1) (2, 2) (2, 3) (2, 4)
(3, 1) (3, 2) (3, 3) (3, 4)
(1, 1)& (3, 4)  węzły
Gliwice
15
Pierwsze rozwiązanie dopuszczalne  metoda kąta PZ
Ilość węzłów bazowych
W przykładzie:
Gliwice
16
Pierwsze rozwiązanie dopuszczalne  metoda kąta PZ
Tablica przewozów
120
20
60
80 30 40 50
Gliwice
17
Pierwsze rozwiązanie dopuszczalne  metoda kąta PZ
Pierwsze rozwiązanie dopuszczalne
x11 = x12 = x13 = x14 =
x21 = x22 = x23 = x24 =
x31 = x32 = x33 = x34 =
FC: Z xij =
( )
Gliwice
18
Pierwsze rozwiązanie dopuszczalne  metoda kąta PZ
Sprawdzenie optymalności rozwiązania
Gliwice
19
Pierwsze rozwiązanie dopuszczalne  metoda kąta PZ
Wskaz
niki optymalności
Dla węzłów bazowych
Gliwice
20
Pierwsze rozwiązanie dopuszczalne  metoda kąta PZ
Wskaz
niki optymalności
Gliwice
21
Pierwsze rozwiązanie dopuszczalne  metoda kąta PZ
Gliwice
22
Pierwsze rozwiązanie dopuszczalne  metoda kąta PZ
Wskaz
niki optymalności dla węzłów niebazowych
Gliwice
23
Pierwsze rozwiązanie dopuszczalne  metoda kąta PZ
Tablica wskaz
ników optymalności
Gliwice
24
Pierwsze rozwiązanie dopuszczalne  metoda kąta PZ
Kryterium optymalności
Rozwiązanie jest optymalne, jeżeli wartości wszystkich
wskaz
ników optymalności są nieujemne.
Gliwice
25
Kolejne rozwiązania
Gliwice
26
Kolejne rozwiązania
wymiana jednego
Nowe rozwiązanie
węzła w bazie
Kryterium wejścia
Do bazy wprowadzany jest węzeł, dla którego wskaz
nik
optymalności ma wartość najmniejszą.
Gliwice
27
Kolejne rozwiązania
Określenie węzła usuwanego z bazy
Budowa tzw. cyklu
 Definicja cyklu
W każdym wierszu bądz
kolumnie do cyklu wchodzą dwa lub
zero węzłów.
Cykl składa się z półcyklu dodatniego i ujemnego.
Gliwice
28
Kolejne rozwiązania
Tablica przewozów
Gliwice
29
Kolejne rozwiązania
Określamy minimum w półcyklu ujemnym:
Kryterium wyjścia
Z bazy usuwany jest węzeł z półcyklu ujemnego, dla którego
wartość przewozu jest najmniejsza.
Gliwice
30
Kolejne rozwiązania
Tablica przewozów  nowe rozwiązanie
Gliwice
31
Kolejne rozwiązania
Tablica wskaz
ników optymalności z poprzedniego kroku
Dla węzłów bazowych:
Gliwice
32
Kolejne rozwiązania
Gliwice
33
Kolejne rozwiązania
Nowe wskaz
niki optymalności
Gliwice
34
Kolejne rozwiązania
Nowe wskaz
niki optymalności
Przykładowo:
Gliwice
35
Kolejne rozwiązania
Tablica przewozów
Gliwice
36
Kolejne rozwiązania
Tablica przewozów  nowe rozwiązanie
FC: Z xij =
( )
Gliwice
37
Kolejne rozwiązania
Tablica wskaz
ników optymalności z poprzedniego kroku
Dla węzłów bazowych:
Gliwice
38
Kolejne rozwiązania
Gliwice
39
Kolejne rozwiązania
Nowe wskaz
niki optymalności
Gliwice
40
Kolejne rozwiązania
Tablica przewozów
Gliwice
41
Kolejne rozwiązania
Tablica przewozów  nowe rozwiązanie
FC: Z xij =
( )
Gliwice
42
Kolejne rozwiązania
Tablica wskaz
ników optymalności z poprzedniego kroku
Dla węzłów bazowych:
Gliwice
43
Kolejne rozwiązania
Gliwice
44
Kolejne rozwiązania
Nowe wskaz
niki optymalności
Gliwice
45
Kolejne rozwiązania
Rozwiązanie optymalne
x11 = x12 = x13 = x14 =
x21 = x22 = x23 = x24 =
x31 = x32 = x33 = x34 =
FC: Z xij =
( )
Gliwice
46