Feasible and Infeasible Region

Suppose the constraints of a problem are written as:

• \(a_1x + b_1y \le c_1\)
• \(a_2x + b_2y \ge c_2\)
• \(x \ge 0, \; y \ge 0\)

Then the feasible region is the set

\( \{ (x, y) : (x, y) \text{ satisfies all the above constraints} \}. \)

In simple words: collect all the points that obey every rule. That collection of points is the feasible region.

Each inequality gives a half-plane. Non-negativity constraints, such as \(x \ge 0\) and \(y \ge 0\), keep us in the first quadrant. When all these half-planes are taken together, their overlapping part is the feasible region.

So the feasible region is formed by:

• drawing each constraint as a line and shading its suitable side,
• keeping only the area where all shaded parts overlap.

On a graph, it helps to think about the feasible region as a visible shape, usually a polygon or a region bounded by straight lines. Looking at this shape tells a lot about the possible solutions and the kind of optimum one can expect.

Consider the constraints:

• \(x + y \le 6\)
• \(x \ge 0\)
• \(y \ge 0\)

Steps:

1. Draw the line \(x + y = 6\). It cuts the axes at \( (6, 0) \) and \( (0, 6) \).
2. Shade the region below or on this line, because of \(\le\).
3. Apply \(x \ge 0\) and \(y \ge 0\). This keeps only the first quadrant.

The overlapping area is a right triangle with vertices \((0, 0), (6, 0), (0, 6)\). This triangle is the feasible region for this system.

Often, the feasible region is a closed and bounded polygon (like a triangle, quadrilateral, or some other convex polygon). This happens when:

• there are enough constraints to enclose the region completely, and
• non-negativity constraints and upper limits cut off the region on all sides.

In such cases, the feasible region is a finite area. The objective function (if linear) will definitely have both a maximum and a minimum value on this region.

Sometimes the feasible region opens out in one or more directions. In that case, it is called an unbounded feasible region. It still satisfies all constraints, but it stretches to infinity in at least one direction.

Even if the region is unbounded, it can still give a finite optimum value for some objective functions. However, there are cases where the objective function also increases without limit, and then no maximum exists.

If the system of constraints is such that there is no common solution, the situation is called infeasible. That means:

\( \{ (x, y) : (x, y) \text{ satisfies all constraints} \} = \emptyset \)

Here, \(\emptyset\) stands for the empty set.

Infeasibility usually appears when some constraints contradict each other. For example:

• One constraint may demand that a certain expression is at most a value, while another might require it to be at least a bigger value.
• Physical or logical conditions might be unrealistic when combined.

When the demands are impossible to satisfy together, no feasible region exists.

On the graph, infeasibility shows up when the shaded half-planes of different inequalities do not overlap at all. Each constraint still has its own region, but their intersection is empty.

Sometimes, parallel lines with conflicting inequalities give a clear sign. For example, constraints like:

• \(x + y \le 2\)
• \(x + y \ge 5\)

These two half-planes do not touch each other, so there is no common region.

Consider the system:

• \(x + y \le 1\)
• \(x + y \ge 4\)

First inequality: shade the region on or below the line \(x + y = 1\).
Second inequality: shade the region on or above the line \(x + y = 4\).

The two shaded parts are separated by a gap. There is no point \((x, y)\) that can satisfy both inequalities together. So the problem is infeasible.

Each boundary line comes from changing an inequality to an equality, for example:

• \(2x + y = 10\)
• \(x + 3y = 12\)

A corner point is the intersection of two (or more) such boundary lines. To find it, solve the corresponding system of equations simultaneously. The solution gives the coordinates of the corner point.

For a linear objective function, something special happens: any maximum or minimum value, if it exists, will occur at a corner point of the feasible region. This is why most solution methods focus on evaluating the objective function at all corner points.

If there is no feasible region, there are no corner points and the optimization part of the problem cannot even begin.

If the constraints force the solution to lie on a single line, the feasible region is that line (or a part of it). For example, if we only have:

\(x + y = 5\)

and maybe some conditions that do not cut the line from both sides, all feasible points lie on that line. The region has no area, but it still has infinitely many feasible points along that line.

Sometimes all constraints together pin down a unique solution. In that case, the feasible region is just one point.

For example, if:

• \(x + y = 5\)
• \(x - y = 1\)

Solving these two equations gives a single pair \((x, y)\). With additional constraints that do not allow any movement around this point, the feasible region is simply that one point.