Linear Programming

If \(\begin{align*}z = 2x + 5y\end{align*}\), find the maximum and minimum values of \(\begin{align*}z\end{align*}\) given these constraints:

\(\begin{align*}2x - y & \le 12\\ 4x + 3y & \ge 0\\ x - y & \ge 6\end{align*}\)

First, we need to find the solution to this system of linear inequalities by graphing and shading appropriately. To graph the inequalities, we rewrite them in slope-intercept form:

\(\begin{align*}y & \ge 2x - 12\\ y & \ge - \frac{4}{3}x\\ y & \le x - 6\end{align*}\)

These three linear inequalities are called the constraints, and here is their graph:

The shaded region in the graph is called the feasibility region. All possible solutions to the system occur in that region; now we must try to find the maximum and minimum values of the variable \(\begin{align*}z\end{align*}\) within that region. In other words, which values of \(\begin{align*}x\end{align*}\) and \(\begin{align*}y\end{align*}\) within the feasibility region will give us the greatest and smallest overall values for the expression \(\begin{align*}2x + 5y\end{align*}\)?

Fortunately, we don't have to test every point in the region to find that out. It just so happens that the minimum or maximum value of the optimization equation in a linear system like this will always be found at one of the vertices (the corners) of the feasibility region; we just have to figure out which vertices. So for each vertex - each point where two of the lines on the graph cross - we need to solve the system of just those two equations, and then find the value of \(\begin{align*}z\end{align*}\) at that point.

The first system consists of the equations \(\begin{align*}y = 2x - 12\end{align*}\) and \(\begin{align*}y = - \frac{4}{3}x\end{align*}\). We can solve this system by substitution:

\(\begin{align*}- \frac{4}{3}x &= 2x - 12 \Rightarrow -4x = 6x - 36 \Rightarrow -10x = -36 \Rightarrow x = 3.6\\ y &= 2x - 12 \Rightarrow y = 2(3.6) - 12 \Rightarrow y = - 4.8\end{align*}\)

The lines intersect at the point (3.6, -4.8).

The second system consists of the equations \(\begin{align*}y = 2x - 12\end{align*}\) and \(\begin{align*}y = x - 6\end{align*}\). Solving this system by substitution:

\(\begin{align*}x - 6 &= 2x - 12 \Rightarrow 6 = x \Rightarrow x = 6\\ y &= x - 6 \Rightarrow y = 6 - 6 \Rightarrow y = 0\end{align*}\)

The lines intersect at the point (6, 0).

The third system consists of the equations \(\begin{align*}y = - \frac{4}{3}x\end{align*}\) and \(\begin{align*}y = x - 6\end{align*}\). Solving this system by substitution:

\(\begin{align*}x - 6 &= - \frac{4}{3}x \Rightarrow 3x - 18 = -4x \Rightarrow 7x = 18 \Rightarrow x = 2.57\\ y &= x - 6 \Rightarrow y = 2.57 - 6 \Rightarrow y = -3.43\end{align*}\)

The lines intersect at the point (2.57, -3.43).

So now we have three different points that might give us the maximum and minimum values for \(\begin{align*}z\end{align*}\). To find out which ones actually do give the maximum and minimum values, we can plug the points into the optimization equation \(\begin{align*}z = 2x + 5y\end{align*}\).

When we plug in (3.6, -4.8), we get \(\begin{align*}z = 2(3.6) +5(-4.8) = -16.8\end{align*}\).

When we plug in (6, 0), we get \(\begin{align*}z = 2(6) + 5(0) = 12\end{align*}\).

When we plug in (2.57, -3.43), we get \(\begin{align*}z = 2(2.57) + 5(-3.43) = -12.01\end{align*}\).

So we can see that the point (6, 0) gives us the maximum possible value for \(\begin{align*}z\end{align*}\) and the point (3.6, –4.8) gives us the minimum value.

In the previous example, we learned how to apply the method of linear programming in the abstract. In the next example, we'll look at a real-life application.