By the strong duality theorem we know that LP can have 4
possible outcomes:
- dual and primal are both feasible,
- dual is unbounded and primal is infeasible,
- dual is infeasible and primal is unbounded,
- dual & primal are both infeasible.
Given the primal program:
Maximize $z = a x_1 + b x_2$
subject to:
$c x_1 + d x_2 \leq e$
$f x_1 + g x_2 \leq h$
$x_1, x_2 \geq 0$
We can construct the dual program :
Minimize $w = e y_1 + h y_2$
subject to:
$c y_1 + f y_2 \geq a$
$d y_1 + g y_2 \geq b$
$y_1, y_2 \geq 0$
And my question is: is it possible to assign values for
$a,b,c,d,e,f,g,h$ such that both primal and dual are infeasible?
I tried to came up with values but the case was always that
one of them (dual or primal) was infeasible and the other was
unbounded.
Best Answer
Take $(c,d,f,g)=(1,-1,-1,1)$ and $(a,b,e,h)=(1,0,0,-1)$. This way the primal constraints are $x_1-x_2\le 0$ and $-x_1+x_2\le -1$, which is equivalent to $x_1-x_2\ge 1$. Together we get $1 \le x_1 - x_2 \le 0$, which is impossible to satisfy.
Similarly, the dual constraints are $0\ge y_1-y_2\ge 1$.