Zagadnienie transportowe i metoda potencjałów

Mgr inż.

Sebastian Dziarmaga-Działyński

Wirtualna kancelaria korepetytorska i konsultacyjna – wszechwiedza.pl

Zagadnienie transportowe jest jednym z klasycznych problemów programowania liniowego. Chociaż każde takie zadanie można, przynajmniej teoretycznie, rozwiązać ogólną metodą simplex, to w praktyce dla pewnych szczególnych typów problemów wygodniej stosuje się algorytmy wyspecjalizowane. Jednym z najważniejszych przykładów takiego podejścia jest właśnie algorytm transportowy.

O ile algorytm simplex jest metodą uniwersalną, przeznaczoną do rozwiązywania ogólnych zadań programowania liniowego, o tyle metoda transportowa wykorzystuje szczególną strukturę pewnej klasy problemów. Dzięki temu obliczenia są bardziej przejrzyste, a samo zadanie można wygodnie zapisać w postaci tabeli transportowej.

W tym artykule omówimy, czym jest zagadnienie transportowe, jak wygląda jego model matematyczny, czym różni się zadanie zbilansowane od niezbilansowanego oraz na czym polegają najważniejsze etapy algorytmu transportowego: wyznaczanie początkowego rozwiązania bazowego i poprawianie go metodą potencjałów.

Spis treści

• Czym jest zagadnienie transportowe?
• Model matematyczny zadania transportowego
• Zadanie zbilansowane i niezbilansowane
• Bilansowanie zadania transportowego
• Rozwiązanie bazowe w zadaniu transportowym
• Metoda kąta północno-zachodniego
• Metoda minimalnego elementu macierzy
• Metoda VAM, czyli metoda Vogla
• Metoda potencjałów
• Wskaźniki optymalności
• Cykl poprawy rozwiązania
• Kiedy rozwiązanie jest optymalne?
• Najczęstsze błędy
• Podsumowanie

Czym jest zagadnienie transportowe?

Zagadnienie transportowe polega na ustaleniu takiego planu przewozów jednorodnego towaru od dostawców do odbiorców, aby spełnić ograniczenia podaży i popytu oraz zminimalizować łączny koszt transportu.

W klasycznym zadaniu transportowym występują:

• dostawcy, czyli miejsca, z których towar może zostać wysłany,
• odbiorcy, czyli miejsca, do których towar ma zostać dostarczony,
• podaż każdego dostawcy, czyli liczba jednostek towaru dostępna u danego dostawcy,
• popyt każdego odbiorcy, czyli liczba jednostek towaru potrzebna danemu odbiorcy,
• koszty jednostkowe transportu między każdą parą dostawca – odbiorca.

Przykładowo, dostawcami mogą być magazyny, fabryki albo bazy logistyczne, natomiast odbiorcami — sklepy, hurtownie, zakłady produkcyjne lub punkty dystrybucji. Towarem może być dowolne dobro jednorodne: paliwo, zboże, cement, piasek, energia, surowiec produkcyjny albo gotowy produkt.

Założenie o jednorodności towaru jest ważne. Oznacza ono, że każda jednostka przewożonego dobra jest traktowana tak samo. Nie rozróżniamy więc różnych gatunków, modeli, klas jakości ani terminów ważności. Jeżeli mamy kilka różnych produktów, to zwykle należy rozwiązać kilka osobnych zadań transportowych albo zbudować bardziej złożony model programowania liniowego.

Klasyczne zadanie transportowe zakłada również podzielność przewozów. Dostawca może więc wysłać część swojej podaży do jednego odbiorcy, część do drugiego, a pozostałą część do kolejnych odbiorców. Nie musimy wysyłać całego towaru od jednego dostawcy do jednego odbiorcy.

Model matematyczny zadania transportowego

Aby zapisać zagadnienie transportowe w postaci matematycznej, wprowadzamy następujące oznaczenia:

• \(m\) — liczba dostawców,
• \(n\) — liczba odbiorców,
• \(a_i\) — podaż \(i\)-tego dostawcy,
• \(b_j\) — popyt \(j\)-tego odbiorcy,
• \(c_{ij}\) — jednostkowy koszt przewozu od \(i\)-tego dostawcy do \(j\)-tego odbiorcy,
• \(x_{ij}\) — liczba jednostek towaru przewieziona od \(i\)-tego dostawcy do \(j\)-tego odbiorcy.

Zmiennymi decyzyjnymi są więc wielkości przewozów:

\[ x_{ij}, \quad i=1,2,\ldots,m, \quad j=1,2,\ldots,n. \]

Funkcja celu ma postać:

\[ \min Z = \sum_{i=1}^{m}\sum_{j=1}^{n} c_{ij}x_{ij}. \]

Oznacza to, że minimalizujemy całkowity koszt transportu. Każdy składnik \(c_{ij}x_{ij}\) oznacza koszt przewozu określonej liczby jednostek towaru na konkretnej trasie.

Oprócz funkcji celu występują ograniczenia dotyczące podaży i popytu. Każdy przewóz musi być również nieujemny:

\[ x_{ij} \geq 0. \]

W zależności od relacji między łączną podażą i łącznym popytem, ograniczenia mogą mieć nieco różną postać. Właśnie dlatego warto najpierw rozróżnić zadanie zbilansowane i niezbilansowane.

Zadanie zbilansowane i niezbilansowane

Zadanie transportowe nazywamy zbilansowanym, jeżeli suma podaży wszystkich dostawców jest równa sumie popytu wszystkich odbiorców:

\[ \sum_{i=1}^{m} a_i = \sum_{j=1}^{n} b_j. \]

W takim przypadku cała dostępna podaż zostanie rozdysponowana i cały popyt zostanie zaspokojony. Ograniczenia przyjmują wtedy postać równości.

Dla każdego dostawcy:

\[ \sum_{j=1}^{n} x_{ij} = a_i. \]

Dla każdego odbiorcy:

\[ \sum_{i=1}^{m} x_{ij} = b_j. \]

Inaczej wygląda sytuacja, gdy zadanie nie jest zbilansowane. Wtedy łączna podaż może być większa od łącznego popytu albo łączny popyt może być większy od łącznej podaży.

Gdy podaż jest większa od popytu

Jeżeli:

\[ \sum_{i=1}^{m} a_i > \sum_{j=1}^{n} b_j, \]

to dostawcy mają więcej towaru, niż potrzebują odbiorcy. Wtedy cały popyt powinien zostać zaspokojony, ale część podaży może pozostać niewykorzystana.

Dla odbiorców mamy więc równości:

\[ \sum_{i=1}^{m} x_{ij} = b_j, \]

natomiast dla dostawców nierówności:

\[ \sum_{j=1}^{n} x_{ij} \leq a_i. \]

Gdy popyt jest większy od podaży

Jeżeli:

\[ \sum_{i=1}^{m} a_i < \sum_{j=1}^{n} b_j, \]

to odbiorcy potrzebują więcej towaru, niż mogą dostarczyć dostawcy. W takiej sytuacji cała dostępna podaż powinna zostać wykorzystana, ale nie cały popyt może zostać zaspokojony.

Dla dostawców mamy więc równości:

\[ \sum_{j=1}^{n} x_{ij} = a_i, \]

natomiast dla odbiorców nierówności:

\[ \sum_{i=1}^{m} x_{ij} \leq b_j. \]

Można powiedzieć, że w zadaniu niezbilansowanym równości pojawiają się po stronie, która jest ograniczającym zasobem. Jeżeli brakuje podaży, cała podaż musi zostać wykorzystana. Jeżeli natomiast podaży jest za dużo, cały popyt musi zostać zaspokojony, ale część podaży może pozostać niewykorzystana.

Bilansowanie zadania transportowego

Klasyczny algorytm transportowy stosujemy do zadania zbilansowanego. Jeżeli zadanie nie jest zbilansowane, należy je najpierw sprowadzić do postaci zbilansowanej.

Robi się to przez dodanie fikcyjnego dostawcy albo fikcyjnego odbiorcy.

Fikcyjny odbiorca

Jeżeli łączna podaż jest większa od łącznego popytu, dodajemy fikcyjnego odbiorcę. Jego popyt jest równy nadwyżce podaży nad popytem:

\[ b_{n+1} = \sum_{i=1}^{m} a_i - \sum_{j=1}^{n} b_j. \]

Przewóz do fikcyjnego odbiorcy oznacza w praktyce niewykorzystaną część podaży. Jeżeli w treści zadania nie podano żadnych dodatkowych kosztów, jednostkowe koszty przewozu do fikcyjnego odbiorcy przyjmuje się zwykle jako zerowe:

\[ c_{i,n+1}=0. \]

Fikcyjny dostawca

Jeżeli łączny popyt jest większy od łącznej podaży, dodajemy fikcyjnego dostawcę. Jego podaż jest równa niedoborowi podaży:

\[ a_{m+1} = \sum_{j=1}^{n} b_j - \sum_{i=1}^{m} a_i. \]

Przewóz od fikcyjnego dostawcy oznacza niezaspokojoną część popytu. Jeżeli brak niezaspokojenia popytu nie jest karany, koszty w fikcyjnym wierszu również przyjmuje się jako zerowe:

\[ c_{m+1,j}=0. \]

Trzeba jednak zachować ostrożność. Jeżeli w treści zadania występują koszty magazynowania, kary za niezaspokojenie popytu, koszty utraconych korzyści albo inne dodatkowe koszty, to nie należy automatycznie wpisywać zer. Wtedy w komórkach fikcyjnego wiersza lub fikcyjnej kolumny powinny znaleźć się wartości wynikające z treści zadania.

Rozwiązanie bazowe w zadaniu transportowym

Po zbilansowaniu zadania można przystąpić do algorytmu transportowego. Składa się on z dwóch głównych etapów:

1. wyznaczenia początkowego rozwiązania bazowego dopuszczalnego,
2. poprawiania tego rozwiązania aż do uzyskania rozwiązania optymalnego.

Rozwiązanie dopuszczalne to taki plan przewozów, który spełnia wszystkie ograniczenia podaży i popytu. Nie musi być ono jednak najlepsze. Może być bardzo dalekie od optimum. Ważne jest tylko to, aby stanowiło punkt wyjścia do dalszych obliczeń.

W zadaniu transportowym o \(m\) dostawcach i \(n\) odbiorcach rozwiązanie bazowe powinno zawierać:

\[ m+n-1 \]

komórek bazowych.

Komórka bazowa to komórka tabeli transportowej, w której znajduje się przewóz dodatni albo przewóz równy zero, ale świadomie potraktowany jako element bazy. Ten drugi przypadek jest szczególnie ważny przy rozwiązaniach zdegenerowanych.

Degeneracja rozwiązania

Jeżeli liczba zajętych komórek jest mniejsza niż \(m+n-1\), mamy do czynienia z rozwiązaniem zdegenerowanym. Wtedy trzeba uzupełnić bazę, wpisując w odpowiednio dobranej pustej komórce przewóz równy zero.

Takie zero nie zmienia wartości funkcji celu ani rzeczywistego planu przewozów. Ma jednak znaczenie techniczne: pozwala zachować prawidłową strukturę bazy, wyznaczyć potencjały i przeprowadzić kolejne kroki algorytmu.

Komórki zerowej nie należy jednak wybierać całkowicie przypadkowo. Powinna ona zostać dodana tak, aby układ komórek bazowych umożliwiał wyznaczenie wszystkich potencjałów i nie tworzył zamkniętego cyklu już w samej bazie.

Praktycznie można kierować się zasadą, że nie powinniśmy doprowadzić do sytuacji, w której jakaś część tabeli zostanie „odłączona” od pozostałych komórek bazowych. Każdy wiersz i każda kolumna powinny być powiązane z resztą bazy tak, aby dało się przechodzić między komórkami bazowymi przez wspólne wiersze i kolumny.

Metoda kąta północno-zachodniego

Jedną z najprostszych metod wyznaczania początkowego rozwiązania bazowego jest metoda kąta północno-zachodniego. Nazwa pochodzi od sposobu poruszania się po tabeli transportowej. Zaczynamy od komórki położonej w lewym górnym rogu, czyli umownie w „północno-zachodnim” kącie tabeli.

W pierwszej komórce wpisujemy możliwie największy przewóz, czyli mniejszą z dwóch wartości: podaży danego dostawcy i popytu danego odbiorcy.

Jeżeli wyczerpie się podaż dostawcy, przechodzimy do następnego wiersza. Jeżeli zaspokoimy popyt odbiorcy, przechodzimy do następnej kolumny. Procedurę powtarzamy, aż cała tabela zostanie rozliczona.

Metoda ta jest bardzo prosta i szybka. Jej główną wadą jest jednak to, że całkowicie pomija koszty transportu. Oznacza to, że początkowe rozwiązanie bazowe może być bardzo dalekie od optymalnego.

W konsekwencji metoda potencjałów może później wymagać wielu iteracji, aby poprawić plan przewozów i dojść do optimum.

Uwaga na przechodzenie po przekątnej

W metodzie kąta północno-zachodniego szczególnie ostrożnie trzeba postępować wtedy, gdy w jednej komórce jednocześnie wyczerpuje się podaż danego dostawcy i zaspokaja popyt danego odbiorcy. Gdybyśmy w takiej sytuacji przeszli od razu po przekątnej do kolejnej komórki, moglibyśmy stracić jedną komórkę bazową.

W praktyce należy wtedy wprowadzić komórkę bazową z przewozem równym zero — obok albo pod spodem, zależnie od dalszego układu tabeli. Chodzi o to, aby liczba komórek bazowych wynosiła \(m+n-1\) i aby możliwe było późniejsze wyznaczenie potencjałów.

Metoda minimalnego elementu macierzy

Drugą popularną metodą wyznaczania początkowego rozwiązania bazowego jest metoda minimalnego elementu macierzy. W przeciwieństwie do metody kąta północno-zachodniego bierze ona pod uwagę koszty transportu.

W najprostszej wersji tej metody wybieramy komórkę o najmniejszym koszcie jednostkowym w całej tabeli. Następnie wpisujemy do niej możliwie największy przewóz, czyli minimum z dostępnej podaży danego dostawcy i niezaspokojonego popytu danego odbiorcy.

Po wpisaniu przewozu wykreślamy z dalszych rozważań zaspokojony wiersz albo zaspokojoną kolumnę. Następnie spośród pozostałych komórek ponownie wybieramy tę o najmniejszym koszcie i powtarzamy procedurę.

Metoda minimalnego elementu macierzy zwykle daje lepsze rozwiązanie początkowe niż metoda kąta północno-zachodniego, ponieważ od początku preferuje tańsze trasy przewozu. Nie gwarantuje jednak rozwiązania optymalnego. Nadal jest to tylko metoda wyznaczania rozwiązania startowego.

Dwie wersje metody minimalnego elementu

W praktyce można spotkać dwa podejścia określane czasem podobną nazwą. Pierwsze, najczęściej stosowane w klasycznych zadaniach transportowych, polega po prostu na wybieraniu najmniejszego dostępnego kosztu w tabeli.

Drugie podejście przypomina w pewnym stopniu ideę znaną z algorytmu węgierskiego. Najpierw przekształca się macierz kosztów, odejmując minima w wierszach i kolumnach, aby uzyskać zera, a następnie próbuje rozmieszczać przewozy w komórkach zerowych. W typowym kursie programowania liniowego częściej spotyka się jednak pierwszą, prostszą wersję metody minimalnego elementu.

Także w tej metodzie może wystąpić degeneracja. Dzieje się tak zwłaszcza wtedy, gdy w wyniku jednego przydziału jednocześnie wyczerpuje się podaż i zaspokaja popyt. W takiej sytuacji również należy zadbać o odpowiednią liczbę komórek bazowych.

Metoda VAM, czyli metoda Vogla

Bardziej zaawansowaną metodą wyznaczania początkowego rozwiązania bazowego jest metoda VAM, czyli metoda aproksymacyjna Vogla. Jej celem jest uzyskanie możliwie dobrego rozwiązania startowego, często lepszego niż w metodzie kąta północno-zachodniego i metodzie minimalnego elementu macierzy.

Metoda VAM opiera się na obliczaniu tzw. kar dla wierszy i kolumn. Kara jest różnicą między dwoma najmniejszymi kosztami w danym wierszu albo kolumnie.

Intuicja jest następująca: jeżeli w danym wierszu najtańsza trasa jest dużo tańsza od drugiej najtańszej, to niewykorzystanie tej najtańszej trasy może być kosztowne. Duża kara oznacza więc, że warto zwrócić uwagę na dany wiersz albo kolumnę.

Ogólny schemat metody VAM jest następujący:

1. Dla każdego niewykreślonego wiersza i każdej niewykreślonej kolumny obliczamy karę jako różnicę między dwoma najmniejszymi kosztami.
2. Wybieramy wiersz albo kolumnę o największej karze.
3. W wybranym wierszu lub kolumnie wybieramy komórkę o najmniejszym koszcie.
4. Wpisujemy tam możliwie największy przewóz.
5. Wykreślamy zaspokojony wiersz lub zaspokojoną kolumnę.
6. Powtarzamy procedurę aż do rozliczenia całej podaży i całego popytu.

Metoda VAM jest nieco bardziej pracochłonna od poprzednich metod, ale zwykle daje lepszy punkt startowy. Dzięki temu późniejsza metoda potencjałów może wymagać mniejszej liczby poprawek.

Metoda potencjałów

Gdy mamy już początkowe rozwiązanie bazowe dopuszczalne, należy sprawdzić, czy jest ono optymalne. Do tego służy metoda potencjałów.

Dla każdego wiersza tabeli wprowadzamy potencjał \(u_i\), a dla każdej kolumny potencjał \(v_j\). Potencjały wyznaczamy na podstawie komórek bazowych.

Dla każdej komórki bazowej musi być spełniona zależność:

\[ u_i + v_j = c_{ij}. \]

Oznacza to, że suma potencjału danego wiersza i potencjału danej kolumny ma być równa kosztowi jednostkowemu w komórce bazowej.

Ponieważ liczba potencjałów jest o jeden większa od liczby niezależnych równań, jeden potencjał można przyjąć dowolnie. Najczęściej przyjmuje się:

\[ u_1 = 0. \]

Następnie, korzystając z równań dla komórek bazowych, wyznacza się pozostałe potencjały.

Jeżeli nie da się wyznaczyć wszystkich potencjałów, jest to zwykle sygnał, że baza została zbudowana nieprawidłowo albo że występuje degeneracja, której nie uzupełniono odpowiednią komórką zerową.

Wskaźniki optymalności

Po wyznaczeniu potencjałów sprawdzamy komórki niebazowe, czyli te, w których aktualnie nie ma przewozu i które nie należą do bazy. Dla każdej takiej komórki obliczamy wskaźnik optymalności:

\[ \Delta_{ij} = c_{ij} - u_i - v_j. \]

W zadaniu minimalizacji interpretacja jest następująca:

• jeżeli wszystkie \(\Delta_{ij} \geq 0\), rozwiązanie jest optymalne,
• jeżeli istnieje przynajmniej jedno \(\Delta_{ij} < 0\), rozwiązanie można poprawić,
• im bardziej ujemny wskaźnik, tym większą poprawę kosztu jednostkowego może dać wprowadzenie tej komórki do bazy.

Wskaźnik optymalności informuje, o ile zmieni się wartość funkcji celu przy wprowadzeniu jednej jednostki przewozu do danej komórki niebazowej, oczywiście przy jednoczesnym odpowiednim skorygowaniu pozostałych przewozów w cyklu.

Jeżeli wskaźnik jest ujemny, oznacza to, że wprowadzenie przewozu w tej komórce pozwala obniżyć łączny koszt transportu. Taka komórka jest kandydatem do wejścia do bazy.

Jeżeli wskaźnik jest równy zero, wprowadzenie tej komórki do bazy nie zmieni wartości funkcji celu. Może to oznaczać istnienie alternatywnego rozwiązania optymalnego.

Cykl poprawy rozwiązania

Jeżeli rozwiązanie nie jest optymalne, wybieramy komórkę niebazową z ujemnym wskaźnikiem optymalności. Najczęściej wybiera się komórkę o najbardziej ujemnym wskaźniku, ponieważ daje ona największą potencjalną poprawę.

Wybrana komórka wchodzi do bazy. Następnie trzeba zbudować dla niej zamknięty cykl przechodzący przez komórki bazowe.

Cykl w zadaniu transportowym ma kilka ważnych cech:

• zaczyna się i kończy w komórce wchodzącej do bazy,
• przechodzi wyłącznie przez komórki bazowe oraz komórkę wchodzącą,
• porusza się tylko poziomo i pionowo, nigdy po skosie,
• w każdym narożniku cyklu zmieniamy kierunek ruchu,
• znaki w cyklu rozmieszcza się naprzemiennie: \(+\), \(-\), \(+\), \(-\).

Komórka wchodząca do bazy otrzymuje znak plus. Następnie w kolejnych narożnikach cyklu wpisuje się naprzemiennie minus, plus, minus i tak dalej.

Spośród komórek oznaczonych znakiem minus wybieramy najmniejszy przewóz. Oznaczmy go przez \(\theta\). Następnie:

• do komórek ze znakiem plus dodajemy \(\theta\),
• od komórek ze znakiem minus odejmujemy \(\theta\).

W ten sposób otrzymujemy nowe rozwiązanie bazowe dopuszczalne. Ograniczenia podaży i popytu pozostają spełnione, ponieważ w każdym wierszu i w każdej kolumnie cyklu jedna wartość jest zwiększana, a druga zmniejszana o tę samą wielkość.

Dla danej komórki wchodzącej, przy prawidłowej strukturze bazy, cykl jest wyznaczony jednoznacznie. W prostych przykładach obejmuje on cztery komórki, ale w większych zadaniach może być dłuższy i przechodzić przez większą liczbę wierszy oraz kolumn.

Kiedy rozwiązanie jest optymalne?

Rozwiązanie zadania transportowego jest optymalne, gdy dla wszystkich komórek niebazowych wskaźniki optymalności są nieujemne:

\[ \Delta_{ij} \geq 0. \]

Wtedy nie istnieje już żadna pusta komórka, której wprowadzenie do bazy mogłoby obniżyć całkowity koszt transportu.

Jeżeli wszystkie wskaźniki optymalności dla komórek niebazowych są dodatnie, rozwiązanie optymalne jest jednoznaczne.

Jeżeli natomiast przynajmniej jeden wskaźnik optymalności dla komórki niebazowej jest równy zero, zadanie może mieć więcej niż jedno rozwiązanie optymalne. Wprowadzenie takiej komórki do bazy prowadzi wtedy do innego planu przewozów, ale o tej samej wartości funkcji celu.

Warto zwrócić uwagę, że istnienie wielu rozwiązań optymalnych nie jest błędem. Oznacza jedynie, że ten sam minimalny koszt transportu można osiągnąć na kilka sposobów.

Przykład zadania transportowego krok po kroku

Rozważmy zadanie transportowe z trzema dostawcami i trzema odbiorcami. W tabeli podano jednostkowe koszty przewozu \(c_{ij}\), podaż dostawców oraz popyt odbiorców.

Rozwiązanie początkowe metodą kąta północno-zachodniego

Zaczynamy od komórki \(D_1O_1\), czyli od lewego górnego rogu tabeli. Możemy tam wpisać:

\[ x_{11}=\min(40,40)=40. \]

W tym momencie jednocześnie wyczerpuje się podaż dostawcy \(D_1\) i zostaje zaspokojony popyt odbiorcy \(O_1\). Gdybyśmy mechanicznie przeszli po przekątnej do komórki \(D_2O_2\), otrzymalibyśmy za mało komórek bazowych. Dlatego wprowadzamy komórkę bazową z przewozem równym zero, na przykład \(x_{12}=0\).

Otrzymaliśmy rozwiązanie dopuszczalne, ale niekoniecznie optymalne. Metoda kąta północno-zachodniego nie bierze bowiem pod uwagę kosztów przewozu. Sprawdzimy więc rozwiązanie metodą potencjałów.

Pierwsze badanie optymalności metodą potencjałów

Dla komórek bazowych wyznaczamy potencjały z zależności:

\[ u_i+v_j=c_{ij}. \]

Przyjmujemy \(u_1=0\). Otrzymujemy:

\[ u_1=0,\quad u_2=7,\quad u_3=14, \]

\[ v_1=1,\quad v_2=4,\quad v_3=-3. \]

Dla komórek niebazowych obliczamy wskaźniki optymalności:

\[ \Delta_{ij}=c_{ij}-u_i-v_j. \]

Pierwszy cykl poprawy rozwiązania

Dla komórki \(D_3O_2\) budujemy cykl:

\[ (D_3,O_2)\to(D_2,O_2)\to(D_2,O_3)\to(D_3,O_3)\to(D_3,O_2). \]

Komórka wchodząca otrzymuje znak plus, a kolejne narożniki cyklu oznaczamy naprzemiennie znakami minus i plus.

Po wykonaniu przesunięcia dodajemy \(\theta=30\) w komórkach oznaczonych plusem i odejmujemy \(\theta=30\) w komórkach oznaczonych minusem.

Drugie badanie optymalności

Po pierwszej korekcie ponownie wyznaczamy potencjały. Dla aktualnej bazy otrzymujemy:

\[ u_1=0,\quad u_2=-10,\quad u_3=-3, \]

\[ v_1=1,\quad v_2=4,\quad v_3=14. \]

Drugi cykl poprawy — przypadek zdegenerowany

Dla komórki \(D_1O_3\) budujemy cykl:

\[ (D_1,O_3)\to(D_3,O_3)\to(D_3,O_2)\to(D_1,O_2)\to(D_1,O_3). \]

Po tej operacji wartości przewozów pozostają takie same, ale do bazy wchodzi komórka \(D_1O_3\), natomiast komórka \(D_3O_3\) przestaje być bazowa.

Końcowe badanie optymalności

Dla nowej bazy ponownie wyznaczamy potencjały. Przyjmując \(u_1=0\), otrzymujemy:

\[ u_1=0,\quad u_2=3,\quad u_3=-3, \]

\[ v_1=1,\quad v_2=4,\quad v_3=1. \]

Ostateczny plan przewozów jest następujący:

Porównanie z metodą minimalnego elementu macierzy

To samo zadanie można rozpocząć metodą minimalnego elementu macierzy. Metoda ta uwzględnia koszty już na etapie budowania rozwiązania początkowego, dlatego w tym przykładzie daje znacznie lepszy punkt startowy.

Najtańsze trasy mają koszt równy \(1\). Możemy więc najpierw przydzielić przewozy na trasach \(D_1O_1\) oraz \(D_3O_2\), a następnie pozostały popyt odbiorcy \(O_3\) zaspokoić dostawą od \(D_2\).

W tym przykładzie metoda minimalnego elementu macierzy od razu prowadzi do rozwiązania optymalnego. Nie oznacza to, że dzieje się tak zawsze. Pokazuje jednak ważną różnicę między metodami znajdowania rozwiązania początkowego. Metoda kąta północno-zachodniego jest bardzo prosta, ale całkowicie ignoruje koszty transportu. Metoda minimalnego elementu macierzy uwzględnia koszty i dlatego często pozwala rozpocząć obliczenia od znacznie lepszego rozwiązania.

W naszym przykładzie metoda kąta północno-zachodniego dała na starcie koszt:

\[ Z=780, \]

natomiast metoda minimalnego elementu macierzy od razu pozwoliła uzyskać:

\[ Z=270. \]

Dlatego w praktyce metoda minimalnego elementu macierzy, a jeszcze częściej metoda VAM, może znacząco skrócić dalsze poprawianie rozwiązania metodą potencjałów.

Najczęstsze błędy przy rozwiązywaniu zadań transportowych

Podczas rozwiązywania zadań transportowych często pojawiają się błędy rachunkowe i metodyczne. Do najczęstszych należą:

• brak sprawdzenia, czy zadanie jest zbilansowane,
• błędne dodanie fikcyjnego dostawcy albo fikcyjnego odbiorcy,
• automatyczne wpisanie zerowych kosztów tam, gdzie w treści zadania występują koszty magazynowania albo kary,
• zbyt mała liczba komórek bazowych,
• pominięcie komórki zerowej przy degeneracji,
• przejście po przekątnej w metodzie kąta północno-zachodniego,
• błędne wyznaczenie potencjałów,
• obliczanie wskaźników optymalności ze złym znakiem,
• tworzenie cyklu po skosie,
• wybór niewłaściwej wartości \(\theta\),
• niezauważenie alternatywnego rozwiązania optymalnego.

Najbardziej niebezpieczne są zwykle błędy związane z degeneracją. Jeżeli baza ma za mało komórek, metoda potencjałów może się „rozpaść” — nie uda się wyznaczyć wszystkich potencjałów albo cykl poprawy rozwiązania nie będzie możliwy do prawidłowego zbudowania.

Podsumowanie

Zagadnienie transportowe jest szczególnym przypadkiem zadania programowania liniowego. Można je rozwiązać ogólną metodą simpleks, ale ze względu na specyficzną strukturę problemu znacznie wygodniej stosować algorytm transportowy.

W klasycznym zadaniu transportowym mamy dostawców, odbiorców, podaż, popyt oraz jednostkowe koszty przewozu. Celem jest znalezienie takiego planu transportu, który spełnia ograniczenia podaży i popytu oraz minimalizuje całkowity koszt.

Przed zastosowaniem algorytmu transportowego zadanie powinno zostać zbilansowane. Jeżeli łączna podaż nie jest równa łącznemu popytowi, dodaje się fikcyjnego dostawcę albo fikcyjnego odbiorcę.

Sam algorytm transportowy składa się z dwóch głównych części. Najpierw wyznacza się początkowe rozwiązanie bazowe, na przykład metodą kąta północno-zachodniego, metodą minimalnego elementu macierzy albo metodą VAM. Następnie rozwiązanie to jest sprawdzane i poprawiane metodą potencjałów.

Rozwiązanie jest optymalne, gdy wszystkie wskaźniki optymalności dla komórek niebazowych są nieujemne. Jeżeli pojawia się wskaźnik ujemny, można zbudować cykl poprawy rozwiązania i obniżyć całkowity koszt transportu.

Metoda transportowa jest dobrym przykładem tego, że w matematyce stosowanej i badaniach operacyjnych sama znajomość ogólnych algorytmów nie zawsze wystarcza. W wielu sytuacjach warto korzystać z metod wyspecjalizowanych, które wykorzystują strukturę konkretnego problemu i dzięki temu prowadzą do rozwiązania w sposób prostszy, bardziej przejrzysty i często szybszy obliczeniowo.

Utworzono: 20.05.2026

Powiązane artykuły

• Programowanie liniowe – metoda graficzna 
• Metoda simpleks — algorytm rozwiązywania zadań programowania liniowego 
• Dualność w programowaniu liniowym — zadanie prymalne, zadanie dualne i warunki komplementarności 

Masz problem z tym tematem?

Wszechwiedza.pl pomaga zrozumieć matematykę, statystykę, ekonometrię, badania operacyjne, analizę danych, mechanikę i wiele innych przedmiotów — spokojnie, konkretnie i krok po kroku. 

Zapytaj o pomoc