306 307
306 Programowanie wypukłe i kwadratowe • i
306 Programowanie wypukłe i kwadratowe • i
sytuacja, w której w bazie jest jednocześnie zmienna i zmienna do niej komplementarna. Stosując kryterium wejścia metody simpleks, będziemy dodatkowo badać, czy w rozpatrywanej bazie znajduje się już zmienna komplementarna do tej, którą chcemy do bazy wprowadzić.
Jeżeli zmiennej komplementarnej w bazie nie ma, to nic nie stoi na przeszkodzie, aby rozpatrywaną zmienną wprowadzić do bazy. Gdy zmienna komplementarna do zmiennej, którą chcemy wprowadzić, jest w bazie, wymaga to dodatkowego badania. Trzeba odpowiedzieć na pytanie, czy przypadkiem zmienna, którą chcemy wprowadzić do bazy, nie wejdzie na miejsce zmiennej komplementarnej. Jeżeli to nastąpi, można takiej zmiany dokonać. Jeżeli natomiast nie jest to możliwe, należy zrezygnować z wprowadzania rozpatrywanej zmiennej do bazy i rozpatrzyć kolejną zmienną kandydującą.
Prześledzimy wykorzystanie metody Wolfe’a na przykładzie rozwiązania zadania zastępczego zapisanego w postaci warunków (6.15). Wyjściowa postać zadania z uwzględnieniem wartości współczynników optymalności przedstawiona została w tablicy 6.1.
Iteracja 1
Pierwsze rozwiązanie bazowe (tablica 6.1) nie jest optymalne, gdyż istnieją ujemne wskaźniki optymalności (należy pamiętać, że w odróżnieniu od rozpatrywanego w rozdziale I zadania maksymalizacji, w rozważanym obecnie problemie minimalizacji rozwiązanie jest optymalne wówczas, gdy wszystkie wskaźniki optymalności są nieujemne).
Tablica 6.1
|
cx — |
min |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 | ||
|
Baza |
CB |
-r. |
*2 |
x1 |
rd •*2 |
>2 |
yi |
yi |
W, |
w: | |||
|
x1 |
0 |
1 |
2 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
10 | |
|
xi |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
9 | |
|
*v, |
I |
20 |
4 |
0 |
0 |
1 |
1 |
-i |
0 |
1 |
0 |
10 | |
|
1 |
4 |
2 |
0 |
0 |
2 |
1 |
0 |
-1 |
0 |
1 |
25 | ||
|
cr |
-Z; |
-24 |
-6 |
0 |
0 |
-3 |
-2 |
1 |
I |
0 |
0 |
X |
Zgodnie z regułą wejścia metody simpleks, zmienną kandydującą do bazy jest jct. Zmienną do niej komplementarną jest yf, która w dotychczasowej bazie nie występuje, więc nic nie stoi na przeszkodzie, aby zmienną x, wprowadzić do bazy. i; Na podstawie kryterium wyjścia metody simpleks zmienną opuszczającą bazę jest Wi. Tablica 6.2 zawiera wyniki uzyskane po wykonaniu pierwszej iteracji.
Tablica 6.2
|
cx |
min |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
h |
|
Baza |
Cu |
*1 |
*2 |
-'l |
,1 |
y> |
yi |
yi |
Yi |
w. |
w2 | |
|
x1 |
0 |
0 |
1,8 |
i |
0 |
-0,05 |
-0,05 |
0,05 |
0 |
-0,05 |
0 |
9,5 |
|
xi |
0 |
0 |
0,8 |
0 |
1 |
-0,05 |
-0,05 |
0,05 |
0 |
-0,05 |
0 |
8,5 |
|
0 |
1 |
0,2 |
0 |
0 |
0.05 |
0,05 |
-0,05 |
0 |
0,05 |
0 |
0.5 | |
|
H-2 |
1 |
0 |
1,2 |
0 |
0 |
1.8 |
0,8 |
0,2 |
-1 |
-0,2 |
1 |
23 |
|
cr |
-Zj |
0 |
-1.2 |
0 |
0 |
-1,8 |
-0,8 |
-0,2 |
l |
1,2 |
0 |
X |
Iteracja 2
Przechodzimy do kolejnej iteracji. Zmienna o najmniejszym wskaźniku optymalności jest y,. Zmienna komplementarną do niej jest x‘l, która jest również zmienną bazową. Należy więc sprawdzić, czy zmienne te mogłyby się wymienić. W tym celu w tablicy 6.2 znajdujemy przecięcie wiersza, odpowiadającego x“i oraz kolumny odpowiadającej y,. Mamy tam wartość ujemną -0,05. Zgodnie z regułą wyjścia metody simpleks ta wymiana nie jest więc możliwa. Oznacza to, że należy zrezygnować z zamiaru wprowadzenia do bazy zmiennej y, i przejść do rozpatrywania kolejnej zmiennej kandydującej (z drugim z kolei najmniejszym wskaźnikiem optymalności). Jest nią zmienna x2. Zmienną do niej komplementarną jest niebazowa zmienna yi, więc do nowej bazy wprowadzamy x2. Wyniki obliczeń przedstawiono w tablicy 6.3.
Tablica 6.3
|
cx — |
min |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
i |
1 |
|) |
|
Baza |
CB |
x2 |
X\ |
xi |
y, |
yi |
yi |
yi |
W, |
^2 | ||
|
X] |
0 |
-9 |
0 |
i |
0 |
-0.5 |
-0.5 |
0,5 |
0 |
-0,5 |
0 |
5 |
|
X2 |
0 |
-4 |
0 |
0 |
1 |
-0,25 |
-0,25 |
0,25 |
0 |
-0,25 |
0 |
6,5 |
|
X, |
0 |
5 |
1 |
0 |
0 |
0,25 |
0,25 |
-0,25 |
0 |
0,25 |
0 |
2,5 |
|
1 |
-6 |
0 |
0 |
0 |
1.5 |
0,5 |
0,5 |
-i |
-0,5 |
1 |
20 | |
|
cr |
6 |
0 |
0 |
0 |
-1,5 |
-0,5 |
-0,5 |
i |
-1,5 |
0 |
X |
Iteracja 3
Zmienną o najmniejszym (i ponownie ujemnym) wskaźniku optymalności w tablicy 6.3 jest y,. Zmienną komplementarną do niej jest x‘(, której nie można wymienić na zmienną y,, (wartość odpowiadającego tej wymianie współczynnika w macierzy wynosi -0,5). Drugą z kolei zmienną kandydującą do bazy jest y2. Jednak i w tym przypadku, ze względu na obecność w bazie zmiennej komplemen-
Wyszukiwarka
Podobne podstrony:
IMG07 ^Gorączka złota» 306 1925. Program do premiery Gorączki złota nych w godne podziwu bogate i p
str06 306 ton* pttrwsiy Podstawy nauk o wychowaniu poprzez program i realizac
37 (306) Cywinski2 - VMware Player (Evaluation license) Player ▼ JL v [fl M © « Programy Miejsca wto
pic 11 06 012751 307 306 LUBOMIR DOLE2EL wacii wszystkich sekwencji motywów dopuszczalnych w określ
346 Indeks pojąć 287. 301 - 303. 306. 307. 321: I. a filozofia 22: I. a matematyka 186; i. a psychol
Pałka J. 287, 288, 289 Pława M. 306 , 307 Sanaokl L.
CCF20100515 009 293. 293. 294. 295. 296. 297. 298. 299. 300. 301. 302. 303. 304. 305. 306. 307. CAT
CCF20120509 088 306 Część II. Rozwiązania i odpowiedzi 5. Dynamika cieczy rzeczywistych 307 z któreg
306 307 SbliografiaUa S.H., S
306 307 Wt* * mi> tu .ikajnmatu .i le/kii praca pr*>w<u1/i do i»,»gii..t> /<ł«iur i.i
306 307 ątig czggoś interesującego dowiedzieć, że również dziecko może być źródłem interesujących
306 307 306 Emocje w relacjach społecznych V-* • ra*" punktów i atrakcyjnymi nagrodami w postac
306 307 (10) - 306- - 306- C. Wykresy stosowane przy obliczeniach na podstawie mechaniki pęknięć i p
306 307 (2) Jeżeli bóle umiejscowione są w okolicy kąta żuchwy i na podstawie głośni, wykonujemy 3 u
306 307 (4) oporność H,dp«=<Rc~p- Podobnie jak w przykładzie 6.3, nie oblicza się dopuszczalnej w
306 307 (5) 306 URAZY I USZKODZENIA SPORTOWEWrastający paznokieć (onychocryptosis) Do choroby dochod
306 307 (7) 306 Akademia sieci Cisco 2. Które zdanie najlepiej opisuje trasy staty
więcej podobnych podstron