1.

Use the Simplex Method to solve the following LP Problem

Maximize Z = 6x1 + 8x2
Subject to constraints
5x1 + 10x2 ≤ 60
4x1 + 4x2 ≤ 40
And
x1 & x2 ≥ 0

Solution:

The Standard form of the above LP problem can be written as

Maximize Z = 6x1 + 8x2 + 0s1 + 0s2
Subject to
5x1 + 10x2 + s1 = 60
4x1 + 4x2 + s2 = 40
And
x1, x2, s1 & s2 ≥ 0
Where s1 & s2 are slack variables which are introduced to balance the constraints

Initial Simplex table Key Element

CBi Cj 6 8 0 0 Solution Ratio

Min
Basic x1 x2 s1 s2
Value
Variable
0 s1 5 10 1 0 60 60/10=6
0 s2 4 4 0 1 40 40/4=10
Key Row
zj 0 0 0 0
cj - z j 6 8 0 0

Key Column Max Value

2
Z j=∑ ( CB i ) ( aij )
i=1
Finding Zj
= 0*5 + 0*4 = 0
= 0*10 + 0*4 = 0
= 0*1 + 0*0 = 0
= 0*0 + 0*1 = 0

Finding Cj-Zj
= 6-0 = 6
=8–0=0
=0–0=0
=0–0=0
Optimality condition:
For Max: all cj-zj ≤ 0

Since we have Cj – Zj positive value, we have to do the iteration.

Key Element
Iteration: 1

CBi cj 6 8 0 0 Solution Ratio

Basic x1 x2 s1 s2
Variable
8 x2 1/2 1 1/10 0 6 6/(1/2) = Min
Value
12
0 s2 2 0 -2/5 1 16 16/2 = 8
Zj 4 8 4/5 0 Key Row
Cj - Zj 2 0 -4/5 0

Key Column Max Value

New Key Row: In order to find the new value, divide all the values by key element
= 5/10 = 1/2
= 10/10 = 1
=1/10 = 1/10
=0/10 = 0
=60/10 = 6

New Value = old value – (corr. Key column value * corr. Key row value) / key element

= 4 – (4*5)/ 10 = 4- (20/10) = 4 - 2 = 2
= 4 – (4*10)/10 = 4 - (40/10) = 4 - 4 = 0
= 0 – (4*1)/10 = 0 – (4/10) = 0 – (2/5) = -2/5
=1 – (4*0)/10 = 1- (0/10) = 1 – 0 = 1
= 40 – (4*60)/10 = 40 – (240/10) = 40 – 24 = 16

Finding Zj

Zj = 8*(1/2) + 0*2 = 4
= 8*1 + 0*0 = 8
=8*(1/10) + 0*(-2/5) = 8/10 = 4/5
= 8*0 + 0*1 = 0
Finding Cj – Zj
6-4 = 2
8–8=0
0 – (4/5) = (-4/5)
0–0=0

Now check for Optimality condition:

For Max: all cj-zj ≤ 0

Since we have Cj – Zj positive value, we have to do the iteration

Iteration: 2

CBi Cj 6 8 0 0 Solution Ratio

Basic x1 x2 s1 s2
Variable
8 x2 0 1 1/5 -1/4 2
6 x1 1 0 -1/5 1/2 8
Zj 6 8 2/5 1
Cj - Zj 0 0 -2/5 -1

New Key Row: In order to find the new value, divide all the values by key element
= 2/2 = 1
=0/2 = 0
= (-2/5)/2 = (-2/5)*(1/2) = -1/5
= 1/2 = 1/2
=16/2 = 8

New Value = old value – (corr. Key column value * corr. Key row value) / key element

= 1/2 – ((1/2*2)/2) = 1/2 – 1/2 = 0

= 1 – ((1/2*0)/2) = 1
= 1/10 – ((1/2*-2/5)/2 = 1/10 – ((-1/5)/2)) = 1/10 – (-1/10) = 2/10 = 1/5
= 0 – ((1/2*1)/2)) = 0 – (1/2 *1/2) = -1/4

Finding Zj

= 8*0+6*1 = 6
=8*1+6*0 = 8
=8*(1/5) + 6* (-1/5) = 8/5 – 6/5 = 2/5
= 8*(-1/4) + 6* (1/2) = -8/4 + 6/2 = -2 + 3 = 1

Finding Cj – Zj
 = 6-6 = 0
= 8-8 = 0
= 0 – (2/5) = -2/5
= 0 – 1 = -1

Now check for Optimality condition:

For Max: all cj-zj ≤ 0
For Min: all cj-zj ≥ 0

All the Cj – Zj values are ≤ 0, so no need for further iterations.

So the corresponding x1 & x2 values are the solutions

x1 = 8
x2 = 2

Max Z = 6x1 + 8x2 = 6*8 + 8*2 = 48 + 16 = 64

Max Z = 64

2. Use the Simplex Method to solve the following LP Problem

Maximize Z = 12x1 + 16x2
Subject to constraints
10x1 + 20x2 ≤ 120
8x1 + 8x2 ≤ 80
And
x1 & x2 ≥ 0

Solution:

The Standard form of the above LP problem can be written as

Maximize Z = 12x1 + 16x2 + 0s1 + 0s2
Subject to
10x1 + 20x2 + s1 = 120
8x1 + 8x2 + s2 = 80
And
x1, x2, s1 & s2 ≥ 0
Where s1 & s2 are slack variables which are introduced to balance the constraints

Initial Simplex table

CBi Cj 12 16 0 0 Key Element
Solution Ratio
Basic x1 x2 s1 s2 Min
Variable Value
0 s1 10 20 1 0 120 120/20 =
6
Key Row
0 s2 8 8 0 1 80 80/8 = 10
zj 0 0 0 0
cj - z j 12 16 0 0

Max Value Key Column

2
Z j=∑ ( CB i ) ( aij )
i=1
Finding Zj
= 0*10 + 0*8 = 0
= 0*20 + 0*8 = 0
= 0*1 + 0*0 = 0
= 0*0 + 0*1 = 0

Finding Cj – Zj
= 12 – 0 = 0
= 16 – 0 = 0
=0–0=0
=0–0=0

Now check for Optimality condition:

For Max: all cj-zj ≤ 0
For Min: all cj-zj ≥ 0
Key Element

All the Cj – Zj values are ≥ 0, so we need to do further iterations.

Iteration 1:

CBi Cj 12 16 0 0 Solution Ratio

Basic x1 x2 s1 s2
Variable Min
16 x2 1/2 1 1/20 0 6 6/(1/2)=12 Value
0 s2 4 0 -2/5 1 32 32/4 = 8
zj 8 16 4/5 0 Key Row
cj - z j 4 0 -4/5 0

Max Value Key Column

To find the new key row, divide all the values with key element

= 10/20 = 1/2
= 20/20 = 1
=1/20 = 1/20
= 0/20 = 0
=120/20 = 6

New Value = old value – (corr. Key column value * corr. Key row value) / key element

= 8 – ((8*10)/20) = 4
= 8 – (8*20)/20 = 8 – 8 = 0
= 0 – (8*1)/20 = 0 – 2/5 = -2/5
= 1 – (8*0)/20 = 1 – 0 = 1
= 80 – (8*120)/20 = 80 – 48 = 32

Finding Zj

= 16*(1/2) + 0*4= 8
= 16*1 + 0*0 = 16
= 16*(1/20) + 0*(-2/5) = 16/20 = 4/5
= 16*0 + 0*1 = 0

Finding Cj – Zj
= 12-8 = 4
= 16-16 = 0
= 0-4/5 = -4/5
= 0 -0 =0

Now check for Optimality condition:

For Max: all cj-zj ≤ 0

We have one Cj – Zj value (4) ≥ 0, so we need to do further iterations.

Iteration 2:

CBi Cj 12 16 0 0 Solution Ratio

Basic x1 x2 s1 s2
Variable Min
16 x2 0 1 1/10 -1/8 2 Value
12 x1 1 0 -1/10 1/4 8
zj 12 16 2/5 1
cj - z j 0 0 -2/5 -1
 To find the new key row, divide all the values with key element
= 4/4 = 1
= 0/4 = 0
= (-2/5) / 4 = (-2/5)* (¼) = -1/10
= 1/4
= 32/4 = 8

New Value = old value – (corr. Key column value * corr. Key row value) / key element
= 1/2 - (1/2*4) / 4 = 1/2 – (2/4) = ½ - ½ = 0
= 1 – (1/2*0)/4 = 1 – 0 = 1
=1/20 – (1/2 * -2/5) / 4 = 1/20 – (-1/5) / 4 = 1/20 – (-1/5 * ¼) = 1/20 + 1/20 = 2/20 = 1/10
= 0 – (1/2 * 1) / 4 = 0 – (½ * ¼) = 0 – 1/8 = -1/8
= 6 – (1/2 * 32) / 4 = 6 – (16/4) = 6 – 4 = 2

Finding Zj

= 16*0 + 12*1 = 12
= 16*1 + 12*0 = 16
= 16*1/10 + 12* (-1/10) = 1/10 * (16-12) = 1/10 * 4 = 4/10 = 2/5
= 16*(-1/8) + 12 * (1/4) = -2 + 3 = 1

Finding Cj – Zj

= 12-12 = 0
= 16 – 16 = 0
= 0 – 2/5 = -2/5
= 0 – 1 = -1

Now check for Optimality condition:

For Max: all cj-zj ≤ 0

All the Cj – Zj values are ≤ 0, so no need for further iterations.

So the corresponding x1 & x2 values are the solutions

X1 = 8
X2 = 2
Maximize Z = 12x1 + 16x2 = 12*8 + 16*2 = 96 + 32 = 128
Max Z = 128

3. Use the Simplex Method to solve the following LP Problem

Maximize Z = 2x1 + 5x2
Subject to constraints
1x1 + 4x2 ≤ 24
3x1 + x2 ≤ 21
X1 + x2 ≤ 9
And
x1 & x2 ≥ 0

Solution:

The Standard form of the above LP problem can be written as

Maximize Z = 2x1 + 5x2 + 0s1 + 0s2 + 0s3
Subject to constraints
1x1 + 4x2 + s1 = 24
3x1 + x2 +s2 = 21
X1 + x2 +s3 = 9
And
x1 , x2, s1, s2, s3 ≥ 0

Initial Simplex Method

CB Cj 2 5 0 0 0 Solution Ratio
Basic X1 X2 S1 S2 S3 Min
Variable Value
0 S1 1 4 1 0 0 24 24/4 =
6 Key Row
0 S2 3 1 0 1 0 21 21/1 =
21
0 S3 1 1 0 0 1 9 9/1 = 9
Zj 0 0 0 0 0
Cj – Zj 2 5 0 0 0

Max Value Key Column

Finding Zj

0*1 + 0*3 + 0*1 = 0

0*4 + 0*1 + 0*1 = 0
0*1 + 0*0 + 0*0 = 0
0*0 + 0*1 + 0*0 = 0
0*0 + 0*0 + 0*1 = 0

Finding Cj – Zj

2–0=2
5–0=5
0–0=0
0–0=0
0–0=0
Now check for Optimality condition:
For Max: all cj-zj ≤ 0

Since we have Cj – Zj positive value, we have to do the iteration

Iteration 1

CB Cj 2 5 0 0 0 Solution Ratio
Basic X1 X2 S1 S2 S3
Variable
5 X2 1/4 1 1/4 0 0 6 =6/(1/4)=24 Min
Value
0 S2 11/4 0 -1/4 1 0 15 =15/(11/4)=60/11=5.45
0 S3 3/4 0 -1/4 0 1 3 =3/(3/4) = 4
Zj 5/4 5 5/4 0 0 Key Row
Cj – Zj 3/4 0 -5/4 0 0

Max Value Key Column

To find the new key row, divide all the values with key element

1/4 = 1/4
4/4 = 1
1/4 = 1/4
0/4 = 0
0/4 = 0

New Value = old value – (corr. Key column value * corr. Key row value) / key element

S2 = 3 – (1*1)/4 = 3 – ¼ = 11/4
= 1 – (1*4)/4 = 1 – 1 = 0
= 0 – (1*1)/4 = -1/4
= 1 – (1*0)/4 = 1
= 0 – (1*0)/4 = 0
= 21 – (1*24)/4 = 21 – 6 = 15

S3 = 1 – (1*1)/4 = 1 – ¼ = ¾
= 1 – (1*4)/4 = 1 – 4/4 = 1 – 1 = 0
= 0 – (1*1)/4 = 0 – ¼ = -1/4
= 0 – (1*0)/4 = 0 – 0 = 0
= 1 – (1*0)/4 = 1
= 9 – (1*24)/4 = 9 – 6 = 3

Finding Zj
= 5* (1/4) = 5/4
= 5*1 = 5
= 5* 1/4 = 5/4
= 5*0 = 0
= 5*0 = 0

Finding Cj – Zj

= 2 – (5/4) = 3/5
=5–5=0
= 0 – (5/4) = -5/4
=0–0=0
=0–0=0
Now check for Optimality condition:
For Max: all cj-zj ≤ 0

Since we have Cj – Zj positive value, we have to do the iteration

Iteration 2
CB Cj 2 5 0 0 0 Solution Ratio
Basic X1 X2 S1 S2 S3
Variable
5 X2 0 1 1/3 0 -1/3 5
0 S2 0 0 2/3 1 -11/3 4
2 X1 1 0 -1/3 0 4/3 4
Zj 2 5 1 0 1
Cj – Zj 0 0 -1 0 -1

To find the new key row, divide all the values with key element

=(3/4) / (3/4) = 1
= 0/ (3/4) = 0
= (-1/4) / (3/4) = -1/4 * 4/3 = -1/3
= 0 / (3/4) = 0
= 1/(3/4) = 4/3
= 3/(3/4) = 4

New Value = old value – (corr. Key column value * corr. Key row value) / key element

X2 = ¼ - (1/4 * ¾) / ¾ = ¼ - (3/16 * 4/3) = ¼ - ¼ = 0

= 1 – (1/4*0)/3/4 = 1 – 0 = 1
= ¼ - (1/4 * (-1/4))/3/4 = -1/4 – (-1/16 * 4/3) = ¼ + 1/12 = 4/12 = 1/3
= 0 – (1/4*0) / ¾ = 0 – 0 = 0
=0 – ((1/4)*1) / ¾ = 0 – (¼ * 4/3) = -1/3
 = 6 – (1/4*3)/3/4 = 6 – (3/4* 4/3) = 6 – 1 = 5

S2 = 11/4 – (11/4 * ¾) / ¾ = 11/4 – (33/16 * 4/3) = 11/4 – 11/4 = 0

0 – (11/4*0)/ ¾ = 0 – 0 = 0
-1/4 – (11/4 * -1/4) / ¾ = -1/4 – (-11/16 * 4*3) = -1/4 + 11/12 = 8/12 = 2/3
1 – (11/4 *0)/ ¾ = 1 – 0 = 1
0 – (11/4*1)/3/4 = 0 – (11/4 * 4/3) = 0 – 11/3 = -11/3
15 – (11/4 *3)/3/4 = 15 – (33/4 * 4/3) = 15 – 11 = 4

Finding Zj

5*0 + 0*0 + 2*1 = 2

5*1 + 0*0 + 0*2 = 5
5*(1/3) + 0* (2/3) + 2* (-1/3) = 5/3 – 2/3 = 3/3 = 1
5*0 + 0*1 + 2*0 = 0
5*(-1/3) + 0*(-11/3) + 2* (4/5) = -5/3 + 8/3 = 3/3 = 1

Finding Cj – Zj

2–2=0
5–5=0
0 – 1 = -1
0–0= 0
0 – 1 = -1

Now check for Optimality condition:

For Max: all cj-zj ≤ 0

All the Cj – Zj values are ≤ 0, so no need for further iterations.

So the corresponding x1 & x2 values are the solutions

X1 = 4
X2 = 5
Maximize Z = 2x1 + 5x2

Z = 2*4 + 5*5
Z = 8 + 25
Z = 33

4. Use the Simplex Method to solve the following LP Problem

Maximize Z = 4x1 + 3x2
Subject to constraints
2x1 + x2 ≤ 1,000
x1 + x2 ≤ 800
x1 ≤ 400
 x2 ≤ 700
And
x1 & x2 ≥ 0

Solution
The Standard form of the above LP problem can be written as
Maximize Z = Z = 4x1 + 3x2+ 0s1 + 0s2+ 0s3+ 0s4
Subject to
2x1 + x2 + s1 = 1,000
x1 + x2 + s2 = 800
x1 + s3 = 400
x2 + s4 = 700

And
x1, x2, s1, s2, s3 & s4 ≥ 0
Where s1 & s2 are slack variables which are introduced to balance the constraints

Initial Simplex Method

CB Cj 4 3 0 0 0 Solutio Ratio
Basic X1 X2 S1 S2 S3 S4 n
Variable
0 S1 2 1 1 0 0 0 1,000 500
0 S2 1 1 0 1 0 0 800 800
0 S3 1 0 0 0 1 0 400 400
0 S4 0 1 0 0 0 1 700 Not
defined
Zj 0 0 0 0 0 0
Cj – Zj 4 3 0 0 0 0

Max Value Key Column

Now check for Optimality condition:

For Max: all cj-zj ≤ 0

Since we have Cj – Zj positive value, we have to do the iteration

Iteration1

CB Cj 4 3 0 0 0 0 Solutio Ratio
Min
Basic X1 X2 S1 S2 S3 S4 n
Value
Variable
0 S1 0 1 1 0 -2 0 200 200
0 S2 0 1 0 1 -1 0 400 400 Key Row
4 X1 1 0 0 0 1 0 400 ND
0 S4 0 1 0 0 0 1 700 700
Zj 4 0 0 0 4 0
Cj – Zj 0 3 0 0 -4 0

Max Value Key Column

To find the new key row, divide all the values with key element
1/1 = 1
0/1 = 0
0/1 = 0
0/1 = 0
1/1 = 1
0/1 = 0
400/1 = 400

New Value = old value – (corr. Key column value * corr. Key row value) / key element

S1= 2-(2*1)/1 = 2-2 = 0

= 1-(2*0)/1 = 1-0 = 1
= 1-(2*0)/1 = 1-0 = 1
=0-(2*0)/1 = 0-0 = 0
= 0-(2*1)/1 = 0-2 = -2
=0-(2*0)/1 = 0-0 = 0
=1,000 – (2*400)/1 = 1,000 – 800 = 200

S2 = 1-(1*1)/1 = 1-1 = 0
= 1-(1*0)/1 = 1-0 = 1
= 0-(1*0)/1 = 0-0 = 0
= 1-(1*0)/1 = 1-0 = 1
= 0-(1*1)/1 = 0-1 = -1
= 0-(1*0)/1 = 0-0 = 0
= 800-(1*400)/1 = 800-400 = 400

S4 = 0-(0*1)/1 = 0-0 = 0
= 1-(0*0)/1 = 1-0 = 1
= 0-(0*0)/1 = 0-0 = 0
= 0-(0*0)/1 = 0-0 = 0
=0-(0*1)/0 = 0-0 = 0
= 1-(0*0)/1 = 1-0 = 1
= 700-(0*400)/1 = 700 – 0 = 700

Now check for Optimality condition:

For Max: all cj-zj ≤ 0

Since we have Cj – Zj positive value, we have to do the iteration

Iteration 2

CB Cj 4 3 0 0 0 0 Solutio Ratio
Basic X1 X2 S1 S2 S3 S4 n Min of the
Variable +ve value
3 X2 0 1 1 0 -2 0 200 -100
0 S2 0 0 -1 1 1 0 200 200
4 X1 1 0 0 0 1 0 400 400 Key Row
0 S4 0 0 -1 0 2 1 500 250
Zj 4 3 3 0 -2 0
Cj – Zj 0 0 -3 0 2 0

Max Value Key Column

To find the new key row, divide all the values with key element

=0/1 = 0
=1/1 = 1
=1/1 = 1
=0/1 = 0
=-2/1 = -2
=0/1 = 0
=200/1 = 200

New Value = old value – (corr. Key column value * corr. Key row value) / key element

S2 = 0-(1*0)/1 = 0-0 = 0
= 1-(1*1)/1 = 1-1 = 0
=0-(1*1)/1 =0-1 = -1
= 1-(1*0)/1 = 1-0 = 1
= -1 – (1*-2)/1 = -1 – (-2) = -1+2 = 1
= 0-(1*0)/1 = 0-0=0
= 400 – (1*200)/1 = 400-200 = 200

X1 = 1-(0*0)/1 = 1-0 = 1
= 0-(0*1)/1 = 0-0 = 0
= 0-(0*1)/1 = 0-0 = 0
= 0-(0*0)/1 = 0-0 = 0
= 1-(0*-2)/1 = 1-0 = 1
= 0-(0*0)/1 = 0-0 = 0
= 400 – (0*200)/1 = 400 – 0 = 400
S4 = 0-(1*0)/1 = 0-0 = 0
= 1-(1*1)/1 = 1 – 1 = 0
=0-(1*1)/1 =0-1 = -1
= 0-(1*0)/1 = 0-0 = 0
= 0-(1*-2)/1 = 0+2 = 2
= 1-(1*0)/1 = 1-0 = 1
= 700- (1*200)/1 = 700 – 200 = 500

Now check for Optimality condition:

For Max: all cj-zj ≤ 0

Since we have Cj – Zj positive value, we have to do the iteration

Iteration 3

CB Cj 4 3 0 0 0 0 Solutio Ratio
Basic X1 X2 S1 S2 S3 S4 n
Variable
3 X2 0 1 -1 2 0 0 600
0 S3 0 0 -1 1 1 0 200
4 X1 1 0 1 -1 0 0 200
0 S4 0 0 1 -2 0 1 100
Zj 4 3 1 2 0 0
Cj – Zj 0 0 -1 -2 0 0

To find the new key row, divide all the values with key element

S3=0/1 = 0
=0/1 = 0
= - 1/1 = -1
=1/1 = 1
=1/1 = 1
=0/1 = 0
=200/1 = 200

New Value = old value – (corr. Key column value * corr. Key row value) / key element

X2 = 0-(-2*0)/1 = 0-0 = 0
= 1-(-2*0)/1 = 1-0 = 1
= 1-(-2*-1)/1 = 1-2 = -1
= 0-(-2*1)/1 = 0+2 = 2
=-2- (-2*1)/1 = -2+2 = 0
= 0-(-2*0)/1 = 0-0 = 0
= 200-(-2*200)/1 = 200+400 = 600
X1 = 1-(1*0)/1 = 1-0 = 1
= = 0-(1*0)/1 = 0-0 = 0
= 0-(1*-1)/1 = 0+1 = 1
= 0-(1*1)/1 = 0-1 = -1
= 1-(1*1)/1 = 1-1 = 0
= 0-(1*0)/1 = 0-0 = 0
= 400 – (1*200)/1 = 400 – 200 = 200

S4 = 0-(2*0)/1 = 0-0 = 0
= 0-(2*0)/1 = 0-0 = 0
= -1-(2*-1)/1 = -1+2 = 1
= 0-(2*1)/1 = 0-2 = -2
= 2-(2*1)/1 = 2-2 = 0
= 1-(2*0)/1 = 1-0 = 1
= 500 – (2*200)/1 = 500-400 = 100

Now check for Optimality condition:

For Max: all cj-zj ≤ 0

All the Cj – Zj values are ≤ 0, so no need for further iterations.

So the corresponding x1 & x2 values are the solutions

X1 = 200
X2 = 600
Maximize Z = 4x1 + 3x2

Z = 4*200 + 3*600
Z = 800 + 1800
Z = 2600