7
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thank you for your help! Could you please tell me though how you constructed this problem? What steps did you take to get to this? $\endgroup$ – dreamer May 16 '13 at 20:32
  • 2
    $\begingroup$ 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. $\endgroup$ – vadim123 May 16 '13 at 20:34
  • 1
    $\begingroup$ @cruise, when a primal (or dual) region is empty, it is irrelevant which objective function is used. However, when the primal and dual constraints are specified, you can determine each objective function from the other. $\endgroup$ – vadim123 May 20 '13 at 12:54
  • 1
    $\begingroup$ @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. $\endgroup$ – vadim123 May 20 '13 at 13:20
  • 1
    $\begingroup$ Sorry for all the questions but I'm still not sure whether I fully understand your solution. Doesn't your dual problem boil down to the following: \begin{align} min \quad -y_1-y_2\\ s.t. \quad y_1\geq -1 \\ y_2\geq -1 \\ \end{align}? How is this dual problem infeasible? $\endgroup$ – dreamer May 20 '13 at 18:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.