CBSE Class 12 Maths Notes Chapter 12 Linear Programming
Linear Programming Problem: A linear programming problem is one in which we have to find optimal value (maximum or minimum) of a linear function of several variables (called objective function) subject to certain conditions that the variables are non-negative and satisfying by a set of linear inequalities with variables, are sometimes called division variables.
Terms related to Linear Programming
Objective Function: A linear function z = px + qy (p and q are constants) which has to be maximised or minimised, is called an objective function.
Constraints: The linear inequalities or equations or restrictions on the variables of the linear programming problem are called constraints. The conditions x ≥ 0, y ≥ 0 are called non-negative restrictions.
Optimal Value: The maximum or minimum value of an objective function is known as its optimal value.
Optimisation Problem: A problem, which seeks to maximise or minimise a linear function subject to certain constraints as determined by a set of linear inequalities, is called an optimisation problem.
Feasible Region: The common region determined by all the constraints including non-negative constraints x,y>0 of a linear programming problem is called the feasible region for the problem. The region other than the feasible region is called an infeasible region. The feasible region is always a convex polygon.
Feasible Solutions: Points within and on the boundary of the feasible region represent feasible solutions of the constraints. Any point outside the feasible region is called an infeasible solution.
Optimal Feasible Solution: Any point in the feasible region that gives the optimal value of the objective function is called the optimal feasible solution.
Bounded and Unbounded Region: A feasible region of a system of linear inequalities is said to be bounded, if it can be enclosed within a circle. Otherwise, it is called unbounded.
Fundamental Theorems for Solving Linear Programming
Theorem 1: Let R be the feasible region for a linear programming problem and let z = ax + by be the objective function. When z has an optimal value (maximum or minimum), where the variables x and y are subject to constraints described by linear inequalities. This optimal value must occur at a corner point (vertex) of the feasible region.
Note: A corner point of a feasible region is a point in the region which is the intersection of two boundary lines.
Theorem 2: Let R be the feasible region for a linear programming problem and let z = ax + by be the objective function. If R is bounded, then z has both a maximum and a minimum value on R and each of these recurs at a corner point of JR.
Note: Maximum or a minimum may not exist,- if the feasible region is unbounded.
Corner Point Method: The corner point method says that, if a maximum or minimum value exists, then it will occur at a corner point of the feasible region.
Steps for Applying Corner Point Method
Find the feasible region of the linear programming problem and determine its corner points either by inspection or by solving the two equations of the lines intersecting at that point.
Evaluate the objective function z = ax + by at each corner point. Let M and m be, respectively denote the largest and the smallest values of these points.
If the feasible region is bounded, then M and m respectively are the maximum and minimum values of the objective function at corner points.
If the feasible region is unbounded , then
(a) M is the maximum value of objective function z, if the open half plane determined by ax + by > M has no point in common with the feasible region. Otherwise, z has no maximum value.
(b) m is the minimum value of z, if the open half plane determined by ax + by < m has no point in common with the feasible region. Otherwise, z has no minimum value.
If two corner points of the feasible region are both optimal solutions of the same type, i.e both produce the same maximum or minimum, then any point on the line segment joining these two points is also an optimal solution of the same type.