Chapter 12: Linear Programming

Summary

• Linear programming involves optimizing a linear function subject to constraints.
• Example problem: A furniture dealer wants to maximize profit from tables and chairs.
• Constraints include budget and storage limitations.
• The graphical method is used to find feasible solutions.
• The feasible region is defined by linear inequalities.
• Optimal solutions occur at corner points of the feasible region.

Key Formulas/Definitions

• Objective Function: Z = ax + by (where a, b are constants)
• Constraints: Linear inequalities that restrict the values of x and y.
• Feasible Region: The area defined by the constraints where solutions exist.
• Optimal Solution: A point in the feasible region that maximizes or minimizes the objective function.

Learning Objectives

• Define linear programming and its applications.
• Formulate a linear programming problem mathematically.
• Graphically solve linear programming problems.
• Identify feasible and infeasible solutions.
• Evaluate objective functions at corner points.

Common Mistakes/Exam Tips

• Ensure all constraints are correctly represented as inequalities.
• Remember that optimal solutions occur at corner points, not within the interior of the feasible region.
• Check for non-negativity constraints on variables.

Important Diagrams

• Graph of Feasible Region: Shows the area where all constraints are satisfied.
  • Axes labeled X and Y.
  • Lines representing constraints intersecting at corner points.
  • Shaded area indicating the feasible region.
• Table of Corner Points and Values: Lists corner points with corresponding values of the objective function Z.
  • Example:

    Corner Point	Corresponding value of Z
    (0, 0)	0
    (30, 0)	120
    (20, 30)	110
    (0, 50)	50

Chapter 12: Linear Programming

12.1 Introduction

• Linear programming involves optimizing a linear objective function subject to constraints.
• Example: A furniture dealer wants to maximize profit from tables and chairs.
  • Investment: Rs 50,000
  • Storage: Maximum of 60 pieces
  • Costs: Table = Rs 2500, Chair = Rs 500
  • Profits: Table = Rs 250, Chair = Rs 75

12.2 Linear Programming Problem and its Mathematical Formulation

12.2.1 Mathematical Formulation

• Let:
  • x = number of tables
  • y = number of chairs
• Constraints:
  1. Investment: 2500x + 500y ≤ 50000 (or 5x + y ≤ 100)
  2. Storage: x + y ≤ 60
  3. Non-negativity: x ≥ 0, y ≥ 0
• Objective function: Z = 250x + 75y (maximize)

12.2.2 Graphical Method of Solving Linear Programming Problems

• Graph the constraints:
  1. 5x + y ≤ 100
  2. x + y ≤ 60
  3. x ≥ 0
  4. y ≥ 0
• Feasible Region: The area that satisfies all constraints.
• Feasible Solutions: Points within or on the boundary of the feasible region.
• Infeasible Solutions: Points outside the feasible region.

Important Theorems

1. Theorem 1: Optimal values occur at corner points of the feasible region.
2. Theorem 2: If the feasible region is bounded, both maximum and minimum values exist at corner points.

Example of Corner Points and Values

Conclusion

• Linear programming is crucial for optimizing resources in various fields such as industry and management.

Common Mistakes and Exam Tips in Linear Programming

Common Pitfalls

• Misunderstanding Constraints: Students often misinterpret the constraints of the problem, leading to incorrect feasible regions.
• Ignoring Non-negativity: Failing to apply the non-negativity constraints (x ≥ 0, y ≥ 0) can result in infeasible solutions.
• Incorrect Graphing: Errors in plotting the inequalities can lead to an incorrect feasible region.
• Not Evaluating All Corner Points: Students may overlook evaluating all corner points of the feasible region, which can lead to missing the optimal solution.
• Assuming Unbounded Regions: Some students may incorrectly assume that an unbounded feasible region means there is no maximum or minimum value.

Tips for Success

• Double-Check Constraints: Always verify that you have correctly identified and graphed all constraints.
• Use the Corner Point Method: Familiarize yourself with the Corner Point Method to systematically find the optimal solution.
• Evaluate All Vertices: Make sure to evaluate the objective function at all corner points of the feasible region to ensure you find the maximum or minimum value.
• Practice Graphing: Regularly practice graphing systems of inequalities to improve accuracy and speed.
• Understand the Problem Context: Read the problem carefully to understand what is being asked, especially in real-life applications.