E. Michlowicz: Zagadnienia transportowe
1. Przykład 1
Trzech dostawców: D1, D2, D3
zaopatruje w towary 4 sklepy: S1, S2, S3 i S4.
Dane:
- jednostkowe koszty transportu (w jzł za tonę);
- oferowane miesięcznie wielkości dostaw Ai (w tonach),
- miesięczne zapotrzebowanie sklepów Bj (w tonach)
podano w tablicy 1.
Tab. 1. Jednostkowe koszty transportu, podaży i popytu
Sklepy
Dostawcy
podaż
S1 S2 S3 S4 Ai [ton]
D1 40 30 40 10 350
D2 30 70 60 20 250
D3 50 30 60 70 400
popyt
Bj [ton] 200 300 250 250 1000
Opracować plan przewozu towarów od dostawców do sklepów,
minimalizujący całkowite koszty transportu z (xij).
Rozwiązanie:
bilans podaży i popytu:
3 4
Ai =� Bj =� 1000
[ton]
��1 ��1
i =� j =�
a więc jest to przykład zamkniętego zagadnienia transportowego (ZZT).
Zmienne decyzyjne xij oznaczają ilość ton towarów, jaka powinna być
dostarczona
od i-tego dostawcy (i=1,2,3) do j-tego sklepu (j=1,2,3,4):
Liczba zmiennych: 3 * 4 = 12.
Wyrażają to warunki:
a) dla dostawców
4
x +� x +� x +� x =� x1 j =� 350
�� (dostawca D1)
11 12 13 14
i =� 1
tzn:
suma wielkości dostaw odpadów od dostawcy D1 do wszystkich sklepów
powinna być równa podaży dostawcy;
i analogicznie dla dostawców D2, D3:
1
E. Michlowicz: Zagadnienia transportowe
4
x +� x +� x23 +� x =� x2 j =� 250 (dostawca D2)
��
21 24
22
i =� 1
4
x31 +� x32 +� x33 +� x34 =� x3 j =� 400
(dostawca D3)
��
i=�1
b) dla odbiorców (sklepy):
3
x +� x +� x =� xi 1 =� 200
�� (odbiorca S1)
11 21 31
i =� 1
tzn. suma dostaw towarów otrzymanych przez sklep S1 od wszystkich trzech
dostawców powinna być równa całkowitemu jej zapotrzebowaniu;
podobnie dla pozostałych odbiorców (S1, S2):
3
x +� x +� x =� xi 2 =� 300
�� (odbiorca S2)
12 22 32
i =�1
3
x13 +� x +� x =� xi 3 =� 250
��
(odbiorca S3)
23 33
i =�1
3
x +� x +� x =� xi 4 =� 250
�� (odbiorca S4)
14 24 34
i =�1
Muszą być także spełnione warunki brzegowe:
ł�
xij 0 dla (i = 1,2,3; j = 1,2,3,4),
a w funkcji celu należy zminimalizować łączne koszty transportu,
czyli:
z (xij) = 40x11 + 30x12 + 40x13 + 10x14 +
30x21 + 70x22 + 60x23 + 20x24 +
50x31 + 30x32 + 60x33 + 70x34 Ł� min
Rozwiązanie:
do wyboru jedna z metod przedstawionych na wykładzie KP-Z, MEM, MODI
lub inne, np. wykorzystujące algorytmy ewolucyjne.
x11 = & , x12 = & , x13 = & , x14 = & ,
x21 = & , & ..
x31 = & , & .. x34 = & ,
z (xij) =
2
E. Michlowicz: Zagadnienia transportowe
2. Przykład 2
Operator logistyczny posiada w różnych miejscach magazyny: M1, M2, M3, M4.
Otrzymał zamówienie od 3 klientów: Wrocław, Wałbrzych, Jelenia Góra.
Jak powinien rozwiązać problem rozdziału zadań przewozowych, by koszt
realizacji zadania był minimalny ?
Dokonaj:
- analizy zadania (schemat, bilans ?),
- napisz równanie: funkcji celu.
Zaproponuj rozwiązanie intuicyjne i porównaj z optymalnym
(optimum wynosi: 680 045 zł)
Punkt
Jelenia
Punkt odbioru Wrocław Wałbrzych podaż
Góra
nadania
240 295 335 465
Magazyn 1
Magazyn 2 243 305 344 680
Magazyn 3 250 312 348 400
Magazyn 4 248 315 352 680
popyt 510 610 1105
Plan przewozów:
Punkt
Jelenia
Punkt odbioru Wałbrzych podaż
Wrocław
Góra
nadania
465
Magazyn 1
Magazyn 2 680
Magazyn 3 400
Magazyn 4 680
popyt 510 610 1105
Plan przewozów - optymalny:
3
E. Michlowicz: Zagadnienia transportowe
Punkt
Jelenia
Punkt odbioru Wałbrzych podaż
Wrocław
Góra
nadania
 465  465
Magazyn 1
Magazyn 2  145 535 680
Magazyn 3   400 400
Magazyn 4 510  170 680
popyt 510 610 1105
3. Przykład 3
Operator logistyczny posiada w różnych miejscach magazyny: M1, M2, M3, M4.
Otrzymał zamówienie od 3 klientów: Tychy, Ruda Śl.,
Jak powinien rozwiązać problem rozdziału zadań przewozowych, by koszt
realizacji zadania był minimalny ?
Dokonaj:
- analizy zadania (schemat, bilans ?),
- napisz równanie funkcji celu,
- podaj obliczone koszty.
Zaproponuj rozwiązanie intuicyjne (własne) i porównaj z optymalnym
(optimum wynosi: 139 135 zł).
Punkt
Ruda
Punkt odbioru Gliwice Bytom podaż
Tychy
Śląska
nadania
60 82 91 76 500
Magazyn 1
Magazyn 2 64 83 95 77 450
Magazyn 3 70 85 100 81 560
Magazyn 4 72 90 105 80 280
popyt 620 420 365 385
4
E. Michlowicz: Zagadnienia transportowe
Plan przewozów:
Punkt
Punkt odbioru Ruda Śląska Gliwice Bytom podaż
Tychy
nadania
Magazyn 1
Magazyn 2
Magazyn 3
Magazyn 4
popyt
Plan przewozów - optymalny:
Punkt
Punkt odbioru Ruda Śląska Gliwice Bytom podaż
Tychy
nadania
170  330  500
Magazyn 1
Magazyn 2 450    450
Magazyn 3  420 35 105 560
Magazyn 4    280 280
popyt 620 420 365 385
4. Przykład 4
Przedsiębiorstwo produkcyjne ma dwa zakłady i cztery punkty przyjęć materiałów
do produkcji. W ciągu tygodnia punkty przyjmują 16 ton materiałów, które
następnie wysyłane są do zakładów. Punkty przyjmują następujące ilości
materiałów: punkt pierwszy 3 tony, drugi 2 tony, trzeci 4 tony, czwarty 7 ton.
Poszczególne zakłady potrzebują następujące ilości do produkcji: pierwszy 6 ton,
drugi 10 ton.
Firma chce ustalić taki plan przewozów materiałów z punktów przyjęć,
aby łączny koszt ich przewozu do zakładów był jak najmniejszy.
Tabela 1 zawiera koszty transportu jednej tony materiału w jednostkach
kosztowych [j] z poszczególnych punktów przyjęć do poszczególnych zakładów.
Tab. 1. Koszty transportu jednej tony w jednostkach [j] z poszczególnych
punktów przyjęć do poszczególnych zakładów
Zakład 1 Zakład 2
Punkt 1 3 2
Punkt 2 1 4
Punkt 3 5 7
Punkt 4 4 1
5
E. Michlowicz: Zagadnienia transportowe
Model matematyczny zadania ma postać:
z ( x )=� 3x11 +� 2 x12 +� 1x21 +� 4 x22 +� 5 x31 +� 7 x32 +� 4 x41 +� 1x42 �� min
1x11 +� 1x12 =� 3 ( 1 )
1x21 +� 1x22 =� 2 ( 2 )
1x31 +� 1x32 =� 4 ( 3 )
1x11 +� 1x12 =� 7 ( 4 )
1x11 +� 1x21 +� 1x31 +� 1x41 =� 6 ( 5 )
1x12 +� 1x22 +� 1x32 +� 1x42 =� 10 ( 6 )
xij ł� 0
Ograniczenia (1  4) dotyczą dostaw materiałów z poszczególnych punktów
przyjęć do obu zakładów. Orzekają one, że każdy punkt przyjęć wyśle całą
przyjętą ilość materiałów do produkcji.
Dwa ostatnie warunki (5  6) są ograniczeniami na wielkość przywozu
materiałów do poszczególnych odbiorców. Oznaczają, że przywóz do j-tego
zakładu ze wszystkich punktów przyjęć jest równy mocy przerobowej tego
zakładu.
Po rozwiązaniu, optymalna wartość funkcji z wynosi:
z (x) = 34,5 [j]
dla:
x1,2 = 30, x2,1 = 20, x3,1 = 40 x4,2 = 65.
Plan przewozów optymalnych przedstawia tabela 2.
Tab. 2. Optymalny plan przewozów
Zakład 1 Zakład 2
Punkt 1 0 30
Punkt 2 20 0
Punkt 3 40 0
Punkt 4 0 65
Według tabeli:
punkt 1 całą przyjętą ilość materiału (30) przesyła do zakładu drugiego,
punkt 2 przesyła 20 ton do zakładu pierwszego,
punkt 3 wysyła wszystko (40) do zakładu pierwszego,
a punkt 4 wysyła 65 ton do zakładu drugiego.
6
E. Michlowicz: Zagadnienia transportowe
5. Przykład 5
Dane jest zadanie transportowe:
Punkt
Odbiorca Odbiorca Odbiorca
Punkt odbioru podaż
1 2 3
nadania
10 20 30 300
Magazyn 1
Magazyn 2 50 40 30 700
popyt 500 300 200
Zapisz:
1. Zmienne decyzyjne
2. Parametry
3. Funkcję celu
4. Bilans podaży i popytu
5. Naszkicuj treść zadania
PRAWIDA
OWE ODPOWIEDZI
1. Zmienne decyzyjne:
xij  ilość dóbr od i-tego dostawcy dostarczona j-temu odbiorcy;
tzn.  jest i=1,2 oraz j=1,3, zatem:
x11  ilość dóbr dostarczona 1 odbiorcy z magazynu 1,
x12  ilość dóbr dostarczona 2 odbiorcy z magazynu 1,
x13  ilość dóbr dostarczona 3 odbiorcy z magazynu 1,
x21  ilość dóbr dostarczona 1 odbiorcy z magazynu 2,
x22  ilość dóbr dostarczona 2 odbiorcy z magazynu 2,
x23  ilość dóbr dostarczona 3 odbiorcy z magazynu 2.
2. Parametry (to zawsze wartości współczynników przy zmiennej decyzyjnej
 w opisie funkcji celu): cij ; i=1,2; j=1,3
c11  koszt transportu jednostki dobra na trasie od M1 do O1; c11 = 10 j
c12  & , c13  & , c21  & , c22  & , c23  & .
3. Funkcja celu:
minimum kosztów realizacji zadania rozdziału zadań przewozowych,
f(x) = z(x) = z(x11, x12, x13, x21, x22, x23) =
= 10 x11+20 x12+30 x13+50 x21+40 x22+30 x23 Ł� min
4. Bilans podaży i popytu:
Można używając sum, a można prosto:
Popyt: 500+300+200 = 1000 Podaż: 300+700 = 1000
stąd: 1000 = 1000 Ł� zadanie zbilansowane ZZT
5. Najprostszy schemat sieciowy połączeń pary (M1, M2) z trójką (O1, O2,
O3).
7