Scribd
Upload
7K views

LPP - Big M Method

This document describes the artificial variable method for solving linear programming problems (LPP) in standard form using the Big M method. It presents an example problem and shows the steps to: 1) Express the original LPP in standard form by introducing slack and artificial variables. 2) Initialize the basic feasible solution by setting some variables to zero and others to large values (Big M). 3) Iterate to find an optimal solution by identifying entering and leaving variables at each step. 4) The optimal solution is found when all reduced costs are non-negative.

Uploaded by

Sundaramali Govindaswamy G
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
7K views

LPP - Big M Method

This document describes the artificial variable method for solving linear programming problems (LPP) in standard form using the Big M method. It presents an example problem and shows the steps to: 1) Express the original LPP in standard form by introducing slack and artificial variables. 2) Initialize the basic feasible solution by setting some variables to zero and others to large values (Big M). 3) Iterate to find an optimal solution by identifying entering and leaving variables at each step. 4) The optimal solution is found when all reduced costs are non-negative.

Uploaded by

Sundaramali Govindaswamy G
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 6

LINER PROGRAMMING PROBLEM- ARTIFICIAL

VARIABLE METHOD BIG M METHOD

Prof G SUNDARAMALI
ARTIFICIAL VARIABLE METHOD BIG M METHOD
Ex 2: Minimize Z = 12x1 + 20x2 To convert LPP into standard form

Subject to Inequality Add Variable

6x1 + 8x2 100, +S Slack variable


-S+A Surplus Artificial
7x1 + 12x2 120 and variable variable
X1, X2 0 = A Artificial variable

Sol: Step 1- Express the LPP in standard form


Minimize Z = 12x1 + 20x2 + 0s1 + 0s2
Subject to
6x1 + 8x2 - s1 = 100
7x1 + 12x2 - s2 = 120
x1,x2, s1, s2 0

12/1/2017 5:50 AM MEE 437 Operations Research


ARTIFICIAL VARIABLE METHOD BIG M METHOD
Since they are artificial variables A1 and A2
should not appear in the final solution. Hence they
are assigned a large unit penalty ( a large + value M)
in the objective function which can be written as
Minimize Z = 12x1+20x2+0s1+0s2+MA1+MA2
Now there are 6 variables and two constraints
and hence we have to set zero to four variables to
get the initial basic feasible solution.
Assume x1=x2=s1=s2=0
A1 = 100, A2 = 120, Z = 220 M

12/1/2017 5:50 AM MEE 437 Operations Research


Minimize Z = 12x1+20x2+0s1+0s2+MA1+MA2
BIG M Method ST 6x1 + 8x2 - s1 + A1 = 100
Table:1 IBFS Key column 7x1 + 12 x2 - s2 + A2 = 120
x1,x2, s1, s2,A1, A2 0
CJ 12 20 0 0 M M
F.R CB Basis
Variable X1 X2 S1 S2 A1 A2 b

2/3 M A1 6 8 -1 0 1 0 100 25/2


M A2 7 12 0 -1 0 1 120 10
ZJ 13M 20M -M -M M M 220M

CJ- ZJ 12-13M 20-20M M M 0 0

Optimal If all (Cj-Zj) 0 Key row


Entering variable = Leaving variable =
Smallest +ve
largest negative

Key element= intersection


of key col and key row
= b/Key col element
4
F.R CB Basis X1 X2 S1 S2 A1 b
Variable
BIG M Method 2/3 M A1 6 8 -1 0 1 100
Table:2 Iteration 1 M A2 7 12 0 -1 0 120

CJ 12 20 0 0 M
F.R CB Basis
Variable X1 X2 S1 S2 A1 b

M A1 4/3 0 -1 2/3 1 20 15
7/16 20 X2 7/12 1 0 -1/12 0 10 120/7
200+
ZJ 35/3+4/3M 20 -M -5/3+2/3M M 20M

5/3
CJ- ZJ 1/3-4/3M 0 M 0
2/3M
Leaving variable =
Optimal If all (Cj-Zj) 0 Smallest +ve
Entering variable =

largest negative
BIG M Method
Table:3 Iteration 2

CJ 12 20 0 0
CB Basis
Variable X1 X2 S1 S2 b
ANS:
12 X1 1 0 -3/4 1/2 15
X1 = 15,
20 X2 0 1 7/16 -3/4 5/4
X2 = 5/4
205
ZJ 12 20 -1/4 -9 Zmin = 205

CJ- ZJ 0 0 1/4 9

As (CJ- ZJ) = non negative


F.R CB Basis X1 X2 S1 S2 b
Table:3 is optimal
Variable
M A1 4/3 0 -1 2/3 20
7/16 20 X2 7/12 1 0 -1/12 10
6

You might also like