Linear Programming Calculator

Find the best feasible allocation and see what limits it. Compare one changed requirement, inspect exact simplex steps, and explore the evidence behind optimal, infeasible or unbounded results.

Linear programming workspace

Find the best plan within your limits.

Optimal objective 10. Unique best plan.

Maximum objective

10

Unique best plan, with an exact proof.

x
2
y
2

Your objective

Added to the objective; it does not change the best allocation.

For example: points, dollars, or hours.

Use consistent units. This model permits fractional quantities; it does not enforce whole-number decisions.

Decision variables (2/6)

Contribution from one unit of x. Enter 0 if it contributes nothing directly.

Bounds for x

With both bounds off, this variable may be any real value, including negative values. Turning a bound off retains its draft.

x (x)

Objective coefficient: 3

y (y)

Objective coefficient: 2

Constraints (3/12)

x

y

Total (sum)

1·x + 1·y ≤ 4

x capacity (xCap)

1·x + 0·y ≤ 2

y capacity (yCap)

0·x + 1·y ≤ 3

Import or save the complete problem

Use the complete-problem template below, with one record per objective, variable, coefficient, constraint or optional inspection. Import validates the whole plan before replacing it.

The exact 15-column header is required. Up to 120 records and 100,000 characters. Empty active numeric cells are errors. The generated template uses an explicit text-encoding record so leading apostrophes and spreadsheet formula text round-trip safely.

Selectable problem CSV
Supported numbers and calculation limits

Enter signed decimals, scientific notation such as 1.2e-7, or an integer fraction such as -7/12 using a normal keyboard minus. Expressions, grouped numbers, percentages and infinity are not accepted.

Authored values permit 24 significant digits, at most 300 characters and explicit exponents from −100 to 100. A nonzero magnitude must be between 1e−100 and 1e100; a reduced numerator and denominator may each have up to 128 digits.

Exact rational arithmetic determines all feasibility tests and pivot choices. Derived results may exceed the input range. Approximate scientific values are labeled; they never change an exact sign or equality.

Each main solve has a 512-pivot and 2,000,000-operation budget, with additional digit, gcd and trace limits. Optimal-coordinate ranges have a separate shared budget. Reaching a limit is reported explicitly and is not proof that a problem is infeasible or unbounded.

Feasible region & best plans

The green area contains the feasible points in this window. Gold highlights the visible optimal set. Dashed borders are window cuts. Each axis is scaled independently.

Horizontal: x (x)Vertical: y (y)
-3/103/233/10-1/5111/5

Horizontal range: -1/5 to 11/5

Vertical range: -3/10 to 33/10

Feasible setOptimal setObjective levelPhase II path□ Selected point
  • This is the exact feasible set clipped to the displayed window, not a statement that the full region is bounded.
  • Phase I points are not shown as feasible allocations. Original variable axes can use different scales.

x = 2; y = 2.

feasible-window; chosen-optimum; optimal-face; phase-two-path

Exact graph points and their roles
Window intersections are drawing points; inspect a point to check every condition.
PointxyRole and visibility
103feasible-window. Inside window.
200feasible-window; phase-two-path. Inside window.
320feasible-window; phase-two-path. Inside window.
422feasible-window; chosen-optimum; optimal-face; phase-two-path. Inside window.
513feasible-window. Inside window.
611/5Approx. 2.2e09/5Approx. 1.8e0boundary:c:sum:+. Inside window.
77/10Approx. 7e-133/10Approx. 3.3e0boundary:c:sum:+. Inside window.
82-3/10Approx. -3e-1boundary:c:xCap:+. Inside window.
9233/10Approx. 3.3e0boundary:c:xCap:+. Inside window.
10-1/5Approx. -2e-13boundary:c:yCap:+. Inside window.
1111/5Approx. 2.2e03boundary:c:yCap:+. Inside window.
120-3/10Approx. -3e-1boundary:b:x:lower. Inside window.
13033/10Approx. 3.3e0boundary:b:x:lower. Inside window.
14-1/5Approx. -2e-10boundary:b:y:lower. Inside window.
1511/5Approx. 2.2e00boundary:b:y:lower. Inside window.
1611/5Approx. 2.2e017/10Approx. 1.7e0objective-level. Inside window.
1717/15Approx. 1.1333333333333333e033/10Approx. 3.3e0objective-level. Inside window.
Set the graph window

Minimum must be below maximum. Decimals, scientific notation and integer fractions are supported. Turning this option off restores the automatic window and retains your draft. The drawn window does not determine feasibility or whether an objective is bounded.

What if a constraint changes?

Replace one right-hand side and solve the full problem again.

Turning the option off keeps its draft. A changed RHS is re-solved; the tool does not assume a fixed marginal value applies to every change.

Inspect a proposed plan

Which constraints matter?

Exact activity at the reported best plan. Binding conditions have no remaining slack.

Base plan: exact activity for every entered condition and finite bound.
ConditionLeft sideRelationRight sideSlackStatus
Total4≤40Binding
x capacity2≤20Binding
y capacity2≤31Satisfied, with slack
x lower bound2≥02Satisfied, with slack
y lower bound2≥02Satisfied, with slack
Is this the only best plan?

This is the unique best plan: each original variable has the same minimum and maximum across the entire optimal set.

Coordinate ranges on the optimal set; endpoints from different rows need not form one feasible plan.
VariableMinimumMaximum
x22
y22

All original-coordinate range problems completed. Range witnesses and proof details are included in the complete report.

Follow the simplex method, step by step

Phase I finds a feasible starting point. Artificial variables are then removed, and Phase II optimizes your objective. Exact ties use Bland’s smallest-index rule. The tableau below is the state after the selected event.

7 of 7

Primal feasibility and an equal original-variable dual bound certify this optimum.

Canonical minimization objective: -10 (your maximization objective is negated internally)

Original feasible point: x=2; y=2

How your variables become standard form

x uses lower shift; the original variable is recovered exactly.

y uses lower shift; the original variable is recovered exactly.

Internal structural, slack, surplus and artificial variables support the algorithm. The plan, proof and optimal ranges above all use your original variables.

Why this result is proved

The plan satisfies every constraint and bound. A nonnegative weighted sum of those conditions proves that no feasible plan has a better objective. The plan and this bound have exactly the same value.

Plan objective = proven objective bound = 10.

Original conditions written as Gx ≤ h. An equality contributes both signs; finite variable bounds are included.
ConditionCoefficients in variable orderUpper bound hWeight λ
Total c:sum:+1, 142
x capacity c:xCap:+1, 021
y capacity c:yCap:+0, 130
x lower bound b:x:lower-1, 000
y lower bound b:y:lower0, -100

Variable order: x, y. The sign σ is +1 for a maximum and −1 for a minimum. The weights satisfy Gᵀλ = σc and λᵀh = σcᵀx. The objective constant is included in the reported bound. Weights alone do not predict the effect of a finite change to a constraint.

Inspect every exact certificate check
Exact arithmetic checks performed before this result is returned.
CheckLeftRelationRightResult
Nonnegative proof weight2>=0Pass
Nonnegative proof weight1>=0Pass
Nonnegative proof weight0>=0Pass
Nonnegative proof weight0>=0Pass
Nonnegative proof weight0>=0Pass
Original condition satisfied0>=0Pass
Original condition satisfied0>=0Pass
Original condition satisfied1>=0Pass
Original condition satisfied2>=0Pass
Original condition satisfied2>=0Pass
Weighted objective coefficient3=3Pass
Weighted objective coefficient2=2Pass
Complementary product0=0Pass
Complementary product0=0Pass
Complementary product0=0Pass
Complementary product0=0Pass
Complementary product0=0Pass
Primal and dual objective equality10=10Pass

Save the complete result

Exact values, transformations, pivot events, certificates, coordinate ranges and enabled comparisons.

Selectable report CSV
Method, assumptions and sources

This workspace solves small continuous linear programs with exact two-phase simplex. It transforms finite bounds, free variables and inequalities into equality form with nonnegative internal variables. Every result is checked again against the original variables and conditions.

It supports one to six real variables and up to twelve entered constraints, plus finite bounds. Strict inequalities, products of variables, integer or binary restrictions are not supported. Fractional quantities are valid; rounding a plan to whole units can make it infeasible or suboptimal.

For two variables, exact clipping shows the portion of the feasible region inside an explicit window. A closed drawing does not prove that the full feasible set is bounded. For other dimensions, use the constraint tables and pivot walkthrough.

Variables are continuous real quantities; fractional plans are not integer solutions.

All feasibility, pivot and certificate decisions use exact rational arithmetic.

User-entered row units must be mutually consistent; no unit conversion is inferred.

The plotted window is not a mathematical bound on the feasible region.

Dual weights certify the entered objective bound; they do not guarantee arbitrary finite-change sensitivity.

Method references: MIT linear programming notes by Michel Goemans; MIT two-phase simplex; MIT linear programming duality.

How to use this calculator

  1. Choose Optimization direction, enter the Constant term and define one to six variables with objective coefficients. Set each Lower bound or Upper bound explicitly; the default lower bound is zero, and disabling both bounds makes a variable free. All variables are continuous.
  2. Enter up to twelve constraint rows with every coefficient, a relation and a right-hand side. Zero entered rows is valid when bounds describe the problem. Alternatively, choose Import format and enter the Complete problem text using the documented CSV/TSV schema, then replace the model only after the whole import validates.
  3. Read the original-variable allocation and objective, or the explanation of infeasibility or an unbounded objective. Inspect active constraints and the exact certificate. A work-limit message leaves the mathematical question unresolved.
  4. For exactly two variables, inspect the feasible plane and selected Phase II step. In other dimensions, use the variable and constraint summaries. Open pivot details for entering/leaving variables, ratio tests and degenerate steps; Phase I has a separate auxiliary objective.
  5. Inspect coordinate ranges for equally good plans. Optionally change one entered constraint RHS or test a complete point while keeping the base problem unchanged. Correct or disable invalid optional checks before complete export; coordinate range endpoints cannot be chosen independently.
  6. Open the exact constraints, certificate and pivot ledger, then request a CSV download or select the same CSV text. Use exact values when rounded chart positions coincide. The imported problem, mathematical result and finite chart window describe different things.

The Formula

The mathematical logic powering this calculation is:

Optimize cᵀx + c₀ over one to six continuous real variables and zero to twelve entered linear constraints. Each constraint uses <=, >= or =; each variable has independently enabled lower and upper bounds. The default lower bound is zero. Disabling both bounds permits negative values. Contradictory well-formed bounds make the problem infeasible; they are not swapped. Units are descriptive labels and must be consistent within each row. Integer/binary variables, strict inequalities and nonlinear expressions are unsupported.
The solver transforms bounds and free variables into a separate nonnegative-variable problem, then uses exact two-phase simplex with Bland's smallest-stable-column rule. Phase I searches for feasibility with artificial variables. Zero artificial basics and redundant rows are removed before Phase II optimizes the original objective. Degenerate pivots can leave the objective unchanged. A Phase I point is not necessarily a feasible original allocation.
Public proofs use original variables in Gx <= h, including finite bounds and both signs of equalities. For σ = +1 on maximization and -1 on minimization, an optimal certificate has λ >= 0, Gᵀλ = σc and λᵀh = σcᵀx with feasible x. The complete objective bound is c₀ + σλᵀh. Infeasibility has λ >= 0, Gᵀλ = 0 and λᵀh < 0. An unbounded objective has feasible x₀ and direction d with Gd <= 0 and σcᵀd > 0. These certificates are checked before solved classifications are returned.
Coordinate minima and maxima on the optimal face distinguish unique from equally good original-variable plans. A zero reduced cost or internal free-variable split direction alone does not prove a different plan. Coordinate ranges are not independent choices that may be combined arbitrarily. Secondary work limits preserve a certified optimum with an explicit unresolved or partial alternatives analysis.
Only two original variables have a feasible-plane visualization. A finite viewport is not a bound, an empty visible window is not proof of infeasibility, and a bounded objective can occur on an unbounded feasible region. Other dimensions use original-variable, constraint and pivot tables. Exact arithmetic decides feasibility, ties and certificates; rounded values and graph coordinates do not.
Authored scalars are signed decimal/scientific atoms or one integer fraction with a positive unsigned denominator. Use ASCII minus. Expressions, grouping commas, percentages, NaN and Infinity are rejected. Inputs allow 300 characters, 24 significant decimal digits after insignificant trailing zeros are removed, explicit exponents from -100 to 100, and reduced rational components up to 128 digits. Nonzero absolute values must be from 1e-100 through 1e100. Derived exact quantities have separate 4,096-digit limits. Main solving allows 512 pivots and 2,000,000 rational operations, with bounded intermediate/gcd/trace work; reaching a limit is unresolved, never a solved mathematical status.
A complete problem can be imported as CSV or TSV with the documented 15-column schema. All coefficients must be present, including zeros. Import is atomic; disabled bound, scenario and inspection drafts are retained without numeric evaluation. Optional enabled scenario or point errors retain the base result but block complete export. One changed RHS is a separately solved scenario, not a global sensitivity range or guaranteed marginal benefit. Exact point inspection uses original variable order and exact rational coordinates. The full input and result exports use their documented schemas and spreadsheet-safe text encoding; this is not a general algebra-text importer.

Worked Example

If you input:

  • Import format: CSV (comma separated)
  • Complete problem text: record_type,id,label,sense,variable_id,coefficient,relation,rhs,lower_enabled,lower,upper_enabled,upper,value,enabled,unit objective,,,max,,,,,,,,,0,, variable,x,x,,,,,,true,0,false,0,,, objective_coefficient,,,,x,3,,,,,,,,, variable,y,y,,,,,,true,0,false,0,,, objective_coefficient,,,,y,2,,,,,,,,, constraint,sum,Total,,,,<=,4,,,,,,, constraint_coefficient,sum,,,x,1,,,,,,,,, constraint_coefficient,sum,,,y,1,,,,,,,,, constraint,xCap,x capacity,,,,<=,2,,,,,,, constraint_coefficient,xCap,,,x,1,,,,,,,,, constraint_coefficient,xCap,,,y,0,,,,,,,,, constraint,yCap,y capacity,,,,<=,3,,,,,,, constraint_coefficient,yCap,,,x,0,,,,,,,,, constraint_coefficient,yCap,,,y,1,,,,,,,,, scenario,sum,,,,,,5,,,,,,false, inspection,,,,,,,,,,,,authored,false, inspection_value,,,,x,,,,,,,,0,, inspection_value,,,,y,,,,,,,,0,,

Result:

Maximize 3x + 2y with x + y <= 4, x <= 2, y <= 3 and lower bounds zero. The unique allocation is x = 2, y = 2, with objective 10. The three entered-row slacks are 0, 0 and 1. The weighted bound 2(x + y) + x <= 2×4 + 2 = 10 certifies the optimum. The optional scenario and inspection are disabled; their draft values remain in the imported model.

Frequently Asked Questions

What kinds of linear programs are supported?

Use one to six continuous real variables, zero to twelve entered linear constraints, maximization or minimization, an optional constant objective term and independently enabled lower/upper bounds. Relations are <=, >= or =. The default lower bound is zero; disabling both bounds permits negative values. Integer/binary restrictions, strict inequalities, nonlinear expressions and resource calendars are not included. A fractional allocation is a valid continuous result, not an instruction to round to an integer.

Does this actually use the simplex method?

The model uses exact Phase I and Phase II simplex. Phase I finds feasibility with artificial variables where needed, followed by artificial-variable and redundant-row cleanup. Phase II optimizes the entered objective. The pivot ledger records deterministic entering/leaving choices, ratio tests and degenerate steps. Internal shifted or split variables map back to the original variables; a Phase I point may violate the original requirements.

How do infeasible, unbounded and work-limit results differ?

Infeasible means no allocation satisfies every requirement and bound. An unbounded objective has feasible allocations whose objective keeps improving; an unbounded feasible region alone does not imply that. Exact contradiction or improving-ray evidence accompanies solved classifications. A work or precision limit is an unresolved computation, not evidence of infeasibility, unboundedness or uniqueness. The model has explicit input, pivot, arithmetic and trace limits.

How can I check that the answer is optimal?

The model supplies a feasible original-variable allocation and nonnegative weights on normalized inequalities. Their weighted sum gives an objective bound attained by that allocation; minimization uses the corresponding sign convention. Every finite variable bound and both signs of an equality participate. The constant term is included in the complete reported objective and bound. Exact values, not rounded graph positions, support the proof; the proof concerns your entered model, not the realism of its assumptions.

Can there be several equally good plans?

Coordinate ranges on the optimal face identify other original-variable plans with the same objective. Zero reduced cost alone is insufficient. Each endpoint may require other variables to change, so combining every coordinate maximum can be infeasible. An unbounded optimal face can still have a finite objective. If separate range analysis reaches its work limit, the certified optimum remains but unresolved ranges and uniqueness are explicitly marked.

What does changing one right-hand side tell me?

It solves one explicit scenario with a changed entered constraint and compares its status, objective and allocations with the unchanged base. This is not a global sensitivity interval, and a dual weight does not guarantee arbitrary finite changes. A stale constraint or malformed enabled RHS keeps the valid base visible but blocks complete export. Optional point inspection similarly checks a complete allocation against every original requirement and enabled bound.

Why is the feasible-region graph limited to two variables?

A faithful plane represents exactly two original variables. Higher-dimensional models use actual variable/constraint summaries and exact tables instead of an ambiguous projection. A finite window is not a mathematical bound, and an empty visible region does not establish global infeasibility. Close exact points remain separately inspectable even if screen positions coincide. The result export and selectable fallback preserve exact quantities and the stated limitations.

Similar Calculators