SIMPLEX METHOD

Simplex method is used to solve linear programming problems. It is an iterative

method. It involves a number of iterations of simplex algorithm . It is a step by
step process from one feasible solution to another until we reach optimal
solution

Slack variable: A slack variable represents unutilized capacity of a variable

.slack variable is represented by S

Cj row: The raw in simplex table which represents profit or contribution of

each variable in the objective function

Zj row: The raw in simplex table which represents the decrease in the value of
the objective function if 1 unit of that variable is brought in the solution

∆ = Cj – Z j row : The raw in the simplex table which represents the net
increase in the objective function , if 1 unit of that variable is brought in that
solution .positive value of∆ indicates gain or increase in profit and negative
value of ∆ indicates decrease in profit or loss

Key column(incoming variable): The variable which has maximum

positive (cj-zj) is called incoming variable for next table

Key row(outgoing variable): The variable which goes out of the solution in the
next table. It is replaced by incoming variables in the basis

To find key row we need to find replacement ratios for all basis variables

The formula for replacement ratio is b column/key column

Optimal solution: A simplex solution is optimal when there is no positive ∆

values in the solution. That is all ∆ values are either negative or zero
 Examples:

Q1. Solve the following LPP

Maximize z= 100x1+80x2

Subject to the constraints

6x1+4x2≤7200

2x1+4x2≤4000

X1≥0 , x2≥0

Solution:

Standard form of given LPP is

Maximize z = 100x1+80x2+0s1+0s2

Subject to the constraints

6x1+4x2+s1=7200

2x1+4x2+s2= 4000

X1,x2,s1,s2 ≥0

cj 100 80 0 0 Replacement ratio

c x b X1 X2 S1 S2
0 S1 7200 6 4 1 0 7200/6=1200
0 S2 4000 2 4 0 1 4000/2 =2000
zj 0 0 0 0
∆=cj-zj 100 80 0 0

Calculation of zj row For x1 (0x6)+(0x2)=0

For x2 (0x4)+(0x4)=0

For s1 (0x1)+(0x0)=0

For s2 (0x0)+(0x1)=0
Maximum positive ∆ value is 100 for the variable X1 .Hence key column is X1

Replacement ratio = b column/key column

Minimum positive replacement ratio is 1200 for the variable s1 .Hence key raw
is S1

Key element = 6 intersection of x1 and S1

Calculation of new values for second table

New values for key row

New values = old values/key element

Key row for the first table = S1

Key element for the first table=6

New values are 7200/6,6/6,4/6,1/6,0/6

That is 1200,1,2/3,1/6,0

New values for non key row

New values= old values –{corresponding key column value x new values of key
row

Non key row is S2. For S2 corresponding key column value is 2

New values

4000-(2x1200)=1600

2-(2x1)=0

4-(2x2/3)=8/3

0-(2x1/6)=-1/3

1-(2x0)=1
 Calculation of Zj

For x1 (100x1)+(0x0)=100

For x2 (100x2/3)+(0x8/3)=200/3

Fors1 (100x1/6)+(0x-1/3)=50/3

For s2 (100x0)+(0x1)=0

2nd simplex table

cj 100 80 0 0 Replacement ratio

c x b X1 X2 S1 S2
100 X1 1200 1 2/3 1/6 0 1800
0 S2 1600 0 8/3 -1/3 1 600
zj 100 200/3 50/3 0
∆=cj-zj 0 40/3 -50/3 0

1200/2/3

=1200*3/2

1600*3/8

Maximum ∆ = 40/3

Key column = x2

Minimum replacement ratio =600

Key row =S2

Key element= intersection of X2andS2 =8/3

Calculation of new values for third table

New values = old values/key element= 600,0,1,-1/8,3/8

These are the new values for X2 row

New values for non key row(X1)

1200-(2/3 x600)= 800

1-(2/3 x0)=1

2/3 – (2/3 x1)=0

 1/6-(2/3 x -1/8)=1/4

0-(2/3x3/8)=-1/4

Calculation of zj

For x1 (100x1)+(80x0)=100

For x2 (100x0+80x1)=80

For s1 (100x1/4)+(80x-1/8)=15

For s2 (100x-1/4)+(80x3/8)=5

cj 100 80 0 0
c x b X1 X2 S1 S2
100 X1 800 1 0 1/4 -1/4
80 X2 600 0 1 -1/8 3/8
zj 100 80 15 5
∆=cj-zj 0 0 -15 -5

All ∆ values are either 0 or negative. The solution is optimal

Max z = (100 x800)+(80x600)=128000

[Link] the following LPP by simplex method

Max z=4000x1+2000x2+5000x3

12x1+7x2+9x3≤1260

22x1+18x2+16x3≤19008

2x1+4x2+3x3≤396

X1,x2,x3≥0

Solution:

Max z = 4000x1+2000x2+5000x3+0s1+0s2+0s3

Subject to the constraints

12x1+7x2+9x3+s1=1260
22x1+18x2+16x3+s2=19008

2x1+4x2+3x3+s3 =396

cj 4000 2000 5000 0 0 0

c x b X1 X2 X3 S1 S2 S3 R.R
0 S1 1260 12 7 9 1 0 0 140
0 S2 19008 22 18 16 0 1 0 1188
0 S3 396 2 4 3 0 0 1 132
zj 0 0 0 0 0 0
∆=cj-zj 4000 2000 5000 0 0 0
Calculation of zj

For x1 (0x12)+(0x22)+(0x2)=0

For x2 (0x7)+(0x18)+(0x4)=0

For x3 ((0x9)+(0x16)+(0x3)=0

For s1 (0x1)+(0xx0)+(0x0)=0

For s2 (0x0)+(0x1)+(0x0)=0

For s3 (0x0)+(0x0)+(0x1)=0

Maximum ∆=5000

key column =x3

minimum replacement ratio =132

key row =s3

key element =3

calculation of 2nd table

new values of key row =old values/key element

=132 , 2/3 , 4/3 , 1 , 0, 0, 1/3

New values of non key row

New values= old values –{corresponding key column value x new values of key
row

For s1

1260-(9x132)= 72

12-(9x3/2)=6

7-(9x4/3)=-5

1-(9x0)=1

0-(9x0)=0

0-(9x1/3)=-3

For s2

19008-(16x132)=16896

22-(16x2/3)=34/3

18-(16x4/3)=-10/3

16-(16x1)=0

0-(16x0)=0

1-(16x0)=1

0-(16x1/3)=-16/3

Zj calculation

For x1 (0x6)+(0x34/3)+(5000x2/3)=10000/3

For x2 (0x-5)+(0x-10/3)+(5000x4/3)=20000/3

For x3 (0x0)+(0x0)+(5000x1)=5000

For s1 (0x1)+(0x0)+(5000x0)=0
For s2 (0x0)+(0x1)+(5000x0)=0

For s3 (0x-3)+(0x-16/3)+(5000x1/3)=5000/3

cj 4000 2000 5000 0 0 0

c x b X1 X2 X3 S1 S2 S3 R.R
0 S1 72 6 -5 0 1 0 -3 12
0 S2 16896 34/3 -10/3 0 0 1 -16/3 1490.8
5000 X3 132 2/3 4/3 1 0 0 1/3 198
zj 10000/3 20000/3 5000 0 0 5000/3
∆=cj- 2000/3 - 0 0 0 -
zj 14000/3 5000/3

Maximum value = 2000/3

Key column = x1

Minimum replacement ratio =12

Key row =s1

Key element=6

Calculation of third table

New values of key row = old values/key element

= 12 , 1 , -5/6, 0 , 1/6 , 0, -1/2

New values for non key row

New values= old values –{corresponding key column value x new values of key
row

For s2

16896-(34/3x12)=16760
34/3-(34/3 x1)=0

-10/3-(34/3 x -5/6)=55/9

0-(34/3 x 0)=0

0-(34/3 x 1/6)=-17/9

1-(34/3 x 0)=1

-16/3 – (34/3 x -1/2)=1/3

For x3

132-(2/3 x12)= 124

2/3 – (2/3 x 1)=0

4/3-(2/3 x -5/6)=17/9

1 –(2/3 x 0)=1

1/3 –(2/3 x -1/2)=2/3

Zj calculation

For x1 (4000x1)+(0x0)+(5000x0)=4000

For x2 (4000x -5/6)+(0x 55/9)+(5000 x 17/9)=55000/9

For x3 (4000x0)+(0x0)+(5000x1)=5000

For s1 (4000x1/6)+(0x -17/9)+(5000x -1/9)=2000/3

For s2 (4000x0)+(0x1)+(4000x0)=0

For s3 (4000 x -1/2)+(0 x 1/3) +(5000 x 2/3)=4000/3

cj 4000 2000 5000 0 0 0
c x b X1 X2 X3 S1 S2 S3
4000 X1 12 1 -5/6 0 1/6 0 -1/2
0 S2 16760 0 55/9 0 -17/9 1 1/3
5000 X3 124 0 17/9 1 -1/9 0 2/3
zj 4000 55000/9 5000 2000/3 0 4000/3
∆=cj-zj 0 - 0 - 0 -
37000/9 2000/3 4000/3
No positive ∆ values . the solution is optimal

Optimal profit = (4000x12)+(0x16760)+(5000x124)=668000