KOMPUTEROWE METODY OPTYMALIZACJI

OPTYMALIZACJA – dziedzina nauki zajmująca się metodami wyboru najlepszych z określonego punktu widzenia rozwiązań wszelkich działań człowieka.

Podstawowe dziedziny zastosowań:

·         Zarządzanie i administracja

·         Zagadnienia przydziału i rozmieszczenia

·         Identyfikacja cech zjawisk, procesów, wyrobów

·         Projektowanie procesów, układów, konstrukcji

·         Optymalne sterowanie

Schemat rozwiązania problemu

Opis końcowy problemu

Optymalne projektowanie

Koncepcyjne opracowanie problemu

Analiza funkcjonalna problemu

Zgromadzenie niezbędnych danych wejściowych

Cel i po-                                                                        wyjście

trzeby   

                   1            2              3              4          5

1 – określenie potrzeb potencjalnego użytkownika,

2 – określenie funkcji, które ma spełniać układ lub system,

3 – intuicyjne (na bazie posiadanej wiedzy) rozwiązanie     problemu lub opracowanie systemu, tak aby spełniał     oczekiwania,

4 – ulepszenie rozwiązania z równoczesnym zmniejszeniem     nakładów,

5 – opis końcowego rozwiązania, tak aby można było go     bezproblemowo wykonać lub zrealizować.

PODSTAWOWE POJĘCIA OPTYMALIZACJI:

·         Zmienne decyzyjne (lub inaczej zmienne projektowania) – opisują rozwiązanie;

·         Funkcja celu (lub inaczej wskaźnik jakości) –

                                                                                    określa “dobroć” (jakość) rozwiązania;

·         Ograniczenia – wyznaczają obszar dopuszczalny,                  w którym może leżeć rozwiązanie.

Przykład:

                                          Obiekt:  prostokąt o bokach a i  b:                 a 

                                                                                                                                        b

Zmienne projektowania:   długości boków a  i  b.

              Funkcja celu:  pole powierzchni:  f(a,b)=

Ograniczenia:

   g1 =   (obwód prostokąta nie                                 może być większy niż 16 cm.)

g2 =

g3 =

g4 =

g5 =

                                                                                                                              obszar dopuszczalny

SFORMUŁOWANIE ZADANIA OPTYMALIZACJI:

Dane są:

1.        Wektor zmiennych decyzyjnych x = {x1, x2, . . xn}T

2.        Funkcja celu f zależna od zmiennych decyzyjnych

                                                                      f(x) = f(x1, x2, . . xn)

3.        Zbiór funkcji ograniczeń zależnych od zmiennych decyzyjnych

                                                                      gi(x) = gi(x1, x2, . . xn)     i = 1,2, . . , m

Znajdź   minimum f(x) przy   spełnieniu  ograniczeń:

                                                                      gi(x1, x2, . . xn) 0     i = 1,2, . . , m

Nieraz poszukuje się maksimum funkcji celu                 wtedy:

                                                                      max. f(x) = min. [-f(x)]

KLASYFIKACJA ZADAŃ OPTYMALIZACJI

·         Optymalizacja dyskretna

·         Optymalizacja ciągła

                                                                                    Zadania programowania liniowego

Optymalizacja                           (ZPL)

                                          ciągła:

                                                                                    Zadania programowania nieliniowego

                                                     (ZPN)

ZPL:  funkcja celu f oraz wszystkie funkcje ograniczeń gi  (i=1,2, . . ,m) są liniowe.

Uwaga:               nieraz ograniczenia uzupełnia się o warunek

ZPN: co najmniej jedna z funkcji f lub gi jest nieliniowa.

PRZYKŁADY ZADAŃ PROGRAMOWANIA

Przykład 1: (ZPL)

przy ograniczeniach:

Inna forma zapisu:

przy ograniczeniach:

Interpretacja geometryczna:

Przykład 2: (ZPN)

przy ograniczeniach:

Inna forma zapisu:

przy ograniczeniach:

Zadanie programowania kwadratowego: ma jednoznaczne rozwiązanie.

Interpretacja geometryczna:

f(x) można zapisać w postaci:

Przykład 2

Założenia:

·...