Linear programming problem Using simplex method.

Question :
                   Max Z = 6X + 8Y
 subject to,
                   30X + 20Y ≤ 300
                     5X + 10Y ≤110
                        X,Y ≥ 0

Solution :


Step 1: First of all,Convert the above equations in standard form.And,then Add S1 ,S2 in the equation (i)  & (ii) respectively in L.H.S Side with coefficient 1.
While in the objective function add or subtract (It doesn't affect the equation) S1 & S2 with coefficient 0 in L.H.S.

Note 1: If there was greater or equal to sign (≥) in the equation then you have to subtract S1 & S2 respectively in the L.H.S. 

Note 2: We had taken here only two variables S1 & S2 because here we have only two equations other than objective function.


             Z-6X-8Y + 0S1 + 0S2 = 0     (Objective function)
             30X + 20Y + S1 = 300......................(i)
               5X + 10Y+ S2  = 110......................(ii)

Step 2: Create a table for Iteration 0 or Basic Iteration & Write the coefficient of each variable of the equation in the table.

Iteration 0 [Basic Iteration]
---------------------------------
                        Basic       Z        X        Y       S1       S2       Solution     Intercept

 Row 1.......       Z            1         -6      -8        0          0            0

Row 2.......       S1           0         30      20       1           0           300

Row 1......        S2           0          5       10       0           1           110 

Step 3: Now, Search the highest -ve number in terms of magnitude like (we have,-6 & -8, We choose -8) in the formed table and Mark it. And, update the table by calculating intercept (Intercept is calculated by Dividing the Solution column of each row by the column elements of the highest negative number).


                       Basic       Z        X        Y       S1       S2       Solution     Intercept

 Row 3.......       Z            1         -6      -8        0          0             0                 0

Row 2.......       S1           0         30      20       1           0           300             15

Row 1......        S2           0          5       10       0           1           110             11

Step 4: Now, find out the Lowest positive number in the intercept Column (Except 0) and Mark it. And, Mark the Number which coincides with the column and the row (Red marked Number is the Coinciding number) and Name that Number as a Pivot Element. And, the Respective Column & Row is known as Pivot Column or Key Column & Pivot Row & Key Row respectively. Rename the Basic Name of that Row where Pivot Element is found as X (If pivot element is found in S1 Row) & Y (If pivot element is found in S2 Row).

                       Basic       Z        X        Y       S1       S2       Solution     Intercept

 Row 3.......       Z            1         -6      -8        0          0            0                 0

Row 2.......       S1           0         30      20       1           0           300            15

Row 1......         Y           0          5       10       0           1           110            11


Step 4: Now, Make That pivot element 1 by using row operation and update the table and remove the intercept column Numbers.
            
Row operation: (R1 -> R1/10)

                      Basic       Z        X        Y       S1       S2       Solution     Intercept

 Row 3.......       Z            1         -6      -8        0          0            0                 

Row 2.......       S1           0         30      20       1          0           300            

Row 1......         Y           0          0.5      1       0          0.1        11              


Step 5: Make all the elements of the pivot column as 0 (Except that 1 which we got after row operation) by using the Row operation.

Row operation: ( R3 ->R3 + 8*R1) & (R2 ->R2 - 20*R1)

                       Basic       Z        X        Y       S1       S2       Solution     Intercept

 Row 3.......       Z           1        -2        0        0         0.8         88              

Row 2.......       S1           0        20       0        1       -0.2         80          

Row 1......         Y           0        0.5      1        0         0.1         11              

Step 6: Now, check-in Row-3(Z Row) is there any negative highest number left.If you find it continue the same operation from Step-3 to step-5.And, from here iteration 1 starts else you have to end here.

Iteration 1:

Repeating step 3: 
                        Basic       Z        X        Y       S1       S2       Solution     Intercept

 Row 3.......       Z            1        -2        0         0          0.8          88               -44

Row 2.......       S1           0        20        0         1         -0.2        80                 4

Row 1......         Y           0        0.5       1          0          0.1        11                22

Repeating step 4:

Row operation : (R2 -> R2/20)

                        Basic       Z        X        Y       S1       S2       Solution     Intercept

 Row 3.......       Z            1       -2          0        0         0.8         88               

Row 2.......        X           0        1          0      0.05    -0.01        4                 

Row 1......         Y           0        0.5       1        0          0.1        11             

Repeating step 5:

Row operation: (R3 ->R3 + 2R2  & R1 -> R1 - 0.5*R2)

                        Basic       Z        X        Y         S1          S2       Solution     Intercept

 Row 3.......       Z            1        0         0         0.1          0.78          96               

Row 2.......        X           0        1         0         0.05        -0.01          4                 

Row 1......         Y           0        0        1        -0.025       0.105         9   

Now, we can clearly see that there is no Negative value left in Row Z.So, the solution column gives the value of all the variables.

Max Z = 96  (Answer)

Now, check the value in the objective equation, that is this value satisfying the equation or not.

Max Z = 6X + 8Y
96 = 6(4) + 8(9) => 96 = 24 + 72 => 96 =96 (Hence our Answer is correct.)


Must check out this :  LPP Problem using Graphical method

Comments

Post a Comment

Popular posts from this blog

Show that number of pendant vertices in a binary tree is (n+1)/2 ,where n is the number of vertices in the tree.

Image
The number of vertices of odd degree in an undirected graph is even,(N-1) is even.  Therefore, n is odd. Let p be the number of pendant vertices. 2+p+3(n- p-1) = 2(n-1) or, 3n-2n-3+4 = 2p or, 2p = n+1 or, P = (n+1)/2 Hence, the number of pendant vertices is (n+1)/2. Also, see : 1.)  Graph Theory and Tree 2.)  The Reflection about line yx is.......... 3.)  Prove that a simple graph with n vertices and k components can have at most 1/2(n-k)(n-k-1) edges. 4.)  Show for what condition rotation and scaling are commutative. 5.) Vector in R space 6.) Prove that every tree has at most one perfect matching. 7.)  Prove that every tree with 2 or more vertices is 2-chromatic. 8.)  Show that every Bi-partite graph is 2 chromatic. 9.) Prove that the number of circular permutations of n different objects is (n-1)! . 10.)  State the "Pigeon Hole Principle" and the " Generalised pigeon Hole principle".
Read more

Prove that every tree with 2 or more vertices is 2-chromatic.

Image
Since a tree is connected and has no cycle if one starts coloring any one vertex with a specific color and keeps on coloring every alternate vertex with another color, the entire graph can be colored with only two colors and since there is one and only one path between any two vertices in a tree, no two vertices will have the same color. Hence every Tree with 2 or more vertices is 2-Chromatic.    [Proved]                                                                 FIG (I)                                                                  FIG (II)
Read more

Top 5 websites to learn coding Online

Image
Now, A Days Technology became our Daily Life partner. Sometimes we people are wondering how this page, website, Blog ,Game works .Then,Our Mind  starts searching for Real phenomenon .How this site works ,why this website is different from others,How the widget is different from others ,How e-commerce website works. So, The answer of all of the above is "CODING". Being a programmer ,i think without Coding Digital Word is Nothing. So, you need to learn Coding if you are interested in Digital world. Myths about coding is that It is Hard to Understand & Hard to Write.There is nothing like this.Just you have to do some basic Homework daily and continuation in learning.Learn Coding like a Interesting Puzzle and solve like a "SUDUKO" Game. Let's Start: Kids Section: For kids Go for  Tynker   (Android/IOS) and  Hopscotch   (IPAD) .These sites are the best tutor of kids ,they teach coding in the form of Games & Puzzles.
Read more