Duality in Operation Research in linear programming PDF

Preview

Summary

simplex method and duality method in linear programming...

Description

Q.1 What is the optimal solution to the dual problem? In mathematical optimization theory, duality or the duality principle is the principle that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem. The solution to the dual problem provides a lower bound to the solution of the primal (minimization) problem. Q.2 What is dual of a LPP explain with example? Definition: The Duality in Linear Programming states that every linear programming problem has another linear programming problem related to it and thus can be derived from it. ... Such that in the primal problem, the inequality sign was “≤” but in the dual problem, the sign of inequality becomes “≥”.

Q.3

Duality in Linear Programming

Definition: The Duality in Linear Programming states that every linear programming problem has another linear programming problem related to it and thus can be derived from it. The original linear programming problem is called “Primal,” while the derived linear problem is called “Dual.” Before solving for the duality, the original linear programming problem is to be formulated in its standard form. Standard form means, all the variables in the problem should be non-negative and “≥,” ”≤” sign is used in the minimization case and the maximization case respectively. Q.4 What is the theorem of duality? ANSWER (a) The duality theorem states that: if the primal problem has an optimal solution, then so has the dual, and zP = zD; 1 Page 2 • if the primal problem is unbounded, then the dual is infeasible; if the primal problem is infeasible, then the dual is either infeasible or unbounded.

Example Maximize Z = 50x1+30x2 Subject to: 4x1 + 3x2 ≤ 100 3x1 + 5x2 ≤ 150 X1, x2 ≥ 0 The duality can be applied to the above original linear programming problem as: Minimize G = 100y1+150y2

Subject to: 4y1 + 3y1 ≥ 50 3y1 +5y2 ≥ 30 Y1, y2 ≥ 0 The following observations were made while forming the dual linear programming problem:

1.

The primal or original linear programming problem is of the maximization type while the dual problem is of minimization type.

2.

The constraint values 100 and 150 of the primal problem have become the coefficient of dual variables y1 and y2 in the objective function of a dual problem and while the coefficient of the variables in the objective function of a primal problem has become the constraint value in the dual problem.

3.

The first column in the constraint inequality of primal problem has become the first row in a dual problem and similarly the second column of constraint has become the second row in the dual problem.

4.

The directions of inequalities have also changed, i.e. in the dual problem, the sign is the reverse of a primal problem. Such that in the primal problem, the inequality sign was “≤” but in the dual problem, the sign of inequality becomes “≥”. Note: The dual of a dual problem is the primal problem.

Some Uses of Duality in Linear Programming The Use of the Duality Principle to Solve Optimization Problems The first time one sees duality in linear programming the first reaction is to ques- tion its relevance. Duality in linear programming seems to be analogous to eigenval- ues and eigenvectors in linear algebra because at first glance the concept does not show immediately its relevance but as one learns further one realizes how fundamen- tal it is to the entire subject . The description of the uses of duality in linear programming includes but not limited to the following. 1. Any feasible solution to the dual problem gives a bound on the optimal objective function value in the primal problem. 2. Understanding the dual problem leads to specialized algorithms for some important classes of linear programming problems. 3. It is easier in some cases to find an initial feasible solution to the dual than finding one for the primal. 4. The dual variables give the shadow prices for the primal constraints. For instance,If there exist a profit maximization problem with a resource constraint i, then the value

yi of the corresponding dual variable in the optimal solution indicates an in- crease of yi in the maximum profit for each unit increase in the amount of resource i . 5. Sometimes the dual is easier to solve. A primal problem with many constraints and few variables can be converted into a dual problem with few constraints and many variables. Fewer constraints are nice in linear programs because the basis matrix is an n by n matrix, where n is the number of constraints. Thus the fewer the constraints, the smaller the size of the basis matrix, and thus the fewer compu- tations required in each iteration of the simplex method. 6. The dual can be used to detect primal infeasibility. This is a consequence of weak duality. 7. Duality in linear programming has certain far reaching consequence of economi nature. This fact may assist managers to arrive at alternative courses of action and their relative values.  Calculation of the dual checks the accuracy of the primal solution....