Master Linear Programming: Theory, Methods, and Python Implementation

Linear Programming

Linear programming is an optimization problem that seeks to maximize or minimize a linear objective function subject to linear constraints. It can be expressed in standard form with decision variables, objective coefficients, constraint coefficients, and right‑hand side constants.

Solution Methods

Common algorithms include the Simplex Method, Interior‑Point Method, and Branch‑and‑Bound Method.

Simplex Method : an iterative geometric approach that moves from one basic feasible solution to a better adjacent vertex, suitable for small‑scale problems.

Interior‑Point Method : searches within the feasible region, handling large‑scale problems more efficiently but requiring more complex mathematics.

Branch‑and‑Bound Method : recursively splits the problem into sub‑problems, using bounds to prune the search space; effective for larger problems but may explore many nodes.

Example

A typical real‑world LP is a production planning problem where a factory with two lines produces products A and B under capacity and material limits. The goal is to maximize profit.

Standard form (maximization) is converted to a minimization problem for the solver.

Python Solution

Using scipy.optimize.linprog we can solve the example.

<code>from scipy.optimize import linprog

# Define objective coefficients (negative for maximization)
c = [-12, -16]

# Constraint matrix and RHS
A = [[2, 4], [3, 2], [2, 1], [1, 2]]
b = [1000, 1200, 800, 1000]

# Variable bounds
x0_bounds = (0, None)
x1_bounds = (0, None)

# Solve with simplex method
res = linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds], method='simplex')
print(res.fun)
print(res.x)
</code>

The optimal solution is to produce 350 units of product A and 75 units of product B, yielding a profit of 5400.

Key parameters of linprog are:

c: objective coefficients.

A_ub, b_ub: inequality constraint matrix and vector.

A_eq, b_eq: equality constraints (optional).

bounds: variable bounds.

method: solver algorithm ('simplex', 'interior-point', 'highs').

options: solver options.

Note that linprog solves the standard minimization form; maximizing profit requires negating the objective coefficients.