Linear Optimization: Duality in Simplex

Question

Consider the optimization problem:

(P) $$Minimize \ \ \ z = c^tx \\subject \ to\ \ \ Ax=c \\ x \ge 0 $$

$c \in \mathbb R^n, A^t=A$

I want to show that if $x$ is a feasable point here, it is already optimal.

I know that the dual problem is

(D)$$Maximize \ \ \ w = c^ty \\subject \ to\ \ \ Ay \le c \\ $$

and if $x$ and $y$ are feasable points for (P) and (D), then $c^tx \ge c^ty$ and $c^tx = c^ty$ if they are optimal. However my efforts to this lead nowhere. Any help is greatly appreciated!

Answer 1

Observe that any feasible solution to $(P)$ is also a solution to $(D)$, since you set $A = A^t$. In words, a primal feasible solution satisfies the dual.

From the hypothesis of the question, we fix a feasible solution $x_0$ in $(P)$.

You are almost there with the weak duality: $c^tx \ge c^ty$ for any feasible $x$ in $(P)$ and $y$ in $(D)$.

For any (non-optimal) feasible $y$ in $(D)$, we have $c^tx_0 \ge c^ty$ thanks to the weak duality. Then, we apply the first paragraph on $x_0$, so that $x_0$ also satisfies $(D)$. Since the choice of $y$ is arbitrary in $(D)$, $x_0$ is an optimal solution for $(D)$.

Now, we apply the Strong Duality Theorem (p.14 of 45) to conclude that $(P)$ has an optimal solution $x_1$, and $c^t x_0 = c^t x_1$.

Summarise the above points so as to see that $x_0$ is in fact an optimal solution for $(P)$.

1. $x_0$ is a feasible solution for $(P)$. (by construction)
2. $x_1$ is an optimal solution for $(P)$. (existence of such $x_1$ proved by Strong Duality)
3. $c^t x_0 = c^t x_1$ (part of the statement of the Strong Duality)

Conclusion: $x_0$ is an optimal solution for $(P)$. $\tag*{$\square$}$