What is Linear Programming Class 12: Definition & Concepts Explained

Definition and Importance of Linear Programming in Class 12

Linear Programming (LP) is a branch of mathematics that deals with optimizing (maximizing or minimizing) a linear objective function, subject to a set of linear inequalities or equations called constraints. In the Class 12 NCERT syllabus, LP is introduced to help students model and solve practical problems such as resource allocation, production scheduling, and cost minimization.

Key points:

• The objective function is a linear expression like $Z = ax + by$.
• Constraints restrict the values of variables and form a feasible region.
• LP helps in making efficient decisions in industries, economics, and management.

Understanding LP equips students with problem-solving skills useful in competitive exams and real-world applications.

Components of Linear Programming Problems

A Linear Programming problem consists of three main components:

1. Decision Variables: Variables that decide the output, usually denoted as $x$, $y$, etc. 2. Objective Function: A linear function to be maximized or minimized, e.g., $Z = 3x + 5y$. 3. Constraints: Linear inequalities or equations that limit the values of variables, e.g.,

$$ \begin{cases} 2x + y \leq 20 \\ x + 3y \leq 30 \\ x, y \geq 0 \end{cases} $$

These constraints define the feasible region where the solution lies. The goal is to find values of variables satisfying constraints and optimizing the objective function.

Graphical Method to Solve Linear Programming Problems

The graphical method is a visual approach used to solve LP problems with two variables. The steps include:

• Step 1: Plot each constraint as a straight line on the $xy$-plane.
• Step 2: Identify the feasible region that satisfies all constraints.
• Step 3: Determine the coordinates of the vertices (corner points) of the feasible region.
• Step 4: Calculate the value of the objective function at each vertex.
• Step 5: Choose the vertex giving the maximum or minimum value as required.

Example:

Maximize $Z = 3x + 4y$ subject to:

$$ \begin{cases} x + 2y \leq 8 \\ 3x + y \leq 9 \\ x, y \geq 0 \end{cases} $$

Plotting these lines and finding vertices helps identify the optimal solution.

This method is simple and effective for two-variable problems but not suitable for higher dimensions.

Feasible Region and Optimal Solution Explained

The feasible region is the set of all points that satisfy the constraints of an LP problem. It is usually a polygon or polyhedron formed by the intersection of linear inequalities.

Key characteristics:

• It includes all possible solutions.
• It is always a convex set.
• The optimal solution (maximum or minimum) lies at one of the vertices (corner points) of the feasible region.

Why vertices?

Because the objective function is linear, its maximum or minimum over a convex polygon occurs at a vertex.

Example:

If the feasible region is bounded by points $A(0,0)$, $B(3,0)$, $C(2,2)$, and $D(0,4)$, evaluate the objective function at each vertex to find the optimum.

Comparison: Linear Programming vs Other Optimization Techniques

Here is a comparison of Linear Programming with other common optimization methods:

Linear Programming is the foundation for many optimization problems and is easier to solve compared to others.

Worked Example: Maximizing Profit Using Linear Programming

Consider a company producing two products, $A$ and $B$. The profit per unit is ₹40 for $A$ and ₹30 for $B$. The production is limited by:

• Machine 1: $2x + y \leq 100$ hours
• Machine 2: $x + 2y \leq 80$ hours
• $x, y \geq 0$ (units produced)

Formulate and solve the LP problem to maximize profit.

Step 1: Define variables

$x$ = units of product $A$, $y$ = units of product $B$.

Step 2: Objective function

Maximize $Z = 40x + 30y$.

Step 3: Constraints

$$ \begin{cases} 2x + y \leq 100 \\ x + 2y \leq 80 \\ x, y \geq 0 \end{cases} $$

Step 4: Graph constraints and find vertices:

• From $2x + y = 100$, intercepts: $x=50$, $y=100$.
• From $x + 2y = 80$, intercepts: $x=80$, $y=40$.

Vertices are at:

• $A(0,0)$
• $B(0,40)$
• $C(20,30)$ (intersection of two lines)
• $D(50,0)$

Step 5: Calculate $Z$ at each vertex:

• $A: Z=0$
• $B: Z=400 + 3040 = 1200$
• $C: Z=4020 + 3030 = 800 + 900 = 1700$
• $D: Z=4050 + 300 = 2000$

Step 6: Conclusion

Maximum profit ₹2000 occurs at $x=50$, $y=0$.

This example shows how LP helps in making optimal production decisions.