####
Applications of Linear Programming

####
APM 236H1S Course outline, Spring 2004

** Professor: ** Mary Pugh,
mpugh@math. utoronto.ca, (416) 978-5233

** Office hours: ** by appointment. Please email.

** Office location: **
room 3141,
Earth Sciences Centre,
22 Russell Street.

**
If you're going to send me email, please include "apm236" in the
subject line. Otherwise, there's a good chance my spam filter
will filter your email.
**

** TA: **Oliver Chen, ochen@math. utoronto.ca

** Office hours: ** by appointment. Please email.

** Office location: ** Sidney Smith, room 3070

**
Prerequisites: ** MAT 223H or MAT 240H

**
Text: ** Bernard Kolman and Robert E. Beck, * Elementary Linear
Programming with Applications, 2nd edition*.
The book is on
reserve in Gerstein. Its call number is T57.74 .K64 1995X.

** Additional Materials: ** nine problem sets are given below.
Solutions for the first six problem sets are available for
short-term loan in the Gerstein Science Information Centre, as are
copies of some term tests (including solutions).
Solutions for the
remaining three problem sets are posted below.
The Association of Part-time Undergraduate Students in SS
1089 has old final exams for most courses currently offered at the
St. George campus.
I've taught this course twice before. Here are the course webpages for
Spring 2002
and
Spring 2003
in case you find them of use.

**
Marking Scheme: ** Two term tests, each worth 25% of the course
mark, and a two-hour final exam worth 50% of the course mark. Calculators
and other devices
are not allowed during the term tests and the final exam.
The first term
test
will be on Wednesday February 4 starting at 6:10, ending at 7:00. The second term test will be on
Wednesday March 10 starting at 6:10, ending at 7:00.

**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 of Toronto has a
counselling and learning skills centre.
**(Advertisement)**

**
Recommended problems:
Make sure you can do the following problems.
**

** 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.
(NOTE: if you try doing problem #7 on page 100, you'll discover that
the answer in the back of the book is wrong. The correct answer is:
7a: not a basic solution since it doesn't satisfy Ax=b. 7b: is a basic
solution with basic variables x2, x3, and x5. 7c: is a basic solution
with basic variables x1, x3, and x5. Or with x2, x3, and x5. Or with
x3, x4, and x5.)

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.121, #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: ** Here are some
game theory problems to work on.
Here are their
solutions.

** problem set 8: ** p 325, #8, #10, #11, #12.
Here are the
solutions
to problem set 8.