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.
Document Outline
- Slide 1
- Slide 2
- Slide 3
- Slide 4
- Slide 5
- Slide 6
- Slide 7
- Slide 8
- Slide 9
- Slide 10
- Slide 11
- Slide 12
- Slide 13
- Slide 14
- Slide 15
- Slide 16
- Slide 17
- Slide 18
- Slide 19
- Slide 20
- Slide 21
- Slide 22
- Slide 23
- Slide 24
- Slide 25
- Slide 26
- Slide 27
- Slide 28
- Slide 29
- Slide 30
- Slide 31
- Slide 32
- Slide 33
- Slide 34
- Slide 35
- Slide 36
- Slide 37
- Slide 38
- Slide 39
Wyszukiwarka
Podobne podstrony:
83 Nw 05 Zostan autorem
83 Nw 04 Powiekszenie parapetu
74 Nw 11 Obwody drukowane
86 Nw 05 Odbiornik radiowy
82 Nw 07 Ogranicznik pradu
82 Nw 06 Drewniana rama
91 Nw 05 Amator stereo
76 Nw 09 Reczna wczepiarka
nw asd w13
69 NW 06 Uzwojenie cewki
77 Nw 01 Wiertarka kolumnowa dok
77 Nw 01 Budujemy skiboby
91 Nw 04 Dwa biosy
72 Nw 01 Zestawy glosnikowe
71 NW 12 Konstrukcje z drutu
75 Nw 08 Jak zostac krotkofalowcem
85 Nw 01 Uchwyt pistoletowy
71 NW 12 Tranzystorowa syrena
82 Nw 04 Stabilizator temperatury
więcej podobnych podstron