1
$\begingroup$

I have been struggling with the following questions, especially the first two:

  1. Is the solution $[y_1, y_2]^T = [2,1]$ of the dual a feasible solution?
  2. Is the solution $[y_1, y_2]^T = [2,1]$ of the dual a basic solution?
  3. Find the optimal solution $[y_1*, y_2*]^T$.

The following primal is given: $$\begin{array}{cc} \text{min } & z = -4x_1 - 7x_2 + 5x_3 -14x_4\\ \text{s.t. } & 2x_1 -4x_2 + x_3 -8x_4 \leq 22 \\ & x_1 + x_2 + 3x_3 + x_4 \leq 8 \\ & x_1, x_2, x_3, x_4 \geq 0 \\ \end{array}$$

If I am not mistaken, this should be equivalent to: $$\begin{array}{cc} \text{min } & z = -4x_1 - 7x_2 + 5x_3 -14x_4\\ \text{s.t. } & -2x_1 +4x_2 - x_3 +8x_4 \geq -22 \\ & -x_1 - x_2 - 3x_3 - x_4 \geq -8 \\ & x_1, x_2, x_3, x_4 \geq 0 \\ \end{array}$$

Which should corresponds to the following dual: $$\begin{array}{cc} \text{max } & w = -22y_1 -8y_2\\ \text{s.t. } & -2y_1 - y_2 \leq -4 \\ & 4y_1 -y_2 \leq -7\\ &-y_1 -3y_2 \leq 5\\ &8y_1 -y_2 \leq -14\\ & y_1, y_2 \geq 0 \\ \end{array}$$

My thoughts:

  1. It is not a feasible solution, since for $y_1 = 2, y_2 = 1$ we have $$\begin{array}{cc} & -2y_1 - y_2 = -5 \neq -4 \\ & 4y_1 -y_2 = 7 \neq -7\\ &-y_1 -3y_2 = -5\neq 5\\ &8y_1 -y_2 = 15\neq -14\\ \end{array}$$
  2. By that same argument, it is not a basic solution, since there is no basis $B$ of row vectors in $A^T$ such that $By_B = c$.
  3. I assume this is simply done by the Dual simplex algorithm, starting with a basic solution. But it feel like I did something incorrect at (1) and (2) and I actually need to use $[2,1]$ for this.

I am familiar with complementary slackness, but I don't think this is useful here?

$\endgroup$
  • 1
    $\begingroup$ Note that you have inequalities in your dual problem. Thus only the second and the fourth constraint are not fullfilled. But this alone is sufficient that (2,1) is not a feasible solution. $\endgroup$ – callculus Nov 20 '16 at 4:44
  • $\begingroup$ So a basic solution, that is not necessarily feasible, has to satisfy all constraints of a LP? Does it also have to satisfy the non-negativity constraint? So if for example $[2,-1]^T$ satisfies the first four inequalities, then it's still not a basic solution because $y_2 < 0$? $\endgroup$ – user260710 Nov 20 '16 at 4:51
  • $\begingroup$ A basic solution is a feasible solution. Because it is a feasibille solution it has to fullfill all constraints. $(2,-1)^T$ is not a basic (feasible) solution, because it does not fullfill the non-negativity condition. $\endgroup$ – callculus Nov 20 '16 at 4:58
  • $\begingroup$ If there is no typo number 2 can be answered immediately. $\endgroup$ – callculus Nov 20 '16 at 5:03
  • $\begingroup$ @callculus I searced "basic infeasible solution", and found "basic infeasible solution" on P.9 of this OR notes $\unicode{x1F517}$ $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Feb 20 '17 at 10:24
0
$\begingroup$
  1. $[y_1, y_2]^T = [2,1]$ is not a feasible solution to the dual since it doesn't satisfy the first constraint $4y_1 -y_2 = 7 > -7$.
  2. $[y_1, y_2]^T = [2,1]$ is not a basic solution. You may say "by the same calculations", but not "by the same arguments". \begin{align} 4y_1 -y_2 = 7 > -7 &\implies [y_1, y_2]^T \text{ infeasible} \\ 4y_1 -y_2 = 7 \ne -7 &\implies [y_1, y_2]^T \text{ non-basic} \end{align} The second implication follows since we actually transform the LP into \begin{array}{lrr} \text{max} & w = -22y_1 -8y_2 &\\ \text{s.t.} & -2y_1 - y_2 +s_1 =& -4 \\ & 4y_1 -y_2 +s_2 =& -7\\ &-y_1 -3y_2 +s_3 =& 5\\ &8y_1 -y_2 +s_4 =& -14\\ & y_1, y_2, s_1, s_2, s_3, s_4 \geq 0 \end{array} The calculations in the question body actually shows that $s_i$'s are nonzero, so the solution $[y_1,y_2]^T$ has more than two nonzero components, so it's not a basic solution.
  3. You have the right choice of method. To use the dual simplex method, we need a basic (infeasible) solution with the optimality satisfied. Note that feasibility and optimality are two independent concepts. It's easy to observe that in the simplex tableau, the $w$-row ($[22, 8, 0,\dots,0]$) is nonnegative, so the optimality condition is satisfied. As a result, the most obvious choice for a basic variable would be $[y_1,y_2]^T=[0,0]$.

Before continuing the dual simplex method, in response to OP's comment corcerning $[y_1,y_2]^T = [2, -1]$, we have $s_1 = -4 + 2(2) + (-1) = -1 \ne 0$, so $[y_1,y_2]^T = [2,-1]$ has more than two nonzero components, so it's nonbasic and infeasible. We can't use this to solve the dual.

Current basis: $s_1, s_2, s_3, s_4$

\begin{array}{rrrrrrr|r} & y_1 & y_2 & s_1 & s_2 & s_3 & s_4 & \\ \hline s_1 & -2 & -1 & 1 & 0 & 0 & 0 & -4 \\ s_2 & 4 & -1 & 0 & 1 & 0 & 0 & -7 \\ s_3 & -1 & -3 & 0 & 0 & 1 & 0 & 5 \\ s_4 & 8 & -1 & 0 & 0 & 0 & 1 & -14 \\ \hline & 22 & 8 & 0 & 0 & 0 & 0 & 0 \\ \text{ratio} & 11/4 & -8 & & & & 0 & \end{array}

Leaving variable: $s_4$, entering variable: $y_2$

Current basis: $s_1, s_2, s_3, y_2$

\begin{array}{rrrrrrr|r} & y_1 & y_2 & s_1 & s_2 & s_3 & s_4 & \\ \hline s_1 & -10 & 0 & 1 & 0 & 0 & -1 & 10 \\ s_2 & -4 & 0 & 0 & 1 & 0 & -1 & 7 \\ s_3 & -25 & 0 & 0 & 0 & 1 & -3 & 47 \\ y_2 & -8 & 1 & 0 & 0 & 0 & -1 & 14 \\ \hline & \color{blue}{86} & \color{blue}{0} & \color{red}{0} & \color{red}{0} & \color{red}{0} & \color{red}{\bbox[2px, border: solid 1px]{8}} & -112 \\ \end{array}

Hence the optimal solution is $[y_1,y_2]^T = [0,14]$ with $w = -112$.

By adding slack variabes $t_1,t_2$ to the primal

\begin{array}{rlr} \min z = & \color{red}{-4x_1 - 7x_2 + 5x_3 -14x_4} &\\ \text{s.t.} & 2x_1 -4x_2 + x_3 -8x_4 +\color{blue}{t_1} &= 22 \\ & x_1 + x_2 + 3x_3 + x_4 +\color{blue}{t_2} &= 8 \\ & \color{red}{x_1, x_2, x_3, \bbox[2px, border: solid 1px]{x_4}}, \color{blue}{t_1,t_2} \geq 0, \end{array}

we can read the solution of the primal from the simplex tableau for the dual: the optimal solution for the primal is $[\color{red}{x_1, x_2, x_3, \bbox[2px, border: solid 1px]{x_4}}, \color{blue}{t_1,t_2}]^T = [\color{red}{0,0,0, \bbox[2px, border: solid 1px]{8}}, \color{blue}{86,0}]$.

$\endgroup$

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.