1. Meaning of Bounded and Unbounded Solutions
When solving a linear programming problem graphically, the feasible region can either be fully enclosed or extend infinitely in some direction. This affects whether an optimal solution exists and how it behaves.
If the feasible region is enclosed, the solution is called bounded. If the region stretches out infinitely, it is unbounded.
2. Bounded Feasible Region
A bounded region is completely enclosed by the constraint lines. It forms a closed polygon (triangle, quadrilateral, etc.).
When the feasible region is bounded:
- The objective function always has a maximum value.
- The objective function always has a minimum value.
2.1. Graphical Understanding
On the graph, the feasible region lies entirely inside a limited space. This means the values of the objective function cannot grow without limit.
2.2. Example of a Bounded Region
For the constraints:
\( x + y \le 6 \)
\( x \ge 0 \)
\( y \ge 0 \)
The feasible region is a triangle with vertices at \( (0,0) \), \( (6,0) \), and \( (0,6) \). This is a bounded region, and both maximum and minimum values of the objective function will exist.
3. Unbounded Feasible Region
An unbounded region is not fully enclosed. It opens out indefinitely in one or more directions.
When the feasible region is unbounded:
- A minimum value may still exist.
- A maximum value might not exist because the objective function can increase without limit.
3.1. Graphical Understanding
On the graph, the feasible region does not form a closed polygon. It stretches to infinity, usually because at least one direction is unrestricted by constraints.
3.2. Example of an Unbounded Region
Consider the constraints:
\( x - y \ge 2 \)
\( x \ge 0 \)
\( y \ge 0 \)
The feasible region extends infinitely towards the right. It does not form a closed shape, so it is unbounded.
4. Checking if an Optimal Solution Exists in an Unbounded Region
Even if the feasible region is unbounded, an optimal solution may still exist for a minimization or maximization problem. To check this:
- Evaluate the objective function at all corner points.
- If the objective function continues to increase (or decrease) in an unbounded direction, no optimal solution exists.
- If the best value occurs at a corner point and no direction improves it further, then the optimal solution exists.