Kenneth Kuttler

11.5. DUALITY 241

Lemma 11.5.1 Let x be a solution of the inequalities of A.) and let y be a solution of theinequalities of B.). Then

cx≥ yb.

and if equality holds in the above, then x is the solution to A.) and y is a solution to B.).

Proof: This follows immediately. Since c≥ yA,

cx≥ yAx≥ yb.

It follows from this lemma that if y satisfies the inequalities of B.) and x satisfies theinequalities of A.) then if equality holds in the above lemma, it must be that x is a solutionof A.) and y is a solution of B.). ■

Now recall that to solve either of these problems using the simplex method, you firstadd in slack variables. Denote by x′ and y′ the enlarged list of variables. Thus x′ has atleast m entries and so does y′ and the inequalities involving A were replaced by equalitieswhose augmented matrices were of the form(

A −I b), and

(AT I cT

)Then you included the row and column for z and w to obtain(

A −I 0 b−c 0 1 0

)and

(AT I 0 cT

−bT 0 1 0

). (11.21)

Then the problems have basic feasible solutions if it is possible to permute the first p+mcolumns in the above two matrices and obtain matrices of the form(

B F 0 b−cB −cF 1 0

)and

(B1 F1 0 cT

−bTB1−bT

F11 0

)(11.22)

where B,B1 are invertible m×m and p× p matrices and denoting the variables associatedwith these columns by xB,yB and those variables associated with F or F1 by xF and yF , itfollows that letting BxB = b and xF = 0, the resulting vector x′ is a solution to x′ ≥ 0 and(

A −I)

x′ = b with similar constraints holding for y′. In other words, it is possible toobtain simplex tableaus,(

I B−1F 0 B−1b0 cBB−1F− cF 1 cBB−1b

(I B−1

1 F1 0 B−11 cT

0 bTB1

B−11 F−bT

F11 bT

B1B−1

1 cT

)(11.23)

Similar considerations apply to the second problem. Thus as just described, a basic fea-sible solution is one which determines a simplex tableau like the above in which you geta feasible solution by setting all but the first m variables equal to zero. The simplex al-gorithm takes you from one basic feasible solution to another till eventually, if there is nodegeneracy, you obtain a basic feasible solution which yields the solution of the problemof interest.

Theorem 11.5.2 Suppose there exists a solution, x to A.) where x is a basic feasible solu-tion of the inequalities of A.). Then there exists a solution, y to B.) and cx = by. It is alsopossible to find y from x using a simple formula.

11.5. DUALITY 241Lemma 11.5.1 Let x be a solution of the inequalities of A.) and let y be a solution of theinequalities of B.). Thencx > yb.and if equality holds in the above, then x is the solution to A.) and y is a solution to B.).Proof: This follows immediately. Since c > yA,cx > yAx > yb.It follows from this lemma that if y satisfies the inequalities of B.) and x satisfies theinequalities of A.) then if equality holds in the above lemma, it must be that x is a solutionof A.) and y is a solution of B.).Now recall that to solve either of these problems using the simplex method, you firstadd in slack variables. Denote by x’ and y’ the enlarged list of variables. Thus x’ has atleast m entries and so does y’ and the inequalities involving A were replaced by equalitieswhose augmented matrices were of the formA —-I b ),and( A? 7 cf( ) and ( )Then you included the row and column for z and w to obtainA -I 0 Db A’ I 0 efand r . (11.21)-c 0 1 0 —b’ 0 1 0Then the problems have basic feasible solutions if it is possible to permute the first p +mcolumns in the above two matrices and obtain matrices of the formB F 0b B FL 0 ctand ae . (11.22)—cg -—cr 1 0 —bz, —b;, 1 0where B, By are invertible m x m and p x p matrices and denoting the variables associatedwith these columns by xg, yz and those variables associated with F or F, by xp and yr, itfollows that letting Bxg = b and xy = 0, the resulting vector x’ is a solution to x’ > 0 andA -I ) x’ = b with similar constraints holding for y’. In other words, it is possible toobtain simplex tableaus,I B'F 0 B'b I By'F 0 Ble" (11.23)0 cgB'F—cr 1 cgB'b }]’\ 0 bs. By'F—bz 1 bpBy'e"Similar considerations apply to the second problem. Thus as just described, a basic fea-sible solution is one which determines a simplex tableau like the above in which you geta feasible solution by setting all but the first m variables equal to zero. The simplex al-gorithm takes you from one basic feasible solution to another till eventually, if there is nodegeneracy, you obtain a basic feasible solution which yields the solution of the problemof interest.Theorem 11.5.2 Suppose there exists a solution, x to A.) where x is a basic feasible solu-tion of the inequalities of A.). Then there exists a solution, y to B.) and ex = by. It is alsopossible to find y from x using a simple formula.