Linear Programming Solver

What Is Linear Programming?

Linear programming (LP) is a mathematical optimization method used to find the best outcome—maximum profit, minimum cost, or optimal resource allocation—in a model where the objective function and all constraints are linear (first-degree) equations or inequalities. The term "programming" refers to planning or scheduling, not computer programming, and dates from the 1940s when George Dantzig developed the simplex algorithm.

Linear programming is the foundation of operations research and is applied in virtually every industry, from airline scheduling and supply chain management to financial portfolio optimization and diet planning. Every LP problem has three components: decision variables (what you control), an objective function (what you optimize), and constraints (what limits your choices).

Objective Function and Constraints

In a 2-variable LP problem, we choose values of x₁ and x₂ to optimize Z = c₁x₁ + c₂x₂, where c₁ and c₂ are the objective coefficients representing profit per unit, cost per unit, or contribution margin. The constraints take the form a₁x₁ + b₁x₂ ≤ (or ≥ or =) RHS, restricting the feasible choices.

Non-negativity constraints (x₁ ≥ 0, x₂ ≥ 0) are typically assumed because decision variables like production quantities, hours worked, or units shipped cannot be negative. These constraints restrict the solution to the first quadrant of the coordinate plane.

The Feasible Region

The feasible region is the set of all points (x₁, x₂) that simultaneously satisfy every constraint in the problem. Graphically, each linear inequality defines a half-plane, and the feasible region is the intersection of all half-planes. If non-negativity constraints are included, the feasible region lies in the first quadrant.

The feasible region can be bounded (a closed polygon, indicating the solution is finite), unbounded (extending to infinity, which may still have an optimal solution depending on the optimization direction), or empty (infeasible, when constraints are contradictory).

The Corner Point (Vertex) Theorem

The most powerful result in linear programming is the Fundamental Theorem of Linear Programming: if an optimal solution exists, at least one optimal solution occurs at a corner point (vertex) of the feasible region. This is because a linear objective function is constant along parallel lines (iso-profit or iso-cost lines), and as you push these lines in the direction of improvement, the last feasible point touched is always a corner of the convex feasible polygon.

This theorem reduces the optimization problem from searching an infinite set of feasible points to evaluating the objective function at a finite number of corner points—making LP computationally tractable. The corner points are found by solving pairs of boundary equations simultaneously, then checking feasibility.

Identifying Corner Points

Corner points arise from intersections of constraint boundary lines with each other and with the axes. For a problem with n constraints plus non-negativity, you compute all pairwise intersections of boundary lines, then filter out any that violate one or more constraints. The surviving feasible intersection points are the vertices of the feasible polygon.

Graphical vs. Simplex Method

The graphical method is intuitive and visual, perfect for 2-variable LP problems. It lets you see the feasible region, corner points, and how the objective function iso-lines move across the feasible set. However, it is strictly limited to two variables—you cannot graph a polytope in more than 3 dimensions.

The simplex algorithm, developed by George Dantzig in 1947, generalizes the corner-point idea algebraically. It starts at a basic feasible solution (a vertex) and moves along an edge to an adjacent better vertex, repeating until no improvement is possible. It handles thousands of variables and constraints efficiently. Modern LP solvers (like the revised simplex, dual simplex, or interior-point methods) can solve problems with millions of variables.

Special Cases in LP

• Infeasible LP: The constraints are contradictory—no point satisfies all of them simultaneously. Example: x + y ≤ 4 and x + y ≥ 6 cannot both be true.
• Unbounded LP: The feasible region extends to infinity and the objective can be improved without limit. For maximization, this means you can always find a better feasible point. Important constraints are likely missing.
• Multiple Optimal Solutions: The objective function iso-line is parallel to a constraint boundary, so an entire edge of the feasible polygon achieves the same optimal Z value. Any point on that edge is equally optimal.
• Degenerate Solutions: More than two constraints are active (binding) at a corner point. This can slow the simplex method but does not affect correctness.

Real-World Applications of Linear Programming

• Production Planning: A manufacturer decides how many units of each product to produce to maximize profit, given limited machine hours, raw materials, and labor.
• Diet and Nutrition: Nutritionists find the minimum-cost meal plan that meets daily requirements for calories, protein, vitamins, and minerals.
• Transportation and Logistics: Shipping companies minimize transportation costs by optimally routing goods from multiple warehouses to multiple customers.
• Portfolio Optimization: Investors maximize expected return subject to risk constraints and budget limits on asset allocations.
• Network Flow: Telecom and utility companies optimize capacity allocation in networks, maximizing throughput or minimizing cost.
• Airline Scheduling: Airlines assign crew and aircraft to routes to minimize costs while satisfying coverage, rest regulations, and demand constraints.

Duality in Linear Programming

Every LP problem (the primal) has a corresponding dual LP problem. If the primal maximizes Z = c·x subject to Ax ≤ b, x ≥ 0, the dual minimizes W = b·y subject to Aᵀy ≥ c, y ≥ 0. The Strong Duality Theorem states that if both are feasible, their optimal values are equal. Dual variables (shadow prices) reveal the marginal value of relaxing each constraint by one unit—a powerful tool for sensitivity analysis and resource valuation.