Linear programming calculator

What is linear programming?

Linear programming finds the largest or smallest value of a linear objective, such as profit = 4x + 3y, among all points that satisfy a set of linear constraints, such as hours = 2x + y ≤ 100. The constraints together describe a feasible region, a polygon in the plane when there are two variables. The method on this page is the graphical or corner-point method taught in algebra and finite-math courses.

Why are only the corner points checked?

The objective is a straight-line function, so on any edge of the region it moves steadily in one direction and cannot peak in the middle of the edge. The maximum and the minimum of the objective therefore occur at one or more of the corner points (OpenStax Contemporary Mathematics, section 5.11). When two neighboring corners give the same best value, every point on the edge between them is also optimal.

How do I type the problem?

Type the objective as an expression in x and y, for example 4x + 3y, choose maximize or minimize, then write one constraint per line with ≤, ≥ or =, for example 2x + y <= 100. You may type <= or ≤, fractions like 1/2 and decimals like 0.75, and put x and y on both sides. The names x1 and x2 also work. The conditions x ≥ 0 and y ≥ 0 are added automatically. Strict signs < and > are refused because a strict limit has no best point on its edge.

What does infeasible mean?

It means the constraints contradict each other and no point satisfies all of them. For x + y ≤ 2 together with x + y ≥ 5 the calculator reports infeasible. In a real problem it usually means a demand is larger than the capacity that was entered.

What does unbounded mean?

The feasible region is open on a side where the objective keeps improving, so there is no best value. Maximizing x + y with only x − y ≤ 2 is unbounded: x and y can grow together forever. In an applied problem this almost always signals a missing limit, such as labor, space or demand.

Can the answer need whole numbers?

This calculator solves the continuous problem, so the optimum may be a fraction. Rounding it is not safe. Maximizing 5x + 4y subject to 6x + 4y ≤ 24 and x + 2y ≤ 6 gives x = 3 and y = 3/2 with a value of 21. Rounding the point down to whole numbers gives 19, but the best whole-number plan is (4, 0) with 20. If you need whole items, treat the result as an upper bound and test nearby whole points against every constraint.

Can there be more than one best answer?

Yes. When the objective line is parallel to an edge of the region, two corners tie, and so does every point between them. Maximizing x + y with x + y ≤ 5 and x ≤ 4 is such a case: the value is 5 along a whole edge, and the calculator says “alternate optima”. That is useful news in practice, because you can choose the point that is best on some other criterion.

The four steps

1. Write the objective, for example profit P = 4x + 3y. 2. Write each limit as an inequality in x and y, and add x ≥ 0 and y ≥ 0 because you cannot make a negative amount. 3. Find the corner points: every point where two boundary lines cross and that also satisfies all the other constraints. 4. Evaluate the objective at each corner and pick the largest (or smallest). The calculator does steps 3 and 4 with exact fractions, so a corner with fractional coordinates is not rounded before the comparison.

Worked example: bread and cakes

A bakery earns $4 per loaf of bread (x) and $3 per cake (y). The oven allows 2x + y ≤ 100 units of oven time, the baker’s labor allows x + y ≤ 80, and the shop sells at most 40 loaves, x ≤ 40. The corner points and the profit at each are: (0, 0) gives 0; (40, 0) gives 160; (40, 20) gives 220; (20, 60) gives 260; (0, 80) gives 240. The best is (20, 60) with a profit of $260, where the oven and labor limits are both used up. The feasible region is a closed polygon with 5 corners, so the best value must sit on one of them.

Common mistakes

The most frequent errors are forgetting x ≥ 0 and y ≥ 0 (the calculator adds them, but a hand sketch often does not), turning a ≥ into a ≤ while rearranging, and checking only the corners you can see on a sketch rather than every intersection of two lines. A second trap is the minimum problem with ≥ constraints, where the region is open to the upper right; the minimum exists, but the maximum does not. A third is units: if one constraint is in minutes and another in hours, convert before typing.

Limits of this method

Only two decision variables can be drawn on a plane, so problems with three or more products need the simplex method or a solver, which are outside this page. The objective and every constraint must be linear: no x·y or x² terms and no “either-or” rules. All coefficients are treated as exactly known; a small change in a profit figure can move the optimum from one corner to the next, so check which corners are close in value before you commit. Finally, this is a model: the answer is only as good as the numbers typed in.

Sources: the corner-point theorem and the four-step graphical method as presented in OpenStax, Contemporary Mathematics, section 5.11 “Linear Programming” (only the method is used here; the examples on this page are our own, checked by listing every vertex). Related: system of equations calculator, line equation calculator, inequality solver and matrix calculator.