prezentacja

Report
Optymalizacja liniowa
Andrzej Torój, Ekonometria
Problem decyzyjny
Która decyzja (z tych możliwych do
podjęcia) jest najlepsza?
co to znaczy
„decyzja”?
zmienne decyzyjne
X1, X2, ..., Xn
kiedy decyzja jest
możliwa do
podjęcia?
warunki
ograniczające
decyzja:
x*=(x1*, x2*, ..., xn*)
co to znaczy
„najlepsza”?
funkcja celu
max
zbiór decyzji
dopuszczalnych
Andrzej Torój, Ekonometria
min
kryterium
optymalizacji
Przykład
Kubuś Puchatek lubi miód i chce go jeść jak najwięcej. Niestety, musi
sobie na tę przyjemność zapracować. Są dwie możliwości: hodowanie
pszczółek w ulu w ogródku lub zakup miodu w sklepie za pieniądze
otrzymane za brawurową rolę w kreskówce. Za każdą godzinę opieki
dziennie pszczoły odwdzięczają mu się 0,2 l miodu. Praca pozwala
Kubusiowi zarobić 5 zł za godzinę, a miód w sklepie kosztuje 10 zł za
litr.
Kubuś jest leniwym misiem i nie może pracować (czy to zarobkowo, czy
przy ulu) dłużej niż 8 godzin dziennie. Kubuś nie spędzi jednak na
planie dłużej niż 5 godzin dziennie, bo będzie tęsknił za Prosiaczkiem i
zechce wrócić do domu. Pszczoły po 7 godzinach z Kubusiem mają go
dość i zaczynają go atakować.
Jak zachowa się Kubuś, by mieć jak najwięcej miodu do dyspozycji?
Andrzej Torój, Ekonometria
Zmienne decyzyjne
• x1 – czas pracy w serialu
• x2 – czas pracy przy ulu
Decyzja
x*=(x1*,x2*)
Andrzej Torój, Ekonometria
Funkcja celu
• cel: maksymalizacja konsumpcji miodu
• f(x)=f(x1,x2) → max
• Jak czas pracy przekłada się na ilość miodu do dyspozycji?
– 1 h z pszczołami to 0,2 l miodu
– 1 h na planie serialu to 5 zł, a 1 l miodu kosztuje 10 zł
– stąd ilość miodu do dyspozycji Kubusia (w litrach) zależy od
jego decyzji w następujący sposób:
5/10 *x1 + 0,2*x2
• funkcja celu: f(x1,x2)=0,5x1+0,2x2
Andrzej Torój, Ekonometria
Warunki ograniczające
(1)
(2)
(3)
(4)
(5)
x1 + x 2 ≤ 8
x1 ≤ 5
x2 ≤ 7
x1 ≥ 0
x2 ≥ 0
warunki nieujemności
Andrzej Torój, Ekonometria
Ilustracja graficzna (1)
(2)
(3)
(4)
(5)
x2
8
7
zbiór decyzji
dopuszczalnych (D)
5
8
Andrzej Torój, Ekonometria
x1 + x2 ≤ 8
x1 ≤ 5
x2 ≤ 7
x1 ≥ 0
x2 ≥ 0
x1
Gdzie jest decyzja optymalna?
f(x1,x2) = 2
x2
10
decyzja
optymalna!
7
f(x1,x2) = 0,5 x1 + 0,2 x2
Warstwica funkcji celu:
f(x1,x2) = 1
f(x1,x2) = 2
f(x1,x2) = 1
itd.
5
2
4 5
 f ( x1 , x2 ) f ( x1 , x2 ) 
f  
,
  0,5 0,2
x2 
 x1
Andrzej Torój, Ekonometria
Gradient funkcji celu:
kierunek najszybszego
wzrostu jej wartości;
pochodna funkcji celu
względem zmiennych
decyzyjnych
10
x1
Warunki luźne i napięte
warunki napięte
x2
(spełnione dla
rozwiązania optymalnego
jako równość)
8
7
(1)
(2)
(3)
(4)
(5)
x1 + x2 ≤ 8
x1 ≤ 5
x2 ≤ 7
x1 ≥ 0
x2 ≥ 0
warunki luźne
5
8
Andrzej Torój, Ekonometria
(spełnione dla
x1
rozwiązania optymalnego
jako nierówność ostra)
Decyzja optymalna
Decyzja x* jest optymalna, jeżeli:
• jest decyzją dopuszczalną, tzn. x*  D
• f(x*) ≥f(x) dla dowolnej decyzji x  D
przy maksymalizacji funkcji celu
ALBO
f(x*) ≤ f(x) dla dowolnej decyzji x  D
przy minimalizacji funkcji celu
Andrzej Torój, Ekonometria
Zadanie programowania liniowego (PL)
szczególny przypadek zadania programowania matematycznego
1.
wszystkie zmienne decyzyjne ciągłe
2.
wszystkie warunki ograniczające w postaci równań lub słabych
nierówności liniowych
a11 x1  a12 x2  ...  a1n xn  b1
a21 x1  a22 x2  ...  a2 n xn  b2
...
am1 x1  am 2 x2  ...  amn xn  bm
3.
x1  0, x2  0,..., xn  0
funkcja celu liniową funkcją zmiennych decyzyjnych
f x1, x2 ,...,xn   c1x1  c2 x2  ... cn xn  max
Andrzej Torój, Ekonometria
Możliwe wyniki – rozwiązanie
optymalne istnieje
x2
x2
jedno rozwiązanie optymalne
x1
x1
alternatywne rozwiązania optymalne
Andrzej Torój, Ekonometria
Możliwe wyniki – rozwiązanie
optymalne nie istnieje
x2
x2
x1
zadanie sprzeczne
x1
funkcja celu
nieograniczona z góry
(z dołu)
Andrzej Torój, Ekonometria
Własności zadań PL (1)
1. Jeżeli zbiór D jest niepusty i ograniczony, to
istnieje rozwiązanie optymalne.
2. W zadaniu PL o nieujemnych zmiennych
decyzyjnych i niepustym zbiorze rozwiązań
optymalnych przynajmniej jeden wierzchołek
zbioru D jest rozwiązaniem optymalnym.
3. Zbiór rozwiązań dopuszczalnych i rozwiązań
optymalnych zadania PL są zbiorami wypukłymi.
4. Wynik procesu rozwiązywania zadania PL nie
ulega zmianie przy zastąpieniu funkcji celu f(x)
funkcją af(x) (gdy a jest dowolną liczbą dodatnią)
lub f(x)+b (gdy b jest ustaloną liczbą rzeczywistą).
Andrzej Torój, Ekonometria
Własności zadań PL (2)
5. Wynik procesu rozwiązywania zadania PL nie ulega zmianie
przy zastąpieniu funkcji celu f(x) funkcją -f(x) i jednoczesnej
zmianie kryterium optymalizacji na przeciwne.
f x1, x2 ,...,xn   max   f x1 , x2 ,...,xn   min
6. Wierzchołek x* niepustego zbioru rozwiązań dopuszczalnych
D jest rozwiązaniem optymalnym zadania PL z
maksymalizacją funkcji celu f(x) wtedy i tylko wtedy, gdy dla
każdego rozwiązania dopuszczalnego x na prostej warunku
napiętego w x* zachodzi f(x*) ≥ f(x).
7. Wierzchołek x* niepustego i ograniczonego zbioru rozwiązań
dopuszczalnych D jest rozwiązaniem optymalnym zadania
PL z maksymalizacją funkcji celu f(x) wtedy i tylko wtedy, gdy
dla każdego sąsiedniego wierzchołka x  D zachodzi
f(x*) ≥ f(x).
Andrzej Torój, Ekonometria
Solver
Narzędzia/Dodatki...
2007/2008 Z
Andrzej Torój, Ekonometria
wybieramy kryterium
optymalizacji funkcji celu:
maksimum, minimum lub
osiągnięcie konkretnej
wartości
tutaj wpisujemy adres komórki
zawierającej formułę funkcji celu;
formuła powinna zawierać zmienne
decyzyjne zdefiniowane w innych,
zmienianych przez program
komórkach
tutaj
wpisujemy
adres
zakresu
zmiennych
decyzyjnych
naciskając „Dodaj”, przechodzimy do okna
definiowania warunku ograniczającego po lewej stronie wpisujemy adres
komórki zawierającej funkcję
zmiennych decyzyjnych; w środku
– charakter ograniczenia; po
prawej – wyraz wolny warunku
ograniczającego
2007/2008 Z
Andrzej Torój, Ekonometria
Opcje…
ustawiamy parametry dla
algorytmu poszukującego
rozwiązania (kiedy ma uznać,
że je już znalazł)
jeżeli model jest liniowy,
zaznaczenie tego pola
upraszcza proces
obliczeniowy (UWAGA!
model liniowy, ale
zapisany w sposób
nieliniowy, np.
ograniczenie x1/x2 = 1,
zostanie odrzucone,
należy zapisać x1=x2)
zaznaczenie w tym miejscu
zwalnia nas z konieczności
dodawania wszystkich
warunków nieujemności do
zbioru warunków
ograniczających
2007/2008 Z
Andrzej Torój, Ekonometria
ustalamy, jaki dokładnie
algorytm ma szukać
rozwiązania
Zadanie programowania liniowego –
pytania...
f x1, x2 ,...,xn   c1x1  c2 x2  ... cn xn  max
czy po zmianie
współczynnika
funkcji celu obecne
rozwiązanie
optymalne nadal
będzie optymalne?
a11 x1  a12 x2  ...  a1n xn  b1
a21 x1  a22 x2  ...  a2 n xn  b2
...
czy zmiana wyrazu
wolnego sprawi,
że zestaw
warunków
napiętych zmieni
się?
am1 x1  am 2 x2  ...  amn xn  bm
x1  0, x2  0,..., xn  0
jak wpłynie na rozwiązanie optymalne
usunięcie/dodanie jednego warunku
ograniczającego?
jak zmiana wyrazu wolnego warunku
ograniczającego wpłynie na optymalną
wartość funkcji celu (cena dualna)?
Andrzej Torój, Ekonometria
Problem Kubusia Puchatka przypomnienie
x2
f(x1,x2)=0,5x1+0,2x2
8
7
(1)
(2)
(3)
(4)
(5)
f ( x1 , x2 )  0,5 0,2
5
Andrzej Torój, Ekonometria
8
x1 + x 2 ≤ 8
x1 ≤ 5
x2 ≤ 7
x1 ≥ 0
x2 ≥ 0
x1
Zmiana współczynnika funkcji celu (1)
• w naszym przypadku:
– zmiana wydajności
pszczół (0,2 l
miodu na godzinę
pracy Kubusia)
– zmiana płacy
realnej w serialu
(0,5 l miodu za
godzinę)
8
7
f ( x1 , x2 )  0,5 0,7
f ( x1 , x2 )  0,5 0,5
f ( x1 , x2 )  0,5 0,2
5
Andrzej Torój, Ekonometria
8
Zmiana współczynnika funkcji celu (2)
f ( x1 , x2 )  0,5x1  (0,2  c2 ) x2
dla rozwiązania optymalnego (x1,x2)=(5,3):
f (5,3)  0,5  5  (0,2  c2 )  3  3,1  3  c2
dla sąsiednich wierzchołków:
f (5,0)  0,5  5  (0,2  c2 )  0  2,5
(x1,x2)=(5,0):
f (7,1)  0,5 1  (0,2  c2 )  7  1,9  7  c2
(x1,x2)=(1,7):
Decyzja (x1,x2)=(5,3) pozostanie optymalna tak
długo, jak spełnione będą warunki:
f (5,3)  f (5,0)  f (5,3)  f (7,1)
3,1  3  c2  2,5  3,1  3  c2  1,9  7  c2
c2  0,2  c2  0,3
c2  (0;0,5)
– przedział stabilności c2
Andrzej Torój, Ekonometria
Zmiana wyrazu wolnego warunku
ograniczającego (1)
w naszym przypadku:
• zmiana poziomu
pracowitości Kubusia
(mało prawdopodobna
)
8
7
•zmiana odporności
Prosiaczka na
tęsknotę za Kubusiem
(jeszcze mniej
prawdopodobna  )
• zmiana odporności
pszczół na obecność
Kubusia
5
Andrzej Torój, Ekonometria
8
Zmiana wyrazu wolnego warunku
ograniczającego (2)
• jeżeli prostą 0*x1+1*x2=7 przesuniemy dowolnie
wysoko (0*x1+1*x2=7+b1, b1>0), rozwiązanie
optymalne nie zmieni się
• jeżeli przesuniemy ją tak, by „przechodziła przez”
dotychczasową decyzję optymalną (0*x1+1*x2=7+b1
dla x1=5, x2 =3, stąd
b1=-4), decyzja optymalna nie zmieni się, ale
warunek tej prostej stanie się napięty
• gdy b1<-4, zmieni się decyzja optymalna i zbiór
warunków napiętych (przestanie być napięty
warunek oznaczony zieloną linią)
Andrzej Torój, Ekonometria
Zmiana wyrazu wolnego warunku
ograniczającego (3)
• struktura bazowa rozwiązania optymalnego – zbiór napiętych warunków
ograniczających
• przedział stabilności struktury bazowej rozwiązania optymalnego
względem wyrazu wolnego bi – przedział zmienności bi, w którym nie
nastąpi zmiana zestawu warunków napiętych
– dla warunku luźnego – pytanie podobne do tego, jakie stawialiśmy
sobie przy zmianie współczynnika funkcji celu (jak wielka zmiana
możliwa bez zmiany decyzji optymalnej?)
– dla warunku napiętego takie pytanie nie miałoby w gruncie rzeczy
sensu (każde przesunięcie linii ograniczenia powodowałoby zmianę
decyzji optymalnej)
Andrzej Torój, Ekonometria
Zmiana wyrazu wolnego warunku
ograniczającego (4)
8
(1)
(2)
(3)
x1 + x 2 ≤ 8
x1 ≤ 5
x2 ≤ 7
(1)
5 ≤ b1 ≤ 12
1 ≤ b2 ≤ 8
3 ≤ b3
7
(2)
(3)
3
5
8
Andrzej Torój, Ekonometria
przedziały stabilności
struktury bazowej
rozwiązania
optymalnego
Cena dualna (1)
• jak wpływa zmiana wyrazu wolnego warunku
ograniczającego na wartość funkcji celu?
warunek luźny
ZAŁOŻENIE: struktura bazowa
rozwiązania optymalnego nie ulegnie
modyfikacji
f ( x1 , x2 )  0
cena dualna wynosi 0
cena dualna to przyrost (spadek)
optymalnej wartości funkcji celu
spowodowany jednostkowym
przyrostem (spadkiem) wyrazu
wolnego jednego z warunków
ograniczających przy założeniu, że
struktura bazowa rozwiązania
optymalnego nie zostanie zmieniona
warunek napięty
ZAŁOŻENIE: struktura bazowa
rozwiązania optymalnego nie ulegnie
modyfikacji
założenie pozwala nam uznać, że te
same warunki pozostaną napięte (np.
warunek (1) i (2) ); zapisujemy warunki
spełniane przez nową decyzję
optymalną:
a11 x1  a12 x2  b1
a21 x1  a22 x2  b2  b2
rozwiązujemy ze względu na x1 i x2
(obie zmienne decyzyjne będą funkcją
b2), a następnie podstawiamy do funkcji
celu:
f ( x1 , x2 )  f (b2 )  c  d  b2
d jest ceną dualną
Andrzej Torój, Ekonometria
Cena dualna (2)
• w przypadku problemu Kubusia Puchatka:
(1)
(2)
(3)
x 1 + x2 ≤ 8
x1 ≤ 5
x2 ≤ 7
warunek (1) jest napięty
warunek (2) jest napięty
x1  x2  8  b1
x1  x2  8
x1  5
x1  5  b2
x1  5
x1  5  b2
x2  3  b1
x2  3  b2
f ( x1 , x2 ) 
f ( x1 , x2 ) 
 0,5  5  0,2  (3  b1 ) 
 0,5  (5  b2 )  0,2  (3  b2 ) 
 3,1  0,2  b1
 3,1  0,3  b2
cena dualna dla warunku (1) = 0,2
warunek (3) jest luźny
cena dualna dla warunku
(3) = 0
cena dualna dla warunku (2) = 0,3
Andrzej Torój, Ekonometria
Co się stanie, gdy dodamy nowy
warunek?
• jeżeli dotychczasowa decyzja optymalna spełnia ten
warunek, pozostanie ona optymalna; w przeciwnym razie
szukamy nowego rozwiązania (o ile zbiór rozwiązań
dopuszczalnych nie stał się pusty!)
Co się stanie, gdy usuniemy warunek?
• jeżeli warunek był luźny, dotychczasowe rozwiązanie
pozostaje optymalne; jeżeli był napięty, musimy rozwiązać
zadanie ponownie
Andrzej Torój, Ekonometria
Uwagi końcowe
• zasada ceteris paribus: przedziałów stabilności
współczynników funkcji celu nie można
rozpatrywać łącznie
• analiza pooptymalizacyjna dotyczy zagadnień
ze zmiennymi ciągłymi
Andrzej Torój, Ekonometria
Zadania – podstawowe typy
Andrzej Torój, Ekonometria
1. Dieta
Andrzej Torój, Ekonometria
1. Dieta (c.d.)
• wyróżnione są składniki (m) diety oraz ich
maksymalne i minimalne dawki
• składniki dostępne są w produktach (n), dla każdego
produktu znana jest jego cena (c) i zawartość
składnika (b)
• należy znaleźć najtańszą mieszankę produktów
zawierającą odpowiednie ilości składników
• klasyczne zagadnienie diety – jedynie
dawki minimalne, nieograniczony
zbiór rozwiązań dopuszczalnych,
ale przy dodatnich cenach i kryterium
minimalizacji – istnieje rozw. opt.
Andrzej Torój, Ekonometria
2. Portfel inwestycyjny
Andrzej Torój, Ekonometria
2. Portfel inwestycyjny
• poszukujemy optymalnej struktury portfela inwestycyjnego:
• jak najmniejsze ryzyko przy zadanej oczekiwanej stopie zwrotu
• jak najwyższa oczekiwana stopa zwrotu przy zadanym
oczekiwanym poziomie ryzyka
• zmienne decyzyjne: udział poszczególnych rodzajów aktywów w
portfelu (%); ograniczenie budżetowe: ich suma równa 1
• limity prawne dla udziału poszczególnych aktywów (np. max. udział
akcji, aktywów zagranicznych itp.)
• założenie o doskonałej podzielności aktywów i płynności rynku
• oczekiwana stopa zwrotu z portfela: średnia ważona z oczekiwanych
stóp zwrotu poszczególnych jego elementów
• założenie o NIEZALEŻNOŚCI stóp zwrotu poszczególnych aktywów
(?)
Andrzej Torój, Ekonometria
3. Harmonogram
Andrzej Torój, Ekonometria
3. Harmonogram
• decydujemy o liczbie pracowników
rozpoczynających pracę o różnych porach
• zadanie ze zmiennymi dyskretnymi (np. liczby
naturalne) – trudniejsze do rozwiązania
Andrzej Torój, Ekonometria
4. Mieszanka
Andrzej Torój, Ekonometria
4. Mieszanka
• mieszamy składniki; każdy z nich ma swoją cenę
• mieszanka musi być jak najtańsza i spełnić
jednocześnie określone wymagania
Andrzej Torój, Ekonometria
5. Zagadnienie transportowe
Andrzej Torój, Ekonometria
5. Zagadnienie transportowe
• produkt zmagazynowany u m dostawców należy dostarczyć do n
odbiorców; ile jednostek produktu przewieźć od i-tego dostawcy
(i=1,...,m) do j-tego odbiorcy (j=1,...,n) by spełnić wymagania odbiorców
•n*m zmiennych decyzyjnych
• należy tak ustalić plan transportu, by zminimalizować jego łączny koszt
(znany jednostkowy koszt transportu od i-tego dostawcy do j-tego
odbiorcy)
• zagadnienie jest zbilansowane, gdy początkowy
zasób u dostawców równy zapotrzebowaniu
odbiorców (warunki ograniczające: równości)
•niezbilansowane, gdy podaż lub popyt mniejsze
(nierówności wśród warunków ograniczających)
•gdy towar jest niepodzielny, nie ma konieczności
uwzględniania całkowitoliczbowości zmiennych
Andrzej Torój, Ekonometria
6. Przydział
Andrzej Torój, Ekonometria
6. Przydział
• m zadań do wykonania i m pracowników, którzy
mogą je wykonać; każdy pracownik otrzymuje
dokładnie jedno zadanie
• zadań może być więcej niż pracowników (wtedy
wśród warunków ograniczających nierówności)
• minimalizujemy koszt realizacji zadań lub łączną
efektywność
• wszystkie zmienne decyzyjne są
binarne; warunek ten można zastąpić
warunkiem xij≥0 (na podstawie
analogicznej własności zagadnienia
transportowego)
Andrzej Torój, Ekonometria
Praca domowa
• Przykłady i zadania do rozdziałów
– 11
– 12
– 13
Andrzej Torój, Ekonometria

similar documents