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

Earlier, when we solved linear programs graphically, the optimal solutions were on the boundary of the convex set of realizable solutions. If there was a unique optimal solution, it was an extreme point.

Recall the canonical form of a linear program:

where the matrix A is assumed to be an m × n matrix of rank m (< n). The standard form is then given by

It is possible to show the following result.

Let Γ (respectively, Σ) be the set of feasible solutions of (P) (respectively of (Ps)):

Then Γ and Σ are closed and convex sets.

Recall that the simplex method only uses the basic solutions of (Ps). The next theorem tells us that these are in fact the extreme points of Σ.

THEOREM 1.5.– is a basic feasible solution of (Ps) if and only if is an extreme point of Σ.

Examples where the solution is not unique show that the optimal solutions lie on the boundary:

THEOREM 1.6.– Every optimal solution of (P) (respectively of (Ps)) belongs to the boundary of Γ (respectively of Σ).

A question presents itself: can there be optimal solutions but no optimal basic feasible solutions? If so, the simplex method, which only considers basic solutions, would not be able to find an optimal solution. The following theorem tells us that this does not happen.

THEOREM 1.7.– If (Ps) has an optimal solution, then (Ps) has an optimal basic feasible solution.