Applicable Mathematics/Linear Programming and Graphical Solutions

Linear Programming

Linear programming is a method that is used to find a minimum or maximum value for a function. That value is going to satisfy a known set of conditions constraints. Constraints are the inequalities in the linear programming problem. Their solution is graphed as a feasible region, which is a set of points. These points are where the graphs of the inequalities intersect. And, the region is said to be bounded when the graph of a system of constraints is a polygonal region.

There are 7 steps that are used when solving a problem using linear programming.

1. Define the variables.

2. Write a system of inequalities.

3. Graph the system of inequalities.

4. Find the coordinates of the vertices of the feasible region.

5. Write a function to be maximized or minimized.

6. Substitute the coordinates of the vertices into the function.

7. Select the greatest or least result. Answer the problem.

Many types of real-world problems can be solved using linear programming. These problems have restrictions placed on the variables. Some function of the variable must be maximized or minimized.

Linear Programming Examples

1. Hannah is planting a garden that she plans on having cover no more than 700 square feet of her backyard. Grass and ground cover are the two types of vegetation she is planning on planting in it. Each grass slab covers 2 square feet, and each ground cover slab covers 3 square feet. Each slab of grass and ground cover costs $3/slab, and Hannah's goal is to spend less than $2,000. Graph the feasible region and write the constraints.

Let g be the number of grass slabs and let c be the number of ground cover slabs. Then, write the constraints:

g is greater than or equal to 0 and c is greater than or equal to 0, because the amount of grass and ground cover slabs cannot be negative.

2g + 3c is less than or equal to 700 , because the total area is less than or equal to 700 feet squared.

3g + 3c is less than or equal to 2000, because the total cost has to be less than or equal to $2,000.

Next, graph the feasible region. Once graphed, you shall see that the region is a quadrilateral with vertices at (0,0), (350,0), (0,233), and ( ).

Finally, check a point in the feasible region to make sure that it satisfies all of the constraints. For example, (200, 200) does not satisfy the constraints, because 2(200) + 3(200) = 1000, which is gives us an area that is greater than our given 700 square feet.

2. Being a receptionist for a doctor, one of Megan's tasks is to schedule appointments. She gives 20 minutes for a routine office visit and 40 minutes for a surgery. The doctor cannot do more than 6 surgeries a day. The office is open 7 hours a day for appointments. An office visit costs $55 and a surgery costs $125. Find a combination of office visits and surgeries that will maximize the income the veterinarian practice receives per day.

1. Define the variables.

v = the number of office visits

s = the number of surgeries

2. Write a system of inequalities.

Since the number of ppointments cannot be negative, v and s must be nonnegative numbers.

v > 0 and s > 0

An office visit is 20 minutes, and a surgery is 40 minutes. There are 7 hours available for appointments.

20v + 40s < 420 7 hours = 420 minutes

The doctor cannot do more than 6 surgeries a day.

s < 6

3. Graph the system of inequalities.

4. Find the coordinates of the vertices of the feasible region. From the graph, the vertices of the feasible region are at (0, 0), (6, 0), (6, 9), and (0, 21). If the vertices could not be read from the graph easily, we could also solve a system of equations using the boundaries of the inequalities.

5. Write a function to be maximized or minimized. The function that describes the income is f(s, v) = 125s + 55v. We wish to find the maximum value for this function.

6. Substitute the coordinates of the vertices into the function.

7. Select the greatest or least result. Answer the problem.

The maximum value of the function is 1245 at (6, 9). This means that the maximum income is $1245 when Megan schedules 6 surgeries and 9 office visits.

(example taken from Glencoe Mathematics Algebra 2)

Objective Function

Sometimes, in linear programming problems, identifying the feasible region is not the only thing necessary to be done. To maximize or minimize the function, the best combination of values must be found. This is what the objective function does. It can either have a maximum value, a minimum value, both, or neither. It all depends upon the feasible region.

There are two different general types of regions: bounded and unbounded regions. Bounded feasible regions have both a minimum and a maximum value. Unbounded feasible regions have either a minimum or maximum value, never both. The minimum or maximum value of such objective functions always occurs at the vertex of the feasible region. This mathematical idea, however, is a proof that is for more advanced mathematics.

Bounded Region Example

Graph the following system of inequalities. Name the coordinates of the vertices of the feasible region. Find the maximum and minimum values of the function f(x,y) = 3x + y for this region. x > 1

y > 0 2x + y < 6

1. Find the vertices of the region. Graph the inequalities.

The polygon formed is a triangle with vertices at (1, 4), (3, 0), and (1, 0).

2. Use a table to find the maximum and minimum values of f(x, y). Substitute the coordinates of the vertices into the function. The maximum value is 9 at (3, 0). The minimum value is 3 at (1, 0).

Unbounded Region Example

Graph the following system of inequalities. Name the coordinates of the vertices of the feasible region. Find the maximum and minimum values of the function f(x, y)= 5x + 4y for this region.

2x + y > 3

3y - x < 9

2x + y < 10

Graph the system of inequalities. There are only two points of intersection: (0, 3) and (3, 4).

The maximum is 31 at (3, 4).

Although f(0, 3) is 12, it is not the minimum value since there are other points in the solution that produce lesser values. For example, f(3, -2) = 7 and f(20, -35) = -40. It appears that way because the region is unbounded, f(x, y) has no minimum value.

Maximum and Minimum Values

Sometimes, it is necessary to find the minimum or maximum value that a linear function has for the points in a feasible region. The minimum or maximum value of a related function always occurs at one of the vertices of the feasible region.