Linear programming is a method for maximizing or minimizing a linear objective under linear constraints. Students use it to model decisions about profit, cost, time, resources, and production. This cheat sheet helps organize the setup process, graphing method, and simplex method so problems are easier to solve accurately.
It is especially useful when moving from two-variable graphing problems to larger systems.
Key Facts
- A standard linear programming maximization problem can be written as maximize subject to linear constraints.
- A constraint such as represents a half-plane, and the feasible region is the intersection of all constraint half-planes.
- For a two-variable linear programming problem, an optimum occurs at a vertex of the feasible region when the feasible region is bounded.
- To change into an equation, add a slack variable: , where .
- In a simplex tableau, the entering variable is usually chosen from the most negative coefficient in the objective row for a maximization problem.
- The leaving variable is found by the minimum positive ratio test using positive entries in the entering column.
- A pivot operation makes the pivot entry equal to and all other entries in the pivot column equal to .
- The simplex method stops for a maximization problem when all coefficients in the objective row are nonnegative.
Vocabulary
- Objective function
- The linear expression, such as , that is maximized or minimized.
- Constraint
- A linear equation or inequality, such as , that limits the possible values of the variables.
- Feasible region
- The set of all points that satisfy every constraint, including nonnegativity conditions such as and .
- Slack variable
- A nonnegative variable added to a constraint to convert it into an equation, such as .
- Pivot
- The selected tableau entry used to update rows so one variable enters the solution and another variable leaves.
- Optimal solution
- A feasible solution that gives the greatest or least possible value of the objective function.
Common Mistakes to Avoid
- Forgetting nonnegativity constraints is wrong because linear programming variables often represent real quantities, so conditions like and must be included.
- Testing only one corner point is wrong because the maximum or minimum must be compared across all relevant vertices of the feasible region.
- Using a negative ratio in the simplex ratio test is wrong because the leaving row must keep the solution feasible, so only positive entries in the entering column are allowed.
- Pivoting without first making the pivot entry equal to is wrong because the entering variable column must become a unit column.
- Stopping the simplex method while the objective row still has a negative coefficient is wrong for a maximization problem because the objective value can still improve.
Practice Questions
- 1 Maximize subject to , , , and by checking the vertices.
- 2 Convert the constraints and into equations using slack variables.
- 3 For the entering column values , , and with right-side values , , and , use the ratio test to choose the leaving row.
- 4 Explain why an optimal solution to a bounded two-variable linear programming problem occurs at a vertex instead of in the middle of an edge.
Understanding Linear Programming & Simplex Reference
Every linear programming model begins with decisions that can vary. These are often numbers of items to make, hours to schedule, kilograms to ship, or amounts of ingredients to use. A good model defines each decision in one unit only.
If x means batches of cookies, then every number connected to x must be measured per batch. Unit mistakes are one of the most common errors. A statement such as each batch uses flour and earns profit becomes two separate pieces of information.
One belongs in a resource limit. The other belongs in the quantity being optimized. It helps to make a small table before writing equations, with each decision in a column and each resource in a row.
The graphing method shows why boundary points matter. Each constraint boundary marks the exact point where a limit is fully used. Moving into the allowed side means some resource remains available.
The objective can be imagined as a family of parallel lines. Sliding one of these lines in the improving direction eventually brings it to the last point that still touches the feasible region. That contact is usually a corner because corners are where several limits interact.
Some problems have no feasible region because their conditions conflict. Others are unbounded, meaning improvement can continue without limit. A whole edge can be optimal when the objective line lies parallel to a boundary edge.
Slack variables have a practical meaning beyond being algebra tools. A slack value tells how much of a limited resource is left unused. If a factory has ten unused machine hours, the related slack is ten.
A slack of zero means that constraint is binding, so it actively restricts the best plan. The simplex method tracks these quantities while moving from one corner solution to a better one. Each tableau row represents a resource relationship.
Choosing an entering variable identifies a decision that can improve the current result. The ratio test prevents that decision from increasing past a resource limit.
A pivot then rewrites the system so the new corner becomes the current solution. Careful arithmetic matters because one wrong sign can create an impossible answer.
Linear programming is useful in planning, but it depends on assumptions. It treats relationships as straight line relationships. For example, it assumes that making one more unit always uses the same extra time and earns the same extra amount.
Real businesses may have bulk discounts, overtime pay, changing demand, or limited storage. These effects can require a different model. Standard linear programming can also return fractional answers, such as three and a half buses or twelve point six workers.
Such answers may be acceptable for mixtures and time, but not for indivisible objects. In those cases, students should learn that integer programming adds a whole-number requirement. Always check the final solution against every original condition and explain what each value means in context.