Programowanie Kwadratowe – Metoda Wolfe’a 

 

1.  Definicja problemu 

Celem  programowania  kwadratowego  jest  znalezienie  minimum  funkcji  kwadratowej  posiadającej 
liniowe ograniczenia. Zadanie można zapisad następująco: 

 

   

   

  

 

     

 

    

(1) 

 

Gdzie: 

 

          

 

                 

(2) 

 

Wzór (1) opisuje funkcję celu, gdzie  c

T

 jest to macierz współczynników przy zmiennych liniowych, a

 

macierz  D  posiada  współczynniki  przy  zmiennych  kwadratowych.  Jednocześnie  macierz  D  jest 
symetryczna i nieujemnie określona. S jest to natomiast przestrzeo dostępnych rozwiązao opisana w 
zborze R

n

. W innych słowach niniejsze ograniczenia są nakładane na zadanie: 

 

       

(3) 

 

 

      

(4) 

 

Co więcej, zakłada się, że 

 

                         

(5) 

 

2.  Warunki Kuhna-Tuckera 

W  celu  poprawnego  ustalenia  warunków  Kuhna-Tuckera  należy  przedstawid  problem  w  postaci 
funkcji Lagrange’a: 

 

     

 

     

 

      

 

            

 

  

(6) 

 

Gdzie Dla przedstawionego w ten sposób równania, warunki Kuhna Tuckera są następujące: 

 

           

 

          

(7) 

 

 

 

 

      

(8) 

 

 

       

(9) 

 

 

      

(10) 

 

 

      

(11) 

 

Z  powodu  ciągłości  funkcji  celu,  którą  należy  minimalizowad,  oraz  z  powodu  założeo  na  temat 
ograniczeo  wynika,  że  problem  jest  zbieżny,  a  co  za  tym  idzie,  powyższe  warunki  są  warunkami 
koniecznymi i wystarczającymi. 

3.  Algorytm Wolfe’a 

Celem algorytmu Wolfe’a jest zredukowanie problemu programowania kwadratowego do problemu 
programowania liniowego, a następnie użycia algorytmu simpleks do rozwiązania. W standardowym 
problemie  programowania  liniowego  wszystkie  zmienne  są  nieujemne,  natomiast  mnożnik 
Lagrange’a  λ  nie  posiada  takich  ograniczeo.  Co  za  tym  idzie  należy  dokonad  następującego 
podstawienia: 

 

          

(12) 

 

gdzie ξ, Ϛ ≥ 0. Wynika z tego, że następująca lista równao musi zostad rozwiązana: 

 

       

(13) 

 

 

       

 

     

 

           

(14) 

 

 

 

 

      

(15) 

 

 

                           

(16) 

 

Warunek (15) nie jest liniowy dlatego nie może byd bezpośrednio użyty do programowania liniowego, 
jednak  po  zastosowaniu  pewnych  przekształceo,  które  zostaną opisane  później,  można  będzie  użyd 
go w algorytmie simpleks. 
Zbiór równao (13-14) można traktowad jako zbiór warunków do problemu programowania liniowego. 
Brakuje jedynie funkcji celu, która zostanie zdefiniowana później. Jednak każde rozwiązanie równao 
(13-15),  spełniające  warunki  (16)  jest  jednocześnie  rozwiązaniem  problemu  programowania 
kwadratowego, dlatego można już w tym momencie stosowad pierwszy krok algorytmu simpleks. 



 

Jeżeli  któreś  z  równao  (13-14)  posiada  wolny  element  znajdujący  się  po  prawej  stronie  ze 
znakiem ujemnym, wtedy należy przemnożyd wiersz przez -1.  



 

Dodajemy po jednej sztucznej zmiennej do każdego równania (13-14). 



 

Określamy funkcję celu jako sumę wszystkich zmiennych sztucznych. 



 

Rozwiązujemy  zadanie  metodą  simpleks.  Jeśli  zostanie  znalezione  rozwiązanie 
programowania  liniowego,  jest  ono  jednocześnie  rozwiązaniem  programowania 
kwadratowego. 

Niestety  ten  algorytm  prowadzi  do  rozszerzenia  ilości  zmiennych  do  rozmiaru  3n  +  3m.  W  celu 
usprawnienia obliczeo należy zredukowad liczbę zmiennych do minimum. 
Łatwo  zauważyd,  że  nowo  zdefiniowana  funkcja  celu  nie  tylko  ułatwia  znalezienie  rozwiązania  ale 
również  wskazuje  na  pierwsze  rozwiązanie  bazowe.  W  rzeczywistości  więc  potrzebujemy  jedynie 
n + m zmiennych bazowych. Pierwsze m zmiennych można wybrad ze wzoru (13) po przekształceniu 
go na postad kanoniczną: 

 

 ̃     ̃ 

(17) 

 

Zbiór równao przedstawiony jest jako tabela (1). 
 

 ̃ 

0 

 

x 

= 

 ̃ 

2D  - ̃

 

 

 ̃

 

 

  

 

 

 

 

  

 

 

 

 

 

 

 

 

 

  

 

Ϛ 

ξ 

µ 

-c 

Tabela 1. Równania ograniczające po zamianie (13) na postad kanoniczną. 

 
Następnie  należy  pozbyd  się  zmiennych  bazowych  z  równania  (14).  W  tym  celu  należy  podstawid 
zmienne  bazowe  do  oryginalnej  funkcji  kwadratowej  korzystając  z  równao  w  postaci  kanonicznej. 
Jeżeli  za  ilośd  zmiennych  bazowych  w  kolumnie  j  przyjmiemy  k  (na  przykład  (a)

kj

=1,  (a)

ij

=0  dla  i≠j), 

wtedy  dla  każdego  wiersza  d

s

  w  w  dolnej  części  macierzy  D,  następujące  obliczenia  muszą  zostad 

wykonane: 

 

  

 

   

 

   

  

 ̃

 

 

(18) 

 

Gdzie  ̃

 

 oznacza k-ty rząd macierzy  ̃. Jako wynik podstawienia otrzymujemy nowe macierze D’ i c’ 

zamiast D i c. Przekształcone równania mają postad: 

 

 ̃     ̃ 

(19) 

 

 

        ̃

 

     ̃

 

            

(20) 

 

Przed  wprowadzeniem  zmiennych  sztucznych  należało  zwrócid  uwagę  na  nienegatywną  formę 
wektora   ̃    

 

 

 

 poprzez  mnożenie  odpowiednich  rzędów  przez  -1.  Należy  zwrócid  uwagę,  że  to 

założenie dotyczy jedynie rzędów odnoszących się do –c. Pozostałe już spełniają te warunki poprzez 
procedurę  znajdywania  postaci  kanonicznej  do  równania  (13).  Należy  więc  przekształcid  równanie 
(20) na: 

 

  

  

     ̃

   

     ̃

   

              

(21) 

 

Macierz E jest diagonalna i zawiera 1 lub -1 na głównej przekątnej. Podsumowując wszystkie operacje 
przeprowadzone  powyżej,  problem  programowania  liniowego  sprowadza  się  do  znalezienia 
minimum z: 

 

        

 

   

 

       

 

  

(22) 

 

Ograniczonego równaniami (19), (21) i (16), z dodatkowym założeniem (15). 
 

 ̃ 

0 

 

x 

= 

 ̃ 

2D’’ 

- ̃  

 

 

 ̃  

 

  E 

   

 

 

   

 

 

 

     

 

 

 

 

 

Ϛ 

ξ 

µ 

u 

c’’ 

Tabela 2. Ostateczna postad programowania kwadratowego po zastosowaniu algorytmu Wolfe’a. 

 
Tabela simpleks dla linearyzacji programowania kwadratowego podana jest w tabeli 2. Ograniczenia 
(15)  mogą  byd  brane  pod  uwagę  przy  zastosowaniu  dodatkowych  założeo  przy  tworzeniu  tabeli 
simpleks.  Warto zauważyd, że  zmienne  µ  nie należą do bazy więc są równe 0. Następnie wystarczy 
stworzyd następną gałąź w następnym kroku, tak aby równanie (15) było zachowane. Pamiętajmy, że 
warunek ten mówi, że jedna ze zmiennych x

i

 i µ

i

 w danej parze jest zerem. Jako że w programowaniu 

liniowym,  zmienna  nie  jest  zerem  jedynie  gdy  jest  zmienną  bazową,  jedynymi  modyfikacjami 
algorytmu simpleks są: 



 

Jeżeli zmienną wchodzącą do bazy jest jedna z ξ

i

, Ϛ

i

 lub u

i

, wtedy algorytm nie ulega zmianie. 



 

Jeżeli  zmienna  wchodząca  do  bazy  jest  zmienną  x

i

,  wtedy  przed  musimy  sprawdzid  czy 

odpowiadająca zmienna µ

i

 jest w bazie. Jeśli tak, to x może wejśd do bazy, lecz tylko jeśli µ

i

=0. 

W przeciwnym razie należy wybrad inną zmienna. 



 

Jeżeli  zmienna  wchodząca  do  bazy  jest  zmienną  µ

i

,  wtedy  przed  musimy  sprawdzid  czy 

odpowiadająca zmienna x

i

 jest w bazie. Jeśli tak, to µ może wejśd do bazy, lecz tylko jeśli x

i

=0. 

W przeciwnym razie należy wybrad inną zmienna. 

4.  Laboratorium 

Przed przystąpieniem do laboratorium należy przede wszystkim odświeżyd wiedzę ze wcześniejszych 
laboratoriów,  w  szczególności  związanych  z  problemem  programowania  liniowego  oraz  metodą 
simpleks.  

W  trakcie  laboratorium  należy  rozwiązad  podany  przez  prowadzącego  problem  programowania 
kwadratowego poprzez linearyzacje zgodnie z metodą Wolfe’a oraz sprawdzid rozwiązanie używając 
Matlab opbimization toolbox. 

Sprawozdanie  powinno  zawierad  szczegóły  dotyczące  zamiany  problemu  programowania  liniowego 
na  programowanie  kwadratowe,  rozwiązanie  metodą  simpleks  oraz  sprawdzenie  za  pomocą 
optimization toolbox. W sprawozdaniu należy pamiętad o wnioskach.