Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • 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
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

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

DeleteCancel

The Simplex Method

No description
by

Francis Castro

on 21 September 2013

Comments (0)

Please log in to add your comment.

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
Source: http://upload.wikimedia.org/wikipedia/commons/f/f4/Leonid_Kantorovich_1975.jpg
1939: developed the linear programming technique
World War II: reduce costs to the army, increase losses to the enemy
Developed by George Dantzig (1946)
Algorithm
1. Convert the LP problem to a system of linear equations (use "slack" variables).
2. Setup the initial tableau. Derive the basic feasible solution.
3. Select the pivot column.
4. Select the pivot element.
5. Use the pivot to clear the pivot column. (Here, the next basic feasible solution is derived.)
6. Iterate (3-5) until all negative values in the last row are eliminated.
7. The solution to the problem is the basic feasible solution from the final tableau.
Full transcript