Ekonometria
Wybrane metody optymalizacji.
Optymalizacja liniowa.
dr hab. inż. Tadeusz Nowicki prof. nadzw.
e-mail:[e-mail]
1. Sformułowanie zadania optymalizacji
Przyjmijmy, że
X  przestrzeń rozwiązań (decyzji) o własnościach zależnych od
typu zadania,
Y  przestrzeń ocen rozwiązań (decyzji) o własnościach zależnych
od typu zadania,
F:XY  funkcja celu (kryterium oceny rozwiÄ…zania).
&!  zbiór rozwiÄ…zaÅ„ dopuszczalnych (&!‚"K)
K  zbiór ocen rozwiązań dopuszczalnych taki, że
K = {y " Y : y = f (x), x "&!}
&!* - zbiór rozwiązań  najlepszych
K*  zbiór ocen  najlepszych
Mówimy, że zadanie optymalizacji jest sformułowane, gdy dane
sÄ… &!, f i D.
y*=f(x*)
X
K
Y
&!
K*
&!*
f
xy
2. Przykłady zadań optymalizacji
2.1. Zadanie załadunku
Dane sÄ…
n  ilość rodzajów ładunków
aj  waga j-tego Å‚adunku, j=1,...,n,
cj  wartość j-tego ładunku, j=1,...,n,
b  ładowność (pojemność) środka transportu.
Nie przekraczając ładowności środka transportu, należy
załadować go tak, aby wartość ładunku była maksymalna.
Sformułujmy teraz zadanie optymalizacji załadunku 
załadowania na środek transportu.
Można to zapisać następująco: wyznaczyć
*
x* = (x1, x* ,..., x* )"&! ‚" En
2 n
takie, że
n n
f (x*) =
"c x* = " j
j j
maxj=1c x
j
x"&!
j=1
gdzie
Å„Å‚ üÅ‚
ôÅ‚x " En : n
&! =
òÅ‚ żł
"a x d" b, x "{0,1}ôÅ‚
j j j
ôÅ‚ ôÅ‚
j=1
ół þÅ‚
- gdy j-ty ładunek załadowany
1
Å„Å‚
x =
òÅ‚0 - gdy j-ty Å‚adunek niezaÅ‚adowany
j
ół
2.2. Zadanie przydziału
Dana jest macierz c=[cij ]mxn , cij  przydatność i-tego pracownika
do j-tej pracy.
x* = [x* ]m×n "&! takÄ…, że
ij
Wyznaczyć macierz
m n m n
f (x*) =
""c x* = ""c
ij ij ij
maxi=1 j=1 xij
x"&!
i=1 j=1
gdzie
n
Å„Å‚ üÅ‚
ôÅ‚x : m
&! =
òÅ‚ żł
"x = 1, j =1,.., n, "x =1, i =1,.., m, x "{0,1}ôÅ‚
ij ij j
ôÅ‚ ôÅ‚
i=1 j=1
ół þÅ‚
1
Å„Å‚ - gdy i-ty pracownik przydzielony jest do j-tej pracy
x =
òÅ‚0 - w przeciwnym przypadku
j
ół
Zatem zadanie to polega na wyznaczeniu takiego przydziału
pracowników do prac, aby ich sumaryczna przydatność była
maksymalna.
3. Elementy analizy wypukłej
Definicja
Zbiór &! nazywamy wypukłym jeśli dla każdych dwóch punktów
x,y"&! punkt z= ¸Å"x+(1-¸)y należy do &! dla każdego ¸"[0,1].
x z y x z y
&! &!
&! - zbiór wypukły &! - zbiór, który nie jest wypukły
Definicja
Hiperpłaszczyzną Hą w przestrzeni En nazywamy zbiór
{ }
HÄ… = x " En : a, x = Ä…,a " En ,Ä… " R
gdzie - iloczyn skalarny wektorów a oraz x.
Definicja
Hiperpłaszczyzna Hą generuje dwie półprzestrzenie domknięte
- +
{ {
HÄ… = x " En : a, x d" Ä…} HÄ… = x " En : a, x e" Ä…}
Definicja
Zbiorem wielościennym (simpleksem) nazywamy zbiór &! postaci
m
&! = { }
x " En : ai, x d" di
I
i=1
Definicja
Funkcja rzeczywista f określona na wypukłym zbiorze &! nazywa
siÄ™ wypukÅ‚Ä…, jeÅ›li dla każdego x,y"&! oraz dla każdego ¸"[0,1]
spełniona jest nierówność
f (¸Å" x + (1- ¸)Å" y) d" ¸Å"f (x) + (1- ¸)Å"f (y)
Jeśli natomiast spełniona jest nierówność
f (¸Å" x + (1- ¸)Å" y) e" ¸Å"f (x) + (1- ¸)Å"f (y)
to funkcję f nazywamy wklęsłą.
Uwaga: funkcja liniowa f(x)= jest jednocześnie wypukła i
wklęsła.
Twierdzenie
m
Funkcja postaci
F(x) =
" Å"fi(x), i e" 0, i =1,..., m
i
i=1
jest wypukła, jeśli fi(x) są wypukłe, i=1,...,m.
Wniosek
Zbiór postaci
{ }
&! = x " En : A Å" x = d, x e" 0
gdzie A=[aij]mxn jest wypukły.
Sformułujemy dwa zadania:
a. wyznaczyć x*"&!‚"En takie, że
f (x*) = min f (x)
x"&!
gdzie &! - zbiór wypukły, f(" )  funkcja wypukła,
b. wyznaczyć x*"&!‚"En takie, że
f (x*) = max f (x)
x"&!
gdzie &! - zbiór wypukły, f(" )  funkcja wklęsła,
Oba zadania nazywane są w literaturze zadaniami wypukłymi.
Dalej zajmować się będziemy rozwiązywaniem zadań wypukłych.
Najpierw zajmiemy siÄ™ zadaniami liniowymi  zatem zadaniami
wypukłymi.
4. Metody rozwiązywania zadań liniowych
4.1. Zadanie prymalne i zadanie dualne
Przyjmijmy, że postać kanoniczna zadania liniowego jest
nastÄ™pujÄ…ca: wyznaczyć x*"&!‚"En takie, że
f (x*) = c,x* = min c, x
x"&!
gdzie &! = x " En : A Å" x e" d, x e" 0 , A = [aij]m×n
{ }
Zadanie to (tzw. prymalne) jest zadaniem wypukłym, ponieważ
funkcja jest wypukła i zbiór &! jest również wypukły.
Do zadania tego skonstruujemy tzw. zadanie dualne postaci
g(y*) = d,y* = max d, y
{ }
&!'= y " Em : AT Å" y d" c, y e" 0
x"&!
4.2. Przykłady zadań liniowych
Zadanie prymalne
min 2x1 - 5x2 + x3
c = (2,-5,1), x = (x1, x2, x3)
przy ograniczeniach
x + 5x2 - x3 e" 5
Å„Å‚
1 5 -1 5
îÅ‚ Å‚Å‚, d = îÅ‚ Å‚Å‚
ôÅ‚4x1 x2 + 2x3 e" 8
A =
&! = +
ïÅ‚ ïÅ‚
òÅ‚
1
ðÅ‚4 1 2 śł ðÅ‚8śł
ûÅ‚ ûÅ‚
ôÅ‚
x1, x2, x3 e" 0
ół
Zadanie dualne
max 5y1 + 8y2 y = (y1, y2)
przy ograniczeniach y1 + 4y2 d" 2
Å„Å‚
ôÅ‚5y1 + y2 d" -5
&!'=
òÅ‚- y1 + 2y2 d"1
ôÅ‚
y1, y2 e" 0
ół
4.3. Związki między rozwiązaniami prymalnymi i dualnymi
Twierdzenie (zachodzÄ… dwa wykluczajÄ…ce siÄ™ przypadki)
a) Zadanie prymalne oraz zadanie dualne majÄ… rozwiÄ…zania
optymalne odpowiednio x* i y* oraz zachodzi : =
b) Zadanie prymalne oraz zadanie dualne nie mają równocześnie
rozwiązań optymalnych.
Twierdzenie
Dla dowolnych dopuszczalnych rozwiązań x"&! i y "&! zachodzi
e".
Twierdzenie
Jeśli x*"&! i y* "&! oraz zachodzi =, to punkty
x* i y* sÄ… odpowiednio rozwiÄ…zaniami optymalnymi zadania
prymalnego i dualnego.
Twierdzenie
Jeśli zadanie prymalne ma rozwiązanie optymalne x*"&! to
istnieje wierzchołek x"&! zbioru &! taki, że
c, x = c,x* = min c, x
x"&!
Zatem, jeśli zadanie liniowe ma rozwiązanie optymalne, to
wystarczy przeglądać tylko wierzchołki zbioru &!, aby znalez
ć
rozwiązanie będące minimum globalnym na zbiorze &!.
Metody wyznaczania rozwiązań optymalnych zadań liniowych
polegają na ogół na konstrukcji algorytmów przeglądu
wierzchołków wielościanów wypukłych (simpleksów).
4.4. Metoda simpleks
Postać standardowa zadania optymalizacji liniowej
Wyznaczyć x=(x1, x2, x3,..., xn) takie, aby
min f (x) = min{c1x1 + c2x2 + c3x3 + ...+ cnxn}
n-zmiennych
przy ograniczeniach:
a11x1 + a12x2 + a13x3 + ...+ a1nxn = b1
a21x1 + a22x2 + a23x3 + ...+ a2nxn = b2 m-ograniczeń
am1x1 + am2x2 + am3x3 + ...+ amnxn = bm
x1, x2, x3,..., xn e" 0
Przykład.
Wyznaczyć x=(x1, x2, x3) takie, aby
min{f (x) = 2x1 + 4x2 - x3}
Mamy trzy zmienne decyzyjne,
przy ograniczeniach:
dwa ograniczenia (n=3, m=2),
2x1 + 3x2 - 4x3 =10
jednak postać ta jest postacią
standardowÄ….
4x1 - 5x2 + x3 = 5
W tym przypadku na przykład
a11 =2, a13 =-4, a22 =-5, b1 =10 itd.
x1, x2, x3 e" 0
Wszystkie zadani optymalizacji liniowej sprowadzić musimy
przede wszystkim do postaci standardowej.
Sprowadzanie zadań optymalizacji liniowej do postaci
standardowej
a) Jeśli szukamy zmiennych maksymalizujących funkcję
kryterium, to zamieniamy ją na przemnożoną przez (-1)
i wtedy szukamy już zmiennych minimalizujących nową
funkcjÄ™
b) Jeśli mamy ograniczenie typu  e" , to od lewej strony
odejmujemy nowÄ… zmiennÄ…  sztucznÄ… i zamieniamy
nierówność na równość; współczynnik tej nowej zmiennej w
funkcji kryterium wynosi 0 (zero),
c) Jeśli mamy ograniczenie typu  d" , to do lewej strony
dodajemy nową zmienną  sztuczną i zamieniamy nierówność
na równość; współczynnik tej nowej zmiennej w funkcji
kryterium wynosi również 0 (zero).
Przykład
2 1
îÅ‚ Å‚Å‚
A =
ïÅ‚ śł
ðÅ‚1 2ûÅ‚
Załóżmy, że mamy zadanie optymalizacji postaci
c = (1,1)
2
îÅ‚ Å‚Å‚
max f (x) = max{x1 + x2}
b =
ïÅ‚
ðÅ‚2śł
ûÅ‚
przy ograniczeniach:
x2 Czyli rozwiÄ…zaniem tego
2x1 + x2 d" 2
zadania jest wektor
2
x=(2/3,2/3)
x1 + 2x2 d" 2
x1, x2 e" 0
f (x)=(1,1)-gradient
Gradient funkcji:
1
df (x) d(x1 + x2) x=(x1, x2)=(2/3,2/3)
= = 1
dx1 dx1
df (x) d(x1 + x2)
= = 1
dx2 dx2
12
x1
Przykład (cd.)
Sprowadz
my zadanie do postaci standardowej
Najpierw zamieniamy  max na  min mnożąc funkcje przez  1
max{x1 + x2} = min{-x1 - x2 + 0Å" x3 + 0Å" x4}
Zmieniamy ograniczenia
2
c = (-1,-1,0,0)
îÅ‚ Å‚Å‚
b =
2x1 + x2 + x3 = 2
ïÅ‚
ðÅ‚2śł
ûÅ‚
2 1 1 0
îÅ‚ Å‚Å‚
A =
x1 + 2x2 + x4 = 2
ïÅ‚1 2 0 1śł
x1
îÅ‚ Å‚Å‚
ðÅ‚ ûÅ‚
ïÅ‚x2śł
x1, x2 e" 0
x =
ïÅ‚x śł
ïÅ‚x3śł
ðÅ‚ 4ûÅ‚
min c, x
Zapis wektorowo-macierzowy
A Å" x = b x e" 0
Przykład (cd.)
Szukamy pierwszego rozwiÄ…zania  bazowego , tzn. takiego,
które spełnia układ równań, ale niekoniecznie jest optymalnym.
Dla nas takim rozwiÄ…zaniem jest wektor x=(0,0,2,2)
2x1 + x2 + x3 = 2
pierwsze zmienne bazowe
x1 + 2x2 + x4 = 2
A
atwo zauważyć, że
x1 = 0, x2 = 0, x3 = 2, x4 = 2
jest rozwiązaniem dopuszczalnym, więc bazowym.
Przykład
0
îÅ‚ Å‚Å‚
2 4 1 0 0
îÅ‚ Å‚Å‚
0
ïÅ‚ śł
ïÅ‚7 3 0 1 0śł
A =
ïÅ‚ śł
b1
ïÅ‚0 5 0 0 1śł x =
ðÅ‚ ûÅ‚
ïÅ‚b2śł
ïÅ‚b śł
3
ðÅ‚ ûÅ‚
sugestia rozwiÄ…zania bazowego
Metoda simpleks  tablica metody simpleks
ci
-1 -1 0 0
Zmienne
cB h0 h1 h2 h3 h4
bazowe
x3 0 2 2 1 1 0
x4 0 2 1 2 0 1
-1 -1 0 0
współczynniki
współczynniki funkcji kryterium (np. bazowych)
wartości aktualne zmiennych bazowych
współczynniki (pierwotnie macierz A)
obliczane współczynniki: ci  cB " hi
Metoda simpleks  tablica metody simpleks (cd.)
ci
-1 -1 0 0
Zmienne
cB h0 h1 h2 h3 h4
bazowe
x3 0 2 2 1 1 0 h0/h2=2/1=2
x4 0 2 1 2 0 1 h0/h2=2/2=1
min
-1 -1 0 0
współczynniki
min
Warunek wejścia do bazy (nowej zmiennej): min{współczynnika}
(mógł być też pierwszy, wybieramy z równych  według woli )
Ta kolumna (h2) teraz jest dla nas podstawą wyjścia zmiennej
bazowej z bazy
Warunek wyjścia z bazy (starej zmiennej bazowej): dzielimy h0/hi
i szukamy wartości minimalnej.
ci
-1 -1 0 0
Zmienne
cB h0 h1 h2 h3 h4
bazowe
SÄ… ujemne,
x3 0 2 2 1 1 0
zatem jeszcze
nie mamy
rozwiÄ…zania
x4 0 2 1 2 0 1
optymalnego
-1 -1 0 0
współczynniki
ci
zamiana
-1 -1 0 0
Zmienne
cB h0 h1 h2 h3 h4
bazowe
Nadal istniejÄ…
ujemne, zatem
x3 0 1 3/2 0 1 -1/2
nadal nie
mamy
x2 -1 1 1/2 1 0 1/2
rozwiÄ…zania
optymalnego
-1/2 0 0 1/2
współczynniki
Jak wyznaczamy nowe współczynniki tabeli simpleks?
ci
-1 -1 0 0
Zmienne
cB h0 h1 h2 h3 h4
bazowe
x3 0 2 2 1 1 0
x4 0 2 1 2 0 1
-1 -1 0 0
współczynniki
Wszystkie wyrazy (bez niebieskiego)
dzielimy przez wartość pola czerwonego
Wszystkie wyrazy (bez niebieskiego)
innych wierszy obliczamy:
np. nowe a11= a11-(a12 a21/ a22)
obliczane współczynniki: ci  cB " hi
ci
-1 -1 0 0
Zmienne
cB h0 h1 h2 h3 h4 Nadal istniejÄ…
bazowe
ujemne, zatem
nadal nie
x3 0 1 3/2 0 1 -1/2
mamy
rozwiÄ…zania
x2 -1 1 1/2 1 0 1/2
optymalnego
-1/2 0 0 -1/2
współczynniki
ci
-1 -1 0 0
Zmienne
cB h0 h1 h2 h3 h4 IstniejÄ…
bazowe
jedynie
x1 -1 2/3 1 0 2/3 -1/3
dodatnie,
zatem mamy
rozwiÄ…zanie
x2 -1 2/3 0 1 -1/3 2/3
optymalne
0 0 1/3 1/3
współczynniki
W ostatniej tabeli otrzymaliśmy:
x=(x1, x2, x3, x4)=(2/3, 2/3, 0, 0)
zatem szukane przez nas rozwiÄ…zanie bez zmiennych sztucznych:
x=(x1, x2)=(2/3, 2/3)
natomiast wartość funkcji kryterium f(x)= x1+x2=2/3 + 2/3=4/3