Linear Programming and Optimization Worksheet

Question 1

For the constraints x >= 0, y >= 0, x + y <= 10, and 2x + y <= 14, list the vertices of the feasible region.

Accepted Answer

The vertices of the feasible region are (0, 0), (7, 0), (4, 6), and (0, 10). These points come from the axis intercepts and the intersection of x + y = 10 and 2x + y = 14.

Question 2

Use the feasible region from problem 1 to maximize P = 3x + 2y.

Accepted Answer

Evaluate the objective function at each vertex: P(0, 0) = 0, P(7, 0) = 21, P(4, 6) = 24, and P(0, 10) = 20. The maximum value is 24 at (4, 6).

Question 3

A workshop makes chairs and tables. Let x be the number of chairs and y be the number of tables. Each chair takes 2 hours and 3 boards. Each table takes 4 hours and 8 boards. The workshop has at most 40 hours and 72 boards. A chair earns $15 profit and a table earns $40 profit. Write the constraints and the objective function.

Accepted Answer

The constraints are 2x + 4y <= 40, 3x + 8y <= 72, x >= 0, and y >= 0. The objective function is maximize P = 15x + 40y, where P is the total profit in dollars.

Question 4

Solve the workshop problem from problem 3. Find the maximum profit and the number of chairs and tables that give it.

Accepted Answer

The vertices are (0, 0), (20, 0), (8, 6), and (0, 9). The profits are $0, $300, $360, and $360. The maximum profit is $360, and it can be earned by making 8 chairs and 6 tables or by making 0 chairs and 9 tables.

Question 5

Decide whether the point (3, 5) is feasible for the constraints x + 2y <= 12, 3x + y <= 14, x >= 0, and y >= 0. Show your substitution.

Accepted Answer

The point (3, 5) is not feasible. It satisfies 3x + y <= 14 because 3(3) + 5 = 14, but it does not satisfy x + 2y <= 12 because 3 + 2(5) = 13, which is greater than 12.

Question 6

Minimize C = 5x + 8y subject to x + y >= 12, x >= 4, and y >= 2.

Accepted Answer

The important corner points for the minimum are (4, 8) and (10, 2). The costs are C(4, 8) = 84 and C(10, 2) = 66. The minimum value is 66 at (10, 2).

Question 7

A feasible region is in the first quadrant, below the line y = 12 - 2x, and below the line y = 6 - 0.5x. Write the system of inequalities.

Accepted Answer

The system is x >= 0, y >= 0, y <= 12 - 2x, and y <= 6 - 0.5x. The first two inequalities place the region in the first quadrant, and the last two describe being below each line.

Question 8

For the system x >= 0, y >= 0, y <= 12 - 2x, and y <= 6 - 0.5x, find the vertices of the feasible region.

Accepted Answer

The vertices are (0, 0), (6, 0), (4, 4), and (0, 6). The point (4, 4) is the intersection of y = 12 - 2x and y = 6 - 0.5x.

Question 9

Use the feasible region from problem 8 to maximize R = 40x + 30y.

Accepted Answer

Evaluate the objective function at the vertices: R(0, 0) = 0, R(6, 0) = 240, R(4, 4) = 280, and R(0, 6) = 180. The maximum value is 280 at (4, 4).

Question 10

Explain why linear programming problems usually test only the vertices of a bounded feasible region when finding a maximum or minimum.

Accepted Answer

A linear objective function changes at a constant rate, so its largest or smallest value over a bounded polygonal feasible region occurs at a vertex or along an edge between two vertices. Testing the vertices is enough to find the optimal value.

Question 11

A meal plan uses food A and food B. Let x be servings of food A and y be servings of food B. Food A has 2 units of protein and 1 unit of fiber per serving. Food B has 1 unit of protein and 2 units of fiber per serving. The plan needs at least 10 units of protein and at least 8 units of fiber. Food A costs $3 per serving and food B costs $2 per serving. Write the linear programming model and find the minimum cost.

Accepted Answer

The constraints are 2x + y >= 10, x + 2y >= 8, x >= 0, and y >= 0. The objective function is minimize C = 3x + 2y. The key vertices are (0, 10), (4, 2), and (8, 0), with costs $20, $16, and $24. The minimum cost is $16 at 4 servings of food A and 2 servings of food B.

Question 12

A linear programming solution for a transportation plan gives x = 2.5 buses and y = 4 vans. Explain why this may not be a usable final answer and what should be done next.

Accepted Answer

This may not be a usable final answer because a plan cannot use 2.5 buses if buses must be counted as whole vehicles. The problem should be treated as an integer programming problem, and nearby feasible whole-number solutions should be tested to find the best practical answer.

Linear Programming and Optimization

Related Cheat Sheets

More Math Worksheets

More Grade 9-12 Worksheets