Consider the following Linear Programming Problem Minimize Z

Consider the following Linear Programming Problem Minimize Z = 2x_1 + 3x_2 + 5x_3 + 6x_4 x_1 + 2x_2 + 3x_3 + x_4 greaterthanorequalto 2 - 2x_1 + x_2 - x_3 + 3x_4 lessthanorequalto -3 x_1, x_2, x_3, x_4 greaterthanorequalto 0. Given that the optimal solution of this LPP\'s dual is (y_1*, y_2*) = (8/5, 1/5) and Z* = (19/5); how the information about the dual linear program and the duality theorem can be utilized to solve the primal problem?

Solution

Answer:- In the primal problem,from each sub-optimal point that sastisfies in all constraints, there is a direction or subspace of directions to move that increase the objective function.

In dual problem, the dual vector multiplies the constraints that determine the positions of the constraints in the primal.

Varying the dual vector in the dual problem is equivalent to revising the upper bounds in the primal problem.

Since, the dual of the dual is primal, we know that dual of minimization problem will be maximization problem.

If the primal ideal problem is maximization problem, the dual variables associated with less than or equal to constraints are non negative, where as the dual associated with the greater than or equal to constraints are non positive,and the dual variables asociated with the equality constraints are unrestricted in sign.

These convection reflect the interpretation of the dual variables as a shadow pieces of primal problem.

Equality constraints in the primal corresponds to unrestricted variable in the dual, while inequality constraints in the primal corresponds to restricted variable in the dual, where the sign of the restriction in the dual depends upon the combination of objective function type and constraint relation in primal.