# 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

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

## 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:

• 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.
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.

## 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