← All Base Form Math projects
BM-19NOT STARTEDBASE FORM · CALCULUSMATHPYTHON

Budget planner

Plan a weekly diet or budget that meets your constraints at the lowest cost, using Lagrange multipliers and a small LP solver.

EST.7 h
REWARD+100 XP
AFTERoriginal

ML-ARENA BENCHMARKS

YOUR NUMBER VS THE INDUSTRY'S
METRICINDUSTRYMINE
optimal cost
GOAL · match within 1e-6
scipy.optimize.linprog—
no results yet
YOUR RESULTS

Your recorded results appear here.

Brief

The diet problem was one of the first problems ever solved by computer: find the cheapest set of foods that meets every nutrient requirement. It is a linear program. The cost is linear in the amounts you buy, and every rule, such as "at least 50 g of protein" or "at most 2,300 mg of sodium", is a linear inequality:

min⁡x c⊤xsubject toAx≤b,  x≥0\min_x\ c^\top x \quad \text{subject to} \quad Ax \le b,\ \ x \ge 0

Each inequality cuts space in half, and the plans that survive every cut form the feasible region. That region is convex: the straight line between any two feasible plans is feasible too. Convexity is why these problems can be solved exactly. There are no false bottoms, so any local minimum is the global one. For a linear cost, the minimum sits at a corner of the region, and the simplex method walks from corner to corner to find it.

Lagrange multipliers tell you what each rule costs. At the optimum, where a constraint g(x)=bg(x) = b is tight, the cost gradient lines up with the constraint gradient: ∇f=λ∇g\nabla f = \lambda \nabla g. The number λ\lambda is the price of that rule, the change in the best cost per extra unit of requirement. LP solvers call these shadow prices.

VISUALFig. 1
cost 13 2x + y ≥ 8 x + 3y ≥ 9 x ≤ 6 y ≤ 5 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 x = units of food A y = food B minimise 3x + 2y feasible: every rule holds cost 9 and cost 20 lines cost 13: last line thatstill touches the region Slide the cost line down until itis about to leave the region.It leaves at a corner. That iswhy LP solvers walk corners.
Two foods, four rules. Lines of equal cost slide toward the feasible region and first touch it at a corner. Why it's here: Objective 2 is exactly this picture. It also shows why the simplex method only needs to visit corners.
HINT · OBJECTIVE 4
Stuck? Hints stay hidden until you ask.

DATA · nutrition or price table

Objectives

0 / 6 CLEARED

Read-only. Log in to update progress.

VICTORY CONDITIONS

  1. Your simplex solver matches `scipy.optimize.linprog` on the full table, with optimal cost within 1e-6. Record your cost with `python tools/mlarena.py record BM-19 "<optimal cost>"`.
  2. Every constraint holds at your solution to within 1e-9, and your solver correctly reports infeasible and unbounded test problems.
  3. Your shadow prices agree with res.ineqlin.marginals, with a one-line meaning for each binding constraint.

Side quests

Whole units only: you can't buy 2.37 cans. Add branch and bound on top of your solver and compare with scipy.optimize.milp.
Add variety rules, such as at most 3 servings of any one food, and see how much the cost moves.

Terms in plain words

Linear program (LP)
Minimise a linear cost subject to linear inequality and equality constraints.
Feasible region
Every plan that satisfies all the constraints. For an LP it is a polygon, or a polytope in more dimensions.
Convex
A set is convex if the straight line between any two of its points stays inside it. In a convex problem, any local minimum is the global minimum.
Lagrange multiplier
The number λ attached to a constraint. At the optimum ∇f = λ∇g, and λ tells you how much the best cost changes if the constraint moves by one unit.
Simplex method
Walks from corner to corner of the feasible region, lowering the cost each time, until no neighbouring corner is cheaper.