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}