Najpierw sprawdzamy czy zadanie jest zbilansowane. Suma dostaw wynosi 100+50+80=230
ton, a suma odbiorów to 40+70+30+50=190 ton. Liczby te są różne, więc zadanie jest niezbilansowane. Dodajemy więc piątego odbiorcę – magazyn. Musi do niego trafić 40 ton (bo
o tyle dostawy są większe od odbiorów). Dla magazynu zamiast kosztów transportu mamy
koszt magazynowania. Czyli tabela z kosztami, dostawami i obiorami wygląda tak:
S1
S2
S3
S4
Mag.
Dostawy
H1
90
140
150
130
20
100
H2
70
150
80
30
25
50
H3
50
30
100
120
20
80
Odbiory
40
70
30
50
40
Wiemy, że H1 ma dostarczyć do S1 30 ton, a więc od dostaw z H1 i odbiorów w S1 możemy
sobie odjąć te 30 ton (bo wiemy, gdzie trafią i nie musimy się nimi zajmować w zadaniu).
Podobnie z 35 tonami z H1 do S1, 10 tonami z H1 do S3 i 10 tonami z H2 do S3. Dodatkowo,
nie możemy mieć żadnych dodatkowych dostaw z H2 do S2 (bo tam ma być dokładnie 35 ton)
i z H2 do S3. Zaznaczymy to sobie na czerwono, żeby nie zapomnieć. A więc nasza tabelka z
dostawami i odbiorami, które mamy zoptymalizować ma postać:
S1
S2
S3
S4
Mag.
Dostawy
H1
90
140
150
130
20
25
H2
70
150
80
30
25
40
H3
50
30
100
120
20
80
Odbiory
10
35
10
50
40
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 20, 25, 30, 50..) A więc może to wyglądać np. tak:
S1
S2
S3
S4
Mag.
Dostawy
H1
10
15
25
H2
40
40
H3
10
35
10
25
80
Odbiory
10
35
10
50
40
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 H1-Mag (prawy górny róg), więc
potencjał ostatniej kolumny musi być równy 20. Wtedy bowiem potencjał komórki to 0+20-
20=0 (potencjał wiersza+potencjał kolumny-koszt komórki):
0
0+20-20=0
Kolejna komórka do wyzerowania potencjału to H1-S4. Potencjał czwartej kolumny musi być
więc równy 130:
130
20
0
0+130-130=0
0+20-20=0
Teraz np. komórka H2-S4. Potencjał drugiego wiersza musi być równy -100:
130
20
0
0+130-130=0
0+20-20=0
-100
-100+130-30=0
I tak dalej, aż wyzerujemy wszystkie potencjały w komórkach, w których mamy jakieś liczby w
naszym odgadniętym rozwiązaniu:
50
30
100
130
20
0
0
0
-100
0
0
0
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:
50
30
100
130
20
0
-40
-110
-50
0
0
-100
-120
-220
-80
0
-105
0
0
0
0
10
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ę H3-S4, bo tam jest 10) 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źć:
50
30
100
130
20
0
-40
-110
-50
0
0
-100
-120
-220
-80
0
-105
0
0
0
0
10
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 H3-S4:
S2
S3
S4
Mag.
Dostawy
H1
10 -
15 +
25
H2
40
40
H3
10
35
10
+
25 -
80
Odbiory
10
35
10
50
40
Bierzemy teraz najmniejszą liczbę w komórkach z minusami (czyli 10) 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
Mag.
Dostawy
H1
25
25
H2
40
40
H3
10
35
10
10
15
80
Odbiory
10
35
10
50
40
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: 50
30
100
120
20
0
-40
-110
-50
-10
0
-90
-110
-210
-70
0
-95
0
0
0
0
0
0
Jak widać, tu już nie ma liczb dodatnich, a więc rozwiązanie jest optymalne.
Dorzucamy do niego, warunki, które odjęliśmy na początku: 30 ton z H1 do S1, 35 t z H1 do
S2 i po 10 t z H1 i z H2 do S3 i to jest nasze ostateczne rozwiązanie.
S1
S2
S3
S4
Mag.
H1
30
35
10
25
H2
10
40
H3
10
35
10
10
15
Możemy wyliczyć jego koszt mnożąc liczby z powyższej tabelki przez liczby z tabeli kosztów
(pierwsza tabela w tym rozwiązaniu):
K=30·90+35·140+10·150+25·20+10·80+40·30+10·50+35·30+10·100+10·120+15·20=
2700+4900+1500+500+800+1200+500+1050+1000+1200+300=15650.
Jeśli pominiemy umowy, rozwiązanie optymalne się zmieni. Popatrzmy np. na takie
rozwiązanie:
S1
S2
S3
S4
Mag.
Dostawy
H1
40
0
0
20
40
100
H2
0
0
20
30
0
50
H3
0
70
10
0
0
80
Odbiory
40
70
30
50
40
Koszt takiego rozwiązania wynosi: K=12600 (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 uwzględniającego umowy. Stąd wniosek, że jeśli nie uwzględnimy umów, to rozwiązanie optymalne z umowami można jeszcze poprawić. A więc rozwiązanie optymalne bez
umów jest inne niż z umowami. (Zadanie nie każe wyliczać rozwiązania optymalnego bez umów, więc tego nie robimy).