Bahçeşehir Cyprus University

DEPARTMENT OF INDUSTRIAL ENGINEERING

OPERATIONS RESEARCH II
INE 3201

Faramarz Khosravi
 SIMPLEX METHOD
❑Dantzig's simplex method, 1947
❑J. Laderman solved a diet-planning linear program with nine equality
constraints and 27 nonnegative variables at the National Bureau of
Standards.
❑Using desk calculators, this problem took 120 man-days to solve and the
worksheets were laboriously glued together and spread out like a "table
cloth."
❑If an optimal solution exists, then an optimal extreme point also exists.
❑Extreme points are characterized in terms of basic feasible solutions.
❑The Simplex Method solves linear programs by moving along the
boundaries from one vertex (extreme point) to the next.
 SIMPLEX METHOD
Vectors and Matrices in LP
Standard Form

Linear program in standard form

Max z = 3x1 + 5x2 +x3 + 0s1 +0s2 + 0e3
X1+ 2x2+x3 +S1 =6
3x1+x2+3x3 +S2 =12
X1 – 5x2 -e 3 = 7
X1, x2, x3 , S1 , S3, e3 >=0
 X1 <=0

X4 = -x1

X1 free ( unrestr
X1 = x4-x5
X4 and x5 are >=

X1+ 2x2+x3 <= -6

-X1- 2x2-x3 > = +6
 Max Z = 5X1 + 4 X2 - X3
Subject To
Cont 1
Cont 2 6X1 + 4 X2 -2X3 +S1 = 24
Cont 3
X1 + 2 x2 + 4X 3 -e2 = -6
X2 + 5X3 = 12

X1 >=0
X2 = -X4 X4 >=0
If x2 = -3 then x4 = +3
X3 free (Unrestricted) X3 = X5-X6 x5>=0
X6 >=0
Slack S1 >=0
Excess e2>=0
 Max Z = 5X1 - 4 X4 - (X5-X6)
Cont 1 Subject To
Cont 2
Cont 3
6X1 - 4 X4 -2 (X5-X6) +S1 = 24

(X1 -2 x4 + 4 (X5-X6) -e2 = -6 )× −𝟏

-X4 + 5 (X5-X6) = 12

X1 >=0
X2 = -X4 X4 >=0
If x2 = -3 then x4 = +3
X3 free (Unrestricted) X3 = (X5-X6) x5>=0
X6 >=0
Slack S1 >=0
Excess e2>=0
 Max Z = 5X1 - 4 X4 - (X5-X6)
Cont 1 Subject To
Cont 2
Cont 3
6X1 - 4 X4 -2 (X5-X6) +S1 = 24
- X1 +2 x4 - 4 (X5-X6) +e2 = +6
-X4 + 5 (X5-X6) = 12

X1 >=0
X4 >=0
x5>=0
X6 >=0
Slack S1 >=0
Excess e2>=0
 Standard Form
Max Z = 5X1 - 4 X4 - X5+X6 + 0 S1 + 0 e2
Cont 1 Subject To
Cont 2
Cont 3
6X1 - 4 X4 -2X5 + X6 +S1 = 24
- X1 +2 x4 - 4 X5+ X6 +e2 = +6
-X4 + 5X5+ X6 = 12

X1 >=0
X4 >=0
x5>=0
X6 >=0
Slack S1 >=0
Excess e2>=0
Max Z = 5X1 + 4X2 + 0s1+ 0s2 + 0 s3 + 0s4
St

6X1 + 4X2 +S1 =24

X1 + 2x2 +S2 =6
-X1 + X2 +S3 = 1
X2 + S4 =2
x1>=0
x2>=0
S1>=0
S2>=0
S3>=0
S4>=0
Example 5
Min z= -3x1+x2 Min z= -3x1+x2
4x1+x2 <=4 (1) 4x1+x2 +s1 = 4 (1)
5x1+3x2 >=7 (2) 5x1+3x2 -E2 =7 (2)
3x1+2x2 <=-6 (3) 3x1+2x2 + s3 =-6 (3)
X1>=0 (4) X1>=0 (4)
X2 <=0 (5) X2 <=0 (5)

4x1+x2 +S1 =4
Example 5
Min z= -3x1+x2 Min z= -3x1+x2
4x1+x2 <=4 (1) 4x1+x2 +s1 = 4 (1)
5x1+3x2 >=7 (2) 5x1+3x2 -E2 =7 (2)
3x1+2x2 <=-6 (3) 3x1+2x2 + s3 =-6 (3)
X1>=0 (4) X1>=0 (4)
X2 <=0 (5) X2 = -X3 (5)
X3 >=0
Example 5
Min z= -3x1+x2 Min z= -3x1+x2
4x1+x2 <=4 (1) 4x1+x2 +s1 = 4 (1)
5x1+3x2 >=7 (2) 5x1+3x2 -E2 =7 (2)
3x1+2x2 <=-6 (3) (3x1+2x2 + s3 =-6 )*-1 (3)
X1>=0 (4) X1>=0 (4)
X2 <=0 (5) X2 = -X3 (5)
X3 >=0
Example 5
Min z= -3x1+x2 Min z= -3x1+x2
4x1+x2 <=4 (1) 4x1+x2 +s1 = 4 (1)
5x1+3x2 >=7 (2) 5x1+3x2 -E2 =7 (2)
3x1+2x2 <=-6 (3) -3x1-2x2 - s3 =6 (3)
X1>=0 (4) X1>=0 (4)
X2 <=0 (5) X2 = -X3 (5)
X3 >=0
Example 5
Min z= -3x1+x2 Min z= -3x1+ (-X3)
4x1+x2 <=4 (1)
4x1+ (-X3) +s1 = 4 (1)
5x1+3x2 >=7 (2)
5x1+3 (-X3) -E2 =7 (2)
3x1+2x2 <=-6 (3) -3x1-2 (-X3) - s3 =6 (3)
X1>=0 (4) X1>=0 (4)
X2 <=0 (5) X2 = (-X3) (5)
X3 >=0
Example 5
Min z= -3x1+x2 Min z= -3x1 -X3 + 0s1 + 0 e2 + 0s3

4x1+x2 <=4 (1) 4x1+ -X3 +s1 = 4 (1)

5x1+3x2 >=7 (2) 5x1-3 X3 -E2 =7 (2)
-3x1+2 X3 - s3 =6 (3)
3x1+2x2 <=-6 (3)
X1>=0 (4) X1>=0 (4)
X3 >=0
X2 <=0 (5) s1 >=0
E2>=0
S3 >=0

-1 * -4 = +4
-2 * -x3 = +x3
Example 5
Min z= -3x1+x2 Standard Form
Min z= -3x1 -X3 + 0s1 + 0 e2 + 0s3
4x1+x2 <=4 (1)
5x1+3x2 >=7 (2) 4x1+ -X3 +s1 = 4 (1)
5x1-3 X3 -E2 =7 (2)
3x1+2x2 <=-6 (3) -3x1+2 X3 - s3 =6 (3)
X1>=0 (4)
X1>=0 (4)
X2 <=0 (5) X3 >=0
s1 >=0
E2>=0
S3 >=0
* -1

DO NOT CHANGE
Min Cost = 5X1 – 3X2
Max -Cost= Z = -5X1 + 3X2
Example 6

Min z= -3x1+x2 + 5X3

4x1+x2 + 2X3 <=4 (1)
5x1+3x2 +3X3 >= - 8 (2)
3x1+2x2 =6 (3)
X1 Unrestricted (4)
X2 <=0 (5)
X3 >=0 (6)