Week 10

Topics

This is the second of two weeks devoted to Linear Programming. It is probably the hardest week of the term. Make sure you get started early enough on the assignments. We will cover

The Simplex Method

We know that the maximum has to occur at a corner of the feasible region. The Geometric Method from last week examined all the corners. The Simplex Method also looks at the corners, but only at some of them.

The basic idea is this: you start at the origin, which is always a corner. You go along an edge to the next corner, from there along another edge to another corner, and so on. At each step, you only consider edges along which P increases. When there are no more such edges, you are at the maximum.

The steps have been streamlined into manipulating a special kind of augmented matrix called a tableau (if you haven't taken French: it is one tableau, two tableaux. The pronunciation is the same). Each tableau corresponds to a corner point of the feasible region. Moving from one corner to another along an edge is called a pivoting step. Explaining the exact correspondence between the geometric move along an edge and the sequence of matrix manipulations goes beyond what we can do in this class, unfortunately.

You need to learn the following steps:

You can find detailed examples in the book and in the homework problems.

For your convenience, we provide the document The Simplex Method Algorithm, Example, and TI-83 / 84 Instructions. You can also watch the videos in Youtube Simplex Method. It is very helpful.

Dual Problems

The Simplex Method is for maximization problems in standard form. For minimization problems, you can form the dual problem, which is a maximization problem again, and solve it. Write the constraints and the objective function as a matrix, form the transpose matrix (interchange rows and columns), and read off the dual problem.

Again, there are detailed examples in the book and in the homework.

Assignments

Read the textbook and do the homework assignment HW 8


Last Updated: Wednesday, August 5, 2015