J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
1
PROGRAMOWANIE NIELINIOWE
Jeżeli wektor zmiennych decyzyjnych
n
x R
, tzn. jego składowe są liczbami a nie funkcjami,
wtedy klasyfikacja problemu optymalizacji zależy od postaci funkcji celu
Q x
i funkcji ograni-
czeo
i
g x
:
Zadanie programowania nieliniowego: występuje wtedy, gdy co najmniej jedna z funkcji jest
nieliniowa względem wektora
x
,
Uwaga:
Zadanie programowania liniowego można potraktować jako szczególny przypadek zadania
programowania nieliniowego. Jednak z uwagi na trudność rozwiązywania nie jest to racjo-
nalne.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
2
METODY ANALITYCZNE
ZADANIE PROGRAMOWANIA NIELINIOWEGO BEZ OGRANICZEO
Zbiorem dopuszczalnym jest cała przestrzeo
n
R
.
Punkt
ˆx
jest minimum lokalnym funkcji
Q x
w przestrzeni
n
R
, jeżeli istnieje takie otwarte
otoczenie
n
U R
punktu
ˆx
, że
ˆ
,
U
Q
Q
x
x
x
, przy czym jeżeli nierównośd jest
ostra
ˆ
Q
Q
x
x
, to jest to ścisłe minimum lokalne.
Punkt
ˆx
jest minimum globalnym funkcji
Q x
w przestrzeni
n
R
, jeżeli
ˆ
,
n
Q
Q
x R
x
x
, przy czym jeżeli nierównośd jest ostra
ˆ
Q
Q
x
x
, to jest to
ścisłe minimum globalne.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
3
Założenie:
,
Q x y
określona w przestrzeni
2
R
, jest klasy C
2
Def.
,
Q x y
ma punkt stacjonarny w punkcie
ˆ ˆ
,
x y
jeżeli
ˆ ˆ
ˆ ˆ
ˆ ˆ
ˆ ˆ
,
,
0
,
,
0
x
y
Q
Q
x y
x y
Q x y
Q x y
x
y
Jest to zarazem warunek konieczny istnienia ekstremum lokalnego
,
Q x y
w punkcie
ˆ ˆ
,
x y
.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
4
Typy punktów stacjonarnych:
Utwórzmy macierz drugich pochod-
nych (hesjan):
,
,
,
,
xx
xy
yx
yy
Q
x y Q
x y
Q
x y Q
x y
H
,
której wyznacznik w punkcie
ˆ ˆ
,
x y
wynosi:
2
ˆ
ˆ ˆ
ˆ ˆ
ˆ ˆ
,
,
,
xx
yy
xy
Q
x y Q
x y Q
x y
H
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
5
Tw.
Jeśli
ˆ ˆ
,
x y
jest punktem stacjonarnym
,
Q x y
, wtedy:
a)
jeżeli
ˆ
ˆ ˆ
,
0 i
0
xx
Q
x y
H
to
,
Q x y
ma lokalne maksimum w punkcie
ˆ ˆ
,
x y
,
b)
jeżeli
ˆ
ˆ ˆ
,
0 i
0
xx
Q
x y
H
to
,
Q x y
ma lokalne minimum w punkcie
ˆ ˆ
,
x y
,
c)
jeżeli
ˆ
0
H
to
,
Q x y
ma siodło w punkcie
ˆ ˆ
,
x y
.
Jeżeli
ˆ
0
H
to problem pozostaje nierozstrzygnięty.
Dowód:
Zbadajmy
,
Q x y
w otoczeniu
ˆ
ˆ
,
x u y v
.
Rozwijając
,
Q x y
w szereg Taylora otoczeniu
ˆ
ˆ
,
x u y v
:
2
2
ˆ
ˆ
ˆ ˆ
ˆ ˆ
ˆ ˆ
,
,
,
,
1
ˆ ˆ
ˆ ˆ
ˆ ˆ
,
2
,
,
2
x
y
xx
xy
Q x u y v
Q x y
uQ x y
vQ x y
u Q
x y
uvQ
x y
v Q x y
Ponieważ
ˆ ˆ
,
x y
jest punktem stacjonarnym :
ˆ ˆ
ˆ ˆ
,
,
0
x
y
uQ x y
vQ x y
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
6
Przyrost
2
2
1
ˆ
ˆ
ˆ ˆ
,
,
2
2
Q Q x u y v
Q x y
Au
Buv Cv
gdzie:
ˆ ˆ
ˆ ˆ
ˆ ˆ
,
,
,
xx
xy
yy
A Q
x y
B Q
x y
C Q
x y
2
2
2
2
2
2
2
2
Bv
B
Bv
Au
Buv Cv
A u
C
v
A u
v
A
A
A
A
gdzie:
2
ˆ
CA B
H
( wyznacznik hesjanu)
a)
jeśli
0 i
0
0
,
A
Q
Q x y
ma lokalne minimum w punkcie
ˆ ˆ
,
x y
,
b)
jeśli
0 i
0
0
,
A
Q
Q x y
ma lokalne maksimum w punkcie
ˆ ˆ
,
x y
c)
jeśli
0
to
,
Q x y
ma w punkcie
ˆ ˆ
,
x y
punkt siodłowy.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
7
PRZYKŁAD:
2
2
,
Q x y
x
y
,
2
0
ˆ ˆ
,
0, 0
,
2
0
x
y
Q x y
x
x y
Q x y
y
2 0
ˆ
ˆ ˆ
4 0
,
0
2
x y
H
jest siodłem.
Uwaga:
Przeprowadzone rozumowanie można uogólnid na funkcję wielu zmiennych.
Założenie:
1
2
, , ,
n
Q
Q x x
x
x
określona w przestrzeni
n
R
, jest klasy C
2
.
Def.
Q x
ma punkt stacjonarny w punkcie
1
2
ˆ
ˆ ˆ
ˆ
, , ,
n
x x
x
x
jeżeli
1
2
ˆ
ˆ
ˆ
ˆ
0
n
Q
Q
Q
grad Q
x
x
x
x
x
x
x
Jest to zarazem warunek konieczny istnienia ekstremum lokalnego
Q x
w punkcie
ˆx
.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
8
Utwórzmy macierz drugich pochodnych (hesjan):
2
2
2
2
1
2
1
1
2
2
2
2
2
1
2
2
2
2
2
2
1
2
n
n
n
n
n
Q
Q
Q
x x
x x
x
Q
Q
Q
x x
x x
x
Q
Q
Q
x x
x x
x
x
x
x
x
x
x
H x
x
x
x
którą w punkcie
ˆx
oznaczymy jako
ˆ
H x
.
Oznaczmy podwyznaczniki (minory) główne, które można utworzyd z hesjanu
ˆ
H x
jako:
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
9
2
2
2
2
1
2
1
2
2
2
1
2
1
2
2
1
2
2
2
2
2
1
2
1
1
2
2
2
2
2
1
2
2
2
2
2
2
1
2
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
n
n
n
n
n
n
Q
Q
x x
Q
x
Q
Q
x
x x
x
Q
Q
Q
x x
x x
x
Q
Q
Q
x x
x x
x
Q
Q
Q
x x
x x
x
x
x
H
x
H
x
x
x
x
x
x
x
x
H
x
x
x
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
10
Tw.
Jeśli
ˆx
jest punktem stacjonarnym
Q x
, wtedy:
a)
jeżeli
ˆ
0 dla
1, ,
i
i
n
H
to
Q x
ma minimum w punkcie
ˆx
(hesjan jest określo-
ny dodatnio),
b)
jeżeli
ˆ
1
0 dla
1, ,
n
i
i
n
H
to
Q x
ma maksimum w punkcie
ˆx
(hesjan jest
określony ujemnie),
c)
jeżeli
ˆ
ˆ
0 dla
1, ,
1 oraz
0
i
n
i
n
H
H
(hesjan jest określony półdodatnio),
lub
ˆ
ˆ
1
0 dla
1, ,
1 oraz
0
n
i
i
i
n
H
H
(hesjan określony półujemnie),to nie można rozstrzygnąd o istnieniu ekstremum w punk-
cie
ˆx
,
Jeżeli nie są spełnione warunki 2 lub 3 (hesjan jest nieokreślony) to
Q x
nie ma ekstre-
mum w punkcie
ˆx
.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
11
PRZYKŁAD:
Mając 36mb kształtownika, zbudowad otwarty zbiornik o największej
objętości.
1
2
1 2
1
2
1
2
1
2
1 2
1
2
,
1
2
4
36
9
2
1
,
9
2
Q x x
x x c
max
x
x
c
c
x
x
Q x x
x x
x
x
max
2
1
2
2
1 2
2
1
2
1
2
1
1
1 2
2
1
,
9
0
2
1
,
9
0
2
Q
x x
x
x x
x
x
Q
x x
x
x
x x
x
x
2
x
1
c
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
12
2
2
2
1 2
2
1
1
1 2
2
2
2
2
2
2
1
1
2
1
1
1
9
9
2
2
2
18
18
9
9
x
x x
x
x
x
x x
x
x
x
x
x
x
Zatem:
ą
ł ż
2
1
2
1
2
1
2
1
1
1
9
9
lub
9
9
lub
18
(to rozwi zanie prowadzi do wyniku
6
co jest sprzeczne z za o eniem
>0)
x
x
x
x
x
x
x
x
x
x
2
2
1
1
1
1
1
1
1
2
1
9
0 :
0
2
3
1
9
6
6
9
6 6
3
2
2
x
x
x
x
bo
x
x
x
x
c
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
13
2
1
2
1
1
1
(6,6)
2
2
1
max
9
6
3
ˆ
36 9 27
9
3
6
ˆ
ˆ
0
i
0
6 6
jest maksimum
6, 6
6 6 3 108
T
x
x
x
x
x
x
Q
x
Q
Q
H
H
x
ZADANIE PROGRAMOWANIA NIELINIOWEGO Z OGRANICZENIAMI W RÓWNOŚCIOWYMI
Problem:
Dana jest funkcja
Q x
klasy C
1
, w zbiorze dopuszczalnym
n
R
. Zbiór dopuszczalny okre-
ślony jest przez ograniczenia równościowe
0
j
h
x
. Znajdź minimum funkcji celu.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
14
Tw. (zasada Lagrange’a)
Niech dane będą stałe
1
2
, , , , ,
j
m
R
takie, że w punkcie
ˆ
n
x R
funkcja
1
ˆ
ˆ
m
j j
j
Q
h
x
x
ma minimum bez ograniczeo (bezwarunkowe). Wtedy punkt
ˆx
jest mi-
nimum (warunkowym) funkcji
Q x
w zbiorze dopuszczalnym określonym przez ograniczenia
równościowe
0 dla
1, ,
j
h
j
m
x
.
Dowód:
Przyjmijmy, że
ˆx
jest lokalnym minimum funkcji
1
ˆ
ˆ
m
j j
j
Q
h
x
x
. Oznacza to, że istnieje
otoczenie
U
punktu
ˆx
takie, że:
1
1
ˆ
ˆ
,
m
m
j j
j j
j
j
U Q
h
Q
h
x
x
x
x
x
Ponieważ dla
ˆ
ˆ
,
,
0 oraz
0
j
j
U
h
h
x x
x
x
, prawdziwe jest
ˆ
Q
Q
x
x
oznacza to, że
Q x
ma minimum w punkcie
ˆ
x
.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
15
Uwaga:
Podobne rozumowanie można przeprowadzid dla zadania maksymalizacji. Podstawiając
Q
x
zamiast
Q x
otrzymamy taki sam rezultat dla zadania maksymalizacji.
Wniosek:
Pierwotny problem
n
– wymiarowy minimalizacji funkcji
Q x
z ograniczeniami równościo-
wymi
0
j
h
x
został zastąpiony
n m
– wymiarowym problemem minimalizacji zastęp-
czej funkcji
1
m
j j
j
Q
h
x
x
bez ograniczeo.
Taki sposób postępowania to metoda mnożników Lagrange’a.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
16
Metoda mnożników Lagrange’a
Dana jest funkcja celu
Q x
klasy C
1
i zbiór dopuszczalny utworzony jest przez ograniczenia
równościowe (funkcjonalne).
:
0;
1,..., ;
;
n
j
h
j
m m n
x
x
R
Φ
gdzie:
m
- liczba ograniczeo równościowych,
n
- liczba zmiennych decyzyjnych.
Funkcje
j
h x
są również klasy C
1
.
Utwórzmy funkcję:
1 1
2 2
...
m m
L
Q
h
h
h
x,
x
x
x
x
λ
gdzie:
1
2
,...,
T
m
λ
- wektor mnożników Lagrange’a.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
17
Warunkiem koniecznym istnienia ekstremum lokalnego funkcji
,
L x λ
w punkcie
ˆx
dla
wektora mnożników
ˆλ
jest:
ˆ
ˆ,
0
1,...,
ˆ
ˆ,
0
ˆ,
0
1,...,
i
j
L
i
n
x
L
L
j
m
x
x
x
λ
λ
λ
Rozwiązując układ (6)
n m
równao znajdujemy punkt
ˆx
i wektor
ˆλ
, dla których zeruje się
gradient a zatem punkt, w którym występują punkty stacjonarne.
Jeśli
Q x
jest klasy C
2
badając hesjan
ˆ
H x
możemy rozstrzygnąd o typie punktu stacjo-
narnego.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
18
PRZYKŁAD:
Dane zadania jak w przykładzie poprzednim.
1
2
1 2
1
2
1
2
1
2
1
2
1
2
1
2
1 2
1
2
, ,
, ,
2
4
36 0
, , ,
, ,
, ,
, , ,
2
4
36
Q x x c
x x c
max
h x x c
x
x
c
L x x c
Q x x c
h x x c
max
L x x c
x x c
x
x
c
max
2
1
1
1
1 2
1
2
2
0
(1)
2
0
(2)
4
0
(3)
2
4
36 0 (4)
L
x c
x
L
x c
x
L
x x
c
L
x
x
c
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
19
1
2
1
2
2
2
2
2
1
1
1
2
(1)=(2)
bo
(5)
z (2)
(6)
(5) i (6) do (3)
bo
(7)
(7) do (2)
bo
(8)
(5) i (8) do (4)
0
2
2
4
0
0
0
2
0
2
0
2 2
2
4
36
3
6
x
x
c
x
c
c
c
c
x c
c
x
c
c
c
c
c
c
x
x
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
20
ZADANIE PROGRAMOWANIA NIELINIOWEGO Z OGRANICZENIAMI NIERÓWNOŚCIOWYMI
Zadanie, w którym funkcja celu jest wypukła i zbiór dopuszczalny jest wypukły, nazywamy za-
daniem programowania wypukłego.
Rozważmy dwuwymiarowe zadanie programowania wypukłego
2
1
2
min,
,
:
0,
1,2, 3
T
j
Q
x x
g
j
x
x
x
x
R
w którym
Q x
jest klasy C
1
.
Utwórzmy funkcję Lagrange’a:
λ
3
1 1
2 2
3 3
1
j j
j
L
Q
g
g
g
Q
g
x,
x
x
x
x
x
x
Możliwe są trzy położenia minimum
ˆx
wg zbioru
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
21
a)
Q x
ma minimum w
ˆx
leżącym wewnątrz
,
Wtedy
ˆ
ˆ
0
0
i
Q
grad Q
x
x
x
oraz
ˆ
0,
1,2, 3
j
g
j
x
.
Co można wyrazid za pomocą funkcji Lagrange’a
λ
3
1
ˆ
ˆ
ˆ
ˆ
ˆ
,
0
j
j
j
i
i
i
g
L
Q
x
x
x
x
x
x
jeśli
ˆ
0,
1,2, 3
j
j
.
Warunek
ˆ
0
j
g
x
jest aktywny w punkcie
ˆx
, jeżeli
ˆ
0
j
g
x
.
Warunek
ˆ
0
j
g
x
jest nieaktywny w punkcie
ˆx
, jeżeli
ˆ
0
j
g
x
.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
22
b)
Q x
ma minimum w
ˆx
leżącym na brzegu
(np. ograniczenie
1
g
jest aktywne),
Wtedy
1
2
3
ˆ
ˆ
ˆ
0,
0,
0,
g
g
g
x
x
x
Zatem w dostatecznie małym otoczeniu
ˆx
zadanie jest
równoważne problemowi optymalizacji z ograniczeniem
równościowym.
1
1
1
1
1
1
1
1
1
2
2
2
ˆ
ˆ
ˆ
ˆ
ˆ
,
0
ˆ
ˆ
ˆ
ˆ
ˆ
,
0
g
L
Q
x
x
x
g
L
Q
x
x
x
x
x
x
x
x
x
Co można wyrazid za pomocą funkcji Lagrange’a
λ
3
1
ˆ
ˆ
ˆ
ˆ
ˆ
,
0
j
j
j
i
i
i
g
L
Q
x
x
x
x
x
x
jeśli
1
2
3
ˆ
ˆ
ˆ
0,
0
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
23
c)
Q x
ma minimum w
ˆx
leżącym w narożu
(np. ograniczenia
1
g
i
2
g
są aktywne),
Wtedy
1
2
3
ˆ
ˆ
ˆ
0,
0,
0,
g
g
g
x
x
x
Zatem w dostatecznie małym otoczeniu
ˆx
za-
danie jest równoważne problemowi optymali-
zacji z dwoma ograniczeniami równościowymi.
1
2
1
1
2
1
1
1
1
1
1
1
1
2
2
2
2
2
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
,
0
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
,
0
g
g
L
Q
x
x
x
x
g
g
L
Q
x
x
x
x
x
x
x
x
x
x
x
x
Co można wyrazid za pomocą funkcji Lagrange’a
λ
3
1
ˆ
ˆ
ˆ
ˆ
ˆ
,
0
j
j
j
i
i
i
g
L
Q
x
x
x
x
x
x
jeśli
1
2
3
ˆ ˆ
ˆ
,
0,
0
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
24
Podsumujmy przypadki a), b), c):
Zawsze dla
ˆ
1,2, 3
0
j
j
, ponadto:
1° jeżeli
ˆ
0
j
g
x
(warunek nieaktywny), to
ˆ
0
j
,
2° jeżeli
ˆ
0
j
g
x
(warunek aktywny), to
ˆ
0
j
.
Zatem punkt
ˆx
jest rozwiązaniem zadania, gdy:
1
ˆ
ˆ
ˆ
ˆ
ˆ
,
0
m
j
j
j
i
i
i
g
L
Q
x
x
x
x
x
x
λ
,
ˆ
ˆ
0
i
0
j
j
g
x
( spełnia wszystkie ograniczenia),
ˆ
ˆ
0
j j
g
x
(co oznacza warunki 1° i 2°).
Powyższe warunki są warunkami koniecznymi istnienia rozwiązania zadania programowania
nieliniowego z ograniczeniami nierównościowymi zwanymi warunkami Kuhna-Tuckera (WKT).
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
25
Inaczej:
ˆ
ˆ,
0
1, ,
ˆ
0
ˆ
0
1, ,
ˆ
ˆ
0
i
j
j
j
j
L
i
n
x
L
j
m
L
x
x
x
λ
Uwaga:
Jeżeli w zadaniu występowałyby jednocześnie ograniczenia typu nierównościowego i równo-
ściowego, to każdą z równości
0
j
g
x
można zastąpid dwoma nierównościami
1
0
j
g
x
i
2
0
j
g
x
.
O tym czy punkt
ˆx
jest minimum
Q x
można rozstrzygnąd badając hesjan
ˆ
H
.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
26
PRZYKŁAD:
2
2
,
1
1
min
Q x y
y x
x
(dolina Rosenbrocka)
przy ograniczeniach:
1
2
1
,
1 0
1
,
1 0
y x
g x y
y x
y
x
g x y
y x
1
2
1 1
2 2
2
2
1
2
, , ,
,
,
,
1
1
1
1
L x y
Q x y
g x y
g x y
y x
x
y x
y x
1
2
1
1
1
1
1
2
2 1
0
1 0
1
0
1
0
L
y x
x
x
L
y x
L
y x
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
27
1
2
2
2
2
2
2
2
0
1 0
2
0
1
0
L
y x
y
L
y x
L
y x
Warunki 1°1 i 2°1 tworzą układ równao:
1
2
1
2
2
2
2 2
0
2
2
0
y
x
x
y
x
Załóżmy, że ograniczenia
1
,
0
g x y
,
2
,
0
g x y
są nieaktywne, tj.
1
2
,
0
.
Wtedy:
2
4
2 0
2
2
ˆ
ˆ
1
1
2
2
0
y
x
x
x
y
y
x
y x
Łatwo sprawdzid, że pozostałe warunki KT w punkcie
ˆ ˆ
,
1,1
x y
są spełnione.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
28
Obliczmy hesjan w punkcie
ˆ ˆ
,
1,1
x y
.
2
2
2
2
2
2
4
2
ˆ
4
2
2
16 4 12 0
2 4
L
L
L
L
x y
y x
x
y
H
Zatem w punkcie
ˆ ˆ
,
1,1
x y
funkcja celu
,
Q x y
ma minimum przy ograniczeniach
1
,
0
g x y
,
2
,
0
g x y
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
29
Zmieomy warunek
2
,
0
g x y
na następujący:
2
3
,
3 0
y
x
g x y
y x
Wtedy:
1
2
1
2
1
2
1
2
2
2
2
2 2
0
2 2
4
0
2
2
0
2
2
0
2 2
2
0
y
x
x
y
x
y
x
y
x
x
Stąd:
2
1 x
1
2
1
2
1
2
1
2
1
2 2
4
0
2 2
4
0
1
2
2
0
2
2
0
2 4
6
2
0
y
x
y
x
y
x
y
x
y
x
Stąd:
1
3
2
1
x
y
Sprawdzamy pozostałe warunki KT:
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
30
1
1
3
2
1
1
0
3
2
1 0
1 0
3
1
1
2
2
L
x
y
y x
x
y
y x
y
x
y x
Stąd:
ˆ ˆ
,
3, 4
x y
,
1
3 3 2 4 1 0
,
2
1 3
2 0
(warunek niespełniony)
2
2
1
3
0
1
0
3 0
1
3
L
x
y x
x
y x
x
y
x
Stąd:
ˆ ˆ
,
1,2
x y
1
3 2 2 1 1 3 0
,
2
1 1 0
1
2 1 1 0
L
,
2
2 1 3 0
L
Zatem punkt
ˆ ˆ
,
1,2
x y
spełnia warunki konieczne rozwiązania zadania.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd3: PROGRAMOWANIE NIELINIOWE – metody analityczne
31
Hesjan
ˆ
H
nie zmienia się, dlatego w punkcie
ˆ ˆ
,
1,2
x y
funkcja celu
,
Q x y
ma mini-
mum przy ograniczeniach
1
,
0
g x y
,
2
,
0
g x y
.