Graphical infeasibility
Graphical Infeasibility
A linear programming problem is infeasible when no point satisfies all constraints.
Graphically, this means the half-planes have no common overlap.
Definition
The feasible region is:
\[S=\{x\mid x\text{ satisfies all constraints}\}\]If:
\[S=\varnothing\]then the problem is infeasible.
There is no feasible solution and therefore no optimal solution.
Simple Example
Consider:
\[x_1\ge 2\] \[x_1\le 1\]No number can be both at least $2$ and at most $1$.
So the feasible region is empty.
Two-Dimensional Example
Consider:
\[x_1+x_2\le 1\] \[x_1+x_2\ge 3\] \[x_1,x_2\ge 0\]The first constraint requires points on or below:
\[x_1+x_2=1\]The second requires points on or above:
\[x_1+x_2=3\]There is a gap between the two lines.
No point can satisfy both.
How to Detect Infeasibility Graphically
To check infeasibility:
- draw every boundary line
- shade or mark the feasible side of each line
- look for a common intersection
- if no common overlap exists, the problem is infeasible
Pairwise Feasible Is Not Enough
Sometimes every pair of constraints overlaps, but all constraints together do not.
So do not check constraints only in pairs.
The feasible region must satisfy all constraints simultaneously.
Objective Function Is Irrelevant
Infeasibility depends only on constraints.
Changing the objective cannot make an infeasible problem feasible.
If $S=\varnothing$, both of these fail:
\[\max c^Tx\] \[\min c^Tx\]because there is no admissible point to evaluate.
Infeasible vs Unbounded
Do not confuse infeasible with unbounded.
| Status | Feasible region | Meaning |
|---|---|---|
| Infeasible | empty | no feasible point exists |
| Unbounded objective | nonempty | feasible points exist and objective improves forever |
An infeasible problem has no solution.
An unbounded problem has feasible points but no finite optimum.
Common Causes
Infeasibility often comes from contradictory requirements.
Examples:
- minimum demand exceeds maximum capacity
- required investment exceeds available budget
- lower bound is greater than upper bound
- equality conflicts with inequality constraints
Example Interpretation
Suppose a farm must produce at least $100$ units, but capacity allows at most $80$ units.
The model contains:
\[\text{production}\ge 100\]and:
\[\text{production}\le 80\]This is infeasible.
What to Report
If the graphical region is empty, report:
\[S=\varnothing\]and say:
The problem is infeasible, so no optimal solution exists.
Do not give an objective value.
Checklist
You understand graphical infeasibility if you can:
- identify an empty feasible region
- explain which constraints conflict
- distinguish infeasibility from unboundedness
- state that no optimal solution exists
- avoid optimizing when no feasible point exists
See Also
Exam checkpoint
For graphical questions, first check whether nonnegativity is explicitly stated. Then draw half-planes, list vertices, evaluate the objective, and state finite optimum, infeasibility, multiple optima, or unboundedness.