n=3

Studiowanie tego przypadku połączymy z badaniem przykładu Klee-Minty'ego dla $n=3$.

Przykład 7.2   Dla $n=3$ przykład Klee-Minty'ego wygląda następująco:

$$% latex2html id marker 8631 \begin{array}{llllcr} \mbox{z... ..._2+x_3 & \leq & 125\\ &&& x_1,x_2,x_3 & \geq & 0 \end{array}$$

Czytelnik który wykonał ćwiczenie otrzymał osiem słowników i tyleż rozwiązań bazowych:

$${\bf x^1}= \left[ \begin{array}{r} 0\\ 0\\ 0\\ 5\\ 25 \\ 125... ...begin{array}{r} 0\\ 25\\ 0\\ 0\\ 0 \\ 125 \end{array} \right]$$

$${\bf x^5}= \left[ \begin{array}{r} 0\\ 25\\ 25\\ 5\\ 0 \\ ... ...gin{array}{r} 0\\ 0\\ 125\\ 5\\ 25 \\ 0 \end{array} \right]$$

(trzy współrzędne tych rozwiązań odpowiadają zmiennym decyzyjnym $x_1,x_2,x_3$ podczas gdy trzy następne zmiennym sztucznym $y_1, y_2, y_3$).

Przyjrzyjmy się tej sytuacji na rysunku (rys. 6.2) na którym oczywiście uwzględniamy jedynie współrzędne x-owe rozwiązań zaś $y_1, y_2, y_3$ ignorujemy (z oczywistych powodów rysunek jest przeskalowany - skala na każdej z osi jest inna).
Zbiorem rozwiązań dopuszczalnych jest wielościan wypukły o wierzchołkach $\bar{x}^1,...,\bar{x}^8$. Ściany wielościanu odpowiadają równościom w ograniczeniach. Od dołu nasz wielobok jest ograniczony przez płaszczyznę $x_3=0$, od góry przez płaszczyznę $8x_1+4x_2+x_3=125$. Krawędzie wyznaczone są przez przecięcia płaszczyzn. Na przykład krawędź łacząca wierzchołki $(5,5,65)$ i $(0,25,25)$ zawarta jest w prostej

$$\left\{ \begin{array}{lcr} 8x_1+4x_2+x_3 & = & 125\\ 4x_1 + x+2 & = & 25 \end{array} \right.$$

Wierzchołki to oczywiście przecięcia trzech płaszczyzn - a więc nasze rozwiązania bazowe! Teraz jasnym sie staje, jak bardzo jak bardzo pechowy dla algorytmu sympleks jest przykład Klee-Minty'ego. Sympleks wybiera wierzchołki wielościanu, przechodząc kolejno od wierzchołka do wierzchołka sąsiedniego po kzawędzi, za każdym razem zwiększając (a raczej nie zmniejszając) wartość funkcji celu. W przykładzie Klee-Minty'ego zaczyna od najgorszego rozwiązania a następnie najgorszy możliwie wierzchołek sąsiedni. W ten sposób sympleks musi sprawdzić wszystkich osiem dla $n=3$, a $2^n$ w ogólnym przypadku, wierzchołków (inaczej: rozwiązań bazowych) - a więc wszystkie możliwe.