Kompendium Metod Optymalizacji (MOO)

Opracowanie na podstawie arkuszy kolokwialnych 2024-2025.

1. Metoda Wolfe'a (Programowanie Kwadratowe)

Cel: Zamienić trudną funkcję z kwadratami ($x^2$) na duży układ prostych równań liniowych.

ALGORYTM POSTĘPOWANIA
1. Uporządkuj funkcję celu: Zsumuj wyrazy podobne. Musisz mieć postać: $ax_1^2 + bx_1x_2 + cx_2^2 + dx_1 + ex_2$.
2. Wyznacz macierz Q (Hessian):
  • Na przekątnej (pozycje 1,1 i 2,2): Współczynniki przy kwadratach ($x_1^2, x_2^2$) pomnóż przez 2.
  • Poza przekątną (pozycje 1,2 i 2,1): Współczynnik przy $x_1x_2$ podziel przez 2.
3. Wyznacz wektor c: Są to liczby stojące przy pojedynczych $x_1$ i $x_2$.
4. Zbuduj układ równań (Wynik): Użyj wzoru macierzowego: $$ \begin{cases} Qx + A^T\lambda - u = -c \\ Ax + s = b \end{cases} $$ Pamiętaj: Po prawej stronie pierwszego równania zmieniasz znaki wektora $c$ na przeciwne!
PRZYKŁAD (Zadanie 1A z 2025) [cite: 1]

Zadanie: Min $f(x) = 2x_1 + 3x_1x_2 + x_1^2 - 3x_2 + x_2x_1 + 5x_2^2$
Ograniczenia: $3x_1 + 2x_2 \le 6$ oraz $5x_1 + 3x_2 \le 15$.

Krok 1 (Porządkowanie):
Mamy $3x_1x_2$ oraz $x_2x_1$. Suma = $4x_1x_2$.
$f(x) = \underbrace{1}_{a}x_1^2 + \underbrace{4}_{b}x_1x_2 + \underbrace{5}_{c}x_2^2 + \underbrace{2}_{d}x_1 \underbrace{- 3}_{e}x_2$
Krok 2 (Macierz Q):
Przekątna: $1 \cdot 2 = 2$ oraz $5 \cdot 2 = 10$.
Boki: $4 / 2 = 2$.
$$Q = \begin{bmatrix} 2 & 2 \\ 2 & 10 \end{bmatrix}$$
Krok 3 (Wektor c i A):
Liniowe elementy to $2x_1$ i $-3x_2$. Zatem $c = [2, -3]^T$.
Macierz ograniczeń $A$ (z nierówności): wiersz 1 to $[3, 2]$, wiersz 2 to $[5, 3]$.
Krok 4 (Zapis układu - Rozwiązanie):
Prawa strona równania to $-c$, czyli $[-2, 3]^T$.
Transpozycja $A^T$ zamienia wiersze na kolumny.

Równania od gradientu ($Qx + A^T\lambda - u = -c$):
1) $2x_1 + 2x_2 + 3\lambda_1 + 5\lambda_2 - u_1 = -2$
2) $2x_1 + 10x_2 + 2\lambda_1 + 3\lambda_2 - u_2 = 3$

Równania od ograniczeń ($Ax + s = b$):
3) $3x_1 + 2x_2 + s_1 = 6$
4) $5x_1 + 3x_2 + s_2 = 15$

Warunki (obowiązkowe!):
$x_i \cdot u_i = 0, \ \lambda_i \cdot s_i = 0, \ \text{wszystkie zmienne } \ge 0$.

2. Warunki KKT (Szukanie Ekstremum)

wiecej...

Cel: Sprawdzić, czy rozwiązanie leży w "dołku" w środku obszaru, czy zatrzymało się na "płocie" (ograniczeniu).

ALGORYTM POSTĘPOWANIA
1. Lagrange: Zapisz funkcję $L(x, \lambda) = f(x) + \lambda \cdot (LewaStrona - PrawaStrona)$.
Ważne: Ograniczenie musi być w postaci $\le 0$.
2. Pochodne (Gradient): Policz pochodne po $x_1$ i $x_2$. Przyrównaj do zera.
3. Testowanie przypadków (To jest istota zadania):
  • Przypadek A (Wnętrze): Załóż, że $\lambda = 0$. Oblicz $x$ z pochodnych. Sprawdź, czy wynik spełnia ograniczenie. Jeśli tak -> Koniec. Jeśli nie -> Przypadek B.
  • Przypadek B (Krawędź): Załóż, że ograniczenie jest równością ($=0$). Rozwiąż układ równań z pochodnymi i ograniczeniem. Sprawdź, czy $\lambda \ge 0$.
PRZYKŁAD (Zadanie 2 - Rekonstrukcja) [cite: 2]

Zadanie: Min $f(x) = (x_1 - 4)^2 + (x_2 - 4)^2$ przy $x_1 + x_2 \le 3$.

Krok 1 (Lagrange):
Przenosimy 3 na lewo: $x_1 + x_2 - 3 \le 0$.
$L = (x_1 - 4)^2 + (x_2 - 4)^2 + \lambda(x_1 + x_2 - 3)$
Krok 2 (Pochodne):
I. $2(x_1 - 4) + \lambda = 0 \implies 2x_1 = 8 - \lambda$
II. $2(x_2 - 4) + \lambda = 0 \implies 2x_2 = 8 - \lambda$
Krok 3 (Przypadek A - $\lambda=0$):
Wtedy $2x_1 = 8 \to x_1=4$. Podobnie $x_2=4$.
Wstawiamy do ograniczenia: Czy $4 + 4 \le 3$? Nie ($8 > 3$).
Wniosek: Punkt $(4,4)$ jest poza dozwolonym obszarem. Odrzucamy.
Krok 3 (Przypadek B - Krawędź $x_1+x_2=3$):
Z równań (I) i (II) widzimy, że $2x_1 = 2x_2 \to x_1 = x_2$.
Wstawiamy do ograniczenia: $x_1 + x_1 = 3 \to 2x_1 = 3 \to x_1 = 1.5$.
$x_2 = 1.5$.
Obliczamy $\lambda$ z równania (I): $2(1.5) + \lambda = 8 \to 3 + \lambda = 8 \to \lambda = 5$.
Werdykt: Ponieważ $\lambda = 5 \ge 0$, jest to poprawne rozwiązanie optymalne.

3. Metoda Sympleks (Liniowe)

Cel: Rozwiązać zadanie "mechanicznie" w tabelce.

ALGORYTM POSTĘPOWANIA
1. Postać Standardowa: Zamień nierówności na równania, dodając zmienne $s$ (plusowe). Przenieś zmienne decyzyjne ($x$) na lewą stronę. Wyraz wolny ($b$) musi być dodatni.
2. Tabela: Wpisz współczynniki. Wiersz funkcji celu ($J$) wpisz ze zmienionymi znakami.
3. Wybór Pivota (Klucza):
  • Kolumna wejściowa: Najbardziej ujemna liczba w wierszu $J$.
  • Wiersz wyjściowy: Podziel kolumnę Wynik przez kolumnę wejściową (tylko liczby dodatnie). Wybierz najmniejszy iloraz.
4. Gaussa (Nowa Tabela): Zrób 1 w miejscu Pivota (dzieląc wiersz) i 0 w reszcie kolumny (odejmując wiersze).
PRZYKŁAD (Zadanie 3 z 2024) [cite: 4]

Zadanie: Max $J = x_1 + 4x_2$.
Ograniczenie 1: $x_2 \le 2x_1 + 2$.
Ograniczenie 2: $2x_1 \le 6$.

Krok 1 (Standardyzacja):
Ogr 1: $-2x_1 + x_2 + s_1 = 2$ (przeniesiono $2x_1$ na lewo, dodano $s_1$).
Ogr 2: $2x_1 + s_2 = 6$ (dodano $s_2$).
Funkcja Celu: $J - x_1 - 4x_2 = 0$.
Krok 2 i 3 (Tabela startowa):
Baza x1 x2 s1 s2 Wynik Iloraz
s1 -2 1 (Pivot) 1 0 2 2/1 = 2 (MIN)
s2 2 0 0 1 6 ---
J -1 -4 0 0 0
Kolumna $x_2$ wchodzi (bo -4 jest najmniejsze). Wiersz $s_1$ wychodzi (bo iloraz 2 jest mniejszy niż brak ilorazu).
Krok 4 (Przeliczenie - Iteracja 1):
Wiersz Pivota ($s_1$) dzielimy przez 1 (bez zmian): $[-2, 1, 1, 0, 2]$. To teraz wiersz $x_2$.
Zerujemy dół (Wiersz $J$):
Stary $J$: $[-1, -4, 0, 0, 0]$
Operacja: $J_{nowy} = J_{stary} - (-4) \cdot Wiersz_{x2}$ (czyli dodajemy $4 \times$ wiersz góry).
$x_1$: $-1 + 4(-2) = -9$
$x_2$: $-4 + 4(1) = 0$
$s_1$: $0 + 4(1) = 4$
Wynik: $0 + 4(2) = 8$.
Nowa tabela ma wiersz celu: $[-9, 0, 4, 0, 8]$. Algorytm idzie dalej, bo mamy $-9$ (kolejna iteracja wymagałaby wzięcia kolumny $x_1$).

4. Dualność

Cel: Napisać "lustrzane odbicie" zadania.

ALGORYTM POSTĘPOWANIA
Zasada Transpozycji: Czytaj tabelę problemu pierwotnego PIONOWO, żeby napisać problem dualny POZIOMO.
  • Max $\leftrightarrow$ Min.
  • Liczby "Wynik" z (P) stają się współczynnikami funkcji celu w (D).
  • Kolumny z (P) stają się wierszami (ograniczeniami) w (D).
  • Kierunek nierówności się odwraca ($\le$ zamienia się na $\ge$).
PRZYKŁAD [cite: 10, 11]

Pierwotny (P): Max $J = x_1 + 4x_2$.
Ogr 1: $-2x_1 + 1x_2 \le 2$
Ogr 2: $2x_1 + 0x_2 \le 6$

Dualny (D):
1. Funkcja celu: Bierzemy prawe strony (2 i 6).
Min $W = 2y_1 + 6y_2$.

2. Ograniczenia (czytamy kolumny P):
Kolumna $x_1$: ma współczynniki $-2$ i $2$. W celu było $1$.
Ogr D1: $-2y_1 + 2y_2 \ge 1$.

Kolumna $x_2$: ma współczynniki $1$ i $0$. W celu było $4$.
Ogr D2: $1y_1 + 0y_2 \ge 4$.