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

Now that we have defined the dual of a linear program, let us study the links between the solutions of programs that are dual to one another.

THEOREM 1.9.– Let (x, y) be a feasible solution of () and (u, v) a feasible solution of (). Then:

 1) z(x, y) ≤ w(u, v);

 2) z(x, y) = w(u, v) ⇒ (x, y) and (u, v) are optimal solutions of () and ( ).

THEOREM 1.10.– One of the following three cases is satisfied:

 1) () and () have optimal solutions and max z(x, y) = min w(u, v);

 2) one of () and () has a feasible solution, but not the other;

 3) neither () nor () have feasible solutions.

THEOREM 1.11.– Let (x, y) (respectively, (u, v)) be feasible solutions of () (respectively, ()). Then (x, y) and (u, v) are optimal solutions of () and () if and only if the following statements hold:

 – if one constraint is strictly an inequality in () (respectively, ()), then the corresponding variable of () (respectively, of ()) is zero;

 – if the value of a restricted variable (i.e. a positive variable or a negative variable) in one of the programs () or () is not zero, then the corresponding constraint in the other program is an equality.

This theorem can alternatively be stated as follows:

THEOREM 1.12.– Let x and p be admissible solutions of the primal and dual programs, respectively. Then the vectors x and p are, respectively, optimal solutions of the two problems if and only if: