

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.
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?
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_{1} and
x_{2}, respectively. Now we introduce
x_{3} and x_{4}
to represent the "slack" between the right and left sides of the
inequalities. That is, x_{3} is
8  2x_{1}  2x_{2},
and similarly for x_{4}. These new
variables turn our inequalities into equations in nonnegative
variables:
2x_{1} + 2x_{2} + x_{3} = 8 
5x_{1} + 3x_{2} + x_{4} = 15 
x_{1} > 0, x_{2} > 0, x_{3} > 0, x_{4} > 0. 
Note that these equations tell us immediately the values of x_{3} and x_{4} when x_{1} and x_{2} are both 0. But what we want to know is the values of x_{1} and x_{2} when x_{3} and x_{4} are both 0.
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
stepbystep 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 twofood meal that meets certain nutritional constraints.