LINEAR

PROBLEM

PROGRAMMING (LPP)

Introducing a Slack, Surplus , Artificial, Variables:

Constraints

Adjustment in
Constraints

Add a slack
variable
=
Add a artificial
variable

Subtract a
surplus
variable and
add artificial
variable
Determine the new row as :

Maximization
Problem
0

Minimization
Problem
0

-M
0
-M

0
M

Number in new row = (Number in old row) [ ( Number above or

below key element) x ( Corresponding number in the row )]
or
New row element = old row element - ( Row element in the Key
column) x ( Corresponding replaced row element)

Example1. Use Simplex Method to solve LPP.

Max Z : 3x1 + 2x2
Subject to :

x1 + x2 4
X1 - x2 2
X1 , x2 0

Solution : Introducing the slack variables s1 and s2

Max Z = 3x1 + 2x2 + 0s1 + 0s2

Subject to ;

x1 + x2 + s1 =4
X1 - x2 + s2 = 2

X1 , x2 , s1 and s2 0
Simplex Table 1
Basis

X1

X2

S1

S2

bi

S1

S2

1*

-1

2
0
2

0
0
0

0
0
0

Cj
Zj
Cj Zj

3
0
3

bi/aij
4/1=4
2/1=2

Since Cj Zj 0, the current solution is not optimal.

R2(new) = R2(old)

1 (Key element) = ( 1 , -1 , 0 ,1 ,2)

R1 (new) = R1 (old) 1 x R2(new)

=11x1=0
= 1 1 x ( -1) =2
=11x0=1
=0 - 1 x 1 = - 1
=41x2=2
Simplex Table 2
Basis
S1

X1

X2

S1

S2

bi

2*

-1

bi/aij
2/2=

X1

-1

Cj
Zj
Cj Zj

3
3
o

2
-3
5

0
0
0

0
3
-3

1
2/1=-2
--

Since all Cj Zj 0 , the current solution is not optimal.

R1(new) = R1(old)

2 R1 = ( 0 , 1 , , -1/2 , 1 )

R2(new) = R2(old) - ( - 1 ) x R1 (new)

= 1 ( -1) x 0 = 1
= -1 (-1) x 1= 0
= 0 ( -1) x =
= 1- (-1) x ( -1/2)=
=2 ( -1) x 1 = 3
Simplex Table 3
Basis
X2
X1

X1

X2

S1

S2

bi

-1/2

1
3

2
3

0
1

1
0

1/2

Cj
Zj

3
3

2
2

0
5/2

Cj Zj

-5/2

1/2
0
1/2
-1/2

bi/aij

Since all Cj Zj 0, the solution is optimal. The solution is X1

= 3 , X2 = 1, Max Z =11
example2. Solve LPP by Simplex method.
Max Z = 3x1 + 2x2
Subject to :

4x1 + 3x2 12
4x1 + x2 8
4x1 x2 8

x1 , x2 0

Solution:
Introducing slack variable s1 , s2 , s3 , the equations
becomes
Max Z = 3x1 + 2x2 +0s1 + 0s2 + 0s3
Subject to :

4x1 + 3x2 +s1 =12

4x1 + x2 + s2 = 8
4x1 x2 + s3 =8

X1 , x2 , s1 , s2 ,s3 0
Simplex Table 1
X1

Basis
S1

S2

0
0

S3

Cj
Zj
Cj-Zj

S1

S2

S3

bi

bi/aij

12

4*

-1

12/4
=3
8/4=
2
8/4=
2

2
0
2

0
0
0

3
0
3

X2

0
0
0
0

1
0
0
0

Since Cj Zj 0 , the solution is not optimal.

R3 (new) = R3(old) 4 (Key element)

( 1 , -1/4 , 0/4 , 0 ,

, , 8/4=2)
R2(new) = R2(old) 4 x R3(new)
x R3 (new)

R1(new) = R1(old) 4

=4 4 x 1=0

=44x

1=0
=1- 4 x (-1/4)=2

=3 4

x(-1/4)= 4
=04x0=0

=1 4 x

0= 1
= 1 4 x 0=1

=0 4 x 0

=0
= 0 4 x 1/4 =-1

=04

x 1/4 =-1
=8 4 x 2 = 0

= 12 4

x2=4
Simplex Table 2
Basis
S1
S2

0
0

X1
0
0

X2
4

S1
1

S2
0

S3
-1

-1

bi
4
0

*
X1

-1/4

Cj
Zj

3
3

2
-3/4

0
0

0
0

1/4
0

bi/aij
4/4=
1
0/2=
0
2/(1/4)=
-8

Cj -ZJ

11/4

3/4
-3/4

Since Cj Zj 0 , This is not optimal solution.

R2(new) = R2(old) 2 (Key element)

(0, 1 , 0 , , -1/2 ,

0)
R3(new) = R3(old) ( -1/4) x R2(new)
R2(new)

R1(new) = R1(old) 4 x

= 1 (-1/4) x 0= 1

=0 4 x 0

=0
= -1/4 ( -1/4) x 1 =0

=4- 4x1

=0
= 0 (-1/4) x 0 = 0

=1 4 x 0

=0 (-1/4) x = 1/8

=0 4 x

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

= -1 4 x

= 2 (-1/4) x 0 = 2

=44x0

=4
Basis
S1
X2
X1

X1

X2

S1

2
3
Cj
Zj

0
1
3
3

1
0
2
2

0
0
0
0

S2
-2
1/2
1/8
0

S3

bi

1*

-1/2
1/8
0

0
2

Bi/aij
4/1=
4
--16

11/8
Cj - Zj

-5/8
5/8

-11/8

Since all Cj Zj 0 , the solution is not optimal.

Since Cj Zj 0 , this is not optimal solution.
R1(new) = R1(old) 1 ( Key element)

( 0 , 0 , 1 ,-2, 1 ,

4)
R2 (New) = R2(old) (-1/2) x R1(new)
x R1(new)

R3(new) = R3(old) 1/8

=0 (-1/2) x 0 =0

=1 1/8 x

= 1 (-1/2) x 0 =1

= 0 1/8 x

0= 1
0=0
= 0 (-1/2) x 1=

= 0 1/8

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

=1/8 1/8

= -1/2 (-1/2) x 1 = 0

= 1/8 1/8

x 1=0
= 0 (-1/2) x 4 = 2

= 2 1/8 x

4 = 3/2
Basis
S3
X2
X1

0
2
3
Cj
Zj

X1

X2

S1

0
0
1
3
3

0
1
0
2
2

1
1/2
-1/8
0
5/8

S2
-2
-1/2
3/8
0
1/8

S3
1
0
0
0
0

bi
4
2
3/2

Cj - Zj

-5/8

-1/8

Since Cj Zj 0, Therefore this is the optimal solution. The

solution is x1 = 3/2 , x2 = 2 , Z = 3 x 3/2 + 2 x 2 = 17/2.

Example 3 .Use the simplex method to solve the following LPP:

Maximise Z = 3x1+5x2 +4x3
Subject to the constraints,
2x1 + 3x2 8
2x2 + 5x3 10
3x1 + 2x2 + 4x3 15

( Rewa, Meerut ,

KU ,MSc 1998)
Solution:
Introducing non-negative slack variable s1, s2 , s3
to convert the given LPP in to standard form :
Maximize Z = 3x1 +5x2 +4x3+ 0 s1 +0s2 +0s3
Subject to the constrains:
2x1 +3x2 +s1 =8
2x2 +5x2 +s2 =10
3x1 +2x2 +4x3 +s3 =15
, s3 0

and x1 , x2 , x3 , s2 , s2

Simplex Table 1
Basis
S1

X1
0

X2

X3

S1

S2

S3

bi
8

bi/aij
8/3

S2
S3

3
0
3

5
0
5

4
0
4

Cj
Zj
Cj Zj

0
0
0

0
0
0

0
0
0

Since all Cj Zj 0 , (j= 1,2,3)

optimal.
R1(New)

10

10/2

15

15/2

the current solution is not

R1 (Old)

3 (key element)

( 8/3 , 2/3 , 3/3 , 0/3 , 1/3 . 0/3 ,

0/3)=( 8/3, 2/3, 1, 0,1/3, 0 ,0)
R2 (New) = R2 (old) 2 R1(New)
R1 (new)

R3 (new) = R3 (old) - 2

=10 2 x 8/3 =14/3

= 15 2 x

= 0 2 x 2/3 = -4/3

=3 - 2 x

8/3 = 20/3
2/3 =5/3
=22x1=0

=22

=52x0=5

=4 2

x 1 =0
x0=0
= 0 -2 x 1/3 = -2/3

=02

x 1/3= - 2/3
= 1 - 2 x 0 =1
2 x 0 =0

=0

=0 -2x0=0

=1

2x0=1
Simplex Table 2
Basi
s
X2
S2
S3

5
0
0
Cj
Zj
Cj
Zj

X1

X2

X3

2/3

4/3
5/3
3
10/3
1/3

0
0
5
5
0

S1

1/3
5*
2/3
4
-2/3
4
0
0
5/3
4
-5/3

S2
0

S3

bi

8/3

0
0

0
0

14/3
29/3

bi/aij
--(14/3)/
5
(29/3)/
4

Since Cj Zj 0 , the current solution is not optimal.

R2 (new) = R2 (old) 5 (key element) = ( 14/15 , - 4/15 , 0 , 1 ,
-2/15 , 1/5 , 0 )
R3 (new) = R3 (old) - 4R2 (new)
29/3 4 x 14/15 = 89/15
5/3 4 x (-4/15) = 41/15
0 4 x 0 =0
4 4 x 1 =0
- 2/3 4 x ( -2/15) = - 2/15
0 4 x 1/5 = - 4/5
14x0=0

Simplex Table 3
Basis

X1

X2

X3

S3

0
Cj
Zj
Cj-Zj

2/3
-4/15
41/1
5
3
34/1
5
11/1
5

X2

X3

S1

S2

S3

bi

8/3

1/5

2/15

-4/5

4/5

1/3
-2/15

17/1
5
17/1
5

R1(new) = R1(old) - 2/3 R3(new)

4/15) R3 (new)
= 8/3 2/3 x 89/3 =50/41

-4/5

bi/aij
4

14/1
5
89/1
5

---

2.17

R2(new) = R2(old) - (= 14/15 + 4/15

SS
= 2/3 - 2/3 x 1 =0
4/15 1 =0
= 1 2/3 x 0 = 1

=- 4/5 +
= 0 + 4/15 x

0 =0
= 0 2/3 x 0 = 0
0 =1
= 1/3 2/3 x (-2/41) =15/41
x (-2/41) = 6/41

= 1 + 4/15 x
= - 2/15 + 4/15

= 0 - 2/3 x (-2/42) = 8/41

( -12/41) = 5/41

= 1/5 + 4/5 x

= 0 2/3 x 15/41 = -10/41

15/41 = 4/41

0 + 4/15 x

Simplex Table 4
Basis
X2
X3
X1

5
4
3
Cj
Zj
Cj-Zj

X1
0
0
1
3
3
0

X2
1

X3
0

S1
S2
15/41 8/41

0
0

1
0

-6/41
-2/41

5
5
0

4
4
0

S3

Bi

10/41 50/41
4/41
15/41

5/41
12/41
0
0
0
45/41 24/41 11/41
45/41 24/41 11/41

All Cj-Zj 0 for non basic variables.The optimal solution is

x1=89/41 , x2 =50/41 , x3 = 62/41 and optimal value of Z
=765/41.

TWO

PHASE

METHOD

In such cases three cases arises :

i) Max Z* < 0 and an artificial variable A1 , A2 etc appears
in the optimum basis at positive level then LPP does not posses
any feasible solution.
ii) Max Z* = 0 and at least one artificial variable appears in the
optimum basis at zero level then we will go to phase II.

iii) Max Z * = 0 and no artificial variable appears in the optimum

basis then we will go to the phase II.

Example 1.

Minimise

Z = X1 + X2

Subject to

2X1 + X2 4
X1 + 7 X2 7

Where

X1, X2 0.

Solution : We introduce surplus and artificial variables to convert

the inequalities into equalities and assign 0 coefficient to basic
and surplus variables and 1 coefficient to artificial variables in
Phase 1 is given below,
Minimize

Z*

Subject to

= 0X1 + 0X2 +0S1 +0S2 +1A1 + 1A2

2X1 + X2 S1 +A1 =4
X1 + 7X2 S2 + A2 =7

Where X1 , X2 , S1 , S2 , A1, A2 0
Phase 1
Simplex Table I
Basis
A1
A2

X1
2

X2
1

S1
-1

S2
0

A1
1

7*

-1

Cj

A2
1

bi
4

bi/aij
4/1=
4
7/7=
1

+1
Zj
Cj
Zj

3
-3

8
-8

-1
1

-1
1

+1

1
0

1
0

Entering variable X2 and leaving variable A2.

Simplex Table 2
Basis

X1

A1

X2

0
Cj
Zj
Cj
Zj

13/7
*
1/7
0
13/7
-13/7

X2

S1

S2

A1

bi

-1

1/7

bi/aij
21/1
3

1
0
0

0
0
-1

-1/7
0
1/7

0
1
1

-1/7

Simplex Table 3
Basis
X1
X2

0
0

X1
1
0

X2
0
1

S1

S2

-7/13

1/13

1/13

-14/9
1
0
0
0

bi
21/13

bi/aij
21/13

10/13 10/13

Cj
0
0
0
Zj
0
0
0
Cj
0
0
0
Zj
Since all the values in Cj Zj row are zero and none of the
Artificial Variable is present in basic variable, so we in Phase II.
Phase II

Simplex Table 4
Basis

X1

X2

X1

X2

Cj
Zj

1
1

1
1

Cj Zj

S1
-7/13

S2
1/13

1/13
0

-14/91
0

-6/13

-7/91

6/13

7/13[

bi
21/13
10/13

Since Cj Zj row has 0 or +ve value so we are having optimum

solution.
X1= 21/13, X2= 10/13 , Z = 31/13.
Example 2.

Minimize

Subject to

Z = 5X1 + 6X2
2X1 + 5X2 1500
3X1 + X2 1200

Where

X1, X2 0

Solution;
We introduce surplus and artificial variable to convert
the inequalities to equalities and assign 1 coefficient to artificial
and 0 coefficient variables and surplus variables in Phase I
Minimize
+A2
Subject to

Z * =0X1 + 0X2 +0S1 + 0S2 +A1

2X1 + 5X2 S1 + A1 =1500
3X1 + X2 - S2 + A2 = 1200

Where

X1, X2, A1, A2 0

Phase I
Simplex table 1
Basi
s
A1

X1
2

A2

Cj
Zj
CjZj

0
5
-5

S1

S2

-1

1
0
6
-6

X2
5*

A1

A2

-1

0
-1
1

0
-1
1

1
1
0

1
1
0

bi
150
0
120
0

bi/aij
1500/5=3
00
1200/1=1
200

Entering variable is X2 and leaving variable is A1 and key

element is -6
Simplex Table 2
Basis
X2

A2

1
Cj
Zj
Cj Zj

X1
2/5
13/5*
0
13/5
-13/5

X2
1
0
0
0
0

S1
-1/5
1/5
0
1/5
-1/5

S2
0

A2
0

-1

0
-1

1
1

bi
300
900

bi/aij
1500/2=
750
4500/13

Entering variable X1 and leaving variable A2

Simplex Table 3
Basis
X2

X1
0

X2
1

S1
-3/13

S2
2/13

bi

X1

Cj
Zj
Cj Zj

0
0
0

1/13

0
0
0

0
0
0

-5/13

2100/1
3
4500/1
3

0
0
0

Since all the values of Cj Zj is 0 and none of artificial variable is

present in the basic variable , so we enter Phase II
Phase II
Simplex Table 4
Basis
X1

X2

5
Cj
Zj
Cj - Zj

X1 = 4500/13 ,

X1
0

X2
1

S1
-3/13

1/13

5
5
0

6
6
0

X2= 2100/13,

0
-1
1

S2
bi
2/13 2100/1
3
-5/13 4500/1
3
0
-1
1

Z = 2700.

Example 3. Solve the following linear programming problem

using Two phase method;
Minimize
Subject to

Z * = 2x1 + X2
5X1 + 10 X2 X3 =8
X1 + X2 + X4 =1

X1, X2, X3, X4, 0

Solution ;

Phase I

Minimize

Z = 0X1 + 0X2 +0X3 + 0X4 + A1 + A2

5X1 + 10X2 X3 + A1 =8
X1 + X2 + X3 + A2 =1
Simplex Table 1

Basi
s
A1

X1
1

A2

Cj
Zj

0
6

Cj Zj

-6

X2
10*
1

X3
-1
0

0
11
-11

X4

A2

bi

bi/aij

8/10=
0.8
1/1=1

A1
0

0
-1

0
-1

1
1

1
1

Simplex Table 2
Basis
X2

X1
0

A2

1
Cj
Zj
Cj
Zj

1/2
1/2

X2
1
0

0
1/2

0
0

-1/2

X3
-1/10
1/10
0
1/10

X4
0

A2
0

-1

0
1

1
1

-1

1/10

Simplex Table 3
Basis
X2

X1
0

1/2

X2
1

X3
-1/10

X4
0

bi
4/5
1/5

bi/aij
1/5

X4

0
Cj
Zj
Cj Zj

1/2

0
0
0

0
0
0

1/10
0
0
0

0
0
0

Since all values are either 0 or ve. We proceed to Phase II

Phase II

Simplex Table 4
Basis
X2
X4

1
0
Cj
Zj

X1
1/2
1/2
2
1/2

Cj Zj

X2
1
0
-1
1

3/2

-2

Since

X3
-1/10
1/10
0
-1/10
1/10

X2 = 4/5 , X4 = 1/5,

Example 5.

Min

Subject to

= X1 -2X2 3X3

-2X1 + X2 + 3X3 = 2
2X2 + 3X3 + 4X3 =1
X1 , X2 , X3 , 0

Solution :
Min
Subject to

Phase I
Z* = 0X1 +0X2 +OX3 + A1 +A2
-2X1 +X2 + 3X3 +A1 =2

X4
0
1
0
0
0

Z =4/5

bi
4/5
1/5

2X1 + 3X2 + 4X3 +A2 =1

X1 , X2 ,X3 ,A1 , A2 0
Simplex Table 1
Basis
A1
A2

X1
1
1
Cj
Zj
Cj
Zj

X2

-2
2
0
0
0

1
3
0
4
-4

X3
3
4*
0
7
-7

A1

A2

bi

1
0
1
1
0

0
1
1
1
0

2
1

bi/aij
2/3

Simplex Table 2
X1

Basis
A1
X3

X2

-7/2

0
Cj
Zj
Cj
Zj

1/2
0
-7/2
7/2

-5/4
3/4
0
-5/4
5/4

X3

A1

bi

5/4

1
0
0
0

0
1
1
0

1/4

Since all the values is equal to 0 or +ve. But the artificial

variable is present as basic variable. Thus above problem has got
infeasible solution.
Example 6.
Subject to

Max

Z = 10X1 +20X2
2X1 +5X2 50
4X1 + X2 28
X1 , X2 , 0
Phase I

Solution;

Max Z *=
Subject to

0X1 + 0X2 + 0S1 +0S2 + A1

2X1 +5X2 - S1 +A1 =50

4X1 +X2 + S2

=28

Simplex Table 1
Basis
A1
S2

X1
1
0
Cj
Zj
Cj
Zj

2
4
0
2
-2

X2

S1

S2

A1

bi

5
1
0
5
-5

-1
0
0
-1
1

0
1
0
0
0

1
0
1
1
0

50
28

bi/aij

So it is unbounded solution.
BIG M Method ( PENALITY METHOD)
Example 7.

Use the penalty ( Big M) method to solve the LPP.

Solution;

Minimize

Subject to

Z = 5X1 + 3X2
2X1 +4 X2 12,
2X1 + 2X2 = 10,
5X1 +2 X2 10,

X1 , X2,

0
Solution; By introducing slack variable S1 and artificial variable
A1 and A2 in the constraints of given LP problem;
Minimize
Subject to

Z = 5X1 +3x2 +0S1 +0S2 +MA1 + MA2

2X1 + 4X2 + S1 =12
2X1 +2X2+ A1 =10

5X1 + 2X2 S2 +A2 =10

X1 , X2 , S1 , S2, A1, A2 0
Simplex Table 1
X1

X2

S1

S2

A1

A2

bi

12

Basi
s
S1

A1

10

A2

5*

-1

10

0
0
0

0
-M
M

M
M
0

M
M
0

Cj
Zj
Cj
Zj

5
3
7M
4M
5-7M 3-4M

bi/aij
12/2
=6
10/2
=5
10/5
=2

Simple Table 2
Basis
S1
A1
X1

X1
0

M
5
Cj
Zj

0
1
5
5

Cj Z
j

X2
16/5*
6/5
2/5
3
6M/5
+2
-6M /5
+1

S1
1

S2
2/5

A1
0

bi
8

bi/aij
5/2

0
0
0
0

2/5
-1/5
0
2M/5
1
-2M/5
+1

1
0
M
M

6
2

5
5

bi/aij

Simplex Table 3
Basis
X2

X1

X2

S1

S2

A1

bi

1/8

5/2

40

A1
X1

M
5
Cj
Zj

Cj - Zj

0
1
5
5

0
0
3
3

5/16
-3/8
-1/8
0
-3M/8
+5/1
6
3M/8

5/16

1/4
-1/4
0
M/4
-7/8

1
0
M
M

-M/4
+7/8

3
1

12

Simplex Table 4
Basis
X2
S2
X1

3
0
5
Cj
Zj
Cj Zj

X1
0
0
1
5
5
0

X2
1
0
0
3
3
0

S1
1/2
-3/2
-1/2
0
-1
1

S2
0
1
0
0
0
0

bi
1
12
4

bi/aij

Since all Cj Zj 0. Thus an optimal solution is reached,

X1 = 4 , X2 = 1, S1 = 0 , S2= 12 , Z = 23.
Example 8 .
Maximize
Subject to

Use Penalty Method ( Big M ) to solve LPP.

Z = X1 + 2X2 +3X3 X4
X1 + 2X2 +3X3 = 15
2X1 + X2 + 5X3 =20
X1 + 2X2 +X3 + X4 =10

X1 , X2 , X3 ,X4 0
1995, AMIE,2004 )

( Calicut, Bangalore ,

Solution ; Since all constraints of the given LPP are equations,

therefore we should add only artificial variable A1 and A2 in the
constraints.
Maximize

Z = X1 + 2X2 + 3X3 X4 MA1 MA2

MA3
Subject to

X1 + 2X2 + 3X3 + A1 = 15
2X1 +X2 +5X3 +A2 =20
X1 + 2X2 +X3 + X4 + A3 =10

And

X1 , X2 , X3 , X4 . A1 , A2 , A3 0
Simplex Table 1

Basis
A1
A2
A3

X1
-M
-M
-M
Cj

X2
2

1
2

X3
3
5*

-4M

-5M

-9M

5M+
2

9M+
3

Zj
Cj 4M+
Zj
1

X4
A1
0
1
0
0
1
0
-1
-M
-1
+M

A2
0

1
0

-M

-M

-M

-M

A3
0

bi bi/aij
15/3=
5
20/5=
4
10/1=
10

15
20
10

-M
-M
0

Simplex Table 2
Basi
s
A1

-M
3

X1

X2

-1/5
2/5

7/5

X3
0

X4
0

A1
1

A3
0

1/5

bi
3

bi/aij
15/7

20

X3
A3

3/5

9/5

-1

-M

-M

(62M)/5
(1+2M)
/5

(316M)/5
(7+16M
)/5

-M
Cj
Zj
Cj Zj

-M

10/3

-M

-M
0

-1+
M

Simplex Table 3
X1

Basis
X2

X3

A3

-M
Cj
Zj
Cj- Zj

X2
1

-1/7

3/7
6/7
1
(76M)/7
6M/7

X3

X4

A3

1*

-1
-M

-M
-M

2
2

3
3

-1
+M

bi
15/7
25/7

bi/aij
-----

15/7

15/7

bi/aij

Simplex Table 4
Basis
X2
X3

2
3

X4

-1
Cj
Zj

X1

X2

X3

X4

bi

-1/7
3/7

1
0

0
1

0
0

15/7

6/7*

1
1/7

2
2

3
3

-1
1

25/7
15/7

-15
25/7
5/2

Cj - Zj

6/7

Simplex Table 5
Basis
X2
X3
X1

2
3
1
Cj
Zj
Cj Zj

X1
0
0
1
1
1
0

X2
1
0
0
2
2
0

X3
0
1
0
3
3
0

X4
1/6
-1/2
7/6
-1
0
-1

bi
5/2
5/2
5/2

Since Cj Zj 0, therefore the optimal basic feasible solution

has been obtained.
The solution X1=5/2, X2 =5/2, X3 = 5/2 , X4 =0
Also A1 = A2 = A3 =0 and

Z = 15.

Example 9.
An Air Force is experimenting with three types of
bombs P , Q and R in which three kinds of explosives, viz, A , B
and C will be used. Taking the various factor in to account, it has
been decided to use the maximum 600 kg of explosive A, at least
480 kg of explosive B and exactly 540 kg of explosive C. Bomb P
requires 3,2,2 kg , bomb Q requires 1, 4 , 3 kg and bomb R
requires 4, 2 , 3 kg of explosives A , B and C respectively. Bomb P
is estimated to give the equivalent of a 2 ton explosion, bomb Q ,
a 3 ton explosion and bomb R , a 4 ton explosion respectively.
Under what production schedule can the Air Force make the
biggest bang ?
Solution :
Let X1 , X2 and X3 be the number of bombs of type
P , Q and R to be experimented, respectively.
Then the LPP model for the problem is :
Maximize

Z = 2X1 + 3X2 + 4X3

Subject to

3X1 + X2 + 4X3 600

2X1 + 4X2 + 2X3 480
2X1 + 3X2 +3X3 = 540

And X1 , X2 , X3 0
Introducing slack , surplus and artificial variables , to covert the
LPP as :
Maximize

Z = 2X1 + 3X2 +4X3 +0S1 +0S2 MA1 -

MA2
Subject to

3X1 +X2 +4X3 +S1 =600

2X1 +4X2 +2X3 S2 + A1 =480
2X1 + 3X2 +3X3 +A2 =540

AND X1 , X2 , X3 S1 , S2 ,A1 , A2 0
Simplex Table 1
Basi
s
S1
A1
A2

0
-M

X1

X2

-M

Cj
Zj

2
-4M

Cj
Zj

2+4
M

X3

S1

S2

A1

A2

-1

4*
3

-7M
3+7
M

-5M
4+5
M

0
0

0
M

-M
-M

-M
-M

-M

Simplex Table 2

bi
600

bi/ai
j

600/
1
480 480/
4
540 540/
3

Basi
s
S1
X2
A1

X1

X2
0

5/2

1/2
1/3

-M
Cj
Zj
Cj Zj

X3
7/2

1/2

3/2 *

3/2M/2
+M
/2

3/23M/2
5/2+3M
/2

S1
1

S2

A2

1/4

-1/4

0
0

3/4

0
1

bi bi/ai
j
480
120
180

960/
7
240
120

-M

0 -3/4-M
3M/4
0 +3M
0
/4

Simplex Table 3
Basis
S1
X2
X3

0
3
4
Cj
Zj
Cj
Zj

X1

X2

X3

S1

4/3

1/3

2
7/3

3
3

4
4

0
0

1/3

-1/3

S2
-3/2
-1/2
1/2
0

bi

bi/aij

60
60
120

1/2
-1/2

All the Cj Zj 0 and artificial variable A1 and A2 have been

reduced to zero. The optimal solution is ;
X1 = 0 bombs of type P , X2 = 60 bombs of type Q, X3 =
120 bombs of type R

Largest benefit Z = 660.

Tie for Entering Basic Variable ( Key Column)

A situation may arise at any iteration (stage) when two or more
columns may have exactly the same Cj Zj value ( positive or
negative depending upon the type of LPP).
I)

If there is a tie between two decision variable , then the

selection can be made arbitrarily.
II)
If there is a tie between a decision variable and a slack
( or surplus) variable, then select the decision variable to
enter into basis first.
III) If there is a tie between two slack (or surplus) variables,
then the selection can be made arbitrarily.
Tie for Leaving Basic Variable (Key Row )
--- Degeneracy
While solving an LPP a situation may arise in which there is a tie
between two or more basic variables for leaving the bais i.e. the
minimum ratio to identify the basic variable to leave the basis is
not unique or in which values of one or more basic variables in
the solution values column (Xb) becomes equal to zero. This
causes the problem of Degeneracy.

Remark : When there is a tie between a slack and artificial

variable to have the basis, the performance should be given to
the artificial variable for leaving the basis.
Example .

Solve the following LPP

Maximize
Z = 3X1 + 9X2
Subject to
X1 + 4X2 8
X1 + 2X2 4
And
X1 , X2 0.

Solution:
Adding slack variables S1 and S2 to the constraints,
the problem can be expressed as
Maximise Z = 3X1 + 9X2 +0S1 +0S2
Subject to
X1 + 4X2 + S1 =8
X1 + 2 X2 + S2 =4
And X1 , X2 , S1, S2, 0.
X1

Basis
S1
S2

0
0
Cj
Zj
Cj - Zj

S1

1
3
0
3

2*
9
0
9

0
0
0
0

1
0
0
0

X2 Column
Key
Column
4
2

Row
S1
S2
i.

X2

S2

bi

bi/aij
8/4=2
4/2=2

Column
S1

S2

1
0

0
1

Divide the coefficient of slack variables S1 and S2 by the

corresponding elements in the key column as
Row
S1
S2

Key
Column
4
2

S1
=1/4
0/2 = 0

S2
0/1 = 0
=1/2

Comparing the ratio of Step (i) from left to right

columnwise , the minimum ratio i.e 0/2 =0 occures in the S2-row.
Thus , variable S2 is selected to leave the basis. The new solution
is as;

Basis
S1
X2

0
9
Cj
Zj
Cj - Zj

X1
-1
1/2
3
9/2
-3/2

X2
0
1
9
9
0

S1
1
0
0
o
0

S2
-2
1/2
0
9/2
-9/2

Since all Cj Zj 0. Hence , an optimal solution is reached.

The solution is ;
X1 = 0, X2 = 2 and Max Z = 18.
Type Of Linear Programming Solutions
A.

Alternative ( Multiple) Optimal Solutions

Example 9.

Solve the following LPP

Maximize

Subject to

Z = 8X1 4X2

4X1 + 5X2 20
-2X1 + 3 X2 -23
X1 0, X2 unrestricted in sign.

Solution :
As mentioned earlier , the twin necessary
conditions for the application of the simplex algorithm are that
the variable involved abd bi,s in the given problem should all be
non-negative. In case of a negative bi, the inequality/ equation is
multiplied by -1 , while a variable unrestricted in sign is replaced
by the difference of two non-negative variables. For the given
problems, we multiply the second of the constraints by -1 and
replace X2 = X3 X4. This yields the following problem:
Maximize

Z = 8X1 4(X3 X3)= 8X1

4X3 +4X4
Subject to

4X1 5X3 5 X4 20

X1 3X3 +3 X4 23
X1 , X3 , X4 0
After introducing slack variable the problem becomes;
Maximize

Z = 8 X1 4X3 + 4X4 +0S1 +0S2

Subject to

4X1 + 5X3 5 X4 + S1 = 20
X1 3X3 + 3X4 +S2 = 23
X1 , X3 , X4 ,S1 , S2 0
Simplex Table 1

Basis
S1
S2

0
0
Cj
Zj
Cj - Zj

X1

X3

X4

4*
1
8
0
8

5
-3
-4
0
-4

-5
3
4
0
4

X1

X3

X4

Basis
X1

S2

Cj
Zj
Cj
Zj

S1

S2

1
0
20
0
1
23
0
0
0
0
0
0
Simplex Table 2
S1

-5/4
1/4
17/4
-1/4
-17/4 *
-4
4
0
10
-10
2
-14
14
-2

bi/aij
5
23

S2

bi

bi/aij

-4

5/4

8
8
0

bi

18

72/17

0
0
0

Simplex Table 3

X1

X3

X4

S1

S2

bi

Basis
X1
X4

3/17

-1

-1/17

Cj
Zj

8
8

-4
-4

4
4

0
20/17

5/17
4/17
0

175/1
7
72/17

56/17

Cj 0
0
0
-20/17 -56/17
Zj
The optimal solution is X1 = 175/17, X2 = X3 X4 = ( 0
72/17) = -72/17
And the objective function value = ( 8 x 175/17) 9 4 x [72/17]) = 1688/17