Skip to content
Tutorials Center
My learning

Topics

Lesson 51 of 62 ยท Applications

Linear Programming: Graphical Method and Simplex

Learn linear programming: write the model, solve it graphically, run the simplex tableau in NumPy and check the answer with scipy.optimize.linprog.

A factory can make two products. Each uses machine time and labor, each earns a different profit, and both resources are limited. How many of each should it build to earn the most? That question, "maximize a linear function of some quantities subject to linear limits", is a linear program (LP). Linear programming schedules airlines, blends fuel, plans diets, routes network traffic and allocates advertising budgets, and it is built entirely out of the matrix ideas from this course: systems of equations, row operations, and bases.

In this lesson you set up an LP, solve a small one by drawing it, understand why the answer always sits at a corner, run the simplex method with a tableau you can follow by hand, and then check everything with scipy.optimize.linprog.

The model

A linear program has three ingredients:

  • Decision variables xโ‚, ..., xโ‚™ (how much of each thing).
  • An objective function to maximize or minimize, linear in the variables: cโ‚xโ‚ + ... + cโ‚™xโ‚™.
  • Constraints, each a linear inequality or equation, plus usually x โ‰ฅ 0.

In matrix form (the standard form for a maximization problem):

TEXT
maximize    cแต€ x
subject to  A x โ‰ค b,    x โ‰ฅ 0

Our running example:

TEXT
maximize    3x + 2y                 (profit)
subject to  x +  y โ‰ค 4              (machine hours)
            x + 3y โ‰ค 6              (labor hours)
            x      โ‰ค 3.5            (material for product x)
            x, y โ‰ฅ 0

The graphical method

With two variables you can draw it. Each inequality describes a half-plane; their intersection is the feasible region, here a convex polygon. The objective 3x + 2y = k is a family of parallel lines, and you slide the line outward (increasing k) until it is about to leave the polygon. The last point touched is the optimum.

Because a linear function on a convex polygon never has its maximum strictly inside, an optimum always occurs at a vertex (corner) of the feasible region, provided one exists. (If the whole top edge is tied, the vertices at its two ends are tied too.) That turns a continuous problem into a finite one: list the vertices and compare. A vertex is where two constraint lines meet, so you find them by solving 2 ร— 2 linear systems and keeping the points that satisfy all other constraints.

Python Graphical method: enumerate the corners of the feasible region

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The corner (3.5, 0.5) earns 11.5, more than any other corner, and no random feasible point beats it. Look at which constraints are active there: x โ‰ค 3.5 and x + y โ‰ค 4 meet at (3.5, 0.5), while the labor constraint x + 3y โ‰ค 6 is not tight (3.5 + 1.5 = 5).

The simplex method

Enumerating all corners works for two variables but explodes in higher dimensions (a problem with 50 variables and 50 constraints has up to C(100, 50) corners). The simplex method walks from corner to neighboring corner, always improving the objective, and stops when no neighbor is better. In practice it finds the optimum in a small number of steps.

The algebra needs equations, so we add slack variables that soak up the unused amount in each constraint: x + y + sโ‚ = 4, x + 3y + sโ‚‚ = 6, x + sโ‚ƒ = 3. Now A x = b is an equation with more unknowns than equations. A basic solution sets all but m variables to zero (the non-basic ones) and solves the square m ร— m system for the basic ones. Corners of the feasible region are exactly the non-negative basic solutions.

Write everything as a tableau: the constraint rows, plus a bottom row for the objective (with -c, so that a negative entry means "increasing this variable improves the profit"). One simplex step:

  1. Choose the entering variable: the most negative entry in the objective row. If there is none, you are optimal.
  2. Choose the leaving variable (ratio test): among rows with a positive entry in the entering column, pick the smallest ratio rhs / entry. That keeps every variable non-negative. If no entry is positive, the problem is unbounded.
  3. Pivot: row-reduce so the entering column becomes a unit column. This is plain Gauss-Jordan elimination.
Python Simplex tableau, one pivot at a time

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The tableau visits a path of corners, (0, 0) then (3.5, 0) then (3.5, 0.5), and stops when the objective row has no negative entries. Each pivot is an ordinary row operation, and each tableau is the system rewritten with a different set of basic variables.

Checking with SciPy

In practice you call a library. scipy.optimize.linprog minimizes by convention, so to maximize cแต€x you minimize -cแต€x and flip the sign of the result. It also reports the status, which distinguishes optimal, infeasible and unbounded problems.

Python linprog: optimal, infeasible and unbounded problems

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The simplex implementation and linprog agree: build 3.5 of the first product and 0.5 of the second, for a profit of 11.5. The machine-hours and material constraints are binding, while labor has one hour left over, so extra labor would not raise the profit and a manager should look at machine time and material instead.

Things to remember

  • Possible outcomes: exactly one of optimal, infeasible (no point satisfies all constraints) or unbounded (the objective can grow forever).
  • Duality: every LP has a dual LP, and the optimal values are equal. The dual variables are shadow prices: how much the profit rises per extra unit of each resource.
  • Integer variables (you cannot build 2.4 cars) make the problem much harder (integer programming). Solving the LP relaxation and rounding is a common first approximation.
  • Large LPs use sparse matrices and interior-point methods, but the picture of corners and basic solutions stays the same.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Where does the optimum of a linear program occur, if one exists?

    A linear function on a convex polygon attains its maximum at a vertex, since sliding the objective line outward last touches a corner (or an edge whose end vertices tie).
  2. 2. What is a slack variable?

    x + y <= 4 becomes x + y + s = 4 with s >= 0. The slack s is the unused amount.
  3. 3. In the simplex method, how do you pick the leaving variable?

    The ratio test keeps all basic variables non-negative after the pivot.
  4. 4. scipy.optimize.linprog minimizes by default. How do you maximize 3x + 2y?

    Maximizing f is the same as minimizing -f, so use c = -[3, 2] and flip the sign of the result.
  5. 5. What does it mean if the simplex method finds a positive entry in no row of the entering column?

    With no positive entries the entering variable can increase forever without breaking any constraint, so the objective is unbounded.

Summary

  • A linear program maximizes (or minimizes) a linear objective cแต€x subject to linear constraints; in standard form it is Ax โ‰ค b, x โ‰ฅ 0.
  • The feasible region is a convex polygon or polytope, and the optimum, if it exists, is at a vertex, so you can list vertices by solving pairs of constraint equations.
  • Simplex adds slack variables and moves between basic solutions with Gauss-Jordan pivots chosen by the entering rule and the ratio test, stopping when the objective row has no negative entry.
  • scipy.optimize.linprog solves LPs (minimizing by default) and reports optimal, infeasible or unbounded status.

Next: Project: Principal Component Analysis, where the covariance matrix and eigenvectors do the work.