A Short Course in Linear Programming

First, look at Theorems of the alternative in my glossary (pay special attention to those of Fourier, Farkas and Motzkin).

Second, read The Fundamental Theorems of Linear Programming, and see if you can prove them.

Third, look up the following terms in my glossary:

• Consistent
• Forced equality
• Forcing substructure
• Infeasible
• Irreducible inconsistent subsystem
• Redundant constraint
• Support set

 

 

 

 

 

1. x and y must satisfy complementary slackness: .

Solution.
2. If both S and  are consistent, there must exist a strictly complementary solution:  such that .

Solution.
3. If  and  are two strictly complementary solutions to S and , their partitions are the same: .

Solution.
4. S is inconsistent if, and only if,  is consistent. Further, let Y = {y: y satisfies S^d and yb > 0}, and suppose . Then,  is an IIS if, and only if, there does not exist  such that . (In the latter, such a y is called an elementary vector of Y.)

Solution.
5. Suppose S is consistent. Then,  is redundant in S if, and only if,  is consistent. This is strongly redundant if, in addition, yb > 0.

Solution.
6. Suppose S is consistent. Then,  is an implied equality of S if, and only if,  is consistent.

Solution.