Overview
This lecture explains special cases in linear programming: alternative optimal solutions, infeasibility, unboundedness, and redundancy, illustrating each with examples and their implications.
Alternative Optimal Solutions
- Occurs when more than one solution yields the same optimal value for the objective function.
- Happens when the objective function line is parallel to a binding constraint.
- Every point along the segment where the objective function and constraint line coincide is optimal.
- Alternative optimal solutions offer flexibility in choosing variable combinations with equal outcomes.
Infeasibility
- Occurs when no region satisfies all constraints at once.
- Happens if the feasible regions of constraints do not overlap.
- Results in no feasible solution or region for the problem.
Unboundedness
- Occurs in maximization problems when the feasible region extends infinitely.
- All “greater than” constraints can result in an open-ended feasible region.
- Objective function can increase without limit, indicating no maximum value exists.
- Suggests a problem with the formulation, such as missing resource limits.
Redundancy
- A constraint is redundant if it does not affect the feasible region.
- Example: If two age constraints are X ≥ 15 and X ≥ 16, the first is redundant.
- Redundant constraints can be removed without changing the feasible region or the optimal solution.
- Constraint lines that do not touch the feasible region are also redundant.
Key Terms & Definitions
- Alternative Optimal Solutions — Multiple solutions providing the same optimal objective function value.
- Infeasibility — No solution exists that satisfies all constraints simultaneously.
- Unboundedness — Feasible region is limitless, allowing the objective function to increase or decrease indefinitely.
- Redundancy — A constraint that does not alter the feasible region or optimal solution.
Action Items / Next Steps
- Review graphical examples of each special case for better understanding.
- Practice identifying special cases in sample linear programming problems.