DS321-Linear & Integer Programming-2021-2022- Prof. Dr. Tarek H. M.
Abou-El-Enien
Notes on Lesson (3)
Simplex Method
Example:
Use the simplex method and TORA to solve the following problem :
Maximize F= 8x1 + 7x2
subject to
4x1 + 3x2 ≤ 18
x1 + 2x2 ≤ 4
x1 , x 2 ≥ 0
Solution:
Maximize F= 8x1 + 7x2+0s1+0s2
subject to
4x1 + 3x2 + s1 +0s2 = 18
x1 + 2x2 +0s1 + s2 = 4
x1 , x2, s1, s2≥0
Let the non-basic variables x1 =0 and x2 =0, which gives the initial basic
feasible solution
s1=18, s2 =4, x1 =0 , x2 = 0 and the value of F =0 .
Let F- 8x1 - 7x2+0s1+0s2=0
Iteration (1):
Basic F x1 x2 s1 s2 Solution
F 1 -8 -7 0 0 0
s1 0 4 3 1 0 18
s2 0 1 2 0 1 4
1
DS321-Linear & Integer Programming-2021-2022- Prof. Dr. Tarek H. M. Abou-El-Enien
Basic F x1 x2 s1 s2 Solution x1
intercepts
(ratios)
F 1 -8 -7 0 0 0 ____
s1 0 4 3 1 0 18 (18/4)=4.5
s2 0 1 2 0 1 4 (4/1)= 4
1- Pivot equation: (x1-equation)
New pivot equation =(0 1 2 0 1 4) /1=(0 1 2 0 1 4)
2- F- equation :
New F- equation = old F- equation - (-8) (new pivot equation)
= (1 -8 -7 0 0 0) - (-8) (0 1 2 0 1 4)
= (1 -8 -7 0 0 0) + (0 8 16 0 8 32)
= (1 0 9 0 8 32)
3- s1- equation :
New s1- equation = old s1- equation - (4) (new pivot equation)
= (0 4 3 1 0 18) – (4) (0 1 2 0 1 4)
= (0 4 3 1 0 18) – (0 4 8 0 4 16)
= (0 0 -5 1 -4 2)
Iteration (2):
Basic F x1 x2 s1 s2 Solution
F 1 0 9 0 8 32
s1 0 0 -5 1 -4 2
x1 0 1 2 0 1 4
The optimal solution is x1* = 4, x2* = 0 and F * = 32 .
