Linear Programming Class 12 Chapter Notes

Key Concepts: Must Remember

• A Linear Programming Problem (LPP) involves optimizing (maximizing or minimizing) a linear objective function subject to a set of linear constraints.
• The objective function is always linear and represents the quantity to be optimized (e.g., profit, cost).
• Constraints are linear inequalities or equalities that restrict the values of decision variables, often representing resource limitations.
• Non-negativity restrictions (x ≥ 0, y ≥ 0) are fundamental as decision variables usually represent physical quantities that cannot be negative.
• The feasible region is the common region determined by all constraints, including non-negativity restrictions. It must be a convex polygon.
• Any point within or on the boundary of the feasible region is a feasible solution.
• An optimal solution (maximum or minimum value) of the objective function, if it exists, always occurs at a corner point (vertex) of the feasible region.
• The graphical method is applicable for LPPs with only two decision variables.
• If the feasible region is unbounded, the objective function may or may not have an optimal solution. Check if the value improves in the unbounded direction.

Key Terms and Definitions

Objective Function

A linear function, Z = ax + by, which is to be optimized (maximized or minimized) in an LPP.

Constraints

A system of linear inequalities or equations (and non-negativity conditions) that limit the resources or conditions available, defining the boundaries of the feasible region.

Decision Variables

The variables (e.g., x, y) whose values are to be determined to optimize the objective function. They are typically non-negative.

Feasible Region

The set of all points that satisfy all the constraints of an LPP simultaneously. It is always a convex polygon. If no such region exists, the LPP has no feasible solution.

Feasible Solution

Any point (x, y) that lies within or on the boundary of the feasible region, satisfying all constraints.

Optimal Solution

A feasible solution that yields the maximum or minimum value of the objective function.

Corner Point (Vertex)

A vertex of the feasible region. According to the Corner Point Method, the optimal solution for an LPP always lies at one of these points.

Unbounded Feasible Region

A feasible region that extends indefinitely in one or more directions. In such cases, an optimal solution might not exist, or it might be unique.

Formulation of a Linear Programming Problem (LPP)

Formulating a Linear Programming Problem (LPP) from a real-world scenario is a critical first step. An LPP consists of three main components: decision variables, an objective function, and a set of constraints. Understanding how to identify and define these components correctly is essential for solving LPPs. First, identify the decision variables, which are the quantities you need to determine to solve the problem. These are usually represented by variables like 'x' and 'y', representing, for example, the number of units of different products to produce or the amount of different resources to allocate. These variables must typically be non-negative, reflecting real-world quantities.

Next, define the objective function. This is a linear expression that represents the quantity you wish to maximize (like profit or revenue) or minimize (like cost or time). It's always in the form Z = ax + by, where 'a' and 'b' are constants related to the per-unit contribution of each decision variable to the objective. For instance, if 'x' units of product A yield a profit of ₹10 per unit and 'y' units of product B yield a profit of ₹15 per unit, the objective function to maximize profit would be Z = 10x + 15y.

Finally, establish the constraints. These are linear inequalities or equalities that describe the limitations or restrictions on the decision variables. Constraints arise from limited resources such as raw materials, labor hours, machine capacity, or financial budgets. For example, if product A requires 2 hours of labor and product B requires 3 hours, and total available labor is 60 hours, a constraint would be 2x + 3y ≤ 60. Always remember to include the non-negativity constraints, x ≥ 0 and y ≥ 0, as physical quantities cannot be negative. The feasible region formed by these constraints is crucial; it represents all possible combinations of decision variables that satisfy the problem's conditions. Properly formulating these three parts sets the stage for finding the optimal solution using graphical or other methods.

Graphical Method for Solving an LPP (Two Variables)

1. Step 1: Formulate the LPP — Clearly define the objective function (Z = ax + by) and all constraints (linear inequalities), including non-negativity constraints (x ≥ 0, y ≥ 0).
2. Step 2: Convert Inequalities to Equations — Replace each inequality constraint with an equality to find the corresponding straight lines (e.g., 2x + 3y ≤ 60 becomes 2x + 3y = 60).
3. Step 3: Plot the Lines — Draw the graph of each linear equation. For each line, find two points (e.g., intercepts by setting x=0 and y=0) and connect them.
4. Step 4: Identify the Feasible Region — Determine the region satisfying each inequality. For '≤' inequalities, the region is typically towards the origin (0,0); for '≥' inequalities, it's away from the origin. The common region satisfying all constraints, including x ≥ 0 and y ≥ 0 (first quadrant), is the feasible region. This region should be a convex polygon.
5. Step 5: Determine Corner Points — Find the coordinates of all the vertices (corner points) of the feasible region. These points are typically intersections of the boundary lines.
6. Step 6: Evaluate Objective Function at Corner Points — Substitute the coordinates of each corner point into the objective function Z = ax + by to calculate the value of Z at each vertex.
7. Step 7: Determine Optimal Solution — For maximization problems, the corner point yielding the largest Z value is the optimal solution. For minimization problems, the corner point yielding the smallest Z value is the optimal solution. If the feasible region is unbounded, an optimal solution may not exist. In such cases, further analysis (drawing a Z-line) is required to confirm.

Worked Examples

• Example 1: Maximization Problem Maximize Z = 3x + 2y subject to the constraints: x + y ≤ 4, x ≥ 0, y ≥ 0. 1. Feasible Region: Plot x + y = 4. The region satisfying x + y ≤ 4, x ≥ 0, y ≥ 0 is the triangle with vertices at (0,0), (4,0), and (0,4). 2. Corner Points: (0,0), (4,0), (0,4). 3. Evaluate Z: Z(0,0) = 3(0) + 2(0) = 0 Z(4,0) = 3(4) + 2(0) = 12 * Z(0,4) = 3(0) + 2(4) = 8 4. Optimal Solution: Maximum Z = 12 at (4,0).
• Example 2: Minimization Problem Minimize Z = 5x + 7y subject to: x + y ≥ 2, x ≥ 0, y ≥ 0. 1. Feasible Region: Plot x + y = 2. The region satisfying x + y ≥ 2, x ≥ 0, y ≥ 0 is an unbounded region in the first quadrant, above the line x + y = 2. Its corner points are (2,0) and (0,2). 2. Corner Points: (2,0), (0,2). 3. Evaluate Z: Z(2,0) = 5(2) + 7(0) = 10 Z(0,2) = 5(0) + 7(2) = 14 4. Optimal Solution: Minimum Z = 10 at (2,0). Since the region is unbounded, we verify by drawing a line 5x + 7y = 10. No part of the feasible region lies below this line, confirming (2,0) as the minimum.

Common Exam Traps & Tips

Careful with Inequality Signs!

One of the most common mistakes is incorrectly identifying the feasible region due to wrong interpretation of inequality signs. Remember:

• ax + by ≤ c means the region towards the origin (if c > 0).
• ax + by ≥ c means the region away from the origin (if c > 0).

Always test a point (like (0,0) if it doesn't lie on the boundary line) to confirm which side of the line represents the inequality.

Identify ALL Corner Points

Forgetting an intersection point as a corner point can lead to an incorrect optimal solution. Ensure you find the coordinates of every vertex of the feasible region, including those on the axes.

Unbounded Regions Need Verification

If the feasible region is unbounded, merely evaluating the objective function at corner points is not enough. You must draw the line ax + by = Z_min (for minimization) or ax + by = Z_max (for maximization) and check if the feasible region has any points common with the region for ax + by < Z_min or ax + by > Z_max respectively. If not, the optimal solution exists; otherwise, it doesn't.

Formulation Accuracy

Pay close attention to word problems when formulating the LPP. A single misplaced coefficient or wrong inequality in the constraints or objective function will lead to an incorrect solution.

Practice Questions with Solutions

• Q: What is the primary purpose of an objective function in a Linear Programming Problem? A: The objective function is a linear function (e.g., Z = ax + by) that represents the quantity to be optimized (maximized or minimized), such as profit, cost, or production.
• Q: What defines a 'feasible region' in an LPP, and why is it always a convex polygon? A: The feasible region is the set of all points that satisfy all the given constraints, including non-negativity. It's a convex polygon because all constraints are linear, and the intersection of half-planes defined by linear inequalities always forms a convex set.
• Q: State the fundamental theorem of LPP regarding optimal solutions. A: The fundamental theorem states that if an optimal solution for an LPP exists, it must occur at one of the corner points (vertices) of the feasible region.
• Q: Can an LPP have multiple optimal solutions? If yes, where would they typically lie? A: Yes, an LPP can have multiple optimal solutions. This occurs when the objective function's optimal value is achieved at two adjacent corner points, and consequently, at every point on the line segment joining these two corner points.

Frequently Asked Questions