1
$\begingroup$

\begin{array}{c|c|cc} \hline \text{BV}& \text{value} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6\\ \hline x_4 & 8& 2& 3 & 2 & 1 & 0& 0\\ x_5 & 8 &4 & 2 & 1 & 0 & 1 & 0\\ x_6 & 4 & 1 & 1 & 1 & 0 & 0 & 1\\ \hline -z & 0 & 2 & b & 0.5 & 0 & 0 & 0\\\hline \end{array}

Above you can see the tableau representation of a linear program with a coefficient $b\in \mathbb{R}$. BV stands for basic variable.

For which $b$ is $y_1 = \frac12, y_2 = \frac14, y_3 = 0$ a optimal solution of the Dual program of this primal program shown in the tableau?

The strong duality property says that the optimal value of the primal and its Dual program are the same. And the optimal value is $z=8\cdot\frac{1}{2}+8\cdot \frac{1}{4}+4\cdot0=6$. So when I do the primal simplex algorithm of the tableau below, in the end $-z$ has to be $-6$. I did the simplex and got the solution $b=2$. But I think my way is eiher wrong or too long. Can anybody help for a fast way to the solution?

$\endgroup$

1 Answer 1

2
$\begingroup$

The key is complementary slackness condition. Let me state the primal problem for clarity.

\begin{align*} & \max (2,b,0.5) (x_1,x_2,x_3)^T \\ & \mbox{s.t.} \begin{pmatrix} 2 & 3 & 2 \\ 4 & 2 & 1 \\ 1 & 1 & 1 \end{pmatrix} \begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix} \le \begin{pmatrix}8\\8\\4\end{pmatrix} \tag{P} \\ & x_1,x_2,x_3 \ge 0 \\ & \min (8,8,4) (y_1,y_2,y_3)^T \\ & \mbox{s.t.} \begin{pmatrix} 2 & 4 & 1 \\ 3 & 2 & 1 \\ 2 & 1 & 1 \end{pmatrix} \begin{pmatrix}y_1\\y_2\\y_3\end{pmatrix} \ge \begin{pmatrix}2\\b\\0.5\end{pmatrix} \tag{D} \\ & y_1,y_2,y_3 \ge 0 \end{align*}

The variables $x_1,x_2,x_3,y_1,y_2,y_3$ are called structual variables. We add slack and surplus variables to the primal problem and its dual so as to transform the above LPPs into their standard form. I write them out for clarity.

\begin{align*} & \max (2,b,0.5) (x_1,x_2,x_3)^T & \\ & \mbox{s.t.} \begin{pmatrix} 2 & 3 & 2 & 1 & 0 & 0 \\ 4 & 2 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix}x_1\\x_2\\x_3\\x_4\\x_5\\x_6\end{pmatrix} = \begin{pmatrix}8\\8\\4\end{pmatrix} \tag{P} \\ & x_1,x_2,x_3,x_4,x_5,x_6 \ge 0 \\ & \min (8,8,4) (y_1,y_2,y_3)^T \\ & \mbox{s.t.} \begin{pmatrix} 2 & 4 & 1 & -1 & 0 & 0 \\ 3 & 2 & 1 & 0 & -1 & 0 \\ 2 & 1 & 1 & 0 & 0 & -1 \end{pmatrix} \begin{pmatrix}y_1\\y_2\\y_3\\y_4\\y_5\\y_6\end{pmatrix} = \begin{pmatrix}2\\b\\0.5\end{pmatrix} \tag{D} \\ & y_1,y_2,y_3,y_4,y_5,y_6 \ge 0 \end{align*}

The variables $x_4,x_5,x_6$ are called primal slack variables, and $y_4,y_5,y_6$ are called dual surplus variables. The complementary slackness condition states that $(x_1,x_2,x_3)(y_4,y_5,y_6)^T = (x_4,x_5,x_6)(y_1,y_2,y_3)^T = 0$.

\begin{align*} &\because x_1,\dots,x_6,y_1,\dots,y_6 \ge 0 \\ &\therefore x_1 y_4 = x_2 y_5 = x_3 y_6 = x_4 y_1 = x_5 y_2 = x_6 y_3 = 0 \end{align*}

Since it's given that $(y_1,y_2,y_3) = (\frac{1}{2},\frac{1}{4},0)$, we can use the standard form (or even from the canonical form) to compute the dual surplus variables $(y_4,y_5,y_6) = (0,2-b,\frac{5}{4})$. Therefore, $x_3 = x_4 = x_5 = 0$. If $y_5 \ne 0$, then $x_2 = 0$. Then it can be easily seen from the standard (or canonical form) that it's impossible. (Only $x_1$ and $x_6$ are left, and $2 x_1 = 8 = 4 x_1$, which is false.) Hence $y_5 = 0 \iff b = 2$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .