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 jc_t. 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 x₂. Zmienną do niej komplementarną jest niebazowa zmienna yi, więc do nowej bazy wprowadzamy x₂. 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 y₂. Jednak i w tym przypadku, ze względu na obecność w bazie zmiennej komplemen-