308 309

308 Programowanie wypukłe i kwadratowe

tarnej x?₂ i niemożność jej wymiany ze zmienną y₂ (wartość odpowiadającego wymianie współczynnika macierzy wynosi -0,25), zmiennej y₂ nie możemy wprowadzić do bazy. Do bazy możemy wprowadzić dopiero trzecią kandydującą zmienną, czyli yf, gdyż komplementarna do niej zmienna x, nie jest zmienną bazową. Wyniki obliczeń przedstawiono w tablicy 6.4.

Tablica 6.4

cx —	min	0	0	0	0	0	0	0	0	1	1	b
Baza	^cn	-Ti	*2	./	4		y2	yl	>2	«’l	w2
yl	0	-18	0	2	0	-i	-i	i	0	-1	0	10
4	0	0,5	0	-0,5	i	0	0	0	0	0	0	4
x2	0	0,5	1	0,5	0	0	0	0	0	0	0	5
w2	1	3	0	-1	0	2	i	0	-1	0	1	15
^cr	-z,	-3	0	1	0	-2	-i	0	1	1	0	X

Iteracja 4

Występowanie ujemnych wartości wskaźników optymalności w tablicy 6.4 wskazuje na to, że należy w dalszym ciągu kontynuować procedurę. Pierwszą zmienną kandydującą do bazy jest jt,, jednak ze względu na obecność w bazie zmiennej komplementarnej yf oraz niemożność jej wyprowadzenia z bazy przechodzimy do rozpatrywania kolejnej zmiennej kandydującej, czyli y,. Zmienną tę możemy wprowadzić do bazy, gdyż zmienna komplementarna x‘( nie występuje w dotychczasowej bazie. Tablica 6.5 zawiera wyniki uzyskane po wykonaniu czwartej iteracji.

Tablica 6.5

cx —	min	0	0	0	0	0	0	0	0	1	1
Baza	Cu		*2	4	4	y<	y2	yl	yi	w,	w2
yl	0	-16,5	0	1,5	0	0	-0,5	i	-0,5	-1	0,5	17,5
xi	0	0,5	0	-0,5	i	0	0	0	0	0	0	4
*7	0	0,5	1	0,5	0	0	0	0	0	0	0	5
y>	0	1,5	0	-0,5	0	i	0,5	0	-0.5	0	0,5	7,5
Cj-	~Zj	0	0	0	0	0	0	0	0	1	1	X

W tablicy 6.5 wszystkie wartości współczynników optymalności są nieujemne, co wskazuje na to, że otrzymaliśmy rozwiązanie optymalne zadania zastępczego.

Zgodnie z twierdzeniem Kuhna-Tuckera z tablicy 6.5 możemy odczytać rozwiązanie optymalne interesującego nas zadania programowania kwadratowego, które jest następujące: x, =0, x₂ = 5. Podstawiając te wartości do wzoru określającego funkcję celu, otrzymujemy jej optymalną wartość, równą 100.

6.3.4. Przypadek ogólny

W poprzedniej części podrozdziału 6.4 zajmowaliśmy się konstrukcją zadania zastępczego do zadania programowania kwadratowego i jego rozwiązaniem w przypadku, gdy w zadaniu (6.4) mieliśmy b>0 i p>0. Uchylimy obecnie te warunki.

Przykład 6.3

Rozpatrujemy zadanie:

/(x,, x₂)~ 10jc, + 25x₂- 10x?~x₂-4x,x₂ —» max,

Xi + 2x₂ ^ 10,

-x,-x₂s$-9, x, 3>0, x₂^0.

Powyższe zadanie różni się od przykładu 6.2 postacią drugiego warunku ograniczającego, mamy bowiem b₂ < 0. Zapisujemy funkcję Lagrange’a, a następnie warunki Kuhna-Tuckera i zadanie zastępcze. Chcąc w zadaniu zastępczym uzyskać pierwszą postać bazową dopuszczalną, do drugiego warunku ograniczającego zadania wyjściowego dołączamy zmienną sztuczną. Zmienne sztuczne wprowadzane do warunków ograniczających zadania wyjściowego w przypadku, gdy niektóre (lub wszystkie) współrzędne wektora b są ujemne nazwiemy zmiennymi sztucznymi typu v. W rozpatrywanym przez nas zadaniu wystarczy wprowadzić jedną taką zmienną. Zmienne typu v wprowadzamy również do funkcji celu. Zadanie zastępcze przyjmuje postać:

yi + wą + Wj —> min, x, +2x₂ + x/= 10,

x,+x₂—x₂+V]=9,

20x, + 4x₂+y, — y₂—y‘l + w, = 10,

4x, +2x₂ + 2yi —y₂—y₂ + w₂ = 25,

X|, x₂, x|, x₂, yi, y₂, yf, y₂, rą, W|, w₂ ^ 0.

Zapisujemy je w postaci tablicy simpleksowej i rozwiązujemy za pomocą algorytmu Wolfe’a. Po wykonaniu czterech iteracji otrzymujemy (tablica 6.6):