Mfrhtyj

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 = -5neq 5\
   &8y_1 -y_2 = 15neq -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?

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