Niezbędne definicje

Niech dany będzie problem programowania liniowego (w postaci standardowej)

$$\begin{array}{rcl} {\bf Ax} & \leq {\bf b} \\ {\bf x} & \geq \Theta_n \end{array}$$ (2.3)

${\bf cx} \rightarrow \mbox{max}$

${\bf x} = (x_1, ..., x_n)$ (lub: $x_j \ (j=1,...,n)$) nazywamy rozwiązaniem dopuszczalnym PPL () jeśli

${\bf x} \geq \Theta_n$ (inaczej: $x_j \geq 0,$ dla $j=1,...,n$), oraz

${\bf Ax} \leq {\bf b}$ (inaczej: $\sum^n_{j=1}a_{ij}x_j \leq b_i, i=1,...,m$).

Rozwiązaniem optymalnym PPL () (lub () - ()) nazywamy takie rozwiązanie dopuszczalne ${\bf x}$, dla którego funkcja $f({\bf x})={\bf cx}$ przyjmuje wartość maksymalną.
Oczywiście, może się zdarzyć, że PPL w ogóle nie ma rozwiązań dopuszczalnych, t.zn. zbiór

$$\{ {\bf x \in R^n}: {\bf x \geq \Theta_n} \mbox{ i } {\bf Ax}\leq {\bf b}\}$$ (2.4)

jest zbiorem pustym. Wtedy mówimy, że PPL () jest problemem sprzecznym (lub, że warunki: ${\bf x \geq \Theta_n} \mbox{ i } {\bf Ax}\leq {\bf b}$ są sprzeczne).
Jeśli zbiór () jest niepusty i funkcja $f$ w tym zbiorze nie ma maksimum, to mówimy że PPL jest nieograniczony. W rzeczy samej, zbiór () jest oczywiście domknięty w ${\bf R^n}$, a funkcja $f$ ciągła. Jeśli więc zbiór () jest niepusty i $f$ nie przyjmuje a tym zbiorze maksimum, to $f$ jest w zbiorze nieograniczona (sam zbiór także jest nieograniczony).

Przykład 2.2   Problem
$\begin{array}{rrl} x_1 & -x_2 & \leq 2\\ x_2 & -x_1 & \leq 3\\ & x_i \geq 0 & (i=1,2) \end{array}$

$x_1+ x_2 \rightarrow \mbox{max}$

jest oczywiście sprzeczny.

Przykład 2.3   Problem
$\begin{array}{rrl} x_1 & - x _2 & \leq 0\\ -3x_1 & +x_2 & \leq 0\\ & x_i & \geq 0 \ \ (i=1,2) \end{array}$

$x_1+ x_2 \rightarrow \mbox{max}$

jest nieograniczony.
Rzeczywiście, dla dowolnego $t \geq 0, \ \ x_1 = t, \ x_2 = 2t$ jest rozwiązaniem dopuszczalnym. Wartość funkcji $f(x_1,x_2)=x_1+x_2=3t$ może być wtedy dowolnie duża.