Learning objectives
- Identify the decision variables, objective function and constraints of an optimization problem.
- Draw the feasible region of a two-variable linear program and find its optimum by the corner-point method.
- Recognize infeasible problems, unbounded problems and problems with multiple optimal solutions.
- Explain slack, binding constraints and shadow prices, and how the solution responds to changes.
- Use derivatives to solve geometric optimization problems with a constraint.
- Explain why whole-number problems cannot always be solved by rounding.
What optimization is
Every optimization problem has three parts. The decision variables are the things you can choose, such as how many loaves to bake. The objective function is what you want to make as large or as small as possible, such as profit or cost. The constraints are the limits the choice must respect, such as the flour in stock. A choice that satisfies every constraint is feasible; the best feasible choice is theoptimal solution.
Linear programming
When the objective and every constraint are linear (no powers or products of variables), the problem is alinear program. With two variables it can be solved on a graph:
Maximize Z = 3x + 2y subject to x + y ≤ 4, x ≤ 2, y ≤ 3, x ≥ 0, y ≥ 0.
Each inequality allows the points on one side of a line. The overlap of all the allowed sides is thefeasible region, a polygon. The points where Z takes one value, such as 3x + 2y = 6, form a straightlevel line, and all level lines are parallel. Sliding the level line in the direction that increases Z, the last position that still touches the region gives the maximum: here Z = 10 at the corner (2, 2).
Why the answer is at a corner
Because the level lines are straight and parallel, the last point of a polygon they touch is a corner, or a whole edge if they are parallel to it. This gives the corner-point method: list the corners (intersections of constraint lines that satisfy every constraint), evaluate Z at each, and choose the best.
| Corner | Z = 3x + 2y |
|---|---|
| (0, 0) | 0 |
| (2, 0) | 6 |
| (2, 2) | 10 (maximum) |
| (1, 3) | 9 |
| (0, 3) | 6 |
Real problems have thousands of variables, so computers use the simplex method, which walks from corner to neighbouring corner, always improving, or interior-point methods that cut through the middle of the region.
Infeasible, unbounded and multiple optima
- Infeasible: the constraints contradict each other, so the feasible region is empty. For example x + y ≥ 6 cannot hold if x ≤ 2 and y ≤ 3.
- Unbounded: the region stretches forever in a direction in which the objective keeps improving, so there is no best value. An open region is not enough on its own: minimizing on the same region may still have an answer.
- Multiple optima: the level lines are parallel to an edge on the best side of the region, so every point of that edge is optimal.
Binding constraints and sensitivity
At the optimum, a constraint is binding if it holds with equality: the resource is used up. The unused amount is the slack. In the textbook example, x + y ≤ 4 and x ≤ 2 are binding at (2, 2), while y ≤ 3 has slack 1. Raising a non-binding limit changes nothing; raising a binding limit can improve the result. The change in the best value per extra unit of a limit is the shadow price: here 2 for x + y ≤ 4 and 1 for x ≤ 2, and 0 for y ≤ 3. A shadow price tells a manager what one more unit of a resource is worth, and it stays the same only until a different set of constraints becomes binding.
The objective can change too. The optimal corner stays the same over a range of optimality of each coefficient; outside it, the best plan jumps to a neighbouring corner. These trade-offs show how robust a plan is to price changes.
Optimization with calculus
When the objective is a smooth curve rather than a straight line, the best value of a function f(x) on an interval is at a point where the slope is zero, f′(x) = 0, or at an end of the interval. The usual method is: write the constraint, use it to express the objective in one variable, differentiate, solve f′(x) = 0, and check it is a maximum or minimum (for example with the second derivative).
- Fenced field: with perimeter P, A(x) = x(P/2 − x), so A′(x) = P/2 − 2x = 0 gives x = P/4: a square.
- Open box: cutting squares of side x from an L × W sheet gives V(x) = x(L − 2x)(W − 2x); V′(x) = 0 is a quadratic equation.
- Can: for a fixed volume V, S(r) = 2πr² + 2V/r is smallest when h = 2r.
Computers often optimize numerically instead. Hill climbing (gradient ascent) repeatedly steps in the direction of the slope, with steps that shrink as the slope flattens near the top. The simulator’s Start button runs this search.
Whole-number plans
Many decisions must be whole numbers: crates, trucks, staff. The best corner of the linear program may be fractional, and simply rounding can break a constraint or miss the best whole-number plan. Integer programmingsearches the allowed whole-number points; for small problems you can check the points near the best corner. Its best value can never beat the fractional optimum, which is why the fractional answer is a useful bound.
Formula reference
| Idea | Formula and meaning |
|---|---|
| Linear program | Maximize or minimize Z = c₁x + c₂y subject to aᵢx + bᵢy ≤ (or ≥) cᵢ, x ≥ 0, y ≥ 0 |
| Level line | c₁x + c₂y = k; all level lines are parallel and Z improves in the direction (c₁, c₂) when maximizing |
| Slack | cᵢ − (aᵢx + bᵢy) for a ≤ constraint; zero slack means the constraint is binding |
| Shadow price | Change in the best Z per one-unit increase of a limit cᵢ |
| Stationary point | f′(x) = 0; a maximum if f″(x) < 0, a minimum if f″(x) > 0 |
| Fenced field | A = x(P/2 − x), best x = P/4, A = P²/16 |
| Open box | V = x(L − 2x)(W − 2x), best x = [(L + W) − √(L² − LW + W²)] / 6 |
| Closed can | S = 2πr² + 2V/r, best r = ∛(V/2π), h = 2r |
| Hill climbing | xₙ₊₁ = xₙ + η·f′(xₙ) to maximize (minus to minimize), with a step size η |
Real-world applications
- Manufacturing: choosing a production mix that makes the most profit from limited machines, materials and labour.
- Transport and logistics: airline crew scheduling, delivery routes and shipping goods at least cost.
- Diet and agriculture: the cheapest feed or meal plan that meets nutritional minimums.
- Engineering design: shapes that use the least material for the required strength or capacity.
- Energy: deciding which power stations to run to meet demand at least cost.
- Machine learning: training a model means minimizing an error function, usually by gradient descent.
Interesting facts
- Leonid Kantorovich developed linear programming in 1939 to plan production in the Soviet Union, and later shared the 1975 Nobel Memorial Prize in Economics for it.
- George Dantzig invented the simplex method in 1947 while working on planning problems for the US Air Force.
- The famous “diet problem” of finding the cheapest adequate diet was one of the first large problems solved with the simplex method.
- Bees build hexagonal cells; mathematicians proved in 1999 (the honeycomb conjecture) that hexagons divide a plane into equal areas with the least total wall length.
Common misconceptions
- “The best point is in the middle of the region.” For linear objectives it is always on the boundary, at a corner or along an edge.
- “An unbounded region means no optimum.” Only if the objective improves along a direction the region extends in.
- “Every constraint affects the answer.” Non-binding constraints have slack; changing them a little changes nothing.
- “Rounding the best fractional answer gives the best whole-number answer.” It can break a constraint or miss a better point.
- “f′(x) = 0 always gives the maximum.” It can be a minimum or neither, and the best value can be at an end of the interval.
What the simulator simplifies
The linear programs have two variables so they can be drawn; real ones have thousands and are solved by the simplex or interior-point methods rather than by listing corners. Every problem includes x ≥ 0 and y ≥ 0. The shadow price is measured by re-solving with a slightly larger limit, which is exact except at the exact point where the binding constraints change. The geometric models ignore wasted material, seams and thickness, and the challenges assume fixed prices and resource use per unit.
Important terms
- Decision variable
- A quantity you can choose, such as x and y.
- Objective function
- The quantity to maximize or minimize.
- Constraint
- A limit that every allowed choice must satisfy.
- Feasible region
- The set of all choices that satisfy every constraint.
- Corner (vertex)
- A point of the feasible region where two constraint lines meet.
- Binding constraint
- A constraint that holds with equality at the optimum (zero slack).
- Shadow price
- How much the best value changes per extra unit of a limit.
- Infeasible / unbounded
- No allowed choice exists / the objective can improve without limit.
Key takeaways
- Optimization means choosing decision variables to make an objective as good as possible within constraints.
- A linear program’s optimum, if it exists, is at a corner of the feasible region.
- Problems can be infeasible, unbounded or have many optimal solutions.
- Only binding constraints limit the best value; their shadow prices measure how much.
- For smooth objectives, the best value is where the derivative is zero or at an end of the allowed range.