Course:Math340

Linear Programming
MATH340
Section:	921
Instructor:	Tali Pinksky
Email:	tali@math.ubc.ca
Office:	Math 229a
Office Hours:	Wed 1-2 pm or by appointment
Class Schedule:	Tue-Thu-Fri 2-4 pm, Wed 2-3 pm
Classroom:	Math Annex 1100
Important Course Pages
Resources
Assignments
Discussion
Projects

Welcome to the the course wiki!

Final exam- Solutions

Here's the course outline

Please look through the "Resources" tab on the right for helpful links, registering your clicker through connect, etc. Use the "Discussion" tab above to post comments/questions/suggestions about the course.

Week 1

We saw applications to various engineering/management problem and how to express these as linear programming problems by defining decision variables, an objective function, and constraints. We will see other such examples throughout the course.

We then saw a few examples of matrix games. For these we showed how to: define the payoff matrix $A$, determine the values of the games "Alice plays pure" and "Betty plays pure", and from these determine the duality gap of $A$. We also showed how to compute the best strategy for "Alice plays mixed" or "Betty plays mixed" for $2\times 2$ matrices (by demanding that $xA$ is a vector of the form $(w,w)$, and how to translate the problem of determining Alice's optimal mixed strategy (for any size matrix) into an LP problem.

Finally we saw one example of a step by step solution to an LP problem (from chapter 2 in the textbook), for which the main points are how to define slack variables and how to use a dictionary to define a solution (and how to use a solution to define a dictionary).

Week 2

Chapter 3 in Chvatal:

We considered the geometric description of the simplex method (this is discussed briefly in Chvatal in chapter 17) and used it to see more examples of dictionaries. We saw an unbounded example as well as an infeasible one, and an [example of degeneracy] in three dimensions. Degeneracy may lead to cycling, as in the example on page 30 in the textbook.

We introduced the perturbation/lexicographic method, and proved that it prevents cycling (or degeneracies in general). Then we looked at the two phase method and saw an example of applying it. This is relevant to a problem with an infeasible origin, and it either yields an initial dictionary from which you can start the simplex method (if $x_{0}=0$) or allows you to conclude that the problem has no feasible solution.

Week 3

This week we went through Duality theory- chapter 5 in Chvatal.

We saw how to define the dual problem, and that any solution to the dual problem offers an upper bound for the primal problem (and in particular, if the a problem is dual feasible it cannot be unbounded). We saw how to find an optimal dictionary/solution to the dual problem from an optimal solution to the prime problem. We also defined shadow prices and discussed the meaning of the dual variables and constraints.

Then, we went through the ideas of Duality theorem and of complementary slackness, and saw a couple of examples of how to use the complementary slackness theorem to check whether a solution is optimal. Another application of duality which appears in the homework is an alternative approach to the two phase method (to determine feasibility).

Finally, we considered applications of duality to matrix games, that follow from the fact Betty plays mixed is the dual of Alice plays mixed.

Week 4

The main topic for this week was matrix notations (chapters 6 and 7 in Chvatal) - we saw how to pass from one dictionary to another using multiplication by eta matrices to perform the row operations. We then used that to formulate the revised simplex method- which is a way to use only the matrix representation of each step without computing all entries of the dictionary. Finally, we saw how to compute a dictionary out of the matrix information by inverting $B$ and multiplying $B^{-1}A_{N}$ by $x_{N}$. We also had our midterm (here with solutions).

Week 5

We started with the sensitivity analysis, chapter 10 in Chvatal. This is a nice application of the revised simplex method and it gives a range for which the estimation using shadow prices are true as well as a range for each constraint of the objective function for which the current solution remains optimal. We showed how the same method offers a better starting point (either in the primal or the dual variables) to determine the new optimal solution if you are outside the above range.

We then went through an interior point method called the path following algorithm, according to chapters 17 and 18 in Vanderbei's book. We showed the mathematical derivation of the method and defined the a step by step algorithm that converges to the optimal vertex. We computed a step in the algorithm for a small problem which is symmetric with respect to switching the primal and dual problems. It is hard to compute anything by hand for larger problems so you should know how to use the symmetry.

Week 6

This was a short week and we went mainly through (1) formatting and (2) solving by an algorithm called branch and bound, Integer/binary problems. This was done according to chapter 23 in Vanderbei.

We also went through a comparison of the different algorithms, and application of LP in topology, but these are not included in the material for the final exam.