Skip to content
Tutorials Center
My learning

Topics

Lesson 4 of 38 ยท Getting Started

Standard Form and Slack Variables

Convert any linear program to standard form with slack, surplus and split free variables, then see basic solutions, with a Python converter checked against linprog.

Solvers and textbooks do not work with every possible way of writing an LP. They first convert the model into one fixed shape called standard form, because algorithms such as the simplex method are easiest to describe when every constraint is an equation. This lesson shows the conversions and builds a small converter you will reuse.

What standard form looks like

Standard form (for a minimization) is

TEXT
minimize    c . x
subject to  A x = b
            x >= 0          (and b >= 0)

Every constraint is an equality, every variable is non-negative, and the right-hand side b is non-negative. Other books use maximize instead of minimize or call this equational form; the exact flavor does not matter as long as you convert consistently.

Conversion rules

Original Conversion
Maximize f(x) Minimize -f(x)
a . x <= b Add a slack variable s >= 0: a . x + s = b
a . x >= b Subtract a surplus variable s >= 0: a . x - s = b
Variable x free (any sign) Split x = xโบ - xโป with xโบ, xโป >= 0
Variable with x <= 0 Substitute x = -x' with x' >= 0
Variable with lower bound x >= L Substitute x = L + x', x' >= 0
Negative right-hand side Multiply the whole equation by -1 (flipping the sign of <=/>=)

A slack variable measures unused capacity, exactly the slack you saw in linprog's output. A surplus variable measures how much a >= requirement is exceeded. Neither appears in the objective (their cost is 0).

The bakery in standard form

TEXT
maximize 40x + 30y   ->   minimize -40x - 30y
2x + y + s1       = 100     s1 = unused oven hours
 x + y      + s2  =  80     s2 = unused labor hours
 x               + s3 = 40  s3 = unused flour
x, y, s1, s2, s3 >= 0

Two decision variables became five variables; three inequalities became three equations. The picture is the same, but the algebra is now a linear system with more unknowns (5) than equations (3).

A converter in Python

Python Convert to standard form

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 last three entries of z are the slacks: [0, 0, 20], matching the earlier output. Slack variables turn "how much is left over?" into ordinary decision variables.

Free variables and surplus

Suppose a variable t can be negative, say a temperature change, and one constraint is t + u >= 2. The conversion splits t = tp - tn and subtracts a surplus variable. This code builds that matrix, with columns tp, tn, u, surplus:

Python Free variable and surplus variable

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.

Here |t| is replaced by tp + tn, which equals |t| at the optimum because minimizing never uses both parts at once. Absolute values get a full treatment in modelling tricks.

Basic solutions

In standard form with m equations and n variables (n > m, rows independent), pick m columns of A that form an invertible matrix B. Set the other n - m variables to zero and solve B x_B = b. The result is a basic solution: the chosen variables are basic, the others non-basic. If it also satisfies x >= 0 it is a basic feasible solution (BFS).

The key theorem: basic feasible solutions are exactly the vertices of the feasible region. The bakery has 5 variables and 3 equations, so each BFS fixes 2 variables at 0. For example, x = 0, y = 0 gives slacks 100, 80, 40 (the origin). Setting s1 = 0, s2 = 0 gives (20, 60). The simplex method travels from one BFS to a neighbouring BFS, improving the objective each time.

Python List all basic feasible solutions

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.

You will see five BFS rows (the five corners) and some "basic, infeasible" rows that correspond to intersections outside the region. This is the same enumeration as the graphical method, now done with matrices.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. To convert x + 3y >= 12 to an equation you should

    x + 3y - s = 12 with s >= 0 means the left side exceeds 12 by s.
  2. 2. How is a free variable t represented in standard form?

    The difference of two non-negative variables can take any sign.
  3. 3. An LP in standard form has 3 equations and 5 variables. How many variables are non-basic in a basic solution?

    m = 3 variables are basic; the other n - m = 2 are set to zero.
  4. 4. Basic feasible solutions of the standard form correspond to

    This equivalence between algebra (BFS) and geometry (vertices) is the foundation of the simplex method.

Summary

  • Standard form: minimize c . x subject to A x = b, x >= 0.
  • Add slack for <=, subtract surplus for >=, split free variables, negate to maximize.
  • Slack variables measure unused resources.
  • A basic feasible solution fixes n - m variables at zero and solves for the rest; BFS = vertex.
  • Simplex moves between neighbouring BFS.

Next: Product Mix and Resource Allocation