Linear Programming: how to write dual problem with slack variables

Question

Lets say I have this primal problem:

maximize $z = 6x_1 + 10x_2$

subject to:

$2x_1+8x_2\leq 60$

$3x_1+5x_2\leq45$

$x_1, x_2 \geq 0$

With slack variables in matrix notation ($Ax=b$) I get:

$A =\begin{pmatrix} 2 & 8 & 1 & 0\\ 3 & 5 & 0 & 1 \end{pmatrix}$

$b =\begin{pmatrix} 60\\ 45 \end{pmatrix}$

$c = \begin{pmatrix} 6\\ 10\\ 0\\ 0 \end{pmatrix}$

$x = \begin{pmatrix} 0\\ 0\\ 60\\ 45 \end{pmatrix}$

But how will this notation look like for the dual problem? The slack variables makes me a bit confussed to be honest.Because for the primal, let us for example add slack variables ($x_3$) to the first constraint:

$2x_1+8x_2 + x_3 = 60$

The first constraint of the dual will however be:

$2y_1+3y_2\geq 6$

If I add a slack variable $y_3$

$2y_1+3y_2 + y_3= 6$

Then the slack variable must be less or equal to zero. A for the dual problem can well not be:

$A =\begin{pmatrix} 2 & 3 & 1 & 0\\ 8 & 5 & 0 & 1 \end{pmatrix}$ ?

Answer 1

When you add slack variables, the dual program isn't affected.

In the original primal program, there are two variables $x_1, x_2$, corresponding to two constraints in the dual; there are two constraints, corresponding to two dual variables which we'll call $u_1$ and $u_2$. Because the constraints are inequalities, $u_1$ and $u_2$ will be nonnegative variables. Here is the primal-dual pair: \begin{array}{rrll rrll} \text{maximize } & 6x_1 + 10x_2 & & & \text{minimize} & 60u_1 + 45u_2 \\ & 2x_1 + 8x_2 & \le 60 & (u_1) & & 2u_1 + 3u_2 & \ge 6 & (x_1) \\ & 3x_1 + 5x_2 & \le 45 & (u_2) & & 8u_1 + 5 u_2 & \ge 10 & (x_2) \\ & x_1, x_2 & \ge 0 & & & u_1, u_2 & \ge 0 \end{array}

When we add slack variables in the primal, two things change. First, the constraints become equations, which means $u_1, u_2$ are now unrestricted variables (with no nonnegativity constraints). Second, there are now two more dual constraints corresponding to the slack variables $s_1$ and $s_2$. Those dual constraints turn out to be exactly the constraints $u_1 \ge 0$ and $u_2 \ge 0$ which we lost from the first change. So we get an identical dual:

\begin{array}{rrll rrll} \text{maximize } & 6x_1 + 10x_2 & & & \text{minimize} & 60u_1 + 45u_2 \\ & 2x_1 + 8x_2 + s_1 & = 60 & (u_1) & & 2u_1 + 3u_2 & \ge 6 & (x_1) \\ & 3x_1 + 5x_2 + s_2 & = 45 & (u_2) & & 8u_1 + 5 u_2 & \ge 10 & (x_2) \\ & x_1, x_2, s_1, s_2 & \ge 0 & & & u_1 & \ge 0 & (s_1) \\ & & & & & u_2 & \ge 0 & (s_2) \end{array}

If you like, you can write both dual programs in matrix notation as $\mathbf u^{\mathsf T}\!A \ge \mathbf c^{\mathsf T}$. This gives us $$ \begin{bmatrix}u_1 & u_2\end{bmatrix} \begin{bmatrix}2 & 3 \\ 8 & 5\end{bmatrix} \ge \begin{bmatrix}6 & 10 \end{bmatrix} $$ in the first dual, and $$ \begin{bmatrix}u_1 & u_2\end{bmatrix} \begin{bmatrix}2 & 3 & 1 & 0 \\ 8 & 5 & 0 & 1\end{bmatrix} \ge \begin{bmatrix}6 & 10 & 0 & 0\end{bmatrix} $$ in the second dual. The change is because in the first dual, we're thinking of $u_1 \ge 0$ and $u_2 \ge 0$ as nonnegativity constraints (treated as a special case), while in the second dual, they are just two linear constraints like any others.

---

We don't typically add slack variables to the dual, but if we did, it would have an identical (but slightly sillier) effect on the primal.

I think the cleanest way to do it is to add a nonpositive slack variable: turn $2u_1 + 3u_2 \ge 6$ into $2u_1 + 3u_2 + w_1 = 6$, where $w_1 \le 0$. A nonpositive slack variable in the dual will correspond to a $\ge$ constraint in the primal, which will replace the nonnegativity constraint on $x_1$. We'll get: \begin{array}{rrll rrll} \text{maximize } & 6x_1 + 10x_2 & & & \text{minimize} & 60u_1 + 45u_2 \\ & 2x_1 + 8x_2 + s_1 & = 60 & (u_1) & & 2u_1 + 3u_2 + w_1 & = 6 & (x_1) \\ & 3x_1 + 5x_2 + s_2 & = 45 & (u_2) & & 8u_1 + 5 u_2 + w_2 & = 10 & (x_2) \\ & x_1 & \ge 0 & (w_1) & & u_1 & \ge 0 & (s_1) \\ & x_2 & \ge 0 & (w_2) & & u_2 & \ge 0 & (s_2) \\ & s_1, s_2 & \ge 0 & & & w_1, w_2 & \le 0 \end{array}

Note that $s_1, s_2$ still have special-cased nonnegativity constraints, just like $w_1, w_2$ still have special-cased nonpositivity constraints.

If we really wanted to do terrible, unnatural things to our primal-dual pair, we could add slack variables to the constraints $x_1 \ge 0, x_2 \ge 0, u_1 \ge 0, u_2 \ge 0$. This would turn the nonnegativity constraints on $s_1, s_2$ and the nonpositivity constraints on $w_1, w_2$ into ordinary constraints, make the matrix even bigger, and add more variables to both programs. You can keep going like this indefinitely, creating bloated primal-dual pairs that are ultimately equivalent to the original.