1
Ekstremum funkcji wielu zmiennych
Z OGRANICZENIAMI
Szczecin 2008-03-16
Metody optymalizacji, Informatyka
Ekstremum funkcji wielu zmiennych z ograniczeniami
2
Zadanie optymalizacji warunkowej  zminimalizować
f(x) przy ograniczeniach:
hk śą xźą=0
k=1,2 ,‹Ä… , K
g śąxźą‡Ä…0
j=1,2 ,‹Ä… , J
j
i=1,2 ,‹Ä…, N
xśąU źą‡Ä…xi‡Ä…xśąDźą
i i
Szczecin 2008-03-16
Metody optymalizacji, Informatyka
Ekstremum funkcji wielu zmiennych z ograniczeniami
3
RozwiÄ…zywanie zadania poszukiwania minimum warunkowego:
hk śą xźą=0
równanie k=1,2 ,‹Ä… , K K "Ä…n
wykorzystujemy do wyeliminowania dowolnych K zmiennych.
FunkcjÄ™ f(x) doprowadza siÄ™ do postaci:
f śąx1, x2,‹Ä…, xnźą= f śą y1, y2,‹Ä… , yn-K źą
1
y1, y2, ..., yn-K  niewyeliminowane zmienne
Szczecin 2008-03-16
Metody optymalizacji, Informatyka
Ekstremum funkcji wielu zmiennych z ograniczeniami
4
RozwiÄ…zywanie zadanie poszukiwania minimum warunkowego
przekształcamy w zadanie poszukiwania wartości zmiennych
y1, y2, ..., yn-K dla których funkcja f1(y) osiąga minimum i na które
nie nałożono żadnych ograniczeń.
zadanie minimalizacji
zadanie minimalizacji
bezwarunkowej
warunkowej
Szczecin 2008-03-16
Metody optymalizacji, Informatyka
Ekstremum funkcji wielu zmiennych z ograniczeniami
5
Przykład 1. Dana jest funkcja dwóch zmiennych i ograniczenie.
Znajdz
minimum tej funkcji.
f śąx , yźą=śąx-1źą2ƒÄ… y2 hśą x , yźą=x2- yƒÄ…1=0
x2- yƒÄ…1=0 Śą y=x2ƒÄ…1
f śąx , x2ƒÄ…1źą= f śą xźą=śą x-1źą2ƒÄ…śą x2ƒÄ…1źą2
" f śą xźą
min f śą xźąŚą =0Śą 2 x3ƒÄ…3 x-1=0 Śą xm=0.313
" x
ym=x2 ƒÄ…1=1.098
m
f śąxm , ymźą=1.678
Szczecin 2008-03-16
Metody optymalizacji, Informatyka
Ekstremum funkcji wielu zmiennych z ograniczeniami
6
Przykład 1. Dana jest funkcja dwóch zmiennych i ograniczenie.
Znajdz
minimum tej funkcji.
f śą x , yźą=śą x-1źą2ƒÄ… y2
hśą x , yźą=x2- yƒÄ…1=0
ym=x2 ƒÄ…1=1.098
m
f śą xm , ymźą=1.678
Szczecin 2008-03-16
Metody optymalizacji, Informatyka
Ekstremum funkcji wielu zmiennych z ograniczeniami
7
Przykład 2. Dana jest funkcja dwóch zmiennych i ograniczenie.
Znajdz
minimum tej funkcji.
f śąx , y , zźą=xÅ"yÅ"z
hśą x , y , zźą=x2Å"zƒÄ… yÅ"z2ƒÄ… y-1Å"x=0
'
uzyskanie wyrażenia analitycznego dowolnej zmiennej za
pomocą innych w tym wypadku nie jest możliwe.
Szczecin 2008-03-16
Metody optymalizacji, Informatyka
Ekstremum funkcji wielu zmiennych z ograniczeniami
8
Przykład 3. Dana jest funkcja dwóch zmiennych i ograniczenia.
Znajdz
minimum tej funkcji.
f śą x , yźą=śą x-1źą2ƒÄ… y2
g1śą x , yźą=-x2ƒÄ… y-1‡Ä…0
g2śą x , yźą=x- yƒÄ…2‡Ä…0
x‡Ä…0
{
y‡Ä…0
Szczecin 2008-03-16
Metody optymalizacji, Informatyka
Ekstremum funkcji wielu zmiennych z ograniczeniami
9
Metody poszukiwania ekstremum funkcji
wielu zmiennych z ograniczeniami
metody graficzne
metoda systematycznego przeszukiwania,
metody losowe,
metoda mnożników Lagrange'a,
warunki Kuhna-Tuckera,
metoda funkcji kary,
Szczecin 2008-03-16
Metody optymalizacji, Informatyka
Metoda mnożników Lagrange'a
10
Metoda mnożników Lagrange'a pozwala przekształcać
zadanie poszukiwania ekstremum warunkowego do postaci
zadania poszukiwania ekstremum bezwarunkowego w
przypadku istnienia ograniczeń w postaci równości.
Szczecin 2008-03-16
Metody optymalizacji, Informatyka
Metoda mnożników Lagrange'a
11
Znalez
ć min f(x)
x=[ x1, x2,... , xn]T
Przy ograniczeniach
hk śąxźą=0
k =1,2 ,... , K K "Ä…n
Wprowadzamy wektor
ÁÄ…=[ÁÄ…1,ÁÄ…2,... ,ÁÄ…K ]
K
Budujemy funkcjÄ™ Lagrange'a
Lśą x , Áąźą= f śąxźąƒÄ… ÁÄ…k hk śą xźą
"
k=1
Punkty stacjonarne funkcji Lagrange'a
Nieokreślone
znajdziemy rozwiązując układ równań:
mnożniki Lagrange'a
" Lśąx ,Áąźą
=0 j=1,2 ,... , n
" x
j
" Lśąx ,Áąźą
=hk śąxźą=0 k=1,2 ,... , K
" ÁÄ…k
Szczecin 2008-03-16
Metody optymalizacji, Informatyka
 Metoda mnożników Lagrange'a  ograniczenia równościowe
12
Przykład
2
Znalez
ć
min f śą xźą=x1ƒÄ…x2
2
Przy ograniczeniu
hśąxźą=x1ƒÄ…x2=1 1-x1-x2=0
2
Budujemy funkcjÄ™ Lagrange'a
Lśą x1, x2,Áąźą=x1ƒÄ…x2ƒÄ…Áąśą1-x1-x2źą
2
" L
=2x1-ÁÄ…=0
1
" x1
x1=
2
" L
RozwiÄ…zanie:
1
=2x2-ÁÄ…=0
x2=
" x2
2
ÁÄ…=1
" L
=1-x1-x2=0
"ÁÄ…
Szczecin 2008-03-16
Metody optymalizacji, Informatyka
 Metoda mnożników Lagrange'a  ograniczenia równościowe
13
2
Znalez
ć
min f śą xźą=x1ƒÄ…x2
2
Przy ograniczeniu
hśąxźą=x1ƒÄ…x2=1 1-x1-x2=0
x2
2
1
1 2
x1
Szczecin 2008-03-16
Metody optymalizacji, Informatyka
 Metoda mnożników Lagrange'a  dowolne ograniczenia
14
2
Znalez
ć min f śą xźą=x1Å"x2 Przy ograniczeniu
Przykład.
gśąxźą=25-x1-x2‡Ä…0
2
Przekształcamy ograniczenie do równości
2 2
gśąxźą=25-x1-x2‡Ä…0Śą gśąxźą=25-x1-x2-u2=0
2 2
Budujemy funkcjÄ™ Lagrange'a
Lśą x , ÁÄ… , uźą=x1Å"x2ƒÄ…Áąśą25-x2-x2-u2źą
1 2
" L
=x2-2ÁÄ… x1=0
" x1
" L
=x1-2ÁÄ… x2=0
" x2
" L
2
=25-x1-x2-u2=0
2
"ÁÄ…
" L
=ÁÄ…u=0
" u
Szczecin 2008-03-16
Metody optymalizacji, Informatyka