Solving a dual linear program using complementary slackness if primal constraints are tight

Question

I have a doubt in the following question:

Consider the linear program

$\min\ \ 5x_1+12x_2 + 4x_3\ \ $, $\ \ $subject to

$x_1+2x_2+x_3 = 10$

$2x_1-x_2+3x_3=8$

$x_1,x_2,x_3 \geq 0$

You are given the information that $x_2$ and $x_3$ are positive in the optimal solution. Use the complementary slackness conditions to find the optimal dual solution.

I'm referred to Problem 1 here to get an idea on how to solve a dual linear program using complementary slackness. Notice that over there, the constraints are all inequalities, so they allow for the possibility of slackness. In fact, the slackness of some constraints is used to conclude that some of the dual constraints are tight, and vice versa.

The problem in the above question is that all constraints are equalities, which means the constraints must be tight! So the procedure detailed in the linked homework solution doc can't be used.

So far what I've done is to use the constraints to express the objective function only in terms of $x_1$ (that's because nothing is specified for $x_1$ of the optimal solution). It turns out to be an increasing function of $x_1$, so I can set $x_1 = 0$ to obtain the primal solution. But I can't understand how exactly to use complementary slackness to get the dual solution in this case. A hint would be appreciated.

Answer 1

First of all the dual program is

\begin{align*} \texttt{Max} \ 10y_1+8y_2 \\ \ \qquad \ y_1+2y_2\leq 5 \\ 2y_1-y_2\leq 12 \\ y_1+3y_2\leq 4 \end{align*}

Using the complementary slackness theorem:

---

$x_j^*\cdot z_j^*=0 \ \forall \ \ j=1,2, \ldots , n \quad\color{blue}{I}$

$y_i^*\cdot s_i^*=0 \ \forall \ \ i=1,2, \ldots , m \quad\color{blue}{II}$

$s_i \text{ are the slack variables of the primal problem.}$

$z_j \text{ are the slack variables of the dual problem.}$

---

We know that that $x_2^*>0$ and $x_3^*>0$. Thus $z_2^*= z_3^*=0$. See $\color{blue}{I}$. That means the constraints $2$ and $3$ are equalities at the dual program.

\begin{align*} 2y_1-y_2= 12 \\ y_1+3y_2= 4 \end{align*}

Solve this little equality system and find $y_1^*$ and $y_2^*$. The values can be insert into the objective function of the dual. This optimal value is equal to the optimal value of the primal problem (Strong duality theorem).

Answer 2

Use the SOB table to organise ideas in a simpler manner.

	variables	constraints, maximizing	constraints, minimizing
sensible	≥ 0	≤	≥
odd	unrestricted	=	=
bizzare	≤ 0	≥	≤

Observe how the table below can be memorised in an intuitive manner from the above table.

	minimization problem		maximization problem
variables	≥ 0 ≤ 0 unrestricted	⇔ ⇔ ⇔	≤ ≥ =	constraints
constraints	≥ ≤ =	⇔ ⇔ ⇔	≥ 0 ≤ 0 unrestricted	variables

In this problem,

• primal equality constraints ("odd") $\implies$ dual unrestricted variables ("odd")
• primal nonnegative ("sensible") variables $\implies$ dual $\le$ ("sensible") constraints
• primal variables $x_2,x_3 > 0 \implies$ dual 2^nd & 3^rd constraints are tight (complementary slackness)

\begin{cases} 2y_1^* - y_2^* &= 12 \\ y_1^* + 3y_2^* &= 4 \end{cases}

This gives $(y_1^*,y_2^*) = (40/7, -4/7)$. The optimal value is $10 y_1^* + 8 y_2^* = (400 - 32)/7 = 368/7$.

---

Check that my work is correct. Set $x_1^* = 0$ and solve the system

\begin{cases} 2x_2^*+x_3^* &= 10 \\ -x_2^*+3x_3^* &= 8. \end{cases}

This gives $(x_1^*, x_2^*) = (22/7, 26/7)$ and the objective value $12 x_1^* + 4 x_2^* = (264 + 104)/7 = 368/7$. From the Weak Duality Theorem, we know that we've obtained optimal solutions for both LP's.