APM 236H1S Course outline, Spring 2002
Applications of Linear Programming
Instructor: Mary Pugh, Sidney Smith room 4058. Office hours
Monday 2-3, Friday 1-2, or by appointment.
Prerequisites: MAT 223H or MAT 240H
Text: Bernard Kolman and Robert E. Beck, Elementary Linear
Programming with Applications, 2nd edition .
Additional Materials: Eight problem sets are given on the other
side of this page. Solutions are available for short-term loan in the
Gerstein Science Information Centre, as are copies of all Fall term
tests since 1997 (including solutions). The Association of Part-time
Undergraduate Students in SS 1089 has old final exams for most courses
currently offered at the St. George campus.
Marking Scheme: Two term tests, each worth 20\% of the total
mark, and a two-hour final exam worth 60\% of the total mark. Calculators
are not allowed during the term tests and the final exam. The times and
locations of the term tests will be announced later.
Course Summary (subject to change): review of linear algebra
(Chapter 0), introduction to linear programming (Chapter 1), the
simplex method (Chapter 2), further topics in linear programming
(Chapter 3), the transportation problem (Section 5.1). If time
permits, I will present some "real-world" applications of linear
programming such as game theory and data-fitting.
Recommended problems:
Make sure you can do the following problems. Warning: we
may cover additional material, in which case I'll add extra
problems to this list.
problem set 1: p 21, #6b. (Additional instructions: (i).
Solve for x, y, and z in terms of w. (ii). Solve for x, z, and w
in terms of y.) p 21, #9a, p 28, #6c, #8b, p 42, #5d, #6b
problem set 2: p 57, #2, #4. p. 28, #6, #8, p 59, #10. Put
these problems in canonical and in standard form.
problem set 3: p 82, #14. p 83, #16. In the preceding
questions, replace instructions (b) and (c) with "draw the line
z = c^T x = k, where k is the optimal value of z." p 91, #4, #8, #12.
p 100, #6, #8.
Supplementary problems:
1. Prove that the set of optimal solutions of any linear programming
problem is convex.
2. Prove that the set of objective values which a linear programming
problem attains over its feasible region is convex.
3. Give an example of a convex set in R^2 which
is not a line segment, and hwihc has (1,0) and (0,2) as its only
extreme points.
4. Find all extreme points (in R^3) of the set
{(x1,x2,x3) such that x1 - x2 + x3 = -1, 3 x1 - 2 x2 + 4 x3 = 2, x1 + x2 + 3 x3 = 9, x1 >=0, x2 >= 0, x3 >= 0}.
problem set 4:
p 120, #6 (solve the problem which this tableau represents), #8 (insert
row labels and solve the problem). p.212, #14, #16, #19. p. 122, #22, #23.
p 131, #6.
problem set 5:
p. 150 #2, p. 152, #10, #20.
Supplementary problems:
1. Maximize z = -x1 + 5 x2 + 3 x3 subject to the constraints
2 x1 + x2 + x3 = 5, 3 x1 + 2 x2 >= 6, 4 x1 + 3 x2 - x3 <= 7, x1 >= 0,
x2 >= 0, x3 >= 0.
2. Maximize z = -9 x1 - 4 x3 subject to the constraints
9 x1 + x2 + x3 >= 27, 3 x1 + x2 + 2 x3 = 9, x1 >= 0, x2 >= 0, x3 >= 0.
problem set 6: p 165, #2, #4. p. 166 #6, p. 183, #9. Modify
this problem by replacing "x1, x2, x3 unrestricted" with
"x1 >= 0, x2 >= 0, x3 >= 0". p 184, #11.
Supplementary problems pertaining to section 3.3:
Consider the standard problem: Maximize z = -76 x1 + 13 x2 - 11 x3 - 27 x4 + 2 x5, subject to constraints
11 x1 + x2 - x3 - 7 x4 + x5 <= 3,
-15 x1 - x2 + 2 x3 + 23 x4 - 3 x5 <= 2,
-7 x1 + 2 x2 - 2 x3 - 9 x4 + x5 <= 4,
x1, x2, x3, x4, x5 >= 0.
a) insert slack variables x6, x7, x8 for the first, second, and third
constraints respectively, and write the initial simplex tableau
for the problem.
b) The final simplex tableau for the problem has basic variables
x5, x3, x2 (in that order). Without using the simplex method to find it,
write the final simplex tableau for the problem.
c) Let w_i (i=1,2,3) be the dual variable associated with the ith primal
constraint. What is the optimal solution of the dual problem?
problem set 7:
p. 214, #2. p 215, #4, #8. p 223, #2, #4. p 224, #6, #8.
problem set 8:
p 325, #8, #10, #11, #12.