Prove that in the duality theorem If the objective function

Prove that in the duality theorem,

If the objective function z of the max problem is not bounded above, the min problem has no feasible solutions. Similarly, if the objective function v of the min problemis not bounded below, the max problem has no feasible solutions.

Solution

. Duality. To every linear program there is a dual linear program with which it is intimately connected. We first state this duality for the standard programs. c and x are n-vectors, b and y are m-vectors, and A is an m × n matrix. We assume m 1 and n 1. The dual of the standard maximum problem maximize transpose of c into x subject to the constraints Az b and z 0 (1) is defined to be the standard minimum problem minimize yTb subject to the constraints transpose of y into A cT and v 0.

we have If z is feasible for the standard maximum problem and if v is feasible for its dual (2), then transpose of c into z transpose of v into b. Proof. transpose of c into z Transpose of c into Az Transpose of y into b. The first inequality follows from z 0 and Transpose of c Transpose of v into A. The second inequality follows from z>=0 and Az<=b.

The Duality Theorem. If a standard linear programming problem is bounded feasible, then so is its dual, their values are equal, and there exists optimal vectors for both problems.

f.b

As an example of the use of Corollary 2, consider the following maximum problem. Find x1 , x2 , x2 , x4 to maximize 2x1 + 4x2 + x3 + x4 , subject to the constraints xj 0 for all j , and x1 + 3x2 + x4 4 2x1 + x2 3 x2 + 4x3 + x4 3. (9) The dual problem is found to be: find y1 , y2 , y3 to minimize 4y1 + 3y2 + 3y3 subject to the constraints yi 0 for all i, and y1 + 2y2 2 3y1 + y2 + y3 4 4y3 1 y1 + y3 1.