Linear Programming Solver

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:

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:

1. 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.
2. Initial tableau: the basis consists of slacks and artificials, which gives an obvious starting vertex.
3. 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.
4. 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.
5. Pivot: use Gaussian elimination to make the entering column a unit vector, with 1 in the leaving row.
6. 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.

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:

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

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

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

1. 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.
2. Use the shortcut x, y >= 0 to declare non-negativity for all listed variables at once.
3. 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.
4. Hover a vertex in the plot to see its coordinates and Z value. The optimum is highlighted with a star.
5. 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.

Further Reading

• Linear programming — Wikipedia
• Simplex algorithm — Wikipedia
• Big M method — Wikipedia
• Duality in optimization — Wikipedia

Related MiniWebtools:

Advanced Math Operations:

• Antilog Calculator
• Beta Function Calculator
• Binomial Coefficient Calculator
• Binomial Probability Distribution Calculator
• Bitwise Calculator Featured
• Central Limit Theorem Calculator
• Combination Calculator
• Complementary Error Function Calculator
• Complex Number Calculator
• Entropy Calculator
• Error Function Calculator
• Exponential Decay Calculator Featured
• Exponential Growth Calculator
• Exponential Integral Calculator
• Exponents Calculator
• Factorial Calculator
• Gamma Function Calculator
• Golden Ratio Calculator
• Half Life Calculator
• Percent Growth Rate Calculator Featured
• Permutation Calculator
• Poisson Distribution Calculator
• Polynomial Roots Calculator
• Probability Calculator
• Probability Distribution Calculator
• Proportion Calculator
• Quadratic Formula Calculator
• Scientific Calculator
• Scientific Notation Calculator
• Significant Figures Calculator New
• Sum of Cubes Calculator
• Sum of Positive Integers Calculator Featured
• Sum of Squares Calculator
• Truth Table Generator New
• Set Theory Calculator New
• Venn Diagram Generator (3 Sets) New
• Chinese Remainder Theorem Calculator New
• Euler's Totient Function Calculator New
• Extended Euclidean Algorithm Calculator New
• Modular Multiplicative Inverse Calculator New
• Continued Fraction Calculator New
• Dijkstra's Shortest Path Calculator New
• Minimum Spanning Tree Calculator New
• Graph Degree Sequence Validator New
• Derangement (Subfactorial) Calculator New
• Stirling Numbers Calculator New
• Pigeonhole Principle Calculator New
• Markov Chain Steady State Calculator New
• Rounding Calculator New
• Negative Binomial Distribution Calculator New
• Permutations with Repetition Calculator New
• Modular Exponentiation Calculator New
• Primitive Root Calculator New
• Boolean Algebra Simplifier New
• Karnaugh Map (K-Map) Solver New
• Graph Coloring Calculator New
• Topological Sort Calculator New
• Adjacency Matrix Calculator New
• Inclusion-Exclusion Calculator New
• Linear Programming Solver New
• Traveling Salesman Solver (TSP) New
• Hamiltonian Path Checker New