Najpierw sprawdzamy czy zadanie jest zbilansowane. Suma dostaw wynosi
1200+800+1200=3200 kg, a suma zapotrzebowań to 700+700+1000+800=3200 ton. Liczby
te są równe, więc zadanie jest zbilansowane. Nie musimy dodawać magazynu. Czyli macierz
kosztów wygląda tak:
P1
P2
P3
P4
Dostawy
G1
6
1
3
3
1200
G2
4
3
5
2
800
G3
3
2
4
5
1200
Zapotrz.
700
700
1000
800
Zróbmy to zadanie metodą elementu minimalnego macierzy.
Od każdej liczby z wiersza pierwszego odejmujemy najmniejszy koszt w wierszu pierwszym
(czyli 1). I podobnie w wierszu drugim (odejmujemy najmniejszy koszt z wiersza drugiego,
czyli 2) i w trzecim (odejmujemy 2):
P1
P2
P3
P4
Dostawy
G1
5
0
2
2
1200
G2
2
1
3
0
800
G3
1
0
2
3
1200
Zapotrz.
700
700
1000
800
Teraz robimy to samo z kolumnami: od każdej liczby z pierwszej kolumny odejmujemy najmniejszy koszt w tej kolumnie (czyli 1). W drugiej kolumnie odejmujemy 0, w trzeciej 2, a
w czwartej 0:
P1
P2
P3
P4
Dostawy
G1
4
0
0
2
1200
G2
1
1
1
0
800
G3
0
0
0
3
1200
Zapotrz.
700
700
1000
800
Teraz robimy sobie pustą tabelkę, w której zaznaczamy (np. na zielono) pola, w których przed
chwilą otrzymaliśmy zera:
P1
P2
P3
P4
Dostawy
G1
1200
G2
800
G3
1200
Zapotrz.
700
700
1000
800
i staramy się rozłożyć nasze dostawy tylko w zielonych komórkach. Widać więc, ze w G2-P4
musi być 800, a w G3-P1 musi być 700. Resztę możemy rozłożyć tak:
P1
P2
P3
P4
Dostawy
G1
700
500
1200
G2
800
800
G3
700
0
500
1200
Zapotrz.
700
700
1000
800
Jeśli nam się to uda (powyżej się udało), to jest to rozwiązanie optymalne. Jeśli się nie uda, to trzeba robić zadanie algorytmem transportowym (tak jak np. zadanie poniżej).
Zadanie 2
Najpierw sprawdzamy czy zadanie jest zbilansowane. Suma dostaw wynosi 100+250+50=400
ton, a suma przyjęć w punktach skupu to 150+100+150=400 ton. Liczby te są równe, więc zadanie jest zbilansowane. Nie musimy dodawać magazynu. Czyli macierz kosztów wygląda
tak:
S1
S2
S3
Dostawy
C1
50
100
100
100
C2
150
200
50
250
C3
20
100
20
50
Przyjęcia
150
100
150
To zadanie nie da się zrobić metodą elementu minimalnego macierzy (nie uda się rozmieścić
wszystkich dostaw w zielonych komórkach), a więc stosujemy algorytm transportowy.
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, 50, 100...) A więc może to
wyglądać np. tak:
S1
S2
S3
Dostawy
C1
50
100
C2
100
150
250
C3
50
50
50
Przyjęcia
150
100
150
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 100. Wtedy bowiem potencjał komórki to 0+100-100=0 (potencjał wiersza+potencjał kolumny-koszt komórki):
100
0
0+100-100=0
Kolejna komórka do wyzerowania potencjału to np. C3-S2. Potencjał trzeciego wiersza musi
być więc równy 0:
100
0
0+100-100=0
0
0+100-100=0
Teraz np. komórka C3-S1. Potencjał pierwszej kolumny musi być równy 20:
100
0
0+100-100=0
0
0+20-20=0
0+100-100=0
I tak dalej, aż wyzerujemy wszystkie potencjały w komórkach, w których mamy jakieś liczby w
naszym odgadniętym rozwiązaniu:
20
100
-80
0
0
130
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:
20
100
-80
0
-30
0
-180
130
0
30
0
0
0
0
-100
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 30) 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źć:
20
100
-80
0
-30
0
-180
130
0
30
0
0
0
0
-100
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
Dostawy
C1
50
100
C2
100 -
+
150
250
C3
50 +
50 -
50
Przyjęcia
150
100
150
Bierzemy teraz najmniejszą liczbę w komórkach z minusami (czyli 50) 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
Dostawy
C1
50
100
C2
50
50
150
250
C3
100
50
Przyjęcia
150
100
150
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:
100
-50
0
0
0
-150
100
0
0
0
-30
0
-30
-100
Jak widać, tu już nie ma liczb dodatnich, a więc rozwiązanie jest optymalne.
Możemy wyliczyć jego koszt (czyli koszt minimalny) mnożąc liczby z tabelki z rozwiązaniem
przez liczby z tabeli kosztów (pierwsza tabela w tym rozwiązaniu):
K=50·100+50·150+50·200+150·50+100·20=5000+7500+10000+7500+2000=32000.