Class 12 Notes - Linear Programming

Download PDF Worksheets
Start a Practice Test

1. Introduction to Linear Programming

Linear Programming (LP) is a mathematical technique used to find the best possible outcome in a given mathematical model whose requirements are represented by linear relationships. It is widely used in business, economics, engineering, and military applications for optimizing resources.

2. Key Terms

  • Objective Function: The function to be maximized or minimized (e.g., profit, cost).
  • Constraints: The restrictions or limitations on the variables, expressed as linear inequalities or equations.
  • Feasible Region: The set of all possible points that satisfy all constraints.
  • Optimal Solution: The point in the feasible region that gives the best value (maximum or minimum) for the objective function.
  • Variables: The unknowns to be determined (usually denoted as x, y, etc.).

3. Steps in Solving Linear Programming Problems

  1. Identify the decision variables.
  2. Formulate the objective function.
  3. Write down the constraints.
  4. Graph the constraints to find the feasible region (for two variables).
  5. Find the corner points (vertices) of the feasible region.
  6. Evaluate the objective function at each corner point.
  7. Select the point that gives the optimal value.

4. Graphical Method (for Two Variables)

  • Plot each constraint as a straight line on the graph.
  • Shade the region that satisfies all constraints (feasible region).
  • Locate the corner points of the feasible region.
  • Substitute the coordinates of each corner point into the objective function to find which gives the maximum or minimum value.

5. Example Problem

Problem: Maximize Z = 3x + 2y, subject to:

  • x + y ≤ 4
  • x ≥ 0
  • y ≥ 0

Solution:

  1. Plot the constraints on the XY-plane.
  2. The feasible region is the triangle formed by (0,0), (4,0), and (0,4).
  3. Evaluate Z at each vertex:
    • At (0,0): Z = 0
    • At (4,0): Z = 12
    • At (0,4): Z = 8
  4. Maximum value of Z is 12 at (4,0).

6. Applications of Linear Programming

  • Resource allocation (e.g., maximizing profit, minimizing cost)
  • Diet problems (finding the cheapest diet that satisfies all nutritional requirements)
  • Transportation and assignment problems
  • Production scheduling
  • Blending problems in industries

7. Practice Questions

  1. Minimize Z = 5x + 4y, subject to: x + 2y ≥ 8, 3x + y ≥ 9, x ≥ 0, y ≥ 0.
  2. Maximize Z = 2x + 3y, subject to: x + y ≤ 10, x ≥ 2, y ≥ 3, x ≥ 0, y ≥ 0.
  3. Explain the significance of the feasible region in a linear programming problem.
  4. What is the difference between a constraint and an objective function?

8. Summary

  • Linear Programming helps in optimizing (maximizing or minimizing) a linear objective function subject to linear constraints.
  • The solution is found at a vertex (corner point) of the feasible region.
  • It has wide applications in various fields for efficient resource management.