Principles of Mathematics in Operations Research

Proof. Ax > b, x >

Either \A-I\ X

AT

-I

y > 0,yTb < 0.

114 8 Linear Programming

» -» Ax - Iz = b,z>9.

has a nonnegative solution or 3y 3

=> ATy > 9, yTb < 0, y < 9. D

Remark 8.5.4 The propositions in this section can also be shown using the
primal dual pair of linear programming problems: If the dual is unbounded,
the primal is infeasible.

1. Either Ax = b has a solution, or else there is a y 3 A^1 y = 9, y^1 b =/= 0;

(PI) : Max 6Tx (Dl) : Min bTy

s.t. s.t.

Ax = b ATy = 9

x : URE y : URE

(P2) : Min 9Tx (D2) : Max bTy

s.t. s.t.

Ax = b ATy = 9

x : URE y : URE

Either PI (or P2) is feasible, or Dl (or D2) is unbounded. For Dl (D2)

to be unbounded, we 'must have bTy < 0 (b^1 y > 0). Thus, either Ax = b

or By 3 ATy = 9, yTb ^ 0.

2. Either Ax = b,x > 9 has a solution, or else there is a y such that
   ATy>9,yTb<0:

(P3) : Max 9Tx (D3) : Mm bTy

s.t. s.t.

Ax = b ATy > 9

x>9 y. URE

Either PS is feasible, or D3 is unbounded. For D3 to be unbounded, we

must have bTy < 0. Thus, either Ax = b, x > 9 has a solution, or else

3y 3 Ary > 9, yTb < 0.

3. Either Ax > b, x > 9 has a solution, or else there is a y such that
   ATy> 9,yTb < 0, y < 9:

(P4) : Max 9rx (D4) : Min bTy

s.t. s.t.

Ax > b ATy > 9

x>9 y<9