UNIT = XI 56, LINEAR PROGRAMMING 1496 - 1540 56.1. Introduction 1496; 56.2. Some Definitions 1497; 56.3. Mathematical formulation of Linear Programming Problems 1498; 56.4 Graphical Method of Solving Linear Programming Problems 1506; 56.5 Corner Point Method 1506; 566, ISO-profit or 1SO-cost Method (Maximum Z) 1512;56.7 ISO-Profit or ISO-Cost Method (Minimum Z) 1512; 56.8 Solution of Linear Programming Problems 1516; 56.9 Theory of Simplex Method Some Important definitions 1532 UNIT = XIV 57. STATISTICAL TECHNIQUE 1841 - 1577 57.1 Statistics 1541; 87.2 Frequency Distribution. 1541; 57.3 Graphical Representation 1541; 57.4 Exclusive and Inclusive Class Intervals 1542; 57.5 Average or Measures of Central Tendency 1543;57.6 Arithmetic Mean 1543;57.7 Median 1544; 57.8 Quartiles 1545, 57.9 Deciles 1546; 57.10 Percentiles 1546; 57.11 Mode 1846; 57.12 Geometric Mean 1547; 57.13 Harmonic Mean 1547;,57.14 Average Deviation or Mean Deviation 1547 57.15 Standard Deviation 1548; 57.16 Shortest Method for Calculating Standard Deviation 1548; 57.17 Symmetry 1549; 57.18 Skewness 1549; 57.19 Test of Skewness 1550; 57.20 Uses of skewness 1550;57.21 Types of distribution 1550; 57.22 Measure of Skewness 1550; 57.23 Karl Pearson’s Coefficient of Skewness: 1550;57.24 Types of skewness in terms of mean and mode 1550; 57.25 Bowley’s Coefficient of Skewness 1553; 57.26 Measure of Bowley’s Coefficient of Skewness 1553; 57.27 Characteristics of Bowley’s Coefficient of Skewness 1553; 57.28 Limitations of Bowley's Coefficient of Skewness 1553; 57.29 Kelly’s Coefficient of Skewness 1556; 57.30 Moments 1558; 57.31 Moment about Mean 1558; 57.32 Moments about any Number (Raw Moment) 58; 57.33 Moment about the Origin 1560; 57.34 Relation between #, and p,” 1560; 57.35 Relation between v, and p, 1561;57.36 Measure of Skewness Based on Moment 1562; 57.37 Kurtosis 1563; 57.38 Grouping Error and its Sheppart’s corrections (for moments) 1563;57.39 Moment Generating function 1572; 57.40 Moment Generating Function of a Function of Continuous Variate 1574; 57.41 Property of Moment Generating Function 1574, 58, METHOD OF LEAST SQUARES 1578-1591 58.1 Principle of Least Square 1578; $8.2 Method of Least Squares 1578; 58.3 Change of origin and scale 1581; 58.4 To fit up the parabola 1583; 58.5 Change of Scale in Second Degree Equations 1588 59, CORRELATION AND REGRESSION 1592-1618 59.1 Introduction 1592; 59.2 Type of Distribution 1592; 59.3 Covariance 1592; 59.4 Correlation 1593; 59.5 Types of Correlations 1593; 59.6 Scatter or Dot-diagram 1594; 59.7 Karl Pearson's coefficient of Correlation 1595; 59.8 Coefficient of Correlation of Grouped Data 1597; 57.9 Spearman’s Rank correlation 1589; 57.10 Spearman’s Rank Correlation coefficient 1589; 59.11 Equal Ranks 1601; 59.12 Correlation Factor 1601; 59,13 Regression 1605;59.14 Line of Regression 1608; 59.15 Equations to the Lines of Regression 1605; 59.16 Multiple Regression 1615;59.17 Error of Prediction 1615;59.18 Relation between Regression analysis and Correlation analysis 1617 cevtiy1496 Higher Engineering Mathematics CHAPTER LINEAR PROGRAMMING 56.1. INTRODUCTION twill be of interest to know that linear programming had its origin during the second world war (1939-45). To fight the war man and material (resources) have to be maintained. There has to be efficient and safe land, sea and airtransport etc. ‘The government in England studied the problems during war particularly problems of armed forces, civil defence and navel strategy etc. The study for the solutions of the above prob- lems resulted the linear programming. Linear programming is the most popular mathematical technique which involve the limited resources in an optimal manner. ‘The term programming means planning to maximize profit or minimize cost or minimize loss ‘or minimum use of resources or minimizing the time etc. Such problems are called optimization Problem. The term linear means that all equations or inequations involved are linear, Example 1. A manufacturer produces two types of toys i.e., A and B. Each toy of type A requires 4 hours of moulding and two hours of polishing whereas each toy of type B requires 3 hours of moulding 5 hours of polishing. Moulder works for 80 hours in a week and polisher works for 180 hours in a week. Profit on a toy of type A is Rs. 3 and on a toy of {ype Bis Rs. 4. In what way the manufacturer allocates his production capacity for the two {types of toys so that he may make the maximum profit per week. Solution, ‘Table. The ahove information can be written in tabular form as follows: ‘operation Moulding Polishing Profit Tey (in hours) (in hours) fin Rs.) A 4 2 3 B 3 3 4 Time 80 180 available in hours) etx be the numberof toys of type A and y be the number of toys of type B produced per week, Profit on one toy of type 4 = Rs. 3 Profit on x toys of type A = Rs. 3x Profit on one toy of type B = Rs. 4 Profit one ¥ toys of type B = Rs. 4y Let Z be the weekly profit Then the weekly profit in Rs. is Z=3rt4y 1496Linear Programming 1497 Here, Z is known as objective function which has to maximize/minimize. One toy of type A on moulding requires = 4 hours, > toys of type A on moulding requires = 4x hours One toy of type B on moulding requires = 3 hours » toys of type B on moulding requires = 3y hours ‘On moulding total time required = 4x + 3y hours But moulder works for only 80 hours in a week. So, 4x + 3y hours cannot exceed 80 hours. > 4x43 $80 This is known as first constraint: One toy of type 4 on polishing requires = 2 hours .« toys of type A on polishing requires = 2x hours One toy of type B on polishing requires = 5 hours » toys of type B on polishing requites = Sy hours ‘On polishing total time required = 2x + Sy hours But polisher works for only 180 hours in a week. So, 2x + Sy hours cannot exceed 180 hours > 2x+5y'< 180 This is known as second constraint. Since, the number of toys produced is non-negative > x20 and y20 This is known as third constraint. Under these three constraints (conditions) we have to plan the system to get the maximum profit. "Now, we summarize the above informations in mathematical form as follows Tomaximize — Z= 3x + dy w Subject to the constraints 4x+3ys80 @ 2x+Sy<180 6) x20) za ® ‘The above mathematical expression is known as mathematical formulation. From the above inequations we find out the values of x and y. ‘The values of x and y’ are substituted in the objective function Z = 3x + 4y. ‘The maximun/minimum value of the objective function is known as optimal value. 56.2. SOME DEFINITIONS 1. Linear Programming Problem Here, we have to optimize the linear function Z subject to certain conditions. Such problems are called linear programming problems. As example 1 on page 613. 2. Objective functions Objective function is a linear function of several variables, subject to the conditions that Z= 3x + 4y in the previous example. 3. Optimal Value Optimal value is a maximum or minimum value of a objective function to be calculated in a linear programming problem,1498 Higher Engineering Mathematics 4. Non-negative Constants Production of any item is always non-negative, so we write x20, y20. 5, Linear Relations All the mathematical relations used in L.PP. are linear relations 6, Programming Programming is the method of determining a particular programme. in Variables Decision variables are x and y which denote the required number of items/products 8. Constraints Constraints are linear inequalities or equations involved in linear programming problem. In the previous example (2), (3), (4) are constraints, 9. Optimization Problem Optimization problem is a problem in which a objective function is to be maximize or ‘minimize subject to the certain conditions. Inthe previous example we have to maxmize the profit, so it is optimization problem. 56.3. MATHEMATICAL FORMULATION OF LINEAR PROGRAMMING PROBLEMS In the previous section we have defined certain technical terms of L.PP. Conversion of the verbal description of L.PP. into algebraic equations/inequations is known us Mathematical Formuton. Working Rule to formulate the L.P. Step 1. Identify the decision variables to be determined and expressed them as x, y ete. ‘Step 2. Identify all the limitations or constraints inthe given problem and then express them as linear inequalities or equations in terms of x,y ete. ‘Step 3. Identify the objective function (Z) which is to optimize (maximize or minimize) and express Z in terms of x, »: Procedure: ‘The solution of the given L.PP. should be divided under the following heads: 1, Preparation of table of information. 2. Write down the decision variables. 3. Form the objective function 4. Write down the constraints. 5. Write down Mathematical Formulation, TYPE 1, TO MAXIMIZE OBJECTIVE FUNCTION Example 2. A company produces two types of ornaments A and B that require gold and silver: Each unit of type A requires 1 gram of silver and 2 grams of gold. Type B requires (each unit) 2 grams of silver and I gram of gold. The company has only 100 grams of silver ‘and 80 grams of gold. Each unit of type A brings a profit of Rs. 500 and each unit of type B brings a profit of Rs. 400. Formulate the problem as a linear programming problem to ‘maximize the profit. Solution. The above information is given in the following table: 1. Table: Metal] Silver Gold | Profit Ornaments an grams) | (in grams) |_ (in Rs) 1 2 500 B 2 1 400 100 30 2. Decision variables. Decision variables are ornaments and B. Let the number of ornaments 4 be x and the mumber of ornaments B be y.Linear Programming 3. Objective function. To maximize profit Let Z be the objective function. Profit of each unit of type 4 = Rs. 500 Profit of x units of type 4 = Rs. 500 x Profit of each unit of type B = Rs. 400 Profit of y units of type B = Rs. 400 y Total profit = 500 x + 400 y > 500 x + 400 y 4. Constraint. () Company has only 100 grams of silver. ‘One unit of ornament A requires 1 gram of silver. x units of ornament A require x grams of silver. ‘One unit of ornament B requires 2 grams of silver. .) units of ornament B require 2y grams of silver. “Total available quantity of silver for ornament A and B = 100 grams > x+2y < 100 Constraint. (ii) Company has only 80 grams of gold. One unit of ornament A requires 2 grams of gold, x units of omament 4 require 2x grams of gold. ‘One unit of ornament B requires 1 gram of gold. .) units of ornament B require y grams of gold, Total available quantity of gold = 80 grams = 2x+y<80 1499 Constraint. (ii) Production of ormament 4 and omament B cannot be negative. = x20 and y20 ‘5. Mathematical Formulation, Hence, the linear programming problem for the given prob- lem is as follows Maximize Z= 500 x + 400» Subject to the constraints: x+2y100 2x+y<80 x20 p20 a @) @) a) (5) Ans. Example 3. Two tailors A and B earn Rs, 150 and Rs. 200 per day respectively. A can stitch 6 shirts and 4 pants per day while B can stitch 10 shirts and 4 pants per day. Form a linear ‘programming problem to minimise the labour cost to produce at least 60 shirts and 32 pants. [CBSE 2005} Solution, The given data can be putin the tabular form a: 1, Tab: Earning per day | Re 130 per day_[ Rs 200 par day Tailors Minimum requirement Stitch A B Shins 6 10 oo Pants z + 32 2. Decision Variable. Let the tailors A and B work for x and y days respectively. 3. Objective function. The total labour cost for working x days of tailor A and y days of tailor B is Rs, (150x + 2003).1500 Higher Engineering Mathematics Let Z denote the minimum labour cost, then Z= 150% + 200 y 4. Constraint (/), The minimum requirement of shirt is 60, Tailor A stitches in one day =6 shirts Tailor A stitches in x days = 6x shirts Tailor B stitches in one day = 10 shirts Tailor B stitches in y days = 10y shirts : 6x +10) 260 Constraint (i). The minimum requirement of pants is 32. Tailor 4 stitches in one day = 4 pants Tailor A stitches in x days = 4 x pants Tailor B stitches in one day=4 pants Tailor B stitches in y days = 4y pants = Ax tdy 232, Constraint (i), The number of days worked by A or B is non negative. x20 and p20. ‘5. Mathematical formulation. ‘The mathematical formulation of given L.PP. is as follows: Minimize Z = 150x + 200) 0 subject to the constraints: 6x +10) 260 @) Axt+4y232 @) and x y20. ® Ans. Example 4. 4 manufacturer of leather belts makes three wpes of belts A, B and C which are processed on three machines M, , M, and M,, Belt A requires 2 hours on machine M, and 3 hours on machine M, Belt B requires 3 hours on machine M,, 2 hours on machine M, and 2 hours on machine M, and belt C requires 5 hours on machine Mz and 4 hours ‘on machine M,. There are 8 hours of time per day available on machine M,, 10 hours of time per day available on machine M, and 15 hours of time per day available on machine M, The profit gained from belt A is Rs. 3.00 per unit, from belt B is Rs, 5.00 per unit and from belt C is Rs, 4.00 per unit. Formulate the LPP. to maximize the profit. Solution. The above information is given in the following Table: 1, Table: Lachines M, wy M, Profit Bets fin hours) | _ (in hours) (in hours) fin Rs) 4 2 oO 3 3 B 3 2 2 5 c 0 3 4 4 “Available time 8 10 15 (in hours) 2. Decision Variables. The decision variables are the number of belt A, belt B and belt C. Let the number of belt 4 be x,, the number of belt B be x,, and the number of belt C be x, 3. Objective Function. To maximise the profit. Profit on 1 belt A= Rs. 3 Profit on x, belis = Rs. 3 x, Profit on 1 belt B = Rs. $ Profit on x, belts B = Rs. Sx, Profit on 1 belt C= Rs. 4 Profit on x, belis C= Rs. 4x, Total profit = 3x, + Sx, + 4x, = Zt Sy t dy,Linear Programming 4. Constraint (The time available on machine M, = 8 hours per day ime requited for 1 belt A on machine M, = 2 hours per day ‘Time required for x, belts 4 on machine M, = 2x, hours per day Time required for 1 belt B on machine M, = 3 hours per day Time required for x, belts B on machine M, = 3x, hours per day 2x, +3y, $8 int (i) The time available on machine M, = 10 hours per day. Time required for 1 belt B on machine M, = 2 hours per day Time required for x, belts B on machine M, = 2x, hours day ‘Time required for 1 belt C on machine M, = $ hours per day ‘Time required for x, belts C on machine Vf, = Sx, hours per day 2m +5m <10 Constraint (ii) The time available on machine M, ‘Time required for 1 belt A on machine M, ‘Time required for x, belts A on machine M, ‘Time required for 1 belt B on machine M, ime required for x, belts B on machine M. ‘Time required for I belt C on machine M, ‘Time required for x, belts C on machine M, 3y t2x +4 S15 Constraint iv). The number of belt A, belt B and belt C are non-negative. Const = 15 hour per dy 3 hours per day }, hours per day 2 hours per day = 2x, hours per day “4 hous per day 4a, hours per day and, 20 5. Mathem: The linear programming problem of the given problem is as follows To maximise Z =3y, +5x, +4x, Subject to the constraints 2x +3x; $8 2x, +5x5 $10 3x +2x, 44x <15 x20 20 20 TYPE Il, DIET PROBLEMS 1501 <) Q) 3) (a) (3) ©) a) Ans. Example 5. A dietician mixes together two kinds of food, say, X and ¥ in such a way that the mixture contains at least 6 units of vitamin A, 7 units of vitamin B, 12 units of vitamin C and 9 units of vitamin D. The vitamin contents of 1 kg of food X and 1 kg of food ¥ are given below: “8 Tar Tra Tea] 4 B ¢ D Food X T 7 T Zz Food ¥ Zi 7 3 T Tie Kg of Joos X costs RS-5, whereas one Keg of food ¥ costs RS. S. Formalare the linear programming problem.1502 Higher Engineering Mathematics Solution. 1. Decision Variables. Decision Variables are units of food X and food Y. Let food in the mixture be x kg. and food ¥ in the mixture be y kg, 2. Objective Function. To minimise the cost 1 kg of food costs Rs. 5 x kg of food costs Rs. Sx 1 kg of food Y costs Rs. & y kg of food Y costs Rs. Total cost of food X and Y = Z=Sx+8y 3. Constraint (i) The mixture contains atleast 6 units of vitamin 4. 1 kg of food. contains 1 unit of vitamin A. x kg of food contains x units of vitamin A. 1 kg of food ¥ contains 1 unit of vitamin A. Jy kg of food ¥ contains 2y units of vitamin A. > x+2y26 Constraint (/) The mixture contains atleast 7 units of vitamin B, 1 kg of food contains 1 unit of vitamin B. x kg of food’ contains x units of vitamin B. 1 kg of food ¥ contains 1 unit of vitamin B. y kg of food ¥ contains y units of vitamin B, = xtye7 Constraint (i) The mixture contains at least 12 units of vitamin C. 1 kg of food contains 1 unit of vitamin C. x kg of food X contains x units of vitamin C. 1 kg of food ¥ contains 3 units of vitamin C. y kg of food ¥ contains 3y units of vitamin C. => xt3y212 Constraint (i) The mixture contains atleast 9 units of vitamin D, 1 kg of food contains 2 units of vitamin D. x kg of food X contains 2x units of vitamin D. 1 kg of food ¥ contains 1 unit of vitamin D. 2 kg of food ¥ contains y units of vitamin D. > wt y29 Constraint (»). The number of kg of food x and y is non-negative. 20 y20 4 Mathematical Formulation, The linear programming problem ofthe given problem i a, To minimise Sr +8) a Subject to the constraints x+2y26 Q) xtye7 @) x43y212 a) axty29 ro) x20 GO) y20 co) Ans.Linear Programming 1503 Example 6. A firm is engaged in breeding goats. The goats are fed on various products grown on the farm. They need certain nutrients, named as X, Y, and Z. The goats are fed ‘on two products A and B. One unit of product A contains 36 units of X, 3 units of ¥ and 20 units of Z, while one unit of product B contains 6 units of X, 12 units of ¥ and 10 units of Z. The minimum requirement of X, ¥ and Z is 108 units, 36 units and 100 units, respec tively. Product A costs Rs, 20 per unit and product B costs Rs. 40 per unit. Formulate the L.PP. to minimize the cost. Solution. The above information is give in the following table’ 1. Table: Nuirienis] Y Cost Food (in Rs) 7 36 3 20 20 B 6 2 10 40 Minimum required units 108 36 100 2. Decision variables. The decision variables are units of nutienis X, Y and Z. Let the units of food A be x the units of food B be y. 3. Objective function. To minimize the cost. cost of I unit of food A = Rs. 20 cost of x units of food A = Rs. 20 x cost of 1 unit of food B = Rs. 40 cost of y units of food B = Rs. 40 y Total cost = 20 x + 40 y > Z=0x+40y 4. Constraint (). Minimum requirement of nutrient = 108 units One unit of food 4 contains 36 units of X units of food A contains 36 x units of X. (One unit of food contains 6 units of ¥. Y units of food B contains 6y units of = 36x+6y2108 Constraint (i), The minimum requirement of Y nutrient One unit of food 4 contains 3 units of nutrients 7. > units of food 4 contains 3x units of nutrients ¥. ‘One unit of food B contains 12 units of nutrients ¥. y units of food B contains 12y units of mutrients ¥ > 3e+12y236 Constraint Gi). The minimum requirement of nutrients Z = 100 units ‘One unit of food A contains 20 units of nutrients Z. x units of food A contains 20 x units of nutrients Z. ‘One unit of food B contains 10 units of mutrients Z y units of food B contains 10 y units of nutrients Z. > 20x +10y 2 100 Constraint (iv). Units of food 4 and B are non-negative x20 and y20 4. Mathematical Formulation, To minimize, Z= 20x + 40y Suibject to the constraints: 36x-+6y 2 108 Se412y236 20x +10y> 100 x20, 920, 36 units,1504 Higher Engineering Mathematics TYPE Ill. TRANSPORTATION PROBLEM Example 7. There is a factory located at each of the two places P and Q. From these locations, a certain commodity is delivered 10 each of the three depots situated at A, B, and C. The weekly requirements of the depots are respectively 5, 5 and 4 units of the commodity while the production capacity of the factories at P and Q are 8 and 6 units respectively just sufficient for the requirement of depots. The cost of transportation ‘per unit is given below: To | Cast an Rey From A B c P 16 10 15 Q 10 2 10 How many units skauld be wansported Jrom each factory to each dapol i order that the transportation cost is minimum. Formulate the above as a linear programming problem. Solution. The given information is shown in the following figure po 3: SX we te ®& ye Roy zg i y Fecioy @ 1, Decision Variables, Decision variables are units of commodity to be transported from the factories to the depots. Let the factory at P transport x units of commodity to depot at A and y units to depot at B 0 the remaining units at P, 8 - (x + y) will be transported to depot at C. 2. Constraint (). From Factory at P, (8 ~ x - y) units will be transported to the depot at C. B-x-y20 xt ys8 o Constraint (i). x and y units are non-negative units x20 2 y20 @ Constraints (ii), ‘The remaining requirements (5 — x) units are 10 be transported from the factory at Q to the depot at. 5x20 > x5 o Constraints (7). ‘The remaining requirements (5 — y) units are to be transported from factory Q to the depot at B. S-y20 > ys5 ©Linear Programming Constraints (). 1505 ‘The remaining requirements 4 — (5 — x + 5 y) units of commodity will be transported from the factory at Q to the depot at C. 4-6-x+5-y20 = xty-420 = xtyed © Objective function. The transportation cost from the factory at P to the depots at 4, B and. C are respectively Rs. 16 x, 10 y and 15 (8 ~~») ‘otal cost of transportation from factory at P = 16x + Loy + 15 (8 ~ x3). Similarly, the transportation cost from the factory at Q to the depots at 1, B and C are Rs. 10(5—x), 12 (5—y),10(x+y—4) respectively ‘Total transportation cost from factory Q 105-2 +12(5-y)+10 (e+ y-4) Grand total cost of transportation from both the factories at P and Q to all the depots > x-Ty+190 Mathematical Formulation. To minimize Z=x-Ty+ 190 Subject to constraints xtys8 xtyed x5 yss 20 y20 EXERCISE 56.1 [A furniture dealer deals in only two items vi, tables and chairs. He has Rs. 11,000 to invest and a space to store at most 40 pieces. A table costs him Rs. $00 and a chair Rs. 200. He ean sella lable ata profit of Rs. 50 and a chair at profit of Rs. 15, ‘Assume that he can sell all the items that he buys. Formulate this problem as an LPP, so that he ean maximize the profit [A manufacturer produces nuts and bolts for industrial machinery Tetakes | hour of work on machine and 3 hours on machine Bio produce a package of nuts, while it takes 3 hours on machine A and | hour on machine B to produce a package of bolts. He ‘cams a profit of Rs. 2.50 per package on nuts and Re. 1 per package on bolts. Form a linear programming problem to maximize his profit, if he operates each machine for atthe most 12 hours a day. A. person consumes two types of food, A and B, everday to ‘bain & units of protein, 12 units of carbohydrates and 9 units ‘of fat whichis his daily minimum requirements. 1 kg of food A ‘contains 2, 6, 1 units of protein, carbohydrates and fat respoc- tively. 1 kg of food B contains 1, 1 and 3 units of protein, carbohydrates and fat, respectively: Food 4 costs Rs, 8 per kg ‘while food B costs Rs. 5 per kg. Form an LPP to find how many kg of each food should he buy daily to minimize his cost of food ‘and sill meet minimal nutitional requirements, 16x +10 y+15 (@—x—y) +10 (S—x) +12 (Sy) +10 (r+ y—4) Ans. ‘Ans. Maximize, Z ~ 50x + 15y Subject to the constraints x+y s40 500x + 200) < 11000 x20 y20 ‘Ans, Maximize, Z = 25x * y Subject 1© the constrats x+3ys12 Br+ysl2 x20 y20 Ans. Minimize Z = Sx + 8y Subject to the constraints Drty28 xt y22 4329 x20 y201506 4 56.4 Higher Engineering Mathematics A dietician wishes to mix two types of foods F and F; in 90h Ans, Minimize z= S0x+75y 4a tal the amin contents of he mist Contin alent AMY EIDINS 4 OU TY ‘units of vitamin A and 8 units of vitamin B. Food F, contains 2 unitskg of vitamin A and 3 unitskg of vitamin B while food F, 2e43y26 contains 3 unitskg of vitamin A and 4 unitskg of vitamin B. Food F costs Rs. SOkg and food F, costs Rs. kp. Formule oats the problem as a LPP to minimize the cost of mixture x20, y20 Cnvestment Problem) A ried person want invest an amount os of upto Rs, 20,000, His broker recommends investing in two AM Minimize 7 = "0.4 1S types of bonds A and B, bond A yielding 10% retum on the 100" “100 {mount invested and bond B viding 15% retum on the amount 2 5000 invete After some combeation, he dies to det at oat Rs, 5000 in bond A and no more than Rs. 8000 in bond B. He $80,000 also want fo ives at last as mh in bond 4 as in bond B. What x20,y20 should his broker suggest if he wants to maximize his return on investments. Formulate LPP. GRAPHICAL METHOD OF SOLVING LINEAR PROGRAMMING PROBLEMS Ifa problem contains only two variables then we can solve the given problem by graphical ‘method. There are two graphical method to solve a linear programming problem, 1, Comer point method 2. Is0-profit or iso-cost method CORNER POINT METHOD This method is based on the fundamental extreme point theorem, In previous class we have learnt how to formulate a system of linear inequalities involving ‘two variables x and y mathematically, Working Rule ‘Step 1. Formulate the given L.PP. in mathematical form, ‘Step 2. The inequations are converted into equations. In the equation on putting y = 0 we get x-coordinate on x-axis. Similarly, putting x = 0 we get y-coordinate on y-axis, Join these two points to get the graph of the equation. ‘Step 3. The inequation of a line divides the plane into two half planes, 10 choose the plane of the inequation we put x= 0 and y = 0 in the inequation. If origin satisfies the inequation then the region containing the origin is the region represented by the given inequation. Otherwise the half plane not containing the origin is the region represented by the given inequation. ‘Step 4, The region satisfying all the inequations is the feasible region. Step 5. The vertices (comer points) of the required region are known as extreme points of the set ofall feasible solutions of the L.PP. ‘Step 6. By putting the values of x and y of each corner point in the objective function we get the values of the objective function at each of the vertices of the feasible region. Out of all the values of the objective function, we get a point at which the objective function is ‘optimum (maximum or minimum), Consider the following example:~ Example 8 Solve the following LPP. graphically Maximize Z= x+y Subject to the constraints x+2y <10 arty sI3 x20 y20Linear Programming 1507 Solution. On changing the given inequations into equations, we have x+2y=10 and 3x+y=15, x=0 and yO Region Represented by x+2y 10. The line x-+2y=10 meets the x-axis at the point 4(10, 0) and meets y-axis at the point (©, 5), Join AB to obtain the graph of x+2y = 10 Here, origin (v= 0, y=0) satisfies the inequation x+2y'<10. So, the half plane containing the origin represents the solution set of the inequation x+2y $10, Region Represented by 3x+y<15. The line 3x+y=15 meets the x-axis at the point C (5, 0) and meets the y-axis at the point D (0,15). Join CD to obtain the graph of the line 3x+=15. Here, origin (x=0, y=0) satisfies the inequation 3x+y-<15. So, the half plane containing the origin represents the solution set of the inequation 3x+y<15, Region represented by x20 and y20. All the points inthe first quadrant satisfies > 0 and y20. So, the first quadrant is the region repre- sented by x20 and y20. The shaded region O C £ BO represents the region satisfying all the inequations. Each point of this region represents a feasible choice Every point of this region is called the feasible solution of the problem, Feasible region. The shaded portion determined by all the constraints including non-negative constants ofa linear programming problem is called the feasible region. In this example O BEC (shaded) is the feasible region for the problem. Feasible Solution. Points within and on the boundary of the feasible region represent feasible solutions of the constraints Here, (5, 0), (4, 3) and (0, 5) are the feasible solutions. Any point outside the feasible region is called an infeasible solution. For example, (0, 15) and (10, 0) are infeasible solutions. Optimal Solution. Any point in the feasible region that gives the optimal value (maximum (or minimum) is called an optimal solution. In the feasible region there are infinitely many points which satisfy all the constraints. It is ‘not possible to check all the points for the maximum value of the objective function, Z=3x+2y For finding out the optimal solution we have to use the following theorems Theorem 1, The optimal value of objective function must occur at a corner point (vertex) of the feasible region. Theorem 2. If the feasible region is bounded then the objective function Z has both ‘maximum and minimum values on corner points of the bounded region. Inthe above example we have following table showing the value of the objective function at the comer points ofthe feasible region.1508 Higher Engineering Mathematics Tertex of the feasible region Corresponding value of Z ~ 3x + 2y (in Rs) 00.0) 0 €6.0) 15 E@.3) 18 Maximum Ley Cd —“—tSC SSSC*izrS We observe that the maximum value of the objective function is 18. This method of solving linear programming problem is called comer point method. Procedure: The solution of the given L.PP. should be divided under the following heads: 1, Conversion of inequalities into equations, 2. Draw the graph of the lines and find regions represented by the inequations. 3. Apply Comer point method. Example 9. Soive the following linear programming problem graphically Minimize =~ 3x+4y Subject to xt2y<8 3x42y<12 x20, y20. Solution. We have, Minimize Z=-3x+4y ay Subject to the constraints: x42ys8 Q) 3x+2y<12 @) #20, 20 a) 1. Conversion Changing the inequations into equations, we have xt2y=8 3x4 2y= 12 x=0,y=0 2. Drawing of Graphs of the lines: Region represented by x+2y <8 xt2y=8 ¥ = a 0 4 A B On joining A and B, we get the graph of the equation x + 2y = 8, Put x=0, y=0in x+2y:<8, then 0+0<8, which is true. So the half plane containing ‘origin represents the solution set of the inequation x+2y <8. Region represented by 3x+2y<12. 3+ 2y= 12 7 a 0 6 c DLinear Programming 1509 ‘On joining the points Cand D, we get the graph of the equation 3x + 2y = 12. Put x= 0, y=0 in the inequation 3x+2y'<12, then 0.40<12 which is tre. So, the half plane containing origin represents the solution set of the inequation 3x+2y-<12. Region represented by x>0 and y20. First quadrant is the region of x20, y20 ‘The shaded region in figure is the feasible region OC E B determined by the system of con straints (2) to (4), which is bounded, The coor- dinates of comer points are C(4, 0), EQ, 3) and D (0, 4. 3. Corner Point Method Now we evaluate Z = ~3x + dy at these comer point, Corner Point of | Corresponding value of the feasible = 3e+4y region OCEBO Ca.) 3) + HO) = — 12 Minimum £@3) =3Q) + 4G)= 6 2O.d =30) +4) = 16 Hence, the minimum value of Z is ~I2 attained at the point C (@, 0) Ans. Example 10. Solve the following linear programming problem graphically: Maximise Z=Se+3y subject 10 3e4SysI5 Sr+2ysl0 20,920, Solution. We have, Maximise Z = Se + 3y subject to the constraints ar+Sysis ) Se+2ys10 @) 20,20. GB) 1. Conversion ‘On converting the above inequations, we have the following equations: Bx + Sy = 15 Sx +2y= 10 x=0,y=0 2. Drawing of the graph of the lines. Region represented by the inequation 3x+5y <15, B+ Sy= 15 3 a > 0 7 a B The line 3x +5y = 15 meets the x-axis at 4G, 0) and meets y-axis at B (0, 3). On joining A, B- we get the graph of the line 3x+5y=15, Since (0, 0) satisfies the inequation1510 Higher Engineering Mathematics 3x4+5y $15. So, the half plane containing origin represents the region of the solution set of the inequation 3x+5y <15, ‘The region represented by Sx+2y <10, 5x +2y = 10 = 2 o 0 5 Gi D. The line Sx + 2y = 10 meets the x-axis at C @, 0) and ects y-axis at D (0,5). On joining C, D we get the graph of the line Se + 2y = 10, Since (0, 0) satisfies the inequation Sx+2y$10. So the half plane containing origin represents the region of the solution set of the inequation Sx+2y< 10. ‘The region represented by x20 and y>0. x20 and y20 represent the frst quadrant. The shaded region OCEBO bounded by the inequations (1) to @) is the = ¥ feasible region. 3. Corner Point Method. The coordinates of the vertices 0, C, E, and B of the feasible region OCEBO ate O (0, 0), C 2, 0), # 20/9, 45/19) and B (0, 3) respectively. Note that the coordinates of F are obtained by solving the equations 3x + Sy = 15 and Sx +2y= 10. The value ofthe objective function at these points are given in the following table: Corner pornt (3) Talue of the objective function of the feasible region OCEBO_|_Z= Sx + 3y 00.9 500) + 30) = 0 C20 3@) ¥ 30) = 10 =(2°) .3(43) 235 E Q0/19, 45/19) Sto} *3U9) = a9 fay hag maim B03) 3Q+3@=9 5 J” = 7p isthe optimal solution 20 Clearly 2 is maximum when *= +5 of the given LPP. Example 11. Solve graphically the following linear programming problem to minimise the cost Z = 3x + 2y subject t0 the following constraints Sety210; xty26; xe4y212; xB0,y20 Solution. We have, Minimise Z= 3x +2y w Sulbject to the constraints Se+y210 ® x+y26 0) reay2I2 ® x20, y20 6)Linear Programming 1511 1, Conversion. On converting the above inequations, we have the following equations Sety ety 2. Drawing of graphs. The region represented by Sx+y 210. Sety= 10 ¥ 2 0 Y 0 10 Point A B On joining the points 4 and B, we get the graph of the line Sx + y = 10, Put x=0, y= 0 in Sx+y210, then 040210 which is false, So half plane not containing origin represents the region of the solution set of the inequation Sx +y 210. ‘The region represented by x+y 26 xhy=6 ¥ e a y 0 6 Point a D ‘On joining the points C and D, we get the graph of the line x+y = 6. Putx=0,y=0in x+y26, then 04026 which is false, So the half plane not containing origin represents the region of the solution set of x+y 26. The region represented by x+4y 212 xhay= 12 2 0 0 3 Point E E On joining the points # and F we get the graph of the line x + 4y Puty=0, y= 0 in x+4y212, then 0+0>12 which is false. So, the haif plane not containing origin represents the region of the solution set of the inequation x+4y2 12. ‘The region represented by x>0 and y2>0. The first quadrant is represented by x20 and y=0. The shaded region is represented by the inequations (2) to (5), 3. Corner Point Method. The coordinates of the vertices of the feasible region are F (12, 0), G (4, 2), H (1, 5) and B (0, 10) respectively: Note that the coordinates of G and Hare obtained by solving the equations x + y xt4y= and x + y= 6, Sx+ y= 10 respectively, 12.1512 Higher Engineering Mathematics The value of the objective function at these points are given in the following table Comer Point (, 9) of the Talue of the objective finetion feasible region EGHB Z= 3x +d (2,0) 3x 2+2*0=36 GED Feded<2=RTI= 16 HA, 3) 3e1F2%35=3F10=1 B, (0, 10) 3e0F2"10=0720=20 Clearly, H is pimum when x= 1, y= 5. So, x = 1, y = 5 is the optimal solution of the given L.PP. Hence, 2 i minimum when x= 1 and y= $ andthe minimum valve of 2 is Rs. 13 56.6. ISO-PROFIT OR ISO-COST METHOD (MAXIMUM Z) Let Z= 31 + 2y be the objective faction ’ On putting any value of Z (say 12) in z= 3042, we have a= 34429 @ and draw the corresponding line of the objective function, This line is called. Is0-profit_ or Isosot line, since every point on this line will give the same value of Z (12) (same profit or same cos), Draw cone more line parallel to (1), within the feasible region and passing through the farthest point from the origin. "The value of the Z onthe second line isthe mai num vale of the Z. It pases through one comer ofthe Shaded region ‘Through the point £ (2, 8), the line of objective function is passing. The point / is on the shaded region and is vertex of the shaded region and the line Z=3x+ = 9 2y is farthest rom te org. Here the maximum value of Z=3 (2) + 2 (8) = 6 + 16 = 22. So, the maximum value of the objective function is 22. 56.7 ISO-PROFIT OR ISO-COST METHOD (MINIMUM Z) Let Z= 2+ 2y Let us take tree diferent vales of Z; ZZ, and Z, we ge, +3 o +2y -Q) axe ® ‘The above thee lines are parallel to (10,0) x ; eeter agi neage(-!} 009 Out of these three lines, line (2) is the >, ‘only line which passes through the point (4, 2) nearest to the origin and passing, through the feasible region. Thus, Z, isthe minimum value of Z. x=4 and y=? gives the optimal solu- tion. 442Q)=444=8 So, the minimum value of Z is 8.Linear Programming 1513 Example 12. Solve graphically the following linear programming problem: ‘maximize Z=se+5y subject (0 the constraints w+ ys300 Ie+y 360 x20 y20 Solution, We have, Maximum 2 Set3y o Subject to the constraints x+ys300 @ det y $360 @ x20 and y20 ® 1. Conversion ‘On changing the inequations into equations we get the following equations. xty=300 and Ox +y= 360 2 Drawing of graphs The region represented by x+y < 300 xt y= 300 ¥ 300) a y 0 300 Point a On joining the poinls A GO0, 0) and BO, 300) we get the graph of the line AB, x ty = 300, Put x= 0, y=0 in x+y<300, then 040300, which is true. The half plane containing. the origin is the region of the solution set of the inequation x+y < 300. ‘The region represented by 2x+y-< 360. 2x + y = 360 ¥ 180 0 y 0 360 Point ic D On joining the points C (180, 0) and D (0, 360) we get the graph of the line 2x + y= 360, Putx=0,y=0in 2x+y-<360, then 0+0< 360, which is ruc, The half plane containing the origin is the region of the solution set of the inequation, (0.900 2x+y 5360, ‘The region represented by x>0 and y20. The first quadrant is represented by x20, and ye. The shaded region OCEB is the feasible solution bounded by the inequations (2) to (4. ‘On solving the equations (2) and (3), we get the x oint of intersection F (60, 240) fo 120 tp bao, s09 0 e ae “118, 0/"°a 80.0)1514 Higher Engineering Mathematics The coordinates ofthe comer points of the feasible region are C (180, 0), (60, 240) and BO, 300). 3. Iso-profit or Iso-cost Method. Now, we take a constant value (say 300) ie, (20 times the Le.m. of 5 and 3). On putting Z = 300 in objective function (1), we get 300 = Sx+ 39. (S) We draw the graph of the line + 4y = 300, Draw one more line parallel to (5) which is the farthest from the origin and has atleast one point of the feasible region. ‘The parallel line to (5) passes through the farthest point E (60, 240) from the origin, Here, x= 60 and y = 240 will give the maximum value of Z, ‘The maximum value of Z is given by Z = 5 (60) + 3 (240) = 300 + 720 = 1020. Hence, the maximum value of Z is 1020. Ans, Example 13, Solve graphically the following LP-P. ‘Minimize Za set ay subject to the constraints 80x-+100y2 88 4084309236 x20,y20 Solution. We have, Minimize Za set dy Od Subject to the constraints 80x+100y 288 -Q) 40x+30) 236 @) x20,y20 @ 1. Conversion ‘On converting the inequations into equations, we get 80x + 100y = 88 2. Drawing of graphs Region represented by 80x +100) > 88. 80 x + 100 y= 88 = i 00) » 0 083 Point 4 B On joining the points 4 (1.1, 0) and B (0.0, 0.83) we get the graph of the line 80x + 100y = 88. Put x = 0, y= 0 in the inequation 80x-+100y> 88 then 0+0>88, which is false. So, the half plane not containing the origin is the region of solution set of the inequation 80x+100y 2 88 Region represented by 40x+30) 236. 40x + 30y = 36 ¥ O91 a y 0 Lit Point c DLinear Programming 1515 On joining the points C (0.91, 0) and D (, y 1.14), we get the graph of the line 40x + 30y = 3 Put x = 0, y = 0 in the inequation 40x+30y> 36, then 0+0236, which is false So, the half plane not containing the origin is the region of solution sct of the inequation 40x-+30y 2 36, ‘The region represented by x20 and y>0 00 1.14) The first quadrant is represented by s x20and y20, ©.0.83) The shaded region AED represents the fea- sible solution bounded by the inequations (2) to (4). On solving (2) and (3), we get the point of intersection of the lines (2) and (3), V0.0) E06, 04). ¥ 1 3. Iso-profit or Iso-cost Method Now, we take a constant = 20 On putting Z = 20 in (1), we get Sx + dy Now, we draw the graph of the line Sx + 4y Draw one more line parallel to (5), which is the nearest from the origin and has at least one point of the feasible region. The parallel line to (5) passes through the nearest point £ (0.6, 0.4) from the origin. Here, x= 0.6 and y= 0.4 will give the minimum value of Z. The minimum value of Z is given by 3) Z= 50.6) +404) = 30416 = 46 ‘Ans. Hence, the minimum value of Z is 4.6. EXERCISE 56.2 Solve graphically each of the following linear programming problems : 1. Maximize Z = 10x + 6y subject to the | 4. Maximize Z ~ 4x + 9y subject to the con- constraints straints axtysi2 x45y<200 aes 3ys 134 2e+Sys34 ae 20, y20 x20,y20 ‘Ans, Maximum : 382; x= 10, y= 38 ‘Ans, Maximum: 56,x=2,9=6 | 5. Maximize Z~ 5x + 1y 2. Maximize Z =60x+15y subject to the subject to the constraints constants xeysd xtys50 Sxs8y 524 3e4y590 lor+7ys35 so ye ny20 *20,920 mn ‘Ans. Maximum : 1650, x ~ 20, y ~ 30 ‘Ans. Maximum Z == 3 Mrimize 2-18 1p set © ihe 5% | Nerimie 2 = a + 2p despo20 sujest tthe contents eye: xty28 tie eee 3x+Sysi5 ¥20,y20 x20,920 ‘Ans. Minimum : 134; x ‘Ans. No feasible region1516 Higher Engineering Mathematics 1. Minimize Z = 3x + Sy 10, Minimize Z = x ~ Sy + 20 subject to the constraints sujet to the constraints x3y23 xoy20 eye? mx+2y22 . x23 xy20 yea x ye0 inimum Z = 7, ny Ans Mi ‘Ans. Minimum Z = 4, x= 4, y= 4 8. Minimize Z 20x + 10y Find x and y for which 3x + 2y fs minimum sub- subject to the constraints ject to these inequalities. Use « graphical method. x2ys40 11, Find the minimum value of 3x ~ Sy subject to the constraints: axty230 ts . Ans. Minimum Z = 200, x = 10, y= 0 BLS ERED 9. Minimize Z = 30 x +20 y x-2ys2, x20,y20 subject to the constants Ans. Minimum Z ~~ 300, x~ 6, y= 0 reyes 12, Find the maximum vale of 2 y subject to < the constrains weay2l2 we3y26, x-3ys3, Srtdys24 my20 Br+2y <6, Se+y25, xy20 ‘Ans. Minimum Z = 60, x=0, y ‘Ans. Maximum Z = ‘56.8 SOLUTION OF LINEAR PROGRAMMING PROBLEMS Here we will solve the linear programming problems. Working Rule ‘Step 1. Define the problem mathematically. ‘Step 2. Graph the constraint inequalities by converting them into equations. Find out their respective intercept on both the axes and connect them by straight lines, ‘Step 3. Find out the vertices ofthe feasible region. ‘Step 4. Find out the value of the objective function on the vertices ‘Step 5. Find out the optimum value of the objective function. Procedure . The solution of the given LPP should be divided under the following heads: 1, Prepare a ‘able of the data given in the problem. 2, Write down the decision variables. 3. Fomm the objective function. 4, Write down the constraints. ‘5. Mathematical formulation, 6. Region represented by inequations. 7. Apply Comer point method/Iso-cost or iso-profit method, ‘Type I. To maximize the objective Function (Z) Example 14, Ifa young man rides his motor eyele at 25 km/hour he had to spend Rs. 2 per 4m on petrol. If he rides at a faster speed of 40 km /hour, the petrol cost increases at Rs. 5 per dm. He has Rs. 100 to spend on petrol and wishes fo find what is the maximum distance he can travel within one hour, express this as an LPP. and solve it graphically. Solution: The above information are given in the following table 1, Table 3N, Speeds Consumption of petrol | Toral amount Spent ham per hour) per km. ‘on petrol T 3 Rs2 Rs. 100, 2. 40 Rs. 5Linear Programming 1517 2, Decision Variables: Let the number of km riding motorcycle at the speed of 25k/h = x km. Let the number of km riding motor eycle at the speed of 40 knvhour = y km 3. Objective function To maximize the distance of the journey. Zaxty 4. Constraint (i). The young man has Rs. 100 to spend on petro. ‘When the speed is 25 knvhour cost of petrol for 1 km = Rs. 2 When the speed is 25 knvhour cost of petrol for x km = Rs, 2x When the speed is 40 knvhour cost of petrol for 1 km = Rs. 5 When the speed is 40 knvhour cost of petrol for y km = Rs. 5 y. 2x+5y 5100 Constraint (ii) Time = ‘Time taken in the first journey = Constraint (ii) The distances inthe joumey are non-negative. : x20 and y20 5, Mathematical Formulation To maximize, Zaxty o Subject o the constraints 2x+5y<100 @) Fete! = 8e+5ys 200 6) 320, y20. ® 6. Region represented by the contraints 2x Sy = 100 B+ 5y = 200 rT 0 [0 x] 35] 0 y[ 0] 20 y| 0 | Pom! a |B , Pom[ eT] We have drawn the graphs of the following lines Feasible region is represented by the shaded portion OCEBO. 7. Corner Point Method The coordinates of the vertices of feasible region OCEBO are O (0, 0), caso, 21518 Higher Engineering Mathematics ‘The values of the objective function at these points are as follows Corner Point (9) of Talue of the objective function the feasible region Z-xty OCEBO Maximum BO, 20) 0+ 20=20 40 Hence, Z= 30 is masimam when x=5° and y Ans, Example 15, 4 factory owner purchased two types of machines, A and B for his factory. The requirements and the limitations for the machines are as follows: Machine | Area occupied Labour force Daily output (in units) A 1000 m? 12 men 60 B 1200 m? 8 men 40 He has maximum area of 9000 m? available, and 72 skilled labourers who can operate both the machines. How many machines of each type should he buy to maximise the daily output ? Solution 1. Decision variables. Let x machines of type A and y machines of type B are bought to maximize the daily output. 2. Objective function. It is given that one machine of type A gives output 60 units so x ‘machines of type A give output 60x units, Similarly, y machines of type B give output 40y units. Total output = 60x + 40y = Z = 60x + 40y 3. Constraint () “* one machine of type A occupies 1000 m? area x machines of type A occupy 1000 x m? area and ~* one machine of type B occupies 1200 m* area -y machines of type B occupy 1200 y m? area Available area is 9000 m? 1000 x + 1200.» < 9000, Constraint (i) ‘one machine of type A can be operated by 12 men x machines of type A can be operated by 12 x men and one machine of type B can be operated by 8 men _y machines of type B can be operated by 8y men Total available labourers = 72. Dx+8ys 72,Linear Programming 1519 Constraint (ii). Number of machines cannot be negative. x20 and y20 4, Mathematical Formulation Thus the given LPP. is Maximize Z = 60x + 40y Subject to 1000 x + 1200 y < 9000 Dx+8y <2 x2 Oandy 20 5S, Region Represented by the inequations ° To solve this LPP. we draw the lines 1000 x + 1200 y = 9000... () cs 12x + 8y= 72 @ 7 x [27° ce Points | 4 | B x [6]0 y [oe |9 Points | © | D 5 ean x ‘The feasible region of the L.PP. is shaded in the adjoining figure. 6. Corner Point Method (On solving (1) and (2), we get the coordinates of E ( & ) ‘The coordinates of comer points are C (6, 0), D (0, 7.5) and e Now we evaluate Z = 60.x + 40 y at the comer points, Can pat Cpa C 6.0) Z = 60 (6) + 0 = 360 (2.2) 7 (2)o( =a tam £= 0 wavine wen = 4 =Oare= By = be Example 16. 4 dealer wishes to purchase a number of fans and sewing machines. He has ‘only Rs. 5,760 to invest and has space for at most 20 items. A fan and sewing ‘machine cost Rs. 360 and Rs. 240 respectively. He can sell a fan at a profit of Rs, 22 and sewing machine at a profit of Rs. 18, Assuming that he can sell whatever he buys, how should he invest his money in order to maximise his profit ? Translate the problem into LPP and solve it graphically,1520 Higher Engineering Mathematics Solution. The above information are given in the following table : 1. Table Items Cost (in Rs) |] Profit (im Rs) | Space for total number of lems Fan 360 2 Sewing machine 240 1g Total 5.760 20 2, Decision Variables. Let x and y be respectively the number of fans and sewing machines purchased, 3. Objective function. To maximize the profit Z=22x+18y 4. Constraint (i). The available space is for at most 20 items. x+ys20 Constraint (i). At most investments is Rs. 5,760. 360x+240y<5,760 = Sx F2y S48 Constraint (i) The numberof fans and sewing machines are non-negative x20 and y20. ‘5, Mathematical formulation. Maximize Z= 22x + 18y a Subject to the constraints x+ys20 @) 3x42y-<48 @ x20,y20 a 6, Region represented by x+y <20 and 3x+2y<48 xty=20 3r42y $48 ¥ 20 0 ¥ % 0 » 0 20 » aE Point | A B int c_[D 7. Corner Point Method The feasible region, OCEBO, is shaded. Here C (16, 0), EG, 12) and B (0, 20) are the comer points. Now the value of Z = 22x + 18y. Corner point (x, y) Value of the objective of the feasible region function Z = 22x + I8y OCEBO C06, 0) 22 (16) + 18 (0) = 352 E (12) 22.(8) + 18 (12) = 392 Maximum, BO, 20) 22 (0) + 18 (20) = 360 ‘Thus the profit will be maximum, when 8 fans and 12 sew- ing machines are purchased and sold. ‘Also the maximum profit = Rs. 392. Ans.Linear Programming 1521 Example 17. Anil wants to invest at most Rs. 12,000 in Bonds A and B. Acconting to the rules, he has to invest at least Rs. 2,000 in Bond A and at least Rs, 4,000 in Bond B. If the rate of interest on Bond A is 8% per annum and on Bond B is 10% per annum, how should he invest his money for maximum interest ? Solve the problem graphically. Solution. The above information are given in the following table: 1. Table Bonds Interest Tnvestment in Rs A 2% ‘At Teast 2,000 B 10% ‘At Teast 4,000 Total 12,000 2. Decision Variables. Let Anil invest Rs. x (more than Rs. 2,000) on bond 4. Let Anil invest Rs. y (more than Rs. 4,000) on bond B. 3. Objective function. To maximise the total interest 1 > z= Lass) 4. Constraint (i) Total investment = 12,000 x+y<12,000 Constraint (i). Investment on Bond 4 = Minimum Rs, 2,000 22,000 Constraint (i). Investment on Bond 8 = Minimum Rs, 4,000. y> 4,000 '. Mathematical formulation 1 To maximise Z=Z(4r+5y) © Subject to the constraints x+ys12,000 @ 22,000 6) 24,000 ® 6. Region represented by x+y = 12,000 2,000 is represented by the line CD. |» = 4,000 is represented by the line DE. x [12,000 oO » 0 12,000 Points [4 B 7. Corner Point Method ‘The shaded bounded region CDEC is the feasible region of the given L.PP,, where the vertices are C (2,000; 10,000), D (2,000; 4,000) and £ (8,000; 4,000).1522 igher Enginosring Mathematics Corner poms Tale of the objective ofthe feasible ‘fetion gion CDE * 1 aessy) 30 (2,000; 10,000) t (4% 2,000-+ 510,000) > emo, som, | 220003040050 : rem sa |yanaowrsaoa=ion | "= For camaing maximum interest (Rs. 1,160), Anil should invest Rs. 2,000 in Bonds 4 and Rs, 10,000 in Bonds B. Ans. ‘Type Il. To minimize the objective function (Z) Example 18. There are two types of fertilisers F, and F;, F, consists of 1096 nitrogen and 6% phosphoric acid and F-, consists of 5% nitrogen and 108% phosphoric acid. After testing the soil conditions, a farmer finds that she needs atleast 14 kg. of nitrogen and 14 kg of phosphoric acid for her crop. If F, costs Rs. 6ikg and F, costs Rs. S/kg, determine how ‘much of each type of ferilizer should be used so that nutrient requirements are met at a ‘minimum cost. What is the minimum cost? Solution. The above information are given in the table given below 1, Table. Fertilisers ‘Nitrogen Phosphoric acid Cost per ke in Rs.) F 10% 6% 6 Fy 3% 10% 3 Mixture Take Tike 2. Decision Variables. Let the fertiliser /, in the mixture be x kg. Let the fertiliser F, in the mixture be y kg. 3. Objective function. ‘To minimise the cost of the mixture of fertilisers F, and x + Sy 4. Constraint (). Minimum requirement of Nitrogen = 14 kg 103% o14 100°” 100 = 2x+y 2280 Constraint (i). Minimum requirement of phosphoric acid = 14 kg => 3et5y 2700 Constraint (i). Number of kg of fertiliser F, and F, be non-negative. x20 and y20. ‘5. Mathematical Fermulation, To minimise Subject to the constraints Zn 6x4 5y 2x+y 2280 3x+5y2 700 x20, y20.Linear Programming 1523 6. Region represented by 2x+y2280,and 3x+y2700 2x +y = 280 3x + Sy = 700 700 xy [mo | 0 x 0 vy | o | 280 > 0 140 Points [ A B Points iG D 1. Comer Point Method. The feasible solution is the shaded portion. ‘The vertices of the feasible solution are B (0, 280), 1 (100, 80) and (= | y Let us calculate the value of Z at these comer points Beal C "ease gion aijecthe fncton Za 6+ 5) B (0, 280) E (100, 80) 7 (0) 625.0 21400 3 : ‘The minimum cost of the mixture of fertilisers F, and F, is Rs. 1000 if 100 kg of the feriliser F, and 80 kg of fertiliser F, are mixed. ‘Ans. Example 19, diet is 0 contain at least 80 units of vitamin A and 100 units of minerals. wo foods F, and Fare available. Food F, costs Rs. 4 per unit and food F, costs Rs. 6 per init, A init of food F, contains at least 3 units of vitamin A and 4 units of minerals. ‘A unit of food F; contains atleast 6 units of vitamin A and 3 units of minerals. Formulate this as a linear programming problem. Find the minimum cost for diet that consists of ‘mixture of these two foods and also meets the minimal nutritional requirements Solution. The above information are given in the table below: 1. Table, Food Titamin A Mineral Cost per unit din units) fin Rs.) F, ‘Atleast 3 units 4 4 Fy ‘At least 6 units 3 6 Diet ‘At Teast 100 80 units 2. Decision Variables. Let x units of food , and y units of food F, be mixed in the dict. 3. Objective function. To \minimise the cost of the diet. Z= 4x + 6y 4, Constraint (i), Diet should contain at least 80 units of vitamin A, 3x+6y 280 Constraint (i). Diet should contain at least 100 units of minerals 4x+3y2100 Constraint (ii). Number of units of food F, and Fyare non-negative <>0 and y=0 ‘5. Region represented by 3x+6y 280 and 4x+43y 21001524 Higher Engineering Mathematics 4x3) =100 o x | a] o «© 1a »fo 4 Fi - Points | A B Points Cc D 1, Comer Point Method ‘The feasible region is the shaded portion. The comer points are 4 (24) ant 0.3 (Corner points of | Value of the the feasible objective region function Z= 4+ 6 4(2.0 3 a(22 3 (0,30) 40 +630 = 180. 2 is minimum for x= 24 and y= ‘The least cost of the mixture is Rs. 40 per unit. Ans. Example 20. 4 dietician wishes fo mix together two kinds of food X and ¥ in such a way ‘that the mixture contains atleast 10 units of vitamin A, 12 units of vitamin B and 8 units of vitamin C. The vitamin contents of one ke. food is given below: Food | Vitamin | Vitamin B Vitamin C_[ Cost per ke. x i 2 3 16 Y 2 2 1 20 ‘Mixture 10 2 8 mie Rg. af Jood X costs Rs. 16 and one Kg. of food costs Rs, 20. Find he Teast cost of the mixture which will produce the required diet? n variables, Let x kg. of food 1 and y kg of food Y are mixed together to make the mixture. 2. Objective function. It is given that one kg, of food costs Rs. 16 and one kg. of food ¥ cost Rs. 20. So, x kg. of food X and y kg of food ¥ will cost Rs. (16x + 203). = Z= 16x + 20y 3. Constraint (i) Since one kg. of food contains one unit of vitamin A .. xkg, of food X contains x units of vitamin A Since one kg, of food ¥ contains 2 units of vitamin A . vkg. of food ¥ contains 2y units of vitamin ALinear Programming 1825 ‘Therefore, the mixture contains x + 2y units of vitamin 4, But the mixture should con- tain atleast 10 units of vitamin 4. x+2y210 Constraint (i). ‘Similarly, the mixture of x kg. of food X and ¥ kg. of food ¥ contains (2x + 2) units of vitamin B. But the mixture should contain at least 12 units of vitamin B. 2e42y212 Constraint (ii). x kg. of food 1 and y kg. of food ¥ contains 3x + y units of vitamin C. But the mixture should contain at least 8 units of vitamin C. . Betye8, Constraint (i). ‘Since the quantity of food X and food Y can not be negative: x20 and. v2. 4. Mathematical Formulato Thus the given LPP is Minimize Z= 6x + 2oy Subject to x+2y210 2x+2y212 Sety28 and x20, y20 '. Region Represented by the inequations. To solve this L.PP. we draw the lines x+2y=10 2e+2y= 12 and 3x+y=8 8 x wo} 0 x 6 | 0 alo » o 3 » o | 6 yes Points| A BI|[Poms[c [ p || [Poms| & [ F ‘The feasible region of the L.PP. is shaded im the adjoining figure 6. Corner Point Method ‘The coordinates of the comer points are 4(10, 0, (2, 4, CL, 5) and F 0,8) Now, we evaluate Z= 16x + 20y at the comer points, [Corner points | Corresponding of the values of feasible = 16s + 20y region AO, 0) |Z = T6(I0) + 200) OG, |Z = 160) +204) = 112 PU, 5) __|Z= 16() + 208) = 116 FOS) [2= 16) + 20 B= 100 ‘The minimum value of Z= 112 at the point xahy= 4 Hence; the least cost of the mixture is Rs. 112. Ans.1526 Higher Engineering Mathematics TYPE Ill. TRANSPORTATION PROBLEMS Example 21. An oil company has two depots A and B with capacities of 7000 | and 4000 I respectively. The company is to supply oil to three petrol pumps, D, E and F. whose requirements are 4500 I, 3000 | and 3500 I respectively: The distances (in km) between the depots and the petrol pumps is given in the following table: Distance in (km.) FromTo A D 7 E 6 FE 3 Assuming that the transportation cost of 10 litres of oil is Re. 1 per km, how should the delivery be scheduled in order that the transportation cost is minimum ? What is the ‘minimum cost? Solution, The given information can be exhibited diagrammatically as follows: 1, Table, Depot A vo Pump Peta Pun tro Pm ire a >> gPal Pum F ec ) ( 20001 2. Decision Variables. Decision variables are the lites of oil to be supplied from depots to the petrol pumps. Let Depot A supplies x litres of oil to petrol pump D and y litres of ol to petro! pump E and [7000 -(x+y)] litres of oil to petrol pump F. Constraint (). 7000-(x+))20 = x+y<7000 x20,y20 Constraint (i) The remaining requirement (4500 - x) litres of oil is supplied from the depot B to the petrol pump D, (3000 ~ 3) litres of oil to petrol pump £ and 4000 — [(4500 ~ x) + G000 ~ 3)] litres of oil to petrol pump F 4500-x20 > x= 4500 3000-y20 => — ys 3000 4000 - 4500 + x ~ 3000 + y > 0 = x+y 23500Linear Programming 1827 3. Objective function, >. ® Te tatsponaton cst fom dept dt he et pump D, Ean Fis. ns, 3 ant Re 3 000 —-9) Similarly, the transportation cost from depot 8 to petrol pump D, E and F is 3 4 2 7p (4500-3), Rs. + 3000- Rs. prt y 3500 Rs. 75 (4500 — 3), Rs. 703000 y) and Rs. s60 50-y20 > ys50 40-00 -x-y) 20 = xy 6020 or xt y2 60 4. Objective function. Cost of transportation from Godown to shops D, H and F are Rs. 6x, Rs. 3y and Rs, 2.5 (100 ~ x — 3), Similarly the cost of transportation from Godown B to shops D, E and F are Rs. 4(60 ~ x), Rs. 2 (50 ~ y) and Rs. 3 [40 ~ (100 — x ~ y)] respectively So total cost of transportation = Z Z= Rs. [6x + 3y + 2.5 (100 ~ xy) + 4 60-2) 2 50-4) +3 (60 +x +4) [6 - 2.5 — 4+ 3x + G- 25~2 +3) y + 250 + 240 + 100-180] =25x+15y +410 ‘5. Mathematical Formulation To minimize Z=2Se+15y+ 410 x+y S100 « and x20 2) veo @) x4 y260 a) and xs60 6) and ys50 6) 6. @ Region represented by x+y 100 x+y 100 = 100 0 y 0 100 Points a B ‘On joining A and B we get the graph of the line x + y = 100, Since, (0,0) satisfies the inequation 0-+0< 100. So, the half plane containing origin represents the region of the inequation x+y < 100. Region represented by x+ 260. xty= 60 ¥ oo. oO » oO 60 Points cl D. ‘On joining the points C(60, 0) and D(0, 60), we get the graph of the line represented by x +y= 60, Since, (0,0) does not satisfy x+y 260. So, the half plane not containing origin represents the region of x+y260.1530 Higher Engineering Mathematics (iii) Region represented by ~>0 and y20 is the first quadrant. (iv) Region represented by x= 60 the half plane containing the origin. (v) Region represented by y<50 is the half plane containing origin, 7. Comer point Method ‘The feasible region is the shaded portion CHIJC. Its vertices are C(60, 0), 11(60, 40), 150, 50) and J(10, 50), ‘The coordinates of // are calculated by solving the equations x + y = 100 and x = 60, ‘The coordinates of / are calculated by solving the equations x + y = 100 and y = 50. ‘The coordinates of are calculated by solving the equations x + y = 60 and y= 50. ‘The values of the objective function at the comer points ate given in the following table. ‘Corner point (x, y) Value of the of the feasible region | objective function at the corner points in Rs. Z= 25x + 15y + 410 C@.H 2.5160) + 1.5(0) + 410 = 360 I (60. 40) 2.5(60) + L5(40) + 410 = 620 TSO, 50) 2360) +15 G0) +410 = 610 70, 50) (0) + 15 Go) + 410 = 510 Hence, 7 is minimum when x = 10 and y= 50, the minimum cost of transportation in Rs, 510. EXERCISE 56.3 1. A manufacturer produces two items X and ¥. X needs two hours on machine A and two hours on ‘machine B. Y needs 3 hours on machine A and 1 hour on machine B. If machine A can run for a maximum of 12 hours per day and machine B for & hours per day and profits ftom X and Y are Rs. 4 and Rs. 5 per items respectively. Formulate the problem as a linear programming problem and solve it graphically ‘Ans, Maximum profit ~ Rs, 22; Number of items X = 3; Number of items Y = 2 2. An aeroplane ean carry a maximum of 200 passengers. A profit of Rs. 400 is made on each first class ticket and a profit of Rs. 300 is made on each economy class Gcket. The srine reserves atleast 20 seas for first class. However, atleast 4 times as many passengers prefer to travel by economy class to the first class. Determine how many each type of tickets must be sold in onder to maximize the profit for the iting. What is the maximum profit ? ‘Ans, Maximum profit ~ Rs. 64000, First clase Gckets = 40. Economy class tickets ~ 160.Linear Programming 1531 3. A manufacturer is tying to decide on the product quantities of two productstables and chairs. There fare 98 units of material and 80 labour-hours available, Each table requires 7 units of material and 10 labourshours, while each chair requires 14 units of material and 8 labour-hours per ehair. The profit fon a table and a chair is Rs. 25 and Rs. 20, respectively. How many tables and chairs should be produced to have maximum profit? (Hint: Use 1so-prfit method. ‘Ans. Maximum profit Rs. 200, Tables ~ 8, chairs ~ 0 of Tables ~ 4, chats ~ 5 4. A man owns a field of area 1000 sq, metre, He wants to plant tees in it, He has a sum of Rs. 1400 to purchase young trees. He has the choice of two types of tees, Type A requires 10 sq, metre of ‘ground per tee and costs Rs. 20 per tre and type B requires 20 sq, metre of ground per tee and costs RS, 25 per tree. When fully grown, type A produces an average of 20 kg. of fruits which can be sold ata profit of Rs. 2 per kg. and type B produces an average of 40 kg of fruits which can be sold at a profit of Rs. 1.50 per kg. How many trees of each type should be planted to achieve ‘maximum profit when the tres are filly grown? What is the maximum profit? ‘Ans, Maximum profit ~ Rs. 32,00, Type A = 20. Type B = 40. ‘5. A farm is engaged in breeding goats. The goats are fed on various produets grown on the farm. They need cerain nutiens, named as X, Y and Z. The goats are fed on two products A and B. One unit of product A contains 36 units of X, 3 units of Y and 20 units of Z, while one unit of product B contains 6 units of X, 12 units of ¥ and 10 units of Z. The minimum requirement of X, Y and Z is 108 units, 36 units and 100 units respectively. Product A costs Rs. 20 per unit and product B costs Rs. 40 per unit. How many units of each product must be taken to minimize the cost? ‘Ans. Minimum cost = Rs. 160, Product A= 4 units, Product B= 2 units. 6. A company producing soft drinks has a contract which requires that a minimum of 80 units of chemical A and 60 units of chemical B are to go in each botle of the drink. The chemicals are available in @ prepared mix from two different suppliers. Supplier X has a mix of 4 units of A and 2 units of B that costs Rs, 10 and the supplier Y has @ mix of 1 unit of A and 1 unit of B that costs Rs. 4, How many mixes from X and Y should the company purchase to honour contract requirement and yet minimize the eost? Ans. Minimum cost = Rs. 260. Mix of type A= 10 units, Mix of type B = 40 units ‘7. To mainiain one’s health, a person must fill minimum daily requitements for the following three rutriens-calcium, protein and calories. His det consists of only food items I and I whose prices and Itrient contents are shown below Food T Food IT Minima Rs. 0.60 per wit | Re 1 per wut requirements 10 4 20) 5 Ls po Calories 2 6 2 Find the combination of food Heme so thatthe ost may be minimum ‘Ans. Minimum cost ~ Rs. 2.80, Food I~ 3 units, Food I = 1 unit 8. A dict for a sick person must contain at least 4000 units of vitamin, 50 units of minerals and 1400 ‘units of calories. Two foods A and B are available ata cost of Rs. 4 and Rs. 3 per unit respectively. fone unit of A contains 200 units of vitamin, 1 unit of mineral and 40 units of calories: one unit of food B contains 100 units of vitamin, 2 units of minerals and 40 units of calories, find what combination of foods should be used to have the least cost? ‘Ans. Minimum cost = Rs. 110, Food A = $ units, Food B = 30 units. 9. Two godowns A and B have grain storage capacity of 100 quintals and 50 quintals respectively. They supply to three ration shopes D, E and F whote requirements are 60, 50 and 40 quintals respectively, ‘The cost of transportation per quital fiom the godown to the shopes are given in the following table:1832 Higher Engineering Mathematics irom Godown Godovn To 4 B D 6.00 400 E 300 200 F 250 300 Low should the wupplicr we Wansported in onder that dhe transportation cost i minimum, ‘Ans. From A: 10 quinals, 50 quintals and 40 quintals to D, E and F respectively From B : 50 quintals, 0 quintal and 0 quintal to D, E and F respectively 10, There is a factory located at each of the two places P and Q. From these locations, a certain commodity is delivered to each of these depots sited at A, B and C. The weekly requirements of the depots are respectively 5, 5 and 4 units of the commodity while the production capacity of the factories at P and O are respectively 8 and 6 units. The cost of transportation per unit is given below: To Cost fn Rs) From a B c FP 16 10 5 0 1 0 ow many units shoud be wansporied rom each fetery w each depot in onder that the transportation cost is minimum. Formulate the above L.PP mathematically and then solve it ‘Ans, Minimum cost = Rs. 15S, From P : 0, 5, 3 units to depots at A, B, C respectively From Q - 5, 0 and 1 units to depots at A, B and C respectively: 11, A brick manufacturer has two depots, A and B with stock of 30,000 and 20,000 bricks respectively He receives orders from three builders P, Q and R for 15,000; 20,000 and 15,000 bricks respectively the cost in Rs, transporting 1000 bricks to the builders from the depots are given below: P 2 R 0 20 30) 20 oO 0 How should the manufacturer fulfill the orders so as to Keep the cost of transportation minimum. ‘Ans. Minimum cost = Rs. 1200 From A : 0, 20 and 10 thousand bricks to builders P,Q and R. From B = 15, 0 and 5 thousand bricks to builders P, Q and R 12, A publisher sells a hard cover edition of a textbook for Rs, 72.00 and a paper back edition of the same text for RS. 40,00, Coats tothe publisher are Rs, $6.00 and Rs. 28.00 per book respectively in dition to weekly costs of Rs. 9600.00. Both types require 5 minutes of printing time, although hard cover requires 10 minutes binding time and the paper back requires only 2 minutes both the printing and binding operations have 4,800 minutes available each week. How many of each type of Book should be produced in order to maximize profit? ‘Ans. Max. profit ~ Rs. 2880, 360 hard cover edition, 600 paper back edition 56.9 THEORY OF SIMPLEX METHOD ‘The basis of the complex method consists of two fundamental conditions :- (The feasibility condition ensures that the starting solution is bs obtained during computation. ie feasible, only basic feasible solution will beLinear Programming 1533 i) Optimality condition It guarantees only better solution (as compared to the current solution) ‘SOME IMPORTANT DEFINITIONS Consider the following problem Maximize Z= ex, +e, + exp Subject 10 ay, + A4:%, + sorue yghy Sy Objective function Ay, # 3% en Oy S Boy Constraints ee el Where x), Xeon %y 20. Introducing slack vairable s,s, 8. 8)...=1-» Sy in m constraint equations. It can be put in the following standard form: Maximize 2 = e,3,4 C¥yhown Gytyh St Sonat Sy « Subject 10 ay)x) 4 4,8 F ens Cy * 8) Ayyh) + Oey + Aah +8 = 2) AyX + May * ems Ag * Sy = 8, Where x.) conron Mp Sip Speen Sy 20 @) 1, Solution : To find out the values of 3,3 sone My Spy oe Sp 2, Feasible solution : The values of.) 0. Xp Ss oo Sy i8 KNOWN as feasible solution if these values satisfy the equations (2) and (3) 3. Basie solution : By making any 1 variables out of» ~ m equal to zero, the values of the remaining m variable is called the basic solution, if the determinant of the coefficients of these slack variables is non negative. 4. Basic variables : The variables of the basic solution are called basic variables (Some of ‘them may be zero). The other » variables are called non-basic variables, 5. Basic feasible solution : The basic solution of non-negative variable is called basic feasible solution, 6. Non- degenerate basic feasible solution : If all m basic feasible variables non-negative, then the set of these variables known as non degenerate basic feasible solution 7. Degenerate basic feasible solution : If one or more basic feasible variable is zero, then the solution known as degenerate basic feasible solution 8. Optimal basic feasible solution : It contains basic feasible solution that optimize the objective function, 9. Sets of points : Linear equation in two variables represents a line and a linear equation in three variables represents a plane. Both of them are considered as set of points, Example 23. Solve by using simplex method Maximize z= 3x, + 4, Subject to x, +x, $ 450 2x, +x, 600 Xp X201534 Higher Engineering Mathematics Solution, ‘Step 1. Express the the above objective function and inequations in the equation of standard form by adding slack variables. Maximize 2 3x, + dx, + 0s, +05, Subject to xy tay ts, = 450 2x, xy + 5 = 600 20 where x), 3,5), Step 2. Find initial basic feasible solution. Putting x, = x, = 0, in the constraints, we get ss, = 450 and s, = 600 and z = 0 This is the initial basic feasible solution. ‘The above information can be expressed in the tabular form as follows. Coefficient G 3,4 0 [0 Basis_| body matrix | identity matrix | value %] % ss |e 0 5 iio i], [2] 4x0 0 Ss 2}1 o | 1 | 600 Row, G, represents the coefficients of the variables in the objective Function Column, C;, represents the coefficients of the current basic variables, The basic variables are the slack variables s, and s,. Body matrix : The body matrix under non-basic variables x, and x, represents their coefficients in the constraints. Indentity matrix : The identi constraints. ‘Column b indicates the values of the basic variables, s, and s, in the initial basic feasible solution. Step 3. Perform optimality test. Here, since C, -Z, is positive under x, and x, columns so initial basic problem is not optimal and can be improved. matrix represents the coefficients of stack variables in the c ane ee oo G, | _ Basis sts |) =|) |e Opener 1 | @ | 1 | 0 | 450 | 450] + (key row) 0 2/1 o | 1 | 600 | «00 Z-=Gay fo | o 0 [0 G-% 3 | 4 a) + K (Key column) Row Z, : Z,= E Cpa, where a, are the matrix element in the i-th row and jth column, For example, Z=0714+0%2=0 If the elements in the C, - Z, row are negative or zero, then the current solution is optimal, Since here, two elements 3 and 4 under x, and x, variable columns are positive, so the solution is not optimal and we proceed to the next step.Linear Programming 1535 Step 4. Iterate towards an optimal solution = Selection of entering variable : For this we look for maximum positive values in C, ~Z, row. IF more than one vairable appears with the same maximum value then any one can be choosen arbitrarily This variables is called entering variable. This column is knows as Key column. Thus here we find x, as entering variable Selection of the leaving variable Elements of column b are divided by the corresponding elements of the key column and row containing the minimum non-negative ratio is marked. This row is called the Key row. ‘The element lying atthe intersection of key column and key row is called key (or pivot) clement and is enclosed in (). Here key element is 1 Preparing new simplex table : ‘We replace 5, by x; from the basis. Corresponding Cy, coefficient is changed from 0 to 4. If Key element is not unity made it unity and other intersectional elements are made zeros by suitable row operations. Thus, we get the following table: G 3 [| 4+] oo G]_ Basis xf ™=[=[= | Te T|—T v 50 ° 1] 0 1 150 Ca) 4] 4 ° 1800) 1-2, 1} 0] +4] 0 Step 5. Sincs here all clements of G, —Z, row are either 2670 oF negative so the second feasible solution is optimal, Hence the optimal solution is x0 50 s 1800 Ans. Z, Example 24, Use simplex method to solve the following problem. Maximize Z= 2x, + 5x Subject to x, t 4x, $24 Br, +x, < 21 xy bx, 59 xn 20 Solution, ‘Step 1. First we express the objective funciton and inequations in equations of standard form by adding slack variables s,, s,, and s,, Maximize Z= 2x,'+ Se, +05, + 0s, + Os, Subject to xy tax +5 228 Bk tats 2 x bxts=9 xtmtye9 Xp By Sie Sp 5 20 ‘Step 2. Find initial basic feasible solution. Putting x, =x; = 0, in the constraints, we get 5, = 24, 5, = 21 and s,=9 and z= 0 This is initial basic feasible solution, ‘The above information can be expressed in matrix form as follow:1536 Higher Engineering Mathematics Gi 2[s[°] o[o CBs % aLs>s Tey ® os, 1 1] 0 | 0 | 24] 6+ ey 0m os 3 o} 1] o | 2] a os raf] of] ofa 5 Z, Tope pepo G=%, a 1] key column solution Step 3. Perform optimality test Here, since C, ~ Z, is positive under x, and x, - columns so initial basic feasible solution is not opti ccan be improved. Step 4. Iterate towards an optimal solution. First we make pivot element unity for this we divide the key row by 4, c 2[s][ol[o|o G,_ Basis Se 5 t}i]t]ofo| «| rote *% 4 4 6 | Ro GR, oy sfij}ofa]o]} a os 1fitofofils Now we make the other elements of Key column 0 by suitable following row operations G Z[ 5] °]0]0 G, Basis x l= pa |S |e | > 1 L Soy giitagle fel s u Oe 7 /e 1 }o] as] RR-R, 3 1 os Flop ]e ja] 3 | Re RHR ° Cy] Basis Eee aa mes en ee eos 1 1 s| zy lt la Jojo je ja ul 1 60 o} s jo Jp fr fo jas |>Linear Programming 1837 5 5 ce || | o | iy ‘ Second 3 GZ tl o 0 | 9 | feasible a solution By the above table we observe that + is the maximum postive value of C, ~ Z, row so its column is the key column, Thus, here x, is entering variable. Also 4 is the minimum ratio under 0, 50 row containing 4 is key row. Thus s, is leaving 33 variable, At the intersection of key row and key column is =, so | is pivot element G [Bas s & | |» [5 |% 1 1 s |x 7 TF le jo feo ° 2 yo }E a fo fis % 7 z 5 a 4 es o |», ro fy fo |Z f+ [Roger oy | Basis x » [ss [oe e jt z s|x oh fs jo fs |s JRowpR 2 Lu u 0} s Oe et 3 |* | ROR-TR 2 o |4 x 1 lo 5; |4 G 2 [5 ]° Jo ]0 G, | Basis x le ta |e [as |e e eu sfx Ogee eb e|s 2 a 0 ofo | fa |-> ]a4 > |, |4 x fe Ol las ae a Zi 2 1 [0 | 1 [33 [Third feasible C-z, ojo ja jo ja solution1538 Higher Engineering Mathematics Since here all elements of C, - Z, row are either zero or negative so the third feasible solution is optimal, Hence, the optimal solution is 4 3 4 33 Ans. Example 25, Solve by simplex method the following L.P. problem. Minimize Z=x,-3x, + 3x, Subject to Bx, — x, +24 <7 2x; + Ae, 2-12 “tx, + 3x, + Bx, < 10 xy tp 20 Solution. Step 1. Right hand side of second constraint is made positive by multiplying —1 ‘Adding the slack variables s,, s, and s, the above inequations can be written in standard form as follows Minimize Zz Subject to By ty +5 =7 “2x, = day + 5) = 12 ty, + 3x, + 8x, +5, = 10 XM Yy Sp Sy 8520 Step 2. To find initial basic feasible solut 5,=7, 8, = 12, and s, = 10; The above information can be written in tabular form as follows: x, = 3x, + 3x, + Os, + 05, + Os, O in the constraints, we get z S Hille De Salers, Basis |, =] als) s)e] 8 5 3 2 ofol7| a4 os, 2 of} 1 fo} 3 10 Key o Is, @ls | oofofa jw) > Row Zz, C-4% RT Key colama Step 3. Perform optimality test: Here as we have to minimize Z, so if any C, ~ Z coefficient is negative the solution is not optimal The column having most negative C, ~Z, value willbe the key column, Since, here element -3 under x, variable column is most negative, so the solution isnot optimal and we proceed to the next step. Step 4. Iterate towards an optimal solution Variable s, is replaced by x, by performing the row operations in the usual ways. Solution will become optimal when all , ~ Z, coefficients become zero oF positive,Linear Programming 1539 ___5 sien oF 6 [0 3/3 = 32 4 | | 38 aie 3 |° Ott 3s )3 ja a 8 wo fos o| x + fa ff fo fo] + | 8 ]-8 z, 1 7 c-z, | 3 ufo fo} 4 Kt Here further we have find a negative element above, with entering variable x; and leavir 3 in C, ~Z, row, so we again proceed as variable s, ¢ oe ee ula 1 fa ils a. hUL re | 5 3 | 3 136 | 22 us | se o| 5 o fo fy 2la | 2] 3 3 5 | nla 3 | ss : of: [2/4 Jo} 2] -2| 2] Zz, 1 2 a|o 8 oz, o fo [ZZ Lo | & | ootimarsottion ar Hence. opimal soliton is 58 M3 ot 8 20,7, 218 a nel 4 An EXERCISE 56.4 Solve the following problems by the Simplex method. 1 Maximize "2 35, + 2x Subject © x, +3 <4 Ams <3. 51 nomed Ze = Hh xm eo1540 5. Subject to Maximize Suiject to Minimize Subject to Minimize Subject to Z= 4x, + 10x, 2x, +x) $50 2x, + Sx, < 100 2x, + 3x, < 90 xem 20 Det xy x + 2x, $10 x ta s6 xy-% 52 x - 2s xm 20 x) 3x) + 2x, 3x, —x, +2427 2x, + 4x, $12 “tx, + 3x, + 8, Xp ky 20 ay tay By tye 4x, + 3x, 26 xy +2y 83 xy m2 Higher Engineering Mathematics Ans. x; 3.6 Ans.x)= 3.5 3 18, oS