The Duality Theorem, in short, states that the optimal value of the Primal (P) and Dual (D) Linear Programs are the same if the solution, of either, is a basic feasible solution.
My question is that it also follows that (from Linear and Nonlinear Programming - Luenberger, Ye), from a corollary to the Weak Duality Lemma
$$\mathbf{c}^{T}\mathbf{x}_{*} = \mathbf{y}_{*}^{T}\mathbf{b},$$
where $\mathbf{x}_{*}$ and $\mathbf{y}_{*}^{T}$ are the optimal feasible solutions, and so we can always find the optimal solutions to the (P) and (D) given that we just find one? Am I interpreting this correctly?
For example, suppose I have the following (P) problem:
$$\text{max}~~~3x_1 - x_2 - x_3 + x_4$$ $$\text{subject to}~~~x_1 + 2x_2 - 4x_3 +x_4 = 3$$ $$~~~~~~~~~~~~~~~~~~~2x_1 - 2x_2 + 3x_3 + 3x_4 = 9$$ $$~~~~~~~~~~~~~~~~~~~x_1 - x_2 + 2x_3 - x_4 = 6$$ $$x_i \ge 0, \forall i$$
Solving (by two-phase simplex) gives an optimal value of -5 and an optimal solution of $\mathbf{x} = \begin{pmatrix} 2 \\ 2 \\ 3 \\ 0 \end{pmatrix}$
But then the optimal solution to the (D) is just the optimal solution to $$-5 = 3y_1 + 9y_2 + 6y_3,$$
which we find by $\mathbf{y}_{*}^T = \mathbf{c}^TB^{-1}$. We have $\mathbf{c}^T = \begin{pmatrix} 3 \\ -3 \\ -1 \end{pmatrix}$ and $B^{-1} = \begin{pmatrix} \frac{1}{3} & 1 & -\frac{4}{3} \\ 0 & -1 & 2 \\ \frac{1}{3} & -1 & \frac{5}{3} \end{pmatrix}$, from the last iteration of the two-phase method. Then $\mathbf{y}_{*}^T = \mathbf{c}^TB^{-1} = \begin{pmatrix} \frac{2}{3} & 7 & -\frac{35}{3} \end{pmatrix}$, which yields $-5$ as the optimal value for the (D) too.
$\endgroup$1 Answer
$\begingroup$Yes, you can. That's precisely the statement of the Strong Duality Theorem, which asserts
- the existence of $\mathbf{y}_{*}$ provided that of $\mathbf{x}_{*}$ (and vice versa)
- the zero duality gap $\mathbf{y}_{*}^{T}\mathbf{b} - \mathbf{c}^{T}\mathbf{x}_{*}$ is zero provided the existence of $\mathbf{x}_{*}$ or $\mathbf{y}_{*}$
Both the primal and the dual LP in your numerical example yield the same objective value. This is a consequence of the Strong Duality Theorem once you showed the existence of $\mathbf{x}_{*}$ in $(P)$ (by two-phase simplex method).
In practice, once you have computed $\mathbf{x}_{*}$, you can use Complementary Slackness condition to find $\mathbf{y}_{*}$.
$\endgroup$
