Linear Programming Feasibility Changes Explained

In linear programming (LP), a problem is considered "feasible" if there exists at least one solution that satisfies all the problem's constraints simultaneously. The set of all such solutions is called the "feasible region". Changes within the LP model can affect whether a feasible solution exists.

Analyzing Potential Causes for Feasibility Change

Let's examine how modifications to different parts of a linear programming problem impact its feasibility:

1. Change in Objective Function Coefficients

The objective function in an LP problem is typically represented as $Z = c_1x_1 + c_2x_2 + \dots + c_nx_n$, where $c_i$ are the coefficients. Changing these coefficients affects the goal of the optimization (e.g., maximizing profit or minimizing cost). While this change can alter the *optimal* solution (the best feasible solution) and potentially shift its location within the feasible region, it does not change the boundaries of the feasible region itself. The set of points satisfying the constraints remains the same. Therefore, changes in objective function coefficients generally do not affect feasibility.

2. Change in Right-Hand Side (RHS) of Constraints

Linear programming problems have constraints, often expressed as inequalities or equalities. A standard form constraint looks like $a_{1}x_1 + a_{2}x_2 + \dots + a_{n}x_n \le b_i$ or $\ge b_i$ or $= b_i$. The values $b_i$ on the right side are known as the right-hand side (RHS) values.

Modifying the RHS value ($b_i$) directly impacts the boundary defined by that specific constraint. For example, consider the constraint $2x + 3y \le 10$. If the RHS changes to $8$ ($2x + 3y \le 8$), the constraint becomes tighter, and the feasible region potentially shrinks. If the RHS changes to $12$ ($2x + 3y \le 12$), the constraint is relaxed, and the feasible region might expand.

Crucially, if the RHS values are adjusted such that the constraints become contradictory (e.g., requiring $x \le 2$ and $x \ge 3$ simultaneously, perhaps indirectly through multiple constraints), then no solution can satisfy all constraints. In this scenario, the feasible region becomes empty, and the problem loses feasibility. Thus, changes in the RHS are a direct cause of feasibility changes.

3. Addition of a New Variable

Introducing a new decision variable (e.g., adding $x_{n+1}$) expands the problem into a higher-dimensional space. While this changes the overall structure and potentially the optimal solution, it doesn't automatically make the original feasible set (now a subset of the new space) infeasible. New constraints involving the new variable might be added, which could affect feasibility, but the act of adding the variable itself isn't the direct cause in the same way modifying an existing boundary (RHS) is. Often, adding variables expands possibilities rather than eliminating them.

4. Feasibility Does Not Change

As demonstrated in the analysis of Option 2, feasibility *can* change based on modifications to the constraints, specifically the RHS values. This option is therefore incorrect.

Conclusion on Feasibility Change

The most direct and common reason for feasibility to change in a linear programming problem is a modification to the right-hand side values of its constraints. These changes alter the boundaries of the feasible region, potentially leading to a situation where no solution satisfies all requirements.