Linear Programming Solver

Solve linear programming problems online using the simplex method. Supports maximize or minimize objectives, mixed ≤/≥/= constraints, up to 8 decision variables, and for 2-variable LPs shows an interactive feasible-region plot with every vertex and the optimum highlighted.

Embed Linear Programming Solver Widget

About Linear Programming Solver

The Linear Programming Solver is an online calculator that finds the maximum or minimum of a linear objective function subject to a system of linear inequalities or equalities. It uses the simplex method (Big-M variant) so that <=, >=, and = constraints can be mixed freely, and for 2-variable problems it draws an interactive feasible-region plot with every vertex and the optimum highlighted.

What Is Linear Programming?

A linear programming (LP) problem asks:

Maximize (or minimize): Z = c₁ x₁ + c₂ x₂ + … + c_n x_n subject to: a₁₁ x₁ + … + a_1n x_n (≤, ≥, or =) b₁ a₂₁ x₁ + … + a_2n x_n (≤, ≥, or =) b₂ … a_m1 x₁ + … + a_mn x_n (≤, ≥, or =) b_m x₁, x₂, …, x_n ≥ 0

The set of points satisfying every constraint is called the feasible region, a convex polyhedron. The Fundamental Theorem of Linear Programming states that if the LP has a finite optimum, it is attained at a vertex (extreme point) of this polyhedron. This is why the simplex method — which walks from vertex to vertex — is so effective.

How the Simplex Method Works

Starting from a feasible vertex, the simplex method repeatedly improves the objective by pivoting to a neighboring vertex with a better value. The mechanics:

Standard form: convert the LP to max c^Tx subject to Ax = b, x ≥ 0. For <= constraints, add slack variables; for >=, subtract a surplus and add an artificial with a large penalty −M; for equalities, add an artificial.
Initial tableau: the basis consists of slacks and artificials, which gives an obvious starting vertex.
Entering variable: pick the non-basic variable with the largest positive reduced cost $ c_j - z_j $. If no such variable exists, the current solution is optimal.
Leaving variable: from the entering column, do the min-ratio test — divide each row's RHS by its positive entry in the entering column, and pick the row with the smallest ratio. If no positive entry exists, the LP is unbounded.
Pivot: use Gaussian elimination to make the entering column a unit vector, with 1 in the leaving row.
Repeat until the stopping criterion is met.

If any artificial variable remains in the basis with a positive value at termination, the original LP is infeasible.

Graphical Method (for 2 Variables)

For two-variable problems the feasible region is a 2-D convex polygon. Since the optimum is always at a vertex, enumerating every vertex and evaluating the objective there is enough to solve the problem. This calculator performs that enumeration by intersecting every pair of constraint boundaries, keeping only intersections that satisfy all other constraints, and sorting them counterclockwise for the visualization.

Input Syntax

Write the objective on the first line, then one constraint per line. Variable names can be any identifier (x, y, x1, profit…). Operators are <=, >=, and =. Non-negativity can be written as x, y >= 0 as a shortcut.

Maximize 3x + 5y x + y <= 10 2x + y <= 16 x + 3y <= 18 x, y >= 0

Blank lines and comments beginning with # are ignored. The solver accepts up to 8 decision variables and 20 constraints.

Worked Example

Consider a furniture workshop that builds tables and chairs. Each table yields \\$3 of profit and requires 1 unit of wood and 2 units of labor. Each chair yields \\$5 of profit and requires 1 unit of wood, 1 unit of labor, and 3 units of varnish. Available: 10 wood, 16 labor, 18 varnish. With x = tables and y = chairs, the LP is:

Maximize Z = 3x + 5y x + y <= 10 (wood) 2x + y <= 16 (labor) x + 3y <= 18 (varnish) x, y >= 0

The feasible region is a pentagon. Evaluating Z at each vertex:

Vertex (x, y)	Z = 3x + 5y	Feasible?
(0, 0)	0	Yes
(8, 0)	24	Yes
(6, 4)	38 ← optimum	Yes
(0, 6)	30	Yes

So the workshop should build 6 tables and 4 chairs for a maximum profit of \\$38. The wood and labor constraints are binding (they equal their RHS at the optimum); varnish has a slack of 0 (also binding in this case), meaning all three resources are exhausted.

Common Pitfalls & What the Solver Detects

Situation	Symptom	How to fix
Unbounded LP	Solver reports "Unbounded"	Add a missing upper bound. Objective can grow without limit because the feasible region extends infinitely in the improving direction.
Infeasible LP	Solver reports "Infeasible"	Constraints contradict one another (e.g. `x >= 10` with `x <= 5`). Review every pair of bounds.
Alternate optima	Warning badge; optimal vertex unique but Z is achieved along an edge	Happens when the objective vector is parallel to a binding edge. Any convex combination of the two vertices on that edge is also optimal.
Degeneracy / cycling	Simplex iterates without improving Z	Rare in textbook problems; can be resolved with Bland's rule or perturbation. This solver caps iterations to avoid infinite loops.

Applications

Product mix & production planning — how many of each product to make for maximum profit under resource limits.
Diet & blending problems — minimize cost of a diet or feed that still meets nutritional minima.
Transportation & assignment — minimize shipping cost when supply and demand must balance.
Portfolio optimization — maximize expected return under risk or exposure constraints (linearized).
Network flow — max-flow and min-cost flow reduce to LPs with totally unimodular coefficient matrices.
Scheduling — workforce rostering with shift requirements and total-hour bounds.

How to Use This Calculator

Type your LP in the text box. The first line must begin with Maximize or Minimize. Each following line is one constraint, one per line.
Use the shortcut x, y >= 0 to declare non-negativity for all listed variables at once.
Click Solve LP Problem. The solver reports the optimal value Z, the optimal values of every decision variable, a list of binding constraints, and for 2-variable LPs an interactive feasible-region plot.
Hover a vertex in the plot to see its coordinates and Z value. The optimum is highlighted with a star.
Review the simplex tableaux to see every pivot and trace how the method improves Z. The entering column is highlighted in amber; the leaving row in red.

Frequently Asked Questions

What is a linear programming problem?

A linear programming (LP) problem asks for the maximum or minimum of a linear objective function over a set of decision variables that satisfy a system of linear inequalities or equalities. The feasible set is a convex polyhedron, and the optimum is always attained at one of its vertices — the key fact the simplex method exploits.

How does the simplex method work?

The simplex method walks along vertices of the feasible polyhedron. Each step (a "pivot") exchanges one variable in the basis for another, moving to a neighboring vertex with a strictly better objective. The algorithm stops when no pivot can improve Z — the current vertex is then optimal. This tool uses the Big-M variant so that <=, >=, and = constraints can be mixed.

What is the feasible region?

The feasible region is the set of all variable values satisfying every constraint simultaneously. For 2 variables it is a 2-D convex polygon; for n variables it is an n-dimensional polyhedron. An empty polyhedron means the LP is infeasible; a polyhedron that extends infinitely in the improving direction means the LP is unbounded.

What does "unbounded" mean in linear programming?

An LP is unbounded when the feasible region stretches to infinity in a direction where the objective keeps improving. For example, Maximize x subject only to x ≥ 0 has no finite maximum. Real-world LPs that return unbounded usually reveal a missing constraint — often an upper bound on a resource or variable.

What does "alternate optima" mean?

Alternate optima occur when more than one point attains the same best objective value. Geometrically, the objective is parallel to a binding edge of the polygon, so every point along that edge — and every convex combination of its endpoints — is optimal. The solver flags this when any non-basic decision variable has a reduced cost of zero at termination.

How many variables and constraints does the solver accept?

Up to 8 decision variables and 20 constraints. The interactive feasible-region plot is drawn only for 2-variable problems; with 3 or more variables you still get the full numerical simplex solution, step-by-step tableaux, and binding-constraint report.

Linear Programming Solver

About Linear Programming Solver

What Is Linear Programming?

How the Simplex Method Works

Graphical Method (for 2 Variables)

Input Syntax

Worked Example

Common Pitfalls & What the Solver Detects

Applications

How to Use This Calculator

Frequently Asked Questions

What is a linear programming problem?

How does the simplex method work?

What is the feasible region?

What does "unbounded" mean in linear programming?

What does "alternate optima" mean?

How many variables and constraints does the solver accept?

Further Reading

Advanced Math Operations:

Top & Updated: