Od czego zacząć?

W ogólnym przypadku problemu PL w postaci standardowej:

$$\begin{array}{rllr} \sum^{n}_{j=1}a_{ij}x_j & \leq & b_i ... ...m^{n}_{j=1}c_{j}x_j & \rightarrow & \mbox{max} \end{array}$$ (3.18)

rozwiązanie bazowe $x_1=x_2=...=x_n=0$ jest dopuszczalne, wtedy i tylko wtedy, gdy $b_i \geq 0$ dla każdego $i=1,...,m$.
Co zrobić jeśli jest inaczej?
Do rozwiązania tego problemu zaprzęgniemy samą metodę simplex. Rozważmy mianowicie następujący PPL:

$$\begin{array}{rllr} \sum^{n}_{j=1}a_{ij}x_j - x_0 & \leq ... ....,n\\ \hline x_0 & \rightarrow & \mbox{min} \end{array}$$ (3.19)

Dla dowolnie ustalonych $x_1,...,x_n$ istnieje takie $x_0$, że nierówności

$$\sum^{n}_{j=1}a_{ij}x_j - x_0 \ \leq \ b_i \ \mbox{ dla } \ i=1,...,m$$

są spełnione bowiem $x_0$ można wziąć dowolnie duże. Tak więc problem () jest niesprzeczny. Jest oczywistym także, że problem wyjściowy () jest niesprzeczny, wtedy i tylko wtedy, jeśli rozwiązaniem PPL () jest $x_0=0$. Pierwszą zmienną wchodzącą będzie $x_0$, natomiast zmienną wychodzącą $x_{i_{0}}$ taka, że $b_{i_0}$ jest najmniejszą ze stałych $b_i$, $i=1,...,m$.
Zobaczymy jak funkcjonuje ta metoda na naszym przykładzie.

Przykład 3.3 (c.d.)   Zgodnie z naszym zwyczajem, będziemy maksymalizować, a nie minimalizować, pewną funkcję celu. Problem

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

przyjmie po wprowadzeniu zmiennych bazowych $x_4, x_5, x_6$ postać

$$\begin{array}{rrrrrrl} x_4 & = \ 5 & + x_0 & - x_1 & + 2x... ...ine & w & = - x_0 & \rightarrow & \mbox{max}\\ \end{array}$$ (3.21)

() nie jest słownikiem dopuszczalnym, bowiem rozwiązaniem bazowym jest $x_0=x_1=x_2=x_3=0, x_4=5, x_5=-6, x_6=-3$, więc $x_5$ i $x_6$ przyjmują wartości ujemne. Ten defekt zniknie po wprowadzeniu $x_0$ jako zmiennej bazowej w miejsce $x_5$, inaczej mówiąc przyjmujemy $x_0$ jako zmienną wchodzącą, $x_5$ jako zmienną wychodzącą. Nowym słownikiem będzie

$$\begin{array}{rlrrrllr} x_0 & = 6 & - x_1 & + 4x_2 & - x_... ...ne w & = -6 & + x_1 & - 4x_2 & + x_3 & - x_5 \end{array}$$ (3.22)

Teraz już () jest słownikiem dopuszczalnym (rozwiązanie bazowe jest rozwiązaniem dopuszczalnym: $x_0=6, \ x_1 = x_2 = x_3 = x_5 = 0, \ x_4 = 11, x_6 = 3, w = -6$).
Zauważmy, że także w ogólnym przypadku, zawsze będzie możliwy taki wybór zmiennej bazowej wychodzącej, żeby pierwsza iteracja dała słownik dopuszczalny. Wystarczy w tym celu tak wybrać $x_{n+i_{0}}$ żeby $b_{i_{0}}$ było najmniejsze spośród $b_i$, $i=1,...,m$. Nową zmienną bazową wchodzącą może być $x_1$ lub $x_3$ (we wzorze na $w$ w słowniku () współczynniki przy tych zmiennych są dodatnie i równe $1$, przy pozostałych zmiennych współczynniki są ujemne). Mamy teraz: $x_0 \geq 0 \Rightarrow x_1 \leq 6,$ $\ x_4 \geq 0 x_1\leq \frac{11}{2},$ $\ x_6 \geq 0 \Rightarrow x_1 \leq \frac{3}{4}$. Wobec tego, zmienną wychodzącą jest $x_6$. Wyliczamy więc $x_1$ z trzeciego z równań () i obliczamy nowe wzory na $x_0, x_4$ oraz $w$. Po elementarnych rachunkach otrzymamy nowy słownik

$$\begin{array}{rlrrrllr} x_0 & = 5\frac{1}{4} & + 2\frac{1... ...}x_3 & - \frac{3}{4}x_5 & - \frac{1}{4}x_6 \\ \end{array}$$ (3.23)

Zmienną wchodzącą jest teraz $x_3$ a wychodzącą $x_1$. Wyliczamy więc $x_3$ z drugiego ze wzorów słownika (), a następnie wstawiamy do pozostałych eliminując w ten sposób $x_3$. Nowym słownikiem jest następujący układ równań:

$$\begin{array}{rrrrrllr} x_0 & = 4\frac{1}{2} & + x_1 & + ... ..._1 & - x_2 & - \frac{1}{2}x_5 & - \frac{1}{2}x_6 \end{array}$$ (3.24)

Wartością maksymalną jaką może przyjąć $w$ w problemie () jest $w=-\frac{9}{2}$, a więc liczba ujemna, nie zero. Oznacza to, że problem () jest sprzeczny. $\Box$