Mathematica Tutor Part 11

Mathematica Tutor

Part 11: Solving Linear Programming Problems (optional)

Linear programming (LP) is an application of linear algebra in which the central problem is to maximize or minimize a linear function (of perhaps many variables) on a domain defined by linear inequalities and equations. In this tutorial, we consider only LP problems in two variables. In this part, we address such problems directly in terms of linear algebra and then briefly mention Mathematica's commands for solving such problems by the Simplex Algorithm, the central tool of applied linear programming.

Our prototypical LP problem* is this:

Problem A. Find values of x and y that will maximize z = 120x + 100y subject to the restrictions

2x + 2y < 8

5x + 3y < 15

x > 0, y > 0.

The function z(x,y) to be optimized is called the objective function. The inequalities that determine the domain are called constraints. Points (x,y) that satisfy all of the constraints are called feasible. Points that are not feasible are excluded. The variables x and y are called decision variables.

First we explore the geometry of the domain determined by the constraint inequalities. Mathematica's ImplicitPlot package has a command called ImplicitPlot that we can use to draw such a domain. Enter
<< Graphics`ImplicitPlot`
Then enter
constraintsA = {2*x+2*y==8, 5*x+3*y==15, x==0, y==0}
and
domainA = ImplicitPlot[constraintsA, {x, 0, 5}, {y, 0, 5}];
The result should look something like this:

However, the default colors are different from the ones we show here. The command that drew this picture was actually
domainA = ImplicitPlot[constraintsA, {x, 0, 5}, {y, 0, 5}, PlotStyle -> {{RGBColor[0, 0, 1], Thickness[0.01]}}];
You may experiment with plot options to find a combination you like. How does the picture drawn by ImplicitPlot represent the feasible region?
Next we draw a contour map of the objective function. Enter
ContourPlot[120*x + 100*y, {x, -1, 5}, {y, -1, 5},
ContourStyle-> {{Thickness[0.01], RGBColor[1, 0, 0]}},
Contours -> {0, 220, 440, 660, 880},
ContourShading -> False];
and explain what the picture shows.

The "contours" or "level curves" of a linear function are just parallel straight lines. In the following figure we have superimposed the contour map on the domain plot -- which you may do in Mathematica by using the Show command. We have also indicated the constant z values on the corresponding contours. [We chose contours through the points (0,0), (1,1), (2,2), etc., to make the calculations easy.]

Observe that z increases as we move up and to the right across the domain. The first two contours (from the left) include points in the domain, but their z values are clearly not maximal. The two contours on the right miss the domain entirely -- that is, they contain no feasible points. It is not clear whether the middle contour meets the domain or not, but the maximal z value must be close to 440. And the exact point where z is maximized must be the "corner" of the domain where the two slanting boundary lines meet. Thus, our job is to find that point.

Finding the point of intersection of two lines in the plane is not a difficult algebra problem. Indeed, all we have to do is solve the simultaneous equations

2x + 2y = 8

5x + 3y = 15

However, we choose deliberately to complicate the problem so that our means of solution relates to more general LP problems for which we will not be able to spot the answer by looking at a picture in the plane.

Because we are about to introduce some new variables, we rename x and y as x₁ and x₂, respectively. Now we introduce x₃ and x₄ to represent the "slack" between the right and left sides of the inequalities. That is, x₃ is 8 - 2x₁ - 2x₂, and similarly for x₄. These new variables turn our inequalities into equations in nonnegative variables:

2x₁ + 2x₂ + x₃ = 8

5x₁ + 3x₂ + x₄ = 15

x₁ > 0, x₂ > 0, x₃ > 0, x₄ > 0.

Note that these equations tell us immediately the values of x₃ and x₄ when x₁ and x₂ are both 0. But what we want to know is the values of x₁ and x₂ when x₃ and x₄ are both 0.

Use the Solve command (as in Part 9) to solve the new equations for x₁ and x₂. Then read by inspection the values of x₁ and x₂ at the intersection of the sloping lines.
Find the maximal value of z. Did the contour z = 440 contain any feasible points or not? Explain.
Mathematica can solve linear programming problems like these all-at-one using an algorithm called the simplex algorithm. First we will define the objective function:
objA[x_, y_] := 120*x + 100*y
Next enter
constraintsA = {2*x+2*y<=8, 5*x+3*y<=15}
Note two differences from the way we entered constraints in Step 1: We are not including the nonnegativity constraints, and we are using inequalities rather than equalities. Finally, enter
ConstrainedMax[objA[x, y], constraintsA, {x, y}]

Apply what you have learned to solve

Problem B.* Find values of x and y that will minimize z = 20x + 25y subject to the restrictions

2x + 3y > 18

x + 3y > 12

4x + 3y > 24

x > 0, y > 0.

Draw the domain, make a contour map of the objective function, and decide where the minimum value must be found. Introduce slack variables, and solve for x and y when the appropriate slack variables are 0. Then use the ConstrainedMin function to check your answer.

The step-by-step procedure is useful for learning to solve linear programming problems. The ConstrainedMax and ConstrainedMin functions are useful once you understand how the solutions work.

* Problems A and B are adapted from Section 1.1 of Elementary Linear Programming with Applications, 2nd ed., by B. Kolman and R. Beck, Academic Press, 1995. The suggested context for Problem A is maximizing profit from a manufacturing product mix and for Problem B minimizing the cost of a two-food meal that meets certain nutritional constraints.