Linear Optimization: Duality in Simplex 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!
 A: 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)$.


*

*$x_0$ is a feasible solution for $(P)$. (by construction)

*$x_1$ is an optimal solution for $(P)$. (existence of such $x_1$ proved by Strong Duality)

*$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$}$
