Consider the LP$$\min c^Tx+b^Ty\\s.t.\;\ Ax\leq b\\\quad \quad A^Ty=-c\\\quad\; \quad y\; \geq 0$$Assume there is a feasible point. Show that there is a (optimal) solution with value $0$.
I am not sure my approach is completely sound, so I would appreciate any improvements and suggestions.
We can rewrite $\;\;\; \min c^Tx+b^Ty\;\;\;$ as $\;\;\;\min c^Tx+\min b^Ty,\;\;\;$ and with that we can split up our LP into two separate LPs:$$\;\min c^Tx\qquad\qquad \min b^Ty\\(P)\quad s.t.\; Ax\leq b\qquad \;s.t.\; A^Ty=-c\quad (D)\\ \qquad\qquad\qquad\qquad\quad y\geq 0 $$$\min c^Tx=\max -c^Tx$ therefore $(D)$ is actually the dual LP of $(P)$. Because they are dual, we know that if both are feasible (and by assumption they are) then they have the same optimal values. This means that:
$\min c^Tx+\min b^Ty=\min b^Ty+\min b^Ty=2\min b^Ty$
For $y\in\Bbb{R}^m$ to be an optimal point to $(D)$ we have to pick $m$ linearly independent rows in the following matrix:$$\begin{pmatrix} A^T\\-A^T\\\Bbb{1}_m \end{pmatrix} $$Where $\Bbb{1}_m$ is the $m$-dimensional identity matrix. Clearly $\Bbb{1}_m$ has $m$ linearly independent rows, so a feasible $y$ is an optimal point of $(D)$, if for the chosen $m$ rows we have equality on our system of inequalities from $(D)$. This means that for all $1\leq i\leq m$, $y_i=0$ and therefore $y=0$ is an optimal solution for $(D)$ and so at that point $(D)$ has the value $b^Ty=b^T0=0$.
We have said that our original LP has double the value of $b^Ty$ at an optimal point $(\min c^Tx+b^Ty=2\min b^Ty)$ and so we have proven that for our original LP there is an optimal solution with value $0$.
Best Answer
Let $z^*$ be the optimal objective value for $(P)$, and let $w^*$ be the optimal objective value for $(D)$ (and its dual). Because $\max\{-s: s \in S\} = -\min\{s: s \in S\}$ for all $S\subset \mathbb{R}$, we have $w^*=-z^*$, and so the optimal objective value for the original problem is $z^*+w^* = z^*-z^* = 0$.