Mathemagic: Linear programming- conversion of L.P.P. into its dual

Linear programming

Conversion of primal into its dual

Duality is an extremely important feature of linear programming. The various useful aspects of this property are:

1.       If the primal problem contains a large number of rows(constraints) and a smaller number of columns(variables), then the computational procedure can be reduced by converting it into dual and then solving it.

2.       Calculation of dual checks the accuracy of the primal solution.

3.       Duality in linear programming shows that each linear programme is equivalent to a two-person zero-sum game. This indicates a close relationship between linear programming and theory of games.

There are following points to remember while converting into dual.

1.       If the primal contains n variables and m constraints, the dual will contain m variables and n constraints.

2.       The maximization problem in the primal becomes the minimization problem in the dual and vice versa.

3.        The maximization problem has (≤) constraints while the minimization problem has (≥) constraints.

4.       The constants c₁, c₂, …, c_n in the objective function of the primal appear in the constraints of the dual.

5.       The constants b₁, b₂, …, b_m in the constraints of the primal appear in the objective function of the dual.

6.       The variables in both problems are non-negative.

Conversion of primal to its dual:

1.       When primal is in canonical form:

                The general L.P.P.(linear programming problem) or primal in canonical form is:

  Maximize z = c₁x₁+c₂x₂+…+c_nx_n

Subject to   a₁₁x₁+a₁₂x₂+…+a_1nx_n ≤ b₁

                    a₂₁x₁+a₂₂x₂+…+a_2nx_n≤b₂

                                  _{…………..………………………………………………}

                                 _{………………………………………………………….}

                      a_m1x₁+a_m2x₂+…+a_mnx_n≤b_m

where,   x_1, x_2, ...,x_n, all ≥ 0.

Now its dual is:

Minimize w = b₁y₁+b₂y₂+…+b_my_m

Subject to   a₁₁y₁+a₂₁y₂+…+a_m1y_m ≤ c₁

                    a₁₂y₁+a₂₂y₂+…+a_m2y_m ≤ c₂

                                _{…………..………………………………………………}

                               _{………………………………………………………….}

       a_1ny₁+a_2ny₂+…+a_mny_m ≤ c_n

where,  the dual variables y₁, y₂, …, y_m, all ≥ 0.

Example: construct the dual of the problem,

                Maximize Z=3x₁+17x₂+9x₃

                Subject to x₁-x₂+x₃≥3

                                    -3x₁+2x₃ ≤1,

                                x_1, x_2, x_3, all ≥ 0

solution:

firstly we need to convert first constraint into (≤) ,multiplying the inequality by (-1),                 because the objective function is maximize.

i.e., -x₁+x₂-x₃≤-3

now the dual of this problem is:

                minimize   W=-3y₁+y₂

                subject to   –y₁-3y₂ ≥ 3

                                        y₁ ≥ 17

                                       -y₁+2y₂ ≥ 9

                                        y_1, y_2, both ≥ 0.

2.       When primal is in standard form:

Consider the L.P.P. or primal,

Maximize    z = c₁x₁+c₂x₂

Subject to    a₁₁x₁+a₁₂x₂ = b₁                          ,,equality showing standard form.

       a_21x1+a₂₂x₂ ≤ b₂

       x₁≥0, x₂≥0.

             Here the first constraint can be expressed in canonical form like,

                a₁₁x₁+a₁₂x₂ ≤ b_{1        ,}    a₁₁x₁+a₁₂x₂   ≥ b₁                     

or,             a₁₁x₁+a₁₂x₂ ≤ b_{1          ,}      -a₁₁x₁-a₁₂x₂  ≤   -b₁      

Now its dual is:

                                Minimize w = b₁(y₁^’-y₁^’’) +b₂y₂

                                                 Subject to a₁₁(y₁^’-y₁^’’) + a₂₁y₂   ≥ c₁

                                                    a₁₂(y₁^’-y₁^’’) + a₂₂y₂  ≥ c₂

                                                                            The dual variables,  y₁^’, y₁^’’, y_2, all  ≥ 0

Or, substituting (y₁^’-y₁^’’) = y₁, where y₁ is unrestricted in sign.

We get,

                                Minimize w = b₁y₁ +b₂y₂

                                                 Subject to a₁₁y₁ + a₂₁y₂   ≥ c₁

                                                    a₁₂y₁ + a₂₂y₂  ≥ c₂

                                                                           so the dual variables,  y₁ is unrestricted in sign and y₂ ≥ 0.

NOTE: A=B IS EQUIVALENT TO->    A ≤ B AND A  ≥ B.

Example: construct the dual of the problem,

                                Maximize Z = 3x₁+10x₂+2x₃

                                                 Subject to 2x₁+3x₂+2x₃ ≤ 7

                                                                                                               

                                              3x₁-2x₂+4x₃ = 3

                                                   x₁, x₂, x_3, all  ≥ 0

solution: since the problem is of maximization , so all constraint should be (≤).

                                Second constraint can be expressed as a pair of inequalities like,

                               

     3x₁-2x₂+4x₃ ≤ 3   ,   3x₁-2x₂+4x₃ ≥ 3  

Or, 3x₁-2x₂+4x₃ ≤ 3   ,  -3x₁+2x₂-4x₃ ≤  -3  

Now the dual of the problem is:

             Minimize W = 7y₁ +3(y₂^’-y₂^’’)

             Subject to  2y₁+3(y₂^’-y₂^’’) ≥ 3

                                   3y₁-2(y₂^’-y₂^’’) ≥ 10

                                   2y₁+4(y₂^’-y₂^’’) ≥ 2

                                y_1, y₂^’, y₂^’’, all ≥ 0

now substituting (y₂^’-y₂^’’) = y_2, where y₂ is unrestricted in sign.

We get,

             Minimize W = 7y₁ +3y₂

             Subject to  2y₁+3y₂ ≥ 3

                                   3y₁-2y₂ ≥ 10

                                   2y₁+4y₂ ≥ 2

                                y₁ ≥ 0 and y₂ is unrestricted in sign.

Some points to remember:

1.       The dual of the dual is the primal.

2.       If either the primal or dual problem has an unbounded solution, then the solution to the other problem is infeasible.

3.       If both the primal and the dual have feasible solutions, then both have optimal solutions.

And max Z = min W.

4.       The value of the objective function is same for primal and dual solutions, but of opposite signs.