Metoda kąta
północno-
zachodniego
NW
plm
Metoda kąta
północno-
zachodniego
NW
plm
Tabela kosztów
jednostkowych
2
6
3
4
8
D
1
1
5
6
9
7
D
2
3
4
1
6
10
D
3
O
1
O
2
O
3
O
4
O
5
do
sta
w
cy
od
bio
rcy
Tabela danych.
2
6
3
4
8
D
1
30
1
5
6
9
7
D
2
35
3
4
1
6
10
D
3
40
O
1
O
2
O
3
O
4
O
5
20
34
16
10
25
20
30
0
35
0
40
20
34
16
10
25
0
10
min(10,34)=10
20
10
30
0
35
0
40
20
34
16
10
25
0
10
min(10,34)=10
20
10
0
0
0
30
0
35
0
40
20
34
16
10
25
0
10 0
24
min(24,35)=24
20
10
0
0
0
30
0
24
35
0
0
40
20
34
16
10
25
0
10 0
24
11
0
min(11,16)=11
20
10
0
0
0
30
0
24
11
0
0
35
0
0
5
40
20
34
16
10
25
0
10 0
24
11 0
0
5
min(5,40)=5
20
10
0
0
0
30
0
24
11
0
0
35
0
0
5
40
20
34
16
10
25
0
10 0
24
11 0
0
5
0
35
min(10,35)=5
20
10
0
0
0
30
0
24
11
0
0
35
0
0
5
10
40
20
34
16
10
25
0
10 0
24
11 0
0
5
0
35
0
25
min(25,25)=25
Wartość podaży i popytu dla ostatniego elementu
zawsze powinna być taka sama.
20
10
0
0
0
30
0
24
11
0
0
35
0
0
5
10
25
40
20
34
16
10
25
0
10 0
24
11 0
0
5
0
35
0
25
0
0
20
10
0
0
0
0
0
24
11
0
0
0
0
0
5
10
25
0
0
0
0
0
0
W
ten
sposób
uzyskaliśmy
rozwiązanie
dopuszczalne.
Wszystkie
zerowe
elementy
rozwiązania nazywamy
elementami niebazowymi
.
Natomiast
elementami
bazowymi
nazywamy
wszystkie elementy niezerowe. Przy czym el.
bazowych powinno być m+n-1 (5+3-1=7), wówczas
rozwiązanie nazywamy
zdegenerowanym.
elementy bazowe
elementy niebazowe
Rozwiązanie
Koszty
Rozwiązanie
dopuszczalne
2
6
3
4
8
1
5
6
9
7
3
4
1
6
10
20
10
0
0
0
0
24
11
0
0
0
0
5
10 25
2·20+6·10+5·24+6·11+1·5+6·10+10·2
5 =
601
Przystępujemy do sprawdzenia czy
nasze
rozwiązanie dopuszczalne
jest
optymalnym
. Posłużymy się w tym
celu
metodą
potencjałów.
2
6
U
1
=0
5
6
1
6
10
ustawiamy
U
1
=0
potencjały U
potencjały V
koszty (tylko w miejscach
baz)
Mamy na wejście ustawioną wartość potencjału U
1
= 0,
więc szukamy w wierszu odpowiadającym temu U
1
(czyli w
pierwszym wierszu) kosztu - jest nim koszt = 2 w pierwszej
komórce. Następnie w potencjał V odpowiadający
znalezionemu kosztowi (czyli V
1
) wpisujemy wartość równą
różnicy kosztu i potencjału U
1
(V
1
=2-0=2).
2
6
U
1
=0
5
6
1
6
10
V
1
=2
V
1
=2-0
2
6
U
1
=0
5
6
1
6
10
V
1
=2 V
2
=6
V
2
=6-0
2
6
U
1
=0
5
6
U
2
=-1
1
6
10
V
1
=2 V
2
=6
U
2
=5-6
2
6
U
1
=0
5
6
U
2
=-1
1
6
10
V
1
=2 V
2
=6 V
3
=7
V
3
=6-(-
1)
2
6
U
1
=0
5
6
U
2
=-1
1
6
10
U
3
=-6
V
1
=2 V
2
=6 V
3
=7
U
3
=1-7
2
6
U
1
=0
5
6
U
2
=-1
1
6
10
U
3
=-6
V
1
=2 V
2
=6 V
3
=7 V
3
=1
2
V
3
=6-(-
6)
2
6
U
1
=0
5
6
U
2
=-1
1
6
10
U
3
=-6
V
1
=2 V
2
=6 V
3
=7 V
5
=1
2
V
5
=1
6
V
4
=10-(-6)
2
6
U
1
=0
5
6
U
2
=-1
1
6
10
U
3
=-6
V
1
=2 V
2
=6 V
3
=7 V
4
=1
2
V
5
=1
6
Tabela przedstawiająca
wyliczone potencjały U i V.
2
6
7+0=7
0+12=12 0+16=16
U
1
=0
2+(-1)=1
5
6
12+(-
1)=11
16+(-
1)=15
U
2
=-1
2+(-6)=-
4
6+(-6)=0
1
6
10
U
3
=-6
V
1
=2 V
2
=6 V
3
=7 V
5
=1
2
V
5
=1
6
Kolejnym krokiem jest wyliczenie
kosztów
pośrednich
.
Należy pozostałe (puste) komórki tabelki z
wynikami wypełnić sumami potencjału Vi i Uj
Następnie
wyliczamy
wskaźniki
optymalności.
W tym celu zestawmy obok siebie dwie tabelki:
tabelkę obliczonych przed chwilą kosztów
pośrednich i tabelkę kosztów z początku zadania
2
6
3
4
8
30
1
5
6
9
7
35
3
4
1
6
10
40
20
34
16
10
25
2
6
7
12
16
U
1
=0
1
5
6
11
15
U
2
=-
1
-4
0
1
6
10
U
3
=-
6
V
1
=2 V
2
=6 V
3
=7 V
4
=1
2
V
5
=1
6
koszty
pośrednie
koszty
Wskaźniki optymalności wyliczamy
odejmując od kosztów pośrednich
koszty.
2-2=0
6-6=0
7-3=4
12-4=8
16-8=8
U
1
=0
1-1=0
5-5=0
6-6=0
11-9=2
15-7=8
U
2
=-1
-4-3=-7
0-4=-4
1-1=0
6-6=0
10-
10=0
U
3
=-6
V
1
=2
V
2
=6
V
3
=7 V
4
=12 V
5
=16
0
0
4
8
8
U
1
=0
0
0
0
2
8
U
2
=-1
-7
-4
0
0
0
U
3
=-6
V
1
=2
V
2
=6
V
3
=7 V
4
=12 V
5
=16
wskaźniki optymalizacji
Jeżeli wśród wskaźników optymalności znajdują
się liczby dodatnie wówczas rozwiązanie nie jest
rozwiązaniem optymalnym. Rozwiązanie jest
więc optymalne kiedy wszystkie liczby są
niedodatnie.
Następnym etapem jest więc budowa cyklu w
celu uzyskania rozwiązania dopuszczalnego o
niższym koszcie a w rezultacie
rozwiązania
optymalnego.
Cykl składa się zawsze z
półcyklu
dodatniego
i
półcyklu ujemnego.
Aby stworzyć cykl trzeba mieć rozwiązanie dopuszczalne, które
będziemy "polepszać" sprawdzone uprzednio metodą potencjałów.
Niezbędna jest nam tabelka wskaźników optymalności z metody
potencjałów. Wśród wskaźników szukamy
największej wartości na
plusie.
0
0
4
8
8
U
1
=0
0
0
0
2
8
U
2
=-1
-7
-4
0
0
0
U
3
=-6
V
1
=2
V
2
=6
V
3
=7
V
3
=12 V
4
=16
Potrzebujemy tabelkę z rozwiązaniem dopuszczalnym
uzyskanym metodą NW, na którą będziemy nanosić
cykl,
Zaznaczamy w tabelce znaczkiem "+" pierwszy element
cyklu dodatniego, który zawsze znajduje się w miejscu
odpowiadającym
największemu
dodatniemu
wskaźnikowi w tabelce wskaźników. Oznacza to, że w to
miejsce opłaca się przenieść towar z innych elementów
bazowych.
20
10
0
0+
0
0
0
24
11
0
0
0
0
0
5
10
25
0
0
0
0
0
0
20
10
0
0+
0
0
0
24
11
0
0
0
0
0
5
10-
25
0
0
0
0
0
0
Mamy już element półcyklu dodatniego więc należy teraz
stworzyć element półcyklu ujemnego. Szukamy w
kolumnie, w której stoimy elementu bazowego, takiego
który z kolei będzie miał element bazowy w wierszu . Jest
nim element o wartości 10 - zaznaczamy go znaczkiem "-"
20
10
0
0+
0
0
0
24
11
0
0
0
0
0
5+
10-
25
0
0
0
0
0
0
Mając element półcyklu ujemnego tworzymy kolejny
element półcyklu dodatniego. Stoimy na komórce
stworzonego elementu półcyklu ujemnego. Szukamy w
wierszu, w której stoimy elementu bazowego, który
jednocześnie ma element bazowy w kolumnie. Jest nim
element o wartości 5 - zaznaczamy go znaczkiem "+"
20
10
0
0+
0
0
0
24
11-
0
0
0
0
0
5+
10-
25
0
0
0
0
0
0
Stworzywszy element półcyklu dodatniego tworzymy
kolejny element półcyklu ujemnego. Stoimy na komórce
stworzonego elementu półcyklu dodatniego. Szukamy w
wierszu, w której stoimy elementu bazowego, który
jednocześnie ma element bazowy w kolumnie. Jest nim
element o wartości 11 - zaznaczamy go znaczkiem "-"
20
10
0
0+
0
0
0
24+
11-
0
0
0
0
0
5+
10-
25
0
0
0
0
0
0
Mając element półcyklu ujemnego tworzymy kolejny
element półcyklu dodatniego. Stoimy na komórce
stworzonego elementu półcyklu ujemnego. Szukamy w
wierszu, w której stoimy elementu bazowego, który
jednocześnie ma element bazowy w kolumnie. Jest nim
element o wartości 24 - zaznaczamy go znaczkiem "+"
20
10-
0
0+
0
0
0
24+
11-
0
0
0
0
0
5+
10-
25
0
0
0
0
0
0
Stworzywszy element półcyklu dodatniego tworzymy
kolejny element półcyklu ujemnego. Stoimy na komórce
stworzonego elementu półcyklu dodatniego. Szukamy w
wierszu, w której stoimy elementu bazowego, który
jednocześnie ma element bazowy w kolumnie. Jest nim
element o wartości 10 - zaznaczamy go znaczkiem "-"
20
10-
0
0+
0
0
0
24+
11-
0
0
0
0
0
5+
10-
25
0
0
0
0
0
0
Mamy stworzony cykl. Należy teraz znaleźć wartość
minimalną wśród elementów cyklu ujemnego - poczym
odjąć tą wartość od wszystkich elementów cyklu ujemnego
oraz dodać do wszystkich elementów cyklu dodatniego.
Elementami cyklu ujemnego są: 10, 11. Najmniejszą
spośród nich jest 10 i tę liczbę odejmujemy od elementów
cyklu ujemnego i dodajemy do elementów cyklu
dodatniego.
20
0-
0
10+
0
30
0
34+
1-
0
0
35
0
0
15+
0-
25
40
20
34
16
10
25
W wyniku czego otrzymujemy nowe rozwiązanie dopuszczalne.
Procedura cyklu spowodowała, że doszła nam jedna nowa baza
(wiersz 1, kolumna 4),
oraz dwie nam odeszły
(wiersz 1,
kolumna 2 oraz wiersz 3, kolumna 4).
Stąd nadal mamy 6
elementów bazowych - rozwiązanie jest zdegenerowane.
Obliczmy
koszt
nowego
rozwiązania
dopuszczalnego i porównajmy ze starym
(stary koszt = 601)
;
20
0
0
10
0
0
34
1
0
0
0
0
15
0
25
2
6
3
4
8
1
5
6
9
7
3
4
1
6
10
2·20+4·10+5·34+6·1+1·15+10·25 =
521
Uzyskaliśmy niższy koszt - rozwiązanie jest lepsze.
Pozostało
teraz
sprawdzić
metodą
potencjałów
optymalność rozwiązania i powtórzyć procedurę jeżeli
rozwiązanie nie jest optymalne.
