Mapa Serwisu
|
| Metoda transportowa |
|
Admin1 dnia marzec 15 2007 16:56:45
|
Metoda transportowa
Trzy lokale pobierają z trzech hurtowni alkohole. Zapotrzebowanie lokali w alkohol wynoszą odpowiednio: (lokal L1) 100, (lokal L2) 300, (lokal L3) 200 butelek (jednostek). Hurtownie dysponują odpowiednio następującymi ilościami butelek alkoholu : (hurtownia H1) 100, (hurtownia H2) 100, (hurtownia H3) 400 butelek (jednostek).
Macierz jednostkowych kosztów przewozu między każdą hurtownią a każdym lokalem przedstawia się następująco:
1 2 4
C = 2 1 3
2 1 2
Należy znale¼ć taki plan przewozów, przy którym łączne koszty przewozu będą najniższe.
Oznaczenia:
xij – wielkość dostawy z i (hurtowni) do j (lokalu),
ai – zasoby (możliwości) hurtowni,
bj – zapotrzebowanie lokalu,
(i = 1, 2, 3 , j = 1, 2, 3)
Należy określić wartości zmiennych xij , które minimalizują całkowity koszt:
K = 1x11 + 2x12 + 4x13 + 2x21 + 1x22 + 3x23 + 2x31 + 1x32 + 2x33
przy ograniczeniach:
x11 + x12 + x13 = 100 warunki ograniczające dla hurtowni
xij
x21 + x22 + x23 = 100
x31 + x32 + x33 = 400
x11 + x21 + x31 = 100 warunki ograniczające dla lokali
xij
x12 + x22 + x32 = 300
x13 + x23 + x33 = 200
xij 0 i = 1, 2, 3, j = 1, 2, 3
Podane informacje wygodnie jest przedstawić w postaci tzw. tabliczki transportowej:
j
i LOKALE Możliwości dostaw
ai
L1 L2 L3
HURTOWN I E H1 1
x11 2
x12 4
x13
100
H2 2
x21 1
x22 3
x23
100
H3 2
x31 1
x32 2
x33
400
Zapotrzebowa-nie
bj
100
300
200 600
600
Rozwiązujemy w/w zagadnienie transportowe metodą algorytmu transportowego. Postępowanie w tej metodzie składa się z trzech zasadniczych etapów:
- wyznaczenia wstępnego dopuszczalnego rozwiązania bazowego,
- oceny optymalności otrzymanego rozwiązania,
- przejścia do nowego rozwiązania bazowego lepszego od poprzedniego.
Wstępne dopuszczalne rozwiązanie bazowe wyznaczone zostanie metodami:
A) metodą kąta północno-zachodniego,
B) metodą minimum w wierszu,
C) metodą minimum w kolumnie,
D) metodą minimalnego elementu w macierzy.
A) Metoda kąta północno-zachodniego
Wypełnianie tablicy transportowej:
x11 = min a1, b1 = min 100, 100 = 100
a1 = b1
x12 = x13 = 0
x21 = x31 = 0
Zapotrzebowanie pierwszego lokalu zostało zaspokojone (pozostałe pola w pierwszej kolumnie i w pierwszym wierszu zostaną puste). Zasoby pierwszej hurtowni zostały wyczerpane.
x22 = min a2 , (b2 – x12) = min 100, (300 – 0) = min 100, 300 = 100
Zasoby drugiej hurtowni zostały wyczerpane, gdyż x23 = 0.
X32 = min a3 , (b2 – x22) = min 400, (300 – 100) = min 400, 200 = 200
x33 = min (a3 – x32) , b3 = min (400-200 ) , 200 = min 200, 200 = 200
Możliwości dostaw zostały wyczerpane.
Macierz wygląda następująco:
j
i LOKALE Możliwości dostaw
ai
L1 L2 L3
HURTOWN I E H1 1
100 2
- 4
-
100
H2 2
- 1
100 3
-
100
H3 2
- 1
200 2
200
400
Zapotrzebowa-nie
bj
100
300
200 600
600
Całkowity koszt dla powyższego rozwiązania wynosi:
K = 100 + 100 + 200 + 2 • 200 = 800
Sprawd¼my czy istnieje inne optymalne rozwiązanie.
Wyznaczamy cykl dla pierwszego pustego pola i obliczamy odpowiadającą temu polu ocenę zgodnie ze wzorem:
ij =
- wska¼nik optymalności,
I1 - zbiór nieparzystych numerów pól cyklu,
I2 - zbiór parzystych numerów pól cyklu,
I1 Cij - suma całkowitych przewozów jednostkowych dla zbioru nieparzystych
pól cyklu,
I2 Cij - suma całkowitych przewozów jednostkowych dla zbioru parzystych
pól cyklu,
- liczba o którą będzie się zmieniać pole w cyklu.
Aby zmniejszyć wartość funkcji kryterium musi istnieć co najmniej jedno swobodne pole, któremu odpowiada ocena ujemna. Istnienie takiego pola oznacza, że możemy znale¼ć lepsze rozwiązanie.
j
i LOKALE Możliwości dostaw
ai
L1 L2 L3
HURTOWN I E H1 1
100
100
H2
1
100
-
3
+
100
H3
+ 1
200 - 2
200
400
Zapotrzebowa-nie
bj
100
300
200 600
600
Rozpoczynamy od obliczenia pola (2, 3).
Cykl dla tego pola (2, 3) (3, 3) (3, 2) (2, 2) wynosi
23 = (3 + 1) – (2 + 1) = 4 – 3 = 1
23 0
Jeżeli rozwiązanie optymalne oceny 23 dla pola swobodnego jest dodatnie to zbilansowane rozwiązanie transportowe posiada dokładnie jedno – dokładnie jedno - rozwiązanie optymalne.
Odpowiadająca temu rozwiązaniu wartość funkcji celu wynosi K = 800.
B) Metoda minimum w wierszu
Minimalnym elementem w wierszu macierzy kosztów jednostkowych pierwszym jest C1k. Zatem w pierwszej kolejności rozpoczynamy wypełnianie od pola x11.
x11 = min a1 , b1 = min 100, 100 = 100
x12 = x13 = 0 ,a także x21 = x31 = 0
następnym minimalnym elementem w wierszu drugim będzie
x22 = min a2 , (b2 – a2) = min 100, (300 – 100) = 100
zatem x23 = 0.
Kolejnym najmniejszym elementem jest w trzecim wierszu
X32 = min (b2 – x22) , a3 = min (300 – 100) , 400 = min 200 , 400 = 200
x33 = min b3, (a3 – x32) = min 200 , (400-200 ) = min 200, 200 = 200
Macierz wygląda następująco:
j
i LOKALE Możliwości dostaw
ai
L1 L2 L3
HURTOWNIE H1 1
100 2
- 4
-
100
H2 2
- 1
100 3
-
100
H3 2
- 1
200 2
200
400
Zapotrzebowa-nie
bj
100
300
200 600
600
Otrzymane rozwiązanie jest identyczne jak przedstawione wcześniej metodą kąta północno-zachodniego.
Odpowiadająca temu rozwiązaniu wartość funkcji celu wynosi K = 800.
C) Metoda minimum w kolumnie
Przy tej metodzie wykonujemy obliczenia podobne jak przy minimum w wierszu. Wypełnianie tablicy rozpoczyna się od pola znajdującego się w pierwszej kolumnie, któremu odpowiada najniższy jednostkowy koszt transportu. Następnie kontynuuje się postępowanie przechodząc kolejno pozostałe kolumny, aż do ostatniej.
Rozwiązanie za pomocą tej metody przedstawia się następująco:
j
i LOKALE Możliwości dostaw
ai
L1 L2 L3
HURTOWNIE H1 1
100 2
- 4
-
100
H2 2
- 1
100 3
-
100
H3 2
- 1
200 2
200
400
Zapotrzebowa-nie
bj
100
300
200 600
600
Otrzymane rozwiązanie odpowiada rozwiązaniom wcześniejszym. Wartość funkcji celu wynosi K = 800.
D) Metoda minimum elementu w macierzy
W przypadku tej metody badana jest cała macierz kosztów jednostkowych, by znale¼ć minimalny element. Rozpoczynamy od pola, któremu ten element odpowiada. Następnie kolejno szukamy minimalnego elementu wśród jednostkowych kosztów odpowiadających pustym polom. Wyznaczamy w ten sposób następne pole, które należy wypełnić.
Wyznaczone tą metodą rozwiązanie ma postać:
j
i LOKALE Możliwości dostaw
ai
L1 L2 L3
HURTOWNIE H1 1
100 2
- 4
-
100
H2 2
- 1
100 3
-
100
H3 2
- 1
200 2
200
400
Zapotrzebowa-nie
bj
100
300
200 600
600
Otrzymaliśmy identyczne rozwiązanie.
Rozwiązanie dla przedstawione w tej pracy problemu transportowego jest jedynym rozwiązaniem optymalnym.
|
|
|
Zaloguj się, żeby móc dodawać komentarze.
|
|
|
Dodawanie ocen dostępne tylko dla zalogowanych Użytkowników.
Proszę się zalogować lub zarejestrować, żeby móc dodawać oceny.
Brak ocen.
|
|
|
|
