Linear Programming Class 12th PDF

# Welcome to Filo! # filo संपूर्ण शिक्षा कवच ## Subject: MATHEMATICS ## Chapter: Linear Programming # LECTURE - 1 ## Linear Programming ### Introduction The technique of linear programming is used to make best possible use of the available resources. The linear programming problems deal with...

# Welcome to Filo! # filo संपूर्ण शिक्षा कवच ## Subject: MATHEMATICS ## Chapter: Linear Programming # LECTURE - 1 ## Linear Programming ### Introduction The technique of linear programming is used to make best possible use of the available resources. The linear programming problems deal with determining the optimal allocation of the resources to meet the given objectives such as least cost, maximum profit or return within minimum time, effective utilisation of the man power etc. # Some Definitions 1. **Optimization Problem:** A problem which maximises or minimises a linear function involving two or more variables subject to certain constraints as determined by a set of linear inequalities is called optimization problem. Linear Programming Problems (LPP) is a special type of optimization problem. 2. **Optimization Function:** Objective function is the linear function which is to be maximised or minimised. The objective function describes the purpose of formulating linear programming problem and it is always non-negative. In business applications the profit function which is to be maximised or the cost function which is to be minimised are objective functions. 3. **Constraints:** The inequalities or equations in the variables of a linear programming problem which describes the conditions under which the optimization is to be done are called constraints, i.e., the constraints are the restrictions of the LPP. 4. **Non-negativity Restrictions:** These are the constraints which describe that the variables involved are non-negative. # Mathematical Formulation of Linear Programming Problems The following are the steps for formulating Linear Programming Problems (LPP). 1. In every LPP certain decisions are to be made. These decisions are represented by decision variables. These decision variables are those quantities which are to be determined. Identify the variables and denote them by $x_1, x_2, x_3, ..., x_n$. 2. Identify the objective function and express it as a linear function of the decision variables. 3. In a LPP objective function is to be either maximised or minimised. Identify the type of the objective function. 4. Identify the set of constraints. Express them as a set of linear inequalities. # Different Types of Linear Programming Problems 1. **Manufacturing Problems:** In these problems, we determine the number of units of different products to be produced and sold by a firm when each requires a fixed men power, machine hours, labour hour per unit of the product, warehouse space per unit of the product etc., in order to make maximum profit. 2. **Diet Problems:** In these problems, we determine the amount of different kinds of constituents/nutrients which should be included in a diet so as to minimise the cost of the desired diet such that it contains certain minimum amount of each constituents/nutrients. 3. **Transportation Problems:** In these problems, we determine the transportation schedule in order to find a cheapest way of transporting a product from plants/factories situated at different locations to markets. # General Mathematical Description of a LPP The general form of a linear programming problem is Optimize (Maximise or Minimise) $Z = c_1x_1 + c_2x_2 + ... + c_nx_n$ *(Objective function)* Subject to $a_{11}x_1 + a_{12}x_2 + ... + a_{1n}x_n (≤,=,≥) b_1$ $a_{21}x_1 + a_{22}x_2 + ... + a_{2n}x_n (≤,=,≥) b_2$ .... .... $a_{n1}x_1 + a_{n2}x_2 + ... + a_{nn}x_n (≤,=,≥) b_n$ (Constrints) $x_1, x_2, ..., x_n ≥0$ (Non-negativity restrictions) # Solution of a Linear Programming Problem A set of values of the variables $x_1, x_2, x_3, ..., x_n$ of the LPP which satisfy the constraints is a solution of the LPP. # Feasible Solution Set of values of the variables which satisfy the constraints as well as non-negativity restrictions also are the feasible solutions of the LPP. In other words feasible solutions are those solutions which satisfy the non-negativity restrictions of the LPP also. # Infeasible Solution Set of solutions of the LPP which do not satisfy the non-negativity restrictions are infeasible solutions. In the LPP given above, x = 1, y = 1, x = 2, y = 1, x = 2, y = 2 are feasible solutions whereas x = −2, y = -3 is an infeasible solution. # Feasible Region The common region determined by all the constraints of a LPP is called the feasible region and every point in this region is feasible solution of the LPP. In other words, the graph of the system of linear inequations, comprising of constraints of the given LPP, is the feasible region of the given LPP. It is either bounded or unbounded. It is bounded if it is enclosed within a circle. It is unbounded if it cannot be enclosed within a circle i.e., if it extends to infinity. # Optimal Feasible Region A feasible region of an LPP is said to be an optimal feasible solution, if it also optimizes (maximises or minimises) the objective function. Now, we shall discuss some definitions and results related to feasible solutions of a LPP. # Convex Set A Set is said to be a convex set if the line segment joining any two points of the set, lies completely within the set. All polygons are convex sets. # Theorem The set of all feasible solutions of a LPP is a convex set. It follows from the theorem that the set of all feasible solutions of a LPP is a convex polygon. In a LPP, we have to find the optimum solution. Sometimes the LPP may not have maximum or minimum values. However, if it exists, then one of the extreme points or corner points of the convex polygon of the feasible solutions will give the optimal solution. This is stated in the following theorem. # Fundamental Extreme Point Theorem An optimal solution of an LPP, if it exists, occurs at any one of the extreme (or corner) points of the convex polygon of the set of all feasible solutions. **Note** 1. It may happen that two vertices of the convex polygon will give optimum value for the objective function. In such a case all the points on the line segment joining these two vertices will give optimum value. In such cases the LPP has infinitely many solutions. 2. Sometimes the convex polygon is an empty set. In such a case the LPP has no solution. # Graphical Method of Solving Linear Programming Problems Graphical method is suitable for solving LPP which contains two variables only. If a LPP contains more than two variables then the graphical method is not suitable to solve them. # Corner Point Method This method is based on the Fundamental extreme point theorem. The following algorithm can be used for solving a LPP involving two variables using corner point method. **Steps for Solving LPP Using Corner Point Method** 1. Draw the graphs of all constraints given in the LPP. 2. Mark the common area, i.e., the feasible region by shaded lines. 3. Find the coordinates of all the vertices of the feasible region. 4. Find the value of the objective function $Z = ax + by$ at each vertex of the feasible region. Let M and m be respectively the maximum and minimum values of Z at the vertices of the feasible region. # QUESTION A toy company manufactures two types of doll; a basic doll A and a deluxe version doll B. Each doll of type B takes twice as long to produce as one of type A and the company would have time to make a maximum of 2,000 per day if it produces the basic version. The supply of plastic is sufficient to produce 1500 dolls per day (both A and B combined). The deluxe version requires a fancy dress of which there are only 600 per day available. If the company makes a profit of 3 and 5 per doll respectively on doll A and doll B; formulate the linear programming problem to maximize the profit. # QUESTION A dietician wishes to mix two types of food in such a way that the vitamin contents of the mixture contains at least 8 units of vitamin A and 10 units of vitamin C. Food I contains 2 units per kg of vitamin A and 1 unit per kg of vitamin C while food II contains 1 unit per kg of vitamin A and 2 units per kg of vitamin C. It costs ₹ 5 per kg to purchase food I and ₹ 7 per kg to purchase food II. Formulate the Linear Programming Problem to minimize the cost of such a mixture. # QUESTION Solve the LPP graphically Maximize $Z = 5x + 3y$ Subject to $3x + 5y ≤ 15$ $5x + 2y ≤ 10$ and, $x, y ≥ 0$ # "Just as a mountaineer climbs a mountain - because it is there, so a good mathematics student studies new material because it is there." - JAMES B. BRISTOL