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

After writing out the first simplex tableau and adding zj = −cj to the last row, there are three possible cases:

 1) zj − cj ≥ 0 for j = 1, . . . , n. The basic feasible solution x is already optimal. This optimal solution may or may not be unique;

 2) there exists j ∈ {1, . . . , n} such that zj −cj < 0 and aij ≤ 0 for every i ∈ J. In this case, the domain of realizable solutions is unbounded and the problem is ill-posed, since max z(x) = +∞;

 3) the usual case: there exists j ∈ {1, . . . , n} such that zj − cj < 0, and there exists i ∈ J such that aij > 0. The change in basis described earlier is now possible and should be performed, possibly several times, until case (1) is reached.

Could the simplex algorithm ever fail to terminate if case (3) leads to a loop? The answer is yes, and examples have been successfully constructed. However, they are very rare in practice.

Let us therefore state two important theorems about the simplex method.

THEOREM 1.3.– Let be a basic realizable solution of (P ) with respect to a basis J (|J| = m = rank(A)). Let for every j = 1, . . . , n, then x is an optimal basic realizable solution.

THEOREM 1.4.– Let be a basic realizable solution of (P ) with respect to a basis Suppose that aij ≤ 0 for every i ∈ J and for every j ∈ {1, . . . , n} such that zj − cj < 0. Then the set {z(x), x is a realizable solution} is unbounded.

REMARK.– For a comprehensive discussion of the efficiency of the simplex method, refer to [CHV 83].