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.

Mathemagic: How to find what kind of singularities the function have!

SINGULARITIES

There are following main terms about singularity.

1.    Zeros:  An analytic function f(z) is said to have a zero of order m if f(z) is expressible as,

f(z) = (z-a)^mφ(z)

where, φ(z) is analytic and φ(a) ≠ 0.

(a) f(z) is said to have a simple zero at z=a, if z=a is a zero of order 1.

Example:  find the zeros of (z+1)²/(z²+1).

Solution: let f(z) = (z+1)² φ(z) , notice that here a=-1 and m=2.

      Where φ(z) = 1/(z²+1). And also φ(z) is analytic and φ(-1)=1/2 ≠ 0.

So zeros of f(z) is given by (z+1)² = 0

OR,    z=-1,-1

Hence we can say z=-1 is a zero of order 2.

2.    Limit point of zeros:  Limit points of zeros is an isolated essential singularity.

Example: what kind of singularity of the function sin[1/(1-z)] at z=1 ?

Solution: let f(z)= sin[1/(1-z)]

            Zeros of f(z) are given by sin[1/(1-z)] = 0

So, 1/(1-z) = nπ or 1-z = 1/nπ

z = 1-(1/n π)  where, n=0, ±1, ±2, …

taking limit n→∞ , we get z=1.

So  we can say, z=1 is a limit points of zeros.

Hence z=1 is an isolated essential singularity.

3.    Singular points: A singularity (or singular points) of a function is the point at which

the function ceases be analytic.

Example: if f(z) = 1/(z-2),  then z=2 is a singularity of f(z). because at z=2, function is not analytic.

Note:: here z=2 is also an “isolated singularity”.

Example: function f(z)=1/z is analytic everywhere except at z=0.

       So z=0 is an isolated singularity.

4.    Removable singularity: A singularity z=a is called removable of f(z) if  

      Lim(z→a)  f(z) exists finitely.

Example: f(z) = sinz/z. then lim(z→0) sinz/z = 1

       Because   sinz = z-z³/3!+z⁵/5!- …  = z(1-z²/3!+z⁴/5!- …)

Hence we can say, z=0 is a removable singularity of f(z).

5.         Poles: A function f(z) is said to have pole of order m if it is expressible as,

f(z) = φ(z) / (z-a)^m

where, φ(z) is analytic and φ(a) ≠ 0.

Example: discuss the nature of singularity of f(z)=1/[z(1-z²)].

Solution: singularities(or poles) of f(z) is given by,

                                    z(1-z²) = 0

                                                or,  z = 0, -1, 1

hence z = 0, -1, 1 are simple poles (or poles of order 1).

6.  Limit points of poles:  limit point of poles is an non-isolated essential singularity.

Example: what kind of singularity has the function?

Solution: f(z)=1/[cos(1/z)] at z=0.

                 Poles of f(z) are given by, cos(1/z) = 0 = cos(π/2)

                                                                       Or, 1/z = 2nπ ± π/2

                                                                            z = 1/(2nπ ± π/2)

                                                                       taking limit n→∞

                                                                           z=0

so z=0 is the limit point of poles.

Hence z=0 is an non-isolated essential singularity.

Mathemagic: How to find all roots of polynomial if one imaginary root is given.

1.      Function: SUPPOSE THE POLYNOMIAL IS :  g(x) = x³ − 2x² − 11x + 52

Zero: 3 + 2i

        
          Remember always imaginary zeros always comes in pair.

So 3-2i is also a zero of g(x).

Hence {x-(3+2i)} and {x-(3-2i)} are factors of g(x).

And also g(x) will be divisible by product of these two factors.

Product of {x-(3+2i)} and {x-(3-2i)} is {(x-3)-2i}*{(x-3)+2i} = (x-3)²-(2i)²

=x²-6x+9-4i² = x²-6x+9+4 = x²-6x+13

Now by synthetic division,

(x²-6x+13 )   )  x³ − 2x² − 11x + 52 (   x+4

                                      

                                            X³-6x²  +13x

                                       ------------------------

                               +4x²-24x+52

                                 4x²-24x+52

                                       ------------------------            
                                                     0

                                                       ------------------------

Hence (x+4) is a factor of g(x).

=> x=-4 is also a zero of g(x).

So all the zeros of g(x) are: 3+2i, 3-2i, -4