General Dual Problems

Section 7.3 General Dual Problems

Because of the equality constraints and the free variables, dual problems take on a different form.

In Chapter 6, we made an argument to develop a bound on the objective function resulting a dual problem. In the case of general problems with equality constraints and free variables, we repeat these steps. Let’s look at Problem 7.1.1. Let’s start with the objective function and then apply steps to verify that the weak duality theorem works for this.

🔗

\begin{align} z = \; \amp \; 5x_1 + 3x_2 \tag{7.3.1}\\ \leq \; \amp \; (y_1 + 2y_2 -2y_3) x_1 + 3x_2 \tag{7.3.2}\\ \leq \; \amp \; (y_1 + 2y_2 -2y_3) x_1 + (y_1 - 3y_2 + y_3)x_2 \tag{7.3.3}\\ = \; \amp \; (x_1 + x_2) y_1 + (2x_1 -3x_2) y_2 + (-2x_1 + x_2)y_3\tag{7.3.4}\\ \leq \; \amp \; 6y_1 + (2x_1 -3x_2) y_2 + (-2x_1 + x_2)y_3\tag{7.3.5}\\ \leq \; \amp \; 6y_1 + 12 y_2 + (-2x_1 + x_2)y_3\tag{7.3.6}\\ \leq \; \amp \; 6y_1 + 12 y_2 -2 y_3\tag{7.3.7}\\ = \; \amp \; w \tag{7.3.8} \end{align}

🔗

To ensure that every step satisifies the \(\geq\) inequality, then we need to be careful with some of the steps. For example, since \(x_1 \geq 0\text{,}\) then (7.3.2) would require that \(y_1 +2y_2 - 2y_3 \geq 5\text{.}\)

🔗

However for the step in (7.3.3), because \(x_2\) is free, it is important that \(y_1 -3y_2 + y_3 = 3\text{.}\) Because of the inequality in the first two constraints in (7.1.1), in order for the \(\leq\) constraints in steps (7.3.5) and (7.3.6), then it is important that \(y_1 \geq 0\) and \(y_2 \geq 0\text{.}\)

🔗

However, if we look at step (7.3.7), since we have the equality constraint, \(-2x_1+x_2 = -2\text{,}\) then \(y_3\) can be a free variable. Putting this all together will result in the dual problem:

🔗

\begin{equation} \begin{aligned} \text{Minimize} \amp \amp w = 6y_1 + 12y_2 - 2y_3, \amp \\ \amp \amp y_1 + 2y_2 -2y_3 \amp \geq 5, \\ \amp \amp y_1 -3 y_2 + y_3 \amp = 3, \\ \text{and} \amp \amp y_1, y_2 \geq 0. \end{aligned}\tag{7.3.9} \end{equation}

🔗

Checkpoint 7.3.1.

Solve (7.3.9) using Phase 0, I, II as needed.

🔗

Solution.

First, we need to switch the inequality on the first inequality or \(-y_1 - 2y_2 + 2y_3 \leq -5\) and then we let \(z = -w = -6y_1 - 12y_2 + 2y_3\text{.}\) Adding only a slack variable to the inequality, the tableau can be written

\begin{equation*} \begin{aligned} \amp \phantom{xxxxxxxxxxi} f \\ \amp \left[\begin{array}{rrr|rr|r} -1 \amp -2 \amp 2 \amp 1 \amp 0 \amp -5\\ 1 \amp -3 \amp 1 \amp 0 \amp 0 \amp 3\\ \hline 6 \amp 12 \amp -2 \amp 0 \amp 1 \amp 0\\ \end{array} \right] \end{aligned} \end{equation*}

🔗

Since there is a free variable \(y_3\) which is not in the basis, then we pivot to bring it into the basis. We’ll use the second line (the equation) to do this.

\begin{equation*} \begin{aligned} \amp \phantom{xxxxxxxxx} f \\ \text{piv}(2,3)\qquad \amp \left[\begin{array}{rrr|rr|r} -3 \amp 4 \amp 0 \amp 1 \amp 0 \amp -11\\ 1 \amp -3 \amp 1 \amp 0 \amp 0 \amp 3\\ \hline 8 \amp 6 \amp 0 \amp 0 \amp 1 \amp 6\\ \end{array} \right] \end{aligned} \end{equation*}

🔗

This is now in phase I, so we pivot to make it feasible:

\begin{equation*} \begin{aligned} \amp \phantom{xxxxxxxi} f \\ 1 \mapsto 4\qquad \amp \left[\begin{array}{rrr|rr|r} 3 \amp -4 \amp 0 \amp -1 \amp 0 \amp 11\\ 0 \amp -5 \amp 3 \amp 1 \amp 0 \amp -2\\ \hline 0 \amp 50 \amp 0 \amp 8 \amp 3 \amp -70\\ \end{array} \right] \end{aligned} \end{equation*}

🔗

This might seem like it is still in phase I, however, since \(x_3\) is free, it can be negative, so we are done with phase I. The solution to this is

\begin{equation} \begin{aligned} \boldsymbol{y} \amp = \frac{1}{3}\left[ \begin{array}{rrr|r} 11 \amp 0 \amp -2 \amp 0 \end{array}\right] \\ \amp =\left[ \begin{array}{rrr|r} 11/3 \amp 0 \amp -2/3 \amp 0 \end{array}\right] \end{aligned}\tag{7.3.10} \end{equation}

with \(z = -70/3\) so \(w = 70/3\text{.}\)

🔗

Checkpoint 7.3.2.

Compare the final tableau in Subsection 7.1.3 in (7.1.4) to the final tableau in (7.3.10). Do the dual solutions appear in the primal problem?

🔗

Solution.

Notice that the objective row in (7.1.4) is

\begin{equation*} \frac{1}{3} \left[\begin{array}{rr|rr} 0 \amp 0 \amp 11 \amp 0 \end{array} \right] \end{equation*}

🔗

which corresponds to the first two values, \(y_1, y_2\) of the dual solution. Note that \(y_3\) is a free variable, so doesn’t have a related slack variable.

🔗

Prev Top Next