### Present Remotely

Send the link below via email or IM

• Invited audience members will follow you as you navigate and present
• People invited to a presentation do not need a Prezi account
• This link expires 10 minutes after you close the presentation

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

# The Simplex Method

No description
by

## Francis Castro

on 21 September 2013

Report abuse

#### Transcript of The Simplex Method

[ ]
Example:
Maximization Problem
Suppose a company manufactures different electronic components for computers
Components
A
C
B
2 hours FABRICATION
1 hour ASSEMBLY
3 hours FABRICATION
1 hour ASSEMBLY
2 hours FABRICATION
2 hours ASSEMBLY
1000 labor-hours
800 labor-hours
FABRICATION
ASSEMBLY
If the profit for each component (A, B, C) is \$7, \$8, and \$10 respectively, how many of each should be produced to maximize profit?
x1 = no. of components of type A
x2 = no. of components of type B
x3 = no. of components of type C
Maximize
Profit
P = 7(x1) + 8(x2) + 10(x3)
A
C
B
2 hours FABRICATION
1 hour ASSEMBLY
3 hours FABRICATION
1 hour ASSEMBLY
2 hours FABRICATION
2 hours ASSEMBLY
Fabrication
2(x1) + 3(x2) + 2(x3) <= 1000
Assembly
1(x1) + 1(x2) + 2(x3) <= 800
A = \$ 7
B = \$8
C = \$10
(1000 hours)
(800 hours)
P = 7(x1) + 8(x2) + 10(x3)
2(x1) + 3(x2) + 2(x3) <= 1000
1(x1) + 1(x2) + 2(x3) <= 800
Maximize:
Fabrication:
Assembly:
-7(x1) - 8(x2) - 10(x3) + P = 0
2(x1) + 3(x2) + 2(x3) + s1 = 1000
1(x1) + 1(x2) + 2(x3) + s2 = 800
-7(x1) - 8(x2) - 10(x3) + P = 0
2(x1) + 3(x2) + 2(x3) + s1 = 1000
1(x1) + 1(x2) + 2(x3) + s2 = 800
x1
x2
x3
s1
s2
P
2
3
2
1
0
0
1
1
2
0
1
0
1000
800
s1
s2
-7
-8
-10
0
0
1
0
Goal: Setup Initial Tableau
x1
x2
x3
s1
s2
P
2
3
2
1
0
0
1
1
2
0
1
0
1000
800
s1
s2
-7
-8
-10
0
0
1
0
1. Set pivot column
2. Set pivot element
"Most negative" in bottom row
1000 / 2 = 500
800 / 2 = 400
[ ]
x3
Iteration 1
Next Goal: Make pivot element = 1
Iteration 1
Next Goal: Make all other elements in pivot column = 0
x1
x2
x3
s1
s2
P
2
3
2
1
0
0
1
1
2
0
1
0
1000
800
s1
x3
-7
-8
-10
0
0
1
0
1/2(R2) = R2
1/2(1) = 1/2
1/2(1) = 1/2
1/2(2) = 1
1/2(0) = 0
1/2(1) = 1/2
1/2(0) = 0
1/2(800) = 400
[ ]
x1
x2
x3
s1
s2
P
2
3
2
1
0
0
1/2
1/2
1
0
1/2
0
1000
400
s1
x3
-7
-8
-10
0
0
1
0
[ ]
Iteration 1
x1
x2
x3
s1
s2
P
2
3
2
1
0
0
1/2
1/2
1
0
1/2
0
1000
400
s1
x3
-7
-8
-10
0
0
1
0
-2(R2) + R1 = R1
10(R2) + R3 = R3
-2 (1/2) + 2 = 1
-2 (1/2) + 3 = 2
-2 (1) + 2 = 0
-2 (0) + 1 = 1
-2 (1/2) + 0 = -1
-2 (0) + 0 = 0
-2 (400) + 1000 = 200
10 (1/2) + -7 = -2
10 (1/2) + -8 = -3
10 (1) + -10 = 0
10 (0) + 0 = 0
10 (1/2) + 0 = 5
10 (0) + 1 = 1
10 (400) + 0 = 4000
[ ]
x1
x2
x3
s1
s2
P
1/2
1/2
1
0
1/2
0
400
s1
x3
1
2
0
1
-1
0
200
-2
-3
0
0
5
1
4000
Are there negative values in the last row?
Yes.
Iterate.
x1
x2
x3
s1
s2
P
1
2
0
1
-1
0
1/2
1
0
1/2
0
200
400
s1
x3
-2
-3
0
0
5
1
4000
1. Set pivot column
2. Set pivot element
"Most negative" in bottom row
200 / 2 = 100
400 / (1/2) = 800
x2
Iteration 2
Next Goal: Make pivot element = 1
1/2
[ ]
[ ]
Iteration 2
Next Goal: Make all other elements in pivot column = 0
x1
x2
x3
s1
s2
P
1
2
0
1
-1
0
1/2
1/2
1
0
1/2
0
200
400
x2
x3
-2
-3
0
0
5
1
4000
1/2(R1) = R1
1/2(1) = 1/2
1/2(2) = 1
1/2(0) = 0
1/2(1) = 1/2
1/2(-1) = -1/2
1/2(0) = 0
1/2(200) = 100
[ ]
x1
x2
x3
s1
s2
P
1/2
x2
x3
-2
-3
0
0
5
1
4000
1/2
1
0
1/2
0
400
1/2
1
0
1/2
-1/2
0
100
[ ]
Iteration 2
x1
x2
x3
s1
s2
P
1/2
1
0
1/2
-1/2
0
1/2
1/2
1
0
1/2
0
100
400
x2
x3
-2
-3
0
0
5
1
4000
-1/2(R1) + R2 = R2
3(R1) + R3 = R3
-1/2 (1/2) + 1/2 = 1/4
-1/2 (1) + 1/2 = 0
-1/2 (0) + 1 = 1
-1/2 (1/2) + 0 = -1/4
-1/2 (-1/2) + 1/2 = 3/4
-1/2 (0) + 0 = 0
-1/2 (100)
+ 400 = 350
3 (1/2) + -2 = -1/2
3 (1) + -3 = 0
3 (0) + 0 = 0
3 (1/2) + 0 = 3/2
3 (-1/2) + 5 = 7/2
3 (0) + 1 = 1
3 (100)
+ 4000 = 4300
[ ]
x1
x2
x3
s1
s2
P
1/4
0
1
-1/4
3/4
0
350
x2
x3
1/2
1
0
1/2
-1/2
0
100
-1/2
0
0
3/2
7/2
1
4300
Are there negative values in the last row?
Yes.
Iterate.
x1
x2
x3
s1
s2
P
1/2
1
0
1/2
-1/2
0
1/4
1
-1/4
3/4
0
100
350
x2
x3
-1/2
0
0
3/2
7/2
1
4300
1. Set pivot column
2. Set pivot element
"Most negative" in bottom row
100 / (1/2) = 200
350 / (1/4) = 1400
x1
Iteration 3
Next Goal: Make pivot element = 1
0
[ ]
[ ]
Iteration 3
Next Goal: Make all other elements in pivot column = 0
x1
x2
x3
s1
s2
P
1/2
1
0
1/2
-1/2
0
1/4
0
1
-1/4
3/4
0
100
350
x1
x3
-1/2
0
0
3/2
7/2
1
4300
2(R1) = R1
2(1/2) = 1
2(1) = 2
2(0) = 0
2(1/2) = 1
2(-1/2) = -1
2(0) = 0
2(100) = 200
[ ]
x1
x2
x3
s1
s2
P
1/4
x1
x3
-1/2
0
0
3/2
7/2
1
4300
0
1
-1/4
3/4
0
350
1
2
0
1
-1
0
200
[ ]
Iteration 3
x1
x2
x3
s1
s2
P
1
2
0
1
-1
0
1/4
0
1
-1/4
3/4
0
200
350
x1
x3
-1/2
0
0
3/2
7/2
1
4300
-1/4(R1) + R2 = R2
1/2(R1) + R3 = R3
-1/4 (1) + 1/4 = 0
-1/4 (2) + 0 = -1/2
-1/4 (0) + 1 = 1
-1/4 (1) + -1/4 = -1/2
-1/4 (-1) + 3/4 = 1
-1/4 (0) + 0 = 0
-1/4 (200)
+ 350 = 300
1/2 (1) + -1/2 = 0
1/2 (2) + 0 = 1
1/2 (0) + 0 = 0
1/2 (1) + 3/2 = 2
1/2 (-1) + 7/2 = 3
1/2 (0) + 1 = 1
1/2 (200)
+ 4300 = 4400
[ ]
x1
x2
x3
s1
s2
P
0
-1/2
1
-1/2
1
0
300
x1
x3
1
2
0
1
-1
0
200
0
1
0
2
3
1
4400
Are there negative values in the last row?
No.
Terminate.
Final Tableau.
x1
x2
x3
s1
s2
P
0
-1/2
1
-1/2
1
0
300
1
2
0
1
-1
0
200
0
1
0
2
3
1
4400
x1
x3
x1 = 200
x3 = 300
Max profit when:
x2 = 0
Profit = 4400
s1 = 0
s2 = 0
Also:
Linear Programming:
The Simplex Method
Ateneo de Manila University, Philippines
Linear
Programming
an optimization technique that deals with meeting a desired objective
Maximizing Profit
Minimizing Cost
Limited resources
(time, money, etc.)
Mathematical functions:
represent objectives and constraints
scheduling or setting a goal / agenda
History
First developed by Leonid Kantorovich