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

**Chapter 6-2**: The Simplex Method**Chapter 6-3**: Dual Problems

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:

**Setting up the initial tableau**

That is pretty easy. You just translate the equations into a matrix.**Finding the pivot column and row**

Each potential pivot corresponds to an edge that leads out of the current point. Selecting the correct pivot corresponds to selecting the edge along which*P*is increasing the fastest.

The pivot column is the one with the most negative coefficient in the last row.

To find the row, we only consider rows that have**positive**coefficients in the pivot column. If there are no positive numbers in that column, the problem has no solution. For each row, divide the number at the right end by the number in the pivot column, and select the row for which the quotient is the smallest.**Doing the pivot operation**

Doing the pivot operation corresponds to taking a step along the selected edge.

Divide the pivot row by the pivot element, to turn the pivot element into 1. Add or subtract suitable multiples of the pivot row from all the other rows, including the last, to introduce 0 in the pivot column. This is the same step as in the Augmented Matrix method for solving linear systems of equations.**Repeat until there are no more negative numbers in the last row.****Interpret the answer**

There will be*m+1*unit columns (columns with one 1 and otherwise 0), where*m*is the number of problem constraints. One of them is always the*P*column, the other ones are your basic variables. Set all nonbasic variables to 0, and solve for the basic variables.

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.

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.

Read the textbook and do the homework assignment HW 8

Last Updated: Wednesday, August 5, 2015