{"id":698,"date":"2022-01-07T06:01:17","date_gmt":"2022-01-07T06:01:17","guid":{"rendered":"https:\/\/www.jagannath.org\/blog\/?p=698"},"modified":"2022-01-07T06:09:13","modified_gmt":"2022-01-07T06:09:13","slug":"duality-in-linear-programming-problem","status":"publish","type":"post","link":"https:\/\/www.jagannath.org\/blog\/duality-in-linear-programming-problem\/","title":{"rendered":"DUALITY IN LINEAR PROGRAMMING PROBLEM"},"content":{"rendered":"\n
\"\"<\/figure><\/div>\n\n\n\n

Ms Pooja Bisht<\/a><\/p>\n\n\n\n

Assistant Professor<\/a><\/p>\n\n\n\n

Jagannath International Management School<\/a><\/p>\n\n\n\n

From the practical and the theoretical point of view, the concept of duality is one of the most imperative topics of linear programming<\/a>. The trivial idea behind the duality theory is that every linear program has an associated linear program called its dual such that a solution to one gives a solution to the other. There are a number of important relationships between the solution to the original problem (primal) and it\u2019s dual. These are useful in investigating the general properties of the optimal solution to a linear program and in testing whether a feasible solution is optimal.<\/p>\n\n\n\n

The significance of duality<\/a> is twofold. Firstly, complete understanding of the shadow-value translation of the ideal simplex multipliers can beextremely helpful in understanding the ramifications of a specific direct programming problem. Second, it isn’t unexpected imaginable to address the connected direct program with the shadow costs as the factors instead of, or related to, the first direct program, accordingly exploiting of some computational efficiencies.<\/p>\n\n\n\n

Formation of the dual problem:<\/p>\n\n\n\n

Consider the Linear Programing Problem which is maximized in nature,<\/p>\n\n\n\n

(PRIMAL)<\/p>\n\n\n\n

Max Zy<\/sub> = d1<\/sub>y1<\/sub> +d2<\/sub>y2<\/sub> +\u2026\u2026..+dn<\/sub>yn<\/sub><\/p>\n\n\n\n

s.t.<\/p>\n\n\n\n

a11<\/sub>y1<\/sub> +a12<\/sub>y2<\/sub> +\u2026\u2026..+a1n<\/sub>yn<\/sub> b1<\/sub><\/p>\n\n\n\n

a21<\/sub>y1<\/sub> +a22<\/sub>y2<\/sub> +\u2026\u2026..+a2n<\/sub>yn<\/sub> b2<\/sub><\/p>\n\n\n\n

.<\/p>\n\n\n\n

.<\/p>\n\n\n\n

am1<\/sub>y1<\/sub> +am2<\/sub>y2<\/sub> +\u2026\u2026..+amn<\/sub>yn<\/sub>bm<\/sub><\/p>\n\n\n\n

and y1<\/sub>, y2<\/sub>, y3<\/sub>,\u2026\u2026.yn<\/sub>0 and d1<\/sub>, d2<\/sub>,\u2026\u2026dn<\/sub>, b1<\/sub>, b2<\/sub>,\u2026.., bm\u00ad<\/sub> are constants.<\/p>\n\n\n\n

Then its dual is<\/p>\n\n\n\n

(DUAL)<\/p>\n\n\n\n

Min Zw<\/sub> = b1<\/sub>w1<\/sub> +b2<\/sub>w2<\/sub> +\u2026\u2026..+bm<\/sub>wm<\/sub><\/p>\n\n\n\n

s.t.<\/p>\n\n\n\n

a11<\/sub>w1<\/sub> +a21<\/sub>w2<\/sub> +\u2026\u2026..+am1 <\/sub>wm<\/sub>d1<\/sub><\/p>\n\n\n\n

a12<\/sub>w1<\/sub> +a22<\/sub>w2<\/sub> +\u2026\u2026..+am2 <\/sub>wm<\/sub>d2<\/sub><\/p>\n\n\n\n

.<\/p>\n\n\n\n

.<\/p>\n\n\n\n

a1n<\/sub>w1<\/sub> +a2n<\/sub>w2<\/sub> +\u2026\u2026..+amn<\/sub>wm<\/sub>dn<\/sub><\/p>\n\n\n\n

and w1<\/sub>, w2<\/sub>, w3<\/sub>,\u2026\u2026.wm<\/sub>0<\/p>\n\n\n\n

Some important Results and theorem<\/p>\n\n\n\n

1.If we take the dual of the dual then it is primal.<\/p>\n\n\n\n

2. If a particular constraint in the primal is perfect equality then the corresponding dual variable is unrestricted.<\/p>\n\n\n\n

3. If any variable is unrestricted in sign in a primal then the corresponding constraint of the duality is a perfect equality.<\/p>\n\n\n\n

Example 1<\/p>\n\n\n\n

Primal<\/p>\n\n\n\n

Max Z = x + y<\/p>\n\n\n\n

s.t. x-y  20<\/p>\n\n\n\n

2x +3y  4<\/p>\n\n\n\n

5x \u2013 2y  2<\/p>\n\n\n\n

x, y 0<\/p>\n\n\n\n

Solution<\/p>\n\n\n\n

Max Z = x + y<\/p>\n\n\n\n

s.t. x-y  20  \u2026\u2026\u2026\u2026w1<\/sub><\/p>\n\n\n\n

2x +3y  4 \u2026\u2026\u2026\u2026\u2026w2<\/sub><\/p>\n\n\n\n

5x \u2013 2y 2  \u2026\u2026\u2026\u2026.w3<\/sub><\/p>\n\n\n\n

Dual<\/p>\n\n\n\n

Min Zw<\/sub> =20w1<\/sub> + 4w2<\/sub> + 2w3<\/sub><\/p>\n\n\n\n

S.t w1<\/sub> +2w2<\/sub> +5w3 <\/sub> 1<\/p>\n\n\n\n

  -w1<\/sub> + 3w2<\/sub> -2w3<\/sub>1<\/p>\n\n\n\n

w1<\/sub>, w2<\/sub>, w3<\/sub>0<\/p>\n\n\n\n

Example 2<\/p>\n\n\n\n

Primal is<\/p>\n\n\n\n

Min Z = x1<\/sub> +x2<\/sub> +x3<\/sub><\/p>\n\n\n\n

s.t. 2x1<\/sub> +3x2<\/sub> +5x3<\/sub>2<\/p>\n\n\n\n

3x1<\/sub> +x2<\/sub> +7x3<\/sub> =3<\/p>\n\n\n\n

x1<\/sub> +4x2<\/sub> +6x3<\/sub> 5<\/p>\n\n\n\n

x1<\/sub>, x2<\/sub>, x3<\/sub>0<\/p>\n\n\n\n

Dual is<\/p>\n\n\n\n

Max Zw<\/sub> = 2x1<\/sub> +3x2<\/sub> +5x3<\/sub><\/p>\n\n\n\n

s.t. 2w1<\/sub> +3w2<\/sub> +w3<\/sub>1<\/p>\n\n\n\n

3w1<\/sub> +w2<\/sub> +4w3<\/sub>1<\/p>\n\n\n\n

5w1<\/sub> +7w2<\/sub> +6w3<\/sub> 1<\/p>\n\n\n\n

w1<\/sub>, w3<\/sub>0, w2<\/sub> is unrestricted<\/p>\n\n\n\n

Rules for the Solutions<\/p>\n\n\n\n

When we obtain solution for one form of the LPP then depending on the nature of the solution for one we can conclude for the nature of the solution of the other as following:<\/p>\n\n\n\n

1. If we obtain bounded optimal solution<\/a> of Primal then the dual has bounded optimal solution.<\/p>\n\n\n\n

2. If we obtain an unbounded solution of primal (dual) then the dual (primal) has no feasible solution.<\/p>\n\n\n\n

3. If we obtain no feasible solution of Primal (dual) then the dual (primal) has either unbounded or no feasible solution.<\/p>\n\n\n\n

Some useful properties<\/p>\n\n\n\n

Even though we have studied how a dual of a primal can be evaluated, it becomes essential to understand the consequence of the same based on the type of solution we obtain.<\/p>\n\n\n\n

 1. Any feasible solution to the dual problem sets a bound on the optimal objective function value in the primal problem.<\/p>\n\n\n\n

2. Understanding the dual problem leads to specialized method for some important classes of linear programming problems. Examples include the transportation simplex method, the Hungarian algorithm for the assignment problem, and the network simplex method.<\/p>\n\n\n\n

3. The dual can be helpful for sensitivity analysis<\/a>. Changing the primal\u2019s right-hand side constraint or adding a new constraint to it can make the original primal optimal solution infeasible.<\/p>\n\n\n\n

4. The variables we get in a dual LPP gives the shadow prices for the primal LPP\u2019s constraints. For instance, suppose you have a profit maximization problem with a resource constraint say \u2018j\u2019. Then the valueyj<\/sub> of the corresponding dual variable in the optimal solution tells you that you get an increase of yj<\/sub> in the maximum profit for each unit increase in the amount of resource j.<\/p>\n\n\n\n

5. Sometimes it is easier to solve the dual of a LPP. A primal problem that has many constraints and few variables can be converted into a dual problem with few constraints and many variables.<\/p>\n\n\n\n

#jims #jimsdelhi #managementcollegeindelhi #pgdmcollegesindelhi #mbacollegesindelhi #toppgdmCollegesindelhi #topbschoolsindelhi<\/a><\/p>\n\n\n\n

For more information visit: https:\/\/www.jagannath.org\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Ms Pooja Bisht Assistant Professor Jagannath International Management School From the practical and the theoretical point of view, the concept of duality is one of the most imperative topics of […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/www.jagannath.org\/blog\/wp-json\/wp\/v2\/posts\/698"}],"collection":[{"href":"https:\/\/www.jagannath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.jagannath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.jagannath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.jagannath.org\/blog\/wp-json\/wp\/v2\/comments?post=698"}],"version-history":[{"count":3,"href":"https:\/\/www.jagannath.org\/blog\/wp-json\/wp\/v2\/posts\/698\/revisions"}],"predecessor-version":[{"id":707,"href":"https:\/\/www.jagannath.org\/blog\/wp-json\/wp\/v2\/posts\/698\/revisions\/707"}],"wp:attachment":[{"href":"https:\/\/www.jagannath.org\/blog\/wp-json\/wp\/v2\/media?parent=698"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.jagannath.org\/blog\/wp-json\/wp\/v2\/categories?post=698"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.jagannath.org\/blog\/wp-json\/wp\/v2\/tags?post=698"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}