Overview
On this page, we discuss linear optimization problems (which are often called “Linear Programs”) and two methods to solve them: A geometric method which works only in dimension 2, and the so-called Simplex Method which works in any dimension, due to George Dantzig (1914-2005).
Important
The basic and advanced learning objectives listed below are meant to give you an idea of the material you should learn about this section. These are mainly intended to be used in a course which uses an Active Learning approach, where students are required to “read ahead” before each class - but can equally be used in a more traditional course setting.
Unless your teacher gives you specific instructions, it is up to you to decide how much of the listed resources you need to read or watch - you probably do not need to go through all of it. You might also want to look at the General Study Tips & Tricks page for some recommendations on how to effectively study with a math textbook and videos.
Basic learning objectives
These are the tasks you should be able to perform with reasonable fluency when you arrive at your next class meeting. Important new vocabulary words are indicated in italics.
- Determine whether an optimization problem is a Linear Program.
- Solve a Linear Program with two variables using the geometric method.
Advanced learning objectives
In addition to mastering the basic objectives, here are the tasks you should be able to perform after class, with practice:
- Rewrite a given linear program in standard form, introducing slack variables as necessary.
- Use the Simplex Method to solve a linear program in standard form.
To prepare for class
-
Watch this video which goes through a detailed example of solving a linear program in two variables geometrically:
-
Watch this video which gives a geometric explanation of the Simplex Method:
-
Do this interactive tutorial about the Simplex Method:
https://www.zweigmedia.com/RealWorld/tutorialsf4/framesSimplex.html
-
Watch this video which shows how to use the Simplex Method on an example with three variables:
After class
-
You can use this online calculator to double-check your calculations when applying the Simplex Method (click on “Examples” to see how to type in a Linear Program):
