CU-BCA-SEM-I-Mathematics

251 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 5: Solution: 252 CU IDOL SELF LEARNING MATERIAL (SLM)

253 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 6: Solution: 254 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 7: Solution: 255 CU IDOL SELF LEARNING MATERIAL (SLM)

256 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 8: Solution: 257 CU IDOL SELF LEARNING MATERIAL (SLM)

258 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 9: A furniture company produces inexpensive tables and chairs. The production process for each is similar in that both require a certain number of hours of carpentry work and a certain number of labour hours in the painting department. Each table takes 4 hours of carpentry and 2 hours in the painting department. Each chair requires 3 hours of carpentry and 1 hour in the painting department. During the current production period, 240 hours of carpentry time are available and 100 hours in painting is available. Each table sold yields a profit of E7; each chair produced is sold for a E5 profit. Find the best combination of tables and chairs to manufacture in order to reach the maximum profit. Solution: 259 CU IDOL SELF LEARNING MATERIAL (SLM)

The decision variables can be defined as X = number of tables to be produced & Y = number of chairs to be produced. Now linear programming (LP) problem can be formulated in terms of X and Y and Profit (P). maximize z = 7X + 5Y subject to 4X + 3Y ≤ 240 (hours of carpentry constraint) 2X + Y ≤ 100 (hours of painting constraint) X ≥ 0, Y ≥ 0 (Non-negativity constraint). Therefore the mathematical formulation of the LPP is: Maximize: Z = 7X + 5Y Subject to: 4X + 3Y ≤ 240 2X + Y ≤ 100 and X ≥ 0 , Y ≥ 0 To find the optimal solution to this LP using the graphical method we first identify the region of feasible solutions and the corner points of the of the feasible region. 260 CU IDOL SELF LEARNING MATERIAL (SLM)

In this example the corner points are (0,0), (50,0), (30,40) and (0,80). Testing these corner points on P = 7X + 5Y gives 261 CU IDOL SELF LEARNING MATERIAL (SLM)

Because the point (30,40) produces the highest profit we conclude that producing 30 tables and 40 chairs will yield a maximum profit of E410. 262 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 10: A company makes two products (X and Y) using two machines (A and B). Each unit of X that is produced requires 50 minutes processing time on machine A and 30 minutes processing time on machine B. Each unit of Y that is produced requires 24 minutes processing time on machine A and 33 minutes processing time on machine B. At the start of the current week there are 30 units of X and 90 units of Y in stock. Available processing time on machine A is forecast to be 40 hours and on machine B is forecast to be 35 hours. The demand for X in the current week is forecast to be 75 units and for Y is forecast to be 95 units. Company policy is to maximise the combined sum of the units of X and the units of Y in stock at the end of the week. ● Formulate the problem of deciding how much of each product to make in the current week as a linear program. Solve this linear program graphically. Solution: Let ● x be the number of units of X produced in the current week ● y be the number of units of Y produced in the current week then the constraints are: 50x + 24y <= 40(60) machine A time 30x + 33y <= 35(60) machine B time 263 CU IDOL SELF LEARNING MATERIAL (SLM)

x >= 75 - 30 i.e. x >= 45 so production of X >= demand (75) - initial stock (30), which ensures we meet demand y >= 95 - 90 i.e. y >= 5 so production of Y >= demand (95) - initial stock (90), which ensures we meet demand The objective is: maximise (x+30-75) + (y+90-95) = (x+y-50) i.e. to maximise the number of units left in stock at the end of the week It is plain from the diagram below that the maximum occurs at the intersection of x=45 and 50x + 24y = 2400 264 CU IDOL SELF LEARNING MATERIAL (SLM)

Solving simultaneously, rather than by reading values off the graph, we have that x=45 and y=6.25 with the value of the objective function being 1.25 Example 11: A company is involved in the production of two items (X and Y). The resources need to produce X and Y are twofold, namely machine time for automatic processing and craftsman time for hand finishing. The table below gives the number of minutes required for each item: Item X Machine time Craftsman time Y 13 20 19 29 265 CU IDOL SELF LEARNING MATERIAL (SLM)

The company has 40 hours of machine time available in the next working week but only 35 hours of craftsman time. Machine time is costed at £10 per hour worked and craftsman time is costed at £2 per hour worked. Both machine and craftsman idle times incur no costs. The revenue received for each item produced (all production is sold) is £20 for X and £30 for Y. The company has a specific contract to produce 10 items of X per week for a particular customer. Formulate the problem of deciding how much to produce per week as a linear program. Solve this linear program graphically. Solution: Let x be the number of items of X y be the number of items of Y Then the LP is: maximise 20x + 30y - 10(machine time worked) - 2(craftsman time worked) subject to: 13x + 19y <= 40(60) machine time 20x + 29y <= 35(60) craftsman time x >= 10 contract 266 CU IDOL SELF LEARNING MATERIAL (SLM)

x,y >= 0 so that the objective function becomes maximise 20x + 30y - 10(13x + 19y)/60 - 2(20x + 29y)/60 i.e. maximise 17.1667x + 25.8667y subject to: 13x + 19y <= 2400 20x + 29y <= 2100 x >= 10 x,y >= 0 It is plain from the diagram below that the maximum occurs at the intersection of x=10 and 20x + 29y <= 2100 Solving simultaneously, rather than by reading values off the graph, we have that x=10 and y=65.52 with the value of the objective function being £1866.5 267 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 12: 268 CU IDOL SELF LEARNING MATERIAL (SLM)

A company manufactures two products (A and B) and the profit per unit sold is £3 and £5 respectively. Each product has to be assembled on a particular machine, each unit of product A taking 12 minutes of assembly time and each unit of product B 25 minutes of assembly time. The company estimates that the machine used for assembly has an effective working week of only 30 hours (due to maintenance/breakdown). Technological constraints mean that for every five units of product A produced at least two units of product B must be produced. ● Formulate the problem of how much of each product to produce as a linear program. ● Solve this linear program graphically. ● The company has been offered the chance to hire an extra machine, thereby doubling the effective assembly time available. What is the maximum amount you would be prepared to pay (per week) for the hire of this machine and why? Solution: Let xA = number of units of A produced xB = number of units of B produced then the constraints are: 12xA + 25xB <= 30(60) (assembly time) xB >= 2(xA/5) i.e. xB - 0.4xA >= 0 269 CU IDOL SELF LEARNING MATERIAL (SLM)

i.e. 5xB >= 2xA (technological) where xA, xB >= 0 and the objective is maximise 3xA + 5xB It is plain from the diagram below that the maximum occurs at the intersection of 12xA + 25xB = 1800 and xB - 0.4xA = 0 270 CU IDOL SELF LEARNING MATERIAL (SLM)

Solving simultaneously, rather than by reading values off the graph, we have that: xA= (1800/22) = 81.8 xB= 0.4xA = 32.7 with the value of the objective function being £408.9 271 CU IDOL SELF LEARNING MATERIAL (SLM)

Doubling the assembly time available means that the assembly time constraint (currently 12xA + 25xB <= 1800) becomes 12xA + 25xB <= 2(1800) This new constraint will be parallel to the existing assembly time constraint so that the new optimal solution will lie at the intersection of 12xA + 25xB = 3600 and xB - 0.4xA = 0 i.e. at xA = (3600/22) = 163.6 xB= 0.4xA = 65.4 with the value of the objective function being £817.8 Hence we have made an additional profit of £(817.8-408.9) = £408.9 and this is the maximum amount we would be prepared to pay for the hire of the machine for doubling the assembly time. Example 13: A company manufactures two products (A and B) and the profit per unit sold is £3 and £5 respectively. Each product has to be assembled on a particular machine, each unit of product A taking 12 minutes of assembly time and each unit of product B 25 minutes of assembly time. The company estimates that the machine used for assembly has an effective working week of only 30 hours (due to maintenance/breakdown). Technological constraints mean that for every five units of product A produced at least two units of product B must be produced. ● Formulate the problem of how much of each product to produce as a linear program. ● Solve this linear program graphically. 272 CU IDOL SELF LEARNING MATERIAL (SLM)

● The company has been offered the chance to hire an extra machine, thereby doubling the effective assembly time available. What is the maximum amount you would be prepared to pay (per week) for the hire of this machine and why? Solution: Let xA = number of units of A produced xB = number of units of B produced then the constraints are: 12xA + 25xB <= 30(60) (assembly time) xB >= 2(xA/5) i.e. xB - 0.4xA >= 0 i.e. 5xB >= 2xA (technological) where xA, xB >= 0 and the objective is maximise 3xA + 5xB It is plain from the diagram below that the maximum occurs at the intersection of 12xA + 25xB = 1800 and xB - 0.4xA = 0 273 CU IDOL SELF LEARNING MATERIAL (SLM)

Solving simultaneously, rather than by reading values off the graph, we have that: xA= (1800/22) = 81.8 xB= 0.4xA = 32.7 with the value of the objective function being £408.9 274 CU IDOL SELF LEARNING MATERIAL (SLM)

Doubling the assembly time available means that the assembly time constraint (currently 12xA + 25xB <= 1800) becomes 12xA + 25xB <= 2(1800) This new constraint will be parallel to the existing assembly time constraint so that the new optimal solution will lie at the intersection of 12xA + 25xB = 3600 and xB - 0.4xA = 0 i.e. at xA = (3600/22) = 163.6 xB= 0.4xA = 65.4 with the value of the objective function being £817.8 Hence we have made an additional profit of £(817.8-408.9) = £408.9 and this is the maximum amount we would be prepared to pay for the hire of the machine for doubling the assembly time. Example 14: A carpenter makes tables and chairs. Each table can be sold for a profit of £30 and each chair for a profit of £10. The carpenter can afford to spend up to 40 hours per week working and takes six hours to make a table and three hours to make a chair. Customer demand requires that he makes at least three times as many chairs as tables. Tables take up four times as much storage space as chairs and there is room for at most four tables each week. Formulate this problem as a linear programming problem and solve it graphically. Solution: Let xT = number of tables made per week xC = number of chairs made per week 275 CU IDOL SELF LEARNING MATERIAL (SLM)

Constraints Total work time 6xT + 3xC <= 40 Customer demand xC >= 3xT storage space (xC/4) + xT <= 4 all variables >= 0 maximise 30xT + 10xC The graphical representation of the problem is given below and from that we have that the solution lies at the intersection of (xC/4) + xT = 4 and 6xT + 3xC = 40 Solving these two equations simultaneously we get xC = 10.667, xT = 1.333 and the corresponding profit = £146.667 276 CU IDOL SELF LEARNING MATERIAL (SLM)

9.4 SUMMARY • In operations analysis, many functional problems can be represented as linear programming problems. • Linear Programming Problems can be solved using a graphical way. • Linear programming is widely used in the optimization field for a variety of reasons. • Owing to the importance of linear programming models in various industries, many types of algorithms have been developed over the years to solve them. Some famous mentions include the Simplex method, the Hungarian approach, and others. Here we are going to concentrate on one of the most basic methods to handle a linear programming problem i.e. the graphical method. 277 CU IDOL SELF LEARNING MATERIAL (SLM)

• In principle, this method works for almost all different types of problems but gets more and more difficult to solve when the number of decision variables and the constraints increases. • Steps in graphical method Step 1: Formulate the LP (Linear programming) problem Step 2: Construct a graph and plot the constraint lines Step 3: Determine the valid side of each constraint line Step 4: Identify the feasible solution region Step 5: Plot the objective function on the graph 9.5 KEYWORD • Convex set: A convex set is a set of elements from a vector space such that all the points on the straight line line between any two points of the set are also contained in the set. • Unbounded Solution If the value of the objective function can be increased or decreased indefinitely; such solutions are called unbounded solutions. • Graphical Solution of a LPP The solution of a LPP obtained by graphical method • Corner point: A point in the feasible region that is the intersection of two boundary lines • Simplex method: The simplex method is a systematic procedure for testing the vertices as possible solutions 278 CU IDOL SELF LEARNING MATERIAL (SLM)

9.6 LEARNING ACTIVITY 1. A firm manufactures two types of products A and B and sells them at profit of Rs 2 on type A and Rs 3 on type B. Each product is processed on two machines M1 and M2.Type A requires 1 minute of processing time on M1 and 2 minutes on M2 Type B requires 1 minute of processing time on M1 and 1 minute on M2. Machine M1 is available for not more than 6 hours 40 minutes while machine M2 is available for 10 hours during any working day. Formulate the problem as a LPP so as to maximize the profit. ___________________________________________________________________________ _____________________________________________________________________ 2. A company manufactures two types of products P1, P2.Each product uses lathe and Milling machine. The processing time per unit of P1 on the lathe is 5 hours and on the milling machine is 4 hours. The processing time per unit of P2 on the lathe is 10 hours and on the milling machine, 4 hours. The maximum number of hours available per week on the lathe and the milling machine are 60 hours and 40 hours, respectively. Also, the profit per unit of selling P1 and P2 are Rs.6.00 and Rs.8.00, respectively. Formulate a linear programming model to determine the production volume of each of the products such that the total profit is maximized. ___________________________________________________________________________ ____________________________________________________________________ 279 CU IDOL SELF LEARNING MATERIAL (SLM)

9.7 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. How do you solve the graphical method in LPP? 2. What are the limitations of graphical method of LPP? 3. What are the advantages of graphical method? 4. When can you use graphical method of linear programming? 5. What are the different kinds of solutions in graphical method? Long Questions 1. Solve to LPP by graphical method (a) Maximize Z = 3x + 5y, subject to x + 4y ≤ 24, 3x + y ≤ 21, x + y ≤ 9, and x ≥ 0, y ≥ 0 2. Solve to LPP by graphical method (a) Maximize Z = 4x + 6y, subject to 3x + 2y ≤ 12, x + y ≥ 4, and x, y ≥ 0 3. Solve to LPP (a) Maximize Z = 7x + 11y, subject to 280 CU IDOL SELF LEARNING MATERIAL (SLM)

3x + 5y ≤ 26, 5x + 3y ≤ 30, and x ≥ 0, y ≥ 0 4. Solve to LPP by graphical method (a) Maximize Z = 6x + 4y, subject to x ≤ 2, x + y ≤ 3, -2x + y ≤ 1, and x ≥ 0, y ≥ 0 5. Solve to LPP (a) Maximize Z = 10 x1 + 25 x2 subject to 0 ≤ x1 ≤ 3, 0 ≤ x2 ≤ 3, x1 + x2 ≤ 5. B. Multiple Choice Questions 1. In equation 3x – y ≥ 3 and 4x – 4y > 4 a.Have solution for positive x and y b. Have no solution for positive x and y c. Have solution for all x d. Have solution for all y 2. The feasible region for a LPP is shown shaded in the figure. Let Z = 3x – 4y be the objective function. Minimum of Z occurs at 281 CU IDOL SELF LEARNING MATERIAL (SLM)

a. (0, 0) b. (0, 8) c. (5, 0) d. (4, 10) 3. Z = 6x + 21 y, subject to x + 2y ≥ 3, x + 4y ≥ 4, 3x + y ≥ 3, x ≥ 0, y ≥ 0. The minimum value of Z occurs at a. (4, 0) b. (28, 8) c. (2, 7/2) d. (0, 3) 282 CU IDOL SELF LEARNING MATERIAL (SLM)

4. The maximum value of the object function Z = 5x + 10 y subject to the constraints x + 2y ≤ 120, x + y ≥ 60, x – 2y ≥ 0, x ≥ 0, y ≥ 0 is a. 300 b.600 c.400 d.800 5. The maximum value of Z = 4x + 2y subject to the constraints 2x + 3y ≤ 18, x + y ≥ 10, x, y ≤ 0 is a.36 b.40 c.30 d. None of these Answers 1-a, 2-b, 3-c. 4-b, 5-a 9.8 REFERENCES References book ● Taha, H.A., “Operations Research: An Introduction”, 9th Edition, Pearson Education, Asia, New Delhi, 2016. 283 CU IDOL SELF LEARNING MATERIAL (SLM)

● Vittal, P.R, “Allied Mathematics”, Reprint,Margham Publications, Chennai. ● Venkata chalapathy, S.G, “Allied Mathematics”, Margham Publications, Chennai. Textbook references ● Singaravelu, A. “Allied Mathematics”, Meenakshi Agency, Chennai. ● Hennoy G.V. and Srivastava U.K., “Operation Research for Management”, Wiley Eastern,1994. ● Bazara M.J., Jarvis and Sherali H., “Linear Programming and Network Flows”, John Wiley,1990. ● Philip D.T. and Ravindran A., “Operations Research”, John Wiley, 1992. ● Hillier and Libeberman, “Operations Research”, Holden Day, 1986. 284 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT - 10: DIFFERENT TYPES OF LINEAR PROGRAMMING (L.P.) PROBLEMS 3 STRUCTURE 10.0 Learning Objectives 10.1 Introduction 10.2 Feasible and infeasible region and solutions 10.3 Optimal feasible solutions 10.4 Summary 10.5 Keywords 10.6 Learning Activity 10.7 Unit End Questions 10.8 References 10.0 LEARNING OBJECTIVES After studying this unit, you will be able to: ● Explain the basic concepts of optimization and linear modelling ● Identify the critical features of linear programming ● Explain why it is critical for business operations success. 285 CU IDOL SELF LEARNING MATERIAL (SLM)

● Solve LP problems with both maximization and minimization objectives, using graphical methods ● Define the LPP assumptions and contents ● Explain the mathematical background of LP 10.1 INTRODUCTION Optimization is the way of life. We all have finite resources and time and we want to make the most of them. From using your time productively to solving supply chain problems for your company everything uses optimization. It’s an especially interesting and relevant topic in data science. It's also a fascinating subject; it begins with simple difficulties but quickly becomes more complex. Sharing a bar of chocolate with siblings, for example, is a straightforward optimization problem. When we solve it, we don't think in mathematical terms. On the other hand, developing an e-inventory tailer's and storage plan can be quite difficult. Millions of SKUs, each with a varying level of popularity in different locations, must be delivered within a certain amount of time and resources - you get the picture. One of the most basic methods of optimization is linear programming (LP). By making a few simplifying assumptions, it can assist you in solving some highly complex optimization issues. As an analyst, you'll almost certainly come across applications and challenges that Linear Programming can handle. For some reason, LP doesn't get the respect it deserves when it comes to understanding data science. So I decided to give this amazing technology its due. I made the decision to produce an article explaining linear programming in plain English. I tried to keep the content as 286 CU IDOL SELF LEARNING MATERIAL (SLM)

straightforward as possible. The goal is to get you enthused about Linear Programming and get you started. 10.2 FEASIBLE OR INFEASIBLEREGION AND SOLUTIONS Location of Optimum The efficiency and reliability of LP solution techniques depend upon a strong statement about the location of the optimum in an LP problem. The statement involves corner point locations in the feasible region. Corner Point: A point is a corner point (p) if every line segment in the set (feasible region) containing p has p as an endpoint. When explaining linear programming, various references use the following terms, all having the same meaning: corner point, extreme point, and vertex Consider a linear programming problem with feasible solutions and a bounded region. The optimal value of the objective function is located at a corner-point solution! Thus, if the problem has one optimal solution, it must be a corner point (vertex); if it has multiple optimal solutions, at least two must be located at corner points (vertices). In addition to the global optimum the solution method that we will learn determines the following: Feasible or infeasible: 287 CU IDOL SELF LEARNING MATERIAL (SLM)

We need to determine whether a feasible region exists or does not exist (no solution). This could be due to a formulation error or a very stringent performance requirement. For example, we might require a reactor product yield of over 60%, while the maximum achievable is less than 60% because of side reactions. 288 CU IDOL SELF LEARNING MATERIAL (SLM)

Bounded or unbounded: We need to determine whether the optimum values of one or more variables are unbounded (giving an objective value of ±∞ occurs)If this the problem formulation is in error, because no real system has variables with infinite range. Unique or alternative: The unique optimum value of the objective occurs at a corner point, as indicated above. However, an “edge” intersecting the corner point could have the same value of the objective. Basic Feasible Solution: A Basic feasible solution is a basic solution which also satisfies the non-negativity restrictions. Working Rule for Marking Feasible Region 289 CU IDOL SELF LEARNING MATERIAL (SLM)

Consider the constraint ax + by ≤ c, where c > 0. First draw the straight line ax + by = c by joining any two points on it. For this find two convenient points satisfying this equation. This straight line divides the xy-plane in two parts. The inequation ax + by c will represent that part of the xy-plane which lies to that side of the line ax + by = c in which the origin lies. Again, consider the constraint ax + by ≥ c, where c > 0. Draw the straight line ax + by = c by joining any two points on it. This straight line divides the xy-plane in two parts. The inequation ax + by ≥ c will represent that part of the xy-plane, which lies to that side of the line ax + by = c in which the origin does not lie. 10.3 OPTIMUM BASIC FEASIBLE SOLUTION Optimum Basic Feasible Solution A Basic feasible solution is said to be optimum, if it also optimizes (Max or min) the objective function. Example 1: Solve to LPP Solution: 290 CU IDOL SELF LEARNING MATERIAL (SLM)

291 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 2: 292 CU IDOL SELF LEARNING MATERIAL (SLM)

Solution: 293 CU IDOL SELF LEARNING MATERIAL (SLM)

294 CU IDOL SELF LEARNING MATERIAL (SLM)

295 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 3: 296 CU IDOL SELF LEARNING MATERIAL (SLM)

Solution: 297 CU IDOL SELF LEARNING MATERIAL (SLM)

298 CU IDOL SELF LEARNING MATERIAL (SLM)

299 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 4: Solution: 300 CU IDOL SELF LEARNING MATERIAL (SLM)