In this article steps of the Simplex Method for solving Linear Programming Problem for Maximizing Objective Function has been explained with the help of an example where all the constraints are of <= type.
Maximize Z= 100X1 + 60X2 + 40X3
Subject to,
X1 + X2 + X3 <= 100
10X1 + 4X2 + 5X3 <= 600
2X1 + 2X2 + 6X3 <= 300
X1, X2, X3 >= 0
Maximize Z= 100X1 + 60X2 + 40X3 + 0.s1 + 0.s2 + 0.s3
Subject to,
X1 + X2 + X3 + s1 = 100
10X1 + 4X2 + 5X3 + s2 = 600
2X1 + 2X2 + 6X3 + s3 = 300
X1, X2, X3, s1, s2, s3 >= 0
Here, s1, s2 and s3 are called slack variable.
Example 01
Consider the problem below,Maximize Z= 100X1 + 60X2 + 40X3
Subject to,
X1 + X2 + X3 <= 100
10X1 + 4X2 + 5X3 <= 600
2X1 + 2X2 + 6X3 <= 300
X1, X2, X3 >= 0
Solution:
Reconstructing the problem by introducing slack variables to convert each in-equation(constraint) into equation as follows:Maximize Z= 100X1 + 60X2 + 40X3 + 0.s1 + 0.s2 + 0.s3
Subject to,
X1 + X2 + X3 + s1 = 100
10X1 + 4X2 + 5X3 + s2 = 600
2X1 + 2X2 + 6X3 + s3 = 300
X1, X2, X3, s1, s2, s3 >= 0
Here, s1, s2 and s3 are called slack variable.
Setup initial solution and construct initial simplex table
Searching starts from the origin(X1=0, X2=0, X3=0). Simplex method relies on the fact that, the solution must be at some corner point of the feasible solution region. When X1=0, X2=0 and X3=0 then obviously s1=100, s2=600 and s3=300. So, the current solution has three slack variables s1, s2, s3 with non-zero solution and three decision variables X1, X2, X3 with zero values. Variables with non-zero values are called basic variables and variables with zero values are called non-basic variables.
Table 01: Initial Simplex Table
________________________________________________________________________________________
Cj 100 60 40 00 00 00
----------------------------------------------------------------------------------------
Basic Solution X1 X2 X3 s1 s2 s3
Variable Variable
CB B b(=XB)
----------------------------------------------------------------------------------------
0 s1 100 1 1 1 1 0 0
0 s2 600 10 4 5 0 1 0
0 s3 300 2 2 6 0 0 1
----------------------------------------------------------------------------------------
Table 02: Calculation of Entering Variable
________________________________________________________________________________________
Cj 100 60 40 00 00 00
----------------------------------------------------------------------------------------
Basic Solution X1 X2 X3 s1 s2 s3
Variable Variable
CB B b(=XB)
----------------------------------------------------------------------------------------
0 s1 100 1 1 1 1 0 0
0 s2 600 10 4 5 0 1 0
0 s3 300 2 2 6 0 0 1
----------------------------------------------------------------------------------------
Z(=CB*XB) Zj= ⅀(CBi*aij) 0 0 0 0 0 0
=0 Cj - Zj 100 60 40 0 0 0
Table 03: Calculation of Departing Variable
________________________________________________________________________________________
Cj 100 60 40 00 00 00
----------------------------------------------------------------------------------------
Basic Solution X1 X2 X3 s1 s2 s3 Min
Variable Variable Ratio
CB B b(=XB) XB/X1
----------------------------------------------------------------------------------------
0 s1 100 1 1 1 1 0 0 100/1=100
0 s2 600 10 4 5 0 1 0 600/10=60
0 s3 300 2 2 6 0 0 1 300/2=150
----------------------------------------------------------------------------------------
Z(=CB*XB) Zj= ⅀(CBi*aij) 0 0 0 0 0 0
=0 Cj - Zj 100 60 40 0 0 0
Note that, intersection of key column and key row is the key element.
At the end of this step, we get the departing variable and new entering variable, according to which next simplex table will be developed for further computations.
Table 04: Calculation of new Simplex Table
________________________________________________________________________________________
Cj 100 60 40 00 00 00
----------------------------------------------------------------------------------------
Basic Solution X1 X2 X3 s1 s2 s3 Min
Variable Variable Ratio
CB B b(=XB)
----------------------------------------------------------------------------------------
0 s1 40 0 3/5 1/2 1 -1/10 0
100 X1 60 1 2/5 1/2 0 1/10 0
0 s3 180 0 6/5 5 0 -1/5 1
----------------------------------------------------------------------------------------
place X1 in place of s2. Divide the row by the key element(10).
Calculate other row value by the formula below:
Old row value - (corresponding element in key column*corresponding new value in the key row )
Explanation of the new values in the table above:
for the row corresponding to s1, element in key column=1
0 s1 100 1 1 1 1 0 0
-(minus)
100 X1 60 1 2/5 1/2 0 1/10 0 X 1
-----------------------------------------------------------
new value 40 0 3/5 1/2 1 -1/10 0
for the row corresponding to s3, element in key column=2
0 s3 300 2 2 6 0 0 1
-(minus)
100 X1 60 1 2/5 1/2 0 1/10 0 X 2
-----------------------------------------------------------
new value 180 0 6/5 5 0 -1/5 1
Table 05: Calculation of Entering Variable & Departing Variable
________________________________________________________________________________________
Cj 100 60 40 00 00 00
----------------------------------------------------------------------------------------
Basic Solution X1 X2 X3 s1 s2 s3 Min
Variable Variable Ratio
CB B b(=XB) XB/X2
----------------------------------------------------------------------------------------
0 s1 40 0 3/5 1/2 1 -1/10 0 40/(3/5)
100 X1 60 1 2/5 1/2 0 1/10 0 60/(2/5)
0 s3 180 0 6/5 5 0 -1/5 1 180/(6/5)
----------------------------------------------------------------------------------------
Z(=CB*XB) Zj= ⅀(CBi*aij) 100 40 50 0 10 0
=6000 Cj - Zj 0 20 -10 0 -10 0
Key Row : s1
Key Element: 3/5
Table 06: Calculation of new simplex table
________________________________________________________________________________________
Cj 100 60 40 00 00 00
----------------------------------------------------------------------------------------
Basic Solution X1 X2 X3 s1 s2 s3 Min
Variable Variable Ratio
CB B b(=XB)
----------------------------------------------------------------------------------------
60 X2 200/3 0 1 5/6 5/3 -1/6 0
100 X1 100/3 1 0 1/6 -2/3 1/6 0
0 s3 100 0 0 4 -2 0 1
----------------------------------------------------------------------------------------
Z(=CB*XB) Zj= ⅀(CBi*aij)
=6000 Cj - Zj
place X2 in place of s1. Divide the row by the key element(3/5).
Calculate other row value by the formula below:
Old row value - (corresponding element in key column*corresponding new value in the key row )
Explanation of the new values in the table above:
for the row corresponding to X1, element in key column=2/5
100 X1 60 1 2/5 1/2 0 1/10 0
-(minus)
60 X2 200/3 0 1 5/6 5/3 -1/6 0 x2/5
---------------------------------------------------------------------------------------------------------------100/3 1 0 1/6 -2/3 1/6 0
for the row corresponding to s3, element in key column=6/5
-(minus)
60 X2 200/3 0 1 5/6 5/3 -1/6 0 x6/5
-----------------------------------------------------------------
100 0 0 4 -2 0 1
Table 07: Final Simplex Table
________________________________________________________________________________________
Cj 100 60 40 00 00 00
----------------------------------------------------------------------------------------
Basic Solution X1 X2 X3 s1 s2 s3
Variable Variable
CB B b(=XB)
----------------------------------------------------------------------------------------
60 X2 200/3 0 1 5/6 5/3 -1/6 0
100 X1 100/3 1 0 1/6 -2/3 1/6 0
0 s3 100 0 0 4 -2 0 1
----------------------------------------------------------------------------------------
Z(=CB*XB) Zj= ⅀(CBi*aij) 100 60 200/3 100/3 20/3 0
=22000/3 Cj - Zj 0 0 -80/3 -100/3 -20/3 0
Since, all the values in Cj - Zj are -ve, so, there are no chance of further improvement in the maximization. So, the solution is,
X1= 100/3
X2= 200/3
X3= 0
Z= 22000/3
Test that, X1, X2, X3 satisfyies all the constraints to verify the solution is feasible or not.
Present sir.
ReplyDeletePresent sir
ReplyDeleteI am present Sir.
ReplyDeletepresent sir
ReplyDeleteWrite down content of this article in your notebook very carefully.
ReplyDeleteAfter completion, please inform here (As Reply)....
done sir.
DeleteWriting finished sir
DeleteDone sir.
DeletePresent sir
ReplyDeleteRead the article.
ReplyDeleteAfter completion of reading, please inform here (As Reply)....
you do not have to mention any query/ confusion/ question regarding this article,
I will make a conference at the end of your reading....
I have read the article.
DeleteTake a break, back at 1.45pm....
DeleteDone sir
DeleteDone sir
DeleteI have read the article
DeleteDone sir
DeleteDone sir
DeleteAttendance submitted
ReplyDeleteDone Sir
ReplyDeleteDone sir
ReplyDeleteDone sir
ReplyDeleteAttendance submitted .
ReplyDeleteDone sir
ReplyDelete