Study Guides (400,000)
CA (160,000)
SFU (5,000)
MATH (300)
Final

MATH 308 Study Guide - Final Guide: Feasible Region, Linear Programming, Yottabyte


Department
Mathematics
Course Code
MATH 308
Professor
Luis Goddyn
Study Guide
Final

This 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 final 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 HRnbe a closed half-space consisting of those points x= (x1, x2,...,xn) satisfying
the inequality a1x1+a2x2+···+anxnb. Suppose x= (x1, x2,...,xn) and y= (y1, y2,...,yn)
belong to H, and let tsatisfy 0 t1. We aim to show that tx+ (1 t)yH. We have that x
and ysatisfy
a1x1+a2x2+···+anxnb
a1y1+a2y2+···+anynb
Since tand 1 tare both nonnegative, these two inequalities remain valid if we multiply the first
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 Sare convex sets, and that xand ybelong to SS. Let tsatisfy
0t1. Since Sis convex, then tx+ (1 t)yS. Since Sis convex, then tx+ (1 t)yS.
Therefore tx+ (1 t)ySS. Therefore SSis 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 finite 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 first.
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→ psrq
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 ui.
Among the current (vio-
lated) constraint (row k=
i) and those unviolated con-
straints (k > i) which come
after, find a wall that I will
run into first.
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→ psrq
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 specified by
cost and constraint vectors, C= [c1c2. . . cn] and B= [b1b2. . . bm]t,
an m×nmatrix of coefficients A= (aij ), and
a constant D.
In canonical slack form, the following are dual linear programs.
(P) max f=CXtD
AXtB=T
X, T 0
(D) min g=YtBD
YtAC=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
gf=SXt+YtT.
If Xand Yare feasible for (P) and (D), then all the entries in X, T, Y, S are nonnegative, so
XtS+YtT0. 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 fg.
If (P) has an optimum solution, then the simplex algorithm correctly finds an optimum solution
for (P). As a bonus, the negative transpose of the final 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 satisfies 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
specific 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 find 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 in(2)
(Rj)
n
X
i=1
xij = 1 for 1 jn(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