Sekwencyjne Programowanie Liniowe (SLP)

Algorytm SLP służy do szukania minimum funkcji (dalej zwanej funkcją celu) przy zadanych ograniczeniach:

• nierównościowych:

• równościowych:

• ograniczeniach ruchu (ang. move limits), które wyznaczają w dziedzinie funkcji f potencjalnie interesujący obszar, w którym są poszukiwane rozwiązania. Ponadto ograniczenia ruchu zapobiegają rozbieżności algorytmu w początkowej fazie obliczeń (gdy pozostałe ograniczenia nie są jeszcze dokładnie uwzględniane). Ograniczenia ruchu są odpowiednio modyfikowane w trakcie wykonywania algorytmu.

Dodatkowo musi być spełnione założenie, że istnieją pochodne funkcji celu oraz funkcji ograniczeń.

Uwaga: Ograniczenia innych postaci można sprowadzić do postaci w/w:

Algorytm SLP polega na sprowadzeniu minimalizacji nieliniowej funkcji celu przy nieliniowych ograniczeniach do ciągu minimalizacji liniowej funkcji celu przy liniowych ograniczeniach (czyli tzw. zadania programowania liniowego - LP). Takie postępowanie jest szczególnie skuteczne dla funkcji słabo nieliniowych, ponieważ ich liniowe przybliżenie jest dość dokładne, a problem LP jesteśmy w stanie rozwiązywać bardzo szybko, nawet przy dużej liczbie zmiennych decyzyjnych.

Sposób działania algorytmu SLP:

Oznaczenia:

X₀ – będzie pierwszym przybliżeniem rozwiązania (wektor w R^N).

G – macierzą zawierającą współczynniki liniowych ograniczeń nie równościowych (o wymiarze N na ilość ograniczeń nie równościowych).

R – macierzą zawierającą współczynniki liniowych ograniczeń równościowych (o wymiarze N na ilość ograniczeń równościowych).

i – licznikiem iteracji

Przebieg obliczeń:

1. i = 0, X₀ = punkt dopuszczalny (spełniający move limits) -każda jego współrzędna jest środkiem przedziału wyznaczonego przez ograniczenia ruchu.

2. dodaj move limits do macierzy G

3. zlinearyzuj (rozwiń w szereg Taylora z dokładnością do czynnika liniowego) funkcje f w punkcie X_i, otrzymując w wyniku liniową funkcje flin

4. i := i + 1

5. rozwiąż problem LP minimalizując funkcje flin przy ograniczeniach nierównościowych zdefiniowanych przez macierz G, oraz równościowych określonych przez macierz R, rozwiązanie przypisz do X_i

6. zbadaj w jakim stopniu naruszone są oryginalne ograniczenia w punkcie X_i :

• jeśli naruszenie ograniczeń zarówno równościowe jak i nierównościowych mieści się w granicy błędu to zakończ (rozwiązaniem jest Xi)

• jeśli którekolwiek z naruszeń ograniczeń równościowych nie mieści się w granicy błędu, to wybierz najbardziej naruszone ograniczenie, zlinearyzuj je w punkcie X_i i dodaj wynik linearyzacji do macierzy R

• jeśli którekolwiek z naruszeń ograniczeń nie równościowych nie mieści się w granicy błędu, to wybierz najbardziej naruszone ograniczenie, zlinearyzuj je w punkcie X_i i dodaj wynik linearyzacji do macierzy G

7. zmodyfikuj ograniczenia ruchu tak by punkt X_i leżał po środku każdego z przedziałów wyznaczonych przez nie (zmiany uwzględnij w macierzy G) oraz popraw ich długość dla każdej (k-tej) współrzędnej, mnożąc ją przez wsp, gdzie:

• jeżeli to wsp = 2,5

• jeżeli to wsp = 0,5

(to k-ta współrzędna punktu X_i)

8. jeśli licznik iteracji i nie przekroczył dopuszczalnego limitu to przejdź do punktu 3