Linear Programming Solver

About the Linear Programming Solver

Type an objective such as Z = 3x + 5y, choose maximize or minimize, and list the constraints one per line — x + 2y ≤ 14, 3x − y ≥ 0, x + y = 10, even 2 ≤ x ≤ 8. The solver works in exact fractions, so an answer such as x = 2/5 is never rounded to 0.39999.

With two variables it shows the corner-point method taught in school: the graph with every constraint line, the shaded feasible region and its corner points, the value of Z at each corner and the optimum, with the half-plane test when the region is unbounded. For any problem — up to 15 variables and 25 constraints — it runs the simplex method and shows every tableau: the standard form with slack, surplus and artificial variables, both phases of the two-phase method, the entering and leaving variables, the ratio test, the pivot and each row operation. It detects problems with no feasible point, an unbounded objective and multiple optimal solutions, and gives the shadow price of every constraint with the ranges over which the solution stays optimal.

Common uses

• Checking homework and exam answers for the graphical method and the simplex method, tableau by tableau.
• Planning a product mix that maximizes profit within limits on labour, machine time and material.
• Finding the cheapest blend or diet that meets nutrient or quality requirements.
• Reading shadow prices to decide which resource is worth buying more of, and how far the plan holds.
• Teaching how slack, surplus and artificial variables, degeneracy and Bland’s rule work, with exact numbers.

The corner-point method

For two variables, each constraint a·x + b·y ≤ c is a half-plane bounded by the line a·x + b·y = c. The points that satisfy every constraint form the feasible region, a convex polygon or an unbounded convex area. If the objective has an optimum, it is reached at a corner point (a vertex where two boundary lines meet), so it is enough to evaluate Z at every corner, as NCERT Class 12 Mathematics, chapter 12 teaches.

On a bounded region the largest corner value is the maximum and the smallest the minimum. On an unbounded region a corner value M is the maximum only if the open half-plane Z > M has no point in common with the region (for a minimum, Z < m); the solver shows such a point when one exists. When two adjacent corners give the same optimal value, every point of the edge between them is optimal.

The simplex method, step by step

• Standard form. Each ≤ row gets a slack variable (x + 2y + s₁ = 14), each ≥ row a surplus variable and an artificial variable, each = row an artificial variable. A row with a negative right-hand side is first multiplied by −1. A variable that may be negative is written x = x⁺ − x⁻.
• Phase I. When there are artificial variables, the solver maximizes W = −(sum of the artificial variables). If W ends below 0, no point satisfies all constraints. Otherwise the final basis is a feasible point, and any artificial variable still in it at level 0 is pivoted out.
• Phase II. Each tableau’s bottom row holds the reduced costs z_j − c_j. A negative entry can enter the basis; the ratio test (right-hand side ÷ positive column entry, smallest wins) picks the row that leaves; the pivot step divides the pivot row and clears the column. When no reduced cost is negative, the tableau is optimal.
• Minimizing. A minimum of Z is found as the maximum of Z′ = −Z, so the tableaux of a minimization show the row Z′.

The two-phase method and the tableau are described in Dantzig’s Linear Programming and Extensions.

Choosing the entering variable: Dantzig or Bland

Most textbooks bring in the column with the most negative reduced cost (Dantzig’s rule). On degenerate problems that rule can cycle — return to a basis it has seen and never finish. Bland’s rule brings in the lowest-numbered column with a negative reduced cost and, on a tie in the ratio test, removes the basic variable with the lowest number; Bland proved that it never cycles. With the first rule selected, the solver changes to Bland’s rule by itself if a basis repeats, and says so.

Shadow prices and ranges

At the optimum, the shadow price of a constraint is the change in the optimal Z when its right-hand side rises by one unit, read from the final tableau as y = c_B·B⁻¹. It holds while the right-hand side stays in the range shown — beyond it a different corner becomes optimal. A non-binding constraint (one with slack) has shadow price 0. The reduced cost of a variable at 0 says how much Z changes per unit if that variable is forced up, and each objective coefficient has a range over which the same point stays optimal. When the optimum is degenerate (a basic variable equals 0), a shadow price may hold in one direction only.

Limitations

• Up to 15 variables and 25 constraints (an unrestricted variable counts once but takes two columns of the tableau).
• Continuous variables only: the solver does not look for whole-number (integer) solutions.
• Coefficients are read as exact fractions; numbers with more than 30 digits are refused, and so is scientific notation such as 1e5 (type 100000), which could be misread as a variable named e5.
• Shadow prices and ranges are not shown when a constraint repeats others (it is dropped during phase I).
• The graph is drawn for problems with two variables; with more, the simplex tableaux give the answer.

Privacy

On this device: nothing is sent

Everything happens in your browser. What you enter or open here is not uploaded or stored by MySmartCoPilot.