1

Suppose I have a linear program (LP) with the constraints $\mathbf{A}\mathbf{x}\leqslant \mathbf{b}$.

A feasible solution $\mathbf{x}$ to the LP is a solution that satisfies the constraints $\mathbf{A}\mathbf{x}\leqslant \mathbf{b}$. If there is no $\mathbf{x}$ such that $\mathbf{A}\mathbf{x}\leqslant \mathbf{b}$ then we say that the LP is infeasible.

I do not understand what does this mean? Geometrically, how can an LP be infeasible? If I draw the feasible region, I cannot find any point in it? Is it empty then?

Ribz
  • 1,492

1 Answers1

2

Yes you are exactly right. Geometrically, it means that the set of points that satisfy all of the constraints is empty. As an example, suppose you have $$ y\le 1-x \\ y \ge 2 \\ x,y\ge 0 $$

The constraints $y \le 1-x$ and $x \ge 0$ imply $y \le 1$, which is not compatible with $y \ge 2$. In other words the problem is infeasible. Draw these lines in the 2D plane to convince yourself that the polygon of constraints is indeed empty.

Kuifje
  • 9,584
  • Thanks. I have a quick question: If I have an LP that is infeasible, can adding a new constraints make it feasible? – Ribz Nov 01 '16 at 16:19
  • No...that is not possible. If your LP in infeasible, then the polygon of constraints is already empty. Adding new constraints cannot take away the fact that some initial constraints are incompatible. – Kuifje Nov 01 '16 at 16:48