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.
Understanding Linear Programming
The hardest part of linear programming is usually building a model that matches the situation. Start by defining what each variable counts. One variable might represent batches of muffins, while another represents batches of cookies.
Keep the units consistent throughout the problem. If ingredients are measured per batch, the limits must use batches too. A coefficient tells how much one unit uses or produces.
For example, if each muffin batch needs two kilograms of flour, then two times the muffin variable represents flour used by muffins. A small table of resources, amounts per unit, and total limits can prevent many setup mistakes.
Inequality direction comes from the wording of the limit. Phrases such as at most, no more than, and cannot exceed describe an upper limit. Phrases such as at least, no fewer than, and must meet describe a lower limit.
On a graph, the boundary line separates points that meet a condition from points that fail it. A test point helps choose the correct side. The origin is often convenient, unless it lies on the boundary line.
Students should check that the shaded side makes sense in the original context. A production limit should not allow more materials than are available, even if an incorrect graph appears neat.
Vertices matter because they represent situations where important limits meet. At a vertex, a business may be using all of one resource and reaching the limit of another. Moving away from that point changes at least one resource use.
For a linear goal, improvement continues in one direction until a boundary blocks it, which is why a best answer is found at a corner in a bounded region. Sometimes two neighboring vertices give the same best value. Then every point on the line segment between them is equally good.
In other cases, a region can extend forever in the direction that improves the goal. That situation has no finite best value. These cases show why graph shape matters, not just arithmetic.
Real decisions often add details that a basic graph does not show. A model may produce an answer such as three point seven batches, even though only whole batches can be made. Rounding without checking can break a limit or reduce the best result.
Test nearby whole-number choices when the context requires integers. Linear programming also assumes that rates stay constant. It treats each extra unit as using the same amount of time or material as the previous unit.
This may not be realistic when workers earn overtime, bulk discounts apply, or a machine has a setup time. Learning to notice these assumptions helps students decide when a linear model is useful and when it needs adjustment.