Content Writer
Linear programming, also known as linear optimization, is a mathematical technique that is used to determine the maximum or minimum value of a linear function.
- In simpler terms, the method is used to find optimal solutions for the collection of linear quantities, also known as linear constraints.
- The first part of the programming, also known as the objective function, is used to maximize or minimize the quantity.
- The second part of the programming, also known as the constant set, is used to describe the condition or constraints under which optimization needs to be done.
- The concept is used in the fields of business, manufacturing, economics and telecommunication.
- Linear Programming objective function is given as
z = px + qy
- where programming constraints are as follows: x ≥ 0, y ≥ 0
According to the CBSE Syllabus 2023-24, the chapter on Linear Programming comes under Unit 5. NCERT Class 12 Mathematics Unit Linear Programming holds a weightage of around 5 marks in the board examination.
Read More:
Terms of Linear Programming Problem
- Constraints: Constraints refer to the conditions or restrictions on variables of linear inequalities. Conditions like x ≥ 0 and y ≥ 0 are called non-negative restrictions.
- Objective Function: Objective function is a type of function where linear functions of the form Z = ax + by are maximized or minimized.
- Optimal Value: Each value of the objective function is either maximized or minimized, the result of which is called the optimal value.
- Optimization Problem: An optimization problem is a type of problem where linear functions are maximized or minimized on the basis of certain conditions to determine the value of a linear variable.
Components of Linear Programming
Graphical Method of Solution for problems in two Variables
- A linear equation is a type of equation where the order of the variable is equal to one.
- When these equations have two variables, then in such a case, it is called linear equations in two variables.
- Linear equations in two variables are of the form ax +by +c = 0, where a, b and c are real numbers.
- The solution of these equations is two variables, x and y, which can be represented on the coordinate plane.
- The intersecting region on the graph will help determine the feasible region.
Steps to calculate solution for problems in two variables using Graphical Method
- First, determine the decision variables and the objective function to be maximized or minimized.
- The graph will contain n dimensions along with n number of decision variables.
- Next, insert the value of origin (0,0) to check whether the objective function has a physical solution or not.
- The feasible region on the graph is the point where all the conditions applied to the function are met.
- Plot the point on the graph and find the optimum points.
Graphical Method of Solution for problems in two Variables
Feasible and Infeasible Region
- Feasible Region: A feasible region is the region on the graph that is satisfied by all the constraints or restrictions, including non-negative constraints (x ≥ 0, y ≥ 0) is called a feasible region.
- Feasible Solutions: The feasible solutions are points that lie either inside or outside the boundary of the feasible region.
- Infeasible Region: Any point that lies outside the feasible region on the graph is called an infeasible solution and forms the infeasible region.
- Bounded and Unbounded Region: If a feasible region of the required linear inequality is enclosed within a circle, then the required region is called the bounded region; otherwise, it is called the unbounded region.
Feasible and Infeasible Solution
Optimal Feasible Solution
Any point that expresses the optimal value of the linear programming function is called the optimal feasible solution.
Theorems to find optimal solution of a linear programming program
- Theorem 1: Consider R to be the required feasible region of the objective function of the form z = ax + by. Then, Z will contain all the optimal values, whether maximized or minimized, with the variables x and y, which are subjected to different conditions applied by linear inequalities.
- Theorem 2: Let R represents the required feasible region of the objective function of the form z = ax + by. In that case, if the value of R lies in the bounded region, then the maximum or minimum value of objective function Z will lie at the corner point of R.
Corner Point Method
- The corner point method involves looking at the maximum or minimum value at the corner point of the feasible region.
- It involves choosing a theoretically possible maximum or minimum value of an objective function.
- The theory behind choosing this method involves the assumption that optimal solutions are found at corner points.
Steps to use Corner Point Method
- First, determine the feasible region of the given linear programming problem.
- Next, determine the corner point or vertices either by the method of inspection or by solving linear equations in two variables for the lines intersecting at that point.
- Evaluate the objective function calculated at each of the corner points.
- Suppose N and g represent the largest and smallest values of these points.
- If the feasible region is bounded, then, in that case, the values of N and m are the maximum and minimum values of the objective function.
- In case the value of the function is determined at the unbounded region, then in such case:
- N is the maximum value of the objective function if the open half of the plane determined by the function ax + by > N has no common point with respect to the feasible region. Otherwise, the objective function has no maximum value.
- Similarly, g is the minimum value of the objective function if the open half of the plane determined by the function ax + by < m has no common point with respect to the feasible region. Otherwise, the objective function has no minimum value.
Corner Point Method
There are Some important List Of Top Mathematics Questions On Linear programming Asked In CBSE CLASS XII
Comments