Podręcznik

Niepewność współczynników macierzy \(A\).   Załóżmy, że w zadaniu \(\{\min_x \mathbf{c}^T x, \mathbf{A}x \geq \mathbf{b}\}\), współczynniki macierzy \(A\) nie mogą być wyznaczone w sposób dokładny. Oznaczmy je jako \(\tilde{a}_i\), zatem problem ma postać:

\(\min\sum_i c_ix_i,\) p.o.:

\(\sum_i\tilde{a}_ix_i\geq b.\)

Jeśli można przyjąć, że wartości współczynników mieszczą się w pewnym zakresie \([L_i, U_i]\) to \([a_i-\delta_i,a_i+\delta_i]\), gdzie \(\delta_i=0.5(U_i-L_i)\) oraz \(a_i=0.5(U_i+L_i)\).
Aby rozwiązanie PL spełniało ograniczenia \(\tilde{a}_ix\geq b\) w każdym przypadku, wystarczy jeśli spełni ograniczenia w najgorszym przypadku:

• dla \(x_i\geq 0\) to ograniczenie będzie spełnione jeśli \(\tilde{a}_ix\geq (a_i-\delta_i)x_i\),
•  dla \(x_i\leq 0\) to ograniczenie będzie spełnione jeśli \(\tilde{a}_ix\geq (a_i+\delta_i)x_i\).

Czyli problem można sformułować jako:

\(\sum_i\tilde{a}_ix\geq a_ix_i-\sum_i\delta_i|x_i|\geq b\).

Wtedy stosując metodę przedstawienia wartości bezwzględnej jako f. wypukłej \( |x_i| = y_i \), używamy teraz nowych zmiennych \( y_i \) w początkowym ograniczeniu, dodając ograniczenia wiążące te zmienne z \(x_i \) dla funkcji celu:

\(\min\sum_i c_ix_i,\) p.o.:     

\begin{eqnarray} & &\sum_i a_ix_i- \sum_i\delta_i y_i \geq b, \\ &-y_i \leq & x_i\leq y_i,\\ & &y_i\geq 0. \end{eqnarray} Uwaga, często warto uwzględnić dodatkowo współczynnik tolerancji \(\epsilon\), pozwalający na nieznaczne naruszenie prawej strony ograniczeń: \begin{eqnarray} && \sum_i a_ix_i-\sum_i\delta_i y_i\geq b-\epsilon\max(1,|b|).\end{eqnarray}