Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 63 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 65 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 67 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 69 Notice: Undefined variable: base in /home/misc/mst/public_html/lecture.php on line 36 Optymalizacja II – Wprowadzenie – MIM UW

Zagadnienia

Wprowadzenie

,,Optymalizacja” to poszukiwanie czegoś ,,najlepszego”. Sprawdzenie, czy coś (np. decyzja) jest najlepsze, wymaga, przede wszystkim, określenia jakiejś miary, która pozwoli tą decyzję ocenić – funkcji celu. Konieczne jest także opisanie zbioru wszystkich dopuszczalnych decyzji – zbioru punktów dopuszczalnych. Matematyczne przedstawienie zadania optymalizacyjnego, które zaprezentujemy na tym wykładzie, może wydać się dużym uproszczeniem, lecz okazuje się ono być wystarczające w wielu praktycznych zastosowaniach. Będziemy opisywać zbiór punktów dopuszczalnych jako podzbiór wielowymiarowej przestrzeni rzeczywistej opisany przez układ równości i/lub nierówności. Funkcja celu będzie przyporządkowywała każdemu punktowi tego zbioru liczbę rzeczywistą mierzącą jego optymalność. W przypadku minimalizacji, funkcja celu często zwana jest funkcją kosztu, a celem optymalizacji jest wybranie spośród dozwolonych, opisanych przez ograniczenia, sposobów postępowania tych, które ten koszt uczynią najmniejszym.

Jeśli funkcja celu i wszystkie funkcje opisujące ograniczenia są liniowe, to mamy do czynienia z programowaniem liniowym. Istnieje wówczas algorytm (tzw. algorytm sympleks) pozwalający na szybkie i dokładne rozwiązywanie takich zagadnień (patrz monografie Bazaraa, Jarvis'a i Sherali [2] oraz Gass'a [8]). Sprawa znacznie się komplikuje, jeśli choć jedna z funkcji jest nieliniowa. Przenosimy się wówczas do świata programowania nieliniowego, który jest dużo bogatszy i trudniejszy. W ten właśnie świat mają wprowadzić czytelnika niniejsze notatki.

Okazuje się, że wiele zastosowań matematyki sprowadza się właśnie do problemów optymalizacyjnych. Zarządzanie procesami produkcyjnymi, logistyka, czy decyzje inwestycyjne to typowe problemy programowania nieliniowego. Nie dziwi zatem, że wielu ekonomistów jest ekspertami w tej dziedzinie. Co więcej, wiele teorii ekonomicznych opiera się na założeniu, że świat dąży lub oscyluje wokół punktu równowagi, czyli punktu będącego rozwiązaniem pewnego problemu optymalizacyjnego.

Równie ważne zastosowania ma programowanie nieliniowe w mechanice, elektronice, zarządzaniu zasobami wodnymi (tamy, irygacja itp.) oraz budownictwie. Można się pokusić o stwierdzenie, że to jedna z najczęściej stosowanych przez niematematyków dziedzin matematyki. Nie można też pominąć statystyki: np. metoda najmniejszych kwadratów, czy największej wiarogodności.

Zwykle, gdy teoria matematyczna zostaje użyta w praktyce, eleganckie metody analityczne oddają pola metodom numerycznym. Metody numeryczne mają na celu znalezienie przybliżenia rozwiązania zadania optymalizacyjnego, gdy staje się ono zbyt skomplikowane, by rozwiązać je w piękny analityczny sposób. Trzy ostatnie rozdziały tych notatek stanowią wprowadzenie do tej ważnej dziedziny. Zainteresowany czytelnik może poszerzyć swoją wiedzę czytając monografie Bertsekasa [4, 5], Luenbergera [9] lub Bazaraa, Sherali i Shetty [3].

Literatura

Monografia Bazaraa, Sherali i Shetty [3] prezentuje podejście bardziej inżynierskie, utylitarne. Prezentuje zarówno teorię, jak i metody numeryczne. Wszystkie twierdzenia poparte są dowodami i uzupełnione przykładami, tak więc stwierdzenie, że jest to pozycja inżynierska, tyczy się tego, że autorzy ilustrują matematyczne rozumowania intuicjami pochodzącymi z zastosowań.

Bertsekas jest ekspertem od metod numerycznych programowania nieliniowego. W jego książkach [4, 5] czytelnik może szukać zaawansowanych algorytmów. Teoria jest jednak zaprezentowana dość skrupulatnie, więc i tutaj można się całkiem dużo dowiedzieć o metodach analitycznych.

Książka Luenbergera [9] prezentuje zarówno teorię programowania liniowego jak i nieliniowego. Większy nacisk położony jest w niej na metody numeryczne niż na prezentację matematycznej teorii w pełnej ogólności.

Programowanie liniowe nie jest przedmiotem tych notatek, lecz co jakiś czas wspominane, szczególnie w przypadku metod numerycznych. Czytelnik chcący pogłębić wiedzę na jego temat odsyłany jest do książek Bazaraa, Jarvis'a, Shetty [2] i Gass'a [8].

Literatura w języku polskim nie jest zbyt obszerna. Warto tu wspomnieć monografie Zangwill'a [12] i Canon'a, Cullum'a i Polak'a [6].

Notacja

\mathbb{R} – zbiór liczb rzeczywistych,

\mathbf{x}=(x_{1},\ldots,x_{n}) – wektor (pogrubiona litery)

\mathbf{x}\le\mathbf{y} – relacja pomiędzy dwoma wektorami; równoważna x_{i}\le y_{i} dla każdego i

\|\mathbf{x}\|=\sqrt{x_{1}^{2}+x_{2}^{2}+\ldots+x_{n}^{2}} – norma euklidesowa w \mathbb{R}^{n},

\mathop{\rm cl}W – domknięcie zbioru W w domyślnej normie (najczęściej euklidesowej)

f^{{\prime}}(x),f^{{\prime\prime}}(x) – pierwsza i druga pochodna funkcji jednej zmiennej

Df(\mathbf{x}) – pierwsza pochodna funkcji wielu zmiennych, wektor wierszowy

D^{2}f(\mathbf{x}) – macierz drugich pochodnych funkcji wielu zmiennych

Podziękowania

Część wykładów i zadań bazuje na notatkach prof. Bronisława Jakubczyka. W największym stopniu dotyczy to wykładów 1, 2, 10, 11. Niektóre zadania pochodzą od dr. Wojciecha Kryńskiego. Ogromne wyrazy wdzięczności należą się Agnieszce Wiszniewskiej-Matyszkiel za liczne uwagi i komentarze dotyczące zarówno samego doboru materiału jak i jego przedstawienia.

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.