Linear Programming-Duality

Every linear programming problem whether of maximization or minimization has associated with it another mirror image problem based on the same data. The original problem is called the primal problem while the other is called its dual problem. However, in general either problem can be considered as primal and the remaining as the dual problem, i.e., both the problems can be derived from each other and there is a unique dual (primal) problem associated with the primal (dual) problem. The format of the simplex method is such that when primal is solved, its associated dual is also solved simultaneously. In other words if the optimum solution to one is known the optimum solution of the other is readily available.

            The above discussion implies that a given situation can be looked at from two different points of view and the same solution obtained in both the cases For example in problem of producing two products where each consume two particular resources, the primal problem could be to determine what amounts of each product will maximize the overall profit subject to the constraints on resource availability. The dual problem would then be to determine the cost per hour of the two resources being used so as obtain an overall minimum cost the constraints in this case would be the total implied profitability per item for each of the two products which must both exceed the actual unit profit which each item produces.

            Consider the general linear programming problem, which we will call as the primal problem.

Minimize Z = c₁x₁+c₂x₂+....+c_nx_n

Subject to       a11x1 + a1₂x₂ +..... a1_nx_n < b₁

                      A₂₁x₁ + a₂₂x₂ +..... + a2_nx_n < b₂

                       :

And              a_m1x1 + a_m2x₂.. +.......+ a_mnx_n< b_m

                     X₁ > 0, x₂ > 0,...... x_n > 0.

The dual of this problem is expressed as:

Minimize Z* = b₁y₁ + b₂y₂ +.....+ b_my_m

Subject to       a₁₁y₁ + a₂₁y₂ +.... + a_m1y_m >c₁

           A 12y1 + a22y2 +.... + a_m 2y_m > c₂

                :

           A1_ny1 + a2_ny2 +.... A_mny_m > c_n

           _Y1 > 0, _y2 > 0,....... Y_m > 0

Where y₁, y₂...., y_m are the dual decision variables.

The credit for displaying, in tabular form, the relationship of the primal and its dual goes to A.W. tucker and is summarised in the following table.

The relationship between the primal and the dual the dual is obtained by reading across by rows for primal and for the dual by reading down by columns.

Linear Programming Duality Tutoring - Assignment Help

Our online expert tutor's team at www.expertsmind.com is passionate & professional experienced people who are providing their precious time by online duality linear programming assignment help, techniques of operation research homework help services which give the best quality answers of subject questions on time given by students. Instant operation research tutors can help you in solving your toughest and complex operation research questions and they can make easy learning subject. We at Expertsmind.com offers instant tutoring sessions in operation research.

ExpertsMind.com - Duality Assignment Help, Duality Homework Help, Duality Assignment Tutors, Duality Solutions, Duality Answers, Linear Programming Assignment Tutors