Question

Prove that if the linear program, max cTx subject to Ax = b x ≥0 does not have a feasible solution, then there exists a vector z such that bTz < 0 and ATz ≥0. Hint: If the linear program is not feasible, then the optimum solution of min 1Ty subject to Ax + y = b x, y ≥0 is bigger than zero. Write the dual program and use strong duality theorem. (1Tdenotes a row vector with all entries equal to 1.) Note that b is non-negative in the given LP.

Answer 1

By writing the dual of the auxiliary optimization problem and applying the strong duality theorem, we establish that for an infeasible linear program, there must exist a vector z such that bTz < 0 and ATz ≥0.

Step-by-step explanation:

The student is tasked with using strong duality theorem to prove the existence of a vector z when a linear programming problem is not feasible. Given a linear program max cTx subject to Ax = b, x ≥0, if it has no feasible solution, then the optimization problem min 1Ty subject to Ax + y = b, x, y ≥0 must have an optimum solution greater than zero. By the strong duality theorem, the dual of this problem has a corresponding objective function value, providing us with a vector z such that bTz < 0 and ATz ≥0.

First, we write the dual of the auxiliary problem min 1Ty:

• 
  
• 
  
• 
  

If the original problem is infeasible, then by the strong duality theorem, the dual's optimal value must be strictly greater than zero, hence

b

T

z

must be negative, and since

w ≥0

, it means

A

T

z ≥0

.