Metoda konta 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 towar pierwszego dostawcy nie został jeszcze całkowicie rozdysponowany,

• w dół, gdy całą podaż tego dostawcy rozdzielono odbiorom.

W rozpatrywanym przykładzie do klatki M_1,P_1 wpisujemy 40 t (x_11=40) i przesuwamy się w prawo (ponieważ zapotrzebowanie piekarni P_1 zostało zaspokojone, a magazynowi M_1, zostało jeszcze 30t, które dostarczy do piekarni P_2 (x_12=30) . Obecnie przesuwamy się w dół ? do magazynu M_2, który dostarczy brakujące 30t mąki do piekarni P_2 (x_22=30) i pozostałe 20t mąki do piekarni P_3 (x_23=20). Przesuwamy się powtórnie w dół do magazynu M_3, który dostarczy brakujące 30t mąki do piekarni P_3 (x_33=30) i pozostałe 50t mąki do piekarni P_4 (x_34=50).

Metoda kąta północno zachodniego

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

rozwiązanie 1

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ć, odejmując od elementów poszczególnych wierszy macierzy kosztów, najmniejszy element znajdujący się w danym wierszu,

zerowanie wierszami

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

zerowanie po kolumnach

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. Rozmieszczanie przewozów rozpoczynamy od dowolnej klatki zerowej. Jeżeli uda się rozmieścić przewozy wyłącznie w klatkach, w których występują zera, to otrzymane rozwiązanie jest już optymalnym planem przewozów. Jeżeli nie, należy je poprawić stosując algorytm transportowy.

Rozdysponowanie przewozów ( dobrze jest zacząć od tych wierszy lub kolumn w których występuje jedno zero a więc nie mamy wyboru) rozpoczynamy od klatki M_2,P_1 gdzie możemy wpisać tylko 40 ( tyle wynosi zapotrzebowanie P_1) Przechodząc do drugiej kolumny ? do klatki M_3,P_2 wpisujemy 60 , w kolumnie trzeciej wpisujemy 20 na trasę M_3,P_3 i 30 na trasę M_1,P_3. Dla zbilansowania wpisujemy 40 na trasę M_1,P_4 i 10 na trasę M_2,P_4. Ponieważ w tym przypadku udało się rozmieścić wszystkie przewozy w klatkach z zerami ? otrzymane rozwiązanie jest optymalne.