To tylko jedna z 11 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Metody i algorytmy optymalizacji dr Helena Spyra Wykład 9
PROGRAMOWANIE WYPUKŁE
f (X) → min
przy warunkach: gi(X) ≤ 0 i€In={1,…,r} funkcja f (X) jest wypukła i obszar rozwiązań dopuszczalnych D jest wypukły.
Zbiór D nazywamy wypukłym, jeżeli dla dowolnych X1, X2 € D i dowolnych również należy do U.
Funkcja f (X) nazywamy wypukłą, jeżeli dla dowolnych X1, X2 € D , dowolnych Jeżeli funkcja wypukła osiąga w punkcie X0 minimum , to jest to minimum globalne. Jeżeli f(x) jest funkcją wypukłą, to zbiór
Q = { X: f (X) ≤ α } jest wypukły dla dowolnego α Iloczyn mnogościowy skończonej ilości zbiorów wypukłych jest zbiorem wypukłym
Jeżeli f (X) jest klasy C2, to następujące zdania są rownoważne:
f (X) jest wypukla
dla dowolnych X1,X2 hesjan jest dodatnio określony w każdym punkcie określoności funkcji.
Funkcja f (X) jest wypukła wtedy iylko wtedy, gdy dla dowolnego X* i R ≠ 0 funkcja h(X) = f (X*+ t∙R) jest wypukła.
Zadania programowania wypukłego postaci:
f (X) = ½ XTCX + PTX → min
przy ograniczeniach: AX = P0 X ≥ 0
tworzą klasę zadań programowania kwadratowego.
Algorytmy dla zadań programowania wypukłego
1. Punktem startowym jest dowolny punkt X0 € D
2. Punkt ciężkości zasady generowania ciągu { Xk } przenosi się na określanie kierunków przemieszczania Rk dopuszczalnych i użytecznych dla minimalizacji i wyznaczanie punktu Xk+1 jako: Xk+1 = Xk + tk*Rk tak, aby 3. Postępowanie zostaje zakończone w punkcie, w którym spełnione są warunki optymalności Kuhna-Tuckera.
(charakterystyczne własności każdego z algorytmów są związane ze sposobem określania wektorów Rk )
algorytmy kierunków dopuszczalnych Algorytm Beale'a
f (X) = ½ XTCX → min przy graniczeniach AX = P0 X ≥ 0 (należy do procedur wzorujących się na znanej programowaniu liniowym metodzie simpleks) Postępowanie rozpoczynamy w dowolnym punkcie będący
(…)
… której argumentami są zmienne niebazowe. Wartości tej funkcji ozn. ui Dla xs = xs* wartością tej funkcji jest u1 = 0.
W naszym zadaniu równanie jest równaniem liniowym, którego jedynym z rozwiązań jest xs = xs* dla zerowych wartości pozostałych zmiennych, w tym również u1 .
Jeżeli równanie dołączymy do układu równań BXB + NXN = P0 to otrzymamy układ równań liniowych, którego rozwiązaniem bazowym będzie punkt o składowych XB oraz dodatkowej składowej xs z równania Pozostałe zmienne otrzymanego układu będą zmiennymi niebazowymi. Otrzymujemy ponownie sytuację znaną z metody simpleks i możemy wyrazić funkcję kryterium-jako funkcję nowych zmiennych niebazowych a następnie przeprowadzić analizę optymalności rozwiązania przez badanie wartości pochodnych cząstkowych zmodyfikowanej funkcji kryterium.
Zmienna swobodna u1 może przybierać dowolne wartości, tak, aby żadna ze zmiennych xj nie stała się ujemna i aby zmiana wartości u1 prowadziła do zmniejszenia się wartości funkcji kryterium.
Jeżeli pochodna cząstkowa zmodyfikowanej funkcji kryterium ze względu na u1 jest różna od zera, to zmniejszenie wartości funkcji f(X) możemy uzyskać:
-zmniejszając wartości u1 gdy pochodna jest dodatnia
-zwiększając wartości u1 gdy pochodna jest ujemna
Zmienna u1 jest nieograniczoną co do znaku, możemy ją traktować na równi z pozostałymi, w praktyce okazuje się , że korzystnie jest stosować regułę preferencji; jeżeli analiza pochodnych cząstkowych wskazuje, że zmienną bazową może stać się zmienna niebazowa xs lub zmienna u, należy preferować zmienną u . Zmienna u1 powinna stać się zmienną bazową, lecz prowadzi to do wyrugowania jej z zadania…
…. Gk -wektor gradientu f (X) w punkcie Xk.
Oznaczmy symbolem Ni (i= 1, ...,m) kolumnowy wektor współczynników lewej strony i-tej nierówności ograniczeń:
Ni/ = [ai1 ... ain]
Przyjmijmy, źe w punkcie Xk nierówności 1, ...,s są spełnione jako równości. Utwórzmy macierz Qk = [N1 ... Ns] i wyznaczmy tzw. macierz rzutowania :
Pk=I-Qk(QkTQk)-1QkT I oznacza macierz jednostkową. Jeżeli s = 0, to przyjmujemy…
... zobacz całą notatkę
Komentarze użytkowników (0)