Metody optymalizacji

Optymalizacja to jedno pytanie zadane na pięć sposobów: gdzie funkcja osiąga kres przy zadanych ograniczeniach. Przy ograniczeniach liniowych odpowiedź zawsze leży w wierzchołku — i stąd sympleks. Bez ograniczeń wystarczy iść pod prąd gradientu. Z nierównościami wchodzą warunki KKT. Każda z tych metod jest tu faktycznie uruchamiana, a wyniki porównywane z drugą, niezależną drogą obliczeń.

max cᵀx, Ax ≤ b

Programowanie liniowe

Obszar dopuszczalny, przesuwająca się poziomica celu i wierzchołek optymalny

optimum zawsze w wierzchołku
TABLICA

Metoda sympleks

Prawdziwe tablice sympleksowe krok po kroku, z podglądem wędrówki po wierzchołkach

baza → sąsiedni wierzchołek
xₖ₊₁ = xₖ − α∇f

Spadek gradientowy

Zygzak przy źle uwarunkowanym zadaniu i próg α, powyżej którego metoda ucieka

α < 2/λmax
∇f + λ∇g = 0

Warunki KKT

Ograniczenie aktywne i nieaktywne, mnożnik λ ≥ 0 i komplementarność

λ·g(x) = 0
PERT / CPM

Ścieżka krytyczna

ES, EF, LS, LF i zapasy czasu w sieci zadań — z harmonogramem Gantta

zapas = LS − ES
Σ cᵢⱼxᵢⱼ → min

Zagadnienie transportowe

Dwie heurystyki startowe zestawione z rozwiązaniem optymalnym policzonym przeglądem wszystkich baz

m + n − 1 komórek bazowych
TABLICA DP

Programowanie dynamiczne

Plecak 0/1: tablica wypełniana wiersz po wierszu, odtworzona ścieżka wyboru i porównanie z zachłannością

D[i][c] = max(D[i−1][c], D[i−1][c−wᵢ] + vᵢ)
V = max_a [r + γPV]

Procesy decyzyjne Markowa

Kiedy wymienić maszynę: iteracja wartości krok po kroku, strategia progowa i tempo zbieżności γᵏ

‖V_k − V*‖ ≤ γᵏ·‖V₀ − V*‖
ZADANIA

Przykłady krok po kroku

Rozwiązanie graficzne, jedna iteracja sympleksu, KKT z komplementarnością

3 rozwiązane zadania

Programowanie liniowe — rozwiązanie graficzne

Funkcja celu jest liniowa, więc jej poziomice to proste równoległe. Przesuwając je w kierunku wzrostu, ostatni punkt kontaktu z obszarem dopuszczalnym to optimum — a ten zawsze da się wybrać w wierzchołku. To jest cały powód, dla którego sympleks może przeglądać wyłącznie wierzchołki.
liczba wierzchołków–
optimum z*–
w punkcie–
ograniczenia aktywne w optimum–
obszar dopuszczalny, poziomica celu i wierzchołek optymalny

Metoda sympleks krok po kroku

Sympleks startuje w wierzchołku (tu: początek układu, baza ze zmiennych swobodnych) i w każdym kroku przechodzi do sąsiedniego wierzchołka o lepszej wartości celu. Kolumnę wejściową wskazuje ujemny współczynnik w wierszu celu, wiersz wyjściowy — test ilorazów, który pilnuje, żeby nie wyjść poza obszar dopuszczalny.
baza–
bieżący wierzchołek–
wartość celu z–
kolumna wejściowa / wiersz wyjściowy–
kontrola: przegląd wierzchołków–
tablica sympleksowa w tym kroku
wędrówka po wierzchołkach obszaru

Spadek gradientowy

xₖ₊₁ = xₖ − α·∇f(xₖ)
Dla funkcji kwadratowej o wartościach własnych hesjanu λmin, λmax metoda zbiega wtedy i tylko wtedy, gdy 0 < α < 2/λmax, a tempo zbieżności zależy od wskaźnika uwarunkowania κ = λmax/λmin.
λmin, λmax hesjanu–
próg zbieżności α < 2/λmax–
‖xₙ − x*‖–
zmierzony iloraz zbieżności–
teoria dla tego α: max|1−α|, |1−ακ|–
najlepsze możliwe α* i jego tempo–
ścieżka iteracji na mapie poziomic
błąd ‖xₖ − x*‖ (skala log)

Warunki Karusha-Kuhna-Tuckera

Dla zadania min f(x) przy g(x) ≤ 0 optimum spełnia cztery warunki naraz:
1. ∇f + λ∇g = 0 (stacjonarność)
2. g(x) ≤ 0 (dopuszczalność)
3. λ ≥ 0 (nieujemność)
4. λ·g(x) = 0 (komplementarność)
Czwarty warunek mówi: albo ograniczenie jest napięte (g = 0), albo nie działa wcale (λ = 0).
min (x−a)² + (y−b)²
p.w. g(x,y) = x² + y² − r² ≤ 0
rozwiązanie x*–
mnożnik λ–
g(x*)–
λ·g(x*) — komplementarność–
‖∇f + λ∇g‖ — stacjonarność–
status ograniczenia–
poziomice celu, ograniczenie i gradienty w optimum

Ścieżka krytyczna (CPM)

Przejście „w przód” daje najwcześniejsze terminy ES i EF, przejście „w tył” — najpóźniejsze LS i LF. Różnica to zapas czasu. Zadania o zerowym zapasie tworzą ścieżkę krytyczną: każde opóźnienie na niej opóźnia cały projekt.
ES = max(EF poprzedników)
LF = min(LS następników)
zapas = LS − ES = LF − EF
czas trwania projektu–
ścieżka krytyczna–
suma czasów na ścieżce–
zadania w toku w chwili t–
sieć zależności; czerwone = ścieżka krytyczna
harmonogram Gantta z zapasami czasu

Zagadnienie transportowe

Trzej dostawcy o podażach aᵢ, czterej odbiorcy o popytach bⱼ, koszt przewozu jednostki cᵢⱼ. Szukamy planu xᵢⱼ ≥ 0, który pokrywa cały popyt i wyczerpuje całą podaż, minimalizując Σ cᵢⱼxᵢⱼ. Rozwiązanie bazowe ma dokładnie m + n − 1 = 6 niezerowych komórek — i tworzą one drzewo w grafie dostawcy–odbiorcy.

Programowanie dynamiczne — plecak 0/1

Zamiast sprawdzać 2ⁿ podzbiorów, budujemy tablicę: D[i][c] to największa wartość, jaką da się zmieścić w pojemności c, mając do dyspozycji pierwsze i przedmiotów. Każda komórka to jedna decyzja — brać i-ty przedmiot czy nie:
D[i][c] = max( D[i−1][c], D[i−1][c−wᵢ] + vᵢ )
Odpowiedź stoi w prawym dolnym rogu, a ścieżka wstecz mówi, które przedmioty wybrać.

Procesy decyzyjne Markowa

Maszyna ma pięć stanów zużycia (0 = nowa, 4 = zajeżdżona). W każdym kroku wybieramy: użytkuj — zysk maleje ze zużyciem, a maszyna z pewnym prawdopodobieństwem psuje się dalej — albo wymień — płacimy K i wracamy do stanu 0. Szukamy strategii maksymalizującej zysk zdyskontowany współczynnikiem γ.
V(s) = max_a [ r(s,a) + γ·Σ P(s′|s,a)·V(s′) ]

Przykład 1 — rozwiązanie graficzne zadania PL

Zmaksymalizuj z = 3x + 5y przy ograniczeniach x + 2y ≤ 14, 3x + y ≤ 18, x − y ≤ 4, x, y ≥ 0.

1. Obszar dopuszczalny to część wspólna pięciu półpłaszczyzn — wielokąt wypukły. Jego wierzchołki znajdujemy, przecinając ograniczenia parami i odrzucając punkty niedopuszczalne.
2. Kandydaci:
   • x = 0, y = 0 → (0, 0), z = 0
   • y = 0 ∩ x − y = 4 → (4, 0), z = 12
   • x − y = 4 ∩ 3x + y = 18 → 3x + (x−4) = 18, x = 5,5, y = 1,5 → z = 24
   • 3x + y = 18 ∩ x + 2y = 14 → y = 18 − 3x, x + 36 − 6x = 14, x = 4,4, y = 4,8 → z = 37,2
   • x = 0 ∩ x + 2y = 14 → (0, 7), z = 35
3. Punkt y = 0 ∩ 3x + y = 18 dałby (6, 0), ale narusza x − y ≤ 4 (6 > 4) — odpada.
4. Największa wartość: z* = 37,2 w punkcie (4,4 ; 4,8).
5. Które ograniczenia są tam aktywne (spełnione z równością)? Sprawdzamy: x + 2y = 4,4 + 9,6 = 14 ✓ oraz 3x + y = 13,2 + 4,8 = 18 ✓. Trzecie: x − y = −0,4 < 4 — nieaktywne. Wierzchołek leży na przecięciu dwóch aktywnych ograniczeń, co w ℝ² jest regułą.
6. Interpretacja poziomicy: prosta 3x + 5y = z przesuwa się równolegle; ostatni jej kontakt z wielokątem to właśnie ten wierzchołek. Gdyby wektor celu był równoległy do którejś krawędzi (np. c = (3 ; 6) przy krawędzi x + 2y = 14), optimum przyjmowałby cały odcinek — rozwiązań byłoby nieskończenie wiele, ale wartość z* wciąż jedna.

Przykład 2 — pierwsza iteracja sympleksu dla tego samego zadania

1. Dodajemy zmienne swobodne s₁, s₂, s₃, zamieniając nierówności w równania:
   x + 2y + s₁ = 14,  3x + y + s₂ = 18,  x − y + s₃ = 4.
2. Baza początkowa to {s₁, s₂, s₃}, czyli wierzchołek x = y = 0 (z = 0). Wiersz celu zapisujemy jako z − 3x − 5y = 0, więc w tablicy stoją współczynniki −3 i −5.
3. Kolumna wejściowa: najbardziej ujemny współczynnik to −5 przy y — wprowadzamy y do bazy (kryterium największego wzrostu na jednostkę).
4. Test ilorazów (tylko dodatnie elementy kolumny y):
   wiersz s₁: 14/2 = 7  ·  wiersz s₂: 18/1 = 18  ·  wiersz s₃: −1 < 0, pomijamy.
   Najmniejszy iloraz to 7 → z bazy wychodzi s₁. Element centralny: 2.
5. Po przeliczeniu tablicy nowa baza to {y, s₂, s₃}, a wierzchołek to (0 ; 7), z = 35. Odpowiada to przejściu wzdłuż osi y aż do ograniczenia x + 2y ≤ 14.
6. W wierszu celu zostaje jeszcze jeden ujemny współczynnik (przy x), więc nie jesteśmy w optimum — kolejna iteracja wprowadza x i prowadzi do (4,4 ; 4,8) z z = 37,2, zgodnie z Przykładem 1.
7. Dlaczego test ilorazów pomija ujemne elementy: zwiększanie zmiennej wchodzącej zwiększa tam wartość zmiennej bazowej, więc to ograniczenie nigdy nie zostanie naruszone. Gdyby cała kolumna była niedodatnia, zadanie byłoby nieograniczone. Zakładka „Metoda sympleks” pokazuje każdą tablicę i równolegle sprawdza wynik pełnym przeglądem wierzchołków.

Przykład 3 — KKT: najbliższy punkt koła

Zminimalizuj f(x,y) = (x−3)² + (y−1)² przy warunku g(x,y) = x² + y² − 4 ≤ 0.

1. Cel (3, 1) leży w odległości √(9+1) = √10 ≈ 3,162 od początku, a promień to 2. Cel jest więc poza zbiorem dopuszczalnym — ograniczenie będzie aktywne.
2. Zapisujemy stacjonarność: ∇f = (2(x−3), 2(y−1)), ∇g = (2x, 2y), więc 2(x−3) + λ·2x = 0 i 2(y−1) + λ·2y = 0.
3. Stąd x(1+λ) = 3 oraz y(1+λ) = 1, czyli (x, y) = (3, 1)/(1+λ) — rozwiązanie leży na półprostej od początku do celu. Geometrycznie oczywiste: najbliższy punkt koła to rzut celu na okrąg.
4. Z komplementarności λ > 0 wymusza g = 0, czyli x² + y² = 4. Podstawiając: 10/(1+λ)² = 4, więc (1+λ)² = 2,5 i 1 + λ = √2,5 ≈ 1,5811, czyli λ ≈ 0,5811.
5. Rozwiązanie: x* = 3/1,5811 ≈ 1,8974, y* = 1/1,5811 ≈ 0,6325. Kontrola: x*² + y*² = 3,600 + 0,400 = 4,000 ✓ leży na okręgu.
6. Wszystkie cztery warunki KKT: stacjonarność ✓ (z konstrukcji), dopuszczalność g = 0 ≤ 0 ✓, λ = 0,5811 ≥ 0 ✓, komplementarność λ·g = 0,5811 · 0 = 0 ✓.
7. Przypadek przeciwny: gdyby cel leżał wewnątrz koła, np. (0,5 ; 0,5), ograniczenie by nie działało — rozwiązaniem byłby sam cel, λ = 0, a g = −3,5 < 0. Komplementarność znów spełniona, tym razem drugim członem. Przyciski na zakładce „Warunki KKT” ustawiają oba przypadki; aplikacja liczy λ, sprawdza stacjonarność i komplementarność liczbowo.