300 301

300 Programowanie wypukłe i kwadratowe

Rysunek 6.12 A

Podzbiór 1

Jeżeli gi>0, g₂> 0, g₃>0, to z warunku 2 wynika, że y,=0, y₂ = 0 i y₃ = 0. Wstawiając te wartości do warunku 1, mamy:

1 —20x_i +0 = 0,

1-20-x₂ + 0 = 0,

czyli 1=0, co doprowadza do sprzeczności. Oznacza to, że w rozpatrywanym podzbiorze nie ma punktu spełniającego układ warunków Kuhna-Tuckera.

Podzbiór 2 ^{1 2 3}

Podstawiając te wartości do warunku (6.5), otrzymujemy:

⁸ (2y,)³ (2y,)³ ’

a stąd }’i = '/₄ lub y, = - '/₄. Wartość y, =-'/₄ eliminujemy, gdyż nie spełnia warunku nieujemności, nałożonego na składowe wektora y. Ze związku (6.6) otrzymujemy wartości x, = 2, x₂ = 2. Tak więc rozwiązanie układu warunków Kuhna-Tuckera w podzbiorze 2 jest następujące:

Xi = 2, x₂ = 2, y, = y₂ = 0, y₃ = 0.

Na podstawie twierdzenia Kuhna-Tuckera rozwiązaniem interesującego nas zadania programowania wypukłego są wartości x_t-2, x₂ = 2.

Analizując w podobny sposób pozostałe podzbiory, możemy stwierdzić, że w żadnym z nich problem Kuhna-Tuckera nie ma rozwiązania (co zresztą stwierdziliśmy już uprzednio, rozwiązując to zadanie metodą geometryczną), czyli jedynym rozwiązaniem problemu wyjściowego jest rozwiązanie znalezione w trakcie analizy podzbioru 2.

6.3. Metoda Wolfe’a

Zajmiemy się rozwiązaniem zadania programowania kwadratowego określonego wzorem (6.4). Zapisanie warunków Kuhna-Tuckera pozwala na sformułowanie zadania zastępczego, które następnie można rozwiązać, stosując pewną modyfikację prymalnej metody simpleks, omówioną w rozdziale 1.

Po znalezieniu rozwiązania optymalnego zadania zastępczego określimy rozwiązanie optymalne wyjściowego zadania programowania kwadratowego. Rozpoczniemy od przypadku, gdy b > 0 i p > 0.

6.3.1. Warunki Kuhna-Tuckera

dla zadania programowania kwadratowego

Pokażemy, w jaki sposób tworzymy to zadanie zastępcze, wykorzystując zadanie rozpatrywane w przykładzie 6.2. Przypomnijmy, że problem ten ma następującą postać:

f(xi, x₂) = 10x, +25x₂— 10x³ —x₂-4x,x₂ —» max, x,+2x₂tą 10,

*1+ *2 <9, (6.7)

x, ^ 0, x₂ > 0.

Jeżeli g₂ > 0 oraz #₃ > 0, to z warunku 2 wynika, że y₂ = 0 oraz y₃ = 0. Warunek ten ma wówczas postać:

>>,(8 — jc? — jr|) = 0.

Możemy założyć, że y,*0 (przypadek .yi=0, y₂ = 0, y₃ = 0 byl już rozpatrywany wcześniej), stąd warunek ten po podzieleniu stronami przez y, przyjmuje postać:

(8—jc?—jcf) = 0. (6-5

Podstawiając wartości y₂ = 0 oraz y₃ = 0 do warunku l, otrzymujemy:

-2y,jT| =0,

1 —2y, x₂ = 0,

a stąd:

x₂-^~. (6-⁽

y, 2y,

300 301

300 301

1 —20xi +0 = 0,

8 (2y,)3 (2y,)3 ’

Xi = 2, x2 = 2, y, = y2 = 0, y3 = 0.

6.3. Metoda Wolfe’a

6.3.1. Warunki Kuhna-Tuckera

dla zadania programowania kwadratowego

x, ^ 0, x2 > 0.

1 —20x_i +0 = 0,

⁸ (2y,)³ (2y,)³ ’

Xi = 2, x₂ = 2, y, = y₂ = 0, y₃ = 0.

x, ^ 0, x₂ > 0.