Linear programming solver (simplex) with graph
Maximise or minimise a linear objective under up to 12 constraints with an exact simplex method, shadow prices and a feasible-region graph.
A clear answer. Here’s how.
Reads each line as a linear constraint (coefficients may be decimals or fractions such as 3/2 x), moves every variable to the left and every constant to the right, and solves with the two-phase simplex method in exact fractions: phase 1 minimises the sum of artificial variables for ≥ and = rows to find a feasible corner, phase 2 optimises the objective. Bland’s rule (the lowest-numbered improving column enters, ties in the ratio test leave by lowest index) guarantees that degenerate problems cannot cycle. The result states whether the problem is optimal, infeasible or unbounded, and flags a degenerate optimum and possible alternative optima. Shadow prices are the dual values y = c_B·B⁻¹: the change in the optimal value per unit increase of a right-hand side; by strong duality Σ yᵢbᵢ equals the optimum. Reduced costs and the range of each objective coefficient over which the final basis stays optimal come from the final tableau (under degeneracy they belong to that basis and may not be unique). For two variables the feasible region is clipped exactly from the half-planes and drawn with each constraint line, the corner points and the objective line through the optimum. Every variable is non-negative; free variables, integer or binary variables, strict inequalities and non-linear terms are not supported.
How this is checked
5 reference checks passed These 5 cases were run when this page was built, on 20 October 2026, and all reproduce within the stated tolerance. The same cases are part of the automated tests that run on every change to Toolmoz. Engine version 1.
See the checks and where each expected answer comes from
Case 1
- Inputs
- The tool’s default inputs
- Expected, and what Toolmoz gave
- Status expected Optimal, Toolmoz OptimalOptimal value expected 180, Toolmoz 180Value of x expected 20, Toolmoz 20Value of y expected 60, Toolmoz 60Shadow price of constraint 1 expected 1, Toolmoz 1Shadow price of constraint 2 expected 1, Toolmoz 1Shadow price of constraint 3 expected 0, Toolmoz 0
- Where the expected answer comes from
- Giapetto’s Woodcarving, Winston, Operations Research (section 3.1): maximum 180 at 20 soldiers and 60 trains, shadow prices 1, 1 and 0; checked by vertex enumeration in Python fractions (raising the first or second right-hand side by 1 gives 181)
- Allowed difference
- exact
Case 2
- Inputs
- Objective 3x + 2yConstraints, one per line x + y <= 4 x + 3y <= 6 x <= 3
- Expected, and what Toolmoz gave
- Status expected Optimal, Toolmoz OptimalOptimal value expected 11, Toolmoz 11Value of x expected 3, Toolmoz 3Value of y expected 1, Toolmoz 1Degenerate vertex expected Yes, Toolmoz Yes
- Where the expected answer comes from
- By hand: corners (0,0) 0, (3,0) 9, (3,1) 11, (0,2) 4; all three constraints meet at (3,1), so the optimum is degenerate
- Allowed difference
- exact
Case 3
- Inputs
- Objective 2x + 3y + 4zConstraints, one per line 3x + 2y + z <= 10 2x + 5y + 3z <= 15
- Expected, and what Toolmoz gave
- Status expected Optimal, Toolmoz OptimalOptimal value expected 20, Toolmoz 20Value of z expected 5, Toolmoz 5Value of x expected 0, Toolmoz 0Value of y expected 0, Toolmoz 0
- Where the expected answer comes from
- Wikipedia, Simplex algorithm, Example 1: maximum Z = 20 at x = y = 0, z = 5
- Allowed difference
- exact
Case 4
- Inputs
- Objective 2x + 3y + 4zConstraints, one per line 3x + 2y + z = 10 2x + 5y + 3z = 15
- Expected, and what Toolmoz gave
- Status expected Optimal, Toolmoz OptimalOptimal value expected 18.571428571428573, Toolmoz 18.571428571428573Value of x expected 2.142857142857143, Toolmoz 2.142857142857143Value of z expected 3.5714285714285716, Toolmoz 3.5714285714285716
- Where the expected answer comes from
- Wikipedia, Simplex algorithm, Example 2 (two-phase, equality constraints): optimum 130/7; the point x = 15/7, y = 0, z = 25/7 from vertex enumeration in Python fractions
- Allowed difference
- ±1e-12 relative
Case 5
- Inputs
- Objective x + yConstraints, one per line x + y <= 1 x + y >= 3
- Expected, and what Toolmoz gave
- Status expected Infeasible, Toolmoz Infeasible
- Where the expected answer comes from
- x + y cannot be at most 1 and at least 3 at once
- Allowed difference
- exact
What this shows: the engine reproduces independently worked values for these cases. It does not prove every possible input is right. To test an answer you were given, see how to check a number; to see what is and is not checked across Toolmoz, see the accuracy ledger.
See a worked example
Worked example
A fixed demonstration, separate from the values you enter above.
- Goal
- Maximise
- Objective
- 3x + 2y
- Constraints, one per line
2x + y <= 100 x + y <= 80 x <= 40
- Table shows
- Solution, slacks and shadow prices
Example result
| Section | Name | Value or left side | Right side | Slack or surplus | Binding | Shadow price | Reduced cost | Objective coefficient | Coefficient range for this basis |
|---|---|---|---|---|---|---|---|---|---|
| Variable | x | 20 | 0 | 3 | [2, 4] | ||||
| Variable | y | 60 | 0 | 2 | [3/2 (≈ 1.5), 3] | ||||
| Constraint (1) | 2x + y <= 100 | 100 | <= 100 | 0 | Yes | 1 | |||
| Constraint (2) | x + y <= 80 | 80 | <= 80 | 0 | Yes | 1 | |||
| Constraint (3) | x <= 40 | 20 | <= 40 | 20 | No | 0 |
Two-phase simplex method in exact fractions with Bland’s rule (lowest index enters and leaves), so degenerate problems cannot cycle. All variables are ≥ 0; free variables, integer constraints and strict inequalities are not supported. Shadow price: the change in the optimal value per unit increase of that right-hand side, while the basis stays the same. Reduced cost: objective coefficient minus the shadow-price-weighted column; it is 0 for variables in the solution. The coefficient range is where the current solution stays optimal with the other coefficients fixed.