Tuesday, July 31, 2012

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 c1, c2, …, cn in the objective function of the primal appear in the constraints of the dual.

5.       The constants b1, b2, …, bm 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 = c1x1+c2x2+…+cnxn

Subject to   a11x1+a12x2+…+a1nxn ≤ b1

                    a21x1+a22x2+…+a2nxn≤b2

                                  …………..………………………………………………

                                 ………………………………………………………….

                      am1x1+am2x2+…+amnxn≤bm



where,   x1, x2, ...,xn, all ≥ 0.



Now its dual is:

Minimize w = b1y1+b2y2+…+bmym

Subject to   a11y1+a21y2+…+am1ym ≤ c1

                    a12y1+a22y2+…+am2ym ≤ c2

                                …………..………………………………………………

                               ………………………………………………………….

       a1ny1+a2ny2+…+amnym ≤ cn

where,  the dual variables y1, y2, …, ym, all ≥ 0.

Example: construct the dual of the problem,

                Maximize Z=3x1+17x2+9x3

                Subject to x1-x2+x3≥3

                                    -3x1+2x3 ≤1,

                                x1, x2, x3, all ≥ 0

solution:

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

i.e., -x1+x2-x3≤-3

now the dual of this problem is:

                minimize   W=-3y1+y2

                subject to   –y1-3y2 ≥ 3

                                        y1 ≥ 17

                                       -y1+2y2 ≥ 9

                                        y1, y2, both ≥ 0.



2.       When primal is in standard form:

Consider the L.P.P. or primal,

Maximize    z = c1x1+c2x2

Subject to    a11x1+a12x2 = b1                          ,,equality showing standard form.

       a21x1+a22x2 ≤ b2

       x1≥0, x2≥0.

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

                a11x1+a12x2 b1        ,    a11x1+a12x2    b1                     

or,             a11x1+a12x2 b1          ,      -a11x1-a12x2     -b1      

Now its dual is:

                                Minimize w = b1(y1-y1’’) +b2y2

                                                 Subject to a11(y1-y1’’) + a21y2   ≥ c1

                                                    a12(y1-y1’’) + a22y2  ≥ c2

                                                                            The dual variables,  y1, y1’’, y2, all  ≥ 0

Or, substituting (y1-y1’’) = y1, where y1 is unrestricted in sign.

We get,

                                Minimize w = b1y1 +b2y2

                                                 Subject to a11y1 + a21y2   ≥ c1

                                                    a12y1 + a22y2  ≥ c2

                                                                           so the dual variables,  y1 is unrestricted in sign and y2 ≥ 0.



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





Example: construct the dual of the problem,

                                Maximize Z = 3x1+10x2+2x3



                                                 Subject to 2x1+3x2+2x3 ≤ 7

                                                                                                               

                                              3x1-2x2+4x3 = 3

                                                   x1, x2, x3, 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,

                               

     3x1-2x2+4x3 ≤ 3   ,   3x1-2x2+4x3 ≥ 3  

Or, 3x1-2x2+4x3 ≤ 3   ,  -3x1+2x2-4x3 -3  



Now the dual of the problem is:

             Minimize W = 7y1 +3(y2-y2’’)

             Subject to  2y1+3(y2-y2’’) ≥ 3

                                   3y1-2(y2-y2’’) ≥ 10

                                   2y1+4(y2-y2’’) ≥ 2

                                y1, y2, y2’’, all ≥ 0

now substituting (y2-y2’’) = y2, where y2 is unrestricted in sign.

We get,

             Minimize W = 7y1 +3y2

             Subject to  2y1+3y2 ≥ 3

                                   3y1-2y2 ≥ 10

                                   2y1+4y2 ≥ 2

                                y1 ≥ 0 and y2 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.










Monday, July 30, 2012

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)2/(z2+1).

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

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

So zeros of f(z) is given by (z+1)2 = 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-z3/3!+z5/5!- …  = z(1-z2/3!+z4/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-z2)].

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

                                    z(1-z2) = 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.

Sunday, July 29, 2012

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


1.      Function: SUPPOSE THE POLYNOMIAL IS :  g(x) = x32x211x + 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)2-(2i)2

=x2-6x+9-4i2 = x2-6x+9+4 = x2-6x+13

Now by synthetic division,

(x2-6x+13 )   )  x32x211x + 52 (   x+4
                                      
                                            X3-6x2  +13x
                                       ------------------------
                               +4x2-24x+52

                                 4x2-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