Linear Programming — Class 12 Maths Notes

Topics covered in Linear Programming

1. 1.Introduction of Linear Programming

   Linear programming is a fascinating area of mathematics that you've already begun to explore through your studies of linear equations and inequalities. Now, let's delve into how these concepts can help solve real-world problems, especially in optimizing resources to achieve the best possible outcomes, such as maximizing profits or minimizing costs.

   Everyday Example of Linear Programming

   Imagine you are planning a school event and you need to decide on the number and type of snacks to serve. You have a limited budget and space, just like the furniture dealer in your textbook who has a limited amount of money and storage space for tables and chairs. By using linear programming, you can figure out the most cost-effective combination of snacks to maximize satisfaction within your budget, ensuring you get the best value for money.

   The Furniture Dealer's Challenge

   Let's look at the furniture dealer's situation from your book:

   • The dealer has Rs 50,000 to invest.
   • Storage space is limited to 60 items.
   • A table costs Rs 2,500 and a chair Rs 500.
   • Selling a table nets a profit of Rs 250, while selling a chair gives a profit of Rs 75.

   The dealer's goal is to determine the number of tables and chairs to buy that maximizes his profit, while staying within his budget and space limitations.

   How Linear Programming Works in This Scenario

   1. Define Variables:

      • Let T represent the number of tables.
      • Let C represent the number of chairs.

   2. Set Up the Constraints:

      • Cost constraint: 2500+500≤500002500T+500C≤50000
      • Space constraint: +≤60T+C≤60

   3. Objective Function:

      • Maximize profit: 250+75250T+75C

   4. Graphical Method:

      • Plot the constraints on a graph.
      • Identify the feasible region where all constraints are satisfied.
      • Evaluate the objective function at each vertex (corner point) of the feasible region to find the maximum profit.

   Real-World Applications

   Linear programming is widely used in various fields:

   • Business: Optimizing resource allocation, like the furniture dealer maximizing his profits.
   • Economics: Determining production levels to maximize output or minimize costs.
   • Healthcare: Allocating limited medical resources most effectively to treat the maximum number of patients.
   • Transportation: Planning routes and schedules to minimize travel time and costs.

   Hands-On Activity

   Try setting up a similar problem yourself! Suppose you're organizing a class picnic with a budget of Rs 10,000, and you need to decide on the number of sandwiches (Rs 200 each) and drinks (Rs 100 each) to maximize the happiness of your classmates, measured by a "happiness score" of 10 points per sandwich and 5 points per drink. Define your variables, set up the constraints, and identify the objective function. Then, see if you can graph the problem and find the solution.

   In Summary

   Linear programming helps us make the best possible decisions within given constraints. It's a powerful tool that finds practical applications in many areas of life and work, preparing you for complex decision-making situations you might encounter in any career, particularly in engineering, management, logistics, and economics.

2. 2.Linear Programming Problem and Its Mathematical Formulation

   Linear Programming (LP) is a method to achieve the best outcome in a mathematical model whose requirements are represented by linear relationships. It's particularly useful for economic and business contexts where you need to maximize profit or minimize costs with certain constraints. Let's explore how a linear programming problem is formulated mathematically, using a practical example to make it more relatable.

   Example: Maximizing Profit in a Bakery

   Imagine you're running a small bakery that makes cookies and cakes. You want to maximize your profit, but you're limited by the ingredients available and the time it takes to bake each item.

   Steps to Formulate the Linear Programming Problem:

   1. Define the Decision Variables:

      • Let x be the number of cookies you make.
      • Let y be the number of cakes you make.

   2. Construct the Objective Function:

      • Suppose each cookie brings a profit of Rs 10 and each cake brings a profit of Rs 20.
      • Objective Function (Profit to maximize): =10+20P=10x+20y

   3. Set up the Constraints:

      • Ingredient constraints (e.g., flour, sugar):
        • Suppose you have 30 kg of flour, and a cookie requires 0.1 kg, a cake 0.3 kg: 0.1+0.3≤300.1x+0.3y≤30
        • Suppose you have 10 kg of sugar, and a cookie requires 0.05 kg, a cake 0.15 kg: 0.05+0.15≤100.05x+0.15y≤10
      • Time constraints (oven time):
        • Suppose you have 50 hours of oven time available, and each cookie needs 0.2 hours, each cake 0.5 hours: 0.2+0.5≤500.2x+0.5y≤50
      • Non-negativity constraints:
        • ≥0x≥0
        • ≥0y≥0

   Graphical Solution Method:

   1. Plot each constraint on a graph with x and y as axes.
   2. The area that satisfies all constraints is called the feasible region.
   3. The vertices of this region are potential solutions.
   4. Evaluate the objective function at each vertex to find the optimal solution.

   Real-World Application:

   This method is widely applicable:

   • Manufacturing: Determining quantities of products to maximize profitability.
   • Agriculture: Allocating resources like seeds, water, and fertilizers to maximize yield.
   • Transportation: Planning routes and schedules to minimize fuel consumption or time.
   • Healthcare: Allocating staff and resources to maximize patient care efficiency.

   Activity to Try:

   Create your own linear programming model for a business idea you might have, like starting a t-shirt printing business where you need to decide how many of each size and design to print given a set budget and fabric constraints. Define your variables, write out your objective function, list your constraints, and try to sketch the feasible region.

   Linear programming is a powerful tool for decision-making and optimizing resource utilization, making it invaluable in many fields, including business, economics, engineering, and logistics.

3. 3.Mathematical formulation of the problem

   The mathematical formulation of a linear programming problem involves constructing a model based on decision variables, an objective function, and a set of constraints. Let's use the bakery example to clearly detail each component:

   1. Define the Decision Variables

   Decision variables are the variables that decision makers will decide upon. These variables represent the quantities that will maximize or minimize the objective function, subject to the constraints.

   For the bakery:

   • x: Number of cookies produced.
   • y: Number of cakes produced.

   These variables should be non-negative, as you cannot produce a negative quantity of cookies or cakes.

   2. Construct the Objective Function

   The objective function is the main function to be optimized (maximized or minimized). It should be a linear combination of the decision variables.

   For the bakery aiming to maximize profit:

   • Profit from a cookie = Rs 10
   • Profit from a cake = Rs 20
   • Objective Function: =10+20P=10x+20y

   3. Set Up the Constraints

   Constraints are limitations or requirements that the solution must satisfy. These can include resource limitations, regulatory limits, or other restrictions. They should also be linear in terms of the decision variables.

   For the bakery:

   • Flour constraint: 0.1+0.3≤300.1x+0.3y≤30 kg
   • Sugar constraint: 0.05+0.15≤100.05x+0.15y≤10 kg
   • Oven time constraint: 0.2+0.5≤500.2x+0.5y≤50 hours
   • Non-negativity constraints: ≥0,≥0x≥0,y≥0

   4. Graphical Solution Approach

   Although not part of the mathematical formulation per se, the graphical approach to solving the LP problem involves plotting these constraints on a graph with axes for x and y, identifying the feasible region (the area that meets all constraints), and finding the vertex (corner point) of this region that maximizes or minimizes the objective function.

   Practical Example - Solving the Bakery Problem Graphically

   1. Plot each constraint:

      • Draw the line for each constraint equation.
      • Determine which side of each line corresponds to the feasible region by substituting in test points.

   2. Identify the feasible region:

      • This region will be bounded by the lines drawn and will satisfy all inequality constraints.

   3. Find the vertices of the feasible region:

      • Where two constraint lines intersect.

   4. Evaluate the objective function at each vertex:

      • Calculate =10+20P=10x+20y for each vertex.
      • Choose the vertex that provides the maximum P, given the bakery wants to maximize profits.

   This structured approach is typical for formulating linear programming problems in various contexts, from production and logistics to finance and resource management. Each application follows the same basic steps but adapts the variables, objective function, and constraints to fit the specific situation.

4. 4.Graphical Method for Solving Linear Programming Problems

   The graphical method for solving linear programming problems, complete with a theorem and an example illustrated with graphs. This will give you a clear view and you can use the content directly for documentation or educational purposes.

   Graphical Method for Solving Linear Programming Problems

   The graphical method is a practical technique used to solve linear programming problems that involve two variables. It allows for the visualization of constraints and the objective function to find the optimal solution.

   Steps Involved:

   1. Identify the Decision Variables: Define the two variables that will be manipulated to find the optimal solution.
   2. Formulate the Objective Function: This is the function you want to maximize or minimize. Typically, it relates to cost or profit.
   3. Establish the Constraints: These are usually resource limits or requirements, formulated as linear inequalities.
   4. Plot the Constraints: Each constraint is plotted on a graph. The area that satisfies all constraints is known as the feasible region.
   5. Identify the Feasible Region: This region is bounded by the constraint lines and is where all constraints overlap.
   6. Find the Optimal Solution: Calculate the objective function at each vertex (corner point) of the feasible region. The vertex that provides the best value (highest or lowest depending on the objective) is the optimal solution.

   Fundamental Theorem of Linear Programming

   Theorem: If a linear programming problem has a feasible solution, the optimal solution will occur at a vertex, or corner point, of the feasible region. If the optimal solution is not unique, then every point on the line segment connecting these vertices represents optimal solutions.

   Example Problem: Maximizing Production Efficiency

   A factory produces two types of gadgets: Type A and Type B. The goal is to maximize the total production value.

   Variables

   • x: Number of Type A gadgets produced.
   • y: Number of Type B gadgets produced.

   Objective Function

   • Maximize profit: =40+30P=40x+30y

   Constraints

   • Machine time constraint: 2+≤1002x+y≤100 (Total available machine hours)
   • Material constraint: +2≤90x+2y≤90 (Total material units available)
   • Demand constraint: ≤40y≤40 (Market demand for Type B)
   • Non-negativity constraints: ≥0,≥0x≥0,y≥0

   Graphical Representation

   1. Plot Each Constraint:

      • Machine time: =100−2y=100−2x
      • Material: =45−0.5y=45−0.5x
      • Demand: =40y=40
      • Non-negativity: x and y must be in the first quadrant.

   2. Determine the Feasible Region:

      • This region will be where all constraints overlap on the graph.

   3. Calculate Objective Function at Each Vertex:

      • The vertices of the feasible region are likely where the constraint lines intersect and where they intersect the axes.
      • Evaluate =40+30P=40x+30y at each vertex to find the maximum profit.

   Practical Use and Graph Generation

   This method is particularly useful in business and engineering for optimizing production, resource allocation, and financial planning. To visually represent this example, you would create a graph based on the provided equations, marking the feasible region and calculating the objective function at each of its vertices.

   The graphical approach provides a clear, visual understanding of how different constraints and objectives interact in a two-variable scenario, making it an ideal educational tool for foundational studies in operations research and decision sciences.