CBSE Mathematics Linear Programming

Linear programming (LP) is a powerful mathematical tool that transforms real-world problems of limited resources and competing demands into solvable equations. For CBSE students, mastering this topic is not just about passing an exam; it's about learning a systematic approach to optimal decision-making, applicable to business, logistics, and economics. The CBSE curriculum focuses on the graphical method, turning word problems into mathematical models and finding the best possible outcome within a defined set of constraints.

What is Linear Programming?

Linear programming is a technique for optimizing (maximizing or minimizing) a linear objective function, subject to a set of linear inequalities or equations called constraints. The key idea is that all relationships are linear, meaning they graph as straight lines or half-planes. The objective function represents what you want to achieve, such as maximizing profit or minimizing cost. The constraints represent the limitations you must work within, like available raw materials, labor hours, or budget. The solution to an LP problem lies within the feasible region, the common area defined by all constraints.

Mathematical Formulation: Translating Words into Equations

This is the most critical step and is where many students face challenges. Formulation involves converting a descriptive problem into a precise mathematical model. The process has three key components:

1. Identify Decision Variables: These are the quantities you can control. They are usually denoted by $x$ and $y$ (e.g., number of product A and product B to manufacture).
2. Formulate the Objective Function: This is a linear expression in terms of the decision variables that needs to be optimized. For example, if profit per unit of A is ₹5 and per unit of B is ₹7, the objective function to maximize is $Z=5x+7y$.
3. List the Constraints: Translate each limitation stated in the problem into a linear inequality. Common constraints involve resources like $2x+3y\le 120$ (machine hours) or $x+y\ge 10$ (minimum production demand). Always include the non-negativity constraints $x\ge 0,y\ge 0$, as you cannot produce a negative quantity of items.

Example: A farmer has 240 acres of land and wants to plant wheat and barley. Planting wheat costs ₹50/acre and barley ₹30/acre. He has only ₹12,000. Wheat gives a profit of ₹120/acre and barley ₹80/acre. How should he plant to maximize profit?

• Variables: Let $x$ = acres of wheat, $y$ = acres of barley.
• Objective: Maximize $Z=120x+80y$ (profit).
• Constraints:

1. Land: $x+y\le 240$
2. Cost: $50x+30y\le 12000$
3. Non-negativity: $x\ge 0,y\ge 0$

Graphing the Constraints and Identifying the Feasible Region

Once formulated, you solve the problem graphically for two variables.

1. Treat each inequality as an equation and plot the corresponding straight line on the $xy$-plane (e.g., plot $x+y=240$).
2. Determine which side of the line satisfies the inequality. A simple test point, usually the origin $(0,0)$, helps. If the origin satisfies the inequality, shade the region containing the origin; otherwise, shade the opposite side.
3. Repeat this for every constraint. The area where all shaded regions overlap is the feasible region. It contains every possible combination of $x$ and $y$ that satisfies all conditions. This region is always a convex polygon (or an unbounded area in some cases).

In our farmer example, after plotting, the feasible region would be a quadrilateral bounded by the axes and the two constraint lines.

The Corner Point Method for Optimization

A fundamental theorem of linear programming states that if an optimal solution exists, it must occur at a corner point (vertex) of the feasible region. The corner point method leverages this theorem:

1. Find the coordinates of all corner points of the feasible polygon. This often involves solving the simultaneous equations of the intersecting lines that form each vertex.
2. Substitute the coordinates of each corner point into the objective function $Z$.
3. Identify which point gives the maximum value (for maximization problems) or the minimum value (for minimization problems).

For the farmer's problem, the vertices might be $(0,0)$, $(0,240)$, $(?,?)$, and $(?,?)$ where the two constraint lines intersect. You would calculate $Z$ at each point to find which acreage mix yields the highest profit.

Handling Different Types of Feasible Regions

Not all feasible regions are closed polygons. Sometimes, they can be unbounded, meaning the area extends infinitely in one direction. In such cases:

• For a maximization problem, an unbounded region does not guarantee a maximum unless the objective function's slope keeps the optimal value finite at a corner.
• For a minimization problem, an unbounded region can still have a minimum at a corner point.

The CBSE syllabus typically focuses on problems yielding a closed, bounded feasible region to ensure a definitive optimal solution.

Common Pitfalls

1. Incorrect Formulation: Misidentifying decision variables or misreading "at least" ($\ge$) versus "at most" ($\le$) is the most common error. Correction: Read the problem slowly, underline key phrases, and write the inequality symbol before translating the sentence.
2. Faulty Graphing and Shading: Accidentally shading the wrong side of a line or miscalculating intercepts leads to an incorrect feasible region. Correction: Always use a test point (like the origin) to check your shading. Plot lines carefully by finding both $x$ and $y$-intercepts.
3. Missing Non-Negativity Constraints: Forgetting that $x\ge 0$ and $y\ge 0$ are implicit in most real-world scenarios. Correction: Make it a habit to always write these constraints first when listing them.
4. Arithmetic Errors in Corner Points: Solving simultaneous equations incorrectly will lead to wrong vertex coordinates and thus an incorrect optimal value. Correction: Solve the system of equations step-by-step, preferably using substitution or elimination, and verify your coordinates by plugging them back into the original constraint equations.

Summary

• Linear programming is a method to find the best outcome (maximize/minimize) under given linear constraints.
• Success hinges on accurate mathematical formulation: defining variables, writing the objective function, and listing all constraints including non-negativity.
• The solution lies within the feasible region, the graphically-determined area satisfying all inequalities.
• The corner point method is used to find the optimal solution by evaluating the objective function at every vertex of the feasible region.
• For CBSE exams, practice translating word problems into mathematical models and meticulously executing the graphical solution step-by-step to avoid common plotting and calculation errors.