Class 12 — Mathematics (NCERT)
Linear Programming: Graphical Method and Feasible Region
Class 12
- ✓Define a Linear Programming Problem (LPP) and identify its components: objective function, constraints, and non-negative restrictions.
- ✓Graph linear inequalities to determine the feasible region of an LPP.
- ✓Identify and determine the coordinates of the corner points (vertices) of the feasible region.
- ✓Apply the Corner Point Method to find the optimal (maximum or minimum) value of the objective function.
- ✓Distinguish between bounded and unbounded feasible regions and interpret the optimal solution accordingly.
Key concepts
A method for finding the maximum or minimum value of a linear function (called the objective function) subject to a set of linear inequalities (called constraints). These problems arise in various fields like business, industry, and economics for optimal resource allocation.
The linear function, Z = ax + by, whose maximum or minimum value is to be determined. Here, 'a' and 'b' are constants, and 'x' and 'y' are decision variables representing quantities.
The system of linear inequalities or equations that limit the values of the decision variables. These represent the restrictions on resources or conditions that must be satisfied.
In most practical LPPs, the decision variables (x and y) cannot be negative, as they often represent physical quantities. Hence, x ≥ 0 and y ≥ 0 are always included as constraints, restricting the feasible region to the first quadrant.
The common region determined by all the constraints, including the non-negative restrictions (x ≥ 0, y ≥ 0), of an LPP. Any point within or on the boundary of this region represents a feasible solution. It is always a convex polygon (may be bounded or unbounded).
A set of values for the decision variables (x, y) that satisfies all the constraints of an LPP. Geometrically, it is any point in the feasible region.
A feasible solution that yields the maximum or minimum value of the objective function.
This fundamental theorem states that the optimal solution (maximum or minimum) of an LPP, if it exists, must occur at one of the corner points (vertices) of the feasible region.
A method used to solve LPPs with two decision variables. It involves graphing all constraints, identifying the feasible region, determining its corner points, and evaluating the objective function at these points to find the optimal value.
Key facts to remember
- 1A Linear Programming Problem (LPP) involves optimising (maximising or minimising) a linear objective function subject to linear constraints.
- 2The feasible region is the set of all points (x, y) that satisfy all the constraints, including non-negative restrictions (x ≥ 0, y ≥ 0).
- 3The feasible region is always a convex polygon, which can be either bounded (enclosed) or unbounded (extending infinitely).
- 4According to the Corner Point Method, the optimal solution (if it exists) for an LPP always occurs at one of its corner points (vertices) of the feasible region.
- 5If the feasible region is bounded, the objective function will always have both a maximum and a minimum value.
- 6If the feasible region is unbounded, an optimal solution may or may not exist. An additional check is required to confirm its existence.
- 7If two corner points yield the same optimal value, then every point on the line segment joining these two points also yields the same optimal value.
Worked examples
Example 1
Maximise Z = 4x + y subject to the constraints:\nx + y ≤ 50\n3x + y ≤ 90\nx ≥ 0, y ≥ 0
Answer
The maximum value of Z is 120 at x = 30, y = 0.
The feasible region is bounded, so an optimal solution is guaranteed to exist.
Example 2
Minimise Z = 3x + 5y subject to the constraints:\nx + 3y ≥ 3\nx + y ≥ 2\nx ≥ 0, y ≥ 0
Answer
The minimum value of Z is 7 at x = 3/2, y = 1/2.
For an unbounded feasible region, an additional check is required to confirm the existence of an optimal solution. If the region formed by Z < min_value (for minimisation) or Z > max_value (for maximisation) has no point in common with the feasible region, then the optimal value exists.
Common mistakes
- ✗**Incorrectly shading the feasible region**: Students often make errors in determining which side of the line to shade for inequalities (e.g., confusing '>' with '<'). Always test a point (like the origin if it's not on the line) to verify.
- ✗**Errors in finding intersection points**: Algebraic mistakes while solving simultaneous equations to find the coordinates of corner points.
- ✗**Ignoring non-negative restrictions**: Forgetting to restrict the feasible region to the first quadrant (x ≥ 0, y ≥ 0), which is crucial for most practical problems.
- ✗**Misinterpreting unbounded regions**: Failing to perform the additional check for unbounded feasible regions to confirm the existence of an optimal solution.
- ✗**Calculation errors**: Simple arithmetic mistakes when evaluating the objective function at the corner points.
Exam tips
- ★**Draw neat and accurate graphs**: Use a ruler and pencil. Label the axes, the lines representing the constraints, and the corner points clearly. This helps in correctly identifying the feasible region and its vertices.
- ★**Clearly identify the feasible region**: Shade it distinctly to avoid confusion. This is a key part of the graphical method.
- ★**Show all calculations for corner points**: Even if they seem obvious, explicitly write down the equations you are solving to find intersection points. This ensures partial credit even if the final answer is incorrect.
- ★**Organise the evaluation of the objective function**: Create a table listing corner points and their corresponding Z values for easy comparison and to minimise calculation errors.
- ★**For unbounded regions, explicitly state the check**: Draw the Z < min_value (or Z > max_value) line and explain whether it intersects the feasible region. This demonstrates a complete understanding of the concept.
Ready to practise?
Try a problem on this topic
Snap a photo or type a question — get step-by-step working instantly.