Big M Method 6 Sept
Big M Method 6 Sept
Big M Method 6 Sept
Code: HSMC701
Group No: 16
Term Paper Title: SWOT ANALYSIS
Student Details
11500120073
SHASHI RANJAN
SOURAV NAYEK
11500320093
< Please do not write anything below the dotted line >
...........................................................................................................................................................................
Marks awarded
Marks Awarded
Total Marks
INDEX
Abstract
Example 1
Example 2
Example 3
Conclusion
Reference
ABSTRACT
4. Iteration: The LP problem is solved using the simplex method with the
modified objective function, which now includes the artificial variables and the
large 'M' values. The simplex method is used to pivot between basic and non-
basic variables until an optimal solution is reached or an unbounded solution is
detected.
5. Artificial Variables and 'M': During the iteration, the artificial variables are
driven to zero in the objective function as the algorithm progresses. The goal is
to minimize their contribution to the objective, and ideally, they should
become zero in the optimal solution. If any artificial variable remains positive
at the optimal solution, it implies that the original LP problem is infeasible.
Step 2- add non- negative artificial variable to the left side of each of the
equations corresponding to constraints of the type '≥' or ' ='.
Example 1:
Ex1: find the optimal solution for the following LPP.
Max z= 5X1+12X2+4X3
X1+2X2+X3≤5
2X1+X2+3X3=2
X1≥0, X2≥0, X3≥0
Substitute in Z
Z = 5X1+12X2+4X3-M(2-2X1+X2-3X3)
= (5+2M)X1+(12-M)X2+(4+3M)X3
-2M = Z-(5+2M) X1-(12-M)X2-(4+3M)X3,
X1+2X2+X3+S1=5,
2X1-X2+3X3+R=2
Basic X1 X2 X3 S1 R Solution
var.
Z -5-2M -12+M -4-3M 0 0 -2M
S1 1 2 1 1 0 5
R 2 -1 3 0 1 2
Z -7/3 -40/3 0 0 4/3+M 8/3
S1 1/3 7/3 0 1 -1/3 13/3
X3 2/3 -1/3 1 0 1/3 2/3
Z -3/7 0 0 40/7 -4/7+M 192/7
X2 1/7 1 0 3/7 -1/7 13/7
X3 5/7 0 1 1/7 2/7 9/7
Z 0 0 3/5 29/5 -2/5+M 141/5
X2 0 1 -1/5 2/5 -1/5 3/5
X1 1 0 7/5 1/5 9/5
2/5
Example 2:
Ex2: Find the optimal solution for the following LPP.
MIN Z=4X1+X2
3X1+X2=3
4X1+3X2≥6
X1+2X2≤4
X1≥0, X2≥0
Substitute in Z
Z = 4X1+X2+M(3-3X1-X2)+M(6-4X1-3X2+S1)
Z = (4-7M)X1+(1-4M)X2+MS1+9M
9M = Z-(4-7M)X1-(1-4M)X2-MS1
3X1+X2+R1=3
4X1+3X2-S1+R2=6
X1+2X2+S2=4
Basic var X1 X2 S1 S2 R1 R2 Solu.
Z 4-7M -1+4M -M 0 0 0 9M
R1 3 1 0 0 1 0 3
R2 4 3 -1 0 0 1 6
S2 1 2 0 1 0 0 4
Z 0 1/3+5/3M -M 0 4/3-7/3M 0 4+2M
X1 1 1/3 0 0 1/3 0 1
R2 0 5/3 -1 0 -4/3 1 2
S2 0 5/3 0 1 -1/3 0 3
Z 0 0 1/5 0 8/5-M -1/5-m 18/5
X1 1 0 1/5 0 3/5 -1/5 3/5
X2 0 1 -3/5 0 -4/5 3/5 6/5
S2 0 0 1 1 1 -1 1
Z 0 0 0 -1/5 7/5-M -M 17/5
X1 1 0 0 -1/5 2/5 0 2/5
X2 0 1 0 3/5 -1/5 0 9/5
S1 0 0 1 1 1 -1 1
Example 3:
Ex3: Find the optimal solution for the following LPP.
Max Z = 3X1 + 2X2+ X3
S.T. 2X1 + X2+ X3= 12
3X1+ 4X3=11
X2≥0, X3≥0 and X1 is unrestricted
Solution:
SLPP
Max Z = 3( X1̇ - X1") + 2X2+X3- M R1- M R2 subject to
2(X1'-X1")+X2+X3+R1=12
3(X1'-X1")+4X3+R2=11
X1', X1", X2, X3, R1, R2≥0
Max z= 3X1'-3X1"+2X2+X3-M R1- M R2
2X1'-2X1"+X2+X3+R1=12
3X1'-3X1"+4X2+R2=11
X1', X2", X2, X3, R1, R2 ≥0.
Cj 3 -3 2 1 -M M
Basic var X1' X1" X2 X3 R1 R2 Solution
R1 2 -2 1 1 1 0 12
R2 3 -3 4 0 0 1 11
Z -5m-3 5m+3 -5m-2 -m-1 0 0 -23M
R1 0 0 -5/3 1 1 X -14/3
X1' 1 -1 4/3 0 0 X -11/3
Z 0 0 5/3 M+2 -M-1 0 X -14M/3-11
X3 0 0 -5/3 1 X X 14/3
X1' 1 -1 4/3 0 X X 11/3
Z 0 0 1/3 0 X X 47/3
Since all 𝑍 ≥ 0, optimal basic feasible solution is obtained
X1' = 11/3, X1"=0
X1=X1'-X1"=11/3-0=11/3
Therefore the solution is max Z=47/3, X1=11/3, X2=0, X3=14/3
Conclusion:
In conclusion, the Big-M Method is a versatile technique in linear programming
that serves as a valuable tool for solving linear programming problems, even
when they do not initially adhere to the standard LP form. By introducing
artificial variables with large positive constants ('M') into the objective
function, this method transforms the problem into standard LP format,
enabling the application of the simplex algorithm to find an optimal solution.
http://www.universalteacherpublications.com/univ/ebooks/or/Ch3/
mmethod.htm
https://link.springer.com/article/10.1007/s11590-020-01644-6
http://pirate.shu.edu/~wachsmut/Teaching/MATH3626/2015-03/
lin_prog_www.pstcc.edu_facstaff_jwlamb/Simplex%20method
%204%20(www.pstcc.edu_facstaff_jwlamb_Math1630_6.4.pdf).pdf