Graphical Method in LPP: Corner Point Method, Feasible Region & Special Cases (Unbounded, Infeasible)
Two-Variable LPP, Extreme Point Theorem, Iso-Profit Line Analysis & Degenerate Solution Typology
1. The Graphical Method in LPP: Mathematical Foundations & The Feasible Region
The Graphical Method is a geometric visualization technique for solving Linear Programming Problems containing exactly two decision variables ($x_1$ and $x_2$). While real-world industrial models frequently contain hundreds of variables (requiring matrix algorithms like the Simplex method), the graphical method provides foundational visual intuition into how linear constraints shape the solution space.
1. Mathematical Foundations: Half-Planes & Convex Sets
Each linear inequality constraint (e.g., $a_1 x_1 + a_2 x_2 \le b$) divides the two-dimensional Cartesian plane into two distinct regions separated by a straight boundary line ($a_1 x_1 + a_2 x_2 = b$). The set of points satisfying the inequality constitutes a closed half-plane.
2. The Feasible Region (Solution Space)
The Feasible Region is the intersection of all half-planes determined by the system of constraints, including the non-negativity restrictions ($x_1 \ge 0, x_2 \ge 0$). Any point $(x_1, x_2)$ within this region satisfies all constraints simultaneously. Mathematically, the feasible region of a linear program possesses two vital geometric properties:
- Convexity: The feasible region is a convex setāmeaning that if any two points within the region are connected by a line segment, all points on that line segment also lie entirely within the region.
- Polygonal Boundary: In two dimensions, a bounded feasible region forms a closed convex polygon whose perimeter consists of straight-line boundary segments intersecting at sharp vertices (corner points).
Comparative Typology: Special Solution Cases in Graphical Linear Programming
| Solution Case | Geometric Appearance on Graph | Mathematical Condition | Managerial Interpretation |
|---|---|---|---|
| Unique Optimal Solution | A single, distinct corner point (vertex) touches the highest Iso-Profit line | Objective line slope does not match the slope of any active binding constraint | Clear, unambiguous production strategy with a single optimal product-mix |
| Multiple / Alternate Optima | The objective function line coincides exactly with an entire boundary edge | Slope of objective function equals slope of a binding constraint ($m_Z = m_C$) | Management enjoys flexibility; infinite combinations along the edge yield identical profit |
| Unbounded Solution | The feasible space is open-ended, extending infinitely into the positive quadrant | Constraints fail to restrict decision variables in direction of optimization | Indicates a flawed model formulation where management forgot critical resource ceilings |
| Infeasible (No Solution) | No common overlapping area exists among the constraint half-planes | Contradictory constraints (e.g., minimum demand requirement exceeds total machine capacity) | Conflicting managerial objectives; requirements cannot be satisfied simultaneously |
| Redundant Constraint | Constraint boundary line lies completely outside the active feasible space | The constraint does not touch, restrict, or alter the shape of the feasible polygon | Wasteful bookkeeping; resource is in such vast supply it can never become a bottleneck |
2. Solving Methodologies: Corner Point Method vs. Iso-Profit Line Method
Two distinct geometric approaches exist for locating the optimal point within the feasible polygon:
1. The Corner Point (Extreme Point) Method
This method is founded on the Extreme Point Theorem of Linear Programming, which proves that if an optimal solution exists, it must occur at one of the extreme boundary vertices of the feasible region:
- Step 1: Plot all constraint boundary lines on graph paper by identifying their X-axis and Y-axis intercepts.
- Step 2: Determine the feasible half-plane for each line using the origin $(0, 0)$ as a test point. Shade the common overlapping feasible polygon.
- Step 3: Identify all corner points (vertices) of the shaded feasible polygon (e.g., $O, A, B, C$).
- Step 4: Calculate the exact numerical coordinates of each vertex by solving the simultaneous linear equations of the two intersecting boundary lines.
- Step 5: Substitute the coordinates of each vertex into the objective function equation ($Z = c_1 x_1 + c_2 x_2$).
- Step 6: For a maximization problem, select the vertex yielding the maximum $Z$; for minimization, select the vertex yielding the minimum $Z$.
2. The Iso-Profit (or Iso-Cost) Line Method
Rather than evaluating every vertex, this method uses visual line translation:
- Draw an initial line for an arbitrary profit value (e.g., $c_1 x_1 + c_2 x_2 = Z_0$). The slope of this line is $-c_1 / c_2$.
- Translate this line outward parallel to itself in the direction of increasing profit.
- The optimal solution is the coordinates of the last point of the feasible region that the Iso-Profit line touches before leaving the feasible space completely.
3. Constraint Classification: Binding, Non-Binding and Redundant Constraints
Analyzing the status of constraints at the optimal corner point provides critical executive intelligence regarding resource bottlenecks:
- Binding (Active) Constraints: Constraints that pass directly through the optimal solution point. The available resource is 100% consumed, leaving zero unused slack ($s_i = 0$). These represent the operational bottlenecks restricting further profit growth. Expanding these resources directly increases profit.
- Non-Binding (Inactive) Constraints: Constraints that do not pass through the optimal corner point. At optimality, consumption is strictly less than available capacity, resulting in positive unused slack ($s_i > 0$). Expanding these resources yields zero increase in profit.
- Redundant Constraints: Constraints whose removal has zero impact on the feasible region. Recognizing redundancy prevents managers from wasting time and capital auditing non-restrictive resources.
Extreme Point Evaluation & Solved Graphical LPP Numerical Problem
Step-by-Step Solved Problem Illustration:
Problem Statement (AKTU Standard Numerical): Solve the following Linear Programming Problem graphically using the Corner Point Method: $\mathbf{\begin{aligned} \text{Maximize } & Z = 40x_1 + 30x_2 \\ \text{Subject to: } & (1)\; x_1 + x_2 \le 12 \quad \text{(Machine Hours)} \\ & (2)\; 2x_1 + x_2 \le 16 \quad \text{(Labor Hours)} \\ & (3)\; x_1 \le 7 \quad \text{(Market Demand Limit)} \\ \text{With: } & x_1 \ge 0,\; x_2 \ge 0 \end{aligned}}$ Provide step-by-step coordinate intercepts, vertex calculations, \(Z\)-evaluations, and identify binding vs non-binding resources.
- Determine Coordinate Axis Intercepts for Boundary Lines:
ā¢ Line 1 (\(x_1 + x_2 = 12\)): If \(x_1 = 0\), \(x_2 = 12\) ā Point \((0, 12)\); If \(x_2 = 0\), \(x_1 = 12\) ā Point \((12, 0)\). Test \((0, 0)\): \(0 + 0 \le 12\) (True, region includes origin).
ā¢ Line 2 (\(2x_1 + x_2 = 16\)): If \(x_1 = 0\), \(x_2 = 16\) ā Point \((0, 16)\); If \(x_2 = 0\), \(x_1 = 8\) ā Point \((8, 0)\). Test \((0, 0)\): \(0 + 0 \le 16\) (True, region includes origin).
ā¢ Line 3 (\(x_1 = 7\)): Vertical line passing through \(x_1 = 7\). Test \((0, 0)\): \(0 \le 7\) (True, region to the left of \(x_1 = 7\)). - Identify the Feasible Region: Plotting all three lines in the first quadrant (\(x_1 \ge 0,\; x_2 \ge 0\)) yields a closed 5-sided convex polygon with vertices: \(O, A, B, C, D\).
- Calculate Exact Coordinates of All 5 Vertices:
ā¢ Vertex \(O\): Origin \((0, 0)\);
ā¢ Vertex \(A\): Intersection of Line 1 with \(X_2\)-axis ā \((0, 12)\);
ā¢ Vertex \(B\): Intersection of Line 1 (\(x_1 + x_2 = 12\)) and Line 2 (\(2x_1 + x_2 = 16\)). Subtracting Eq (1) from Eq (2): \((2x_1 + x_2) - (x_1 + x_2) = 16 - 12 \rightarrow x_1 = 4\). Substitute \(x_1 = 4\) into Eq (1): \(4 + x_2 = 12 \rightarrow x_2 = 8\). Vertex \(B = (4, 8)\);
ā¢ Vertex \(C\): Intersection of Line 2 (\(2x_1 + x_2 = 16\)) and Line 3 (\(x_1 = 7\)). Substitute \(x_1 = 7\) into Eq (2): \(2(7) + x_2 = 16 \rightarrow 14 + x_2 = 16 \rightarrow x_2 = 2\). Vertex \(C = (7, 2)\);
ā¢ Vertex \(D\): Intersection of Line 3 (\(x_1 = 7\)) with \(X_1\)-axis ā \((7, 0)\). - Evaluate Objective Function \(Z = 40x_1 + 30x_2\) at Each Vertex:
ā¢ At Vertex \(O (0, 0)\): \(Z = 40(0) + 30(0) = ā¹0\);
ā¢ At Vertex \(A (0, 12)\): \(Z = 40(0) + 30(12) = ā¹360\);
ā¢ At Vertex \(B (4, 8)\): \(Z = 40(4) + 30(8) = 160 + 240 = ā¹400\) [Maximum];
ā¢ At Vertex \(C (7, 2)\): \(Z = 40(7) + 30(2) = 280 + 60 = ā¹340\);
ā¢ At Vertex \(D (7, 0)\): \(Z = 40(7) + 30(0) = ā¹280\). - Identify the Optimal Solution: $\mathbf{Z^* = ā¹400 \quad \text{at Vertex } B (x_1^* = 4, \; x_2^* = 8)}$
- Managerial Interpretation & Resource Slack: Optimal Product-Mix: Produce 4 units of Product 1 and 8 units of Product 2 to achieve a Maximum Profit of ā¹400. Constraint 1 (Machine Hours): \(4 + 8 = 12\) hours used out of 12 available ā Slack \(s_1 = 0\) (Binding Constraint / Bottleneck); Constraint 2 (Labor Hours): \(2(4) + 8 = 16\) hours used out of 16 available ā Slack \(s_2 = 0\) (Binding Constraint / Bottleneck); Constraint 3 (Market Limit): \(x_1 = 4 \le 7\) ā Slack \(s_3 = 7 - 4 = 3\) units (Non-Binding Constraint; firm has capacity to produce 3 more units of Product 1 if machine and labor hours are expanded).
4. Limitations of the Graphical Method
While the graphical method is pedagogically invaluable for developing geometric intuition, its practical operational utility is strictly limited:
- Dimensional Barrier: It cannot solve problems with more than two decision variables ($n > 2$). A three-variable problem requires 3D solid geometry, and $n ge 4$ variables enter hyper-dimensional space which cannot be drawn.
- Drawing Inaccuracy: Hand-drawn graphs are prone to parallax errors, scaling mistakes, and imprecise intersection readings when lines meet at acute angles.
2D Cartesian Space
Plotting straight-line constraint boundaries and non-negativity axes to form convex polygon feasible sets.
Extreme Point Theorem
Mathematical proof that optimal profit/cost must reside at an outer vertex (corner point) of the polygon.
Iso-Profit Line Shift
Parallel translation of objective slope line (-c_1/c_2) outward until touching the final exiting vertex.
Special Solution Cases
Multiple Optima (parallel boundary), Unbounded (open set), Infeasible (zero intersection), and Redundancy.
6. Corporate Case Vignette: Corporate Case Vignette: Amul Dairy Packaging & Batch Production Graphic Optimization
Background: Gujarat Cooperative Milk Marketing Federation (Amul) operates dairy processing plants packaging standardized pouch milk into two primary commercial SKUs: Amul Gold (Full Cream, $x_1$) and Amul Taaza (Toned Milk, $x_2$). Both products share pasteurization vat capacity and high-speed pouch-filling machinery.
The Operational Optimization Dilemma: At the Anand processing facility, daily milk intake fluctuated seasonally. Packaging lines operated with strict capacity limits: Pasteurization line (max 18,000 liters/shift) and Filling line (max 20,000 liters/shift). Amul Gold yielded a higher net margin contribution of ā¹4.50 per liter, while Amul Taaza yielded ā¹3.00 per liter. Cooperative commitments mandated producing at least 4,000 liters of Taaza daily to supply municipal schools.
Graphical Optimization Applied:
- Plant managers plotted the two-variable formulation on Cartesian coordinate axes, identifying the four boundary vertices of the daily feasible region.
- Evaluating the vertices proved that allocating maximum available capacity to Amul Gold up to the pasteurization ceiling, while satisfying the municipal school Taaza floor, was optimal.
- The optimal corner point achieved a daily contribution of ā¹82,500, identifying filling machine capacity as the sole binding bottleneck.
Strategic Outcome: Amul added a secondary high-speed filler head, which shifted the binding constraint line outward, expanding the feasible region and increasing plant daily throughput by 22% with zero milk spoilage.
7. AKTU Previous Years Questions & Model Solutions
The following questions reflect the official examination patterns, marks allocation, and rigorous mathematical evaluation guidelines of Dr. A.P.J. Abdul Kalam Technical University (AKTU) MBA Semester Examinations.
The Extreme Point Theorem states that if a linear programming problem possesses an optimal solution, that optimal solution must occur at one of the extreme boundary vertices (corner points) of the convex feasible region. If the optimal value occurs at more than one vertex, then all points on the line segment connecting those vertices are also optimal.
Multiple optimal solutions occur when the slope of the linear objective function is exactly parallel to the slope of a binding constraint boundary line. As the Iso-Profit line moves outward, it coincides with the entire boundary edge, meaning every point along that line segment yields the identical maximum profit.
An Infeasible solution occurs when there is no common overlapping area satisfying all constraints simultaneously (feasible region is empty). An Unbounded solution occurs when the feasible region is open-ended in the direction of optimization, allowing the objective value Z to increase infinitely (+ā) without violating any constraints.
Model Answer Structure:
1. Axis Intercepts: Calculate X and Y intercepts for all 3 boundary lines and verify test origin $(0, 0)$.
2. Graph Construction: Draw the 2D Cartesian plane, plot lines, and shade the convex polygon feasible region.
3. Vertex Coordinates Calculation: Identify all corner points ($O, A, B, C, D$) and compute exact $(x_1, x_2)$ coordinates by solving intersecting simultaneous equations.
4. Objective Function Evaluation: Present a neat tabular calculation of $Z = 30x_1 + 20x_2$ at each vertex.
5. Optimal Solution Identification: State the optimal vertex $(x_1^*, x_2^*)$ and maximum profit value $Z^*$.
6. Slack & Constraint Analysis: Calculate slack $s_i$ for each constraint. Formally declare which constraints are Binding (bottlenecks) and which are Non-Binding (excess capacity).
Discussion & Questions
0 CommentsAcademic insights, questions, and conceptual clarifications from students & faculty.
No questions or comments yet
Have a doubt about this topic, an exam tip, or a conceptual perspective? Start the discussion below!
Leave a Comment / Ask a Question
Your email address will not be published. Required fields are marked *