Graphical Method for Solving LPPs in Two Variables

Graphical Method of Solving an L.P.P: Overview and Steps

The Graphical Method is a visual technique used to solve Linear Programming Problems (LPPs) that involve only **two decision variables**. It leverages graphical representations to find the optimal solution by mapping out the problem constraints and the objective function on a two-dimensional plane.

This method is founded on the **Corner Point Theorem**, which provides the crucial insight that if an optimal solution exists for an LPP, it must be located at one of the vertices (corner points) of the feasible region.

General Steps for the Graphical Method

The process of solving a two-variable LPP using the graphical method involves the following general steps:

1. Formulate the LPP: Clearly define the problem in its mathematical form. This includes identifying the decision variables (typically denoted as $x$ and $y$), stating the objective function (which needs to be either maximized or minimized, represented as $Z = ax + by$), and listing all the linear constraints (which are usually inequalities, but can sometimes be equalities). Also, include the non-negativity restrictions for the decision variables, which are almost always $x \ge 0$ and $y \ge 0$ in real-world problems.
2. Graph the Constraints: Plot each constraint on a Cartesian coordinate system (the $xy$-plane). For each inequality constraint, treat it as a linear equation temporarily to draw the boundary line. Then, determine which side of the line represents the solution set for the original inequality. This is often done by testing a point (like the origin, $(0,0)$) in the inequality. Shade the appropriate half-plane for each constraint. The non-negativity constraints ($x \ge 0, y \ge 0$) restrict the solution space to the first quadrant.
3. Identify the Feasible Region: The feasible region is the area on the graph that satisfies all the constraints simultaneously. It is the region where the shaded areas of all the individual constraints overlap. If this common region is empty, the LPP is infeasible and has no solution. If it exists, it will be a convex set (a polygon if bounded, or an unbounded region with straight-line boundaries).
4. Find the Corner Points (Vertices): Identify the coordinates of all the vertices (corner points) of the feasible region. These are the points where the boundary lines of the feasible region intersect. For each vertex, determine its exact coordinates. This usually involves solving the system of two linear equations that correspond to the intersecting lines forming that vertex.
5. Evaluate the Objective Function: Substitute the coordinates $(x, y)$ of each vertex found in the previous step into the objective function $Z = ax + by$. Calculate the numerical value of $Z$ at each vertex. It's helpful to list these values, perhaps in a table.
6. Determine the Optimal Solution:
   • Compare the calculated values of $Z$ at all the vertices.
   • If the objective is to **Maximize Z**: The vertex that yields the largest value of $Z$ is the optimal solution point $(x^*, y^*)$, and this largest value is the optimal (maximum) value $Z^*$.
   • If the objective is to **Minimize Z**: The vertex that yields the smallest value of $Z$ is the optimal solution point $(x^*, y^*)$, and this smallest value is the optimal (minimum) value $Z^*$.
   • Special cases (like multiple optimal solutions occurring when the optimal value is attained at more than one vertex, or the LPP having an unbounded solution if the feasible region is unbounded and the objective function can increase/decrease indefinitely) should be considered and appropriately interpreted.

By following these steps, the graphical method allows us to find the values of the decision variables that optimize the objective function while respecting all the constraints.

Graphical Method of Solution for Problems in Two Variables (Detailed Procedure)

Here is a more detailed breakdown of the standard procedure for applying the graphical method to solve a Linear Programming Problem with exactly two decision variables, $x$ and $y$.

Detailed Steps for Solving an LPP Graphically

Step 1: Formulate the Mathematical Model

Ensure the LPP is clearly written in its standard mathematical form:

• Identify the decision variables, typically $x_1$ and $x_2$, or $x$ and $y$. Define what each variable represents in the real-world problem.
• Write the objective function as a linear expression of these variables, indicating whether it is to be maximized or minimized: Optimize $Z = c_1x_1 + c_2x_2$ (or $Z = ax + by$).
• Write down all the constraints as linear inequalities (or equations) in terms of the decision variables: $a_ix_1 + b_ix_2 (\le, \ge, =) d_i$.
• Explicitly state the non-negativity restrictions: $x_1 \ge 0, x_2 \ge 0$ (or $x \ge 0, y \ge 0$).

Step 2: Graph the Boundary Lines of the Constraints

• For each constraint inequality (e.g., $ax + by \le c$), temporarily replace the inequality sign with an equality sign to get the equation of the boundary line ($ax + by = c$).
• For each linear equation, find at least two points that lie on the line. The easiest points to find are usually the intercepts with the axes:
  • Set $x=0$ and solve for $y$ to find the y-intercept (point $(0, y_0)$).
  • Set $y=0$ and solve for $x$ to find the x-intercept (point $(x_0, 0)$).
  • If the line passes through the origin (e.g., $ax + by = 0$), you need to choose another non-zero value for $x$ or $y$ to find a second point.
• Draw these lines on a graph paper or graphing tool. Use a solid line for constraints with $\le$ or $\ge$ (since points on the line are included in the solution set) and a dashed line for strict inequalities $<$ or $>$ (though strict inequalities are less common in basic LPPs).

Step 3: Identify the Feasible Region (Solution Space)

• For each inequality constraint, determine which side of the boundary line represents the solution set. Choose a test point that does not lie on the line (the origin $(0,0)$ is often the most convenient test point, unless the line passes through it).
• Substitute the coordinates of the test point into the original inequality.
  • If the inequality holds true, the side of the line containing the test point is the solution region for that constraint.
  • If the inequality is false, the solution region is the side of the line opposite to the test point.
• Lightly shade or indicate the solution region for each constraint.
• The non-negativity constraints, $x \ge 0$ and $y \ge 0$, mean that the feasible region must lie in the first quadrant (including the positive x and y axes).
• The **feasible region** is the area on the graph that is the intersection of all the individual solution regions (including the first quadrant). Shade this common area more darkly. This region represents all the feasible solutions.
• If there is no area common to all constraints, the feasible region is empty, and the LPP has no feasible solution (it is an **infeasible LPP**).

Step 4: Find the Coordinates of the Vertices (Corner Points)

• Identify all the corner points (vertices) of the feasible region. These are the points where two or more boundary lines intersect on the perimeter of the feasible region.
• For each vertex, determine its exact $(x, y)$ coordinates.
  • Vertices on the axes are easy to find (e.g., y-intercept or x-intercept).
  • Vertices formed by the intersection of two lines require solving the system of two linear equations corresponding to those lines simultaneously. For example, if lines $L_1: a_1x + b_1y = c_1$ and $L_2: a_2x + b_2y = c_2$ intersect at a vertex, solve this system to find $(x, y)$. Methods like substitution or elimination are typically used.
• List the coordinates of all the vertices.

Step 5: Evaluate the Objective Function at Each Vertex

• Create a table with columns for "Vertex", "Coordinates $(x, y)$", and "Value of $Z$".
• For each vertex identified in Step 4, substitute its $(x, y)$ coordinates into the objective function $Z = ax + by$ and calculate the resulting value of $Z$.
• Record the vertex, its coordinates, and the calculated $Z$ value in the table.

Example Table Structure (from a previous section):

Step 6: Determine the Optimal Value and Optimal Solution(s)

• Examine the column of $Z$ values in the table from Step 5.
• If the objective is **Maximization**: Find the largest value among all calculated $Z$ values. This is the **maximum value** of the objective function. The vertex (or vertices) corresponding to this maximum value is the **optimal feasible solution(s)**.
• If the objective is **Minimization**: Find the smallest value among all calculated $Z$ values. This is the **minimum value** of the objective function. The vertex (or vertices) corresponding to this minimum value is the **optimal feasible solution(s)**.
• **Special Consideration for Unbounded Regions:** If the feasible region is unbounded, the value found in Step 5 might not be the true optimum. An additional check is required (as detailed in section I5 on Existence of Optimal Solution). If, for a maximization problem, the region $ax+by > Z_{max\_at\_vertex}$ overlaps with the feasible region, or for a minimization problem, the region $ax+by < Z_{min\_at\_vertex}$ overlaps with the feasible region, then the LPP has an unbounded solution (no finite max or min). Otherwise, the value found at the vertex is indeed the optimum.
• Finally, state the optimal solution(s) (the values of $x$ and $y$) and the resulting optimal value of $Z$.

This detailed procedure ensures a systematic approach to solving two-variable LPPs using the graphical method, relying fundamentally on the properties of linear functions and convex feasible regions as stated by the Corner Point Theorem.

Solving Maximization Problems Graphically

When the objective of a Linear Programming Problem (LPP) is to **maximize** a linear function $Z = ax + by$, the graphical method is used to find the values of the decision variables ($x$ and $y$) within the feasible region that result in the largest possible value of $Z$. The process follows the general steps of the graphical method, focusing on identifying the highest objective function value at the vertices.

Example: Maximization LPP

Answer:

Step 1: Formulate the Mathematical Model

The LPP is already formulated as given in the question.

• Decision variables: $x$ and $y$.
• Objective function: Maximize $Z = 3x + 4y$.
• Constraints: $x + y \le 4$, $2x + y \le 6$, $x \ge 0$, $y \ge 0$.

Step 2: Graph the Constraints and Find the Feasible Region

We convert the inequalities into equations to graph the boundary lines:

$x + y = 4$

[Line L1 for constraint (1)]

$2x + y = 6$

[Line L2 for constraint (2)]

$x = 0$

[y-axis for constraint (3)]

$y = 0$

[x-axis for constraint (3)]

Plotting the lines:

• For $x+y=4$: Points are (4,0) and (0,4). Test (0,0): $0+0 \le 4$ (True). The feasible region for this constraint is the half-plane containing the origin.
• For $2x+y=6$: Points are (3,0) and (0,6). Test (0,0): $2(0)+0 \le 6$ (True). The feasible region for this constraint is the half-plane containing the origin.
• For $x \ge 0$: Region to the right of the y-axis.
• For $y \ge 0$: Region above the x-axis.

The feasible region is the area in the first quadrant that is below or on the lines $x+y=4$ and $2x+y=6$. This region is bounded and is a polygon.

The feasible region is the shaded polygon OABC in the graph.

Step 3: Find the Coordinates of the Vertices (Corner Points)

The vertices of the feasible region OABC are the intersection points of the boundary lines:

• Vertex O: Intersection of $x=0$ and $y=0$. Coordinates: O(0, 0).
• Vertex A: Intersection of line L2 ($2x+y=6$) and $y=0$ (x-axis). Substituting $y=0$ into $2x+y=6$: $2x+0=6 \implies 2x=6 \implies x=3$. Coordinates: A(3, 0).
• Vertex C: Intersection of line L1 ($x+y=4$) and $x=0$ (y-axis). Substituting $x=0$ into $x+y=4$: $0+y=4 \implies y=4$. Coordinates: C(0, 4).
• Vertex B: Intersection of line L1 ($x+y=4$) and line L2 ($2x+y=6$). We solve the system of equations:

  $x + y = 4$

  ... (i)

  $2x + y = 6$

  ... (ii)

  Subtracting equation (i) from equation (ii):

  $(2x + y) - (x + y) = 6 - 4$

  $x = 2$

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

  $2 + y = 4$

  $y = 4 - 2$

  $y = 2$

  Coordinates: B(2, 2).

The vertices of the feasible region are O(0,0), A(3,0), B(2,2), and C(0,4).

Step 4: Evaluate the Objective Function at Each Vertex

We evaluate $Z = 3x + 4y$ at the coordinates of each vertex:

Vertex	Coordinates $(x, y)$	Objective Function Value $Z = 3x + 4y$
O	(0, 0)	$Z = 3(0) + 4(0) = 0$
A	(3, 0)	$Z = 3(3) + 4(0) = 9$
B	(2, 2)	$Z = 3(2) + 4(2) = 6 + 8 = 14$
C	(0, 4)	$Z = 3(0) + 4(4) = 0 + 16 = 16$

Step 5: Determine the Optimal Solution and Optimal Value

The feasible region OABC is bounded, so an optimal solution is guaranteed to exist at one of the vertices. We need to find the maximum value of $Z$ from the table.

• Comparing the Z values (0, 9, 14, 16), the largest value is 16.
• This maximum value occurs at vertex C(0, 4).

Conclusion: The maximum value of the objective function $Z = 3x + 4y$ is $\mathbf{16}$, and this occurs at the optimal feasible solution $\mathbf{(x, y) = (0, 4)}$.

Solving Minimization Problems Graphically

When the objective of a Linear Programming Problem (LPP) is to **minimize** a linear function $Z = ax + by$, the graphical method is used to find the values of the decision variables ($x$ and $y$) within the feasible region that result in the smallest possible value of $Z$. The process follows the general steps of the graphical method, focusing on identifying the lowest objective function value at the vertices and potentially verifying optimality in unbounded regions.

Example: Minimization LPP

Answer:

Step 1: Formulate the Mathematical Model

The LPP is already formulated as given in the question.

• Decision variables: $x$ and $y$.
• Objective function: Minimize $Z = 50x + 70y$.
• Constraints: $2x + y \ge 8$, $x + 2y \ge 10$, $x \ge 0$, $y \ge 0$.

Step 2: Graph the Constraints and Find the Feasible Region

We convert the inequalities into equations to graph the boundary lines:

$2x + y = 8$

[Line L1 for constraint (1)]

$x + 2y = 10$

[Line L2 for constraint (2)]

$x = 0$

[y-axis for constraint (3)]

$y = 0$

[x-axis for constraint (3)]

Plotting the lines:

• For $2x+y=8$: Points are (4,0) and (0,8). Test (0,0): $2(0)+0 \ge 8 \implies 0 \ge 8$ (False). The feasible region for this constraint is the half-plane opposite to the origin.
• For $x+2y=10$: Points are (10,0) and (0,5). Test (0,0): $0+2(0) \ge 10 \implies 0 \ge 10$ (False). The feasible region for this constraint is the half-plane opposite to the origin.
• For $x \ge 0$: Region to the right of the y-axis.
• For $y \ge 0$: Region above the x-axis.

The feasible region is the area in the first quadrant that is above or on both lines $2x+y=8$ and $x+2y=10$. This region is unbounded.

The feasible region is the shaded area above the polygon formed by the intersection of the boundary lines and the axes.

Step 3: Find the Coordinates of the Vertices (Corner Points)

The vertices of the unbounded feasible region are the intersection points where boundaries meet:

• Vertex A: Intersection of line L1 ($2x+y=8$) and $x=0$ (y-axis). Substituting $x=0$ into $2x+y=8$: $2(0)+y=8 \implies y=8$. Coordinates: A(0, 8).
• Vertex C: Intersection of line L2 ($x+2y=10$) and $y=0$ (x-axis). Substituting $y=0$ into $x+2y=10$: $x+2(0)=10 \implies x=10$. Coordinates: C(10, 0).
• Vertex B: Intersection of line L1 ($2x+y=8$) and line L2 ($x+2y=10$). We solve the system of equations:

  $2x + y = 8$

  ... (i)

  $x + 2y = 10$

  ... (ii)

  Multiply equation (i) by 2:

  $4x + 2y = 16$

  [Multiplying (i) by 2] ... (iii)

  Subtract equation (ii) from equation (iii):

  $(4x + 2y) - (x + 2y) = 16 - 10$

  $3x = 6$

  $x = 2$

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

  $2(2) + y = 8$

  $4 + y = 8$

  $y = 8 - 4$

  $y = 4$

  Coordinates: B(2, 4).

The vertices of the feasible region are A(0,8), B(2,4), and C(10,0).

Step 4: Evaluate the Objective Function at Each Vertex

We evaluate $Z = 50x + 70y$ at the coordinates of each vertex:

Vertex	Coordinates $(x, y)$	Objective Function Value $Z = 50x + 70y$
A	(0, 8)	$Z = 50(0) + 70(8) = 0 + 560 = 560$
B	(2, 4)	$Z = 50(2) + 70(4) = 100 + 280 = 380$
C	(10, 0)	$Z = 50(10) + 70(0) = 500 + 0 = 500$

Step 5: Determine the Optimal Solution and Optimal Value

The feasible region is unbounded. According to the Corner Point Theorem, if a minimum value exists, it must occur at a vertex. The smallest value of $Z$ found at the vertices is 380, which occurs at vertex B(2, 4). We need to verify if this is the true minimum value in the unbounded region.

Step 6: Check for Optimality in the Unbounded Feasible Region

The minimum value found among the vertices is $m = 380$. We graph the open half-plane $Z < m$, i.e., $50x + 70y < 380$. This is the region below the line $50x + 70y = 380$. We can simplify the equation to $5x + 7y = 38$. This line passes through the point B(2, 4) since $5(2) + 7(4) = 10 + 28 = 38$.

Test point (0,0) for $50x + 70y < 380$: $0 < 380$ (True). The half-plane $50x+70y < 380$ is the region towards the origin from the line $50x+70y=380$.

By examining the graph, we see that the open half-plane $50x + 70y < 380$ has **no points in common** with the feasible region (the shaded area above lines L1 and L2 in the first quadrant). This means there is no feasible solution that gives a value of $Z$ less than 380.

Therefore, the minimum value of $Z$ is indeed 380.

Conclusion: The minimum value of the objective function $Z = 50x + 70y$ is $\mathbf{380}$, and this occurs at the optimal feasible solution $\mathbf{(x, y) = (2, 4)}$. This indicates that to minimize cost while satisfying the constraints, the decision variables should be $x=2$ and $y=4$.

Handling Special Cases in the Graphical Method (No Feasible Solution, Unbounded Solution)

The graphical method is not only useful for finding unique optimal solutions but also provides a clear visual indication of special situations that can occur in Linear Programming Problems (LPPs). These special cases are:

1. No Feasible Solution (Infeasible LPP)
2. Unbounded Solution
3. Multiple Optimal Solutions

Understanding these cases is crucial for correctly interpreting the graphical output.

1. No Feasible Solution (Infeasible LPP)

An LPP has **no feasible solution** (or is called an **infeasible LPP**) if there is no set of values for the decision variables that can satisfy all the constraints simultaneously. This indicates that the constraints are contradictory or inconsistent.

• How it Occurs: When formulating an LPP, it is possible to set conflicting requirements that cannot be met at the same time. For example, demanding that the sum of two non-negative variables be both less than or equal to 5 and greater than or equal to 10.
• Graphical Indication: In the graphical method, after plotting the boundary lines for all constraints and determining the solution region for each inequality, the feasible region is the intersection of all these individual solution regions. If there is absolutely **no area** on the graph where all the shaded regions overlap, then the feasible region is empty.
• Conclusion: If the feasible region is empty, the LPP is infeasible. There are no points $(x, y)$ that satisfy all constraints, and therefore, no feasible solution exists. Since an optimal solution must be a feasible solution, an infeasible LPP has no optimal solution either. Such a situation requires re-examining the problem formulation to identify and correct the conflicting constraints.

The image above illustrates a case where the shaded regions for different constraints (shown by arrows pointing towards the solution side) do not have any common overlapping area. This means there is no feasible region.

Example of an Infeasible LPP

Answer:

2. Unbounded Solution

An LPP has an **unbounded solution** if the value of the objective function can be increased indefinitely (for maximization) or decreased indefinitely (for minimization) while remaining within the feasible region. This implies that there is no finite optimal value.

• How it Occurs: This can only happen when the feasible region is **unbounded** (extends infinitely in at least one direction). If the objective function's gradient points towards this infinite extension, its value can become arbitrarily large or small.
• Graphical Indication:
  1. The feasible region is an unbounded region on the graph.
  2. After finding the "best" value of $Z$ ($M$ for max, $m$ for min) among the vertices of the unbounded feasible region, perform the check for unboundedness:
     • For Maximization: Graph the open half-plane $ax + by > M$. If this region **overlaps** with the feasible region, the solution is unbounded for maximization.
     • For Minimization: Graph the open half-plane $ax + by < m$. If this region **overlaps** with the feasible region, the solution is unbounded for minimization.
• Conclusion: If the check reveals overlap, the LPP has an unbounded solution. There is no finite maximum (or minimum) value. In practical problems, an unbounded solution often suggests that a relevant constraint (e.g., resource limitation, demand limit) has been omitted in the problem formulation.

The image illustrates an unbounded feasible region and a dashed line representing the objective function value at a vertex ($Z=M$). The shaded area shows where $Z>M$. Since this area overlaps with the feasible region, higher values of Z are possible within the feasible region, extending infinitely, indicating an unbounded solution for maximization.

Example of an Unbounded Solution

Answer:

Graph Constraints and Find Feasible Region:

• Line 1: $x-y=1$. Points (1,0), (3,2), (0,-1). Test (0,0): $0-0 \le 1$ (True). Shade towards origin.
• Line 2: $x+y=3$. Points (3,0), (0,3). Test (0,0): $0+0 \ge 3$ (False). Shade away from origin.
• $x \ge 0, y \ge 0$: First quadrant.

The feasible region is the unbounded area in the first quadrant where the shading overlaps.

Find Vertices:

The vertices of this unbounded feasible region are:

• Intersection of $x+y=3$ and $y=0$: $(3, 0)$.
• Intersection of $x+y=3$ and $x-y=1$:

  $x + y = 3$

  ... (i)

  $x - y = 1$

  ... (ii)

  Adding (i) and (ii): $2x = 4 \implies x=2$. Substitute $x=2$ into (i): $2+y=3 \implies y=1$. Point is (2, 1).
• Intersection of $x-y=1$ and $x=0$: Substitute $x=0$ into $x-y=1$: $0-y=1 \implies y=-1$. This point (0,-1) is not in the first quadrant, so it is not a vertex of the feasible region.

The vertices are (3,0) and (2,1).

Evaluate Z = x + y at Vertices:

Vertex	Coordinates $(x, y)$	Objective Function Value $Z = x + y$
Vertex 1	(3, 0)	$Z = 3 + 0 = 3$
Vertex 2	(2, 1)	$Z = 2 + 1 = 3$

The maximum value of Z found at the vertices is $M = 3$. This value occurs at two vertices.

Check for Unbounded Solution (Maximization):

The feasible region is unbounded. We graph the open half-plane $Z > M$, i.e., $x + y > 3$. This is the region strictly above the line $x+y=3$.

Observing the graph, the region $x+y > 3$ (above the dashed line $x+y=3$) clearly **overlaps** with the feasible region (the shaded area). This means there are feasible points $(x,y)$ for which $x+y$ can be greater than 3, and we can find feasible points where $x+y$ is arbitrarily large.

Therefore, the objective function $Z=x+y$ is unbounded in the feasible region.

Conclusion: The LPP has an unbounded solution. There is no finite maximum value for $Z$.

3. Multiple Optimal Solutions

As discussed in the previous section (I4), an LPP can have **multiple optimal solutions** if the optimal value of the objective function is achieved at more than one feasible point.

• How it Occurs: This happens when the "slope" of the objective function line ($Z = ax + by$) is the same as the slope of one of the boundary edges of the feasible region, and that edge corresponds to the optimal value of $Z$.
• Graphical Indication:
  • The feasible region is formed by linear constraints.
  • When evaluating $Z$ at the vertices, the highest value (for maximization) or the lowest value (for minimization) is obtained at **two or more distinct vertices**.
  • If these vertices are adjacent (connected by an edge of the feasible region), the objective function line for the optimal value will coincide with the boundary edge connecting these vertices.
• Conclusion: If the optimal value occurs at multiple vertices, then all points lying on the line segment(s) connecting these vertices are also optimal solutions. All these points yield the same optimal value of the objective function.

The image shows an objective function line (dashed) evaluated at the optimal value. This line segment lies exactly on one of the boundary edges of the feasible region, indicating that all points on that edge segment are optimal solutions.

As shown in the example in the previous section (I4), if the maximum value of $Z = 4x + 6y$ is 36, and this occurs at both vertex R(3, 4) and vertex S(0, 6), then both R and S are optimal solutions. Furthermore, every point on the line segment RS is also an optimal solution, yielding $Z=36$.