There are three things that have to be satisfied in order for a solution to a linear programming problem to be optimal:
- The primal solution must be feasible.
- The dual solution must be feasible.
- Complementary slackness must be satisfied. (Remember that primal variables are paired with dual slack variables and dual variables are paired with primal slack variables. Complementary slackness is the requirement that, for each of these pairs, at least one variable must be zero.)
The primal simplex method (after Phase I) keeps (1) and (3) always true and searches for a solution that satisfies (2). The dual simplex method (again, after Phase I), keeps (2) and (3) always true and searches for a solution that satisfies (1).
The approach you are describing (minus the $b^Ty \geq c^T x$ constraint) is used. It's the other option, in which (1) and (2) are always kept true while the algorithm searches for a solution that satisfies (3). As Yuval Filmus indicates, this is called a primal-dual method or the parametric self-dual simplex method. See, for example, Rader's Deterministic Operations Research, pp. 432-440, or Vanderbei's Linear Programming: Foundations and Extensions, pp 119-121. (See also Vanderbei's text for how to find an initial feasible solution to both problems; i.e., Phase I.) The idea dates back at least to George Dantzig, the inventor of the simplex method.
As a side comment, Vanderbei indicates that the parametric self-dual simplex method is more amenable to probabilistic analysis than the other versions of the simplex method.
You're close. You should have $y_1 \leq 0$, $y_2 \leq 0$, $y_3 \geq 0$, and $y_4$ should be free. Everything else is correct.
One way to view the dual of a primal maximization problem is that it arises from attempting to find a tight upper bound on the optimal value of the primal problem.
Suppose we decide to take a linear combination of the four primal constraints to find an upper bound on the optimal primal value. Then we're looking for multipliers $y_1, y_2, y_3,$ and $y_4$ to force
$$\begin{align}
2x_1 - 2x_2 + x_3 + 4x_4 &\leq y_1(x_1 - x_2 - x_3) + y_2(-x_1 + x_2 + x_3) + y_3(x_3 + 3x_4) \\&\:\:\:\:\:\:\:\:\:\:\:+ y_4(-5x_1 + 5x_2 + 4x_3 + x_4) \\&\leq 3y_1 -3y_2 + 2y_3 + 10y_4 .\end{align}$$
Now, we want the upper bound to be as tight as possible, so we want to minimize $3y_1 -3y_2 + 2y_3 + 10y_4$. That's where the dual objective comes from.
In order for the second inequality to hold, we've got to flip the direction of the first inequality constraint in the primal from $\geq$ to $\leq$. In other words, we've got $x_1 - x_2 - x_3 \geq 3$, but we want $y_1(x_1 - x_2 - x_3) \leq 3y_1$. So the multiplier $y_1$ must be negative or zero. The same logic dictates that $y_2$ be negative or zero and that $y_3$ be positive or zero. The fourth primal constraint is an equality, though. Since we don't have to worry about the sign on $y_4$ flipping the inequality in the wrong direction, we don't get any restrictions on $y_4$. Thus $y_4$ is free.
Similar logic yields the form of the constraints in the dual (i.e., $=$, $\leq$, or $\geq$), which you have correct.
For more details, see my answer to "Duality. Is this the correct Dual to this Primal LP?"
Best Answer
Yes, it should. I think you typed incorrect data. This is what I got. Note the difference in the primal problem representation. In your case it says $$ x_1,x_2\ge 0,\ X_1\text{ unrestricted} $$ but $X_1$ (capital) is not a variable there.