How to use the linear programming solver
- Choose whether to maximize or minimize the objective, and give the variables names if you like, separated by commas.
- Enter the objective coefficients, one per variable, such as 40, 30 for 40 x1 + 30 x2. The example shows a small product mix.
- Add each constraint: its coefficients, whether it is at most, at least or exactly the limit, and the limit itself.
- Read the best plan, the value of the objective, which constraints are binding, and the shadow price of each.
Formula
maximize (or minimize) c1 x1 + c2 x2 + ... + cn xn
subject to a1 x1 + a2 x2 + ... + an xn <= (or >= or =) b for every constraint
all variables x >= 0
shadow price of a constraint = change in the best value when its limit rises by 1
The two phase simplex method moves from corner to corner of the feasible region, always improving the objective, and uses Bland's rule so it can never loop. A first phase finds a feasible corner or shows there is none.
Tables and chairs
Maximize 40 Tables + 30 Chairs, with labor 2 Tables + 1 Chairs <= 100 hours, material 1 Tables + 1 Chairs <= 80 and at most 40 tables. The best plan is 20 tables and 60 chairs for a value of 2,600. Labor and material are both used up, while the table limit has 20 to spare.
The shadow price of labor is 10 and of material is 20. If the same two constraints stay binding, one more labor hour raises the best value by 10 and one more unit of material raises it by 20. The table limit has a shadow price of 0 because it is not binding. For a minimizing example, minimize 2x + 3y with x + y >= 10, x + 3y >= 15 and 2x + y >= 12: the best is x = 7.5 and y = 2.5 for a cost of 22.5.
Reading the result
A binding constraint is one with no room left: it holds the plan back, and loosening it improves the result. A constraint with room left is not limiting anything. Shadow prices rank which limits are worth relaxing, but they only hold for small changes, and at a corner where several constraints meet they may differ depending on which direction you move.
If no values satisfy every constraint at once, the tool says there is no feasible solution. If nothing stops the objective from growing forever, it says the problem is unbounded, which usually means a real limit was left out.
Limits and related tools
All variables can be any non-negative number, including fractions. For whole items, round carefully and check that every constraint still holds. For a system of equations without an objective, use the System of Equations Solver, and to weigh options on several criteria, the Decision Matrix Calculator.
More planning and optimization tools
For related planning and optimization problems, try the NPK Blend Calculator, Knapsack Optimizer and Assignment Optimizer.
Assumptions and limits
- The objective and every constraint are linear, and every variable is zero or more.
- Up to 8 variables and 12 constraints can be entered.
- Coefficients and limits are numbers below 1,000,000,000 in size.
- Example data are shown until you replace them.
Frequently asked questions
What is linear programming used for?
It finds the best use of limited resources when everything is a straight-line relationship, such as the mix of products that earns the most from fixed labor and material.
What is a shadow price?
It is how much the best objective value changes if a constraint's limit rises by one unit, while the same constraints stay binding. A non-binding constraint has a shadow price of zero.
What does infeasible mean?
No set of values satisfies all the constraints together, for example one rule needs a total of at least 10 while another allows at most 5.
What does unbounded mean?
The objective can grow without limit while still meeting every constraint. In real problems this usually means a limit such as capacity or budget is missing.