Wykład III Ekonometria
Optymalizacja jest to postępowanie polegające na wyborze elementu z danego zbioru w oparciu o relacje, ustalające pewien porządek w tym zbiorze
* Zmienne decyzje
* Zbiór rozwiązań dopuszczalnych
* Wsk. Jakości lub funkcja celu
Zadanie optymalizacji zo (programowania matematycznego)
max f(x)
x є ZR
x- n wymiarowy wektor zmiennych decyzyjnych czyli xє Rn
ZR- zbiór rozwiązań dopuszczalnych
f- funkcja celu (wskaźnik jakości) Rn→R1 →jednowymiarowy
Klasyfikacja zo:
Ograniczenia
* Zadanie optymalizacji bez ograniczeń- jeżeli ZR = Rn
max f(x)
xє Rn
* Zadanie optymalizacji z ograniczeniami jeżeli Ze< Rn
Funkcja celu i funkcja ograniczeń:
* Zadanie optymalizacji liniowej – f(x) i wszystkie funkcje gi (x) są liniowe
* Zadanie optymalizacji nieliniowej – f(x)lub przynajmniej jedna z funkcji gi(x) jest nieliniowa
Klasyfikacja zo
Zmienne decyzyjne:
* Ciągłe zadanie optymalizacji- zmienne decyzyjne mogą przyjmować wartości rzeczywiste
* Dyskretne zadanie optymalizacji- zmienne decyzyjne mogą przyjmować wartości ze zbioru skończonego lub przeliczalnego (np. programowanie całkowitoliczbowe)
Czas:
* Optymalizacja statyczna- wartości liczbowe
* Optymalizacja dynamiczna- funkcji czasu
Liczba funkcji celu
* Jednokryterialne zadanie optymalizacji- w zadaniu występuje jedna funkcja celu
* Wielokryterialne zadanie optymalizacji- w zadaniu występuje kilka funkcji celu
Zadanie bez ograniczeń:
max f(x)
xє Rn
* Rozwiązanie analityczne
Warunek konieczny istnienia ekstremum
…
max (-x21 +2x1-3x2 – 2x22)
x1,x2єR
max (-x21+ 2x1-3x2-2x22)
40 – 2x1-3x2≥0
20-8x1-x2≥0
* Przykład 1: min x1,x2єR(x21-2x1+x22-6x2)
x1=1
x2=3
df/dx1=2x1-2=0
df/dx2=2x2-6=0
* Przykład 2: max x1,x2єR x1*e-x21-x22
df/dx1=1e-x21-x22+x1e-x21-x22 (-2x1)=o
df/dx2=x1e-x21-x22(-2x2)=0
* Algorytmy optymalizacji nieliniowej bez ograniczeń
Zadanie z ograniczeniami
max f(x) xє Rn={xi gi(x)≥0, i=1,…,m}
Gdzie gi Rn→R1 dla i=1,…,m są funkcja ograniczeń
* Rozwiązanie analityczne- warunki Kuhna- Tuckera
* Funkcja Lagrange’a :L(x,l)= f(x) + <l, g(x)>
* Rozwiązaniem jest, x0, dla którego istnienia l0 takie, że
· Rozwiązanie analityczne
Max (150*x1+100*x2)
0,5*x1+1*x2≤90
xT=[x1,x2]
0,5 1
A=
2 1
2*x1+1*x2≤240
cT=[150,100]
x1≥0,x2≥0
cT=[90,240
L(x,l)=150x1+100x2+l1*(90-0,5*x1-x2)+l2(240-2x1-x2)
Dl(x,l)/dx1=150-0,5l1-2l2
l1=100/3=33,33
Dl(x,l)/dx2=100=l1-l2
l2=200/3=66,67
l1*dl(x,l)/dl1=33,33(90-0,5*x1-x2)
x1=100
l2*dl(x,l)/dl2=66,67(240-2*x1-2*x2)
x2=40
· Algorytmy optymalizacji nieliniowej z ograniczeniami
Zadanie programowania liniowego
· Postać klasyczna ZPL
Zysk
Plastik
Drewno
X1: zabawka 1
32
3
1
X2: zabawka2
22
2
2
60 40
Algorytm sympleksów:
ü Sympleks- wielościan wypukły rozpięty na n+1 wierzchołkach w przestrzeni Rn
ü Można udowodnić, ze rozwiązaniem ZPL jest jeden z wierzchołków wielościanu rozpiętego na ograniczeniach
ü Metoda sympleksów polega na wyznaczaniu kolejnych wierzchołków i sprawdzaniu, czy uzyskano rozwiązanie optymalne. Każde kolejne rozwiązanie jest nie gorsze od poprzedniego.
Dualizm w programowaniu liniowym- w tym programowaniu można sformułować z symetryczne zadania
Prymarne ZPL Dualne ZPL
max cTx min bTy
przy ograniczeniach
Ax ≤b ATy ≥c
...