Exercise

Solve the following LPP using simplex method:

1- Max 𝒁 = 𝟑𝑿𝟏 + 𝟒𝑿𝟐
Subject to
15𝑋1 + 10𝑋2 ≤ 300
2.5𝑋1 + 5𝑋2 ≤ 110
𝑋1 ≥ 0, 𝑋2 ≥ 0
Solution: (we have canonical form)
The standard form of LPP
Max 𝑍 − 3𝑋1 − 4𝑋2 = 0
Subject to
15𝑋1 + 10𝑋2 + 𝑆1 = 300
2.5𝑋1 + 5𝑋2 + 𝑆2 = 110
𝑋1 ≥ 0, 𝑋2 ≥ 0, 𝑆1 ≥ 0, 𝑆2 ≥ 0
We have m= 2 and n= 4 , thus n-m=2 ( Non-basic variable which equal zero)
Initial Basic Feasible Solution = (0,0,300,110)
Entering
Iteration 1 Variable
(pivot Colum)

Basic
𝒙𝟏 𝒙𝟐 𝑺𝟏 𝑺𝟐 Solution Ratio
Variables
Z -3 -4 0 0 0
𝑺𝟏 15 10 1 0 300 300/10=30 𝑅𝑜𝑤 3
Leaving Variable 𝑺𝟐 2.5 5 0 1 110 110/5=22 𝑝𝑖𝑣𝑜𝑡 𝑒𝑙𝑒𝑚𝑒𝑛𝑡

Basic
𝒙𝟏 𝒙𝟐 𝑺𝟏 𝑺𝟐 Solution Ratio
Variables
Z -3 -4 0 0 0
𝑺𝟏 15 10 1 0 300 300/10=30
𝒙𝟐 0.5 1 0 0.2 22 110/5=22 Row 2 -(10) Row 3 =
new Row2

Row 1 -(-4) Row 3 =

Iteration 2 Basic 𝒙𝟏 𝒙𝟐 𝑺𝟏 𝑺𝟐 Solution Ratio new Row1
Variables
Z -1 0 0 4/5 88
𝑺𝟏 10 0 1 -2 80 80/10=8
𝒙𝟐 0.5 1 0 0.2 22 22/0.5=44

Row 1 -(-1) (Row2 /10) =

Basic new Row1
𝒙𝟏 𝒙𝟐 𝑺𝟏 𝑺𝟐 Solution
Variables Row 3 -(0.5) (Row2/10) =
Z 0 0 0.1 0.6 96 new Row3
𝒙𝟏 1 0 0.1 -0.2 8
𝒙𝟐 0 1 -0.05 0.3 18

Bayan Almukhlif ‫ | بيان المخلف‬1

The optimal solution: 𝒙𝟏 = 𝟖, 𝒙𝟐 = 𝟏𝟖, 𝑺𝟏 = 𝑺𝟐 = 𝟎, 𝒁 = 𝟗𝟔

2- Min 𝒁 = −𝟑𝑿𝟏 + 𝑿𝟐
Subject to
𝑋1 + 𝑋2 ≤ 5
2𝑋1 + 𝑋2 ≤ 8
𝑋1 ≥ 0, 𝑋2 ≥ 0
Solution:
The standard form of LPP
Min 𝒁 + 𝟑𝑿𝟏 − 𝑿𝟐 = 𝟎
Subject to
𝑋1 + 𝑋2 + 𝑆1 = 5
2𝑋1 + 𝑋2 + 𝑆2 = 8
𝑋1 ≥ 0, 𝑋2 ≥ 0, 𝑆1 ≥ 0, 𝑆2 ≥ 0
We have m= 2 and n= 4 , thus n-m=2 ( Non-basic variable which equal zero)
Initial Basic Feasible Solution = (0,0,5,8)
Basic 𝒙𝟏 𝒙𝟐 𝑺𝟏 𝑺𝟐 Solution Ratio
Variables
Z 3 -1 0 0 0
𝑺𝟏 1 1 1 0 5 5/1=5
𝑺𝟐 2 1 0 1 8 8/2=4

Basic 𝒙𝟏 𝒙𝟐 𝑺𝟏 𝑺𝟐 Solution
Variables
Z 0 -5/2 0 -3/2 -12
𝑺𝟏 0 1/2 1 -1/2 1
𝒙𝟏 1 1/2 0 1/2 4

We note all coefficient of objective function are non-positive values. Thus, the optimal
solution is 𝒙𝟏 = 𝟒, 𝑺𝟏 = 𝟏 , 𝒙𝟐 = 𝟎 , 𝑺𝟐 = 𝟎 , Z= -12

Bayan Almukhlif ‫ | بيان المخلف‬2

 3- Max 𝒁 = 𝟐𝟎𝟎𝑿𝟏 + 𝟏𝟒𝟎𝑿𝟐
Subject to
3𝑋1 ≤ 6000
2.9𝑋2 ≤ 8000
2.5𝑋1 + 2𝑋2 ≤ 7500
1.3𝑋1 + 1.5𝑋2 ≤ 5000
𝑋1 ≥ 0, 𝑋2 ≥ 0
Solution: (we have canonical form)
The standard form of LPP
Max 𝑍 − 200𝑋1 − 140𝑋2 = 0
Subject to
3𝑋1 + 𝑆1 = 6000
2.9𝑋2 + 𝑆2 = 8000
2.5𝑋1 + 2𝑋2 + 𝑆3 = 7500
1.3𝑋1 + 1.5𝑋2 + 𝑆4 = 5000
𝑋1 ≥ 0, 𝑋2 ≥ 0, 𝑆1 ≥ 0, 𝑆2 ≥ 0, 𝑆3 ≥ 0, 𝑆4 ≥ 0
We have m= 4 and n= 6 , thus n-m=2 ( Non-basic variable which equal zero)
Iteration 1
Basic 𝒙𝟏 𝒙𝟐 𝑺𝟏 𝑺𝟐 𝑺𝟑 𝑺𝟒 Solution Ratio
Variables
Z -200 -140 0 0 0 0 0
𝑺𝟏 3 0 1 0 0 0 6000 6000/3=2000
𝑺𝟐 0 2.9 0 1 0 0 8000 -----
𝑺𝟑 2.5 2 0 0 1 0 7500 7500/2.5=3000
𝑺𝟒 1.3 1.5 0 0 0 1 5000 5000/1.3=3846
New pivot row= current pivot row / pivot element
All other rows
New row= (current row) - (pivot column coefficient) (New pivot row)

Row 1 Row 3 Row 4 Row 5

[ -200 -140 0 0 0 0 0] [0 2.9 0 1 0 0 8000] [2.5 2 0 0 1 0 7500 ] [1.3 1.5 0 0 0 1 5000 ]
- (-200)* -(0)* - (2.5)* - (1.3)*
[ 1 0 1/3 0 0 0 2000 ] [1 0 1/3 0 0 0 2000] [1 0 1/3 0 0 0 2000] [1 0 1/3 0 0 0 2000]
= [0 -140 200/3 0 0 0 400000] =[0 2.9 0 1 0 0 8000] =[0 2 -5/6 0 1 0 2500] =[0 1.5 -13/30 0 0 1 2400]

Bayan Almukhlif ‫ | بيان المخلف‬3

 Iteration 2
Basic
𝒙𝟏 𝒙𝟐 𝑺𝟏 𝑺𝟐 𝑺𝟑 𝑺𝟒 Solution Ratio
Variables
Z 0 -140 200/3 0 0 0 400000
𝒙𝟏 1 0 1/3 0 0 0 2000 ----
𝑺𝟐 0 2.9 0 1 0 0 8000 8000/2.9=2758.62
𝑺𝟑 0 2 -5/6 0 1 0 2500 2500/2=1250
𝑺𝟒 0 1.5 -13/30 0 0 1 2400 2400/1.5=1600

[ 0 -140 200/3 0 0 0 400000 ] [1 0 1/3 0 0 0 2000] [0 2.9 0 1 0 0 8000 ] [0 1.5 -1.3/3 0 0 1 2400 ]
-(-140)* -(0)* -(2.9)* -(1.5)*
[0 1 -5/12 0 0.5 0 1250] [0 1 -5/12 0 0.5 0 1250] [0 1 -5/12 0 0.5 0 1250] [0 1 -5/12 0 0.5 0 1250]
= [0 0 25/3 0 70 0 575000] = [1 0 1/3 0 0 0 2000] = [0 0 7.25/6 0 -2.9/2 0 4375] = [0 0 1.15/6 0 -1.5/2 1]

Iteration 3
Basic
𝒙𝟏 𝒙𝟐 𝑺𝟏 𝑺𝟐 𝑺𝟑 𝑺𝟒 Solution
Variables
Z 0 0 25/3 0 70 0 575000
𝒙𝟏 1 0 1/3 0 0 0 2000
𝑺𝟐 0 0 7.25/6 1 -2.9/2 0 4375
𝒙𝟐 0 1 -2.5/6 0 1/2 0 1250
𝑺𝟒 0 0 1.15/6 0 -1.5/2 1 525

The optimal solution:

𝒙𝟏 = 𝟐𝟎𝟎𝟎, 𝑺𝟐 = 𝟒𝟑𝟕𝟓 , 𝒙𝟐 = 𝟏𝟐𝟓𝟎 , 𝑺𝟒 = 𝟓𝟐𝟓 , Z=575000
H.W 3- Max 𝒁 = 𝟑𝟎𝑿𝟏 + 𝟐𝟎𝑿𝟐 + 𝟓 𝑿𝟑
Subject to
2𝑋1 + 𝑋2 + 𝑋3 ≤ 8
𝑋1 + 3𝑋2 − 4𝑋3 ≤ 8
𝑋1 ≥ 0, 𝑋2 ≥ 0 , 𝑋3 ≥ 0

Bayan Almukhlif ‫ | بيان المخلف‬4

H.W 4- Max 𝒁 = 𝟐𝑿𝟏 − 𝑿𝟐 + 𝑿𝟑
Subject to
2𝑋1 + 𝑋2 ≤ 10
𝑋1 + 2𝑋2 − 2𝑋3 ≤ 20
𝑋2 + 2𝑋3 ≤ 5
𝑋1 ≥ 0, 𝑋2 ≥ 0 , 𝑋3 ≥ 0
Solution: (we have canonical form)
The standard form of LPP
Max z
𝑍 − 𝟐𝑿𝟏 + 𝑿𝟐 − 𝑿𝟑 = 0
𝟐𝑿𝟏 + 𝑿𝟐 + 𝒔𝟏 = 𝟏𝟎
𝑿𝟏 + 𝟐𝑿𝟐 − 𝟐𝑿𝟑 + 𝒔𝟐 = 𝟐𝟎
𝑿𝟐 + 𝟐𝑿𝟑 + 𝒔𝟑 = 𝟓
𝑿𝟏 ≥ 𝟎, 𝑿𝟐 ≥ 𝟎 , 𝑿𝟑 ≥ 𝟎, 𝒔𝟏 , 𝒔𝟐 𝒔𝟑 ≥ 𝟎
We have m= 3 and n= 6 , thus n-m=3 ( Non-basic variable which equal zero)
Iteration 1
Basic 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝑺𝟏 𝑺𝟐 𝑺𝟑 Solution Ratio
Variables
Z -2 1 -1 0 0 0 0
𝑺𝟏 2 1 0 1 0 0 10 10/2= 5
𝑺𝟐 1 2 -2 0 1 0 20 20/1= 20
𝑺𝟑 0 1 2 0 0 1 5 ---

Iteration 2
Basic 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝑺𝟏 𝑺𝟐 𝑺𝟑 Solution Ratio
Variables
Z 0 2 -1 1 0 0 10
𝒙𝟏 1 1/2 0 1/2 0 0 5 ---
𝑺𝟐 0 3/2 -2 -1/2 1 0 15 ---
𝑺𝟑 0 1 2 0 0 1 5 5/2 =2.5

Iteration 3
Basic 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝑺𝟏 𝑺𝟐 𝑺𝟑 Solution
Variables
Z 0 5/2 0 1 0 1/2 25/2
𝒙𝟏 1 1/2 0 1/2 0 0 5
𝑺𝟐 0 5/2 0 -1/2 1 1 20
𝒙𝟑 0 1/2 1 0 0 1/2 5/2

𝟐𝟓 𝟓
The optimal solution: 𝒁 = , 𝒙𝟏 = 𝟓, 𝒙𝟐 = 𝟎 , 𝒙𝟑 = 𝟐 , 𝒔𝟐 = 𝟐𝟎, 𝐬𝟏 = 𝟎, 𝐬𝟑 = 𝟎
𝟐

Bayan Almukhlif ‫ | بيان المخلف‬5