Give An Example Of A Linear Program For Which The Feasible Region Is Not Bounded, But The Optimal Objective

Give An Example Of A Linear Program For Which The Feasible Region Is Not Bounded, But The Optimal Objective

Linear programming (LP) is a fundamental mathematical technique used in operations research, economics, engineering, and numerous other fields to optimize a linear objective function subject to a set of linear constraints. It allows decision-makers to find the best possible outcome—such as maximizing profit or minimizing cost—within a feasible region defined by these constraints.

A critical aspect of linear programming is understanding the nature of the feasible region—the set of all points that satisfy the constraints. Typically, the feasible region is a convex polyhedron, which can be bounded (forming a closed, finite region) or unbounded (extending infinitely in one or more directions). The boundedness of this region has significant implications for the existence and nature of optimal solutions.

In many cases, the feasible region is bounded, ensuring a finite optimal solution. However, intriguing scenarios exist where the feasible region is unbounded—meaning it extends infinitely in at least one direction—but the LP still has a finite, well-defined optimal value for the objective function. This phenomenon occurs because the objective function does not increase (or decrease) indefinitely along the unbounded directions, leading to a bounded optimal value despite an unbounded feasible region.

This article will explore this concept in detail, providing a concrete example of such a linear program, analyzing its feasible region, and explaining why the optimal solution remains finite despite unboundedness.

---

Understanding Bounded and Unbounded Feasible Regions in Linear Programming

What Is a Feasible Region?

The feasible region in a linear program is the set of all points that satisfy all the given constraints. These constraints are usually expressed as linear inequalities or equations, such as:

• \(a1x1 + a2x2 \leq b\)


• \(c1x1 + c2x2 = d\)

The intersection of these constraints forms a convex polyhedron in the decision variable space.

Bounded vs. Unbounded Regions

• Bounded Feasible Region: The region is closed and finite, meaning it contains all points within a finite volume. In this case, the optimal solution, if it exists, occurs at a vertex (corner point) of the region.
• Unbounded Feasible Region: The region extends infinitely in at least one direction. There are directions along which the feasible points can grow without limit.

Implications for Optimization

• For bounded regions, the LP has at least one optimal solution, which is finite and occurs at a vertex.
• For unbounded regions, the LP may have:
• No finite optimal solution (if the objective improves infinitely along an unbounded direction).
• A finite optimal solution (if the objective does not improve infinitely in any feasible direction).

This last point is crucial: an unbounded feasible region does not necessarily mean the LP's optimal value is infinite. The nature of the objective function and the constraints determines whether an optimal solution exists and whether it is bounded.

---

Scenario: Unbounded Feasible Region with Finite Optimal Objective

Let's consider the core question: Can a linear program have an unbounded feasible region but still possess a finite optimal value?

The answer is yes, and such cases are essential in understanding the subtleties of LP. This occurs when the objective function does not increase (or decrease) along the unbounded directions of the feasible region, effectively "capping" the optimal value.

---

Constructing an Example Linear Program

To illustrate this, we'll develop a specific LP example with the following characteristics:

• The feasible region is unbounded.


• The objective function has a finite maximum (or minimum).


• The potential unbounded directions do not improve the objective.

Example LP Formulation

Maximize:
\[ Z = 3x1 + 2x2 \]

Subject to constraints:
\[
\begin{cases}
x1 - x2 \leq 2 \\
x1 + x2 \geq 4 \\
x_1 \geq 0 \\
x_2 \geq 0
\end{cases}
\]

---

Analyzing the Constraints

Let's interpret the constraints:

1. \(x1 - x2 \leq 2\): This restricts the difference between \(x1\) and \(x2\).


2. \(x1 + x2 \geq 4\): Ensures the sum of the variables is at least 4.


3. \(x1 \geq 0\) and \(x2 \geq 0\): Non-negativity constraints.

---

Graphical Representation and Feasible Region

Plotting these constraints in the \(x1 x2\)-plane:

• The line \(x1 - x2 = 2\) divides the plane; feasible points satisfy \(x1 - x2 \leq 2\), which is the region below or on this line.


• The line \(x1 + x2 = 4\) divides the plane; feasible points satisfy \(x1 + x2 \geq 4\), which is above or on this line.


• Non-negativity restricts us to the first quadrant.

The feasible region is the intersection of:

• The region below or on the line \(x1 - x2 = 2\),


• The region above or on the line \(x1 + x2 = 4\),


• The first quadrant (\(x1, x2 \geq 0\)).

Resulting shape: An unbounded polygon extending infinitely in certain directions.

---

Identifying the Unbounded Directions

Let's analyze the boundaries:

• The intersection points of the lines:


• Solve for \(x1, x2\):

\[
\begin{cases}
x1 - x2 = 2 \\
x1 + x2 = 4
\end{cases}
\]

• Adding the equations:

\[
2x1 = 6 \implies x1 = 3
\]

• Substituting back:

\[
3 + x2 = 4 \implies x2 = 1
\]

• So, the intersection point is \((3,1)\).


• The feasible region includes all points satisfying \(x1 \geq 0, x2 \geq 0\), and lying between the lines \(x1 - x2 \leq 2\) and \(x1 + x2 \geq 4\).


• The corner point of the feasible region (the feasible vertex) is at \((3,1)\).


• The region extends infinitely in certain directions beyond the constraints, especially toward larger \(x1\) and \(x2\).

---

Analyzing the Objective Function

The objective function is:

\[ Z = 3x1 + 2x2 \]

• To maximize \(Z\), consider the directions in which \(Z\) increases:


• Increasing \(x1\) and \(x2\) generally increases \(Z\).


• But constraints limit how far we can go:


• The line \(x1 - x2 \leq 2\) restricts the difference \(x1 - x2\).


• The line \(x1 + x2 \geq 4\) restricts the sum.


• Importantly, the feasible region is unbounded in the direction where both \(x1\) and \(x2\) grow large while remaining within the constraints.

---

Checking for Unboundedness in the Objective

• Does \(Z\) tend to infinity along some unbounded direction?
• To determine this, analyze the direction vectors along which the feasible region extends infinitely.
• For example, consider moving along the vector \(\mathbf{d} = (d1, d2)\).
• Along \(\mathbf{d}\), the constraints become:

\[ \begin{cases} (x1 + t d1) - (x2 + t d2) \leq 2 \\ (x1 + t d1) + (x2 + t d2) \geq 4 \\ x1 + t d1 \geq 0 \\ x2 + t d2 \geq 0 \end{cases} \]

• For unboundedness, we look for a direction \(\mathbf{d}\) such that:
• The constraints are satisfied as \(t \to \infty\).
• The objective \(Z\) tends to infinity: \(Z(t) = 3(x1 + t d1) + 2(x2 + t d2) \to \infty\).
• For the objective to tend to infinity, the components of