E. Michlowicz: Metody optymalizacji......(wyk1)..
Wykład 3
OPTYMALIZACJA
1. Ogólna postać zadania optymalizacyjnego
Nale\
y zoptymalizować funkcję z(x):
z(x) = f(x1, x2, ....xi .... xn) => max, min
gdzie: x = (x1, x2, ....xi .... xn)  zmienne decyzyjne
przy ograniczeniach:
gi (x1, x2, xj,.... xm) e"
e" 0
e"
e"
xi e" e" 0;
e" 0; xj e"
e" e"
e" e"
i = 1, 2, ....n; j = 1, 2, ....m
RozwiÄ…zanie:
1. Metody graficzne
2. Klasyczne  analityczne - metody optymalizacji
" obliczenia ró\
niczkowe ( min bez ograniczeń)
" mno\
niki Lagrange a (ekstremum warunkowe  ograniczenia równościowe),
" teoria Kuhna  Tuckera (ograniczenia nierównościowe).
3. Metody programowania matematycznego
" programowanie liniowe,
" programowanie nieliniowe (kwadratowe, geometryczne),
" dualne.
4. Metody wariacyjne
5. Metody numeryczne
" enumeracyjne (przeglÄ…dowe),
" statystyczne (Monte Carlo),
" deterministyczne (poszukiwań)
" optymalizacja bez ograniczeń,
" optymalizacja z ograniczeniami.
1
E. Michlowicz: Metody optymalizacji......(wyk1)..
6. Algorytmy ewolucyjne (genetyczne)
Ró\
norodność metod optymalizacji powoduje to, i\
nie istnieje jeden uniwersalny sposób,
mogący rozwiązywać szereg zagadnień. Ka\
da z metod posiada swoje zalety, ale równie\
nie jest
pozbawiona wad, które dyskwalifikują ją w wielu sytuacjach.
Parametry procesu optymalizacji zale\
Ä… od specyfiki rozpatrywanej funkcji. Mo\
e
zaistnieć irracjonalny problem optymalizacji metod optymalizacji, czyli dopasowania takiej
metody, aby wynik otrzymać jak najmniejszym kosztem.
Jako kryteria doboru algorytmu optymalizacji często przyjmuje się:
" dokładność przybli\
ania wyznaczona przy ocenie:
o miary zbioru poziomicowego otaczajÄ…cego ekstremum,
o odległości od poszukiwanego ekstremum,
o przybli\
enia wartości funkcji w poszukiwanym ekstremum,
" odporność na ekstrema lokalne,
" koszt symulacji.
Wśród metod optymalizacji szczególne miejsce zajmują algorytmy Inteligentnych
Systemów Wspomagania Decyzji (ISWD), czyli algorytmy oparte na idei sieci neuronowych,
ewolucyjnych i genetycznych.
Mają one szczególne zastosowanie, gdy wiedza o optymalizowanym problemie jest
bardzo nikła. Algorytm genetyczny jest często zwany  metodą ostatniej szansy .
Zadania programowania liniowego (ZPL) są modelami zadań programowania
dyskretnego, czyli poszukują rozwiązania ekstremalnego funkcji opisanej na spójnym zbiorze
(dziedzinie) utworzonym z izolowanych punktów.
2. Zagadnienia programowania liniowego
Programowanie liniowe (matematyczne) to jedna z metod optymalizacyjnych
rozwiązywania problemów optymalizacji. Bazuje ona na ściśle określonym modelu
rzeczywistości, budowanym przy określonych warunkach.
Z matematycznym liniowym modelem optymalizacyjnym mamy do czynienia wtedy, kiedy
równania i nierówności modelu opisujące rzeczywistość mają charakter liniowy.
2
E. Michlowicz: Metody optymalizacji......(wyk1)..
Ogólna postać tego zadania
Wyznaczyć wartość ekstremalną funkcji celu z ( x ):
T
z (x ) = c x
przy warunkach (ograniczeniach):
Ax " b
x e" 0
gdzie:
z (x) - funkcja celu (kryterium),
x - wektor kolumnowy zmiennych decyzyjnych,
A - macierz współczynników przy zmiennych decyzyjnych o wymiarach - m n -,
przy czym m < n oraz rzędzie macierzy rzA = m, co oznacza, \
e wiersze
macierzy sÄ… liniowo niezale\
ne,
c - n wymiarowy wektor kolumnowy współczynników funkcji celu,
b - m wymiarowy wektor kolumnowy wyrazów wolnych ograniczeń zwany
prawymi stronami ograniczeń,
- oznacza relacjÄ™ typu d" e"
d", e" lub =.
d" e"
d" e"
Zagadnienie programowania liniowego posiada cztery postaci w zale\
ności od relacji .
" Postać standardowa I typu, je\
eli zale\
ność jest opisana wzorem:
Ax d" b
" Postać standardowa II typu dla przypadku, gdy:
Ax e" b
" Postać kanoniczna dla:
Ax = b
" Postać mieszana dla zale\
ności:
3
E. Michlowicz: Metody optymalizacji......(wyk1)..
A x d" b
1 1
A x = b
2 2
A x e" b
3 3
gdzie:
" macierz A jest macierzÄ… blokowÄ… postaci:
A
îÅ‚ Å‚Å‚
1
ïÅ‚ śł
A = A
2
ïÅ‚ śł
ïÅ‚ śł
A
ðÅ‚ 3 ûÅ‚
b
a wektor jest postaci:
b1
îÅ‚ Å‚Å‚
ïÅ‚ śł
b = b
2
ïÅ‚ śł
ïÅ‚ śł
b
ðÅ‚ 3 ûÅ‚
Równanie to określane jest jako warunek brzegowy.
3. METODA MNOśNIKÓW LAGRANGE A
Metoda pośrednia  wyznaczanie ekstremum warunkowego przy
ograniczeniach równowartościowych
Ogólna postać funkcji celu:
z(x) = f(x1, x2, ....xi .... xn)
i=1, n
ograniczenia:
g1 = g1 (x1, x2, xj,.... xm)
g2 = g2 (x1, x2, xj,.... xm)
.......................
gm = gm (x1, x2, xj,.... xm)
4
E. Michlowicz: Metody optymalizacji......(wyk1)..
j=1,..m
Ka\
de z ograniczeń g(x) mno\
ymy przez stałe mno\
niki nieoznaczone 
i dodajemy do funkcji celu z(x);
stÄ…d otrzymujemy:
m
"
L = z (x1, x2, x3, ...... xn) +
+
+ j
+ * gi (x1, x2, x3, ...... xm)
j
j
j
j=1
RozwiÄ…zanie:
m
" L
"g
"z
j

"
= + * = 0
j
"x
" x "x
i i
j
j
........................................
" L
= 0
" 
j

INTERPRETACJA
efekt krańcowy optymalizacji zwiększy się o parametr 
w odniesieniu do rozpatrywanego parametru
np. koszt zwiększy się o  gdy zwiększymy pojemność o jednostkę pojemności.
PRZYKA
AD:
Obliczyć optymalne koszty wykonania zbiornika cylindrycznego o wymiarach:
V = 50 m3 - pojemność zbiornika,
koszty materiału:
- dno zbiornika: c1 = 10 j / m2
L
- ściany boczne zbiornika: c2 = 5 j / m2
5
D