304 305

304 Programowanie wypukłe i kwadratowe

Warunek 3

Warunek ten stanowi powtórzenie warunków ograniczających rozpatrywanego zadania. Mamy więc:

g, U,, x₂) = 10-x, - 2x₂ Ss 0, g₂U,, *₂) = 9-X|-x₂35 0, g₃(x„ x₂)=x, >0,

SiOo. x₂) = x₂ >0.

Uwzględniając wprowadzone powyżej zmienne bilansujące x‘l i jc₂, możemy je zapisać następująco:

10—jc, — 2x₂—4 = 0,

9—JC| —x₂—x₂ = 0,

x, > 0,

x₂$*0.

Warunek 4

Wszystkie składowe wektora y muszą być nicujemne, czyli: yi > 0, y₂ > 0, y‘l > 0, y‘i 5* 0.

m.

i

:4.

Zestawiając warunki Kuhna-Tuckera, otrzymujemy:

(6.9)

(6.10)

(6.11)

(6.12)

(6.13)

(6.14)

20x, + 4x₂ + y, + y₂-y f = 10,

4jf, + 2.r₂ + 2y, + y₂—y₂ = 25, y,j:f+y₂4+yfjc, + 4*2 = 0, jc, + 2jc₂+4= 10,

X, +Xj+4=9,

*i. -*2. 4> xi y_h y₂, y^du yi > 0.

6.3.2. Sformułowanie zadania zastępczego

m

Korzystając z przekształconych odpowiednio warunków Kuhna-Tuckera, zapisanych wzorami (6.9)-(6.14), przystąpimy do formułowania zastępczego zadania optymalizacyjnego. Łatwo zauważyć, że jeżeli pominiemy warunek (6.11), to pozostałe warunki tworzą układ równań liniowych. Z kolei z warunku (6.14) wynika, że wszystkie występujące zmienne są nieujemne. Rozpatrywany przez nas układ równań liniowych można łatwo sprowadzić do postaci bazowej, mnożąc równania (6.9) i (6.10) przez liczbę — 1. Otrzymane rozwiązanie bazowe ma postać:

4 = 10, 4 = 9, yi-~ 10, y₂ = —25,

a pozostałe zmienne są zerami.

Ze względu na to, że mamy dwie zmienne o wartościach ujemnych, rozwiązanie to, choć bazowe, nie jest dopuszczalne. W takiej sytuacji wprowadzamy odpowiednio do warunków (6.9) i (6.10) zmienne sztuczne w, i w₂. Zmienne sztuczne wprowadzane do warunków ograniczających zadania zastępczego, powstałych przez przyrównanie do zera pochodnych cząstkowych funkcji Lagrange’a, nazywamy zmiennymi sztucznymi typu w. Zmienne te wprowadzamy również do funkcji celu (która nie była dotychczas uwzględniana, gdyż jej wszystkie współczynniki były zerami). Wystarczające jest przy tym wprowadzenie do funkcji celu zmiennych sztucznych ze współczynnikiem jeden.

Zapiszemy poniżej otrzymany problem programowania liniowego, rozpoczynając od warunków ograniczających zadania wyjściowego. Mamy:

w i + h>2 —^ min, jc, +2x₂+x‘I= 10, x_t+x₂+x^J2 = 9,

lQx_[ + 4x₂+y_l+y₂-y‘{+w\ = \0,    (6.15)

4x, + 2x₂+2y, +y₂—y₂ + w₂ = 25, x„ X₂, xf, *2, y„ y₂, yf, y₂, w,, w₂ > 0.

Konstruowane przez nas zadanie zastępcze obejmuje również nieliniowy warunek (6.11). Po lewej stronie równości znajduje się suma iloczynów zmiennych, które nazwiemy odpowiednio zmiennymi komplementarnymi. Parami zmiennych komplementarnych są:

y, i xi y₂ i x'{,

yi i *„ yt i *₂•

Zapiszmy ponownie pominięty poprzednio warunek (6.11). Ma on postać: y_lxUy₂xi+y^Jlx\+yix₂=0.

Każda ze zmiennych występujących po lewej stronie równania jest nieujemna. Wynika stąd, że każdy ze składników rozpatrywanej sumy musi być równy zeru. Tak więc jeżeli jedna z pary zmiennych komplementarnych jest dodatnia, to druga musi przyjąć wartość zero. Przypomnijmy, że taką samą własność wykorzystaliśmy przy rozwiązywaniu zadania z przykładu 6.1, rozpatrując kolejne podzbiory zbioru rozwiązań dopuszczalnych.

6.3.3. Rozwiązanie zadania zastępczego

Zadanie zastępcze rozwiążemy za pomocą zmodyfikowanego algorytmu simpleks, opisanego w rozdziale 1. Niezbędna modyfikacja uwzględnia występowanie w zadaniu zmiennych komplementarnych i ich własności. Nie może zaistnieć