Читать книгу Optimizations and Programming - Bouchaib Radi, Ghias Kharmanda, Michel Ledoux - Страница 22

Let x be a basic feasible solution of (P). Then

Our goal is to find another feasible basis and a basic feasible solution such that z() > z(x) (meaning that is better than x). The simplex method proceeds by replacing one of the basic variables xr with a non-basic variable xk. We say that

 – the variable xr enters the basis J : xr → r = 0;

 – the variable xk leaves the basis : xk = 0 → k > 0.

Thus, = (J − {r}) ∪ {k}. We need rules to choose r and k. These rules are as follows:

 – Choose r such that[1.3]

 – Choose k such that[1.4]

EXAMPLE 1.4.– Returning to the previous example: J = {3, 4}, c₃ = c₄ = 0, and so zj = 0 for j = 1, 2, 3, 4. Thus, zj − cj = −cj, j = 1, 2, 3, 4. Hence, k = 1.

To choose r,

Thus, r = 2, x₄ leaves the basis, and x₁ enters the basis. The new basis is = {3, 1}. We have

Hence, = (2, 0, 6, 0)T and Passing from J = {3, 4} to = {3, 1} increases the value of z to 8, but this value is not yet maximal.