CBSE Class 12 Maths Chapter 12 Linear Programming Revision Notes

Section 1

Key Definitions in Linear Programming

Linear Programming Problem (LPP)

A method to achieve the best outcome (e.g., maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships.

Objective Function

The linear function (e.g., Z = ax + by) that needs to be maximized or minimized. It represents the quantity for which optimality is sought.

Constraints

A set of linear inequalities or equations that represent limitations or restrictions on the resources or conditions in the problem. These define the feasible region.

Non-Negative Restrictions

Constraints that state variables (like x and y) cannot be negative (x ≥ 0, y ≥ 0), as they often represent physical quantities such as number of items or production units.

Feasible Region

The common region determined by all the constraints, including non-negative restrictions. Any point within or on the boundary of this region is a feasible solution.

Feasible Solution

A set of values for the variables that satisfies all the constraints of the LPP.

Optimal Solution

A feasible solution that gives the maximum or minimum value of the objective function.

Corner Point Theorem

States that the optimal solution (maximum or minimum value) of the objective function, if it exists, occurs at one of the corner points (vertices) of the feasible region.

Understanding the Structure of an LPP and its Graphical Solution

A Linear Programming Problem fundamentally involves optimizing (maximizing or minimizing) a linear objective function subject to a set of linear constraints. These constraints are typically given as inequalities, defining a region in the coordinate plane. The variables involved, usually x and y, often represent quantities that cannot be negative, leading to non-negative restrictions (x ≥ 0, y ≥ 0).

The collection of all points that satisfy all the constraints simultaneously forms the feasible region. This region is always a convex polygon (bounded) or an unbounded convex region. Each point within this feasible region represents a feasible solution to the problem. The core idea is to find the specific point within this feasible region that yields the best possible value for our objective function.

The Graphical Method is the primary technique for solving LPPs with two variables. It involves plotting all the constraint inequalities to identify the feasible region. Each linear inequality defines a half-plane, and the intersection of all these half-planes forms the feasible region. Once the feasible region is identified, its corner points (vertices) are determined. According to the Corner Point Theorem, the optimal solution (maximum or minimum value of the objective function) must occur at one of these corner points. Thus, to find the optimal solution, we evaluate the objective function at each corner point and select the point that gives the desired maximum or minimum value. If the feasible region is unbounded, an optimal solution may or may not exist. For maximization, if the open half-plane defined by ax + by > Z_max has no point in common with the feasible region, then Z_max is the maximum value. Similarly for minimization.

Steps for Solving an LPP Graphically

1. —
2. —
3. —
4. —
5. —
6. —
7. —

Worked Example: Identifying Feasible Region

• {"title":"Problem Formulation & Feasible Region","bodyMarkdown":"Consider the following LPP:\nMaximize Z = 3x + 2y\nSubject to:\n1. x + 2y ≤ 10\n2. 3x + y ≤ 15\n3. x ≥ 0, y ≥ 0\n\nSolution Steps:\n1. Plot lines:\n For x + 2y = 10: Points are (10,0) and (0,5).\n For 3x + y = 15: Points are (5,0) and (0,15).\n2. Test origin (0,0):\n 0 + 2(0) ≤ 10 (0 ≤ 10) → True. Shade towards origin for x + 2y ≤ 10.\n 3(0) + 0 ≤ 15 (0 ≤ 15) → True. Shade towards origin for 3x + y ≤ 15.\n3. Feasible Region: The common region satisfying all inequalities (including x ≥ 0, y ≥ 0) is bounded by the points O(0,0), A(5,0), B(4,3), and C(0,5).\n Point B(4,3) is the intersection of x + 2y = 10 and 3x + y = 15 (solve simultaneously).\n4. Evaluate Z at corner points:\n Z(0,0) = 3(0) + 2(0) = 0\n Z(5,0) = 3(5) + 2(0) = 15\n Z(4,3) = 3(4) + 2(3) = 12 + 6 = 18\n * Z(0,5) = 3(0) + 2(5) = 10\n5. Optimal Solution: The maximum value of Z is 18, occurring at x=4, y=3."}

Must Remember: Key Points for LPP

• The feasible region is always a convex polygon (for bounded regions) or a convex set (for unbounded regions).
• If the feasible region is empty, then no feasible solution exists, and thus no optimal solution.
• If the objective function is to be maximized/minimized, its optimal value (if it exists) occurs at a corner point of the feasible region.
• For unbounded feasible regions, the objective function may or may not have a maximum or minimum value. Always verify by checking the open half-plane for intersection with the feasible region.
• Multiple optimal solutions can exist if the objective function line is parallel to one of the boundary lines of the feasible region and coincides with it at the optimal value. In such cases, all points on that boundary segment are optimal solutions.
• Non-negative restrictions (x ≥ 0, y ≥ 0) are critical and limit the feasible region to the first quadrant.
• Carefully plot the lines and accurately identify intersection points to avoid errors in determining corner points.
• Always state the optimal value of Z and the coordinates (x, y) at which it occurs as your final answer.

Exam Tip: Avoiding Common Traps

When solving LPP problems in exams, pay close attention to the direction of inequality signs. A common mistake is to shade the wrong side of the line, leading to an incorrect feasible region. Always test a point (like the origin if not on the line) to correctly identify the region. For unbounded regions, remember to perform the extra check: for maximization, if the region formed by ax + by > Z_max (or Z_min for minimization) has common points with the feasible region, then no maximum (or minimum) exists. Be precise with your graph, use a scale, and label axes and lines clearly. This helps you identify corner points accurately and fetches full marks for presentation.

Practice Questions with Solutions

• Q1: What does it mean if the feasible region of an LPP is unbounded? A: An unbounded feasible region means the set of feasible solutions extends infinitely in some direction. In such cases, an optimal solution (maximum or minimum) may or may not exist.
• Q2: Can an LPP have more than one optimal solution? A: Yes, an LPP can have multiple optimal solutions. This occurs when the objective function's optimal line segment coincides with an edge of the feasible region. Any point on that edge (including its endpoints) will yield the same optimal value.
• Q3: What is the significance of the non-negative restrictions in an LPP? A: Non-negative restrictions (x ≥ 0, y ≥ 0) are crucial because variables in practical LPPs (like quantities of products, number of hours) cannot be negative. They restrict the feasible region to the first quadrant of the coordinate plane.
• Q4: If an LPP has no feasible region, what can be concluded about its solution? A: If an LPP has no feasible region (i.e., the constraints contradict each other, and there's no common region satisfying all of them), then it has no feasible solution, and consequently, no optimal solution.

Frequently Asked Questions