Badania operacyjne: Zagadnienia transportowe + Solver

Olśniło mnie kiedyś i rozwiązałem takie jedno przykładowe zadanie od A do Z. Postanowiłem wiec zamieścić je dla potomnych bo mi już nie będzie potrzebne. Sesja Zaliczona!!!

Trzy magazyny: $M_1, M_2, M_3$, zaopatrują w mąkę cztery piekarnie: $P_1, P_2, P_3, P_4$. Jednostkowe koszty transportu (w zł za tonę), oferowane miesięczne wielkości dostaw $A_i$ (w tonach) oraz miesięczne zapotrzebowanie piekarń $B_j$ (w tonach) podano w tabeli poniżej.

Tabela 1

Należy opracować plan przewozu mąki z magazynów do piekarń, minimalizujący całkowite koszty transportu.

Oznacza to, że mamy do czynienia z zagadnieniem transportowym zamkniętym (ZTZ).

Zmienne decyzyjne $x_{ij}$ oznaczają ilość ton mąki, jaka powinna być dostarczona z $i$-tego magazynu ($i=1,2,3$) do $j$-tej piekarni ($j=1,2,3,4$); jest ich $3 \times 4 = 12$. Ponieważ jest to zagadnienie transportowe zamknięte (zbilansowane), dostawcy sprzedadzą całą ilość oferowanego towaru, a zapotrzebowania piekarń zostaną w całości zaspokojone.

Ograniczenia dla dostawców

Suma wielkości dostaw mąki z magazynu $M_i$ do wszystkich piekarń powinna być równa podaży magazynu:

Ograniczenia dla odbiorców

Suma dostaw mąki otrzymanych przez piekarnię $P_j$ ze wszystkich trzech magazynów powinna być równa całkowitemu jej zapotrzebowaniu:

Dodatkowe warunki brzegowe (nieujemności)

Minimalizacja łącznych kosztów transportu – Funkcja Celu

albo prościej:

gdzie $c_{ij}$ to jednostkowe koszty transportu z tabeli 1.

Dla tak sformułowanego modelu wyznaczamy początkowe rozwiązanie dopuszczalne – przykładowo za pomocą dwu wybranych metod.

Metoda kąta północno-zachodniego

Polega na tym, że wypełnienie macierzy przewozów $[x_{ij}]$ rozpoczyna się od klatki w lewym górnym rogu (stąd nazwa kąta północno-zachodniego). Wpisuje się do niej mniejszą z liczb $(A_1, B_1)$ odpowiadających tej klatce, a następnie przesuwa się w prawo lub w dół:

• w prawo, gdy popyt bieżącej kolumny został wyczerpany,
• w dół, gdy podaż bieżącego wiersza została wyczerpana,
• jeśli oba wyczerpią się jednocześnie — występuje degeneracja (należy wstawić sztuczne zero).

W rozpatrywanym przykładzie do klatki $M_1, P_1$ wpisujemy $40\text{ t}$ ($x_{11} = 40$) i przesuwamy się w prawo (ponieważ zapotrzebowanie piekarni $P_1$ zostało zaspokojone, a magazynowi $M_1$ zostało jeszcze $30\text{ t}$, które dostarczy do piekarni $P_2 \implies x_{12} = 30$).

Obecnie przesuwamy się w dół – do magazynu $M_2$, który dostarczy brakujące $30\text{ t}$ mąki do piekarni $P_2$ ($x_{22} = 30$) i pozostałe $20\text{ t}$ mąki do piekarni $P_3$ ($x_{23} = 20$).

Przesuwamy się powtórnie w dół do magazynu $M_3$, który dostarczy brakujące $30\text{ t}$ mąki do piekarni $P_3$ ($x_{33} = 30$) i pozostałe $50\text{ t}$ mąki do piekarni $P_4$ ($x_{34} = 50$).

Uwaga: W tym przykładzie ani razu popyt i podaż nie wyczerpały się jednocześnie, więc degeneracja nie wystąpiła. Rozwiązanie bazowe ma $3 + 4 - 1 = 6$ niezerowych przewozów — tyle, ile powinno.

Rozwiązaniu temu odpowiadają następujące koszty transportu:

Metoda minimalnego elementu macierzy (klatek zerowych)

Polega na rozmieszczaniu przewozów przede wszystkim po tych trasach, na których koszty są najmniejsze. Punktem wyjścia jest przekształcenie macierzy kosztów do takiej postaci, by w każdym wierszu i w każdej kolumnie występowało co najmniej jedno zero.

Można to uzyskać:

1. Odejmując od elementów poszczególnych wierszy macierzy kosztów najmniejszy element znajdujący się w danym wierszu:

2. A następnie od poszczególnych kolumn otrzymanej w ten sposób macierzy odejmując element najmniejszy znajdujący się w danej kolumnie:

Mając tak przekształconą macierz kosztów, staramy się rozmieścić przewozy na trasy, gdzie koszty są najniższe, czyli gdzie występują zera. Otrzymujemy w ten sposób początkowe rozwiązanie bazowe. Aby potwierdzić, że jest ono optymalne, należy przeprowadzić test optymalności — na przykład metodą potencjałów (MODI) lub stepping stone. W tym konkretnym zadaniu rozwiązanie okazało się optymalne, ale nie wynika to z samego faktu użycia klatek zerowych.

Rozdysponowanie przewozów najlepiej rozpocząć od tych kolumn (lub wierszy), w których występuje tylko jedno zero — nie mamy wtedy wyboru i unikamy błędów.

W przekształconej macierzy:

• Kolumna $P_1$ (popyt $40$) ma tylko jedno zero — w klatce $M_2, P_1$ (podaż $M_2 = 50$). Wpisujemy mniejszą z tych dwóch wartości: $\min(50, 40) = 40$. Popyt $P_1$ zostaje wyczerpany, podaż $M_2$ spada z $50$ do $10$.

• Kolumna $P_2$ (popyt $60$) ma tylko jedno zero — w klatce $M_3, P_2$ (podaż $M_3 = 80$). Wpisujemy $\min(80, 60) = 60$. Popyt $P_2$ zostaje wyczerpany, podaż $M_3$ spada z $80$ do $20$.

Teraz w kolumnie $P_3$ (popyt $50$) zera są w $M_1, P_3$ i $M_3, P_3$. $M_3$ ma już tylko $20$ podaży — wpisujemy tam $x_{33} = 20$, co wyczerpuje podaż $M_3$. Pozostały popyt $P_3$ wynosi $50 - 20 = 30$ — pokrywa go $M_1$: $x_{13} = 30$. Podaż $M_1$ spada z $70$ do $40$.

W kolumnie $P_4$ (popyt $50$) zera są w $M_1, P_4$ i $M_2, P_4$. Zostało: $M_1$ ma $40$, $M_2$ ma $10$, popyt to $50$. Wpisujemy $x_{14} = 40$ i $x_{24} = 10$.

Wszystkie przewozy udało się rozmieścić w klatkach zerowych. W tym przykładzie rozwiązanie to okazuje się optymalne (co można potwierdzić metodą potencjałów lub Solverem).

Związane są z nim następujące koszty transportu:

W tym przykładzie metoda klatek zerowych prowadzi do znacznie lepszego rozwiązania początkowego (8000 zł vs 13 100 zł metodą kąta północno-zachodniego). W innych zadaniach przewaga jednej metody nad drugą zależy jednak od konkretnej macierzy kosztów.

Solver

Postępować według instrukcji. Analogicznie rozwiązuje się podobne zadania :)