ZAGADNIENIE
TRANSPORTOWE
(część 1)
Zadanie zbilansowane
3
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.
4
Zadanie zbilansowane
G
F
E
D
C
11
3
2
9
B
2
4
6
4
A
2
8
3
5
Tabela kosztów jednostkowych:
dostawcy
odbiorcy
Model matematyczny
6
Model matematyczny
Produkcja zakładów (podaż):
120 20 60
+
+
200
=
Zapotrzebowanie w centrach dystrybucyjnych (popyt):
80 30 40 50
+
+
+
200
=
Produkcja = Zapotrzebowanie
lub
Podaż = Popyt
Zadanie jest zbilansowane
7
Model matematyczny
1
1
m
n
i
j
i
j
a
b
=
=
=
∑ ∑
gdzie:
a
i
– zasoby
i
– tego dostawcy
b
j
– zapotrzebowanie
j
– tego odbiorcy
m
– ilość dostawców
n
– ilość odbiorców
c
ij
– koszt transportu od
i
– tego dostawcy do
j
– tego odbiorcy
8
Model matematyczny
Zmienne decyzyjne
x
ij
– ilość towaru przewożonego od
i
– tego dostawcy do
j
– tego odbiorcy
i = 1...m
j = 1...n
m = 3 n = 4
np.
x
24
– ilość towaru przewożonego od drugiego dostawcy
(miasto
B
) do czwartego odbiorcy (miasto
G
).
9
Model matematyczny
Funkcja celu
11
12
13
14
21
22
23
24
31
32
33
34
Z( ,
,
,
,
,
,
,
,
,
,
,
)
x x x x x x x x x x x x
=
11
12
13
14
5
3
8
2
x
x
x
x
=
+
+
+
+
21
22
23
24
4
6
4
2
x
x
x
x
+
+
+
+
+
31
32
33
34
9
2
3
11
x
x
x
x
+
+
+
+
MIN
→
1
1
Z( )
MIN
m
n
ij
ij ij
i
j
x
c x
=
=
=
→
∑∑
10
Model matematyczny
Ograniczenia
Dostawcy:
11
12
13
14
:
120
x
x
x
x
+
+
+
=
A
21
22
23
24
:
20
x
x
x
x
+
+
+
=
B
31
32
33
34
:
60
x
x
x
x
+
+
+
=
C
1
1...
n
ij
i
j
x
a
i
m
=
=
=
∑
11
Model matematyczny
Ograniczenia c. d.
Odbiorcy:
11
21
31
:
80
x
x
x
+
+
=
D
12
22
32
:
30
x
x
x
+
+
=
E
13
23
33
:
40
x
x
x
+
+
=
F
14
24
34
:
50
x
x
x
+
+
=
G
1
1...
m
ij
j
i
x
b
j
n
=
=
=
∑
12
Model matematyczny
Warunki brzegowe
0
1...
1...
ij
x
i
m
j
n
≥
=
=
Pierwsze rozwiązanie
dopuszczalne
Metoda kąta
północno - zachodniego
15
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
(3,4)
(3,3)
(3,2)
(3,1)
(2,4)
(2,3)
(2,2)
(2,1)
(1,4)
(1,3)
(1,2)
(1,1)
(1,1)...(3,4)
- węzły
16
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Ilość węzłów bazowych:
1
m n
+ −
W przykładzie:
3 4 1 6
+ − =
17
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Tablica przewozów:
120
20
60
80
30
40
50
min(120,80)
80
=
80
18
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Tablica przewozów:
120
20
60
80
30
40
50
80
40
0
0
0
19
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Tablica przewozów:
120
20
60
80
30
40
50
80
40
0
0
0
min(40,30)
30
=
30
20
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Tablica przewozów:
120
20
60
80
30
40
50
80
40
0
0
0
30
10
0
0
0
21
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Tablica przewozów:
120
20
60
80
30
40
50
80
40
0
0
0
30
10
0
0
0
min(10,40)
10
=
10
22
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Tablica przewozów:
120
20
60
80
30
40
50
80
40
0
0
0
30
10
0
0
0
10
0
30
0
23
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Tablica przewozów:
120
20
60
80
30
40
50
80
40
0
0
0
30
10
0
0
0
10
0
30
0
min(20,30)
20
=
20
24
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Tablica przewozów:
120
20
60
80
30
40
50
80
40
0
0
0
30
10
0
0
0
10
0
30
0
20
0
10
0
25
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Tablica przewozów:
120
20
60
80
30
40
50
80
40
0
0
0
30
10
0
0
0
10
0
30
0
20
0
10
0
min(60,10)
10
=
10
26
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Tablica przewozów:
120
20
60
80
30
40
50
80
40
0
0
0
30
10
0
0
0
10
0
30
0
20
0
10
0
10
50
0
27
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Tablica przewozów:
120
20
60
80
30
40
50
80
40
0
0
0
30
10
0
0
0
10
0
30
0
20
0
10
0
10
50
min(50,50)
50
=
50
0
28
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Tablica przewozów:
120
20
60
80
30
40
50
80
40
0
0
0
30
10
0
0
0
10
0
30
0
20
0
10
0
10
50
50
0
0
0
29
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
80
0
0
30
0
0
10
0
20
0
10
50
*
*
*
*
*
*
*
- węzły bazowe
Pierwsze rozwiązanie dopuszczalne:
11
12
13
14
21
22
23
24
31
32
33
34
80
30
10
0
0
0
20
0
0
0
10
50
x
x
x
x
x
x
x
x
x
x
x
x
=
=
=
=
=
=
=
=
=
=
=
=
FC : Z( ) 1230
ij
x
=
30
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Sprawdzenie optymalności rozwiązania
1
u
2
u
3
u
1
v
2
v
3
v
4
v
u
i
– zmienne związane z dostawcami
v
j
– zmienne związane z odbiorcami
31
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
ij
i
j
ij
e
u
v
c
= + +
Wskaźniki optymalności:
Dla węzłów bazowych:
0
ij
e
=
32
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
(1,1)
1
1
5 0
u
v
+ + =
(1,2)
1
2
3 0
u
v
+ + =
(1,3)
1
3
8 0
u
v
+ + =
(2,3)
2
3
4 0
u
v
+ + =
(3,3)
3
3
3 0
u
v
+ + =
(3,4)
3
4
11 0
u
v
+ + =
33
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Układ 6 równań z 7 niewiadomymi.
Układ ma nieskończenie wiele rozwiązań.
Aby go rozwiązać za jedną zmienną przyjmuje się dowolną
wartość.
34
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Przyjmujemy
u
1
= 0
z :
z :
z :
z :
z :
z :
1
5
v
= −
2
3
v
= −
3
8
v
= −
2
3
4
4
u
v
= − − =
3
3
3
5
u
v
= − − =
4
3
11
16
v
u
= − − = −
35
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Wskaźniki optymalności dla węzłów niebazowych:
(1,4)
14
1
4
14
14
e
u
v
c
= + +
= −
(2,1)
21
2
1
21
3
e
u
v
c
= + +
=
(2,2)
22
2
2
22
7
e
u
v
c
= + +
=
(2,4)
24
2
4
24
10
e
u
v
c
= + +
= −
(3,1)
31
3
1
31
9
e
u
v
c
= + +
=
(3,2)
32
3
2
32
4
e
u
v
c
= + +
=
36
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
0
0
4
9
-10
0
7
3
-14
0
0
0
*
*
*
*
*
*
Tablica wskaźników optymalności
37
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Kryterium optymalności
Rozwiązanie jest optymalne, jeżeli wartości wszystkich
wskaźników optymalności są nieujemne
Rozwiązanie nie jest optymalne
Kolejne rozwiązania
39
Kolejne rozwiązania
Nowe rozwiązanie
wymiana jednego węzła w bazie
Kryterium wejścia
Do bazy wprowadzany jest węzeł, dla którego wskaźnik
optymalności ma wartość najmniejszą.
W przykładzie:
(1,4)
40
Kolejne rozwiązania
Określenie węzła usuwanego z bazy
Budowa tzw. cyklu
„Definicja cyklu”
W każdym wierszu i kolumnie do cyklu wchodzą dwa lub zero
węzłów.
Cykl składa się z półcyklu dodatniego i ujemnego.
41
Kolejne rozwiązania
80
0
0
30
0
0
10
0
20
0
10
50
*
*
*
*
*
*
Tablica przewozów
+
(1,4)
węzeł
wprowadzany
do bazy
Węzeł wprowadzany do bazy – półcykl dodatni
42
Kolejne rozwiązania
80
0
0
30
0
0
10
0
20
0
10
50
*
*
*
*
*
*
Tablica przewozów
+
–
(3,4)
drugi węzeł w czwartej kolumnie – półcykl ujemny
43
Kolejne rozwiązania
80
0
0
30
0
0
10
0
20
0
10
50
*
*
*
*
*
*
Tablica przewozów
+
–
(3,3)
drugi węzeł w trzecim wierszu – półcykl dodatni
+
44
Kolejne rozwiązania
80
0
0
30
0
0
10
0
20
0
10
50
*
*
*
*
*
*
Tablica przewozów
+
–
–
(1,3)
drugi węzeł w trzeciej kolumnie – półcykl ujemny
+
45
Kolejne rozwiązania
80
0
0
30
0
0
10
0
20
0
10
50
*
*
*
*
*
*
Tablica przewozów
+
–
–
Cykl składający się z czterech węzłów
+
46
Kolejne rozwiązania
Określamy minimum w półcyklu ujemnym:
min(10,50) 10
=
Minimum odpowiada węzłowi
(1,3)
Kryterium wyjścia
Z bazy usuwany jest węzeł z półcyklu ujemnego, dla którego
wartość przewozu jest najmniejsza.
47
Kolejne rozwiązania
10
*
Tablica przewozów – nowe rozwiązanie
48
Kolejne rozwiązania
10
*
Tablica przewozów – nowe rozwiązanie
0
49
Kolejne rozwiązania
10
*
Tablica przewozów – nowe rozwiązanie
0
40
*
50
Kolejne rozwiązania
10
*
Tablica przewozów – nowe rozwiązanie
0
40
*
20
*
51
Kolejne rozwiązania
10
*
Tablica przewozów – nowe rozwiązanie
0
40
*
20
*
80
0
0
30
0
0
20
0
*
*
*
FC : Z( ) 1090
ij
x
=
52
Kolejne rozwiązania
0
0
4
9
-10
0
7
3
-14
0
0
0
*
*
*
*
*
*
Tablica wskaźników optymalności z poprzedniego kroku
(1,1)
1
1
0 0
u
v
+ + =
Dla węzłów bazowych:
(1,2)
1
2
0 0
u
v
+ + =
(1,4)
1
4
14 0
u
v
+ − =
(2,3)
2
3
0 0
u
v
+ + =
(3,3)
3
3
0 0
u
v
+ + =
(3,4)
3
4
0 0
u
v
+ + =
53
Kolejne rozwiązania
Przyjmujemy
u
1
= 0
1
0
v
=
2
0
v
=
3
14
v
=
2
14
u
= −
3
14
u
= −
4
14
v
=
Otrzymujemy:
54
Kolejne rozwiązania
Nowe wskaźniki optymalności:
ij
i
j
ij
e
u
v
e
′ = + +
e
ij
– wskaźniki optymalności z poprzedniego kroku
55
Kolejne rozwiązania
0
0
-10
-5
-10
0
-7
-11
0
14
0
0
*
*
*
*
*
*
Nowe wskaźniki optymalności
Rozwiązanie nie jest optymalne
56
Kolejne rozwiązania
10
*
Tablica przewozów
0
40
*
20
*
80
0
0
30
0
0
20
0
*
*
*
Węzeł wprowadzany do bazy:
(2,1)
+
57
Kolejne rozwiązania
10
*
Tablica przewozów
0
40
*
20
*
80
0
0
30
0
0
20
0
*
*
*
(1,1)
drugi węzeł w pierwszej kolumnie – półcykl ujemny
+
–
58
Kolejne rozwiązania
10
*
Tablica przewozów
0
40
*
20
*
80
0
0
30
0
0
20
0
*
*
*
(1,4)
drugi węzeł w pierwszym wierszu – półcykl dodatni
+
–
+
59
Kolejne rozwiązania
10
*
Tablica przewozów
0
40
*
20
*
80
0
0
30
0
0
20
0
*
*
*
(3,4)
drugi węzeł w czwartej kolumnie – półcykl ujemny
+
–
+
–
60
Kolejne rozwiązania
10
*
Tablica przewozów
0
40
*
20
*
80
0
0
30
0
0
20
0
*
*
*
(3,3)
drugi węzeł w trzecim wierszu – półcykl dodatni
+
–
+
–
+
61
Kolejne rozwiązania
10
*
Tablica przewozów
0
40
*
20
*
80
0
0
30
0
0
20
0
*
*
*
(2,3)
drugi węzeł w drugim wierszu – półcykl ujemny
+
–
+
–
+
–
62
Kolejne rozwiązania
10
*
Tablica przewozów
0
40
*
20
*
80
0
0
30
0
0
20
0
*
*
*
Cykl składający się z sześciu węzłów
+
–
+
–
+
–
min(80,20,40) 20
=
(2,3)
usuwany z bazy
63
Kolejne rozwiązania
30
*
Tablica przewozów – nowe rozwiązanie
0
20
*
40
*
60
20
0
30
0
0
0
0
*
*
*
FC : Z( ) 870
ij
x
=
64
Kolejne rozwiązania
0
0
-10
-5
-10
0
-7
-11
0
14
0
0
*
*
*
*
*
*
Tablica wskaźników optymalności z poprzedniego kroku
(1,1)
1
1
0 0
u
v
+ + =
Dla węzłów bazowych:
(1,2)
1
2
0 0
u
v
+ + =
(1,4)
1
4
0 0
u
v
+ + =
(2,1)
2
1
11 0
u
v
+ − =
(3,3)
3
3
0 0
u
v
+ + =
(3,4)
3
4
0 0
u
v
+ + =
65
Kolejne rozwiązania
Przyjmujemy
u
1
= 0
1
0
v
=
2
0
v
=
3
0
v
=
2
11
u
=
3
0
u
=
4
0
v
=
Otrzymujemy:
66
Kolejne rozwiązania
0
0
-10
-5
1
11
4
0
0
14
0
0
*
*
*
*
*
*
Nowe wskaźniki optymalności
Rozwiązanie nie jest optymalne
67
Kolejne rozwiązania
30
*
Tablica przewozów
0
20
*
40
*
60
20
0
30
0
0
0
0
*
*
*
Węzeł wprowadzany do bazy:
(3,2)
+
68
Kolejne rozwiązania
30
*
Tablica przewozów
0
20
*
40
*
60
20
0
30
0
0
0
0
*
*
*
–
+
(1,2)
drugi węzeł w drugiej kolumnie – półcykl ujemny
69
Kolejne rozwiązania
30
*
Tablica przewozów
0
20
*
40
*
60
20
0
30
0
0
0
0
*
*
*
–
+
(1,4)
drugi węzeł w pierwszym wierszu – półcykl dodatni
+
70
Kolejne rozwiązania
30
*
Tablica przewozów
0
20
*
40
*
60
20
0
30
0
0
0
0
*
*
*
–
+
(3,4)
drugi węzeł w czwartej kolumnie – półcykl ujemny
–
+
71
Kolejne rozwiązania
30
*
Tablica przewozów
0
20
*
40
*
60
20
0
30
0
0
0
0
*
*
*
–
+
Cykl składający się z czterech węzłów
–
+
min(30,20) 20
=
(3,4)
usuwany z bazy
72
Kolejne rozwiązania
50
*
Tablica przewozów – nowe rozwiązanie
0
0
*
40
*
60
20
0
10
0
20
0
0
*
*
*
FC : Z( ) 670
ij
x
=
73
Kolejne rozwiązania
0
0
-10
-5
1
11
4
0
0
14
0
0
*
*
*
*
*
*
Tablica wskaźników optymalności z poprzedniego kroku
(1,1)
1
1
0 0
u
v
+ + =
Dla węzłów bazowych:
(1,2)
1
2
0 0
u
v
+ + =
(1,4)
1
4
0 0
u
v
+ + =
(2,1)
2
1
0 0
u
v
+ + =
(3,2)
3
2
10 0
u
v
+ − =
(3,3)
3
3
0 0
u
v
+ + =
74
Kolejne rozwiązania
Przyjmujemy
u
1
= 0
1
0
v
=
2
0
v
=
3
10
v
= −
2
0
u
=
3
10
u
=
4
0
v
=
Otrzymujemy:
75
Kolejne rozwiązania
10
0
0
5
1
1
4
0
0
4
0
0
*
*
*
*
*
*
Nowe wskaźniki optymalności
Rozwiązanie optymalne
76
Kolejne rozwiązania
11
12
13
14
21
22
23
24
31
32
33
34
60
10
0
50
20
0
0
0
0
20
40
0
x
x
x
x
x
x
x
x
x
x
x
x
=
=
=
=
=
=
=
=
=
=
=
=
FC : Z( ) 670
ij
x
=
Rozwiązanie optymalne
77
A jednak się skończyło!!!
Wyszukiwarka
Podobne podstrony:
BO, bo zagadnienie transportowe, Badania operacyjne - wprowadzenie
Wykład 1 cd3 zagadnienie transportowe, Elektrotechnika-materiały do szkoły, Gospodarka Sowiński
Jadczak R Badania operacyjne, wyklad zagadnienia transportowe i przydziału
badania operacyjne wykład 5 (zagadnienie transportowe)
BO II stacjonarne wykład nr 09
ZAGADNIENIA SOCJOLOGIA WYKŁAD
BO II stacjonarne wykład nr 08
poruszane zagadnienia na wykładzie, Automatyka i Robotyka, Semestr 3, Obróbka cieplna i powierzchnio
Zagadnienia transportowe z zadaniami, Podstawy logistyki, Transport i spedycja
Polityka transportowa, Polityka transportowa 2, wykładowca - prof
Poetyka reklamy & Dzieje dyskursu publicznego dr Warchala, Dzieje dyskursu publicznego zagadnienia d
zagadnienia MCR wykłady
zagadnienia transpor
Zagadnienia chemia wykład
BO II stacjonarne wykład nr 03
więcej podobnych podstron