Szczegóły metody

Do tej pory zapoznając się z metodą simpleks skrupulatnie omijaliśmy wszelkie rafy na które można natrafić. W szczególności przykłady były dobrane tak, by

- po pierwsze:

wiadomo było od czego trzeba zacząć $x_j = 0$ dla $j=1,...,n$ było rozwiązaniem dopuszczalnym,

- po drugie:

raz rozpoczęty algorytm działał bez zacięć, to znaczy: na żadnym etapie jego funkcjonowania nie mieliśmy wątpliwości co będzie trzeba zrobić w następnym kroku i następny krok był zawsze wykonalny,

- po trzecie:

po trzech (co najwyżej!) zmianach zmiennych bazowych otrzymywaliśmy optymalne rozwiązanie.

Czy tak musi być zawsze? Okazuje się, że nie. Rozważmy przykład następujący.

Przykład 3.3  

$$\begin{array}{rrrrrrl} x_1 & - & 2x_2 & + & 3x_3 & \leq &... ...ow & \mbox{max}\\ &&& x_i & \geq & 0 & i=1,2,3 \end{array}$$ (3.17)

Tym razem $x_1 = x_2 =x_3 =0$ nie jest rozwiązaniem dopuszczalnym problemu, nie spełnia drugiej ani trzeciej nierówności w PPL (). Co więcej, wcale nie jest oczywistym, że takie rozwiązanie w ogóle istnieje.