Introduction to Computer Engineering

Description

• mémoire

12-10-03 ENGIN112 - 1 Introduction to Computer Engineering

• engin112 computing systems
• engin112 computer networks
• fall 199712-06-02 l16
• -03 engin112
• engin112
• circuit design
• computer

Sujets

• Mémoire
• Reconfigurable computing
• Massachusetts
• System
• Computer
• Design

Informations

• Publié par: phawyir
• Nombre de lectures: 18
• Langue: English

Extrait

Linear Programming: Chapter 2
The Simplex Method
Robert J. Vanderbei
October 17, 2007
Operations Research and Financial Engineering
Princeton University
Princeton, NJ 08544
http://www.princeton.edu/rvdbSimplex Method
An Example.
maximize x + 3x 3x1 2 3
subject to 3x x 2x 71 2 3
2x 4x + 4x 31 2 3
x 2x 41 3
2x + 2x + x 81 2 3
3x 51
x ; x ; x 0:1 2 3Rewrite with slack variables
maximize = x + 3x 3x1 2 3
subject to w = 7 3x + x + 2x1 1 2 3
w = 3 + 2x + 4x 4x2 1 2 3
w = 4 x + 2x3 1 3
w = 8 + 2x 2x x4 1 2 3
w = 5 3x5 1
x ; x ; x ; w ; w ; w ; w ; w 0:1 2 3 1 2 3 4 5
Notes:
This layout is called a dictionary.
Setting x , x , and x to 0, we can read o the values for the other variables: w = 7, w = 3, etc. This1 2 3 1 2
speci c solution is called a dictionary solution.
Dependent variables, on the left, are called basic variables.
Independent variables, on the right, are called nonbasic variables.Dictionary Solution is Feasible
maximize = x + 3x 3x1 2 3
subject to w = 7 3x + x + 2x1 1 2 3
w = 3 + 2x + 4x 4x2 1 2 3
w = 4 x + 2x3 1 3
w = 8 + 2x 2x x4 1 2 3
w = 5 3x5 1
x ; x ; x ; w ; w ; w w w 0:1 2 3 1 2 3 4 5
Notes:
All the variables in the current dictionary solution are nonnegative.
Such a solution is called feasible.
The initial dictionary solution need not be feasible|we were just lucky above.Simplex Method|First Iteration
If x increases, obj goes up.2
How much can x increase? Until w decreases to zero.2 4
Do it. End result: x > 0 whereas w = 0.2 4
That is, x must become basic and w must become nonbasic.2 4
Algebraically rearrange equations to, in the words of Jean-Luc Picard, "Make it so."
This is a pivot.A Pivot: x $w2 4
becomesSimplex Method|Second Pivot
Here’s the dictionary after the rst pivot:
Now, letx increase.1
Of the basic variables, w hits zero rst.5
So,x enters andw leaves the basis.1 5
New dictionary is...Simplex Method|Final Dictionary
It’s optimal (no pink)!
Click here to practice the simplex method.
For instructions, click here.Agenda
Discuss unboundedness; (today)
Discuss initialization/infeasibility; i.e., what if initial dictionary is not feasible.
(today)
Discuss degeneracy. (next lecture)Unboundedness
Consider the following dictionary:
Could increase either x or x to increase obj.1 3
Consider increasing x .1
Which basic variable decreases to zero rst?
Answer: none of them, x can grow without bound, and obj along with it.1
This is how we detect unboundedness with the simplex method.