Ile jest rozwiązań optymalnych?

Problemowi ilości rozwiązań optymalnych nie będziemy poświęcali wiele miejsca i czasu. Niemniej często można stosunkowo łatwo stwierdzić, że rozwiązanie jest jedyne. Najlepiej wyjaśni to poniższy przykład.

Przykład 3.6   Niech będzie dany problem PL

$$\begin{array}{rrrrrr} & x_1 & - x_2 & +2x_3 & \leq & 1 \\... ...1 & - x_2 & + x_3 & \rightarrow & \mbox{max} \\ \end{array}$$ (3.32)

Kolejnymi słownikami dla tego problemu będą:

$$\begin{array}{rrrrrrrr} x_4 & = & 1 &- x_1 & + x_2 & - 2x... ...1 & - x_2 & + x_3 & \rightarrow & \mbox{max} \\ \end{array}$$ (3.33)

$$\begin{array}{rrrrrrrr} x_1& = & 1 & + x_2 & - 2x_3 & - x... ...& & - x_3 & - x_4 & \rightarrow & \mbox{max} \\ \end{array}$$ (3.34)

Zauważmy, że wartość maksymalna $z=1$ jest przyjęta dla więcej niż jednego wektora ${\bf x}$. Rzeczywiście, we wzorze na $z$ słownika (), a więc ostatniego słownika w metodzie simpleks dla naszego problemu, nie występuje zmienna bazowa $x_2$. Jeżeli we wzorze na $z$ w ostatnim słowniku występują wszystkie zmienne niebazowe, to rozwiązanie jest jedyne: zmienne niebazowe muszą w rozwiązaniu maksymalizującym $z$ być równe zeru, zaś zmienne bazowe wyznaczone są jednoznacznie przez odpowiednie równania słownika. W naszym przykładzie, aby $z$ było równe $1$ musi zachodzić $x_3=0$ oraz $x_4=0$, natomiast $x_2$ niekoniecznie jest równe zero. Na przykład dla $x_3=x_4=0$, $x_2=t \in <0,1>, \ x_1=1+t, \ x_5=3-3t, \ x_6=1$ wartość $z$ jest także równa wartości maksymalnej $1$. Dla problemu () oznacza to, jak łatwo stwierdzić, że zbiorem wszystkich rozwiązań jest zbiór punktów odcinka $\{ (x_1,x_2,x_3): x_1=1+t, x_2=t, x_3 = 0, t\in <0,1> \}$.