Tutorial: Graphical solution of linear programming problems: Game version

I don't like this new tutorial. Take me back to the old tutorial!

Resources

Note To follow this tutorial, you should know how to graph linear inequalities and systems of linear inequalities.

Fundamentals

We start by looking at the kinds of problems we will be solving:

Linear programming problem (LP problem) in two unknowns

A linear programming problem or LP problem in two unknowns $x, y$ is one in which we are to find the maximum or minimum value of a linear expression

$ax + by$ called the objective function, subject to a number of linear constraints of the form

$cx + dy \leq e \qquad$ or $\qquad cx + dy \geq e.$ The solution set of the collection of constraints is called the feasible region of the LP problem. The largest or smallest value of the objective function is called the optimal value, and a pair of values $(x, y)$ that gives the optimal value constitutes an optimal solution.

Example

Feasible region (unshaded region plus its boundary)

Fundamental theorem of linear programming

If an LP problem has optimal solutions, then at least one of these solutions occurs at a corner point of the feasible region.
A subset of the plane is bounded if it can be entirely enclosed in a box. Otherwise, it is unbounded. Linear programming problems with bounded (see below), nonempty feasible regions always have optimal solutions.

Example

The linear programming problem above has the following feasible region with four corner points marked with dots:

Corner point		Value of $p = x + 3y$
● $(0, 0)$		$p = 0 + 3(0) = 0$
● $(30, 0)$		$p = 30 + 3(0) = 30$
● $(10, 40)$		$10 + 3(40) = 120$
● $(0, 50)$		$p = 0 + 3(50) = 150$ Maximum

Since the corner point with the maximum value of p is (0, 50), we have solved the linear programming problem. The solution is:

$x = 0, y = 50;\ \ p = 150.$ Notes

Each corner point is at the intersection of two (or more) bounding lines, so to find the exact coordinates of a corner point you may need to solve a system of two linear equations in two unknowns.
If the optimal value of the objective function occurs at two corner points, then every point on the line connecting them is also an optimal solution.

The graph on the right shows the feasible region for the following LP problem:

Enter coordinates as they are normally written, eg.(2,-3)

The solution to the LP problem is therefore as follows:

Unbounded feasible sets

LP problems with unbounded feasible sets

Recall from above that a subset of the plane is bounded if it can be entirely enclosed in a box. Otherwise, it is unbounded. When the feasible region for an LP problem is unbounded, there may or may not be an optimal solution.

Below are two LP problems with the same unbounded feasible region. The one on the left has an optimal solution, but the one on the right does not. Verify this yourself by clicking on various points in the feasible region to see the corresponding values of $c$.

Examples

Solving LP problems with unbounded feasible sets

Sometimes we can recognize whether or not an LP problem with an unbounded feasible region has optimal solutions:

The following apply when we have the constraints $x \geq 0,\ y \geq 0.$

If you are minimizing $c = ax + by$ with $a$ and $b$ nonnegative, then optimal solutions always exist.
If you are maximizing $p = ax + by$ with $a$ and $b$ both positive, then there is no optimal solution.
If you are maximizing $p = ax + by$ with $a \leq 0$ and $b \leq 0,$ then optimal solutions always exist.
If you are minimizing $c = ax + by$ with $a$ and $b$ both negative, then there is no optimal solution.

Example

The example above left satisfies (a) and therefore has optimal solutions (we will solve it below). The example above right satisfies none of the requirements, so in principle may or may not have optimal solutions. We shall see a method of dealing with examples like that below.

Now solve the example above left:

%Q What about problems that do not satisfy any of the conditions (a)–(d) above?
%A In %4 you will find a discussion of easy method to determine whether there are optimal solutions in the case of an unbounded feasible region:

Draw a (large) rectangle that includes all the corner points of the feasible region, and compute the values of the objective at the new corner points introduced by the rectangle. If the optimal value is still at one of the original vertices then the LP problem has an optimal solution; otherwise, it does not.

Now try the exercises in %4, some the %8, or move ahead to the next tutorial by pressing "Next tutorial" on the sidebar.