Solution Space: Feasible Region

Graphical Representation of Linear Inequalities

Representing Constraints on the Cartesian Plane

In Linear Programming Problems (LPPs) involving two decision variables, conventionally denoted as $x$ and $y$, each constraint is expressed as a linear inequality or, occasionally, a linear equation. When we solve such LPPs using the graphical method, the first essential step is to visualize these constraints on a two-dimensional Cartesian plane. Each linear inequality in two variables corresponds to a specific region on this plane called a half-plane.

A linear equation of the form $ax + by = c$ represents a straight line in the $xy$-plane. This line divides the plane into two half-planes. A linear inequality like $ax + by \le c$ or $ax + by \ge c$ represents one of these two half-planes, including the boundary line itself. Strict inequalities ($ax + by < c$ or $ax + by > c$) represent a half-plane excluding the boundary line. Standard LPP formulations primarily use inclusive inequalities ($\le$ or $\ge$).

Steps for Graphing a Linear Inequality

To accurately represent a single linear inequality, such as $ax + by \le c$ or $ax + by \ge c$, on the Cartesian plane, follow these systematic steps:

Step 1: Draw the Boundary Line

Convert the inequality into a linear equation by replacing the inequality sign ($\le, \ge, <, >$) with an equality sign (=). This equation, $ax + by = c$, represents the straight line that forms the boundary of the region defined by the inequality.

To draw this line, find any two distinct points that lie on it and connect them with a straight line. The easiest points to find are usually the intercepts with the axes:

• To find the $y$-intercept, set $x=0$ in the equation and solve for $y$. The point is $(0, y)$.
• To find the $x$-intercept, set $y=0$ in the equation and solve for $x$. The point is $(x, 0)$.
• If the line passes through the origin $(0,0)$ (i.e., $c=0$), find one intercept (it will be (0,0)) and then find another point by choosing any non-zero value for $x$ (or $y$) and solving for the other variable.

When drawing the line:

• Use a solid line if the original inequality includes equality ($\le$ or $\ge$). This indicates that the points lying on the boundary line are considered part of the solution set of the inequality. In standard LPPs, constraints are typically inclusive inequalities, so solid lines are common.
• Use a dashed or broken line if the original inequality is strict ($<$ or $>$). This indicates that the points on the boundary line are *not* part of the solution set. (Strict inequalities are less common in introductory LPP formulations).

Step 2: Choose and Test a Point

Select any point on the Cartesian plane that does not lie on the boundary line drawn in Step 1. This test point will help you determine which side of the line represents the solution to the inequality. The origin, with coordinates $(0, 0)$, is generally the most convenient test point to use, provided the boundary line $ax + by = c$ does not pass through $(0, 0)$ (i.e., $c \ne 0$). If the line passes through the origin, choose any other point not on the line, such as $(1, 0)$ or $(0, 1)$.

Substitute the coordinates of your chosen test point into the original inequality (before replacing the inequality sign with an equals sign).

Step 3: Determine and Shade the Solution Region (Half-Plane)

Based on the result of substituting the test point into the inequality in Step 2:

• If the substitution results in a true statement (e.g., $0 \le 12$ is true), then the half-plane containing the test point is the solution region for the inequality. Shade this entire region.
• If the substitution results in a false statement (e.g., $10 \le 5$ is false), then the half-plane that does not contain the test point is the solution region. Shade this other region.

This shaded area visually represents all possible pairs of $(x, y)$ values that satisfy the given single linear inequality.

Graphical Representation of Non-Negativity Constraints

The non-negativity restrictions, which are typically part of every LPP formulation involving real-world quantities, are also linear inequalities. For two variables $x$ and $y$, these are:

• $x \ge 0$: The boundary line is $x = 0$, which is the $y$-axis. Testing a point not on the line, say $(1, 0)$, gives $1 \ge 0$, which is true. So, the solution region is the half-plane to the right of the $y$-axis, including the $y$-axis itself (because it's $\ge$).

• $y \ge 0$: The boundary line is $y = 0$, which is the $x$-axis. Testing a point not on the line, say $(0, 1)$, gives $1 \ge 0$, which is true. So, the solution region is the half-plane above the $x$-axis, including the $x$-axis itself (because it's $\ge$).

When considered together, the non-negativity constraints $x \ge 0$ and $y \ge 0$ restrict the solution space to the area where these two half-planes overlap. This region is the entire first quadrant of the Cartesian plane, including the positive parts of the $x$-axis and $y$-axis. Any feasible solution to a standard LPP must lie within this quadrant.

(Illustrative graph of a single inequality $2x + y \le 4$)

(Illustrative graph of the region $x \ge 0, y \ge 0$)

Answer:

Step 1: Draw the Boundary Line

The boundary line equation is $3x + 4y = 24$.

• Find $y$-intercept (set $x=0$):

  $3(0) + 4y = 24$

  $4y = 24$

  $y = \frac{24}{4} = 6$

  Point: $(0, 6)$.

• Find $x$-intercept (set $y=0$):

  $3x + 4(0) = 24$

  $3x = 24$

  $x = \frac{24}{3} = 8$

  Point: $(8, 0)$.

Draw a straight line passing through points $(0, 6)$ and $(8, 0)$. Since the inequality is $3x + 4y \le 24$, use a solid line.

Step 2: Choose and Test a Point

Choose the test point $(0, 0)$, as the line does not pass through the origin ($3(0) + 4(0) = 0 \ne 24$).

Substitute $(0, 0)$ into the original inequality $3x + 4y \le 24$:

$3(0) + 4(0) \le 24$

$0 \le 24$

Step 3: Shade the Solution Region

The statement $0 \le 24$ is true. Therefore, the region containing the test point $(0, 0)$ is the solution region. Shade the half-plane below the line $3x + 4y = 24$.

[An image showing the line $3x+4y=24$ passing through (8,0) and (0,6) with the region below the line shaded would be displayed here.]

The process of graphically representing each linear inequality constraint is fundamental to solving two-variable LPPs using the graphical method. Each constraint's graph defines a permissible half-plane, and the combination of all these defines the feasible region.

Feasible Region: Definition and Identification

Defining the Feasible Region

In a Linear Programming Problem (LPP), a Feasible Solution is any combination of values for the decision variables that satisfies all the constraints of the problem simultaneously, including the non-negativity restrictions. The set of all such feasible solutions constitutes the Feasible Region (also known as the solution space, feasible set, or feasible domain).

The feasible region is essentially the collection of all points in the $n$-dimensional space (where $n$ is the number of decision variables) that do not violate any of the problem's restrictions. In the case of LPPs with two decision variables ($x, y$), the feasible region is a subset of the two-dimensional Cartesian plane.

Any point $(x, y)$ within or on the boundary of the feasible region represents a valid choice for the decision variables that is permissible given the limited resources and stated requirements. The optimal solution to an LPP, if one exists, must always be a point within the feasible region.

Identifying the Feasible Region Using the Graphical Method (for Two Variables)

For LPPs with only two decision variables, the feasible region can be visually determined by graphing all the constraints on the same coordinate plane. This process involves finding the area where all individual constraint requirements are met simultaneously.

Follow these steps to identify the feasible region graphically:

Step 1: Graph Each Constraint Individually

On a single Cartesian plane, graph each linear inequality constraint of the LPP separately. Use the steps outlined in the previous section (I1): draw the boundary line (solid for $\le$ or $\ge$, dashed for $<$ or $>$), test a point, and shade the corresponding half-plane that satisfies the inequality.

Crucially, remember to include the non-negativity constraints ($x \ge 0$ and $y \ge 0$). Graphing these restricts the area of consideration to the first quadrant (including the non-negative parts of the axes). Any region outside the first quadrant cannot be part of the feasible region in most real-world LPPs.

It can be helpful to use different colours or shading patterns for each constraint's satisfied region initially.

Step 2: Find the Intersection of All Regions

The feasible region is the area where the shaded regions of all constraints (including non-negativity) overlap. Visually inspect your graph to find the portion of the plane that has been shaded by every single constraint. This is the region where all inequalities are satisfied simultaneously.

Step 3: Clearly Mark and Label the Feasible Region

Once the common region of overlap is identified, clearly mark it on your graph. This is often done by re-shading it more distinctly or using boundary lines to enclose it. Label this region as the "Feasible Region".

The feasible region for an LPP with two variables will always have a specific geometric shape: it will be a convex polygon if it is bounded (enclosed on all sides), or a convex unbounded region if it extends infinitely in one or more directions. The boundary of the feasible region is formed by segments of the lines corresponding to the active constraints.

(Illustrative graph showing the intersection of multiple constraints forming the feasible region)

Answer:

We will graph each constraint and find the common region of overlap.

Constraint 1: $x + y \leq 6$

Boundary line: $x + y = 6$.

• If $x=0, y=6$. Point $(0, 6)$.
• If $y=0, x=6$. Point $(6, 0)$.

Test point $(0, 0)$: $0 + 0 \le 6 \implies 0 \le 6$ (True). Shade the region below the line $x+y=6$. Use a solid line.

Constraint 2: $2x + y \leq 8$

Boundary line: $2x + y = 8$.

• If $x=0, y=8$. Point $(0, 8)$.
• If $y=0, 2x=8 \implies x=4$. Point $(4, 0)$.

Test point $(0, 0)$: $2(0) + 0 \le 8 \implies 0 \le 8$ (True). Shade the region below the line $2x+y=8$. Use a solid line.

Constraints 3 & 4: $x \ge 0, y \ge 0$

$x \ge 0$ restricts the region to the right of the $y$-axis (including the $y$-axis).

$y \ge 0$ restricts the region to the above the $x$-axis (including the $x$-axis).

Together, these restrict the region to the first quadrant.

Identifying the Feasible Region:

Graph all four inequalities on the same plane. The feasible region is the area within the first quadrant that is simultaneously below the line $x+y=6$ and below the line $2x+y=8$.

[An image showing the graph with lines $x+y=6$ and $2x+y=8$ in the first quadrant, with the common region below both lines and in the first quadrant shaded. The vertices of the feasible region would be (0,0), (4,0), intersection of $2x+y=8$ and $x+y=6$, and (0,6).]

To find the intersection point of $2x+y=8$ and $x+y=6$, we can solve the system of equations:

$2x + y = 8$

... (A)

$x + y = 6$

... (B)

Subtract equation (B) from equation (A):

$\begin{array}{cc} & 2x & + y & = 8 \\ - & x & + y & = 6 \\ \hline & x & & = 2 \\ \hline \end{array}$

Substitute $x=2$ into equation (B):

$2 + y = 6$

$y = 6 - 2 = 4$

The intersection point is $(2, 4)$.

The feasible region is the polygon with vertices at $(0, 0)$, $(4, 0)$, $(2, 4)$, and $(0, 6)$. This region includes its boundaries.

Identifying the feasible region is a crucial step in the graphical method because the optimal solution to the LPP will always be found at one of the vertices (corner points) of this region, provided an optimal solution exists.

Feasible and Infeasible Regions (Graphical Interpretation)

Understanding the Solution Space: Feasible Region

The Feasible Region is the cornerstone of the graphical method for solving Linear Programming Problems (LPPs) with two variables. As discussed previously, it is the set of all points $(x, y)$ on the Cartesian plane that simultaneously satisfy all the linear constraints of the LPP, including the non-negativity restrictions ($x \ge 0, y \ge 0$).

Graphically, the feasible region is the area of intersection of the half-planes represented by each individual constraint. Every point $(x, y)$ located within or on the boundary of this region represents a feasible solution – a combination of decision variable values that adheres to all the limitations and requirements of the real-world problem being modelled. If a potential solution $(x, y)$ falls within this region, it means it is a valid and permissible course of action according to the problem's rules (e.g., you have enough resources to produce those quantities, the nutritional requirements are met).

(The shaded area in the graph above represents a typical feasible region for a two-variable LPP with $\le$ constraints and non-negativity.)

The Infeasible Region: Non-Permissible Solutions

Conversely, the Infeasible Region encompasses all points $(x, y)$ on the Cartesian plane that lie outside the feasible region. These points represent combinations of decision variable values that violate at least one of the constraints of the LPP.

Any point located in the infeasible region corresponds to an infeasible solution. This means the combination of $x$ and $y$ values at such a point is not allowed or is impossible to achieve given the problem's restrictions. For example, producing quantities of products that require more raw material than available, or designing a diet that does not meet minimum vitamin requirements, would correspond to points in the infeasible region. The optimal solution to an LPP can never be found in the infeasible region.

(The unshaded area outside the feasible region is the infeasible region.)

The Case of an Infeasible LPP (No Feasible Region)

In some cases, when attempting to graph all the constraints of an LPP, it may turn out that there is no common region where all the shaded half-planes overlap. This means that there is no single point $(x, y)$ that can simultaneously satisfy all the constraints, including the non-negativity restrictions.

When this happens:

• The feasible region is the empty set (it contains no points).
• There exists no feasible solution to the Linear Programming Problem.
• The LPP is termed infeasible.

An infeasible LPP usually indicates that the constraints defined are contradictory or overly restrictive, making it impossible to find a solution that satisfies all conditions at once. Graphically, you would see that the individual shaded regions for each constraint do not have any common overlapping area.

(In the graph above, suppose the constraints were $x+y \le 2$ and $x+y \ge 4$, along with non-negativity. The region for $x+y \le 2$ is below the line $x+y=2$, and the region for $x+y \ge 4$ is above the line $x+y=4$. These two regions do not overlap anywhere in the first quadrant, indicating no feasible region.)

Identifying an infeasible LPP graphically tells us that there is no valid solution, prompting a review of the problem formulation or the real-world assumptions.

Answer:

Let's graph each constraint:

Constraint 1: $x + 2y \le 4$

Boundary line: $x + 2y = 4$. Intercepts: $(4,0)$ and $(0,2)$. Test $(0,0)$: $0+0 \le 4$ (True). Shade below the line $x+2y=4$. Solid line.

Constraint 2: $x + 2y \ge 8$

Boundary line: $x + 2y = 8$. Intercepts: $(8,0)$ and $(0,4)$. Test $(0,0)$: $0+0 \ge 8$ (False). Shade above the line $x+2y=8$. Solid line.

Constraints 3 & 4: $x \ge 0, y \ge 0$

Restrict the region to the first quadrant.

When we graph these, we see that the region satisfying $x + 2y \le 4$ (below $x+2y=4$) and the region satisfying $x + 2y \ge 8$ (above $x+2y=8$) do not overlap anywhere, not even within the first quadrant. The two lines are parallel ($y = -\frac{1}{2}x + 2$ and $y = -\frac{1}{2}x + 4$), and their required regions lie on opposite sides with a gap in between.

[An image showing two parallel lines x+2y=4 and x+2y=8 in the first quadrant. The region below x+2y=4 is shaded in one direction, and the region above x+2y=8 is shaded in another direction. It is clear there is no overlapping shaded area in the first quadrant.]

There is no region on the graph that satisfies all constraints simultaneously.

Conclusion:

The feasible region is the empty set. The LPP is infeasible. There is no combination of $x$ and $y$ that satisfies all the given conditions.

Distinguishing between feasible and infeasible regions is vital. The feasible region contains all potential optimal solutions, while the infeasible region contains none. An empty feasible region means the problem itself has no solution that satisfies all its requirements.

Bounded and Unbounded Feasible Regions

Characteristics of the Feasible Region's Extent

Once the feasible region for an LPP with two variables is identified graphically, it is important to determine its nature, specifically whether it is "bounded" or "unbounded". This characteristic has significant implications for whether an optimal solution exists for the objective function.

1. Bounded Feasible Region

• Definition: A feasible region is considered bounded if it is entirely enclosed within a finite area. More technically, it is bounded if you can draw a circle of a sufficiently large radius around the origin such that the entire feasible region lies inside that circle.

• Graphical Appearance: A bounded feasible region always appears as a closed polygon on the graph. This polygon is formed by the intersection of the boundary lines of the constraints, usually within the first quadrant defined by the non-negativity constraints. Examples include triangles, quadrilaterals, pentagons, etc. Every point within a bounded region is a finite distance away from the origin.

• Significance for Optimization: If the feasible region of an LPP is bounded, then a fundamental theorem of Linear Programming (the Corner Point Theorem) guarantees that:

  • The objective function $Z$ will always have both a finite maximum value and a finite minimum value within this region.
  • These optimal values will occur at one or more of the corner points (vertices) of the feasible region.

  Finding the optimal solution in a bounded feasible region involves evaluating the objective function at each corner point and selecting the one that gives the desired maximum or minimum value.

(Example of a bounded feasible region, a closed polygon.)

2. Unbounded Feasible Region

• Definition: A feasible region is considered unbounded if it extends infinitely in at least one direction. You cannot draw any circle, no matter how large, that would completely enclose an unbounded feasible region.

• Graphical Appearance: An unbounded feasible region appears as a region in the graph that is bounded by line segments on some sides but opens up and extends infinitely in one or more directions (typically along the positive x and/or y axes in the first quadrant). It does not form a closed polygon.

• Significance for Optimization: When the feasible region is unbounded, an optimal solution (maximum or minimum) may or may not exist:

  • An optimal solution might exist at a corner point, similar to the bounded case. This happens if the objective function values do not continue to improve indefinitely as you move further into the unbounded part of the region.
  • However, it is also possible that the value of the objective function can be made arbitrarily large (for a maximization problem) or arbitrarily small (for a minimization problem) by choosing points further and further into the unbounded region. In such cases, the LPP is said to have an unbounded solution (or the objective function is unbounded over the feasible region). This means there is no finite maximum (for maximization) or no finite minimum (for minimization) value.

  Specifically, for an unbounded feasible region in the first quadrant:

  • If the objective is Maximization ($Z = ax + by$), and the coefficients $a > 0, b > 0$, the maximum value is often unbounded. However, it might be bounded if the unbounded edge of the feasible region slopes downwards relative to the objective function's increasing direction.
  • If the objective is Minimization ($Z = ax + by$), and the coefficients $a > 0, b > 0$, a minimum value usually exists at a corner point. It is less likely for the minimum to be unbounded unless the region extends infinitely towards large negative values of $x$ or $y$ (which is ruled out by non-negativity).

(Example of an unbounded feasible region, extending infinitely upwards and to the right.)

Identifying whether the feasible region is bounded or unbounded is crucial because it determines whether a finite optimal solution is guaranteed to exist and guides the process of finding it using corner points.

Answer:

Let's graph the constraints:

Constraint 1: $x + y \ge 4$

Boundary line: $x + y = 4$. Intercepts: $(4,0)$ and $(0,4)$. Test $(0,0)$: $0+0 \ge 4$ (False). Shade above the line $x+y=4$. Solid line.

Constraint 2: $2x + y \ge 6$

Boundary line: $2x + y = 6$. Intercepts: $(3,0)$ and $(0,6)$. Test $(0,0)$: $0+0 \ge 6$ (False). Shade above the line $2x+y=6$. Solid line.

Constraints 3 & 4: $x \ge 0, y \ge 0$

Restrict the region to the first quadrant.

The feasible region is the area within the first quadrant that is simultaneously above the line $x+y=4$ and above the line $2x+y=6$. Graphing this, we find the region above both lines and in the first quadrant.

[An image showing the lines $x+y=4$ and $2x+y=6$ in the first quadrant. The region above both lines and bounded by the axes segments is shaded.]

Looking at the shaded feasible region, we can see that it extends infinitely upwards and to the right. It cannot be enclosed by any circle.

Conclusion:

The feasible region is unbounded.

(Note: For an objective like Minimize $Z = 3x + 2y$ over this region, an optimal minimum solution would exist at a corner point. For Maximize $Z = 3x + 2y$, the solution would be unbounded).

The nature (bounded or unbounded) of the feasible region is a critical property to determine graphically, as it directly impacts whether a finite optimal solution can be found using the standard methods.