Linear Programming Ex 12.2: Graphical Method for Class 12 NCERT

Understanding Linear Programming Problems (LPPs) and the Graphical Method

Linear Programming is a technique for optimizing an objective function (e.g., maximizing profit or minimizing cost) subject to certain constraints, which are expressed as linear inequalities. These problems are ubiquitous in fields like business, engineering, and economics. For two-variable problems, the most intuitive and fundamental method of solution is the graphical method, which is the cornerstone of NCERT Exercise 12.2. The core idea is to represent all constraints as linear inequalities on a graph, identify the region that satisfies all these inequalities simultaneously (known as the feasible region), and then evaluate the objective function at the 'corner points' of this feasible region to find the optimal solution. The Corner Point Theorem is critical here; it states that the optimal solution (maximum or minimum) of a linear programming problem, if it exists, occurs at one of the corner points of the feasible region. This systematic approach allows us to solve complex real-world optimization challenges efficiently and accurately, providing tangible solutions for resource allocation, production planning, and much more. Pay close attention to identifying the correct feasible region and its vertices, as these are common areas for errors.

Essential Terms in Linear Programming

Objective Function

A linear function, Z = ax + by, which is to be maximized or minimized. This function represents the quantity we want to optimize, such as profit, cost, or production.

Constraints

A set of linear inequalities or equations that impose restrictions on the variables (x, y) of the LPP. These limitations arise from resource availability, production capacities, or other practical conditions. Non-negativity constraints (x ≥ 0, y ≥ 0) are always implied.

Feasible Region

The common region determined by all the constraints, including the non-negativity constraints (x ≥ 0, y ≥ 0), of an LPP. Every point within or on the boundary of this region represents a feasible solution.

Feasible Solution

Any set of values (x, y) that satisfies all the constraints of the LPP is called a feasible solution. Points within the feasible region are feasible solutions.

Optimal Solution

A feasible solution that optimizes (maximizes or minimizes) the objective function is called the optimal solution. According to the Corner Point Theorem, this solution always occurs at a corner (vertex) of the feasible region.

Corner Point Theorem

This fundamental theorem states that if an optimal solution for an LPP exists, it must occur at one of the corner points (vertices) of the feasible region. If the feasible region is unbounded, an optimal solution may or may not exist.

Step-by-Step Graphical Method for Solving LPPs

1. Step 1: Formulate the LPP (if not given) — Clearly define the decision variables (e.g., x and y), the objective function (Z = ax + by), and all the linear constraints (inequalities) based on the problem statement. Don't forget the non-negativity constraints: x ≥ 0, y ≥ 0.
2. Step 2: Convert Inequalities to Equations and Plot — For each constraint inequality, replace the inequality sign (≤, ≥) with an equality sign (=) to obtain a linear equation. Plot each of these lines on a graph. To plot a line, find its x and y intercepts (e.g., set x=0 to find y, and y=0 to find x).
3. Step 3: Determine the Feasible Region — For each inequality, choose a test point (usually (0,0) if it doesn't lie on the line) and substitute its coordinates into the original inequality. If the inequality holds true, the region containing the test point is the solution region for that inequality. If false, the region opposite to the test point is the solution. The feasible region is the common region that satisfies all constraints, including x ≥ 0 (first quadrant) and y ≥ 0 (first quadrant). This region can be bounded (enclosed polygon) or unbounded.
4. Step 4: Identify Corner Points — Find the coordinates of all the corner points (vertices) of the feasible region. These points are the intersections of the lines forming the boundaries of the feasible region. Some points might be intercepts with the axes, others might be intersections of two constraint lines. Solve the corresponding equations simultaneously to find these intersection points.
5. Step 5: Evaluate the Objective Function — Substitute the coordinates of each corner point into the objective function (Z = ax + by) to find the value of Z at each corner point. Keep a clear record of these values.
6. Step 6: Determine the Optimal Solution — If the objective function is to be maximized, the largest value of Z obtained from Step 5 is the maximum value, and the corresponding corner point gives the optimal solution. If it's to be minimized, the smallest value of Z is the minimum value. If the feasible region is unbounded, a further check is needed (see Exam Tips).

Solved Examples from NCERT Ex 12.2

• Example 1: Maximization Problem Maximize Z = 4x + y Subject to the constraints: x + y ≤ 50 x ≥ 10 y ≥ 0 Solution: Step 1: Identify objective function and constraints. Objective Function: Maximize Z = 4x + y Constraints: (1) x + y ≤ 50, (2) x ≥ 10, (3) y ≥ 0 Step 2: Plot the lines corresponding to the constraints. For x + y = 50: If x=0, y=50. If y=0, x=50. Points: (0,50), (50,0). For x = 10: A vertical line passing through x=10. For y = 0: The x-axis. Step 3: Determine the feasible region. For x + y ≤ 50: Test (0,0). 0+0 ≤ 50 (True). Region towards the origin. For x ≥ 10: Region to the right of x=10. For y ≥ 0: Region above the x-axis. The feasible region is a triangle with vertices A, B, C. Step 4: Identify corner points. Intersection of x=10 and x+y=50: Substitute x=10 into x+y=50 => 10+y=50 => y=40. Point A = (10, 40). Intersection of x=10 and y=0: Point B = (10, 0). Intersection of x+y=50 and y=0: Substitute y=0 into x+y=50 => x+0=50 => x=50. Point C = (50, 0). Step 5: Evaluate Z at each corner point. At A(10, 40): Z = 4(10) + 40 = 40 + 40 = 80. At B(10, 0): Z = 4(10) + 0 = 40. At C(50, 0): Z = 4(50) + 0 = 200. Step 6: Determine the optimal solution. The maximum value of Z is 200, which occurs at the corner point (50, 0). Final answer: The maximum value of Z is 200 at x=50, y=0.
• Example 2: Minimization Problem Minimize Z = 3x + 2y Subject to the constraints: x + y ≥ 8 3x + 5y ≤ 15 x ≥ 0, y ≥ 0 Solution: Step 1: Objective function and constraints. Objective Function: Minimize Z = 3x + 2y Constraints: (1) x + y ≥ 8, (2) 3x + 5y ≤ 15, (3) x ≥ 0, y ≥ 0 Step 2: Plot the lines. For x + y = 8: (0,8), (8,0). For 3x + 5y = 15: (0,3), (5,0). Step 3: Determine the feasible region. For x + y ≥ 8: Test (0,0). 0+0 ≥ 8 (False). Region away from the origin. For 3x + 5y ≤ 15: Test (0,0). 0+0 ≤ 15 (True). Region towards the origin. Combined with x ≥ 0, y ≥ 0 (first quadrant). Upon plotting, observe that the region satisfying x + y ≥ 8 (above line 1) and 3x + 5y ≤ 15 (below line 2) along with x ≥ 0, y ≥ 0 does not overlap. There is no common region that satisfies all constraints simultaneously. Step 4: Conclusion. Since there is no common feasible region, the LPP has no feasible solution. Final answer: The problem has no feasible solution, hence no optimal solution exists.

Key Exam Tips for Linear Programming Problems

When solving LPPs, precision is key. First, ensure your graph is neat and clearly labeled, including axes, lines, and the feasible region. Use a ruler and pencil! A common mistake is to misidentify the feasible region, especially with multiple constraints or when inequalities include 'greater than or equal to'. Always use a test point (like (0,0)) for each inequality to correctly shade the region. Don't forget the non-negativity constraints (x ≥ 0, y ≥ 0) – they restrict your feasible region to the first quadrant. For unbounded feasible regions, after finding the minimum/maximum at corner points, you must draw the graph of the inequality formed by setting Z < minimum value (for minimization) or Z > maximum value (for maximization). If this new region has no point in common with the feasible region, then the optimal value exists. Otherwise, no optimal solution exists. Always double-check your calculations for corner points and Z-values; small arithmetic errors can lead to incorrect optimal solutions.

Practice Questions with Solutions

• Q: Minimize Z = 200x + 500y Subject to the constraints: x + 2y ≥ 10 3x + 4y ≤ 24 x ≥ 0, y ≥ 0 A: Step 1: Identify objective function and constraints. Minimize Z = 200x + 500y. Constraints: (1) x + 2y ≥ 10, (2) 3x + 4y ≤ 24, (3) x ≥ 0, y ≥ 0. Step 2: Plot the lines. For x + 2y = 10: (0,5), (10,0). For 3x + 4y = 24: (0,6), (8,0). Step 3: Determine feasible region. For x + 2y ≥ 10 (away from origin). For 3x + 4y ≤ 24 (towards origin). Combined with x ≥ 0, y ≥ 0, the feasible region is a bounded quadrilateral. Step 4: Identify corner points. Intersection of x+2y=10 and y=0: (10,0). Intersection of 3x+4y=24 and x=0: (0,6). Intersection of x+2y=10 and x=0: (0,5). Intersection of x+2y=10 and 3x+4y=24: Multiply (1) by 3: 3x+6y=30. Subtract (2) from this: (3x+6y)-(3x+4y) = 30-24 => 2y=6 => y=3. Substitute y=3 into x+2y=10 => x+6=10 => x=4. Point: (4,3). Corner points: (0,5), (0,6), (4,3), (10,0). Step 5: Evaluate Z. At (0,5): Z = 200(0) + 500(5) = 2500. At (0,6): Z = 200(0) + 500(6) = 3000. At (4,3): Z = 200(4) + 500(3) = 800 + 1500 = 2300. At (10,0): Z = 200(10) + 500(0) = 2000. Step 6: Determine optimal solution. The minimum value of Z is 2000. Final answer: The minimum value of Z is 2000 at x=10, y=0.
• Q: Maximize Z = x + 2y Subject to the constraints: x + y ≥ 3 x + 2y ≤ 10 x ≥ 0, y ≥ 0 A: Step 1: Objective function and constraints. Maximize Z = x + 2y. Constraints: (1) x + y ≥ 3, (2) x + 2y ≤ 10, (3) x ≥ 0, y ≥ 0. Step 2: Plot the lines. For x + y = 3: (0,3), (3,0). For x + 2y = 10: (0,5), (10,0). Step 3: Determine feasible region. For x + y ≥ 3 (away from origin). For x + 2y ≤ 10 (towards origin). Combined with x ≥ 0, y ≥ 0. The feasible region is a bounded quadrilateral. Step 4: Identify corner points. Intersection of x+y=3 and x=0: (0,3). Intersection of x+2y=10 and x=0: (0,5). Intersection of x+2y=10 and y=0: (10,0). Intersection of x+y=3 and y=0: (3,0). The intersection of x+y=3 and x+2y=10: Subtract (1) from (2): (x+2y)-(x+y) = 10-3 => y=7. Substitute y=7 into x+y=3 => x+7=3 => x=-4. This point is not in the first quadrant, so it's not a corner point of the feasible region defined by x,y >= 0. The actual corner points in the first quadrant are (0,3), (0,5), (10,0), and (3,0). Step 5: Evaluate Z. At (0,3): Z = 0 + 2(3) = 6. At (0,5): Z = 0 + 2(5) = 10. At (10,0): Z = 10 + 2(0) = 10. At (3,0): Z = 3 + 2(0) = 3. Step 6: Determine optimal solution. The maximum value of Z is 10. Note that it occurs at two corner points, (0,5) and (10,0), and thus at every point on the line segment joining them. Final answer: The maximum value of Z is 10, occurring at (0,5) and (10,0) and all points on the line segment connecting them.
• Q: Minimize Z = x + 3y Subject to the constraints: x + 2y ≤ 20 x + y ≥ 10 x ≥ 0, y ≥ 0 A: Step 1: Objective function and constraints. Minimize Z = x + 3y. Constraints: (1) x + 2y ≤ 20, (2) x + y ≥ 10, (3) x ≥ 0, y ≥ 0. Step 2: Plot the lines. For x + 2y = 20: (0,10), (20,0). For x + y = 10: (0,10), (10,0). Step 3: Determine feasible region. For x + 2y ≤ 20 (towards origin). For x + y ≥ 10 (away from origin). Combined with x ≥ 0, y ≥ 0. The feasible region is a line segment between (0,10) and (10,0), and a quadrilateral including these two points, extending to (20,0) and (0,10). Step 4: Identify corner points. Intersection of x+2y=20 and x=0: (0,10). Intersection of x+2y=20 and y=0: (20,0). Intersection of x+y=10 and x=0: (0,10). Intersection of x+y=10 and y=0: (10,0). The two lines intersect at (0,10) and (10,0). So, the corner points of the feasible region (which is a quadrilateral) are (0,10), (10,0), (20,0), and (0,10). Step 5: Evaluate Z. At (0,10): Z = 0 + 3(10) = 30. At (10,0): Z = 10 + 3(0) = 10. At (20,0): Z = 20 + 3(0) = 20. Step 6: Determine optimal solution. The minimum value of Z is 10. Final answer: The minimum value of Z is 10 at x=10, y=0.
• Q: Maximize Z = 3x + 2y Subject to the constraints: x + y ≤ 4 x - y ≤ 2 x ≥ 0, y ≥ 0 A: Step 1: Objective function and constraints. Maximize Z = 3x + 2y. Constraints: (1) x + y ≤ 4, (2) x - y ≤ 2, (3) x ≥ 0, y ≥ 0. Step 2: Plot the lines. For x + y = 4: (0,4), (4,0). For x - y = 2: (0,-2), (2,0). Step 3: Determine feasible region. For x + y ≤ 4 (towards origin). For x - y ≤ 2 (test (0,0): 0-0 ≤ 2 (True) - towards origin). Combined with x ≥ 0, y ≥ 0. The feasible region is a bounded quadrilateral. Step 4: Identify corner points. Intersection of x+y=4 and x=0: (0,4). Intersection of x+y=4 and y=0: (4,0). Intersection of x-y=2 and y=0: (2,0). Intersection of x-y=2 and x=0: (0,-2) (not in 1st quadrant). Intersection of x+y=4 and x-y=2: Add the two equations: (x+y)+(x-y) = 4+2 => 2x=6 => x=3. Substitute x=3 into x+y=4 => 3+y=4 => y=1. Point: (3,1). Corner points: (0,0), (2,0), (3,1), (0,4). Step 5: Evaluate Z. At (0,0): Z = 3(0) + 2(0) = 0. At (2,0): Z = 3(2) + 2(0) = 6. At (3,1): Z = 3(3) + 2(1) = 9 + 2 = 11. At (0,4): Z = 3(0) + 2(4) = 8. Step 6: Determine optimal solution. The maximum value of Z is 11. Final answer: The maximum value of Z is 11 at x=3, y=1.

Frequently Asked Questions