Week 5
Linear Programming: The simplex method

Business

The start of the week email. No need to reread it if you received it. It's just linked here in case anyone accidentally deleted it (it's happened before 🥺). Definitely let me know if you didn't receive it though so we can figure out why not.

Course Survey 1: Results and Response 📄 Slide show | 📘 PDF Thank you all for filling out the survey! 🤗 In this isolated teaching-learning situation it gives me a much better idea of how things are going. I have tried to respond to each concern expressed. If I missed any it’s due to simple oversight so please don’t hesitate to bring it to my attention.

The simplex method

Handout: The simplex method for problems in standard form 📘 PDF
The steps to formulate and solve a LP problem with 3 or more dimensions. (If the problem is in "standard form".)
Example: 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 cont'd: Pivoting the simplex tableau 📹 Pencast 10:29|📘 PDF
Continuing the example, we see how to follow the simplexx rules for pivoting our tableau to reach the final answer.
Example cont'd: Interpreting the simplex tableau 📹 Pencast 6:12|📘 PDF
The sequence of simplex tableaux tell a story as it moves through the solution space looking for the optimum, and each tableau can be interpreted to hear what it is telling us.
Example cont'd: Sensitivity analysis and shadow prices 📹 Pencast 9:00|📘 PDF
The numbers in the final tableau are particularly meaningful and 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?
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.
Handout: Furniture manufacturing expansion 📘 PDF
The information we need to formulate an expanded furniture manufacturing problem.
Example: Expanded furniture manufacturing problem 📹 Pencast 16:45|📘 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: NASA dietary requirements revisited 📹 Pencast 21:35|📘 PDF
We revisit the NASA problem to see if the general simplex method really does work on minimization problems.
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 we will all start from the same point I develop the formulation in this pencast. Bonus! I make a mistake! See if you spot it in the pencast, then check the PDF where I've corrected it (in green). I re-recorded it. Mistake-free. I hope. 🤭

Supplementary resources

Some of you have requested traditional textbook-like materials for the course content. Here are some for the Simplex method for maximization (unfortunately they use a different approach than we do for minimization problems).

If you would like an interactive tutorial see 4.3: The Simplex Method: Solving Standard Maximization Problems. If the text is very small (as it was for me) remember that you can ahve your browser scale it up by pressing Ctrl-+ or Command-+ repeatedly.

If you are interested in a thorough, deeper look at the simplex method Solving Linear Programs is very good.

If you use any of these resources, please let me know how you found them! Even a simple 0-3 star rating would be helpful.

Exercises

Exercise Set 5 Part 1: Problems and Solutions. Due by 4 pm Monday February 8.

Exercise Set 5 Part 2: Problems and Solutions. Due by 4 pm Monday February 8.

Assignment

Assignment 4 is posted. Due by 4 pm Friday February 12. Note that the problems are worth different numbers of marks. Use your time wisely.

Submit PDF files of work done by hand, or in a word processor. (Let me know if you are unsure how to create these.) Email is preferred, but you can also submit your work through Moodle.
Excel or other binary files should be sent as file attachments.
Google sheets can be submitted by sharing a link to them.

Name the file you submit A4_firstname.pdf, e.g.

A4_Tim.pdf

If you have to submit multiple files, add a suffix number to each, e.g.

A4_Tim_1.pdf
A4_Tim_2.pdf