Linear Programming and Optimization
Model constraints, find feasible regions, and optimize objective functions
Linear Programming and Optimization
Model constraints, find feasible regions, and optimize objective functions
Math - Grade 9-12
- 1
For the constraints x >= 0, y >= 0, x + y <= 10, and 2x + y <= 14, list the vertices of the feasible region.
Find where each boundary line meets the axes, then find where the two slanted boundary lines intersect.
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. - 2
Use the feasible region from problem 1 to maximize P = 3x + 2y.
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). - 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.
Use one inequality for hours, one inequality for boards, and nonnegative constraints for the number of items.
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. - 4
Solve the workshop problem from problem 3. Find the maximum profit and the number of chairs and tables that give it.
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. - 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.
A point must satisfy every constraint to be feasible.
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. - 6
Minimize C = 5x + 8y subject to x + y >= 12, x >= 4, and y >= 2.
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). - 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.
Being below a line means the inequality uses <= when the equation is solved for y.
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. - 8
For the system x >= 0, y >= 0, y <= 12 - 2x, and y <= 6 - 0.5x, find the vertices of the feasible region.
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. - 9
Use the feasible region from problem 8 to maximize R = 40x + 30y.
For a linear objective function, test the vertices of the feasible region.
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). - 10
Explain why linear programming problems usually test only the vertices of a bounded feasible region when finding a maximum or minimum.
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. - 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.
Because the requirements say at least, the nutrient inequalities use >=.
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. - 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.
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.