Back to the on-screen lesson ·
Slacks, surpluses, split free variables and the change of sense that put any program into one shape.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to convert any linear program to standard form by adding a slack to each less-than constraint, subtracting a surplus from each greater-than constraint, splitting each free variable into a difference of two non-negative ones and negating the objective to change its sense, and to say how many variables and equations the result has.
You can write a model as $A$, $b$ and $c$, and you can rearrange an inequality. This lesson is a short list of mechanical rewrites that put any model into the one shape the simplex method is written for.
A slack is a non-negative variable added to a $\le$ constraint to make it an equation. A surplus is subtracted from a $\ge$ constraint for the same reason. A free variable is one the problem allows to be negative. Standard form is a program whose constraints are all equations and whose variables are all non-negative.
The simplex method is written for programs of one shape: minimise (or maximise) $c^{T}x$ subject to $Ax = b$ and $x \ge 0$. Any linear program reaches that shape by four rewrites, none of which changes which plans are feasible or which is best.
A $\le$ row gains a slack: $a^{T}x \le b$ becomes $a^{T}x + s = b$, $s \ge 0$. A $\ge$ row gives up a surplus: $a^{T}x - s = b$. A free variable splits: $y = u - v$ with $u, v \ge 0$. A maximisation becomes a minimisation by negating $c$; the same $x$ wins, and the optimal values differ only in sign.
What none of them can do is impose integrality. That is not an oversight in the list — it is the line between this subject and unit 5.
Another way: steps
Another way: example
$\max 30x_1 + 50x_2$ with $2x_1 + 5x_2 \le 100$ and $3x_1 + 2x_2 \le 60$ becomes $2x_1 + 5x_2 + s_1 = 100$, $3x_1 + 2x_2 + s_2 = 60$, with all four variables non-negative: two equations in four unknowns.
The surplus is the trap. A $\ge$ row needs a variable subtracted, and adding one instead quietly reverses the constraint. The second trap is a free variable handled by adding $y \ge 0$, which forbids answers the original problem allows — the rewrite has to preserve the feasible set exactly, or the answer is to a different question.
$\min 2x_1 + 3x_2$ with $x_1 + 2x_2 \ge 8$ and $3x_1 + x_2 \ge 10$: two $\ge$ rows, so two surpluses.
Requirements point the other way.
$x_1 + 2x_2 - s_1 = 8$ and $3x_1 + x_2 - s_2 = 10$, with every variable non-negative.
Subtract, do not add.
Setting $x = 0$ now gives $s_1 = -8$, which is not allowed — so the slack columns are not a feasible starting basis here. That is what phase one exists for.
Standard form does not guarantee a start.
Write $y = u - v$ with $u, v \ge 0$, so the objective is $4x - u + v$ and the constraint is $x + u - v \le 6$.
Split first.
Then add a slack: $x + u - v + s = 6$, with $x, u, v, s \ge 0$.
A program has $5$ constraints of the form $\le$, $4$ of the form $\ge$ and $1$ equalities. Fill in how many new variables each kind needs.
| New variables | |
|---|---|
| From the $\le$ constraints | |
| From the $\ge$ constraints | |
| From the equalities | |
| New variables in total |
A program has $2$ decision variables, $5$ constraints of the form $\le$ and $2$ of the form $\ge$. How many variables does its standard form have?
Answer:
The wood constraint is $4x + 6y \le 44$. Write its slack $s$ in terms of $x$ and $y$.
Answer:
A program with $8$ variables has one of them, $y$, free: it may come out positive or negative. How does standard form carry it?
In standard form, $7x + 2y + s_1 = k$ and $x + 7y + s_2 = m$. Write the coefficient matrix, columns in the order $x$, $y$, $s_1$, $s_2$.
This task has no paper form; do it on a device.
A minimisation has $5$ variables, of which $1$ are free, and $5$ constraints of the form $\le$ and $1$ of the form $\ge$. Complete the count for its standard form.
After the splits the program has a original variables; adding slacks and surpluses brings it to b variables in c equations.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A program has $2$ constraints of the form $\le$, $3$ of the form $\ge$ and $2$ equalities. Fill in how many new variables each kind needs.
| New variables | |
|---|---|
| From the $\le$ constraints | |
| From the $\ge$ constraints | |
| From the equalities | |
| New variables in total |
You can put any linear program into standard form and count the variables and equations it then has. Say in your own words why a greater-than constraint needs its new variable subtracted rather than added.
7. Your turn: put $\max 4x - y$ subject to $x + y \le 6$, $y$ free, into standard form, step 2