wzbo-wyklad nr 2b, MATERIAŁY DYDAKTYCZNE, WYBRANE ZAGADNIENIA BADAŃ OPERACYJNYCH
[ Pobierz całość w formacie PDF ]
Wybrane zagadnienia badań operacyjnych
dr inż. Zbigniew Tarapata
Wykład nr 2b: Zagadnienie transportowe
__________________________________________________________________________________________
ZAGADNIENIE TRANSPORTOWE
ZT jest specyficznym problemem z zakresu zastosowań
programowania liniowego.
ZT wykorzystuje się najczęściej do:
•
optymalnego planowania transportu towarów, przy
minimalizacji kosztów, lub czasu wykonania zadania;
•
optymalnego rozdziału czynników produkcji, w celu
maksymalizacji wartości produkcji, zysku, lub dochodu
np. rolniczego.
Zagadnienie transportowe ma prostą interpretację sieciową.
Przypuśćmy, że mamy
sieć skierowaną
(zwaną także
diagramem
ważonym),
określoną za pomocą zbioru wierzchołków
V
i zbioru
łuków (tj. skierowanych łuków)
E
(zob. Rys. 1). W zagadnieniu
transportowym sieć jest
dwudzielna i pełna
,
tzn. wszystkie jej
wierzchołki można podzielić na dwie grupy, na
węzły dostawy
ponumerowane
i=
1,2,...,
m
i
węzły odbioru
ponumerowane
j=
1,2,...,
n
,
każdy wierzchołek dostawy ma
n
łuków wychodzących
z niego do wszystkich wierzchołków odbioru. Dla każdego łuku
jest określony jednostkowy koszt
c
ij
transportowanego dobra.
Zagadnienie polega na wyznaczeniu takich wielkości przewozu
x
ij
,
które minimalizują całkowity koszt transportu
z
.
Rys.1
1
Wybrane zagadnienia badań operacyjnych
dr inż. Zbigniew Tarapata
Wykład nr 2b: Zagadnienie transportowe
__________________________________________________________________________________________
Zagadnienie transportowe definiujemy
następująco:
znaleźć minimum
∑
==
m
n
(1.1)
z
=
c
ij
x
ij
i
11
j
przy warunkach
∑
=
n
x
≤
a
,
i
= 1, 2, ...,
m,
(1.2)
ij
i
j
1
∑
=
m
x
≥
b
,
j
= 1, 2, ...,
n,
(1.3)
ij
j
i
1
x
ij
≥
0,
i
= 1, 2, ...,
m;
j
= 1, 2, ...,
n.
Pierwszych
m
nierówności odnosi się do wierzchołków dostawy
(podaż), następne
n
nierówności odnosi się do wierzchołków
odbioru (popyt). Elementy
a
i
oznaczają podaż
i
-tego dostawcy,
a elementy
b
j
- popyt (zapotrzebowanie)
j
-tego odbiorcy.
Zagadnienie można rozwiązywać metodą simpleks, jednak jest
ona w tym przypadku mało efektywna. Najczęściej stosuje się
metodę kąta północno-zachodniego
. Służy ona do znalezienia
pierwszego rozwiązania bazowego.
2
Wybrane zagadnienia badań operacyjnych
dr inż. Zbigniew Tarapata
Wykład nr 2b: Zagadnienie transportowe
__________________________________________________________________________________________
Zagadnienie transportowe ma rozwiązanie dopuszczalne, gdy
∑∑
=
m
n
(1.4)
a
i
≥
b
j
i
1
j
=
1
a ograniczenia odbioru stają się równościami dla rozwiązania
optymalnego, tj.
∑
=
m
x
=
b
,
(1.5)
ij
j
i
1
dla wszystkich
j .
Ponadto, jeśli
∑∑
=
m
n
a
=
b
(1.6)
i
j
i
1
j
=
1
to każde rozwiązanie dopuszczalne spełnia wszystkie
nierówności jako równości.
Bez utraty ogólności można przyjąć, że (1.2) i (1.3) są
równościami, ponieważ zawsze
możemy wprowadzić fikcyjny
wierzchołek
odbioru
n +1
, o wartości odbioru równej
∑∑
=
m
n
(1.7)
b
n
+
1
=
a
i
−
b
j
i
1
j
=
1
i kosztami
c
i,n+1
= 0
, i
= 1, 2, . . . ,
m
.
Postępowanie to nazywamy
bilansowaniem zagadnienia
transportowego
.
3
Wybrane zagadnienia badań operacyjnych
dr inż. Zbigniew Tarapata
Wykład nr 2b: Zagadnienie transportowe
__________________________________________________________________________________________
Przykład
Pewna firma ma zakłady wytwórcze w miejscowościach A, B,
C oraz centra dystrybucyjnie w miejscowościach D, E, F.
Możliwości produkcyjne zakładów wynoszą odpowiednio 50, 70 i
30 jednostek, natomiast prognozy popytu w centrach -
odpowiednio 20, 40 i 90 jednostek. Należy określić taki plan
przewozów, by przy uwzględnieniu możliwości produkcyjnych
zakładów oraz przewidywanego popytu w centrach
dystrybucyjnych zminimalizować łączne koszty transportu
(które są proporcjonalne do ilości przewożonego towaru).
Jednostkowe koszty transportu przedstawione są w tabeli:
Miejscowość
D
E
F
A
3
5
7
B
12
10
9
C
13
3
9
Opis oznaczeń:
Dostawcy: D
1
, D
2
, D
3
- zakłady produkcyjne w miejscowościach A,
B, C
Odbiorcy: O
1
, O
2
, O
3
- centra dystrybucyjne w miejscowościach D,
E, F
Określenie popytu i podaży:
Podaż: 50 + 30 + 70= 150
Popyt: 20 + 40 + 90 = 150
Zadanie jest zbilansowane, ponieważ: POPYT = PODAŻ.
4
Wybrane zagadnienia badań operacyjnych
dr inż. Zbigniew Tarapata
Wykład nr 2b: Zagadnienie transportowe
__________________________________________________________________________________________
Sieć skierowana dla tego problemu:
Celem jest minimalizacja kosztów transportu
.
M A T E M A T Y C Z N E S F O R M UŁO W A N I E
Z A G A D N I E N I A T R A N S P O R T O W E G O
Wprowadzamy oznaczenia:
x
ij
- wielkość przewozu od
i
-tego dostawcy do
j
-tego odbiorcy;
Koszty transportu (funkcja celu):
Z(x
11
, x
12
, x
13
, x
21
, x
22
, x
23
, x
31
, x
32
, x
33
) =
= 3x
11
+5x
12
+7x
13
+12x
21
+10x
22
+9x
23
+13x
31
+3x
32
+9x
33
--> min
Ograniczenia podaży:
1.
Ilość towaru wysyłanego przez dostawcę D
1
odbiorcom O
1
, O
2
,
O
3
jest równa podaży dla tego dostawcy i wynosi 50:
x
11
+x
12
+x
13
= 50
2.
Ilość towaru wysyłanego przez dostawcę D
2
odbiorcom O
1
, O
2
,
O
3
jest równa podaży dla tego dostawcy i wynosi 70:
x
21
+ x
22
+ x
23
= 70
3.
Ilość towaru wysyłanego przez dostawcę D
3
odbiorcom O
1
, O
2
,
O
3
jest równa podaży dla tego dostawcy i wynosi 30:
x
31
+x
32
+x
33
= 30
oraz
Xij
≥
0
5
[ Pobierz całość w formacie PDF ]