Najpierw sprawdzamy czy zadanie jest zbilansowane. Suma zdolności produkcyjnych wynosi
3·900=2700 ton, a suma zapotrzebowań to 500+600+700+800=2600 ton. Liczby te są różne,
więc zadanie jest niezbilansowane. Dodajemy więc piątego odbiorcę – niewykorzystane moce
produkcyjne (NM). Musi do niego trafić 100 ton (bo o tyle zdolności produkcyjne są większe od
zapotrzebowań). Tworzymy macierz kosztów. Dla odbiorców S1-S4 koszty to koszt
wyprodukowania + koszt transportu, dla niewykorzystanych mocy koszt to 0 (bo nic nie
produkujemy). Czyli macierz kosztów wygląda tak:
S1
S2
S3
S4
NM
Produkcja
C1
113
113
111
110
0
900
C2
108
104
102
103
0
900
C3
114
117
116
114
0
900
Zapotrz.
500
600
700
800
100
Zaczynamy od wyznaczenia jakiegoś rozwiązania startowego. Może być ono zupełnie dowolne,
ale im lepsze będzie tym mniej liczenia potem, więc staramy się jak najbardziej korzystać z
tych komórek, w których są małe koszty (tutaj będą to koszty 0, 102, 103, 104...) A więc
może to wyglądać np. tak:
S1
S2
S3
S4
NM
Produkcja
C1
300
600
900
C2
700
200
900
C3
500
300
100
900
Zapotrz.
500
600
700
800
100
Sprawdzamy czy to odgadnięte rozwiązanie jest optymalne. W tym celu tworzymy sobie tabelę
z tzw. potencjałami. Zaczynamy od nadania potencjału 0 któremuś (np. pierwszemu)
wierszowi:
0
Potencjał komórki, to suma potencjałów wiersza i kolumny, w której ona leży minus jej koszt
(czyli liczba z pierwszej tabelki). Chcemy tak nadać potencjały wierszom i kolumnom, aby
komórki, w których mamy w naszym odgadniętym rozwiązaniu jakieś liczby miały potencjały
równe zero.
Np. chcemy mieć potencjał 0 w komórce odpowiadającej za C1-S2 (druga komórka w
pierwszym rzędzie), więc potencjał drugiej kolumny musi być równy 113. Wtedy bowiem
potencjał komórki to 0+113-113=0 (potencjał wiersza+potencjał kolumny-koszt komórki):
113
0
0+113-113=0
Kolejna komórka do wyzerowania potencjału to C1-S4. Potencjał czwartej kolumny musi być
więc równy 110:
113
110
0
0+113-113=0
0+110-110=0
Teraz np. komórka C2-S4. Potencjał drugiego wiersza musi być równy -17:
113
110
0
0+113-113=0
0+110-110=0
-7
-7+110-103=0
I tak dalej, aż wyzerujemy wszystkie potencjały w komórkach, w których mamy jakieś liczby w
naszym odgadniętym rozwiązaniu:
110
113
109
110
-4
0
0
0
-7
0
0
4
0
0
0
Doliczamy teraz potencjały do pozostałych komórek, cały czas stosując wzór
potencjał=potencjał wiersza + potencjał komórki – koszt komórki
i mamy ostateczną tabelkę z potencjałami:
110
113
109
110
-4
0
-3
0
-2
0
-4
-7
-5
2
0
0
-11
4
0
0
-3
0
0
Rozwiązanie jest optymalne, jeśli w tabelce z potencjałami nie ma liczb dodatnich. U nas jest
taka liczba, więc nasze zgadnięte rozwiązanie można poprawić.
Aby poprawić rozwiązanie bierzemy komórkę z największą liczbą w tabeli z potencjałami (czyli
komórkę C2-S2, bo tam jest 2) i znajdujemy cykl zawierający tą komórkę oraz same zera.
Przez cykl rozumiemy łamaną zamkniętą (np. prostokąt). Tutaj taki cykl łatwo znaleźć:
110
113
109
110
-4
0
-3
0
-2
0
-4
-7
-5
2
0
0
-11
4
0
0
-3
0
0
Taki sam cykl rysujemy sobie na naszym zgadniętym rozwiązaniu i oznaczamy kolejne
wierzchołki tego cyklu na zmianę plusami i minusami (zaczynając od + w komórce, którą nam
wskazały potencjały czyli w C2-S2:
S1
S2
S3
S4
NM
Produkcja
C1
300 -
600 +
900
C2
+
700
200 -
900
C3
500
300
100
900
Zapotrz.
500
600
700
800
100
Bierzemy teraz najmniejszą liczbę w komórkach z minusami (czyli 200) i dodajemy ją do
komórek z plusami, a odejmujemy od komórek z minusami i to jest nasze nowe rozwiązanie:
S1
S2
S3
S4
NM
Produkcja
C1
100
800
900
C2
200
700
900
C3
500
300
100
900
Zapotrz.
500
600
700
800
100
I znów musimy, za pomocą potencjałów sprawdzić, czy jest ono optymalne, a więc budujemy
tabelkę z potencjałami, zupełnie identycznie, jak do rozwiązania odgadniętego. Wychodzi taka:
110
113
111
110
-4
0
-3
0
0
0
-4
-9
-7
0
0
-2
-13
4
0
0
-1
0
0
Jak widać, tu już nie ma liczb dodatnich, a więc rozwiązanie jest optymalne.
Możemy wyliczyć jego koszt mnożąc liczby z tabelki z rozwiązaniem przez liczby z tabeli
kosztów (pierwsza tabela w tym rozwiązaniu):
K=100·113+800·110+200·104+700·102+500·114+300·117+100·0=283600.
Jeśli za kryterium przyjmiemy tylko koszty transportu, to macierz kosztów jest taka jak w
zadaniu (bo nie dodajemy kosztów produkcji) :
S1
S2
S3
S4
NM
Produkcja
C1
8
8
6
5
0
900
C2
8
4
2
3
0
900
C3
4
7
6
4
0
900
Zapotrz.
500
600
700
800
100
Nasze rozwiązanie optymalne dla zadania z kosztami produkcji ma koszt
K=100·8+800·5+200·4+700·2+500·4+300·7+100·0=11100.
Popatrzmy np. na takie rozwiązanie:
S1
S2
S3
S4
NM
Produkcja
C1
800
100
900
C2
200
700
900
C3
500
400
900
Zapotrz.
500
600
700
800
100
Koszt takiego rozwiązania wynosi: K=11000 (wyliczony, tak jak wyżej, mnożąc liczby z
powyższej tabelki przez liczby z tabeli kosztów), a więc jest niższy niż koszt rozwiązania
optymalnego z uwzględnieniem kosztów produkcji. Stąd wniosek, że jeśli nie bierzemy pod
uwagę kosztów produkcji, to rozwiązanie optymalne można jeszcze poprawić. A więc
rozwiązanie optymalne bez kosztów produkcji jest inne niż z tymi kosztami. (Zadanie nie każe
wyliczać rozwiązania optymalnego bez kosztów produkcji, więc tego nie robimy).