Kilka słów więcej na temat optymalizacji

Wprowadzenie

Szukanie minimum (maksimum) funkcji to zadanie praktycznie bardzo istotne. Sprowadza się ono najczęściej do problemu:

  • szukania miejsc zerowych funkcji pochodnych;
  • iteracyjnych metod poszukiwania minimum (maksimum) metodami, które bardzo często sprowadzają się do lokalnego wyznaczania kierunku spadku funkcji (czyli lokalnego wyznaczania pochodnej).

Ale oprócz opisanych zadań możemy mieć do czynienia z zadaniami bardziej skomplikowanymi w których poszukujemy minimum (maksimum) uwzględniając ograniczenia narzucone na zmienne:

  • na przykład zakres,
  • oczekiwanie, że spełniają inne wymogi (na przykład są liczbami całkowitymi).

Ograniczenia

Najprostszą metodą uwzględnienia ograniczeń jest dodanie kary za przekroczenie ograniczeń. Jeżeli funkcja kary jest dobrana odpowiednio — działa to całkiem nieźle…

Programowanie liniowe

Szczególnym przypadkiem jest zadania optymalizacji gdy funkcja celu jest funkcją liniową o postaci:

\[f(x) = \sum_{i=1}^{N} a_{i}x_{i}\]

Funkcja taka maleje (rośnie) bez ograniczeń. Stąd zazwyczaj są to zadania optymalizacji z ograniczeniami postaci: \[
\sum_{j=0}^{N}\alpha_{j}^{k} x_{j} \le \beta^{k}; \quad k=1,2,\ldots M
\]
Bardzo często wymaga się również aby \(x_{j}\) były dodatnie (lub nieujemne).

Szczególnym przypadkiem są zadania w którym pojawiają się znaki równości w ograniczeniach. Wymagają one specjalnych metod postępowania.

Łatwo pokazać, że optimum funkcji z takimi ograniczeniami realizuje się na krawędzi (w wierzchołku) obszaru rozwiązań dopuszczalnych.

Istnieją specjalne metody rozwiązywania tego typu zagadnień. Najpopularniejszą jest metoda simplex.

Programowanie liniowe całkowitoliczbowe

Bardzo szczególnym przypadkiem może być zadanie identyczne z powyższym w którym dodano kolejne ograniczenie: wszystkie (lub niektóre) zmienne decyzyjne \(x_{i}\) mogą przyjmować tylko wartości całkowite. Zadania takie zazwyczaj pojawiają się w ekonomi.

Łatwo można pokazać, że rozwiązanie problemu bez ograniczenia na całkowitoliczbowość, a następnie „zaokrąglenie” wybranych zmiennych do wartości całkowitych ie prowadzi do rozwiązań optymalnych.

Opracowano specjalne metody rozwiązywania tego typu zadań.

Optymalizacja „dyskretna”

Kolejnym, szczególnym przypadkiem zadani optymalizacji jest optymalizacja dyskretna (to znaczy taka, w której zmienne decyzyjne nie przyjmują wartości ciągłych).

Typowym zadaniem z tej klasy jest zagadnienie komiwojażera (codziennie rozwiązywane1 przez kurierów rozwożących przesyłki).

W zadaniu tym trzeba wybrać optymalną (najtańszą, zajmującą najmniej czasu,…) trasę dla kuriera (uwzględniającą dodatkowo ograniczenia czasowe dla odbiorców, pojemność i nośność pojazdu,…)

W najprostszym przypadku złożoność obliczeniowa tego problemu jest rzędu \(O(n!)\).

Przykłady

  1. Przygotowany notatnik jupyter zawiera przykład optymalizacji funkcji jednej i dwu zmiennych w Pythonie
  2. Na stronie Linear programming and discrete optimization with Python using PuLP są bardzo ładne przykłady opisujące programowanie liniowe i całkowitoliczbowe. Notatniki pobrać można z GitHuba. Wymagają one pakietu PuLP, który standardowo nie jest dostępny w anakondzie. Można o dodać wykonując następujące polecenie:
  3.  

  1. Albo i nie.↩︎