Linear Programming Class 12 NCERT Solutions & Concepts

Understanding Mathematical Formulation in LPP

Linear Programming (LPP) is a mathematical optimization technique used to find the best outcome (such as maximum profit or minimum cost) in a given mathematical model whose requirements are represented by linear relationships.

The core components of any LPP are:

1. Decision Variables ($x, y$): These are the quantities to be determined. For example, the number of units of product A and B to manufacture.
2. Objective Function ($Z = ax + by$): This is the linear function of decision variables that needs to be maximized or minimized.
3. Constraints: These are linear inequalities or equations representing limitations on resources (e.g., $3x + 2y \le 18$, $x \ge 0, y \ge 0$).
4. Non-negativity Restrictions ($x \ge 0, y \ge 0$): These ensure that we cannot produce a negative quantity of physical items, which restricts our feasible region to the first quadrant.

Key Terminology in Linear Programming

Feasible Region

The common region determined by all the given constraints including non-negative constraints of a linear programming problem. Every point in this region represents a feasible solution.

Infeasible Region

The region outside the feasible region where one or more constraints are violated.

Optimal Solution

Any point in the feasible region that gives the optimal value (maximum or minimum) of the objective function.

Bounded Feasible Region

A feasible region that can be enclosed within a circle. It always guarantees both a maximum and minimum value for the objective function.

Step-by-Step Corner Point Method to Solve LPP

1. Formulate the Inequalities — Write down the objective function Z and all the system of linear inequalities (constraints) based on the given problem statement.
2. Plot the Constraints on a Graph — Treat each inequality as an equation (line) and plot it on a Cartesian plane. Find the intercepts of each line to draw them accurately.
3. Identify the Feasible Region — Determine the region that satisfies all inequalities simultaneously. Use a test point like (0,0) to verify which side of the line to shade. Shade the common region.
4. Find the Corner Points (Vertices) — Identify all the corner points of the shaded feasible region. Find their coordinates by solving the corresponding system of equations where the boundary lines intersect.
5. Evaluate the Objective Function — Substitute the coordinates of each corner point into the objective function Z = ax + by. Compare these values to determine the maximum or minimum value.

Fully Solved Examples

• Example 1: Maximize $Z = 4x + y$ subject to constraints: $x + y \le 50$, $3x + y \le 90$, $x \ge 0, y \ge 0$. Step 1: Plot the boundary lines. - For line $x + y = 50$, intercepts are $(50, 0)$ and $(0, 50)$. - For line $3x + y = 90$, intercepts are $(30, 0)$ and $(0, 90)$. Step 2: Find the feasible region. Testing $(0,0)$: $0+0 \le 50$ (True) and $0+0 \le 90$ (True). The shaded region is in the first quadrant, bounded by the axes and these two lines. Step 3: Find corner points. The vertices of the feasible region are: - $O(0,0)$ - $A(30,0)$ (intersection of $3x + y = 90$ with x-axis) - $B(20,30)$ (solving $x + y = 50$ and $3x + y = 90$ simultaneously) - $C(0,50)$ (intersection of $x + y = 50$ with y-axis) Step 4: Evaluate $Z = 4x + y$ at each corner point: - At $O(0,0)$: $Z = 4(0) + 0 = 0$ - At $A(30,0)$: $Z = 4(30) + 0 = 120$ - At $B(20,30)$: $Z = 4(20) + 30 = 110$ - At $C(0,50)$: $Z = 4(0) + 50 = 50$ Conclusion: The maximum value of $Z$ is $120$, which occurs at the point $(30,0)$.

Crucial Alert: Unbounded Feasible Regions

If the feasible region is unbounded (extends infinitely), the maximum or minimum value found at the corner point may or may not exist! To verify:

1. For a minimization problem with corner point minimum value $m$, construct the inequality $ax + by < m$. Plot this open half-plane. If it has no common points with the feasible region, then $m$ is the minimum value. Otherwise, no minimum exists.
2. For a maximization problem with corner point maximum value $M$, construct the inequality $ax + by > M$. If this open half-plane has no common points with the feasible region, then $M$ is the maximum value. Otherwise, no maximum exists.

Practice Questions with Solutions

• Q: Minimize $Z = 3x + 5y$ subject to $x + 3y \ge 3$, $x + y \ge 2$, $x, y \ge 0$. A: Step 1: Write down equations for boundary lines: Line 1: $x + 3y = 3$. Intercepts are $(3,0)$ and $(0,1)$. Line 2: $x + y = 2$. Intercepts are $(2,0)$ and $(0,2)$. Step 2: Determine the feasible region. Testing $(0,0)$ gives $0 \ge 3$ (False) and $0 \ge 2$ (False). The region is unbounded, extending away from the origin in the first quadrant. Step 3: Solve for intersection of the two lines: $x + 3y = 3$ and $x + y = 2$. Subtracting: $2y = 1 \implies y = 0.5$, which gives $x = 1.5$. Intersection point is $(1.5, 0.5)$. Step 4: Identify corner points of the feasible region: $A(3,0)$, $B(1.5, 0.5)$, $C(0,2)$. Step 5: Evaluate $Z = 3x + 5y$ at these points: - At $A(3,0)$: $Z = 3(3) + 5(0) = 9$ - At $B(1.5, 0.5)$: $Z = 3(1.5) + 5(0.5) = 4.5 + 2.5 = 7$ - At $C(0,2)$: $Z = 3(0) + 5(2) = 10$ Since the region is unbounded, we must check if $3x + 5y < 7$ has any common points with the feasible region. Plotting $3x + 5y < 7$, we see the open half-plane does not overlap with the feasible region. Final answer: The minimum value of $Z$ is $7$ at the point $(1.5, 0.5)$.
• Q: Maximize $Z = 3x + 2y$ subject to $x + 2y \le 10$, $3x + y \le 15$, $x, y \ge 0$. A: Step 1: Find intercepts of boundary lines: - $x + 2y = 10 \implies (10,0), (0,5)$ - $3x + y = 15 \implies (5,0), (0,15)$ Step 2: Find the corner points of the bounded feasible region: - $O(0,0)$ - $A(5,0)$ - $B(4,3)$ (by solving $x + 2y = 10$ and $3x + y = 15$ simultaneously) - $C(0,5)$ Step 3: Evaluate $Z = 3x + 2y$: - $Z(0,0) = 0$ - $Z(5,0) = 15$ - $Z(4,3) = 3(4) + 2(3) = 18$ - $Z(0,5) = 10$ Final answer: The maximum value of $Z$ is $18$ at $(4,3)$.
• Q: Solve the LPP graphically to maximize $Z = x + y$ subject to constraints $x - y \le -1$, $-x + y \le 0$, $x, y \ge 0$. A: Step 1: Plot the constraints: - Line 1: $x - y = -1$ passing through $(0,1)$ and $(-1,0)$. The inequality $x - y \le -1$ represents the region above/left of this line. - Line 2: $-x + y = 0 \implies y = x$, passing through origin. The inequality $-x + y \le 0 \implies y \le x$ represents the region below/right of this line. Step 2: Find common region. Note that the region for $x - y \le -1 \implies y \ge x + 1$ and the region for $y \le x$ do not overlap anywhere in the first quadrant. Step 3: Since there is no common point satisfying all constraints simultaneously, the feasible region is empty. Final answer: There is no feasible solution for this linear programming problem.
• Q: Show that the maximum of $Z = 5x + 10y$ occurs at more than one point for constraints $x + 2y \le 120$, $x + y \ge 60$, $x - 2y \ge 0$, and $x, y \ge 0$. A: Step 1: Find the vertices of the bounded feasible region by plotting the lines: - $x + 2y = 120$ - $x + y = 60$ - $x - 2y = 0$ Solving pairs of equations gives corner points of the bounded region: - $A(60,30)$ (intersection of $x + 2y = 120$ and $x - 2y = 0$) - $B(120,0)$ (on the x-axis) - $C(60,0)$ - $D(40,20)$ (intersection of $x+y=60$ and $x-2y=0$) Step 2: Evaluate $Z = 5x + 10y = 5(x + 2y)$: - At $A(60,30)$: $Z = 5(60 + 60) = 600$ - At $B(120,0)$: $Z = 5(120 + 0) = 600$ - At $C(60,0)$: $Z = 300$ - At $D(40,20)$: $Z = 400$ Step 3: Analyze the results. The maximum value of $600$ is achieved at two corner points: $A(60,30)$ and $B(120,0)$. Since both are vertices of the same boundary line $x + 2y = 120$, the objective function is parallel to this line segment. Final answer: The maximum value of $Z$ is $600$, occurring at every point along the line segment joining $(60,30)$ and $(120,0)$.

Frequently Asked Questions