Programowanie Kwadratowe - metoda Wolfe'a
zadanie PK |
zadanie równoważne pierwotnemu ZPK (problem Kuhn'a-Tucker'a z modyfikacją Wolfe'a) |
|
|
w - zmienne sztuczne ograniczeń zadania dualnego |
|
Postępowanie Wolfe'a polega na użyciu zmodyfikowanej wersji prymalnego algorytmu simpleksowego. Modyfikacja dotyczy kryterium wejścia i kryterium optymalności. Początkowe, bazowe rozwiązanie dopuszczalne: 
Jeżeli najmniejszy wskaźnik optymalności 
jest ujemny, to odpowiednią zmienną wprowadzamy do bazy, jeśli zachodzi jeden z trzech przypadków:
zmienną wprowadzaną jest zmienna sztuczna,
zmienną wprowadzaną jest zmienna, której komplementarna "towarzyszka" jest zmienną niebazową
zmienną wprowadzaną jest zmienna, której komplementarna "towarzyszka" jest zmienną bazową, ale wyzeruje się ona w nowej bazie; jeżeli to miałoby nie nastąpić to do wejścia wybiera się kolejną zmienną o najniższym wskaźniku.
Jeżeli w kolejnej iteracji stwierdzimy, że żadna ze zmiennych o ujemnym wskaźniku nie może być wprowadzona (w szczególnym przypadku wszystkie zmienne mają nieujemne wskaźniki) to kończymy postępowanie.
|
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
|
zmien- ne bazo- we |
|
|
|
|
|
|
|
|
|
|
|
|
iloraz wyj- ścia |
|
|
1 |
2 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
10 |
10 |
|
|
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
9 |
9 |
|
|
20 |
4 |
0 |
0 |
1 |
1 |
-1 |
0 |
1 |
0 |
10 |
0,5 |
|
|
4 |
2 |
0 |
0 |
2 |
1 |
0 |
-1 |
0 |
1 |
25 |
6,25 |
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
|
0 |
0 |
1,8 |
1 |
0 |
-0,05 |
-0,05 |
0,05 |
0 |
-0,05 |
0 |
9,5 |
|
|
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 |
|
|
1 |
0 |
1,2 |
0 |
0 |
1,8 |
0,8 |
0,2 |
-1 |
-0,2 |
1 |
23 |
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
|
0 |
-9 |
0 |
1 |
0 |
-0,5 |
-0,5 |
0,5 |
0 |
-0,5 |
0 |
5 |
|
|
0 |
-4 |
0 |
0 |
1 |
-0,25 |
-0,25 |
0,25 |
0 |
-0,25 |
0 |
6,5 |
|
|
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 |
-1 |
-0,5 |
1 |
20 |
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
|
0 |
-18 |
0 |
2 |
0 |
-1 |
-1 |
1 |
0 |
-1 |
0 |
10 |
|
|
0 |
0,5 |
0 |
-0,5 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
|
|
0 |
0,5 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
5 |
|
|
1 |
3 |
0 |
-1 |
0 |
2 |
1 |
0 |
-1 |
0 |
1 |
15 |
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
|
0 |
-16,5 |
0 |
1,5 |
0 |
0 |
-0,5 |
1 |
-0,5 |
-1 |
0,5 |
17,5 |
|
|
0 |
0,5 |
0 |
-0,5 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
|
|
0 |
0,5 |
1 |
0,5 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
5 |
|
|
0 |
1,5 |
0 |
-0,5 |
0 |
1 |
0,5 |
0 |
-0,5 |
0 |
0,5 |
7,5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
Wyszukiwarka