Title 12. LINEAR PROGRAMMING.pdf ✅

Revision Notes z Linear Programming Problems: Problems which minimize or maximize a linear function z subject to certain conditions determined by a set of linear inequalities with non-negative variables are known as linear programming problems. z Objective function: A linear function z = ax + by, where a and b are constants which has to be maximised or minimised according to a set of given conditions, is called as linear objective function. z Decision variables: In the objective function z = ax + by, the variables x, y are said to be decision variables. z Constraints: The restrictions in the form of inequalities on the variables of a linear programming problems are called constraints. The condition x 3 0, y 3 0 are known as non-negative restrictions. [Board 2017, 18, 19, 20, 21, 22, 23] z Feasible region: The common region determined by all the constraints including non-negative constraints x, y ≥ 0 of linear programming problem is known as the feasible region. z Feasible solution: Points with in and on the boundary of the feasible region represents feasible solutions of constraints. In the feasible region, there are infinitely many points (solutions) which satisfy the given conditions. THEOREMS 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 variables x and y are subject to constraints described by linear inequalities, the optimal value must occur at a corner point (vertex) of the feasible region. 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 the objective function Z has both maximum and minimum values of R and each of these occurs at a corner point (vertex) of R. However, if the feasible region is unbounded, the optimal value obtained may not be maximum or minimum. Example-1 Solve the following linear programming problem graphically: Maximise Z = 4x + y Subject to the constraints: x + y ≤ 50 3x + y ≤ 90 x ≥ 0, y ≥ 0 Sol. Let x + y ≥ 50 ...(i) 3x + y ≥ 90 ...(ii) x ≥ 0, y ≥ 0 ...(iii) x + y = 50 3x + y = 90 X 0 50 Y 50 0 X 0 30 Y 90 0 From graph, we see that feasible region is OABCO. The coordinates of the corner points O, A, B and C of feasible region are (0, 0), (30, 0), (20, 30) and (0, 50) respectively. Now we evaluate Z at each corner point. Corner Point Value of Z = 4x + y O (0, 0) 0 A (30, 0) 120 (Maximum) B (20, 30) 110 C (0, 50) 50 Hence, maximum value of Z is 120 at the point (30, 0). Scan this Linear Programming Introduction UNIT – V : LINEAR PROGRAMMING LINEAR PROGRAMMING Learning Objectives After going through this Chapter, the student would be able to learn:  Optimal Solution  Feasible, Bounded and Unbounded region  Graphical method for LPP 12 CHAPTER

Linear Programming SUBJECTIVE TYPE QUESTIONS Short Answer Type Questions-I (2 marks each) 1. A small firm manufactures necklaces and bracelets. The total number of necklaces and bracelets that it can handle per day is at most 24. It takes one hour to make a bracelet and half an hour to make a necklace. The maximum number of hours available per day is 16. If the profit on a necklace is ` 100 and that on a bracelet is ` 300. Formulate on L.P.P. for finding how many of each should be produced daily to maximize the profit ? It is being given that at least one of each must be produced. R&U [Delhi Set-1, 2017] Sol.Let x necklaces and y bracelets are manufactured \ L.P.P. is Maximize profit, P = 100x + 300y 1⁄2 Subject to constraints x + y £ 24 1 2 x + y £ 16 or x + 2y £ 32 1⁄2 + 1⁄2 + 1⁄2 x, y 3 1 [Marking Scheme Delhi Set-1, 2017] 2. A firm has to transport at least 1200 packages daily using large vans which carry 200 packages each and small vans which can take 80 packages each. The cost for engaging each large van is ` 400 and each small van is ` 200. Not more than ` 3,000 is to be spent daily on the job and the number of large vans cannot exceed the number of small vans. Formulate this problem as a LPP given that the objective is to minimize cost. R&U [Delhi Comptt. Set-1, 2017] 3. If a 20 year old girl drives her car at 25 km/h, she has to spend ` 4/km on petrol. If she drives her car at 40 km/h, the petrol cost increases to ` 5/km. She has ` 200 to spend on petrol and wishes to find the maximum distance she can travel within one hour. Express the above problem as a Linear Programming Problem. R&U [SQP 2016-17] Sol. Let the distance covered with speed of 25 km/h = x km and the distance covered with speed of 40 km/h = y km 1⁄2 Total distance covered = z km The L.P.P. of the above problem, therefore, is Maximize z = x + y 1⁄2 Subject to constraints 4x + 5y £ 200 x y 50 40 + £ 1 1⁄2 and 25 40 x y + ≤ 1 and x 3 0, y 3 0 1⁄2 [Marking Scheme SQP, 2016-17] Short Answer Type Questions-II (3 marks each) 1. Solve the following linear programming problem graphically: Minimize : Z = 5x + 10y subject to constraints: x + 2y ≤ 120 x + y ≥ 60 x – 2y ≥ 0 x ≥ 0, y ≥ 0. U [Outside Delhi Set-1, 2023-24] [Delhi Set-1, 2, 3, 2017] OR Solve the following Linear Programming problem graphically: Minimize: Z = 6x + 3y Subject to the constraints: 4 + 80 +5 115 3 2 , 150 0, 0 x y x y x y x y ≥ ≥ + ≤ ≥ ≥       Ap [Delhi Comptt. Set-1, 2017] Concept Applied Minimization LPP Topper's Answer, 2023 Sol. These Questions are for practice and their solutions are given at the end of the chapter.