Class 12 Mathematics (041) · Chapter 12 NotesLinear Programming

A Linear Programming Problem (LPP) starts with identifying decision variables, usually denoted as x and y, which represent the quantities to be determined. The problem aims to optimize a linear objective function, expressed as Z = ax + by, where a and b are constants. This optimization is subject to various constraints, which are linear inequalities or equations that limit the values of the decision variables based on available resources like budget, space, or time. Additionally, non-negative restrictions (x >= 0, y >= 0) are always included because physical quantities like items produced or hours worked cannot be negative. This mathematical structure allows complex business or logistical decisions to be solved using systematic algebraic and geometric techniques.

• Objective FunctionThe linear function Z = ax + by to be maximized or minimized
• Decision VariablesThe variables x and y that represent unknown quantities
• ConstraintsLinear inequalities or equations restricting the variables
• Non-negative RestrictionsThe conditions x >= 0 and y >= 0

When all the linear constraints of an LPP, including the non-negative restrictions, are graphed on a coordinate plane, the common area that satisfies every inequality simultaneously is called the feasible region. Every point within this region, as well as every point on its boundary, represents a feasible solution to the problem. These points are valid choices that meet all the given requirements. Conversely, any point outside this region is an infeasible solution because it violates at least one constraint. The feasible region is always a convex region, meaning any line segment connecting two points within the region lies entirely inside the region. Identifying this area is the first step in finding the optimal solution.

• Feasible RegionThe common shaded area determined by all constraints
• Feasible SolutionAny point (x, y) located within or on the boundary of the feasible region
• Infeasible SolutionAny point outside the feasible region
• Convex RegionThe geometric property where the region has no indentations

The solution to an LPP is governed by two major theorems. Theorem 1 states that if an optimal value (maximum or minimum) exists for an objective function Z = ax + by, it must occur at a corner point (vertex) of the feasible region. A corner point is where two boundary lines intersect. Theorem 2 specifies that if the feasible region is bounded (meaning it can be enclosed within a circle), then the objective function will definitely have both a maximum and a minimum value, and both will occur at corner points. If the region is unbounded, a maximum or minimum value might not exist, but if it does, it will still be found at one of the vertices.

• Theorem 1Optimal values occur at the vertices of the feasible region
• Theorem 2Bounded regions always guarantee both a maximum and a minimum value
• Corner PointThe intersection of two boundary lines in the feasible region
• Bounded vs UnboundedBounded regions are finite; unbounded regions extend infinitely

The Corner Point Method is a systematic procedure for solving LPPs graphically. First, the feasible region is graphed and all its corner points are identified. Second, the objective function Z = ax + by is evaluated at each of these corner points. For a bounded region, the largest resulting value is the maximum, and the smallest is the minimum. If the region is unbounded, extra steps are required. To check if a value M is truly the maximum, one must graph the open half-plane ax + by > M and see if it shares any points with the feasible region. If it does, no maximum exists. A similar check is done for the minimum using ax + by < m.

• Step 1Graph constraints and find the feasible region
• Step 2Identify coordinates of all corner points
• Step 3Calculate Z at each corner point
• Step 4For unbounded regions, verify the optimal value using an open half-plane check

Sometimes, an LPP may not have a single unique solution. If two different corner points produce the same maximum or minimum value, then every single point on the line segment connecting those two corner points is also an optimal solution. This results in infinite optimal solutions for the same problem. On the other hand, some problems have no solution at all. This occurs when the system of linear inequalities is inconsistent, meaning there is no overlapping area that satisfies all constraints simultaneously. In such cases, the feasible region does not exist, and therefore, no feasible or optimal solution can be found.

• Multiple Optimal SolutionsOccurs when two vertices yield the same optimal value
• Line Segment PropertyAll points on the segment between two optimal vertices are also optimal
• No Feasible SolutionOccurs when there is no common region for the constraints
• InconsistencyWhen constraints contradict each other