Finding the Optimal Solution: Corner Point Method Principle

Corner Point Theorem: Statement

The foundation for solving Linear Programming Problems (LPPs) using graphical methods lies in the **Corner Point Theorem**. This theorem is a direct consequence of the properties of convex sets and linear functions, and it significantly simplifies the process of finding the optimal solution by limiting the search space.

Statement of the Corner Point Theorem

The theorem can be formally stated as follows:

Theorem: For a Linear Programming Problem with a linear objective function and a feasible region defined by linear constraints:

If an optimal solution (either a maximum or a minimum value of the objective function) exists, then this optimal value will occur at least at one of the **vertices** (also known as **corner points** or **extreme points**) of the feasible region.

This theorem applies whether the feasible region is a bounded polygon or an unbounded region, provided that an optimal solution actually exists for the problem.

---

Implication and Significance

The critical implication of the Corner Point Theorem for solving LPPs graphically is that the search for the optimal solution does not require evaluating the objective function at every single point within the feasible region. The feasible region typically contains infinitely many points, making an exhaustive search impossible.

Instead, the theorem guarantees that if an optimal solution exists, we only need to consider the values of the objective function at the finite number of vertices of the feasible region. The optimal value will be the maximum or minimum value found among these vertices.

This principle forms the basis of the **Corner Point Method**, the standard graphical technique for solving two-variable LPPs.

Evaluation of the Objective Function at Corner Points

Following the logic of the Corner Point Theorem, the practical step after identifying the vertices of the feasible region is to evaluate the objective function at each of these points. This evaluation provides the potential optimal values among which the true optimum will be found.

Steps for Evaluation

The process for evaluating the objective function at the corner points is as follows:

1. Identify the Feasible Region: Graph all the linear inequality constraints (and non-negativity restrictions) on a coordinate plane. The region that satisfies all constraints simultaneously is the feasible region.
2. Determine the Vertices: Find the coordinates $(x, y)$ of all the corner points (vertices) of the feasible region. These are the points where boundary lines intersect and lie within the feasible region. As seen in the previous section, finding these coordinates involves solving systems of two linear equations.
3. List the Vertices: Make a list of the coordinates of all the vertices found.
4. Evaluate the Objective Function: For each vertex $(x_v, y_v)$ in the list, substitute its coordinates into the objective function $Z = ax + by$ (for a two-variable problem, where $a$ and $b$ are coefficients) and calculate the corresponding value of $Z$.
5. Tabulate the Results: Organize the results clearly, typically in a table that lists each vertex, its coordinates, and the calculated value of the objective function at that vertex. This makes comparison easy.

---

Example of Evaluation Table

Consider an LPP with the objective function to Maximize $Z = 5x + 3y$. Suppose, after graphing the constraints and finding the intersection points, the vertices of the feasible region are determined to be A(0, 0), B(4, 0), C(2, 3), and D(0, 5).

We evaluate $Z$ at each of these vertices:

• At Vertex A(0, 0): $Z = 5(0) + 3(0) = 0 + 0 = 0$
• At Vertex B(4, 0): $Z = 5(4) + 3(0) = 20 + 0 = 20$
• At Vertex C(2, 3): $Z = 5(2) + 3(3) = 10 + 9 = 19$
• At Vertex D(0, 5): $Z = 5(0) + 3(5) = 0 + 15 = 15$

We can present these results in a table:

Vertex	Coordinates $(x, y)$	Objective Function Value $Z = 5x + 3y$
A	(0, 0)	$Z = 5(0) + 3(0) = 0$
B	(4, 0)	$Z = 5(4) + 3(0) = 20$
C	(2, 3)	$Z = 5(2) + 3(3) = 10 + 9 = 19$
D	(0, 5)	$Z = 5(0) + 3(5) = 15$

This table lists the value of the objective function at each potential optimal point. The next step is to interpret these values to find the actual optimal solution and value.

Identifying the Optimal Value and Optimal Solution(s)

Once the objective function has been evaluated at all the vertices of the feasible region, the final step in the Corner Point Method is to identify the optimal value and the corresponding optimal feasible solution(s). This is determined by simply comparing the calculated $Z$ values.

Steps for Identification

Using the table of vertex evaluations:

1. Compare $Z$ Values: Examine the column showing the values of the objective function $Z$ for all the vertices.
2. Identify the Optimal Value:
   • If the objective of the LPP is to **Maximize Z**: Find the largest numerical value among all the calculated $Z$ values. This largest value is the **maximum value** of the objective function.
   • If the objective of the LPP is to **Minimize Z**: Find the smallest numerical value among all the calculated $Z$ values. This smallest value is the **minimum value** of the objective function.
3. Identify the Optimal Solution(s):
   • The vertex (or vertices) whose objective function value matches the optimal value found in the previous step represents the **optimal feasible solution(s)**. The coordinates $(x, y)$ of this vertex (or vertices) give the specific values of the decision variables that achieve the desired optimal outcome (maximum profit, minimum cost, etc.).

It is important to clearly state both the optimal value (the best possible value of $Z$) and the optimal solution(s) (the point(s) $(x, y)$ that achieve this value).

---

Example Using the Evaluation Table from I2

Let's revisit the example where the objective is to Maximize $Z = 5x + 3y$, and the evaluated values at the vertices were:

Vertex	Coordinates $(x, y)$	Objective Function Value $Z = 5x + 3y$
A	(0, 0)	$Z = 0$
B	(4, 0)	$Z = 20$
C	(2, 3)	$Z = 19$
D	(0, 5)	$Z = 15$

• Comparison: The calculated values of $Z$ are 0, 20, 19, and 15.
• Identify Optimal Value (Maximize Z): The objective is to maximize $Z$. Comparing the values, the largest value is 20. Therefore, the **maximum value** of the objective function $Z$ is $\mathbf{20}$.
• Identify Optimal Solution(s): The maximum value $Z = 20$ occurs at vertex B, which has coordinates (4, 0). Thus, the **optimal feasible solution** is $\mathbf{(x, y) = (4, 0)}$.

Conclusion: For this LPP, the maximum value of the objective function $Z = 5x + 3y$ is $\mathbf{20}$, and this occurs when $x=4$ and $y=0$. This means the best outcome (e.g., maximum profit) is 20 units, achieved by setting decision variable $x$ to 4 and decision variable $y$ to 0.

Cases of Multiple Optimal Solutions

While a Linear Programming Problem (LPP) often yields a single optimal solution that occurs at a unique vertex of the feasible region, it is also possible for an LPP to have **multiple optimal solutions**.

Conditions for Multiple Optimal Solutions

Multiple optimal solutions arise under the following conditions:

1. The maximum (for maximization problems) or minimum (for minimization problems) value of the objective function $Z$ is attained at **two or more** distinct vertices of the feasible region.
2. If the optimal value is attained at two adjacent vertices (let's call them $V_1$ and $V_2$) of the feasible region, then every point on the line segment connecting $V_1$ and $V_2$ is also an optimal solution. All these points on the line segment will yield the exact same optimal value of the objective function.

Graphically, this phenomenon occurs when the objective function line (representing different values of $Z$, i.e., lines of the form $ax + by = Z$, where $Z$ varies) is **parallel** to one of the boundary edges of the feasible region, and this boundary edge happens to be where the objective function attains its optimal value. The entire edge (the line segment) becomes part of the set of optimal solutions.

---

Identification of Multiple Optimal Solutions

Multiple optimal solutions are easily identified when applying the Corner Point Method:

• After evaluating the objective function $Z$ at all the vertices of the feasible region, examine the list of $Z$ values.
• If the highest value (for a maximization problem) or the lowest value (for a minimization problem) is repeated for two or more different vertices, then multiple optimal solutions exist.
• The optimal solutions include all the vertices where the optimal value is attained, plus all points on the line segment(s) connecting any pair of these vertices that are adjacent on the boundary of the feasible region.

---

Example of Multiple Optimal Solutions

Answer:

Existence of Optimal Solution (for Bounded and Unbounded Regions)

The Corner Point Theorem is a powerful tool for finding the optimal solution *if* one exists. However, it doesn't guarantee that an optimal solution always exists for every LPP. The existence of an optimal solution depends on the nature of the feasible region and the objective function.

1. Bounded Feasible Region

A feasible region is considered **bounded** if it can be completely enclosed within a sufficiently large circle. In the case of two variables, a bounded feasible region is typically a convex polygon (or a single point).

• Definition: A region R is bounded if there exists a real number $M > 0$ such that for every point $(x, y)$ in R, we have $\sqrt{x^2 + y^2} \leq M$.
• Existence of Optimal Solution: If the feasible region of an LPP is non-empty and **bounded**, then the objective function $Z = ax + by$ is guaranteed to have **both a maximum value and a minimum value** within that region.
• Location of Optimal Solution: According to the Corner Point Theorem, these maximum and minimum values will occur at one or more of the vertices of the bounded feasible region.
• Procedure: If the feasible region is bounded, the process is straightforward: find all vertices, evaluate $Z$ at each, and the largest/smallest values are the maximum/minimum.

A bounded feasible region ensures that the objective function cannot increase or decrease indefinitely within the feasible set, thus guaranteeing the existence of finite maximum and minimum values.

---

2. Unbounded Feasible Region

A feasible region is considered **unbounded** if it extends infinitely in at least one direction. It cannot be enclosed within any circle, no matter how large.

• Definition: A region R is unbounded if for any real number $M > 0$, there exists a point $(x, y)$ in R such that $\sqrt{x^2 + y^2} > M$.
• Existence of Optimal Solution: If the feasible region is **unbounded**, an optimal solution (maximum or minimum) **may or may not exist**.
  • **Case 1: Optimal Solution Exists.** It is possible for the objective function to have a finite maximum or minimum value even in an unbounded feasible region. If an optimal solution exists in an unbounded region, it will still occur at one or more vertices.
  • **Case 2: Unbounded Solution.** The objective function value might increase indefinitely (for maximization problems) or decrease indefinitely (for minimization problems) as feasible points move further away from the origin within the unbounded region. In this case, the LPP has an **unbounded solution** (meaning no finite maximum or minimum exists).
• Procedure to Check for Optimality in Unbounded Regions:

  When the feasible region is unbounded, follow these steps after finding the minimum/maximum value among the vertices:

  1. Find the coordinates of all vertices of the unbounded feasible region.
  2. Evaluate the objective function $Z = ax + by$ at each of these vertices.
  3. Let $M$ be the maximum value found among the vertices (if maximizing). Graph the open half-plane defined by the inequality $ax + by > M$. If this open half-plane has **no point in common** with the feasible region, then $M$ is the maximum value, and the vertex(es) yielding $M$ are optimal solutions. If the half-plane $ax + by > M$ **has points in common** with the feasible region, it means we can find feasible points where $Z$ is greater than $M$, and potentially increase $Z$ indefinitely. Thus, the LPP has no maximum value (unbounded solution for maximization).
  4. Let $m$ be the minimum value found among the vertices (if minimizing). Graph the open half-plane defined by the inequality $ax + by < m$. If this open half-plane has **no point in common** with the feasible region, then $m$ is the minimum value, and the vertex(es) yielding $m$ are optimal solutions. If the half-plane $ax + by < m$ **has points in common** with the feasible region, it means we can find feasible points where $Z$ is less than $m$, and potentially decrease $Z$ indefinitely. Thus, the LPP has no minimum value (unbounded solution for minimization).

General Observation: For LPPs in the first quadrant ($x \geq 0, y \geq 0$) with a minimization objective $Z = ax + by$ where $a \ge 0$ and $b \ge 0$, if the feasible region is unbounded, the minimum value usually exists at a vertex. This is because the region $ax+by < m$ (for $m>0$) is typically bounded and will not overlap with an unbounded region in the first quadrant that goes towards increasing $x$ and $y$. Conversely, for maximization with $a \ge 0, b \ge 0$ in an unbounded first-quadrant region, the maximum value often does not exist (unbounded solution).