Applications of Linear Programming

APM 236H1S Course outline, Spring 2003

Professor: Mary Pugh, mpugh@math.utoronto.ca, (416) 978-5233, room 3141, Earth Sciences Centre, 22 Russell Street.
Office hours: Mondays, 2:30-3:30, Tuesdays, 2:30-3:30 (until Tues April 8)

TA: Joon Song, song@math.utoronto.ca, (416) 978-3201, room 209, 1 Spadina Crescent.
Office hours are by appointment: please call or email.

Prerequisites: MAT 223H or MAT 240H

Text: Bernard Kolman and Robert E. Beck, Elementary Linear Programming with Applications, 2nd edition .

Additional Materials: nine problem sets are given below. Solutions for the first eight problem sets are available for short-term loan in the Gerstein Science Information Centre, as are copies of some term tests (including solutions). I will post solutions for the other problem sets after we cover that material. 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 course mark, and a two-hour final exam worth 60% of the course 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, you read it on your own), introduction to linear programming (Chapter 1), the simplex method (Chapter 2), further topics in linear programming (Sections 3.1-3.4), matrix games (supplementary class notes), problems from integer programming (Chapter 5).

(Advertisement) If test-taking generally makes you nervous, have a look at the test-taking brochure from the University of Illinois at Urbana-Champaign. They also have brochures on other aspects of student life --- have a look --- they're soundly written. For something more than brochures, the University has a counselling and learning skills centre. (Advertisement)

Recommended problems: Make sure you can do the following problems. Note: when the time comes, I will add problems concerning matrix games.

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 325, #8, #10, #11, #12. Here are the solutions to problem set 7.
problem set 8: p 338, #1-7. Here are the solutions to problem set 8.