Class 12 Mathematics Notes Chapter 12 (Linear Programming) – Examplar Problems (English) Book

Alright class, let's begin our detailed study of Chapter 12: Linear Programming. This is a crucial topic, not just for your board exams but also frequently tested in various government entrance exams due to its application in optimization problems. We'll focus on the core concepts as presented in NCERT and often elaborated upon in the Exemplar problems.

Chapter 12: Linear Programming - Detailed Notes

1. Introduction:

• What is Linear Programming? Linear Programming (LP) is a mathematical technique used to determine the best possible outcome (like maximum profit or minimum cost) in a given mathematical model whose requirements are represented by linear relationships.
• Why is it important? It's widely used in business, economics, engineering, and other fields for resource allocation, production planning, transportation scheduling, diet planning, etc., where you need to optimize a certain objective under given limitations.

2. Key Terminology:

• Decision Variables: These are the variables (usually denoted by x, y, etc.) that represent the quantities we need to determine. For example, the number of units of two different products to manufacture. These variables are non-negative (x ≥ 0, y ≥ 0).
• Objective Function: This is a linear function (e.g., Z = ax + by) that represents the quantity we want to maximize (e.g., profit) or minimize (e.g., cost). The coefficients 'a' and 'b' represent the per-unit contribution of each decision variable to the objective.
• Constraints: These are linear inequalities or equations (e.g., cx + dy ≤ e, fx + gy ≥ h, px + qy = r) that represent the limitations or restrictions on the decision variables. These arise from limited resources, specific requirements, etc.
• Non-Negative Restrictions: As mentioned, decision variables usually represent quantities and thus cannot be negative (x ≥ 0, y ≥ 0). These are also a type of constraint, often implicitly assumed.
• Linear Programming Problem (LPP): The problem of maximizing or minimizing the linear objective function Z subject to a set of linear constraints and non-negative restrictions is called an LPP.
• Feasible Region: This is the common region determined by all the constraints, including the non-negative restrictions, of an LPP. It represents the set of all possible combinations of decision variables that satisfy all the given conditions. Geometrically, it's a convex polygon (possibly unbounded) in the 2D plane (for two variables).
• Feasible Solution: Any point (x, y) that lies within or on the boundary of the feasible region is called a feasible solution. It represents a possible solution to the problem.
• Infeasible Solution: If there is no point (x, y) that satisfies all the constraints simultaneously, then there is no feasible solution, and the problem is called infeasible. The feasible region is empty in this case.
• Optimal Solution (or Optimal Feasible Solution): Any feasible solution that maximizes or minimizes the objective function is called an optimal solution.

3. Mathematical Formulation of an LPP:

• Step 1: Identify the unknown quantities to be determined (decision variables, say x and y).
• Step 2: Formulate the objective function (Z) as a linear expression in x and y, specifying whether it needs to be maximized or minimized.
• Step 3: Translate the restrictions/limitations given in the problem into a set of linear inequalities or equations (constraints) involving x and y.
• Step 4: Add the non-negativity restrictions (x ≥ 0, y ≥ 0).

4. Graphical Method for Solving LPP (for two variables):

This is the primary method taught at the Class 12 level.

• Step 1: Formulate the LPP mathematically (as described above).
• Step 2: Plot the constraints on a graph. Treat each inequality as an equation (e.g., cx + dy = e) to draw the corresponding straight line.
• Step 3: Determine the region represented by each inequality. A simple way is to test a point (like the origin (0,0), if the line doesn't pass through it) in the inequality. If it satisfies the inequality, the region containing the test point is the solution; otherwise, the region on the other side of the line is the solution.
• Step 4: Identify the Feasible Region, which is the intersection (common area) of all the regions determined in Step 3, including the first quadrant due to x ≥ 0, y ≥ 0.
• Step 5: Determine the coordinates of the Corner Points (Vertices) of the feasible region. These are the points where the boundary lines of the feasible region intersect.
• Step 6: Evaluate the Objective Function (Z) at each corner point.
• Step 7:
  • Bounded Feasible Region: If the feasible region is bounded (enclosed), the maximum or minimum value of Z will occur at one of the corner points (Fundamental Theorem of Linear Programming). The largest value among these is the maximum, and the smallest is the minimum.
  • Unbounded Feasible Region: If the feasible region is unbounded, an optimal solution may or may not exist.
    • Find the values of Z at the corner points. Let M be the maximum and m be the minimum value among these.
    • For Maximization: If the open half-plane defined by ax + by > M has points in common with the feasible region, then there is no maximum value (unbounded solution). Otherwise, M is the maximum value.
    • For Minimization: If the open half-plane defined by ax + by < m has points in common with the feasible region, then there is no minimum value (unbounded solution). Otherwise, m is the minimum value.

5. Important Theorems:

• Theorem 1: Let R be the feasible region (a convex polygon) for an LPP and let Z = ax + by be the objective function. When Z has an optimal value (maximum or minimum), where the variables x and y are subject to constraints described by linear inequalities, this optimal value must occur at a corner point (vertex) of the feasible region.
• Theorem 2: Let R be the feasible region for an LPP, and let Z = ax + by be the objective function. If R is bounded, then the objective function Z has both a maximum and a minimum value on R and each of these occurs at a corner point of R.
  • (Note: If R is unbounded, the optimal value may or may not exist, as explained in Step 7 above).

6. Special Cases in LPP:

• Multiple Optimal Solutions: If the objective function has the same optimal value (max or min) at two adjacent corner points of the feasible region, then every point on the line segment joining these two points is also an optimal solution. This happens when the line representing the objective function (ax + by = constant) is parallel to one of the boundary lines of the feasible region corresponding to a constraint.
• Infeasible Solution: As mentioned earlier, if the constraints are contradictory, there might be no common region, leading to an empty feasible region.
• Unbounded Solution: The feasible region is unbounded, and the value of the objective function can be increased (for maximization) or decreased (for minimization) indefinitely within that region.

7. Types of Linear Programming Problems:

• Manufacturing Problems: Determine the number of units of different products to maximize profit, given constraints on machine hours, labor, raw materials, etc.
• Diet Problems: Determine the minimum cost combination of different foods that satisfies certain minimum nutritional requirements.
• Transportation Problems: Determine the shipping schedule to minimize total transportation cost from various origins to various destinations, given supply and demand constraints.

8. Key Points for Exam Preparation (Especially focusing on Exemplar style):

• Always remember the non-negativity constraints (x ≥ 0, y ≥ 0), which restrict the feasible region to the first quadrant.
• Read the problem statement carefully to correctly identify decision variables, the objective (maximize/minimize), and formulate the constraints accurately. Pay attention to keywords like "at least," "at most," "not more than," "exactly."
• Plot the lines corresponding to constraints carefully. Use intercepts or other points.
• Shade the correct region for each inequality. Use test points wisely.
• Identify the feasible region accurately. Be careful with intersections.
• Find the coordinates of ALL corner points precisely by solving the equations of the intersecting lines.
• Evaluate Z at all corner points.
• Crucially, for unbounded regions, always perform the check (drawing Z > M or Z < m) to confirm if the optimal solution found at a corner point actually exists. Exemplar problems often test this.
• Understand the conditions for multiple optimal solutions, infeasible solutions, and unbounded solutions.

Multiple Choice Questions (MCQs)

Here are 10 MCQs based on the concepts discussed, similar to what you might encounter:

1. The function Z = px + qy, which is to be optimized (maximized or minimized) in an LPP, is called the:
   (a) Constraint Function
   (b) Objective Function
   (c) Feasible Function
   (d) Decision Function

2. The common region determined by all the constraints including non-negative constraints (x ≥ 0, y ≥ 0) of a linear programming problem is called the:
   (a) Optimal Region
   (b) Infeasible Region
   (c) Feasible Region
   (d) Unbounded Region

3. In an LPP, the optimal value of the objective function (if it exists) occurs at:
   (a) Any point inside the feasible region
   (b) Any point on the boundary of the feasible region
   (c) A corner point (vertex) of the feasible region
   (d) The origin

4. Which of the following statements is correct regarding the feasible region of an LPP?
   (a) It must be a bounded region.
   (b) It is always a convex set.
   (c) It must contain the origin.
   (d) It cannot be a single point.

5. Consider an LPP with a maximization objective function Z and an unbounded feasible region. Let M be the maximum value of Z at the corner points. The problem has an optimal solution if:
   (a) The open half-plane determined by Z > M has no point in common with the feasible region.
   (b) The open half-plane determined by Z > M has points in common with the feasible region.
   (c) The feasible region includes the origin.
   (d) Z = M at more than one corner point.

6. If the objective function Z = ax + by of an LPP has the same maximum value at two adjacent corner points of a bounded feasible region, then:
   (a) The LPP has no solution.
   (b) The LPP has a unique optimal solution.
   (c) The LPP has infinitely many optimal solutions.
   (d) The feasible region is unbounded.

7. If the feasible region for an LPP is empty, the solution is:
   (a) Optimal
   (b) Infeasible
   (c) Unbounded
   (d) Degenerate

8. The constraints x ≥ 0, y ≥ 0 in an LPP restrict the feasible region to the:
   (a) First quadrant
   (b) First and Second quadrants
   (c) First and Fourth quadrants
   (d) Second and Third quadrants

9. For the LPP: Maximize Z = 3x + 4y subject to x + y ≤ 4, x ≥ 0, y ≥ 0. The corner points of the feasible region are (0,0), (4,0), and (0,4). The maximum value of Z is:
   (a) 0
   (b) 12
   (c) 16
   (d) 7

10. A point which does not lie in the feasible region of an LPP is called:
    (a) An optimal solution
    (b) A feasible solution
    (c) An infeasible solution
    (d) A corner point

Answer Key:

1. (b)
2. (c)
3. (c)
4. (b) [Note: Convexity is a fundamental property of feasible regions in LPPs]
5. (a)
6. (c)
7. (b)
8. (a)
9. (c) [Z(0,0)=0, Z(4,0)=12, Z(0,4)=16]
10. (c)

Study these notes thoroughly, practice formulating LPPs from word problems, and master the graphical method, especially handling unbounded regions and special cases. Good luck with your preparation!