Ch 3: Linear Programming :Simplex

Method

By Mohamed Cherif

1
OR Ch 3: Linear Programming: Simplex Method
Exercise 1

A factory manufactures two products F and G

on three machines A, B, and C. Product F
requires 10 hours of machine A and 5 hours of
machine B a one our of machine C. The
requirement of product G is 6 hours, 10 hours
and 2 hours of machine A, B, and C
respectively. The profit contribution of
products F and G are Rs. 23/– per unit and Rs.
32 /– per unit respectively. In the coming
planning period the available capacity of
machines A, B, and C are 2500 hours, 2000
hours and 500 hours respectively. Find the
optimal product mix for maximizing the profit.

2
OR Ch 3: Linear Programming: Simplex Method
Solution

1. Decision Variables
X= number of produced product F
Y= number of produced product G

Products Capacity in
Constraints
F (X) G (Y) Hours
A 10 6 2500
B 5 10 2000
C 1 2 500
Profit 23 32 ----

3
OR Ch 3: Linear Programming: Simplex Method
2. Objective Function

Maximize Z = 23 X + 32 Y
Subject to
10 X + 6Y ≤ 2500
5 X + 10Y ≤ 2000
X + 2Y ≤ 500
X,Y ≥ 0 Non-Negativity Constraint

4
OR Ch 3: Linear Programming: Simplex Method
Expressed in equation form

Maximize 𝑍 −23 X − 32 Y − 0𝑆1 − 0𝑆2 − 0𝑆3 = 0

Subject to
0𝑍 + 10 X + 6Y + 𝑆1 + 0𝑆2 + 0𝑆3 = 2500
0𝑍 + 5 X + 10Y + 0𝑆1 + 𝑆2 + 0𝑆3 =2000
0𝑍 + X + 2Y + 0𝑆1 + 0𝑆2 + 𝑆3 =500
X,Y,𝑆1 , 𝑆2 , 𝑆3 ≥ 0
The above data is entered in a table known as simplex table (or tableau). There are many
versions of table but in this book only one type is used.

5
OR Ch 3: Linear Programming: Simplex Method
Table 1

Basic 𝑍 X Y 𝑆1 𝑆2 𝑆3 Solution

𝑍 1 −23 −32 0 0 0 0 𝑍 − 𝑟𝑜𝑤

𝑆1 0 10 6 1 0 0 2500 𝑆1 − 𝑟𝑜𝑤

𝑆2 0 5 10 0 1 0 2000 𝑆2 − 𝑟𝑜𝑤

𝑆3 − 𝑟𝑜𝑤
𝑆3 0 1 2 0 0 1 500

6
OR Ch 3: Linear Programming: Simplex Method
Ratio for leaving Variable

Ratio (or
Basic Entering Y Solution
intercept)
𝑆1 6 2500 2500/6 =417

𝑆2 10 2000 2000/10=200

𝑆3 2 500 500/2=250

Conclusion Y enter at level 200 and 𝑺𝟐 leave at level 0

7
OR Ch 3: Linear Programming: Simplex Method
 Table 2
Enter

Basic 𝑍 X Y 𝑆1 𝑆2 𝑆3 Solution

𝑍 1 −23 −32 0 0 0 0 𝑍 − 𝑟𝑜𝑤

𝑆1 0 10 6 1 0 0 2500 𝑆1 − 𝑟𝑜𝑤

Leave 𝑆2 0 5 10 0 1 0 2000 𝑆2 − 𝑟𝑜𝑤 Pivot

Row
𝑆3 − 𝑟𝑜𝑤
𝑆3 0 1 2 0 0 1 500

Pivot
Column
8
OR Ch 3: Linear Programming: Simplex Method
 The Gauss-Jordan
computations

Pivot row All other rows,

including z

Replace the leaving variable

New row = (Current row) – (Pivot column
in the Basic column with the
coefficient) × (New pivot row)
entering variable.

New pivot row =

Current pivot row /
Pivot element

9
OR Ch 3: Linear Programming: Simplex Method
1. Replace 𝑺𝟐 in the Basic column with 𝒀

𝑁𝑒𝑤 𝑌 − 𝑅𝑜𝑤 = Current 𝑆2 − 𝑟𝑜𝑤 ÷ 10

1
0 5 10 0 1 0 2000 = 0 0.5 1 0 0.1 0 200
10

2. 𝑵𝒆𝒘 𝒁 − 𝑹𝒐𝒘 = Current 𝒁 − −𝟑𝟐 𝑵𝒆𝒘 𝒀 − 𝑹𝒐𝒘

= 1 − 23 − 32 0 0 0 0 − −𝟑𝟐 0 0.5 1 0 0.1 0 200
= 1 − 23 − 32 0 0 0 0 − 0 − 16 − 32 0 − 3. 𝟐 0 − 𝟔𝟒𝟎𝟎
= 1 − 7 0 0 3.2 0 6400

10
OR Ch 3: Linear Programming: Simplex Method
3. 𝑵𝒆𝒘𝑆1 − 𝑟𝑜𝑤 = Current𝑆1 − 𝑟𝑜𝑤 − −𝟑𝟐 𝑵𝒆𝒘 𝒀 − 𝑹𝒐𝒘
= 0 10 6 1 0 0 2500 − 𝟔 0 0.5 1 0 0.1 0 200
= 0 10 6 1 0 0 2500 − 0 3 6 0 0.6 0 𝟏𝟐𝟎𝟎
= 0 7 0 1 − 0.6 0 1300

4. 𝑵𝒆𝒘𝑆𝟑 − 𝑟𝑜𝑤 = Current𝑆𝟑 − 𝑟𝑜𝑤 − −𝟑𝟐 𝑵𝒆𝒘 𝒀 − 𝑹𝒐𝒘

= 0 1 2 0 0 1 500 − 𝟐 0 0.5 1 0 0.1 0 200
= 0 1 2 0 0 1 500 − 𝟎 𝟏 𝟐 𝟎 𝟎. 𝟐 𝟎 𝟒𝟎𝟎
= 0 0 0 0 − 0.2 1 100

11
OR Ch 3: Linear Programming: Simplex Method
Table 2

Basic 𝑍 X 𝒀 𝑆1 𝑆2 𝑆3 Solution

𝑍 1 −7 0 0 3.2 0 6400

𝑆1 0 7 0 1 -0.6 0 1300

Y 0 0.5 1 0 0.1 0 200

𝑆3 0 0 0 0 -0.20 1 100

12
OR Ch 3: Linear Programming: Simplex Method
Ratio for leaving Variable

Ratio (or
Basic Entering X Solution
intercept)
1300/7 =186
𝑆1 7 1300
(Minimum)
𝑌 0.5 200 200/0.5=400

𝑆3 0 100 ------

13
OR Ch 3: Linear Programming: Simplex Method
 Enter

Basic 𝑍 X 𝒀 𝑆1 𝑆2 𝑆3 Solution

𝑍 1 −7 0 0 3.2 0 6400

Leave 𝑆1 0 7 0 1 -0.6 0 1300

Y 0 0.5 1 0 0.1 0 200

𝑆3 0 0 0 0 -0.20 1 100

14
OR Ch 3: Linear Programming: Simplex Method
1. Replace 𝑺𝟏 in the Basic column with 𝑿

𝑁𝑒𝑤 𝑋 − 𝑅𝑜𝑤 = Current 𝑆1 − 𝑟𝑜𝑤 ÷ 7

1 1 −0.6
0 7 0 1 − 0.6 0 1300 = 0 1 0 7 0 186
7 7

2. 𝑵𝒆𝒘 𝒁 − 𝑹𝒐𝒘 = Current 𝒁 − −𝟕 𝑵𝒆𝒘 𝑿 − 𝑹𝒐𝒘

1 −0.6
= 1 − 7 0 0 3.2 0 6400 − −𝟕 0 1 0 0 186
7 7
= (1 − 7 0 0 3.2 0 6400) − 0 − 7 0 − 𝟏 𝟎. 𝟔 0 − 1302
= 1 0 0 1 2.6 0 7702

15
OR Ch 3: Linear Programming: Simplex Method
3. 𝑵𝒆𝒘𝒀 − 𝑟𝑜𝑤 = Current 𝒀 − 𝑟𝑜𝑤 − 𝟎. 𝟓 𝑵𝒆𝒘 𝑿 − 𝑹𝒐𝒘
1 −0.6
= 0 0.5 1 0 0.1 0 200 − 𝟎. 𝟓 0 1 0 0 186
7 7
𝟎.𝟓 −0.3
= 0 0.5 1 0 0.1 0 200 − 𝟎 𝟎. 𝟓 𝟎. 𝟓 𝟎 𝟗𝟑
7 7
𝟎.𝟓
= 0 0 0.5 − 0.14 0 107
7

4. 𝑵𝒆𝒘𝑆𝟑 − 𝑟𝑜𝑤 = Current𝑆𝟑 − 𝑟𝑜𝑤 − 𝟎 𝑵𝒆𝒘 𝑿 − 𝑹𝒐𝒘

= 0 0 0 0 − 0.2 1 100

16
OR Ch 3: Linear Programming: Simplex Method
Table 3

Basic 𝑍 X 𝒀 𝑆1 𝑆2 𝑆3 Solution

𝑍 1 0 0 1 2.6 0 7702

𝑋 0 1 0 1/7 -0.6/7 0 186

Y 0 0 0.5 -0.5/7 0.14 0 107

𝑆3 0 0 0 0 -0.20 1 100

17
OR Ch 3: Linear Programming: Simplex Method
The optimum solution can be read from the simplex tableau in the following
manner

Decision Variable Optimum value Recommendation

X 186 Produce 186 of product F

Produce 107 of product G

Y 107

Z 7702 Profit per day

18
OR Ch 3: Linear Programming: Simplex Method
Otherwise, if the slack is positive, then the resource is abundant. The following
table classifies the constraints of the model:

Resources Slack Value Status

Machine A 𝑆𝟏 = 𝟎 Scarce

Machine B
𝑆𝟐 = 𝟎 Scarce

Machine C 𝑆3 =100 Abundant

19
OR Ch 3: Linear Programming: Simplex Method
Exercise 1 using TORA APP

Maximize Z = 23 X + 32 Y
Subject to
10 X + 6Y ≤ 2500
5 X + 10Y ≤ 2000
X + 2Y ≤ 500
X,Y ≥ 0 Non-
Negativity Constraint

20
OR Ch 3: Linear Programming: Simplex Method
STEP 1: SELECT LINEAR PROGRAMMING

21
OR Ch 3: Linear Programming: Simplex Method
 22
OR Ch 3: Linear Programming: Simplex Method
STEP 5: FINAL SOLUTION

23
OR Ch 3: Linear Programming: Simplex Method
 Exercise 2

A patient visits the doctor to get treatment for ill health. The
doctor examines the patient and advises him to consume at least
40 units of vitamin A and 50 units of vitamin B daily for a specified
time period. He also advises the patient that to get vitamin A and
vitamin B he has to drink tonic X and tonic Y that have both
vitamin A and vitamin B in a proportion. One unit of tonic X
consists 2 units of vitamin A and 3 units of vitamin B and one unit
of tonic Y consists of 4 units of vitamin A and 2 units of vitamin B.
These tonics are available in medical shops at a cost of Rs.3.00
and Rs.2.50 per unit of X and Y respectively. Now the problem of
patient is how much of X and how much of Y is to be purchased
from the shop to minimise the total cost and at the same time he
can get required amounts of vitamins A and B. 24
OR Ch 3: Linear Programming: Simplex Method
Solution

1. Decision Variables
X= number of units tonic X
Y= number of units tonic Y

tonic
Constraints Capacity
X Y
Vitamin A 2 4 40
Vitamin B 3 2 50
Cost 3 2.5 ----

25
OR Ch 3: Linear Programming: Simplex Method
2. Objective Function

Minimize Z = 3 X + 2.5 Y
Subject to
2 X + 4Y ≥ 40
3 X + 2Y ≥ 50
X,Y ≥ 0 Non-Negativity Constraint

26
OR Ch 3: Linear Programming: Simplex Method
Expressed in equation form

Minimize 1Z − 3 X − 2.5 Y − 100𝑅1 − 100𝑅2 −0𝑆1 − 0𝑆2 = 0

Subject to
0Z + 2 X + 4Y +1𝑅1 + 0𝑅2 − 1𝑆1 = 40 Constraint 1
0Z + 3 X + 2Y + 0𝑅1 + 1𝑅2 − 1𝑆2 =50 Constraint 2
X,Y,𝑅1 , 𝑅2 ,𝑆1 , 𝑆2 ≥ 0
The above data is entered in a table known as simplex table (or tableau). There are many
versions of table but in this book only one type is used.

27
OR Ch 3: Linear Programming: Simplex Method
Table 1

Soluti
Basic 𝑍 X Y 𝑹1 𝑹2 𝑺1 𝑺2
on

𝑍 1 −3 −2.5 -100 -100 0 0 0 𝑍 − 𝑟𝑜𝑤

𝑅1
𝑅1 0 2 4 1 0 -1 0 40
− 𝑟𝑜𝑤
𝑅2
𝑅2 0 3 2 0 1 0 -1 50
− 𝑟𝑜𝑤

28
OR Ch 3: Linear Programming: Simplex Method
Before Going to Simplex Method

 z = (100 × 40) + (100 × 50) = 9000

100 ×R1- Row+100 × 𝐑2- Row

Old Z R1- Row 100 ×R1- Row 𝐑2- Row 100 × 𝐑2- Row New Zrow

1 0 0 0 0 0 1
-3 2 200 3 300 500 497
-2.5 4 400 2 200 600 597.5
-100 1 100 0 0 100 0
-100 0 0 1 100 100 0
0 -1 -100 0 0 -100 -100
0 0 0 -1 -100 -100 -100
0 40 4000 500 5000 9000 9000

29
OR Ch 3: Linear Programming: Simplex Method
Table 1

Soluti
Basic 𝑍 X Y 𝑹1 𝑹2 𝑺1 𝑺2
on

𝑍 1 497 597.5 0 0 -100 -100 9000 𝑍 − 𝑟𝑜𝑤

𝑅1
𝑅1 0 2 4 1 0 -1 0 40
− 𝑟𝑜𝑤
𝑅2
𝑅2 0 3 2 0 1 0 -1 50
− 𝑟𝑜𝑤

30
OR Ch 3: Linear Programming: Simplex Method
Ratio for leaving Variable

Ratio (or
Basic Entering Y Solution
intercept)
𝑅1 4 40 40/4 =10

𝑅2 2 50 50/2=25

Conclusion Y enter at level 10 and 𝑺𝟏 leave at level 0

31
OR Ch 3: Linear Programming: Simplex Method
 Enter

Soluti
Basic 𝑍 X Y 𝑹1 𝑹2 𝑺1 𝑺2
on

𝑍 1 497 597.5 0 0 -100 -100 9000 𝑍 − 𝑟𝑜𝑤

𝑅1
Leave 𝑅1 0 2 4 1 0 -1 0 40
− 𝑟𝑜𝑤
𝑅2
𝑅2 0 3 2 0 1 0 -1 50
− 𝑟𝑜𝑤

32
OR Ch 3: Linear Programming: Simplex Method
1. Replace 𝑹𝟏 in the Basic column with 𝒀

Current 𝑹𝟏 -Row New Y - Row= Current 𝑹𝟏 − 𝑟𝑜𝑤 ÷ 4

0 0
2 0.5
4 1
1 0.25
0 0
-1 -0.25
0 0
40 10

33
OR Ch 3: Linear Programming: Simplex Method
2. 𝑵𝒆𝒘 𝒁 − 𝑹𝒐𝒘 = Current 𝒁 − 𝟓𝟗𝟕. 𝟓 𝑵𝒆𝒘 𝒀 − 𝑹𝒐𝒘

Current Z-Row 𝑵𝒆𝒘 𝒀 − 𝑹𝒐𝒘 𝟓𝟗𝟕. 𝟓 𝑵𝒆𝒘 𝒀 𝑵𝒆𝒘 𝒁 − 𝑹𝒐𝒘

− 𝑹𝒐𝒘
1 0 0 1
497 0.5 298.75 198.25
597.5 1 597.5 0
0 0.25 149.375 -149.375
0 0 0 0
-100 -0.25 -149.375 49.375
-100 0 0 -100
9000 10 5975 3025

34
OR Ch 3: Linear Programming: Simplex Method
2. 𝑵𝒆𝒘𝑹𝟐 − 𝑹𝒐𝒘 = Current 𝑹𝟐 − 𝟐 𝑵𝒆𝒘 𝒀 − 𝑹𝒐𝒘
𝑹𝟐-Row 𝑵𝒆𝒘 𝒀 − 𝑹𝒐𝒘 𝟐𝑵𝒆𝒘 𝒀 − 𝑹𝒐𝒘 𝑵𝒆𝒘𝑹𝟐−Row

0 0 0 0
3 0.5 1 2
2 1 2 0
0 0.25 0.5 -0.5
1 0 0 1
0 -0.25 -0.5 0.5
-1 0 0 -1
50 10 20 30

35
OR Ch 3: Linear Programming: Simplex Method
Table 2

Solutio
Basic 𝑍 X Y 𝑹1 𝑹2 𝑺1 𝑺2
n

𝑍 1 198.25 0 -149.38 0 49.38 -100 3025

𝑌 0 0.5 1 0.25 0 -0.25 0 10

𝑅2 0 2 0 -0.5 1 0.5 -1 30

36
OR Ch 3: Linear Programming: Simplex Method
Ratio for leaving Variable

Ratio (or
Basic Entering X Solution
intercept)
Y 0.5 10 10/0.5 =20

𝑅2 2 30 30/2=15

Conclusion X enter at level 15 and 𝑅2 leave at level 1

37
OR Ch 3: Linear Programming: Simplex Method
 Enter

Basic 𝑍 X Y 𝑹1 𝑹2 𝑺1 𝑺2 Solution

𝑍 1 198.25 0 -149.38 0 49.38 -100 3025

𝑌 0 0.5 1 0.25 0 -0.25 0 10

Leave 𝑅2 0 2 0 -0.5 1 0.5 -1 30

38
OR Ch 3: Linear Programming: Simplex Method
1. Replace 𝑹𝟐 in the Basic column with 𝑿

Current 𝑹𝟐 -Row New X - Row= Current 𝑹𝟐 − 𝑟𝑜𝑤 ÷ 2

0 0
2 1
0 0
-0.5 -0.25
1 0.5
0.5 0.25
-1 -0.5
30 15

39
OR Ch 3: Linear Programming: Simplex Method
2. 𝑵𝒆𝒘 𝒁 − 𝑹𝒐𝒘 = Current 𝒁 − 198.25 𝑵𝒆𝒘 𝑿 − 𝑹𝒐𝒘

Current Z-Row 𝑵𝒆𝒘 𝑿 − 𝑹𝒐𝒘 𝟏𝟗𝟖. 𝟐𝟓 𝑵𝒆𝒘 𝒀 𝑵𝒆𝒘 𝒁 − 𝑹𝒐𝒘

− 𝑹𝒐𝒘
1 0 0 1
198.25 1 198.25 0
0 0 0 0
-149.375 -0.25 -49.56 -99.82
0 0.5 99.125 -99.125
49.375 0.25 49.56 -0.185
-100 -0.5 -99.125 -0.875
3025 15 2973.75 51.25

40
OR Ch 3: Linear Programming: Simplex Method
3. 𝑵𝒆𝒘𝒀 − 𝑹𝒐𝒘 = Current 𝒀 − 𝟎. 𝟓 𝑵𝒆𝒘 𝑿 − 𝑹𝒐𝒘
Current 𝒀 Row 𝑵𝒆𝒘 𝑿 − 𝑹𝒐𝒘 𝟎. 𝟓 𝑵𝒆𝒘 𝑿 − 𝑹𝒐𝒘 𝑵𝒆𝒘 𝒀−Row

0 0 0 0
0.5 1 0.5 0
1 0 0 1
0.25 -0.25 -0.125 0.375
0 0.5 0.25 -0.25
-0.25 0.25 0.125 -0.375
0 -0.5 -0.25 0.25
10 15 7.5 2.5

41
OR Ch 3: Linear Programming: Simplex Method
Table 2

Solutio
Basic 𝑍 X Y 𝑹1 𝑹2 𝑺1 𝑺2
n

𝑍 1 0 0 -99.82 -99.125 -0.185 -0.875 51.25

𝑌 0 0 1 0.375 -0.25 -0.375 0.25 2.5

X 0 1 0 -0.25 0.5 0.25 -0.5 15

42
OR Ch 3: Linear Programming: Simplex Method
The optimum solution can be read from the simplex
tableau in the following manner

Decision Variable Optimum value Recommendation

X 15 15 units of Tonic X

2.5 units of Tonic Y

Y 2.5

Z 51.25 Minimize Cost per day

43
OR Ch 3: Linear Programming: Simplex Method
Solution of Exercise 2 using TORA

44
OR Ch 3: Linear Programming: Simplex Method
 45
OR Ch 3: Linear Programming: Simplex Method
Optimal Solution

46
OR Ch 3: Linear Programming: Simplex Method
Any Question

47
OR Ch 3: Linear Programming: Simplex Method