I am trying to prove what is often titled the strong duality theorem. There is a hint in the book that I'm following, and I want to follow the method they have outlined for me. I will outline the problem:
Let A.1: Minimize $c^tX$ subject to $AX\ge b$, $X \ge 0$
Let A.2 (Dual): Maximize $Y^tb$ subject to $A^tY \le c$, $Y \ge 0$
Farkas' Lemma states: Given a matrix $D$ and a row vector $d$, either there exists a column vector $v$ such that $Dv \le 0$ and the scalar $dv$ is strictly positive, or there exists a non-negative row vector $w$ such that $wD = d$, but not both.
The strong duality theorem states: If a linear program has a finite optimal solution, then so does its dual, and the optimal values of the objective functions are equal.
Prove this using the following hint: If it is false, then there cannot be any solutions to
$$AX \ge b, \; A^tY \le c, \; X \ge 0,\; Y\ge 0, \; c^tX \le Y^tb.$$
My attempt at a solution picks up from the hint. If someone will help me complete the proof, I want it to follow my line of reasoning. I know there are many other proofs of this out there.
Let $X'$ be optimal for A.1, and let $c^tX' = \lambda$.
Assume for contradiction that the hypothesis is wrong:
$$\begin{bmatrix} A^t & -c\\ 0 & -1 \end{bmatrix} \begin{bmatrix} Y\\1\end{bmatrix} \le \begin{bmatrix} 0\\ 0 \end{bmatrix}, \quad \begin{bmatrix} b^t & -\lambda\end{bmatrix} \begin{bmatrix} Y\\1\end{bmatrix} \ge 0 \text{ is unsolvable.}$$
By Farkas' Lemma, we know the following system is solvable:
$$\begin{bmatrix} X & w_2\end{bmatrix} \begin{bmatrix} A^t & -c\\0 & -1\end{bmatrix} \ge \begin{bmatrix} b^t & -\lambda\end{bmatrix}, \text{ where $X,w_2 \ge 0$.}$$
Now, from the system above, we may write $XA^t \ge b^t$, and $Xc \le \lambda - w_2$.
If $w_2$ is greater than $0$, then we have found a contradiction with the assumption that $X'$ was optimal for A.1. However, one cannot reach that conclusion if $w_2$ is exactly $0$.
I feel like I can't be that far off from a correct complete proof as I've followed exactly the hint, and the use of Farkas' Lemma which was explained on the previous page. If someone could help me finish/correct the proof, I'd be greatly appreciative.