Week 4: The Simplex Algorithm


Steel mill photo by MCR Safety

Profits and pollution

This week's question is: what can a local community do to get a steel plant to pollute less? Let's put ourselves in the community's shoes. The community accepts that the steel company wants to maximize profits. They have leverage on the company through taxes and levies. How should they deploy those to minimize the pollution from the plant? Hopefully you noticed the words maximize and minimize!

There should be a way to model this as an optimization problem. And there is, but it has three variables! That means we will have a feasible set defined along three axes
→ so we can't draw it on a sheet of paper
→ which means we can't solve it using last week's graphical technique.

What to do? It turns out we can represent multidimensional linear programming models using matrices 🤯, and find the optimal vertex by pivoting the matrix according to some well-defined rules.

The rules that will guide our pivoting are defined by the Simplex algorithm. It's an involved procedure, and is as long as any we will encounter in this course, so if you can manage this you've seen the worst 😅. Like last week we'll start with simplified problems to learn the technique, and then turn our attention back to the question we really care about, how to diminish pollution from the steel plant.

So, we are back to pivoting matrices this week, but this time we'll have our computers do the pivoting for us using an online tool. (Not Excel. Excel can do this, but only through its Solver add-in which is not included in the educational edition of Office 365).

The end of the beginning

This week marks the end of the first segment of the course on linear models. Next week we will turn to nonlinear models, and from there work our way through some topics from calculus that will enable us to model change and accumulation in systems.

Advice from previous students

For several years now I have given a Course Improvement Survey at the end of the semester. One of the questions on it asks students what advice they would give future students. Here's a sampling for you:

  • Doing the homework and being engaged in class goes a long way in helping your understanding of the material
  • Practice often and work on the cheatsheet after every week.
  • The semester is longer than it feels, make sure you’re taking the time to re-review your notes from the beginning of the semester.
  • The best advice for future students is to do the exercises as soon as possible. I found that I was able to finish them faster right after class than waiting a few days. I also think that it's helpful to read through the assignment right after doing the exercises to see what you know how to do.
  • Work hard and trust that you can do it (even if you don't consider yourself a math person, you *can* do it!).
  • Finding your rhythm with the work load will eliminate stress.
  • Do the exercises and assignments as early as possible, so you can attend office hours with questions before having to hand it in.
  • Don't hesitate to ask questions if you are feeling stuck.
  • Practice questions after every class!
  • Really, just to stay on top of things. I think the course is so good that it's kind of hard to do badly in it unless you are either really really bad at math, or you aren't doing the work. So my advice would be to make sure that you're not falling behind, get the work done at all costs! And ask any questions you have. Especially about assignments.

Don't stay stuck!

We all get stuck working on problems, but my heart sinks when students tell me that they spent two hours stuck on a problem. Unless they were steadily trying new things for those two hours, it was time wasted. Time spent stuck is not time spent learning.

If you get stuck working on a problem, check your notes and the course resources, maybe give it ten minutes, but then set it aside and move on to the next one. If you get stuck on that one too, it's time for a break. Switch tasks for a bit. If you don't get any new ideas ask for help! If it's a class day you can see me there, but you can email me anytime. I will get back to you! 🤗 Hopefully with a way to get unstuck.

Reminder: Exercise Set 3 is due by 9 am Monday!

Be sure to give or send me your work. Don't let these easy marks slip through your fingers.

That's all for now!

See you soon,
Tim