MSIS 685: Linear Programming
Lecture 2
9/22/98
Scribe: Nawei chen
The Simplex Method
Two forms of linear programming problems:
The standard formthe Canonical form
s.t. AX =bs.t. AX b
X 0 X 0
ARm x n ARm x n
bRm bRm
X RnX Rn
X3
C
We use canonical form in our course.
X2
The simplex strategy (Geometrically): X1
EFigure 1
We use figure 1,a geometrical expression of a LP problem, as example
A)Find an extreme point E (any one of vertices).
B)Test if E is optimal (that is check if objective function value at E is better than all of its neighbors).
If optimal, stop. Else go to C)
C)Move to a neighbor of E that has a better objective function value.
D)Go to A)
Convex Sets and Polyhedron
DefinitionHyper plane : a set of points satisfy
XRn , XT= (x1, x2,…… xn )
DefinitionHalf space : a set of points satisfy
In LP, every constraint is half space. Feasible set is the intersection of all half space .
Definition CRn is convex
If for any pair of points X1, X2C then every point of Z on the line segment from X1 to X2 is also in C. Z can be expressed as Z= X1 + (1-) X2, 01
Example:
Figure 1 figure 2
Figure 1 is convex and figure 2 is not convex
If Z=1X1+…nXn and 0i1
Then Z is a convex combination of X1, X2…Xn.
The convex hull of X1, X2…Xn is the set
conv(X1, X2……Xn)=1X1+…….nXn , 0i1,i=1}
The convex hull of a set of vectors is the smallest convex set containing the set.
DefinitionZ==1 X1 +2 X2+…+m Xm is a strict convex combination of X1, X2,….. Xm if at least one of 0<i<1, otherwise it is non-strict convex combination.
Definition if C is a convex set and XC, then X is an extreme point if it can’t be expressed as a strict convex combination of other points of C.
Figure afigure b
Example : figure a) has infinite extreme points. All the vertices and points on curve on Figure b) are extreme points.
Example . a half space is convex.
Proof :
Let XT=(x1,x2,…….. xn)H
YT=(y1, y2,…….. yn)H
ZT =(z1,z2,…….. zn)
Z = X+(1-) Y, 01, so
a1z1+ ……. anzn = a1[x1+(1-) y1]+……… an[xn+(1-) yn]
= [ a1 x1+……..an xn] +(1-)[ a1 y1+……..an yn]
b+(1-)b =b
then Z must in H..
Theorem: if C1, C2 are convex set, then is C1C2.
Proof: let X1, X2C1C2, Z = X1+(1-) X2, 01
X1, X2 C1, so Z C1
X1, X2 C2, so Z C2
So, Z C1C2
The feasible set of LP is convex since it is intersection of half spaces.
Definition A convex polyhedron is the intersection of a finite number of half-spaces.
Note: the feasible set of a canonical linear program is a polyhedron.
Definition A bounded convex polyhedron is called a polytope.
Fact: a polyhedron has a finite number of extreme points.
Fact: The optimum of Max CTX
Subject to X C
Where C is a convex set, if it exists, is attained at an extreme point of C.
An extreme point of a polyhedron in Rn is always a point where at least n of the inequalities are satisfied with equalities.
Note: in a LP, an extreme point is always the solution of a system of n equations.
Definition Two extreme points X1 and X2 are neighbors if their corresponding system
of equations differ only in a equation.
We use an example to illustrate the steps of simplex method.
Max 5x1+ 3 x2+ 4x3
Subject to x1+ x2 + x3 1
2 x1- x2+ x3 5
x1 + 3 x2 - x3 4
x1 , x2, x3 0
Step 1. Introduce n variable to make n inequalities into equalities.
Then, we introduce three slack variable x4, x5, x6, and the constraints become
x1+ x2+ x3 + x4 = 1
2 x1- x2+ x3 + x5 = 5
x1 + 3 x2 - x3 + x6 = 4
x1,2,3 ,4,5,6 0
step 2. Find an initial solution (extreme point) and construct a dictionary.
Group non basic variable to the right side and basic variable to the left side.
When x1 = x2 = x3 = 0 ,all constraints are satisfied. we get the initial solution.
We construct the dictionary:
Z = 5 x1+ 3 x2+ 4 x3
x4 = 1 - x1 - x2 - x3
x5= 5 - 2 x1+ x2 - x3
x6= 4 - x1 - 3 x2 +x3 x1,2,3 ,4,5,6 0
basic var non-basic var
step 3. Move from one point to its neighbor. Since only one equation differs , we will
change one basic variable with one non-basic variable.
Choose x1 as the entering variable, since the coefficient of x1 is positive.
x1should satisfy x1 1, x1 5/2, x1 4 to make x4,5,6 0,then min(1,5/2,4)=1,
we choose x4
as out variable.
Step 4 . Construct new dictionary .
We use x1as entering variable, x4as out variable and get new dictionary:
Z = 5 -2 x2 - x3- 5 x4
x1= 1 - x2- x3- x4
x5=3 + 3 x2 + x3
x6= 3 - 2 x2 +2 x3 +x4
step 5. If coefficients of variable function in objective function is positive , we will go
to step 3. Else, when coefficients is negative, we get the optimal solution.
The coefficients in step 4. Objective functions are all negative, we get the
optimal solution. Max Z= 5 at the extreme point (1,0,0,0,3,3).