2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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).

$\endgroup$
1
$\begingroup$

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

\begin{array}{l|l|l|l} & \text{Variables} & \text{Constraints, Maximizing} & \text{Constraints, Minimizing} \\ \hline \text{Sensible} & \ge 0 & \le & \ge \\ \hline \text{Odd} & \text{Unrestricted} & = & = \\ \hline \text{Bizarre} & \le 0 & \ge & \le \end{array}

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

dual LP table

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 2nd & 3rd 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.

$\endgroup$
  • $\begingroup$ @ShirishKulhari (1) From the context of the question, I assume that all solutions are basic, so that only finitely many solutions are considered. In the primal LP, there're two constraints, so only two of $x_i$'s can be nonzero, so the answer is yes. (2) Complementary slackness. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Mar 28 '18 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.