I have really no idea where to go in this problem. This is from Bertsimas Introduction to Linear Optimization, Exercise 4.26. My teacher would like us to create a primal and dual LP to solve the following:
Let A be a given matrix. Show that exactly one of the following alternatives must hold.
(a) There exists some $x \neq 0$ such that $Ax = 0, x ≥ 0$.
(b) There exists some p such that $p'A > 0$.
My teacher released the answers, hopefully this helps someone else:
Primal : $Max\ c'x\ subject\ to\\ Ax = 0\\ x \ge 0$
Dual: $Min\ 0'p\ subject\ to\\ A'p \ge c$
Assuming $c > 0$
From now on youl have to excuse me if I write A'p vs p'A. Just know that they mean the same thing.
(a) If some x* satisfies $Ax\* =0$ then we can say that the primal is feasible and unbounded, since any positive multiple of c'x* will still satisfies $Ax = 0$ and increase the objective function. From weak duality, we know that since the primal is unbounded but feasible, the dual must be infeasible. This shows that no p can satisfy $A'p \ge c > 0$ or $A'p > 0$. Thus, if (a) is true (b) cannot be true.
(b) We can see the dual problem is feasible, since p has no restrictions and a solution to the constraints is simply $p = A^{-1} c$. Knowing the problem is feasible, we can see the optimal solution is simply $0$. We can also see that the primal is feasible, since $x = 0$ is a feasible solution. From strong duality (and i think weak duality) we can say that since both problems are feasible, their optimal solutions must be equal. The duals optimal solution is 0 so the primal must also be optimal at 0. Since c is strictly positive and x is non-negative, we conclude that the only x that satisfies this is $x = 0$, proving that is (b) is true (a) cannot be true.