School

Simon Fraser UniversityDepartment

MathematicsCourse Code

MATH 308Professor

Luis GoddynStudy Guide

FinalThis

**preview**shows pages 1-3. to view the full**11 pages of the document.**Supplementary Notes

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 Rnis convex.

Proof. Let H⊆Rnbe a closed half-space consisting of those points x= (x1, x2,...,xn) satisfying

the inequality a1x1+a2x2+···+anxn≤b. Suppose x= (x1, x2,...,xn) and y= (y1, y2,...,yn)

belong to H, and let tsatisfy 0 ≤t≤1. We aim to show that tx+ (1 −t)y∈H. We have that x

and ysatisfy

a1x1+a2x2+···+anxn≤b

a1y1+a2y2+···+anyn≤b

Since tand 1 −tare both nonnegative, these two inequalities remain valid if we multiply the ﬁrst

by tand the second by 1 −t. We add the resulting scaled inequalities to obtain the inequality

a1(tx1+ (1 −t)y1) + a2(tx2+ (1 −t)y2) + ···+an(txn+ (1 −t)yn)≤tb + (1 −t)b=b

This last inequality states that the point tx+ (1 −t)ybelongs to H, as required.

Lemma 1.2. The intersection of two convex sets is convex.

Proof. Suppose that Sand S′are convex sets, and that xand ybelong to S∩S′. Let tsatisfy

0≤t≤1. Since Sis 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

of current tableau.

Are we within the feasible re-

gion?

If some biis <0, then solution is not

feasible. Go to step (7) to preprocess.

(2) Is the current

tableau optimal?

Is there no edge which is

“downhill”?

If every cjis ≤0, then output this op-

timal tableau and STOP.

(3) Select an outgoing

column v.

Select a downhill edge to

travel along.

Any column, say j=vsuch that cv>0

will do. The “best” vis hard to guess.

(4) Is column vun-

bounded?

Is there nothing to stop me

travelling (downhill) forever?

If cv<0 and every aiv (in column v)

is ≤0, then indicate the troublesome

column vof the unbounded tableau and

STOP.

(5) Select an incom-

ing row u.

Find a wall that I will run

into ﬁrst.

Among those aiv (in column v) with

positive values, select a row, say i=u

giving the smallest ratio bv

aiv .

(6) Pivot on auv and

go to step (2).

Move to the new extreme

point, and repeat.

Swap the labels of row uand column v.

Replace tableau entries, via the rules:

p7→ 1

p,q7→ q

p,r7→ −r

p,s7→ ps−rq

p.

1

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

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

of current tableau.

Are we within the feasible re-

gion yet?

If all biare ≥0, then our solution is

feasible. Go to step (1).

(8) Find the last vio-

lated row (row i).

Find the violated constraint

which occurs latest in order.

Find the largest isuch that bi<0.

(9) Check if the prob-

lem is infeasible.

Does row ishow that the fea-

sible region is empty?

If every aij (in row i) is ≥0, then indi-

cate the troublesome row iand STOP.

The LP has no solution at all!

(10) Select an outgo-

ing column v.

Select a wall to leave. Any column vsuch that aiv <0 will do.

(11) Select an incom-

ing row u≥i.

Among the current (vio-

lated) constraint (row k=

i) and those unviolated con-

straints (k > i) which come

after, ﬁnd a wall that I will

run into ﬁrst.

Compute the ratio bk

akv for k=iand

for every k > i with akv >0. Select a

row, say k=u, which gives the smallest

ratio.

(12) Pivot on auv and

go to step (7).

Move to the new basic point,

and repeat.

Swap the labels of row uand column v.

Replace tableau entries, via the rules:

p7→ 1

p,q7→ q

p,r7→ −r

p,s7→ ps−rq

p.

3. Duality

In matrix notation, we have primal and dual variables

X= [x1x2. . . xn]Y= [y1y2. . . ym]t,

and primal and dual slack variables

T= [t1x2. . . xm]S= [s1s2. . . sn]t.

A particular linear program is speciﬁed by

•cost and constraint vectors, C= [c1c2. . . cn] and B= [b1b2. . . bm]t,

•an m×nmatrix of coeﬃcients A= (aij ), and

•a constant D.

In canonical slack form, the following are dual linear programs.

(P) max f=CXt−D

AXt−B=−T

X, T ≥0

(D) min g=YtB−D

YtA−C=S

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),

then

g−f=SXt+YtT.

If Xand Yare feasible for (P) and (D), then all the entries in X, T, Y, S are nonnegative, so

XtS+YtT≥0. Here the Duality Equation applies, and immediately gives the following.

Theorem 3.2 (Principle of Weak Duality).If Xand Yare 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.

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

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 satisﬁes g=f.

The following is a way of proving that a vector Xis 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

Duality.

Corollary 3.4. If Xand Yare feasible solutions to (P) and (D), then both Xand Yare 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 Xis 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 Xand Ysatisfy complementary slackness if for each index

iwe have xisi= 0, and for each index jwe have yiti= 0. Informally, “if any constraint in (P) or

(D) is slack, then the corresponding dual variable should equal zero.”

Corollary 3.5. If Xand Yare feasible solutions to (P) and (D), then both Xand Yare optimal

solutions to (P) and (D) if and only if Xand Ysatisfy 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 Ywhich gives a

speciﬁc value for g. Since (P) is unbounded, it has a feasible solution Xwhich gives a value of fthat

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 problem

Chapter 6, Section 6 of the text (p. 164) introduces the Assignment Problem as follows. There

are npeople P1,...,Pnand njobs J1,...,Jn. Each person should be assigned one job, and each

job is assigned to one person. Assigning Pito job Jjentails a cost of cij . The object is to ﬁnd an

assignment of minimum total cost.

For each pair i, j (where 1 ≤i, j ≤n) we have an indicator variable xij . The value xij = 1

indicates that Piis assigned to Jj. We have xij = 0 if Piis not assigned to Jj. A fractional value

xij = 1/2 may not have a real-world interpretation, as it indicates something like Piis half-assigned

to Jj. The indicator vector X= (x11, x12,...,xn,n) is the set of variables for the following linear

program.

min

n

X

i=1

n

X

j=1

cij xij

(1)

(ri)

n

X

j=1

xij = 1 for 1 ≤i≤n(2)

(Rj)

n

X

i=1

xij = 1 for 1 ≤j≤n(3)

xij ≥0 for 1 ≤i, j ≤n(4)

Notice that any feasible assignment of people to jobs gives rise to an indicator variable Xwhich is

feasible for the LP.

This LP has 2nmain constraints. In parentheses I have indicated a set of dual variables

Y= (r1, r2,...,rn, R1, R2,...,Rn)

###### You're Reading a Preview

Unlock to view full version