# Construct a linear programming problem for which both the primal and the dual problem has no feasible solution

Construct (that is, find its coefficients) a linear programming problem with at most two variables and two restrictions, for which both the primal and the dual problem has no feasible solution.

For a linear programming problem to have no feasible solution it needs to be either unbounded or just not have a feasible region at all I think. Therefore, I know how I should construct a problem if it would only have to hold for the primal problem. However, could anyone tell me how I should find one for which both the primal and dual problem have no feasible solution? Thank you in advance.

Let $A=\left(\begin{smallmatrix} -1&0\\0&1\end{smallmatrix}\right)$, $b=\left(\begin{smallmatrix}1\\1\end{smallmatrix}\right)=-c$. $Ax\ge b$ and $A^Ty\le c$ cannot both be satisfied with positive $x,y$.
• First I tried to find a 1-d solution but I'm pretty sure there isn't one. Then I tried to find a simple (diagonal) $A$ that works, which wasn't too hard to do. One coordinate makes the primal infeasible, while the other makes the dual infeasible. – vadim123 May 16 '13 at 20:34
• @cruise, there is a relationship between the primal and dual regions. The $b$ is both the bound for the primal solution, and the objective function for the dual solution. Similarly, the $c$ is both the bound for the dual solution and the objective function for the primal solution. – vadim123 May 20 '13 at 13:20