Introductory problems

A typical linear programming problem involves finding the maximum or minimum of a linear function (called the objective function) subject to restrictions (constraints) given by linear inequalities. An example of such a problem is given below.

Example 1

Maximize

subject to the constraints

( i )

( ii )

( iii )

( iv )

( v )

We need to find the largest value of P using only x and y values that satisfy the five inequalities.

We first have to find the solution to the system of inequalities. The solution to this system (shown in yellow below) is called the set of feasible solutions.

We must now find the points in yellow where the objective function, , is as large as possible.

First let's show how to find the location of points where P takes on a specified value. Assume we'd like to know where P = 24. This means that we need to know where This, of course, is a line which in slope-intercept form is This is shown in blue on the next graph.

The line corresponding to where the objective function equals 24 intersects the feasible region at the pair (6, 0). (Note that 4(6) + 5(0) = 24 + 0 = 24)

Now let's find where the objective function P equals 30. This happens when or The next graph shows where P equals 30.

The line where P = 30 is parallel to the line drawn in the previous picture since both lines have slope of -4/5. As we continue the process we will get a series of parallel lines with each one the location of where P equals a specified value. We will do this to try to confirm what the text tells you, namely, that the maximum will occur at one of the corners of the feasible region.

In the next picture P = 48.

We certainly can try for a larger value of P and still stay inside of the feasible area. Below we try P = 55.

It looks like we can still get a bigger value. Try P = 60.

Now try P = 72.

We see that there are no pairs in the feasible region (in yellow) when P = 72 . We have tried too big of a value. Now try P = 66.

This also misses the feasible region as well, but not by much. Now try P = 64.8

This touches the feasible region at one point. This point is (36/5, 36/5) = (7.2, 7.2) Note that at this point P = 4(7.2) + 5(7.2) = 28.8 + 36.0 = 64.8

In this series of graphs we have seen P range from 24 to 64.8 at pairs in the feasible regions. The minimum occurred at (6, 0) and the maximum at (7.2, 7.2). This confirms what the book says, i.e. if a linear programming problem has an optimal solution, it occurs at one of the vertices (corners) of the feasible region.

Below is a "movie" which shows a series of these blue lines. In each frame as the blue line changes you should see the value of P change as well.

Unfortunately, at the present time, there is no way to slow this down.

The previous problem had both a minimum value and a maximum value for the objective function. In the next example, we will only be able to get a minimum value.

Example 2

Minimize

subject to

( i )

( ii )

( iii )

( iv )

( v )

Below is a graph of the feasible region given by the restrictions

Note that this set of feasible points is unbounded .

The vertices (corners) are found by solving systems of equations containing the lines that intersect at each vertex. Below are the vertices and the systems used to get each corner.

(0, 120)

which is at the intersection of x = 0 and 3x + y = 120

(10, 90)

which is at the intersection of x + y = 100 and 3x + y =120

(70, 30)

which is at the intersection of x + y = 100 and x + 2y =130

(130, 0)

which is at the intersection of y = 0 and x + 2y = 130

To find the minimum value of P evaluate P at each vertex.

At (0, 120) P = 4(0) + 7(120) = 840

At (10, 90) P = 4(10) + 7(90) = 40 + 630 = 670

At (70, 30) P = 4(70) + 7(30) = 280 + 210 = 490

At (130, 0) P = 4(130) + 7(0) = 520

The smallest value of P is 490 when x = 70 and y = 30.

P can have smaller values but not by using points that meet all of the constraints . Here is a graph showing where P = 400. Note that the blue line is not inside the feasible region.

Here is the minimum value of 490 that occurs at the point (70, 30).

The value will only go up as we check out the other corners. Here is where P = 520

Here P = 670.

At the last corner, P = 840.

There are lots of points where P is even bigger. Since this region is unbounded there is no maximum value for P . In the graph below, we see points in the feasible region where P = 1000.

The following "movie" shows various values of the objective function. .

Unfortunately, at the present time, there is no way to slow this down .

Example 3

Maximize

subject to

( i )

( ii )

( iii )

( iv )

The graph of the feasible region appears below.

This region has corners at (40, 0), (2, 28.5 ), and (2, 19)

The following graph shows the G has the value 164 at (2, 19)

The blue line appears to be parallel to the top edge of the feasible region. In fact this is true because the top edge which has equation, , and the blue line which has equation, , both have slopes of -3/4. As a result, the pairs (40, 0) and (2, 28.5) along with all points in between on that top edge will make G a maximum. In the next picture we will push the blue line closer to the pair (40, 0).

When we move out to (40, 0), the blue line will coincide with the top edge of the region and will seem to disappear from the graph because of this.

The maximum value of G is 240. This value occurs along the line segment from (40, 0) to (2, 28.5)

In the "movie" below you should be able to see the blue line traveling parallel to the top edge of the feasible region.