UNIT-V : LINEAR PROGRAMMING Term-| LINEAR PROGRAMMING > Introduction, related terminology such as constraints, objective function, optimization, different types of linear programming (I.P.) problems, graphical method of solution for problems in two variables, {feasible and infeasible region (bounded), feasible and infeasible solutions, optimal feasible solutions (up to three non-trivial constraints). STAND ALONE MCQs (1 Mark each) Q.1. The comer points ofthe feasible region determined _Q. 2'The feasible solution for a LPP is shown in given by the system of linear constraints are 0,0), (0, 40), figure. Let Z 4y be the objective function (20, 40), (60, 20), (60,0). The objective function is Minimum of Z occurs at Z= ax y Compare the quantity in Column A and Column B (4,10) Column A Column B Maximum of Z. 325 0.8), (A) The quantity in column Ais greater (B) The quantity in column Bis greater, (©) The two quantities are equal. (D) The relationship cannot be determined on the basis ofthe information supplied. Ans. Option (B) is correct — F 0,40) zu ‘Ans. Option (B) is correct. (20, 40) 200 Be (60, 20) 300 — Maximum. —— So, the quantity in column Bis greater. a)69 15 < Maximum 65) 2 68) a (4, 10) 28 8) 32 © Minimum ence, ihe minimum of Z occurs at (0, 8) and its rin imnurn value is (32). Q.3. Refer to Q2of multiple choice questions, maximum ‘of Z occurs at (a) 6.0) (B) (6,5) © 68) (D) 4.10) ‘Ans, Option (A) is correct [esptonaion Maximum of ocursat(50. | 4. Referto Q.2of multiple choice questions, (Maximum Value of Z + Minimum value of Z) is equal to (ays at © 13 o 7 Ans. Option (D) is correct Explanation: Maximum value of 2 + Minimum| value of Z = 15 —32= 17 Q.5. The feasible region for an LPP is shown in the given Figure, Let F = 3x ~ dy be the objective function. Maximum value of Fis (2,6) 4 eo (ajo (B) 8 jon (D) -18 Ans. Option (C) is correct. Explanation: The feasible region as shown in the! [.sptanation: Minimum value of Fis ~16.t 0,4). Q.7.Corner points of the feasible region for an LPP are (0.2), (,0), (6,0) (6,8) and 0,5) Let F = 4s + 6y be the objective function, ‘The minimum value of Toesurs at (A) @.2)only (8) G.0)only (the mid-paint of the Hine segment joining the points 0,2) and @, 0) only {) any point on the line segment joining the points (0,2)and (3,0) Ans. Option (D) is correct Explanation : Corresponding value ‘Comer points Beate GD = Minimum Go 12 © Minimum 6.9) 24 3), 72 & Maximum wa) 30 Flence, minimum value of Foccurs at any points (on the line segment joining the points (0,2) and 0) Q.8. Refer to Q. 7 above, Maximum of F~ Minimum of Fe (ay 0 (B) 48 on (D) 18 ‘Ans. Option (A) is correct Explanation: Maximum of F ~ Minimum of F=72-12 Q.9.Corner points of the feasible region determined by the system of linear constraints aze (0,3), (1,1) and G,0)- Let Z = px + ay, where p,q > 0. Condition on. jpandg 30 that the minimum of Z occurs at (3,0}and Dis Wray (B) p= 92 Or=% Dp Ans. Option (B) is correct Explanation igure, has objective function F = 2 ~4y GESaIRETaE Corresponding value Comer points | of Z= pt ay Comer points fi eereah a 0) 0 OE 3 (2, 6) 12 © Maximum a.) eta 4 =16 — Minimum —— — Hence, ihe maximum Value of is 12 Q. 6 Refer to Q5 of multiple choice questions, minimum value of Fis (ajo (B) -16 on (D) does not exist Ans. Option (B) is correct. 'So, condition of p and g, so that the minimum of Z occurs at (3,0) and (1,1) isASSERTION AND REASON BASED MCQs (1 Mark each) Directions: Inthe following questions, A statement ‘of Assertion (A) is followed by a statement of Reason (R). Mark the correct choice as (A) Both Aand Rare trueand Risthe correct explanation ofA (B) Both A and R are true but R is NOT the correct explanation of A (©) Ais true but Ris false {D) Ais false but Ris True Q.1.Assortion (A): Feasible region is the set of points which satisfy all of the given constraints and ebjective function too. Reason (R) is also correct. Reason (R): The optimal value of the objective - function is attained atthe points on X-axis only Sines Rotts Laity [Ans Option (C) is correct Go) 2 Explanation: The optimal value of the objective (2,3) é function is attained at the comer points of (22) feasible region aa et Q.2. Assertion (A): The intermediate solutions of 5) 5 constraints must be checked by substituting them back into objective function Q.4. Assertion (A): Z = 20s, + 20x, subject to x, 0, Reason (K) a2 2x, + 25,2805, +252 15,34, + 26,220 Out of the corer points of feasible region (8, 0), 5.15) (7 9) } (0.0 the nu au of yay(aa) em n° 2ccunai (2.2) Reason (R) + Here (0,2) (0,0) and (3,0) all are vertices of feasible Corner Points 2% = We, | Ae, region. Oy 160) Ans. Option (D) is correct. ; plenation: The intermediate solutions of (4) bs constraints must be checked by substituting them back into canstraint equations. ( ) i Q.3. Assertion (A) + For the constraints of linear ‘optimizing function Z ~ x, + x, given by x, +3, 1, 10) 200 3x, + x, 2 1 there is no feasible region, ‘Ans. Option (A) Is correct Reason (R): Z = 7x + y, subject to 5x + y <5, x+y 23,220, y20. Out ofthe comer points of Explanation: Assertion (A) and Reason (R) both are correct and Reason (R) is the correct explanation of Assertion (A), . coe ron 0, (25), aa 09, te snanimum value of Z occurs at (7,0). Q.5. Assertion (A): For the constraints of a LPP problem ‘Ans. Option (B) i correct given by _ Fmertion (OY texorred 1+ 2s, $2000, x, + 4,5 1800, x, $600 and x), 20, eae ran ant 7 theo points (10, 0, 0 50), 2 U) ie i te positive [Cleary from the graph below that there is no aeedeutace bounded region, but point (2000, 0) does not lie in sa the positive bounded regionReason (R): septa 1500 From the graph, Iti clear that the point (2000, 0) outside. ‘Ans. Option (A) is correct [sr Assertion (A) and Reason (R) snl are correct, Reason (R)is the correct explanation of Assertion (A). CASE-BASED MCQs Q. 6, Assertion (A) : The graph of x <2 and y2 2 will be situated in the first and second quadrants Reason (R): x yea a >x ‘Ans. Option (A) is correct. Explanation: It is lear from the graph given “| the Reason (R) that Assertion (A) i tue. ‘Attempt any four sub-parts from each question. Each sub-part carries 1 mark. [Read the following text and answer the following {questions on the basis ofthe same: ‘An eeroplane con carry a maximum of 200 passengers. A profit of © 1000 is made on each ‘execulive class licket and a profit of € 600 is made ‘on each economy elass ticket. The airline reserves at least 20 seals for the executive class. However, at least 4 times as many passengers prefer to travel by ‘economy class, than by executive class. tis given That the number af execitive clas tickets ie x and that of economy class tickets is. ik Q.1. The maximum value of x + yis, (a) 100 (8) 200 19» ©) 80 nt bi Ans. Option (B) is carrect. Q.2.The relation between x andl y is, Ayxcy (B) y>80 (© x24y (D) yee ‘Ans. Option (D) is correct. Q.3. Which among these isnot a constraint for this LPP? (A) x20 (@) x4 ys200 (9 280 (D) 4x-ys0 ‘Ans. Option (C) is comrect. Q.4. The profit when y= 20 and y= 80 is, (A) 2600000 (B) 68,000 (©) 264,000 (D) 21,26,000 Ans. Option (B) is correct. Q.5. The maximum profitis® (A) 1,26,000 (8) 1,28,000 (©) 68,000 (D) 1,20,000 ‘Ans, Option (A) is correct. Explanation: Objective function Maximise Z: = 100s + 600y Constraints x+y 220 y22,x20 yeas0. ‘The comer points are AQ0, 180), B(10, 160), 120, 80) Evaluating the objective function Z= 1000x + 600y at A, Band C ‘Z= L000 x 2+ 600 x 180 = 20,000 + 1,08,000, 128,000 1000 % 40+ 600 > 160) 40,000 + 96,000 1,36,000 (max) 1000 x 20 + 600 80 = 20,000 + 48,000 = © 68,000 Jor Zis maximum, when x = 40, y = 160. Jor 40 tickets of executive class and 160 tickets Jof economy class should be sold to get the maximum profit of 1,36,000, At A(20, 180), At B40,160), 2 ALCO, 80), Z: Read the following text and answer the following questions on the basis of the sau ‘A dealer in rural area wishes to purchase a number cof sewing machines. He has only 25,760 to invest and has space for at most 20 items for storage. An lectronic sewing machine cost him %30 and a manually operated sewing machine @240, He can soll an electronic sewing machine at a profit of 22 and a manually operated machine ata profit of 718. ‘Assume that the electronic sewing machines he can sella x and that of manually operated machines iy. ‘The objective fun {A) Maximise Z = 360% + 240y (B) Maximise Z = 22x + 18y (© Minimise Z = 360% + 240 (©) Minimise 7 = 228 + 1y ‘Ans, Option (B) i correct Q.2.The maximum value af x+y is (a) 5760 on Ans. Option (D) is correct. Q.3. Which ofthe following is nota constraint? (8) 18 (D) 20 (a) xt y220 (8) 360% + 240y 35,760 (x20 ()y20 ‘Ans, Option (A) is correct. Q.4. The profit is maximum when (9 ) 615) ©) 613 (© (12,8) (D) (15,5) Ans. Option (8) correct. Q.5.The maximum profit ist. (a) 5,700 (B) 392 (© 382 (D) 290 Ans, Option (B) is correct. Explanation: Objective function : Maximise Z, (Constraints 2x + I8y xtys 20 360 + 240y < 5,700 Be 2y <8 x= 0, y20 lor y DO,29 Vorices of feasible region are: A, 20), 28 12), CAG, 0) & 00, 0) (a) = 360, PB) = 282, PC) = 352 ++ For Maximum P, Electronic machines and Manual machines = 12, Max. profit 8392II, Read the following text and answer the following, questions on the basis of the same: A fruit grower can use two types of fertilizer in his ‘garden, brand P and brand Q, The amounts (in kg) ‘of nitrogen, phosphoric acid, potash, and chlorine ina bag of each brand are given in the table. ‘ests indicate that the garden needs at least 240 kg of phosphoric acid, at least 270 kg, of potash and at most 310 kg of chlorine. eg por bag Brand P Brand Q Nanogen 3 35 Phosphoric acid 1 2 Potash 3 Ls Chlorine is 2 Q.1. The Objective function to minimise the amount of nitogen added to garden? (A) Maximise Z = + y (B) Minimise Z = 2x +35y (C) Maximise Z = 4x + 3.5y (D) Minimise Ont dy ‘Ans. Option (B) is correct. Q.2.1f the grower wants to minimise the amount of nitrogen added to the garden, how many bags of brand P should be used? (a) 40 (©) 100 Option(A) is correct. the grower wants to minimise the amount of nitrogen adcied to the garden, how many bags of ‘brand Q should be used? (B) 50 (D) 60 Ans. (a) 0 @ 50 (©) 100 (0) 0 ‘Ans. Option (C) is correct. ‘Q.4. What is the minimum amount of niteogen added in the garden? (A) 595, (@) 550kg (©) 400kg (0) 470kg Ans. Option (D) is correct, (Q.5.What is the total number of bags used by f ‘grower to minimise the amount of nitrogen ? (a) 160 (B) 190 © 40 (0) 30 ‘Ans. Option (C) is correct. Explanation: Let the fruit grower use x bags of brand P and y bags of brand Q. he problem can be formulated as follows: Minimise Z = ax + 3.5y Ai) [Subject to the constraings, x+2y 2 240 i) x4 05y = 90 ca Lr +2y < 310 Gv) ny20 lV) The feasible region determined by the system of constraints is as follows: oeeszeye The corner points are A(240, 50), B(20, 140), and }c(40, 100) re Goins | 223+ Sy ACA, 50) 535 B20, 140) 350 (C40, 100) 70 = Minimum Te mininaun value of Z is 470 at (40, 100). Tus, 40 bags of brand P and 100 bags of brand |Qshould be added to the garden to minimise the Jemount of nitrogen. Jum amount of nitrogen added to the garden is 470 kg. The mini