Linear Programming Solver
Solve a two-variable linear program exactly in rational arithmetic by enumerating the feasible vertices, with infeasibility and unboundedness both refused.
Linear Programming Solver
Solve a two-variable linear program exactly in rational arithmetic by enumerating the feasible vertices, with infeasibility and unboundedness both refused.
How this page computes
Constraints are normalised to a x + b y <= c, and x >= 0 with y >= 0 are added. Every pair of boundary lines is intersected with exact fractions, and a vertex is kept only when it satisfies every constraint.
The objective is evaluated at each kept vertex. The recession cone is then tested along every constraint direction and the axes, so an unbounded objective is detected rather than reported as the best vertex found.
The calculation runs entirely in this browser tab; nothing is uploaded.
The page maximises or minimises a two-variable objective over a region bounded by inequalities. Maximising 3x + 2y subject to 2x + y ≤ 10 and x + 2y ≤ 8 gives 16 at x = 4, y = 2, where both constraints are tight.
The arithmetic is exact rational, not floating point, because the optimum sits exactly where two constraint lines cross and 1/3 is not one third in a double. Each answer is printed as a fraction and as a decimal beside it.
How to use Linear Programming Solver
Write one constraint per line as "2 1 <= 10" — the x and y coefficients, then <= or >=, then the bound. Type the objective as two coefficients and choose maximise or minimise.
Press Run for the optimum and the vertex. The output also names the binding constraints and states that a feasible improving direction was searched for and none found, which is the unboundedness check.
Vertices, and the ray that makes a problem unbounded
The feasible region of a two-variable linear program is a polygon, and a linear objective attains its optimum at a vertex. The page intersects every pair of boundary lines, keeps the intersections that satisfy every constraint, and evaluates the objective at each.
A region can be unbounded, and then no finite optimum exists. The page tests every extreme direction of the recession cone — the directions along each constraint line and the axes — and refuses if one stays feasible while improving the objective.
What to Expect
Best for
- A two-variable linear program with integer or simple fractional data
- Seeing which constraints bind at the optimum
- A worked vertex enumeration
Not ideal for
- Three or more variables, which need a simplex tableau
- Strict inequalities and equalities, which are refused
- Integer programming, where the optimum must be whole
What this tool keeps
- Every coefficient as an exact fraction
What may need cleanup
- Nothing: the optimum is exact
Common errors
- An empty feasible region is refused rather than answered with a nearby point
- An unbounded objective is refused with the improving direction named
- An equality or strict inequality is refused with the spelling to use
Example use cases
- Maximise 3x + 2y subject to two constraints
- Find which constraints bind at the optimum
- See an unbounded program refused
Sample input
objective 3 2, 2 1 <= 10 and 1 2 <= 8, maximise
Sample output
maximum 16 at x = 4, y = 2, with both constraints binding
Who this is for
- Students meeting linear programming
- Readers checking a graphical solution
Frequently asked questions
Why is the optimum at a vertex?
A linear objective has level lines that are straight, so moving the line as far as it can go inside the polygon always ends at a corner. That is why evaluating the vertices finds the optimum.
What does binding mean?
A constraint is binding at a point when it holds with equality there. At the sample optimum both constraints are tight, which is why the vertex is their intersection.
Why does the page refuse an equality?
Because a region bounded by inequalities has an interior, and an equality alone describes a line. Writing the pair of opposite inequalities gives the same set and keeps the vertex method valid.
Build custom tools for your store
Join the SDK program to create useful ecommerce utilities for your store.