Zgryźliwość kojarzy mi się z radością, która źle skończyła.
Skrypt niniejszy ma za zadanie przedstawić metody obliczeniowe optymalizacji, w odróżnieniu od podstaw teoretycznych. Uznano, że użytkownicy tego skryptu w zasadzie znają teorię optymalizacji, lecz brak im umiejętności rozwiązywania zadań praktycznych. W rozwiązaniu tym, jak można przewidzieć, rolę podstawową odgrywa elektroniczna technika obliczeniowa. Tym niemniej, raczej dla wygody Czytelnika niż w celu wykładowym, w skrypcie przedstawione są w skrócie najważniejsze rezultaty współczesnej teorii optymalizacji; podana jest również odpowiednia źródłowa literatura.
Skrypt opracowany był z myślą o studentach specjalności automatyka; nie oznacza to oczywiście, że przedstawione tu metody obliczeniowe są specyficzne dla automatyki. Zadania optymalizacji występują w wielu dziedzinach, a po ich matematycznym sformułowaniu przestaje być istotne, z jakiego konkretnego problemu powstały. Specyfika automatyki odbiła się na skrypcie w ten sposób, że bardzo mało uwagi poświęcono zadaniom programowania liniowego. Zagadnienia optymalizacji procesów produkcyjnych prowadzą bowiem zazwyczaj do zadań programowania nieliniowego lub zadań optymalizacji dynamicznej. W związku z tym skrypt niniejszy poświęcony jest w zasadzie metodom, służącym do rozwiązywania zadań następujących:
a) Znaleźć
(1)
gdzie f(x) jest funkcją n zmiennych x1, x2, ..., xn
- przy warunkach ubocznych („ograniczeniach”)
, i = 1,...,m (2)
gdzie gi(x) są funkcjami zmiennych x1, x2,...,xn, a bi danymi liczbami; rozwiązania tego zadania są liczbami .
b) Znaleźć
(3)
gdzie Q[x(t), u(t), t] jest funkcjonałem określonym na funkcjach zmiennej niezależnej t, t Î[t1, t2]
- przy warunkach ubocznych („więzach”)
(4)
gdzie (4) oznacza układ n równań różniczkowych pierwszego rzędu, tzn. oznacza wektor złożony z pochodnych ; rozwiązania tego zadania są funkcjami zmiennej niezależnej, , określonymi na przedział sterowania t Î[t1, t2].
Zadania typu (a) należą do dziedziny tzw. programowania nieliniowego; nazywa się je też niekiedy zadaniami optymalizacji statycznej. Poświęcona im jest część I skryptu. Zadania typu (b) należą do dziedziny optymalizacji dynamicznej; w skrypcie zajmuje się nimi część II.
Jeżeli, z innej strony patrząc, rozpatrywać zadania optymalizacji sterowania procesami produkcyjnymi, to łatwo jest podzielić je na dwie grupy:
- zadania optymalizacji stanu ustalonego,
- zadania optymalizacji dynamicznej.
W grupie pierwszej znajdą się przypadki wtedy, gdy proces produkcyjny ma charakter procesu ciągłego, jak to ma np. miejsce w przypadku wytwarzania kwasu siarkowego z siarki czy amoniaku z gazu ziemnego. Optimum średniej wydajności, średniego kosztu przy zadanej wydajności czy innego podobnego wskaźnika otrzymuje się wówczas najczęściej w sytuacji, gdy bieg procesu jest stały w czasie. Pozwala to przyjąć, jako element rozwiązania optymalnego, że pochodne względem czasu wszelkich zmiennych są równe zeru. Jeżeli obiekt ma stałe skupione, czyli jego równania stanu są np. postaci (4), to założenie stanu ustalonego oznacza, że opis ten przyjmuje postać równań typu (2)
(5)
Pisząc (5) założono dla uproszczenia, że równania (4) nie zależą od czasu. Związki (5) pokazują, że zadanie optymalizacji stanu ustalonego sprowadzi się do zadania programowania nieliniowego, czyli zadania typu (a).
Zadania optymalizacji dynamicznej procesów produkcyjnych powstają przede wszystkim wówczas, gdy proces jest prowadzony jako tzw. proces cykliczny. Przykładem może być proces wytopu w piecu stalowniczym: w czasie trwania procesu zmienia się temperatura, skład chemiczny itd., aby w chwili zakończenia procesu osiągnąć pewne zadane wartości. Istotne są zatem równania różniczkowe, opisujące obiekt, a zadanie matematyczne przyjmuje postać typu (b).
W niektórych przypadkach zadania optymalizacji stanu ustalonego mogą przybrać postać zadań optymalizacji dynamicznej, tj. zadań typu (b). Na przykład, gdy w obiekcie o stałych rozłożonych zmienne xi są funkcjami czasu t oraz długości l, równania stanu mogą przyjąć postać
(6)
gdzie x = x(l,t), u = u(l,t). W stanie ustalonym procesu równania (6) sprowadzają się do
(7)
Równania (7) nie są różniczkowe względem zmiennej t, lecz zawierają pochodne względem zmiennej l. Jest to zatem zadanie optymalizacji z więzami różniczkowymi; jest ono typu (b), a rozwiązanie będzie w postaci , czyli w postaci funkcji zmiennej l.
Część I
PROGRAMOWANIE NIELINIOWE I LINIOWE
1. Podstawowe sformułowania i definicje
1.1. Zadania programowania nieliniowego i liniowego
Zadaniem programowania nazywany będzie problem następujący: Znaleźć wektor , który minimalizuje bądź maksymalizuje skalarną funkcję
(1)
spełniając równocześnie układ równań lun nierówności o postaci (A)
, i = 1,...,m (2)
przy czym x jest n-wymiarowym wektorem kolumnowym, złożonym z elementów x1, x2, ..., xn. Zakłada się przy tym, że znane są postaci analityczne funkcji (1) oraz zależności (2), jak również wartości stałych bi. W wielu przypadkach powyższe sformułowanie uzupełnione jest dodatkowymi wymaganiami; np. żąda się, aby niektóre bądź wszystkie zmienne niezależne xj były nieujemne (tzn. xj ³ 0 dla j = 1,...,n) lub też, aby przyhmowały tylko określone wartości dyskretne. Wartość nazwano rozwiązaniem zadania optymalizacji (zadania programowania). Wartość f() nazwano ekstremum warunkowym funkcji f(x).
Funkcja (1) będzie dalej nazywana „funkcją celu”, natomiast zbiór zależności (2) – „zbiorem ograniczeń”. W zbiorze tym w każdym z ograniczeń może występować tylko jeden ze znaków wymienionych w zależności (2). Liczba ograniczeń m może być dowolna, to znaczy m może zarówno być większe, mniejsze jak i równe n. W przypadku gdy m = 0 rozpatrywane przez nas zadanie sprowadza się do problemu optymalizacji funkcji wielu zmiennych bez ograniczeń. Ten szczególny przypadek ma bardzo duże znaczenie przy poszukiwaniu ekstremum metodami iteracyjnymi i zostanie omówiony oddzielnie.
Zadania programowania (optymalizacji statycznej) dzielą się na dwie podstawowe grupy:
- zadania programowania liniowego,
- zadania programowania nieliniowego.
Jeżeli funkcja celu (1) i zbiór ograniczeń (2) są liniowe tzn. można jest przedstawić w postaci:
(3)
oraz
, i = 1,...,m (4)
przy czym stałe współczynniki aij i cj są znane, to zadanie należy do programowania liniowego. W przytoczonym sformułowaniu warunki (4) uzupełnia się zwykle żądaniem, aby wszystkie zmienne były nieujemne, tzn.
j = 1,...,n (5)
co znacznie ułatwia numeryczne rozwiązanie zadania. Zwróćmy uwagę, że wymaganie to nie zmniejsza w jakimkolwiek stopniu ogólności rozważań, gdyż każde zadanie, w którym zmienne xj są nieograniczonego znaku, można łatwo sprowadzić do postaci (5). Tak więc, zadanie programowania liniowego polega na znalezieniu nieujemnego wektora , który ekstremalizuje liniową funkcję
oraz równocześnie spełnia zbiór ograniczeń (B)
, i = 1,...,m
Problem ten po raz pierwszy został rozwiązany w 1947 roku przez G. Dantzinga, który opracował dla niego metodę Simpleks stosowaną z różnymi modyfikacjami do dnia dzisiejszego.
Wszystkie pozostałe zadania optymalizacji typu (1) i (2), które nie mają postaci (3) i (4), zalicza się do programowania nieliniowego, wyodrębniając przy tym szereg szczególnych przypadków, różniących się pod względem metod ich rozwiązywania:
1. Funkcja celu F jest nieliniowa, ograniczenia są liniowe.
Zadanie programowania nieliniowego sprowadza się tu do wyznaczenia nieujemnego wektora , który minimalizuje lub maksymalizuje nieliniową funkcję
oraz równocześnie spełnia zbiór ograniczeń liniowych (C)
, i = 1,...,m
przy
j = 1,...,n
Zadanie to posiada dwa interesujące przypadki, upraszczające rozwiązanie. W pierwszym funkcja celu ma postać sumy n składników, z których każdy jest funkcją tylko jednej zmiennej xj. Tak więc
(C1)
Funkcja celu posiadająca powyższą własność nazywana jest funkcją addytywną.
W drugim przypadku, funkcja celu może być przedstawiona jako suma formy liniowej i formy kwadratowej, a mianowicie
(C2)
Tego rodzaju problem optymalizacji nazywa się zadaniem programowania kwadratowego.
2. Funkcja celu F oraz ograniczenia są nieliniowe, ale zakładamy ich addytywność. Oznacza to, że w problemie (A) zbiór ograniczeń (2) można przedstawić w postaci
, i = 1,...,m (D)
3. Funkcja celu F oraz ograniczenia są nieliniowe, ale ponadto zadanie na następujące cechy:
- ograniczenia są tylko równowartościowe,
- wszystkie zmienne xj są nieograniczonego znaku,
- m < n, oraz
- zarówno gi(x) jaki f(x) są ciągłe i posiadają przynajmniej drugie pochodne.
W tym przypadku zadanie ma zatem postać: znaleźć wektor , który ekstremalizuje funkcję
(E)
przy warunkach
, i = 1,...,m
Ten typ zadania nosi nazwę „klasycznego problemu optymalizacji”; jego analityczne rozwiązanie zostało po raz pierwszy podane przez Lagrange’a.
Na zakończenie listy poszczególnych przypadków programowania nieliniowego warto wspomnieć o jeszcze dwóch jego rodzajach. Pierwszy z nich nosi nazwę programowania liniowego w liczbach całkowitych i definiowany jest tak jak problem programowania liniowego (B), z tym jednak, że zmienne xj mogą przyjmować tylko wartości całkowite. Drugi natomiast nazywany jest programowaniem stochastycznym; jego celem jest rozwiązanie ogólnego problemu (A), lub jego przypadków szczególnych, w warunkach gdy parametry zadania (np. bi) są zmiennymi przypadkowymi.
Wśród metod stosowanych do rozwiązywania zadań optymalizacji statycznej wyróżnić należy metody analityczne oraz metody numeryczne. Nie istnieją jednak ani metody analityczne, ani numeryczne, pozwalające w sposób ogólny rozwiązać problem (A). Udaje się to tylko w szczególnych przypadkach, których lista prawie w całości została przedstawiona. I tak, metody analityczne dostarczają ogólnego narzędzia dla rozwiązywania „klasycznego problemu optymalizacji” (E) oraz takiej jego modyfikacji, ...