Podręcznik

2. Modelowanie zależności

2.2. Techniki dla prostych zależności nieliniowych

W wielu przypadkach pierwotny problem optymalizacji nie ma standardowej liniowej postaci, ale można go bezpośrednio przekształcić w równoważny problem liniowy. Są to problemy typu:

minmax, czyli minimalizacja największej wartości,
wartość bezwględna, występująca często, gdy koszty są ponoszone, gdy wynik w jakiś sposób powoduje powstanie odchyłki od wartości bazowej, np. wynoszącej zero.

Problem minmax to zadanie optymalizacji z funkcją celu minimalizującą największą z możliwych do osiągnięcia wartości, tj. problem postaci:

$\min \max_i x_i,$

p.o.:

$Ax \geq b, \; x \geq 0.$

Na przykład, w zadaniu harmonogramowania operacji kryterium może być minimalizacja czasu ukończenia całego przedsięwzięcia. Optymalny plan może się różnić od uzyskanego w przypadku przyjęcia innego kryterium, np. dla kryterium minimalizacji średniego czasu ukończenia zadań. Inne typowa sytuacja, w której stosuje się funkcję celu minmax, to dążenie do osiągnięcia jak najbardziej sprawiedliwego rozwiązania, czyli takiego, w którym indywidualne miary zadowolenia są możliwie równe - nie ma między nimi dużych skrajności.

Problem minmax sprowadzamy do postaci PL poprzez:

wprowadzenie dodatkowej zmiennej $y$ reprezentującej minimalizowaną wartość, czyli:
$\min \max_i x_i = \min y$
ograniczenie tej zmiennej od dołu:
$y\geq x_i, \forall i.$

Zauważmy, że w powyższym sposobie korzystamy z tego, że zmienna

$y$ jest minimalizowana, a więc w optimum będzie de facto równa największej z wartości

$x_i$ - mniejsza nie może być, jeśli ma być spełnione ograniczenie, a „nie opłaca się” aby była większa.

Pokazany sposób przeformułowania można zastosować do każdego problemu, który ma funkcję celu typu minmax. Działa on również w przypadku analogicznego celu maxmin, z maksymalizacją zamiast minimalizacji i przy ograniczeniach

$y\leq x_i, \forall i.$

Drugi rodzaj nieliniowej funkcji, którą można przedstawić w postaci zależności liniowych, to funkcja wartości bezwzględnej. Jak zostało wspomniane wcześniej, można się posłużyć takim samym sposobem, jak przy transformowaniu problemu z postaci kanonicznej do standardowej, czyli zastąpieniem zmiennej - czy w tym przypadku, funkcji, różnicą między nieujemnymi składnikami.

Wartość bezwzględną zmiennej

$|x|$ możemy przedstawić w sposób jawny jako sumę nieujemnych odchyłek na plus

$x^+$ i na minus

$x^-$ , czyli:

$\left|x\right| =x^+ + x^-,\;$

gdzie

$x =x^+ - x^-,\;$ oraz

$x^+ \geq 0,\; x^-\geq 0.$

Aby tylko jedna ze zmiennych

$x^+, x^-$ była niezerowa (i de facto równa

$|x|$ ) wystarczy, aby z wystąpieniem odchyłki wiązały się koszty, minimalizowane w funkcji celu.

Problem regresji liniowej. Rozważmy problem wyznaczenia współczynników

$a_j, b$ regresji liniowej, gdy dysponujemy

$m$ obserwacjami zmiennej

$y$ zależnej od

$n$ -wymiarowej zmiennej

$x$ . Szukamy funkcji zależności:

$y^k = \sum_{j=1}^n a_j x_j^k +b +\epsilon_k, \; \forall k = 1..m,$

gdzie

$\epsilon_k$ jest miarą braku dopasowania krzywej regresji od

$k$ -tej obserwacji. Wśród różnych metryk dopasowania krzywej regresji do danych szczególne znaczenie mają:

MAE - Mean Absolute Error (średni bezwględny błąd dopasowania), czyli: $\min\frac{1}{m} \sum_k|\epsilon_k|$
MAXAE - Maximum Absolute Error, czyli: $\min\,\max_k|\epsilon_k|$
RMSE, MSLE jako miary nieliniowe nie mogą być wyznaczane w zadaniach PL.

Zadanie PL wyznaczenia MAE. Stosując wyjaśniony wcześniej sposób otrzymujemy następujące sformułowanie problemu.

\begin{eqnarray} &&\min \frac{1}{m}\sum_k (\epsilon^+_k +\epsilon^-_k)\\ \epsilon^+_k -\epsilon^-_k&\geq&y^k-\sum_{j=1}^n a_jx^k_j-b,\;\;\;\forall k=1,\ldots, m,\\ &&\epsilon^+_k,\epsilon^-_k\geq 0. \end{eqnarray}

Zadanie PL wyznaczenia MAXAE. Dalej, łącząc oba poznane w tym rozdziale sposoby, otrzymujemy następujące sformułowanie problemu, w któym zmienna

$\Delta$ reprezentuje wartość maksymalnego błędu dopasowania.

\begin{eqnarray} &&\min \Delta\\ \epsilon^+_k -\epsilon^-_k&\geq&y^k-\sum_{j=1}^n a_jx^k_j-b,\;\;\;\forall k=1,\ldots, m,\\ \Delta &\geq &\epsilon^+_k +\epsilon^-_k,\;\;\;\forall k=1,\ldots, m,\\ &&\epsilon^+_k,\epsilon^-_k\geq 0. \end{eqnarray}

Zapisz w postaci PL problem minimalizacji czasu trwania całego przedsięwzięcia, składającego się z czterech niezależnych operacji A, B, C i D, gdzie każda

$i$ -ta operacja trwa

$p_i$ dni. Jedynym warunkiem jest ukończenie operacji A oraz B, zanim rozpocznie się wykonywanie operacji D.