Przykłady zadań optymalizacji, klasyfikacje zadań optymalizacji



Metody optymalizacji










Niewątpliwie najwięcej traktatów napisano o Bogu, następnie o miłości, ale jaki temat jest na trzecim miejscu? Patrioci optymalizacji twierdzą, że o optymalizacji (sam w domu mam ponad trzydzieści książek poświeconych tej tematyce). Dlatego (optymalny?) wybór tego co najistotniejsze z tej przywalającej człowieka góry informacji nie jest łatwy. Zatem prezentowane dalej rozważania odzwierciedlają mój punkt widzenia na to co ważne, a co można pominąć z nagromadzonej wiedzy związanej z metodami optymalizacji i zdaję sobie sprawę z tego, że mój wybór może być krytykowany.


Optymalizacja



Optymalizują



Optymalizacja - wybór wariantu najlepszego


Przykłady zadań optymalizacji




Planowanie produkcji







We wzorze określającym zysk:
p^u_j – cena jednostki j-tej benzyny w kontrakcie,

p^v_j – cena jednostki j-tej benzyny w wolnej sprzedaży,
p^z_i – cena jednostki i-tego komponentu w wolnej sprzedaży,
c^s_i – koszt wytworzenia jednostki komponentu i,
c^b_i – koszty komponowania przeliczone na jednostkę komponentu i.







Współczynniki \eta_i i \mu_j można traktować dla benzyn np. jako liczbę oktanową.




Przykłady zadań optymalizacji




Projektowanie autopilota



Automatycy przy projektowaniu układów sterowania zamiast „opisem różniczkowym” obiektu liniowego wolą posługiwać się równoważnym opisem transmitancyjnym przyjmując, że funkcja \varphi(\cdot) będąca rozwiązaniem równania różniczkowego obiektu oraz sygnał sterujący \delta(\cdot) mają transformaty Laplace’a.





Jakie wybrać nastawy regulatora PID?





Jak wybrać najlepsze nastawy regulatora PID?




Zatem do oceny "odległości od zera” uchybu możemy posłużyć się całką z modułu uchybu (32.A), albo całką z kwadratu uchybu (32.B).

Które kryterium ?





Projektowanie autopilota







Identyfikacja










Ogólna postać zadania optymalizacji





Zbiór wariantów dopuszczalnych




Przypadku x_i^- = -\infty albo x_i^+ = \inftynie wykluczamy.


Ogólna postać zadania minimalizacji





Minima lokalne i minimum globalne





Zbiór dopuszczalny i funkcja wyboru




 

 


Widać, że najbardziej restrykcyjne sąograniczenia równościowe. Bez nich przykładowy zbiór dopuszczalny byłbyspójny (składałby się z jednej części) i “miał punkty w środku” (tak jak zbiór z rysunku poprzedniego), matematyk powie:miał niepuste wnętrze.


Klasyfikacja zadań optymalizacji














Optymalizacja statyczna, optymalizacja dynamiczna





Sterowanie czaso-optymalne








Optymalizacja statyczna, optymalizacja dynamiczna





Dyskretny zbiór dopuszczalny





Jest to nieskończony przeliczalny zbiór izolowanych punktów płaszczyzny, a warianty są opisywane wektorami całkowitoliczbowymi. Zbiory tego typu nazywamy zbiorami dyskretnymi.


Zauważmy, że przedstawiony przykład ograniczeń definiujących zbiór całkowitoliczbowy jest przykładem teoretycznym i ma głównie na celu pokazanie bogactwa "różności” jakie kryje w sobie przyjęta definicja zbioru dopuszczalnego.



Zadania dyskretne




Zadanie lokalizacji




Niepodzielny produkt to np. lodówka, lub lokówka, ale także paleta z kubeczkami jogurtu.





Jest to funkcja n\cdot m + n +n\cdot m = n(2m + 1)zmiennych. Przy czterech miejscach lokalizacji, n = 4,, i dwudziestu pięciu odbiorcach, m = 25, daje to 204 zmienne. W porównaniu do zadań optymalizacji, które naprawdę są rozwiązywane przy wspomaganiu decyzji podejmowanych przez menedżerów różnych korporacji, gdzie zmiennych potrafi być kilkanaście tysięcy (np. dlatego bo trzeba uwzględnić różne produkty a także różne ich rodzaje), jest to niewiele.



Ograniczenia (85.C) mogliśmy zapisać w takiej postaci, bo jeżeli w miejscu i nie zostanie wybudowana nowa fabryka to, y_i = 0, zatem na mocy (85.A) i (85.B), dla każdego j wielkość przewozu x_i_j = 0.



Są to związki logiczne a nie nierówności. Nie pasują zatem do przyjętego sposobu określania zbioru dopuszczalnego!




Przez \mathbb{Z} oznaczono zbiór liczb całkowitych tj. zbiór \{...,-1,0,1,2,...\}.



Zadania optymalizacji dyskretnej




Mamy zadania optymalizacji (wektory rzeczywiste, jak mówimy zmienne są ciągłe) i zadania dyskretne (wektory całkowitoliczbowe – zmienne dyskretne) mogą więc być zadania mieszane, w których część zmiennych jest ciągła, a pozostała – dyskretna.

Klasyfikacje zadań optymalizacji




Przedstawione dotąd rozważania pokazały, że analizując zadania optymalizacji, obok zwrócenia uwagi na stopień trudności znajdowania ich rozwiązania („łatwiejsze – trudniejsze”, czyli: bez ograniczeń – z ograniczeniami, liniowe – nieliniowe itp.) trzeba także zwrócić uwagę na ich strukturę, co prowadzi do klasyfikacji takiej jak na rysunku.


Ogólna postać zadania minimalizacji