linear programming infeasibility, dual & primal relation

Question

By the strong duality theorem we know that LP can have 4 possible outcomes:

1. dual and primal are both feasible,
2. dual is unbounded and primal is infeasible,
3. dual is infeasible and primal is unbounded,
4. 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.

Answer 1

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

Answer 2

You can get a more complete description of all the cases by arguing along the following lines: The feasible regions in both cases are the intersection of two half-spaces in the plane. (I am ignoring the nonnegative constraints on the coordinates). For such a region to be empty the lines defining the boundary should be parallel.

We can multiply each inequality by a positive number, without changing the region. So, it is enough to focus on the case where $c,f \in \{-1,0,+1\}$ from which all others can be obtained by rescaling. Consider the case where $c = 1$, then $f$ has be $-1$ for the the lines to be parallel and with possible non-empty intersection for the half-spaces. Now, if either of $d,g$ are anything but $\pm 1$, the lines in the dual won't be parallel, hence either $d = -1$ and $g = +1$ or vice versa. One an argue about the $0$ case similarly.