Zagadnienie transportowe
Przykład
Cztery piekarnie są zaopatrywane w mąkę z trzech magazynów. Zasoby mąki w magazynach wynoszą: mag.1 - 100 t, mag.2 - 150 t i mag.3 - 200 t., a zapotrzebowanie na mąkę zgłaszane przez piekarnie wynoszą: piekarnia 1 - 50 t, piekarnia 2 - 80 t, piekarnia 3 - 180 t, piekarnia 4 - 120 t. Koszty transportu pokazano w tabelce:
Magazyny |
Piekarnie |
|||
|
1 |
2 |
3 |
4 |
mag.1 |
20 |
15 |
18 |
25 |
mag.2 |
10 |
18 |
13 |
20 |
mag.3 |
18 |
20 |
25 |
6 |
Wyznaczyć plan przewozów, aby koszt transportu był minimalny.
Zadanie zamknięte - popyt równa się podaży
Zadanie otwarte - podaż jest większa od popytu. W tym wypadku należy zadanie zamknąć poprzez dodanie fikcyjnego odbiorcy.
Magazyny |
Piekarnie |
|
Podaż |
|||
|
1 |
2 |
3 |
4 |
fikcyjny |
|
mag.1 |
20 |
15 |
18 |
25 |
0 |
100 |
mag.2 |
10 |
18 |
13 |
20 |
0 |
150 |
mag.3 |
18 |
20 |
25 |
6 |
0 |
200 |
Popyt |
50 |
80 |
180 |
120 |
20 |
450 |
Model matematyczny:
Jest 15 zmiennych: x11, x12, x13, ..., x35
Każda zmienna xij jest ilością mąki przewożonej z i-tego magazynu do j piekarni.
x11+x12+x13+x14+x15 ≤ 100
x21+x22+x23+x24+x25 ≤ 150
x31+x32+x33+x34+x35 ≤ 200
x11+x21+x31 = 50
x12+x22+x32 = 80
x13+x23+x33 = 180
x14+x24+x34 = 120
x15+x25+x35 = 20
F= 20x11+15x12+18x13+25x14+0x15+10x21+18x22+13x23+20x24+0x25+
+18x31+20x32+25x33+6x34+0x35 → min
xij ≥ 0
Metody poszukiwania rozwiązania dopuszczalnego
Metoda konta Północno - Zachodniego (M N-W)
50 |
50 |
0 |
0 |
0 |
100 |
0 |
30 |
120 |
0 |
0 |
150 |
0 |
0 |
60 |
120 |
20 |
200 |
50 |
80 |
180 |
120 |
20 |
|
Koszt rozwiązania:
F=20*50+15*50+18*30+13*120+25*60+6*120+0*20 = 6070.
Rozwiązanie nie jest optymalne!
Metoda najmniejszego elementu macierzy
0 |
80 |
20 |
0 |
0 |
100 |
50 |
0 |
100 |
0 |
0 |
150 |
0 |
0 |
60 |
120 |
20 |
200 |
50 |
80 |
180 |
120 |
20 |
|
Koszt rozwiązania:
F=10*50+15*80+18*20+13*100+25*60+6*120+0*20 = 5580.
Rozwiązanie nie jest optymalne!
Zadania pochodne od zadania transportowego
Wszystkie przykłady są pochodną zadania o magazynach i piekarniach.
Zadanie transportowo - magazynowe
Jeżeli pozostawienie mąki w magazynach będzie nas kosztować odpowiednio 10, 6 i 5 zł/t to tabela kosztów będzie wyglądać następująco:
Magazyny |
Piekarnie |
|
Podaż |
|||
|
1 |
2 |
3 |
4 |
fikcyjny |
|
mag.1 |
20 |
15 |
18 |
25 |
10 |
100 |
mag.2 |
10 |
18 |
13 |
20 |
6 |
150 |
mag.3 |
18 |
20 |
25 |
6 |
5 |
200 |
Popyt |
50 |
80 |
180 |
120 |
20 |
450 |
Odpowiednie zmiany nastąpią również z funkcji celu.
Zadanie produkcyjno - transportowe
Jeżeli mamy do czynienia nie z magazynami mąki ale z młynami i w każdym z nich tona maki kosztuje odpowiednio: 100, 80 i 90 zł/t to tabela kosztów będzie wyglądała następująco:
Magazyny |
Piekarnie |
|
Podaż |
|||
|
1 |
2 |
3 |
4 |
fikcyjny |
|
młyn 1 |
120 |
115 |
118 |
125 |
100 |
100 |
młyn 2 |
900 |
98 |
93 |
100 |
80 |
150 |
młyn 3 |
108 |
110 |
115 |
96 |
90 |
200 |
Popyt |
50 |
80 |
180 |
120 |
20 |
450 |
Odpowiednie zmiany nastąpią również z funkcji celu.
Zadanie produkcyjno - transportowo - magazynowe
Jeżeli połączymy zadanie produkcyjno - transportowe i transportowo magazynowe, tzn. młyny mąkę produkują i transportują do piekarni lub pozostawiają w magazynie to tabela kosztów będzie wyglądała następująco:
Magazyny |
Piekarnie |
|
Podaż |
|||
|
1 |
2 |
3 |
4 |
fikcyjny |
|
młyn 1 |
120 |
115 |
118 |
125 |
110 |
100 |
młyn 2 |
900 |
98 |
93 |
100 |
86 |
150 |
młyn 3 |
108 |
110 |
115 |
96 |
95 |
200 |
Popyt |
50 |
80 |
180 |
120 |
20 |
450 |
Odpowiednie zmiany nastąpią również z funkcji celu.
Zadanie z blokowaniem tras
Jeżeli piekarnia 3 nie zapłaciła trzeciemu magazynowi ostatnich 5 faktur i kierownik tego magazynu odmówił przewożenia mąki do tej piekarni to należy odpowiednią trasę zablokować poprzez wpisanie dużej liczby:
Magazyny |
Piekarnie |
|
Podaż |
|||
|
1 |
2 |
3 |
4 |
fikcyjny |
|
mag.1 |
20 |
15 |
18 |
25 |
0 |
100 |
mag.2 |
10 |
18 |
13 |
20 |
0 |
150 |
mag.3 |
18 |
20 |
100 |
6 |
0 |
200 |
Popyt |
50 |
80 |
180 |
120 |
20 |
450 |
Odpowiednie zmiany nastąpią również z funkcji celu.
Zadanie wieloetapowe
Mąka jest produkowana przez 2 młyny i dostarczana do magazynów a następnie piekarni z zadania. Koszt transportu z młynów do magazynów pokazano w tabeli:
|
mag.1 |
mag.2 |
mag.3 |
Młyn 1 |
20 |
25 |
15 |
Młyn 2 |
16 |
18 |
30 |
Młynom nie wolno sprzedawać maki bezpośrednio do piekarni. Należy skonstruować plan przewozów tak aby łączny koszt transportu był minimalny.
Powstanie nowa tabela kosztów:
|
Odbiorcy |
|||||||
|
mag.1 |
mag.2 |
mag.3 |
piek.1 |
piek.2 |
piek.3 |
piek.4 |
|
Dostawcy |
młyn 1 |
20 |
25 |
15 |
M |
|||
|
młyn 2 |
16 |
18 |
30 |
|
|||
|
mag.1 |
M |
20 |
15 |
18 |
25 |
||
|
mag.2 |
|
10 |
18 |
13 |
20 |
||
|
mag.3 |
|
18 |
20 |
25 |
6 |
||
Gdzie M oznacza dużą liczbę ( wystarczy powyżej 30).
Załącznik
Dla chętnych rozwiązane do końca zadanie transportowe (do uzyskania rozwiązania optymalnego).
Zadanie
Pewien dystrybutor jest odpowiedzialny za rozwiezienie butelek z napojami chłodzącymi od trzech dostawców do czterech odbiorców. Dystrybutor wie ile jednostek towaru mają do dyspozycji dostawcy (odpowiednio 1000, 1500 i 2000 butelek) i wie ile jednostek towaru potrzebują odbiorcy (odpowiednio 1250, 650, 1850, 750). Aby zaspokoić popyt odbiorców, dostawcy dysponować muszą ilością towaru co najmniej równa popytowi. Zadaniem dystrybutora jest ustalić taki plan przewozów, który spełniałby wymagania odbiorców i jednocześnie brał pod uwagę możliwości dostawców. Kryterium oceny rozwiązań jest koszt całkowity transportu. Koszty jednostkowe transportu przedstawiają się następująco:
.
Rozwiązanie.
I. Szukanie dowolnego rozwiązania dopuszczalnego.
Metodą kąta N-W szukam rozwiązania:
1000 |
0 |
0 |
0 |
1000 |
250 |
650 |
600 |
0 |
1500 |
0 |
0 |
1250 |
750 |
2000 |
1250 |
650 |
1850 |
750 |
|
Wartość funkcji celu F=54.800 zł.
II. Sprawdzanie czy rozwiązanie jest optymalne
Buduję tabelę kosztów zastępczych (KZ).
Z tabeli zawierającej koszty wybieram pola odpowiadające niezerowym rozwiązaniom. Następnie pozostałe pola uzupełniam w taki sposób aby kolumny i wiersze były liniowo zależne.
12 |
14 |
17 |
11 |
6 |
8 |
11 |
5 |
12 |
14 |
17 |
11 |
Następnie znajduję różnicę między kosztami i kosztami zastępczymi (K-KZ):
0 |
-4 |
-6 |
-4 |
0 |
0 |
0 |
9 |
0 |
1 |
0 |
0 |
Jeżeli w K-KZ znajdują się liczby ujemne - rozwiązanie nie jest optymalne (analogicznie jak w metodzie SIMPLEX). To nie jest.
III. Poprawianie rozwiązania.
W miejscu w którym w K-KZ znajduje się najmniejsza ujemna liczba będzie znajdowało się nowe niezerowe rozwiązanie. Aby sumy kolumn i wierszy zgadzały się należy jednocześnie odjąć i dodać odpowiednie liczby w innych zmiennych. W tym celu wyznaczam graf zadania (linia łącząca wszystkie elementy rozwiązania „zakręcająca” wyłącznie w miejscach niezerowych rozwiązań). Nowy element rozwiązania należy połączyć z najbliższymi elementami grafu w taki sposób, aby powstała zamknięta ścieżka. Liczb znajdujące się na wierzchołkach tej ścieżki kolejno oznaczam znakiem (+) i (-) rozpoczynając od (+) dla nowego elementu rozwiązania. Z liczb z (-) wybieram najmniejszą. Liczbę te w zależności od znaku dodam i odejmę od wierzchołków.
1000(-) |
0 |
?(+) |
0 |
|
400 |
0 |
600 |
0 |
250(+) |
650 |
600(-) |
0 |
|
850 |
650 |
0 |
0 |
0 |
0 |
1250 |
750 |
|
0 |
0 |
1250 |
750 |
Wartość funkcji celu F=50.000 zł.
II. Sprawdzanie czy rozwiązanie jest optymalne
KZ=
12 |
14 |
9 |
3 |
6 |
8 |
3 |
-3 |
20 |
22 |
17 |
11 |
K-KZ=
0 |
-4 |
0 |
4 |
0 |
0 |
8 |
17 |
-8 |
-7 |
0 |
0 |
W tabeli są liczby ujemne - rozwiązanie nie jest optymalne.
III. Poprawianie rozwiązania.
400(-) |
0 |
600(+) |
0 |
|
0 |
0 |
1000 |
0 |
850 |
650 |
0 |
0 |
|
850 |
650 |
0 |
0 |
?(+) |
0 |
1250(-) |
750 |
|
400 |
0 |
850 |
750 |
Wartość funkcji celu F=46.800 zł.
II. Sprawdzanie czy rozwiązanie jest optymalne
KZ=
4 |
6 |
9 |
3 |
6 |
8 |
11 |
5 |
12 |
14 |
17 |
11 |
K-KZ=
8 |
4 |
0 |
4 |
0 |
0 |
0 |
9 |
0 |
1 |
0 |
0 |
Brak liczb ujemnych.
Rozwiązanie:
0 |
0 |
1000 |
0 |
850 |
650 |
0 |
0 |
400 |
0 |
850 |
750 |
jest optymalne.
Tomasz Owczarek Strona 4 Zagadnienie transportowe.doc
Wyszukiwarka