Math 308-3 Fall 2010 Luis Goddyn
These notes are a supplement and summary to the textbook for Math 308. Students are
expected to know this material for the nal examination.
1. Convexity of Feasible Regions
Here is the missing proof of Theorem 13, Page 13.
Lemma 1.1. Every closed half-space in R n is convex.
Proof. Let H R n be a closed half-space consisting of those points x = (x ,x ,...,x ) satisfying
1 2 n
the inequality a1x 1 a x2+2 + a x n bn Suppose x = (x ,x ,...1x 2 and y n (y ,y ,...,y1) 2 n
belong to H, and let t satisfy 0 t 1. We aim to show that tx + (1 t)y H. We have that x
and y satisfy
a1x 1 a x2+2 + a x n bn
a1 1+ a 2 2 + a yn nb
Since t and 1t are both nonnegative, these two inequalities remain valid if we multiply the rst
by t and the second by 1 t. We add the resulting scaled inequalities to obtain the inequality
a (tx + (1 t)y ) + a (tx + (1 t)y ) + + a (tx + (1 t)y ) tb + (1 t)b = b
1 1 1 2 2 2 n n n
This last inequality states that the point tx + (1 t)y belongs to H, as required.
Lemma 1.2. The intersection of two convex sets is convex.
Proof. Suppose that S and S are convex sets, and that x and y belong to S S . Let t satisfy
0 t 1. Since S is convex, then tx + (1 t)y S. Since S is convex, then tx + (1 t)y S .
Therefore tx + (1 t)y S S . Therefore S S is convex.
Theorem 1.3. The feasible region of a linear program is convex.
Proof. The feasible region of an LP is the intersection of a nite number of closed half-spaces. Each
half-space is convex. The theorem follows from Lemma 1.2
2. The Simplex Algorithm
The following table gives geometric and algebraic interpretations of each step of the Maximum
Simplex Algorithm. We assume that we are starting with a Tucker Tableau (which corresponds to
a basic solution to a maximization linear program).
Step Goal Geometrically Algebraically
(1) Check feasibility Are we within the feasible re- If some b is < 0, then solution is not
of current tableau. gion? feasible. Go to step (7) to preprocess.
Is the current Is there no edge which is If every c is 0, then output this op-
tableau optimal? downhill? timal tableau and STOP.
(3) Select an outgoing Select a downhill edge to Any column, say j = v such that c >v0
column v. travel along. will do. The best v is hard to guess.
(4) Is column v un- Is there nothing to stop me If cv< 0 and every a iv (in column v)
bounded? travelling (downhill) forever? is 0, then indicate the troublesome
column v of the unbounded tableau and
(5) Select an incom- Find a wall that I will run Among those a iv (in column v) with
ing row u. into rst. positive values, select a row, say i = u
giving the smallest ratio aiv.
(6) Pivot on a uv and Move to the new extreme Swap the labels of row u and column v.
go to step (2). point, and repeat. Replace tablequ entries, via tpsrqles:
p p , q p, r p , s p .
1 Preprocessing: The following steps are executed only if the initial tableau is not feasible. It
converts an infeasible tableau into a feasible tableau. Note that the ordering of the rows in the
Tucker Tableau imposes an ordering of the main constraints.
Step Goal Geometrically Algebraically
(7) Check feasibility Are we within the feasible re- If all i are 0, then our solution is
of current tableau. gion yet? feasible. Go to step (1).
(8) Find the last vio- Find the violated constraint Find the largest i such that b i 0.
lated row (row i). which occurs latest in order.
(9) Check if the prob- Does row i show that the fea- If every aij(in row i) is 0, then indi-
lem is infeasible. sible region is empty? cate the troublesome row i and STOP.
The LP has no solution at all!
(10) Select an outgo- Select a wall to leave. Any column v such that a iv< 0 will do.
ing column v.
(11) Select an incom- Among the current (vio- Compute the ratio akv for k = i and
ing row u i. lated) constraint (row k = for every k > i with a kv > 0. Select a
i) and those unviolated con- row, say k = u, which gives the smallest
straints (k > i) which come ratio.
after, nd a wall that I will
run into rst.
(12) Pivot on a uv and Move to the new basic point, Swap the labels of row u and column v.
go to step (7). and repeat. Replace tableau entries, via the rules:
1 q r psrq
p p , q p, r p , s p .
In matrix notation, we have primal and dual variables
X = [x 1 ..2 x ] n Y = [y 1 .2. y ] m t
and primal and dual slack variables
T = [t1x 2.. x ] m S = [s 1 2.. s ] nt
A particular linear program is specied by
cost and constraint vectors, C = [c c1..2 c ] and B = [b b ..1 b2] , m t
an m n matrix of coecients A = (a ), aij
a constant D.
In canonical slack form, the following are dual linear programs.
(P) max f = CX Dt (D) min g = Y B D
AX B = T Y A C = S
X,T 0 Y,S 0
The textbook calls the following the Duality Equation.
Theorem 3.1 (Duality Equation). If (X,T) and (Y,S) satisfy the main constraints of (P) and (D),
g f = SX + Y T. t
If X and Y are feasible for (P) and (D), then all the entries in X,T,Y,S are nonnegative, so
X S + Y T 0. Here the Duality Equation applies, and immediately gives the following.
Theorem 3.2 (Principle of Weak Duality). If X and Y are feasible for (P) and (D), then f g.
If (P) has an optimum solution, then the simplex algorithm correctly nds an optimum solution
for (P). As a bonus, the negative transpose of the nal Tucker tableau also provides an optimum
solution for (D). This fact privides a proof of the following.Theorem 3.3 (Principle of Strong Duality). If (P) has an optimum solution with value f, then (D)
also has an optimum solution, and its value satises g = f.
The following is a way of proving that a vector X is an optimal solution to (P). The if part
follows from the Principle of Weak Duality. The only if part follows from the Principle of Strong
Corollary 3.4. If X and Y are feasible solutions to (P) and (D), then both X and Y are optimal
solutions to (P) and (D) if and only if their objective functions satisfy f = g,
The following is a second way of proving that a vector X is an optimal solution to (P). The
if part follows directly from the Duality Equation. The only if part needs again relies on the
Principle of Strong Duality. We say that X and Y satisfy complementary slackness if for each index
i we have x i i 0, and for each index j we have y t i i. Informally, if any constraint in (P) or
(D) is slack, then the corresponding dual variable should equal zero.
Corollary 3.5. If X and Y are feasible solutions to (P) and (D), then both X and Y are optimal
solutions to (P) and (D) if and only if X and Y satisfy Complementary Slackness,
Another consequence of Weak Duality is as follows.
Corollary 3.6. If (P) is unbounded, then (D) is infeasible.
To see this, suppose that (P) is unbounded and that (D) has a feasible solution Y which gives a
specic value for g. Since (P) is unbounded, it has a feasible solution X which gives a value of f that
is greater than g. This contradicts the Principle of Weak Duality. Therefore if (P) is unbounded,
then (D) can not have any feasible solutions at all.
4. Euclidean Assignment pr