Primal-Dual basic (feasible) solution?

Question

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?

Answer 1

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}]$.