Big M Method 6 Sept

Download as docx, pdf, or txt
Download as docx, pdf, or txt
You are on page 1of 12

1

B. P. Poddar Institute of Management and Technology


Department of Computer Science & Engineering

Term Paper Details

Paper Name: PROJECT MANAGEMENT AND ENTREPRENEURSHIP

Code: HSMC701

Group No: 16
Term Paper Title: SWOT ANALYSIS

Student Details

Name University Roll No

SAGAR DEBNATH 11500120009

11500120073
SHASHI RANJAN

SURAJIT BAG 11500120115

SOURAV NAYEK
11500320093

< Please do not write anything below the dotted line >
...........................................................................................................................................................................
Marks awarded

Marks Awarded

Total Marks
INDEX

 Abstract

 Introduction Of Big- M Method to Solve LPP Problems

 Steps of Big-M Method

 Example 1

 Example 2

 Example 3

 Conclusion

 Reference
ABSTRACT

The Big-M Method is a fundamental tool in linear programming (LP) used to


address LP problems that don't conform to the standard LP form. It is
particularly useful when dealing with inequality constraints, mixed variable
types (some continuous, some discrete), or problems involving both
maximization and minimization objectives.

In the Big-M Method, the LP problem is modified to convert it into a


standard form. This involves the introduction of surplus and artificial variables
to handle inequalities and ensure non-negativity of variables. The key feature
is the inclusion of a large positive constant, typically referred to as 'M,' in the
coefficients of the artificial variables in the objective function. The choice of 'M'
is crucial, as it needs to be large enough to ensure these variables are driven to
zero during the optimization process but not so large as to cause numerical
instability.

The method proceeds with the iterative application of the simplex


algorithm, which pivots between basic and non-basic variables, aiming to find
the optimal solution while minimizing the artificial variables. The algorithm
terminates when no further improvement in the objective function value is
possible, indicating optimality.

While the Big-M Method is a powerful approach to transform and solve


non-standard LP problems, it may have computational challenges, especially
when 'M' values are not chosen carefully or when the problem is ill-
conditioned. Despite these challenges, it remains a valuable tool in the LP
toolbox for addressing complex real-world optimization problems.
Introduction Of Big- M Method to Solve LPP Problems

The Big-M Method is a widely-used technique in linear programming (LP) to


solve linear programming problems, including linear programming problems
with inequality constraints and linear programming problems with
minimization or maximization objectives. It was developed to handle situations
where the problem is not initially in the standard form of linear programming,
which typically requires all constraints to be in the form of equations and all
variables to be non-negative.

Here is a brief overview of the Big-M Method:

1. Objective Function: The first step is to convert the LP problem into an


equivalent problem with equality constraints and all variables non-negative.
This involves introducing surplus variables for inequalities and artificial
variables for any missing non-negativity constraints. The objective function is
modified accordingly to include these artificial variables.

2. Big-M Values: The Big-M Method relies on introducing a large positive


constant (usually denoted as 'M') into the coefficients of the artificial variables
in the modified objective function. The value of 'M' should be chosen carefully
to ensure that it is significantly larger than any feasible solution but not too
large to cause numerical instability.

3. Initial Solution: An initial basic feasible solution (BFS) is needed to begin


the iterative process. This can be obtained using various techniques such as the
graphical method, the two-phase method, or the simplex method for linear
programming.

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.

6. Optimality and Termination: The Big-M Method continues to pivot


variables until the optimal solution is reached. The algorithm stops when no
further improvement in the objective function value can be achieved,
indicating optimality. At this point, the artificial variables should ideally be
zero, and the solution can be interpreted.

7. Post-Optimality Analysis: After obtaining the optimal solution, further


analysis can be conducted to check for infeasibility, unboundedness, and
sensitivity analysis to assess how changes in problem parameters affect the
optimal solution.

Steps of Big-M Method:


Step 1- express the problem in the standard from.

Step 2- add non- negative artificial variable to the left side of each of the
equations corresponding to constraints of the type '≥' or ' ='.

When artificial variables are added, it causes violation of the corresponding


constraints. This difficulty is removed by introducing a condition which ensures
that variables will be zero in the final solution (provided the solution of the
problem exists).
On the other hand , if the problem does not have a solution, at least one of
the artificial variables will appear in the final solution with positive value. This
is achieved by assigning a very large price (per unit penalty) to these variables
in the objective function. Such large will be designated by –M for maximization
problems (+M for minimizing problem), where M>0.
Step 3- in the last, use the artificial variables for the starting solution and
proceed with the usual simplex routine until the optimal solution is obtained.

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

Convert to the standard form:


Z=5X1+12X2+4X3-MR
X1+2X2+X3+S1=5
2X1-X2+3X3+R=2
R=2-2X1+X2-3X3

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

Convert to the standard form


Min Z=4X1+X2+MR1+MR2
3x1+x2+R1=3
4x1+3x2-S1+R2=6
X1+2X2+S2=4
X1,X2,S1,S2,R1,R2≥0
R1=3-3x1-x2
R2=6-4x1-3x2+S1

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.

While the Big-M Method is effective in handling a wide range of linear


programming problems, it does come with some considerations. The choice of
the 'M' values is crucial; if 'M' is too large, it can lead to numerical instability,
and if it's too small, it may not drive the artificial variables to zero effectively.
Additionally, the method can be computationally intensive, particularly for
complex problems.

Despite these challenges, the Big-M Method remains a valuable approach in


addressing real-world optimization problems with inequality constraints, mixed
variable types, and both maximization and minimization objectives. It provides
a systematic way to convert and solve non-standard LP problems and can be
combined with other optimization techniques for more robust and efficient
solutions. When used judiciously, the Big-M Method helps decision-makers
optimize resources, make informed choices, and address complex business and
engineering challenges.
References:
 https://en.wikipedia.org/wiki/Big_M_method

 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

You might also like