Theorem $$\max\{c^Tx:x\ge0;Ax\le b\} = \min\{y^Tb:y\ge0;y^TA\ge c^T\}$$ (assuming both sets are nonempty)
Use the above theorem to prove the following variant of the duality theorem: $$\max\{c^Tx:Ax=b;x\le0\} = \min\{y^Tb:y^TA\le c^T\}$$ (assuming both sets are nonempty)
Please help me to prove the above variant of the duality theorem.
I am a masters student and linear programming is new to me. This question is a part of my assignment. I was not able to prove it.
Rewrite the given problem into canonical form. \begin{equation*} \begin{array}{lr@{}l} \max & c^T x & \\ \text{s.t.} & Ax &{} = b \\ & x &{} \le 0 \end{array} \end{equation*} Replace $-x$ by $x$. \begin{equation*} \begin{array}{lr@{}l} \max & -c^T x & \\ \text{s.t.} & Ax &{} = -b \\ & x &{} \ge 0 \end{array} \end{equation*} Replace the equality with two inequalities. \begin{equation*} \begin{array}{lr@{}l} \max & -c^T x & \\ \text{s.t.} & Ax &{} \le -b \\ & -Ax &{} \le b \\ & x &{} \ge 0 \end{array} \end{equation*} Compute its dual. According to the (Strong Duality) Theorem, the optimal solution of the primal problem and its dual is the same. \begin{equation*} \begin{array}{lr@{}l} \min & \begin{bmatrix} u \\ v \end{bmatrix}^T \begin{bmatrix} -b \\ b \end{bmatrix} & \\ \text{s.t.} & \begin{bmatrix} u \\ v \end{bmatrix}^T \begin{bmatrix} -A \\ A \end{bmatrix} &{} \ge -c^T \\ & u, v &{} \ge 0 \end{array} \end{equation*} Simplify the results. \begin{equation*} \begin{array}{lr@{}l} \min & -u^T b + v^T b & \\ \text{s.t.} & u^T A - v^T A &{} \ge -c^T \\ & u, v &{} \ge 0 \end{array} \end{equation*} Factorise the terms. \begin{equation*} \begin{array}{lr@{}l} \min & (v - u)^T b & \\ \text{s.t.} & -(v - u)^T A &{} \ge -c^T \\ & u, v &{} \ge 0 \end{array} \end{equation*} Note that $y := v - u$ is free. (i.e. $y$ can be any vector in $\mathbb{R}^m$). \begin{equation*} \begin{array}{lr@{}l} \min & y^T b & \\ \text{s.t.} & -y^T A &{} \ge -c^T \end{array} \end{equation*} We finally get the problem on the RHS. \begin{equation*} \begin{array}{lr@{}l} \min & y^T b & \\ \text{s.t.} & y^T A &{} \le c^T \end{array} \end{equation*}