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^+ = \infty, nie 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