I have been struggling with the following questions, especially the first two:
- Is the solution $[y_1, y_2]^T = [2,1]$ of the dual a feasible solution?
- Is the solution $[y_1, y_2]^T = [2,1]$ of the dual a basic solution?
- 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:
- 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}$$
- 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$.
- 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?