Wyklad_7.doc

47

Algorytmy i metody numeryczne

Wykład 7

Metody optymalizacji

Wstęp

Z problemami optymalizacji spotykamy się praktycznie we wszystkich obszarach nauki, przemysłu, ekonomii, zarządzania itp. Do ich analizy niezbędna jest znajomość metod pozwalających na znalezienie optymalnych rozwiązań. Istnieje wiele metod opty­malizacji, które z pomocą coraz wydajniejszych komputerów pozwalają na rozwiązywanie złożonych zadań optymalizacji. Ciągły rozwój metod optymalizacji podyktowany jest faktem, że nie istnieją optymalne (uniwersalne) algorytmy w tym zakresie. Każda z metod optymalizacji może bowiem okazać się zawodna lub mało efektywna podczas poszukiwania minimum (maksimum) analizowanej funkcji. Dlatego też, z uwagi na trudności w procesie poszukiwania rozwiązań optymalnych analizowanego zagadnienia (trudności w uzyskaniu zbieżności lub wysokie nakłady czasów obliczeń), niezbędna jest znajomość więcej niż jednej metody optymalizacji. Metody te różnić się mogą efek­tywnością oraz czasami obliczeń, w zależności od optymalizowanej funkcji.

W wielkim skrócie możemy powiedzieć, że optymalizacja to dziedzina matematyki, która umożliwia znalezienie najlepszego rozwiązania, tzn. rozwiązania dającego najmniejszą lub największą (minimum lub maksimum) wartość pewnego wyrażenia nazywanego funkcją celu (także kryterium jakości, kryterium optymalizacji, funkcjonałem jakości).

Początków teorii optymalizacji można się doszukiwać już w czasach starożytnych, kiedy to Euklides (III wiek p.n.e.) zajmował się poszukiwaniem najkrótszej drogi łączącej dwa punkty. Pierwszą technikę optymalizacyjną wiąże się z Gaussem (przełom XVIII i XIX w.), który opracował tzw. metodę największego spadku. Natomiast za „ojca” terminu optymalizacja uważa się amerykańskiego matematyka George B. Dantziga (1914-2005), który zajmował się programowaniem liniowym i jest twórcą metody sympleks.

Rozkwit teorii optymalizacji obserwuje się od początku drugiej połowy XX w., kiedy nastąpił intensywny rozwój metod numerycznych, związany z dynamicznym rozwojem technik komputerowych.

Ogólnie, celem optymalizacji jest wybór najlepszego (minimalnego lub maksymal­nego) rozwiązania danego problemu, które spełnia wszystkie ograniczenia i uwarunkowania. W życiu codziennym rozwiązania optymalne zadań praktycznych są wynikiem zdobytego doświadczenia, wiedzy praktycznej i często dochodzi się do nich metodą prób i błędów. Jest to zazwyczaj proces długotrwały i często bardzo kosztowny. Znalezienie w sposób bardziej efektywny tego „optimum” umożliwiają metody optymalizacji, które w sposób algorytmiczny, na drodze analitycznej lub numerycznej, pozwalają na poszu­kiwanie rozwiązań optymalnych bez konieczności analizowania wszystkich możliwych wariantów.

Z teoretycznego punktu widzenia, zagadnienie poszukiwania rozwiązań optymalnych stanowi odrębną teorię, którą zaliczyć można do dziedziny matematyki stosowanej. Jej zadaniem jest odpowiednie sformułowanie, w sposób matematyczny, analizowanego problemu optymalizacji, zbioru poszukiwań oraz funkcji celu optymalizacji (kryterium jakości). Dla tak sformułowanego problemu optymalizacji, zadaniem jest znalezienie optymalnego rozwiązania, które spełnia przyjęte kryterium optymalizacji. Ogólnie, poszukiwanie rozwiązań optymalnych związane jest z następującymi zadaniami:

- doborem (opracowaniem) modelu matematycznego analizowanego procesu,

- zdefiniowaniem funkcji celu optymalizacji (funkcjonału jakości, kryterium optymali­zacji, kryterium jakości itp.),

- poszukiwaniem optymalnego rozwiązania z zastosowaniem jednej z metod optymalizacji.

O ile pierwsze z wymienionych zadań jest głównie przedmiotem identyfikacji i modelowania procesów, o tyle pozostałe dwa zadania są nierozerwalnie związane z optymalizacją.

Załóżmy, że dane są:

■                  funkcja celu ,

■                  zbiór .

Zadaniem optymalizacji, nazywanej też programowaniem matematycznym, jest poszukiwanie takiego elementu , że

(poszukiwanie minimum, )

lub

(poszukiwanie maksimum, ).

Stosowane algorytmy optymalizacyjne wyznaczają pewne rozwiązanie . Znalezione rozwiązanie stanowić ma przybliżenie minimum (maksimum) globalnego optymalizowanej funkcji celu (tzn. wartość powinna być dobrym przybliżeniem liczby ). Należy zaznaczyć, że znalezione minimum (maksimum) jest globalne jedynie wewnątrz zdefiniowanego obszaru poszukiwań zmiennych optymalizacji, w którym znajdują się dopuszczalne rozwiązania , a niekoniecznie w całej dziedzinie funkcji celu.

Cz...