The Simplex Method
The simplest multidimensional constrained optimization is
Simplex method
Assumes that the optimal solution will be an extreme point.
The approach must recognize whether during problem solution
an extreme point occurs.
To do this, the constraint equations are reformulated as
equalities by introducing slack variables.
1
Standard Maximization Problem
A maximization problem is in standard for if the objective function is
generally expressed as
Z = c1 x1 + c2 x2 + + cn xn
is to be maximized, subject to the constraint:
a11 x1 + a12 x2 + + a1n xn b1
a21 x1 + a22 x2 + + a2 n xn b2
. . . .
. . . .
an1 x1 + an 2 x2 + + ann xn bn
With additional constraint:
xi 0
bi 0
2
Characteristics of standard maximization problem:
1. Objective function is to be maximized
2. All variables are non-negative (xi ≥ 0)
3. Each linear constraint is in the form of ≤ to a non-negative
constants (bi ≥ 0)
3
Example 4
Find the maximum value of P = 10x + 12y subject to the
constraints:
x + 2y ≤ 12
3x + 2y ≤ 24
x ≥ 0, y ≥ 0
Solve it by using simplex method.
4
Procedures:
1. P = 10x+12y → P-10x-12y=0
2. Add slack variable
a. x+2y+S1=12
b. 3x+2y+S2=24
3. Arrange the data in table:
Basic P x y S1 S2 solution integration
P
S1
S2
5
Basic P x y S1 S2 solution integration
P 1 -10 -12 0 0 0
S1 0 1 2 1 0 12
S2 0 3 2 0 1 24
by Lale Yurttas, Texas A&M
University
4. Select negative with the largest value of the variable (for this selection refer to
value of x and y at row 1 only) Highlight the
column
Basic P x y S1 S2 solution
P 1 -10 -12 0 0 0
S1 0 1 2 1 0 12
S2 0 3 2 0 1 24
5. Calculate: integration= solution/y
Basic P x y S1 S2 solution integration
P 1 -10 -12 0 0 0 0
S1 0 1 2 1 0 12 6
S2 0 3 2 0 1 24 12
by Lale Yurttas, Texas A&M
University
REMEMBER!
6. At integration column select positive smallest value x and y must
have value.
7. Intercept value need to change to 1 (in this case 2/2) Cannot be
8. All S1 row value divide by 2 zero
Basic p x y S1 S2 solution integration
p 1 -10 -12 0 0 0 0
S1 0 1 2 1 0 12 6
S2 0 3 2 0 1 24 12
9. Other value in column y make it equal to 0 (apply Gauss Jordan)
Basic p x y S1 S2 solution
p 1 -4 0 6 0 72
y 0 0.5 1 0.5 0 6
S2 0 2 0 -1 1 12
8
10. Now repeat procedure 4 - 9
Basic p x y S1 S2 solution integration
p 1 -4 0 6 0 72 -18
y 0 0.5 1 0.5 0 6 12
S2 0 2 0 -1 1 12 6
by Lale Yurttas, Texas A&M
University
12. S1 and S2 become x and y
Basic p x y S1 S2 solution
p 1 0 0 4 2 96
y 0 0 1 0.75 -0.25 3
x 0 1 0 -0.5 0.5 6
Answer:
Maximize value, P = 96 with x = 6 and y = 3
10
Standard Minimization Problem
A minimization problem is in standard for if the objective function
is generally expressed as Z = c x + c x + + c x
1 1 2 2 n n
is to be minimized, subject to the constraint:
a11 x1 + a12 x2 + + a1n xn b1
a21 x1 + a22 x2 + + a2 n xn b2
. . . .
. . . .
an1 x1 + an 2 x2 + + ann xn bn
With additional constraint:
xi 0
bi 0
11
Characteristics of standard minimization problem:
1. Objective function is to be minimized
2. All variables are non-negative (xi ≥ 0)
3. Each linear constraint is in the form of ≥ to a non-
negative constants (bi ≥ 0)
➢ The basic procedure used to solve the standard minimization
problem is to convert it to a standard maximization problem and
then solved it using the techniques for standard maximization
problem.
➢ The transformed maximization problem from the
minimization problem is called dual maximization problem.
12
Example 5
Find the minimum value of P = 0.12x + 0.15y subject to the
constraints:
60x + 60y ≥ 300
12x + 6y ≥ 36
10x + 30y ≥ 90
x ≥ 0, y ≥ 0
Solve it by using simplex method.
13
Procedures:
1. Arrange data in table
x y Solution
60 60 300
12 6 36
10 30 90
0.12 0.15 Objective function
2. Transpose the matrix
u v w solution
60 12 10 0.12
60 6 30 0.15
300 36 90 New Objective
function
3. Generate the new equation:
P=300u +36v+90w
Constraints: 60u+12v+10w ≤ 0.12
60u+6v+30w ≤ 0.15
14
P=300u +36v+90w
Constraints: 60u+12v+10w ≤ 0.12
60u+6v+30w ≤ 0.15
4. Arrange data in table
Basic p u v w S1 S2 solution
p 1 -300 -36 -90 0 0 0
S1 0 60 12 10 1 0 0.12
S2 0 60 6 30 0 1 0.15
5. Solve using maximization problem (Refer to procedure for maximization problem)
15
Basic p u v w x y min
p 1 0 12 0 3 2 0.66
u 0 1 0.25 0 0.025 -0.008333 0.00175
w 0 0 -0.3 1 -0.05 0.05 0.0015
Answer: min=0.66, x=3, y=2
by Lale Yurttas, Texas A&M
University
Chapter 13 by Lale Yurttas, Texas A&M
University
Example 6: Maximize the Profit
Resource Regular, Premium, Resource
X1 X2 Available
Raw Gas 7 11 77
(m3/tonne)
Production 10 8 80
Time
(hr/tonne)
Storage 9 6
(tonnes)
Profit 150 175
(per tonne)
17
ANSWER:
Z= 1413.889
X2 = 3.889
X1 = 4.889
