Week 4
Linear Programming: The simplex method

⦿ Monday. The simplex method. Introductory example.

Handout: The simplex method for problems in standard form PDF

Here are the steps to formulate and solve a LP problem with 3 or more dimensions. (If the problem is in "standard form".)

Some of the terms and procedures won't be familiar, but the next four pencasts will work through an example of applying these steps to a familiar problem and explaining them as we go.

Example 1: Simplex formulation of the furniture manufacturing problem Pencast 6:03|PDF

We begin by stepping through a problem we already know: the furniture manufacturing problem of chairs and sofas. This way we can focus on what is new, the simplex method, without having to learn about a new application domain. Also we can check that we get the right answer! 😏

We begin with the formulation step, and writing the simplex matrix (known as a tableau).

Example 1 continued: Pivoting the simplex tableau Pencast 10:29|PDF

Continuing the example, we see how to follow the simplex rules for pivoting our tableau to reach the final answer.

Example 1 continued: Interpreting the simplex tableau Pencast 6:12|PDF

The sequence of simplex tableaux tells a story as it moves through the solution space looking for the optimum, and each tableau can be interpreted to see what it is telling us.

Example 1 concluded: Sensitivity analysis and shadow prices Pencast 9:00|PDF

The numbers in the final tableau are particularly meaningful. They can tell us how sensitive our solution is to small changes, and how valuable each of the resources our production depends on is.

Geometrical interpretation of the simplex method in 2D Pencast 6:40|PDF

We've see how the simplex tableau changes as we pivot it, but what does it mean? Can we visualize what it is doing?

⦿ Wednesday. The simplex method: Two more examples

Handout: Furniture manufacturing expansion PDF

The information we need to formulate an expanded furniture manufacturing problem.

Example 2: Expanded furniture manufacturing problem Pencast 16:44|PDF

If we expand to three products, then we can't solve the system graphically because our solution space will have three dimensions (3D) instead of just two (2D). This is when we need the simplex method.

Geometrical interpretation of the simplex method in 3D PDF

Can we visualize what the simplex method is doing in 3D?

Handout: The general simplex method PDF

If our problem is not in standard form then we need to convert it to standard form. Fortunately there are, uh, standard, ways of doing that. They are detailed in this handout.

Example 3: NASA dietary requirements revisited Pencast 21:34|PDF

We revisit the NASA problem to see if the general simplex method really does work on minimization problems.

⦿ Friday. The steel plant case study

Handout: Steel plant problem PDF

The fourth problem on this week's assignment describes a steel mill. Here's the information about it that the next pencast will refer to.

Steel plant problem formulation Pencast 18:11|PDF

The formulation of the steel mill problem is fairly involved. So that we all start from the same point I develop the formulation in this pencast.

Using an online tool to pivot our matrices PDF

Pivoting is a mechanical procedure, and humans are bad at carrying out such procedures without making small errors. Computers however excel at mechanical tasks. Last week we saw how we could have Excel solve systems of equations for us. This week we can use the online tool at https://www.zweigmedia.com/RealWorld/tutorialsf1/scriptpivot2.html do our pivoting for us.