Podręcznik

Zanim zaczniemy szukać rozwiązań, warto wiedzieć, czego w ogóle szukamy. W optymalizacji chodzi o znajdowanie najlepszych możliwych rozwiązań dla danego problemu. A w przypadku minimalizacji – po prostu takich, które dają najmniejszą możliwą wartość jakiejś funkcji. To właśnie tę funkcję nazywamy funkcją celu.

Brzmi ogólnie? To dobrze – bo tak naprawdę minimalizować można praktycznie wszystko: czas produkcji, koszt transportu, ryzyko inwestycji, liczbę strat podczas rozładunku, ilość odpadów, czy nawet… liczbę popełnionych błędów przy projektowaniu mostu.

Funkcja celu – czyli co właściwie minimalizujemy?

Funkcja celu to matematyczny sposób na opisanie tego, co chcemy zoptymalizować. Zazwyczaj oznacza się ją jako $f(x)$, gdzie $x$ to zestaw tzw. zmiennych decyzyjnych – czyli tego, na co mamy wpływ.

Przykład? Proszę bardzo – wróćmy do zadania z poprzedniego rozdziału, w którym projektowaliśmy prostopadłościenne zbiorniki do transportu chemikaliów. Celem było zminimalizowanie kosztów transportu, a zmiennymi decyzyjnymi były wymiary pojemników (np. wysokość, szerokość i długość). Funkcja celu mogła więc wyglądać np. tak:

$f(x_1,x_2,x_3)=z*k_j = \frac{V_{całkowita}}{x_1*x_2*x_3} * (km_A \cdot 2(x_2 \cdot x_3) + km_{góra} \cdot (x_1 \cdot x_2) + k_{transport} )$

Szukaliśmy takiego zestawu wymiarów, który pozwala przewieźć zadaną objętość przy jak najmniejszym koszcie.

Ograniczenia – bo nie wszystko nam wolno

W rzeczywistości nie da się „po prostu” minimalizować. Zawsze są jakieś ograniczenia. To one wyznaczają granice naszej wolności w doborze zmiennych decyzyjnych. Ograniczenia pilnują, żeby proponowane rozwiązanie miało sens praktyczny, fizyczny, techniczny, ekonomiczny albo formalny.

Ograniczenia możemy podzielić na kilka rodzajów:

• Twarde (formalne) – muszą być spełnione zawsze. Ich naruszenie oznacza, że rozwiązanie nie ma prawa istnieć. Np.:

  • $x \geq 0$: długości, czasy, liczby jednostek nie mogą być ujemne,

  • $\sum x_i = 1$: suma udziałów w portfelu inwestycyjnym musi wynosić 100%,

  • $T_r \leq 10,\text{s}$: czas regulacji musi być mniejszy niż 10 sekund.

• Miękkie (preferencyjne) – nie są obowiązkowe, ale zalecane. Zwykle wprowadza się je jako dodatkowe funkcje kary. Np.:

  • "unikaj użycia aluminium, jeśli nie jest konieczne",

  • "preferuj rozwiązania o mniejszej liczbie elementów ruchomych".

• Geometryczne / fizyczne – wynikają z fizyki lub geometrii zadania:

  • pojemnik musi się zmieścić w kontenerze,

  • odległość między pojemnikami nie może być mniejsza niż 1 m,

  • długość pręta musi być większa niż 0, ale mniejsza niż 2,5 m.

• Logiczne – np. zakaz inwestowania w firmy z określonego sektora, ograniczenia zgodne z regulaminem czy normą prawną.

W języku matematyki ograniczenia zapisujemy najczęściej jako:

• nierówności: $g(x) \leq 0$,

• równości: $h(x) = 0$.

W przykładzie portfela inwestycyjnego (z rozdziału 1) ograniczenia wyglądały tak:

• $\sum_{i=1}^4 x_i = 1$ – całość kapitału musi być zainwestowana,

• $x_i \geq 0$ – nie można inwestować ujemnych pieniędzy,

• $\sum_{i=1}^4 x_i \mu_i \geq 0.1$ – oczekiwany zysk powyżej 10%.

W przykładzie sterowania napędem, ograniczenia dotyczyły:

• zakresów parametrów regulatora PID (np. $K_r \in [0.1, 2.5]$),

• dopuszczalnych wartości odchyłki regulacji ($e_\infty \leq 0.05$ mm),

• fizycznych ograniczeń wynikających z modelu siłownika.

A w zadaniu rozmieszczenia pojemników z insektycydem mieliśmy np.:

• pozycje pojemników musiały mieścić się na polu uprawnym,

• minimalna odległość między nimi musiała gwarantować efektywne działanie,

• niektóre rejony mogły być wykluczone ze względów bezpieczeństwa.

Dobre zdefiniowanie ograniczeń to często połowa sukcesu – od nich zależy, czy algorytm będzie przeszukiwał rozsądny obszar przestrzeni, czy błądził w miejscach kompletnie nieużytecznych.

Przestrzeń poszukiwań i rozwiązań dopuszczalnych

Zmiennych decyzyjnych zwykle jest kilka lub kilkanaście. Ich wszystkie możliwe kombinacje tworzą tzw. przestrzeń poszukiwań – czyli wszystkie teoretycznie dostępne rozwiązania.

Ale tylko część z nich spełnia wszystkie ograniczenia – i to właśnie ta część nazywa się przestrzenią rozwiązań dopuszczalnych. Przykładowo: możemy mieć 10 miliardów potencjalnych rozwiązań, ale tylko 5 milionów z nich spełnia warunki techniczne, prawne albo biznesowe.

Z punktu widzenia algorytmu optymalizacyjnego najważniejsze pytanie brzmi:

Przykłady z życia – optymalizacja jako chleb powszedni

Spróbujmy wrócić do przykładów z poprzedniego rozdziału:

1. Portfel inwestycyjny – minimalizujemy ryzyko inwestycji (wariancję zysków), ale przy założeniu, że średni zysk musi wynosić co najmniej 10%. Zmiennymi decyzyjnymi są udziały różnych aktywów. Ograniczenia? Łączna suma udziałów = 100%, żaden nie może być ujemny, zysk powyżej 10%.

2. Rozmieszczenie pojemników z insektycydem na polu – minimalizujemy liczbę przeżywających os (czyli maksymalizujemy skuteczność środka). Zmiennymi są współrzędne pojemników, a ograniczenia wynikają z rozmiarów pola, działania środka, bezpiecznych odległości.

3. Sterowanie napędem – minimalizujemy czas reakcji albo przeregulowanie, dbając o to, żeby układ był stabilny. Ograniczenia: dopuszczalne zakresy parametrów regulatora, wymogi na odpowiedź skokową, granice fizyczne układu.

Wszystkie te zadania są przykładami problemów minimalizacji, które pojawiają się w prawdziwej inżynierii, ekonomii i logistyce. A skoro już wiemy, że są – czas dowiedzieć się, jak się za nie zabrać.