ekonometria

 

 

1          Zadanie programowania liniowego

1.1        Wprowadzenie

Jeżeli w zadaniu (1.5-6) funkcja celu oraz warunki ograniczające są liniowe, to zadanie takie nazywamy zadaniem programowania liniowego.  Postać ogólna zadania programowania liniowego jest zatem następująca:

Każdy liniowy model decyzyjny odwzorowujący określoną sytuację decyzyjną zawiera się w ogólnej postaci zadania programowania liniowego. Postać ta nie jest wygodna do określenia różnych własności zadań. Z tego powodu sformułowana zostanie inna postać zadania programowania liniowego.

 

 

Zadanie o postaci ogólnej można przekształcić do zadania o postaci standardowej w następujący sposób:

·       zamiana rodzaju ekstremum - zadanie na minimum (maksimum) można przekształcić w zadanie na maksimum (minimum) zmieniając funkcję celu na przeciwną (mnożąc ją przez -1)

·       zamiana zmiennych decyzyjnych dowolnych co do znaku na zmienne nieujemne. Jeżeli x jest zmienną dowolną co do znaku, to podstawiając:  x=x+-x-, gdzie x+=max{0,x}, x-=max{0,-x}, otrzymujemy przedstawienie tej zmiennej za pomocą nieujemnych zmiennych x+ i x-

·       zamiana nierówności na równość:

               aTx£b    lub     aTx³b      można zastąpić  odpowiednio:       aTx+xd=b     lub     aTx-xd=b.

Nowo wprowadzona zmienna xd nosi nazwę zmiennej dodatkowej (osłabiającej).GZmienne te nie występują w funkcji celu.

 

PRZYKŁAD:

Postać wyjściowa:                               

                   funkcja celu:                     (max) z=2x1-x2+5x3-2x4

                   ograniczenia:                    x1+x2+2x3+5x4<=-20

                                                         2x1-x2-x4>=15

                                                         3x2+x3-2x4=14

                                                         x1,x3,x4>=0, x2 dowolne

 

Postać standardowa:                            

                   funkcja celu:                     (min) z’=-2x1+(x2+-x2-)-5x3+2x4

                   ograniczenia:                    -x1-(x2+-x2-)-2x3-5x4-x5=20

                                                         2x1-(x2+-x2-)-x4-x6=15

                                                         3(x2+-x2-)+x3-2x4=14

                                                         x1,x2+,x2-,x3,x4,x5,x6>=0

þ PYTANIA:

Czym się różni zadanie programowania liniowego od zadania programowania matematycznego ?

Czym się różni postać standardowa zadania programowania liniowego od jego postaci ogólnej ?

Czy zmienne osłabiające występują w funkcji celu ?

Czy zmienne decyzyjne lub osłabiające mogą być ujemne ?

1.2        Interpretacja geometryczna zadania programowania liniowego

Zadanie programowania liniowego ma prostą interpretację geometryczna. Z konieczności ograniczymy się do przypadku dwóch zmiennych decyzyjnych.

 

PRZYKŁAD :

                   funkcja celu:                     (max) z=x1+x2

                   ograniczenia:                    -x1+2x2<=6           (równanie prostej:  2x2=6+x1)

                                                         2x1-x2<=6            (równanie prostej:  x2=2x1-6)         

                                                         x1,x2>=0

 

Zadanie to możemy rozwiązać w sposób graficzny:

 

x2=2x1-6

 
 

1. Znajdujemy obszar rozwiązań dopuszczalnych - X

 

x2

 
a. rysujemy proste w oparciu o ograniczenia

 

2x2=6+x1

 
b. zaznaczamy półpłaszczyzny spełniające nierówności

c. część wspólna jest obszarem rozwiązań dopuszczalnych

 

2. Znajdujemy rozwiązanie optymalne – x*

 

z=4

 
a. rysujemy prostą przechodząca przez rozwiązania

          o tej samej wartości funkcji celu

 

z=12

 
b. przesuwamy równolegle tę prostą w kierunku

 

z=2

 
     polepszania wartości funkcji celu

c. skrajne rozwiązanie jest rozwiązaniem optymalnym

 

 


 

x 1

 
Dla naszego zadania:

 

6

 
x1*=6, x2*=6    z*=x1*+x2*=12

G Graficzna prezentacja następujących sytuacji:

·       nie ma skończonego rozwiązania - rozwiązanie jest nieograniczone gdy X nie jest zwarte

·       jest jedno skończone rozwiązanie

·       jest wiele skończonych rozwiązań

·       nie ma żadnego rozwiązania - X jest puste.

1.3        Własności zadania programowania liniowego

1.3.1      Kombinacja liniowa wektorów, wektory liniowo niezależne (cel: baza)

Wektor xÎRn nazywamy kombinacją liniową wektorów x1,x2,...,xkÎRn jeżeli:

                                                                                    (2.1)

Przykład: wektor  jest kombinacją liniową wektorów  ponieważ:

 

Wektor xÎRn nazywamy wypukłą kombinacją liniową wektorów x1,x2,...,xkÎRn jeżeli:

                       przy czym          (2.2)

Zbiór wektorów x1,x2,...,xn nazywamy liniowo niezależnym, jeżeli równość:

                                                                                    (2.3)

zachodzi tylko wtedy, gdy wszystkie  li=0 (i=1,...,k). W przeciwnym razie zbiór jest liniowo zależny.

W n-wymiarowej przestrzeni euklidesowej Rn  istnieje układ n liniowo niezależnych wektorów, ale każdy układ n+1 wektorów w tej przestrzeni jest układem liniowo zależnym.

1.3.2      Baza, rozwiązanie bazowe (cel: zadanie PL a baza)

Bazą zbioru S Ì Rn jest zbiór liniowo niezależnych wektorów, takich że wszystkie inne wektory należące do S da się przedstawić jako kombinację liniową wektorów bazy.

Dowolny zbiór n liniowo niezależnych wektorów należących do Rn jest bazą w przestrzeni Rn .

Zbiór n wektorów jednostkowych [1,0,...,0],[0,1,...,0],...,[0,0,...,1] jest bazą w Rn. !!!

Dany jest układ równań liniowych Ax=b. Macierz A jest typu m x n i zakładamy że m<=n. Niech AB jest bazą zbioru kolumn macierzy A, xB niech będzie wektorem zmiennych stojących przy kolumnach bazowych (zmienne bazowe), xR wektorem zmiennych stojących przy kolumnach niebazowych (zmienne niebazowe lub wtórne). Układ równań liniowych możemy przedstawić teraz w postaci ABxB+ARxR=b.

1.3.3      Zbiory wypukłe, sympleks

Wypukłą kombinacją punktów U1,U2,...,Uk  (UiÎ Rn i=1..k) nazywamy punkt:

                                                                      (2.4)

TWIERDZENIE: Dowolny punkt leżący na odcinku łączącym dwa punkty w Rn może być wyrażony jako kombinacja wypukła tych dwóch punktów.

W interpretacji geometrycznej, zbiór wypukły jest to taki zbiór, który składa się z odcinków łączących każde dwa punkty zbioru.

Punkt U zbioru wypukłego nazywamy wierzchołkiem, jeśli nie może być on wyrażony jako kombinacja wypukła dwóch różnych punktów należących do tego zbioru.

Sympleks jest n-wymiarowym wielościanem wypukłym mającym dokładnie n+1 wierzchołków. Brzeg sympleksu składa się z sympleksów niższych wymiarów zwanych powierzchniami sympleksu. Ilość takich płaszczyzn o wymiarze „i” wynosi . Sympleksem w przestrzeni zerowymiarowej jest punkt, jednowymiarowej - prosta, dwuwymiarowej -trójkąt, trójwymiarowej - czworościan.

1.3.4      Związek między rozwiązaniami optymalnymi a punktami wierzchołkowymi (cel: wierzchołek a baza)

Rozwiązaniem dopuszczalnym zadania programowania liniowego jest wektor x spełniający warunki  (W1) i (W2)

Rozwiązaniem bazowym układu równań (W1) nazywamy rozwiązanie układu powstałe z (W1) przez przyrównanie do zera n-m zmiennych przy założeniu, że wyznacznik współczynników tych m zmiennych jest niezerowy. Te m zmiennych nazywamy zmiennymi bazowymi.

Rozwiązaniem bazowym dopuszczalnym nazywamy rozwiązanie bazowe, które spełnia warunek (W2), czyli wszystkie zmienne bazowe są nieujemne.

Niezdegenerowanym rozwiązaniem bazowym dopuszczalnym nazywamy bazowe rozwiązanie dopuszczalne, w którym wszystkie zmienne bazowe są dodatnie (>0).

WŁASNOŚĆ: Zbiór wszystkich rozwiązań dopuszczalnych zadania programowania liniowego jest zbiorem wypukłym (sympleksem).

WŁASNOŚĆ: Funkcja celu zadania programowania liniowego przyjmuje wartość optymalną w punkcie wierzchołkowym zbioru wypukłego X. Jeśli przyjmuje wartość optymalna w więcej niż jednym punkcie wierzchołkowym, to tę samą wartość przyjmuje dla każdej kombinacji wypukłej tych punktów.

1.3.5      Związek między punktami wierzchołkowymi a wektorami liniowo niezależnymi.

Warunek ograniczający (W1) można przedstawić także w następującej postaci:

                                                         P1*x1+P2*x2+ ...+Pn*xn=Po                                                      (W1’)

gdzie Pi ÎRm    i=0..n

WŁASNOŚĆ: Jeżeli można znaleźć k<=m wektorów P1,...,Pk liniowo niezależnych takich że:

                   P1*x1+P2*x2+ ...+Pk*xk=Po oraz wszystkie xj>=0

to punkt o współrzędnych x=[x1,...,xk,0,...,0]T jest punktem wierzchołkowym zbioru X.

WŁASNOŚĆ: Jeśli x=[x1,...,xn]T jest punktem wierzchołkowym zbioru X, to wektory Pj odpowiadające dodatnim xj są liniowo niezależne.

Z obu własności wynika, że dodatnich xj jest co najwyżej m.

WNIOSEK: Każdemu punktowi wierzchołkowemu zbioru X odpowiada zbiór m wektorów liniowo niezależnych z danego zbioru P1,...,Pn. Tych m wektorów tworzy bazę m-wymiarowej przestrzeni wektorowej, a odpowiadający im punkt wierzchołkowy reprezentuje bazowe rozwiązanie dopuszczalne zadania programowania liniowego.

Uogólnienie dotychczasowych 4 własności:

 

 

 

 

TWIERDZENIE:  Punkt x jest punktem wierzchołkowym zbioru X wtedy i tylko wtedy, gdy w kombinacji liniowej wektorów niezależnych Pj

                                                                                                            (2.5)

współczynniki xj są dodatnie.

WNIOSKI:

·       Każde bazowe rozwiązanie dopuszczalne jest punktem wierzchołkowym zbioru X

·       Istnieje punkt wierzchołkowy zbioru X, w którym funkcja celu przyjmuje optimum

Trzeba więc badać tylko rozwiązania w punktach wierzchołkowych. Takich punktów wierzchołkowych jest  - tyle ile wektorów liniowo niezależnych z danego zbioru n wektorów. Idea rozwiązania może polegać więc na wygenerowaniu wszystkich kombinacji i porównaniu funkcji celu. Dla dużych m i n byłoby niemożliwe obliczenie wszystkich rozwiązań. Potrzebna jest metoda, pozwalająca utworzyć ciąg rozwiązań dopuszczalnych, zbieżny do rozwiązania optymalnego. Taką metodą jest metoda sympleks (sympleksów) podana przez G.B.Dantziga. Dla znalezienie minimalnego rozwiązania wystarczy zwykle m do 2m kroków (skończona i ograniczona liczba kroków).

1.4        Metoda Sympleks (MINIMALIZACJA)

1.4.1      Idea

Z wcześniejszych rozważań[1] wiemy, że jeżeli zadanie programowania liniowego ma skończone rozwiązanie optymalne to jest nim punkt wierzchołkowy tego obszaru. Ogólna idea metody sympleks polega na przechodzeniu pomiędzy sąsiednimi punktami wierzchołkowymi obszaru rozwiązań dopuszczalnych w celu polepszenia funkcji celu. W przypadku niemożności polepszenia wartości funkcji celu, dane rozwiązanie jest rozwiązaniem optymalnym.

Z matematycznego punktu widzenia każdemu punktowi wierzchołkowemu odpowiada bazowe rozwiązanie dopuszczalne. Przejściu pomiędzy sąsiednimi wierzchołkami odpowiada zaś zamiana danej bazy (danego dopuszczalnego rozwiązania bazowego) na sąsiednią (sąsiednie dopuszczalne rozwiązanie bazowe). Sąsiednia baza jest konstruowana przez zamianę jednego wektora bazowego innym - niebazowym. Wektory te są tak dobierane, by polepszyć wartość funkcji bazowego rozwiązania dopuszczalnego. Problemem pozostaje jedynie dobór początkowego (startowego) bazowego rozwiązania dopuszczalnego.

GZakładać będziemy, że każde dopuszczalne rozwiązanie bazowe jest niezdegenerowane.

1.4.2      Początkowe bazowe rozwiązanie dopuszczalne

Metoda sympleks startuje od początkowego bazowego rozwiązania dopuszczalnego. Dla pewnej klasy problemów, rozwiązanie to można znaleźć natychmiast. Spójrzmy na zadanie programowania liniowego:

                   funkcja celu:                     (min) z=cTx

                   ograniczenia:                    Ax£b     (b³0)

                                                         x³0

Należy sprowadzić to zadanie do postaci standardowej - dodanie zmiennych osłabiających utworzy początkową bazę.

 

Przykład:                  

                   funkcja celu:                     (min) z=-x1-4x2

                   ograniczenia:                    x1+x2£1

                                                         4x1+2x2£3

                                                         x1,x2³0

Po dodaniu zmiennych osłabiających otrzymamy następujące zadanie (zadanie PL. o postaci standardowej):

                   funkcja celu:                     (min) z=-x1-4x2

                   ograniczenia:                    x1+x2+x3=1

                                                         4x1+2x2+x4=3

                                                         x1,x2,x3,x4³0

Współczynniki przy zmiennych osłabiających (wektory jednostkowe) tworzą bazę. Zmienne te są więc zmiennymi bazowymi. Wartości tych zmiennych są równe wartościom elementów wektora b. Pozostałe zmienne (zmienne decyzyjne) są zmiennymi niebazowymi i ich wartości są równe 0. Funkcja celu ma zatem wartość równą 0.



[1] patrz – interpretacja geometryczna zadania programowania liniowego