 | Pobierz cały dokument wyklad.1.cd.elektrotechnika.materialy.do.doc Rozmiar 231 KB |
Metody optymalizacji
Rozpatrywane będą jednowskaźnikowe zadania programowania, przy czym elementy zbioru rozwiązań dopuszczalnych należą do przestrzeni skończenie wymiarowej Rn. Zadanie optymalizacji polega na znalezieniu takiego wektora należącego do zbioru , że dla każdego x należącego do zbioru X0, f () ≤ f (x). W zadaniu tym X0, jest zbiorem rozwiązań dopuszczalnych, f : Rn → R1 jest funkcją celu, g: Rn → i h: Rn → są wektorowymi funkcjami ograniczeń.
Jeden ze sposobów podziału zadań programowania:
programowanie liniowe - jeśli funkcje f , g i h są liniowe, a więc
f (x) = <c, x〉
oraz
[ g (x)T, h (x)T]T = Ax - b,
gdzie wektory c ∈ Rn, b ∈ Rm oraz macierz A o wymiarach m × n są znane.
programowanie nieliniowe - jeśli co najmniej jedna z funkcji f , g bądź h jest nieliniowa.
Wśród wymienionych wyżej typów zadań, za podstawowe zadanie programowania należy uznać ciągłe deterministyczne zadanie programowania nieliniowego o postaci:
znaleźć takie, że
f () = ,
gdzie
,
przy czym
f : Rn → R1, g: Rn → , h: Rn → .
Warunki konieczne optymalności Kuhna - Tuckera
Warunki te sformułujemy dla uproszczonej postaci zadania programowania nieliniowego, mianowicie: znaleźć takie, że
f () = f (x),
gdzie
X0 = {x ∈ Rn: gi (x) ≤ 0, i = 1, ..., m}.
Niech funkcje f : Rn → R1 oraz gi : Rn → R1 mają ciągłe pochodne cząstkowe oraz niech będzie minimum lokalnym. Niech ponadto x będzie dowolnym punktem należącym do zbioru X0. W punkcie x określimy zbiór indeksów ograniczeń aktywnych
A(x) = {i ∈ [1: m]: gi (x) = 0}.
Z ciągłości funkcji gi wynika, że jeśli ograniczenie nie jest aktywne
w x, tzn. gi (x) < 0 dla i ∉ A(x), to można dokonać małego przesunięcia z x w dowolnym kierunku bez naruszenia tego ograniczenia. Stąd w małym otoczeniu punktu x wystarczy brać pod uwagę tylko zbiór ograniczeń aktywnych, tzn. ograniczeń o indeksach i ∈ A(x).
Kierunkiem dopuszczalnym w x będzie kierunek d, dla którego istnieje σ>0 takie, że dla ∈ σ zachodzą nierówności
gi (x + d) ≤ 0, ∀i ∈ A(x).
Warunkiem koniecznym na to, aby kierunek d był dopuszczalny jest
<∇gi (x), d〉 ≤ 0, ∀i ∈ A(x).
Wynika stąd, że jeśli kierunek d jest dopuszczalny, to musi spełniać powyższy warunek. Natomiast nie każdy kierunek spełniający ten warunek jest kierunkiem dopuszczalnym.
Warunek regularności Kuhna - Tuckera
Dla dowolnego kierunku d ∈ D (), gdzie zbiór D () określony jest przez
D () = {d: <∇gi (), d〉 ≤ 0, i ∈ A()}
istnieją:
n-wymiarowa różniczkowalna funkcja wektorowa
e() = [e1 (), ..., en ()]T
 | Pobierz cały dokument wyklad.1.cd.elektrotechnika.materialy.do.doc rozmiar 231 KB |