Click image to open full size
Linear Programming Cheat Sheet
A printable reference covering objective functions, constraints, feasible regions, vertices, and optimization for linear programming in grades 10-12.
Related Tools
Related Labs
Related Worksheets
Linear programming is a method for finding the best possible value of a linear objective under a set of linear constraints. Students use it to model real limits such as time, money, materials, and production capacity. This cheat sheet helps organize the steps for turning a word problem into inequalities, a graph, and a final decision. It is especially useful for applied math problems involving maximum profit or minimum cost. The core idea is to write an objective function such as P = ax + by, then list constraints as linear inequalities. The solution must come from the feasible region, which is the overlap of all constraint graphs. For two-variable problems, the maximum or minimum value occurs at a vertex of the feasible region when one exists. Testing each vertex in the objective function gives the optimal solution.
Key Facts
- A linear programming objective function has the form Z = ax + by, where Z is the quantity being maximized or minimized.
- A constraint is a linear inequality such as 2x + 3y <= 60 that limits the possible values of the variables.
- Nonnegative variables are usually required, so include x >= 0 and y >= 0 when quantities cannot be negative.
- The feasible region is the set of all points that satisfy every constraint at the same time.
- Boundary lines are found by replacing each inequality sign with an equal sign, such as 2x + 3y = 60.
- For a closed and bounded feasible region, the optimal value occurs at one or more vertices of the region.
- To find the optimum, substitute each vertex into the objective function and compare the resulting values.
- If the feasible region is empty, the linear programming problem has no feasible solution.
Vocabulary
- Linear programming
- A method for maximizing or minimizing a linear objective function subject to linear constraints.
- Objective function
- The formula being optimized, such as P = 40x + 25y for total profit.
- Constraint
- A linear equation or inequality that represents a limit on the possible solutions.
- Feasible region
- The set of all points that satisfy every constraint in the problem.
- Vertex
- A corner point of the feasible region formed by the intersection of boundary lines.
- Optimal solution
- The feasible point or points that give the maximum or minimum value of the objective function.
Common Mistakes to Avoid
- Forgetting nonnegative constraints is wrong because real quantities such as units produced or hours worked usually cannot be less than zero.
- Graphing the boundary line but shading the wrong side is wrong because the feasible region must contain only points that satisfy the inequality.
- Testing only one or two corner points is wrong because the optimum could occur at any vertex of the feasible region.
- Mixing up the objective function and constraints is wrong because the objective is what you optimize, while constraints are the limits you must obey.
- Reporting the best value without the variable values is incomplete because the solution should state both the optimal point and the maximum or minimum result.
Practice Questions
- 1 Maximize P = 5x + 8y subject to x + y <= 10, x <= 6, y <= 7, x >= 0, and y >= 0. Find the optimal point and maximum value.
- 2 A shop sells item x for 20 profit. It can make at most 40 items total, and item y must be no more than 15. Write the objective function and constraints.
- 3 Find all vertices of the feasible region defined by x >= 0, y >= 0, x + 2y <= 8, and 3x + y <= 9.
- 4 Explain why a maximum or minimum in a two-variable linear programming problem is checked at the vertices instead of at every point in the feasible region.