CU-BCA-SEM-I-Mathematics (1)

Solution: Example 3: Solution: 151 CU IDOL SELF LEARNING MATERIAL (SLM)

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

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

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

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

Example 8: Solution: 156 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. 157 CU IDOL SELF LEARNING MATERIAL (SLM)

Solution: 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. 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 158 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. 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. 159 CU IDOL SELF LEARNING MATERIAL (SLM)

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 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 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 160 CU IDOL SELF LEARNING MATERIAL (SLM)

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 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 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 161 CU IDOL SELF LEARNING MATERIAL (SLM)

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 Example 12: 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). 162 CU IDOL SELF LEARNING MATERIAL (SLM)

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 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 163 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 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 164 CU IDOL SELF LEARNING MATERIAL (SLM)

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 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 165 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 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 166 CU IDOL SELF LEARNING MATERIAL (SLM)

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 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 167 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. • 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 168 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. ___________________________________________________________________________ ____________________________________________________________________ 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 169 CU IDOL SELF LEARNING MATERIAL (SLM)

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 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 170 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) 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 171 CU IDOL SELF LEARNING MATERIAL (SLM)

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. ● 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. 172 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. ● 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 173 CU IDOL SELF LEARNING MATERIAL (SLM)

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 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: 174 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. 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. 175 CU IDOL SELF LEARNING MATERIAL (SLM)

Working Rule for Marking Feasible Region 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: 176 CU IDOL SELF LEARNING MATERIAL (SLM)

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

Solution: 178 CU IDOL SELF LEARNING MATERIAL (SLM)

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

Solution: 180 CU IDOL SELF LEARNING MATERIAL (SLM)

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

182 CU IDOL SELF LEARNING MATERIAL (SLM)

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

184 CU IDOL SELF LEARNING MATERIAL (SLM)

10.4 SUMMARY ● A feasible solution to a linear program is a solution that satisfies all constraints. ● An optimal solution to a linear program is the feasible solution with the largest objective function value (for a maximization problem) ● A linear program is infeasible if there exists no solution that satisfies all of the constraints -- in other words, if no feasible solution can be constructed ● A solution region of a system of linear inequalities is bounded if it can be enclosed within a circle. If it cannot be enclosed within a circle, it is unbounded. 10.5 KEYWORD • Corner (or Extreme) Point. A point that lies on one of the corners of the feasible region. This means that it falls at the intersection of two constraint lines. • Corner Point Method. The method of finding the optimal solution to an LP problem by testing the profit or cost level at each corner point of the feasible region. The theory of LP states that the optimal solution must lie at one of the corner points. • Decision Variables. The unknown quantities in the problem for which optimal solution values are to be found • Infeasibility. A condition that arises when there is no solution to an LP problem that satisfies all of the constraints. 10.6 LEARNING ACTIVITY 1. Consider a chocolate manufacturing company that produces only two types of chocolate – A and B. Both the chocolates require Milk and Choco only. To manufacture each unit of A and B, the following quantities are required: 185 CU IDOL SELF LEARNING MATERIAL (SLM)

Each unit of A requires 1 unit of Milk and 3 units of Choco Each unit of B requires 1 unit of Milk and 2 units of Choco The company kitchen has a total of 5 units of Milk and 12 units of Choco. On each sale, the company makes a profit of Rs 6 per unit A sold Rs 5 per unit B sold. Now, the company wishes to maximize its profit. How many units of A and B should it produce respectively? ___________________________________________________________________________ ___________________________________________________________________________ 2.A toy Company manufactures two types of doll, a basic version –doll A and a deluxe version-doll B. Each doll of type B takes twice as long to produce as one of type A, and the company have time to make a maximum of 2000 per day. The supply of plastic is sufficient to produce 1500 dolls per day (both A and B combined). The deluxe version requires a fancy dress of which there are only 600 per day available. If the company makes a profit of Rs.3.00 and Rs.5.00 per doll, respectively on doll A and B, then how many of each doll should be produced per day in order to maximize the total profit. Formulate this problem and discuss the components of decision problem. ___________________________________________________________________________ _____________________________________________________________________ 10.7 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. What is bounded and unbounded solution in LPP? 2. How can you say the LPP has an unbounded solution? 3. What is a optimal solution? 4. What is basic feasible solution in simplex method? 5. What is degenerate basic feasible solution? Long Questions 1. A bolt manufacturing organization manufactures two types of toys A and B. Both the bolts are sold at Rs.25 and Rs.20 respectively. There are 2000 resource units available every day from which the bolt A requires 20 units while bolt B requires 12 units. Both 186 CU IDOL SELF LEARNING MATERIAL (SLM)

of these toys require a production time of 5 minutes. Total working hours are 9 hours a day. What should be the manufacturing quantity for each of the pipes to maximize the profits? 2. Solve to maximize the profit function Z = 40x + 15y, subject to constraints, (a) x+2y ≤ 100 x+2y ≤ 70 x, y ≥ 0 3. Examine the Linear programming problem. Maximize Z = 3x1 + 5x2 Subject to x1 + x2 ≤ 8, x1 + 3x2 ≤12 x1 , x2 ≥ 0. 4. Solve the following LPP by graphical Method. Maximize Z = 3x1 + 2x2 Subject to -2x1 + x2 ≤ 1, x1 ≤2 x1 + x2 ≤ 3, x1 , x2 ≥ 0. 5. 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. Create a linear programming model to determine the production volume of each of the products such that the total profit is maximized. and also solve. B. Multiple Choice Questions 1. Which technique is used in finding a solution for optimizing a given objective, such as profit maximization or cost reduction under certain constraints? 187 CU IDOL SELF LEARNING MATERIAL (SLM)

a. Quailing Theory b. Waiting Line c. Both A and B d. Linear Programming 2. What have been constructed from OR problems an methods for solving the models that are available in many cases? a. Scientific Models b. Algorithms c. Mathematical Models d. None of these 3. What is the objective function in linear programming problems? a. A constraint for available resource b. An objective for research and development of a company c. A linear function in an optimization problem d. A set of non-negativity conditions 4. Which statement characterizes standard form of a linear programming problem? a. Constraints are given by inequalities of any type b. Constraints are given by a set of linear equations c. Constraints are given only by inequalities of >= type d. Constraints are given only by inequalities of <= type 5. Feasible solution satisfies __________ a. Only constraints b. only non-negative restriction c. [a] and [b] both d. [a],[b] and Optimum solution Answers 1-d, 2-c, 3-c. 4-a, 5-c 188 CU IDOL SELF LEARNING MATERIAL (SLM)

10.8 REFERENCES References book ● Taha, H.A., “Operations Research: An Introduction”, 9th Edition, Pearson Education, Asia, New Delhi, 2016. ● 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. 189 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT - 11: COMBINATIONS 1 STRUCTURE 11.0 Learning Objectives 11.1 Introduction 11.2 Basics of counting Principle 11.3 Permutations. 11.4 Summary 11.5 Keywords 11.6 Learning Activity 11.7 Unit End Questions 11.8 References 11.0 LEARNING OBJECTIVES After studying this unit, you will be able to: ● Learn to Set up and compute factorials ● Apply and calculate permutations ● Learn to count using the fundamental counting principle ● Describe the notion of permutations. ● Explain to Count in accordance with the basic counting principle 11.1 INTRODUCTION A new startup sells tablet and smartphone cases that may be customised. Each case is available in a range of colours and may be personalised with photos or a monogram for an extra charge. Customers can opt to have no personalization or one, two, or three photos or a monogram. The order of the photos and letters in the monogram can be customised by the buyer. The company is collaborating with a marketing agency to create a campaign that highlights the vast array of possibilities available. It's difficult to keep track of all the choices! Every day, we come across a wide range of counting challenges. This type of counting problem is studied in an area of mathematics called combinatorics. Other applications of counting include secure passwords, horse racing outcomes, and college scheduling choices. We will examine this type of mathematics in this section. The Counting Principle: 190 CU IDOL SELF LEARNING MATERIAL (SLM)

Consider option A, which has three alternatives (A1,A2,A3), and option B, which has two options (B1,B2). The total number of alternatives would be 32=6 if you had to choose an option from A and then an option from B. A1B1, A1B2, A2B1, A2B2, A3B1, A3B2 are the alternatives. Using the Fundamental Counting Principle and a decision tree, you can figure out where the 6 comes from. A decision tree is a graph that represents the many alternatives available at each stage of a study. To create a decision tree, first figure out how many decisions you'll be making. There are only two options available here: You will have two \"slots\" in your choice tree if you 1) choose an option from A and 2) choose an option from B. Next, think about how many possibilities there are for the 1st choice (in this case there are 3), and how many possibilities there are for the 2nd choice (in this case there are 2). The Fundamental Counting Principle says that you can multiply those numbers together to get the total number of outcomes. The Multiplication Principle can be used to solve a variety of problem types. One type of problem involves placing objects in order. We arrange letters into words and digits into numbers, line up for photographs, decorate rooms, and more. An ordering of objects is called a permutation. For some permutation problems, it is inconvenient to use the Multiplication Principle because there are so many numbers to multiply. Fortunately, we can solve these problems using a formula. Before we learn the formula, let’s look at two common notations for permutations. If we have a set of n objects and we want to choose r objects from the set in order, we write P(n,r). Another way to write this is nPr, a notation commonly seen on computers and calculators. To calculate P(n, r), we begin by finding n!, the number of ways to line up all n objects. We then divide by (n−r)! to cancel out the (n−r) items that we do not wish to line up. Let’s see how this works with a simple example. Imagine a club of six people. They need to elect a president, a vice president, and a treasurer. Six people can be elected president, any one of the five remaining people can be elected vice president, and any of the remaining four people could be elected treasurer. The number of ways this may be done is 6×5×4=120. Using factorials, we get the same result. 6!3!=6⋅5⋅4⋅3!3!=6⋅5⋅4=120 191 CU IDOL SELF LEARNING MATERIAL (SLM)

There are 120 ways to select 3 officers in order from a club with 6 members. We refer to this as a permutation of 6 taken 3 at a time. The general formula is as follows. P(n, r)=n!/(n−r)! 11.2 THE FUNDAMENTAL COUNTING PRINCIPLE Definition of n Factorial: (n !)n! = n(n-1)(n-2)(n-3)…1 For example, 5! = 5(4)(3)(2)(1) = 1200! = 1 by definition. Fundamental counting Principle: Recall that the theoretical probability of an event E is P(E)=number of outcomes in E / size of sample space. To compute such probabilities, we must be able to enumerate the number of possible possibilities. This isn't always easy. Assume you're dealt a five-card draw poker hand from a normal deck. What is the sample space's size, or the total number of possible hands? We’ll have three counting techniques. The simplest, and the foundation for many more sophisticated techniques, is the Fundamental Counting Principle, sometimes called the Multiplication Rule. It is very simple: if there are m ways to do a task, say, Task 1, and n ways to then do another task, Task 2, then there are m⋅n ways to do first Task 1 and then Task 2. Example 1: John wants to give a novel and a cookbook to his friend. He has four different novels and three different cookbooks to choose from. How many different choices can he make? Solution: John has two assignments: choose a novel and a cookbook. He has four distinct novels from which to choose, so he has four options; he has three recipes from which to choose, so he has three options. As a result, he has 43=12 options for selecting a novel and subsequently a cookbook. Example 2: The Thursday special at Lisa’s Pizza is a large pizza with any combination of toppings (but no more than one of each). The available toppings are pepperoni, mushrooms, onions, sausage, peppers, olives, and pineapple. How many different Thursday specials can be ordered? Solution: 192 CU IDOL SELF LEARNING MATERIAL (SLM)

Think of ordering a Thursday special as a sequence of seven different tasks: choose whether or not to have pepperoni, then choose whether or not to have mushrooms, and so on. There are two choices for each task, so there are 2⋅2⋅2⋅2⋅2⋅2⋅2=27=128 different ways to order. Example 3: You are going on a road trip with 4 friends in a car that fits 5 people. How many different ways can everyone sit if you have to drive the whole way? Solution: The Fundamental Counting Principle is an excellent way to approach this issue. You must take the wheel of the vehicle. For the first passenger seat, there are four alternatives. There are three alternatives for the next passenger seat once that individual is seated. This goes on until there is one person left with 1 seat. 1⋅4⋅3⋅2⋅1=24 Example 4: How many different 4-digit ATM passwords are there? Assume you can repeat digits. Solution: It is true that order is important. There are ten digits, and you can repeat them as many times as you want. Each of the four alternatives may be solved using the Fundamental Counting Principle. 10⋅10⋅10⋅10=10,000 11.3 PERMUTATION Definitions: A permutation of some objects is an arrangement of those objects in a definite order. For any positive integer n, we define n factorial, denoted n!, to be the product of all the positive integers up to and including n itself. That is, n!=n(n−1)(n−2)⋯(2)(1) Number of Permutations: 193 CU IDOL SELF LEARNING MATERIAL (SLM)

The number of permutations of r objects chosen from among n different objects is nPr=n!/(n−r)! Example 1: It is obvious that if you have two different pool balls, there are two ways to arrange them in a row: But what if there were three balls, or four, or twelve? Consider placing the balls as a sequence of two tasks: first choose the left ball, then choose the right ball to see how to find the answer for any number of balls. There are two options for the left ball, but only one for the right, so there are a total of 2 1=2 ways to arrange the balls. Similarly, if you have three balls, you can arrange them in any of the following ways: An arrangement of objects in a definite order is called a permutation of those objects. We’ve just seen that there are two possible permutations of two different objects and six possible permutations of three different objects. These examples make it clear that if we have n different objects, then there are n(n−1)(n−2)⋯(2)(1) possible permutations of those objects. Clearly there are n! possible permutations of n different objects. We need to push this just a little further. Suppose we have five pool balls and a box with only three slots. Assuming that the order of the balls in the box matters, in how many different ways could we choose three balls to put in the box? This is not much different from the earlier question: we have five choices for the first ball, then four for the second, and then three for the third, so there are 5⋅4⋅3=60 ways to choose the three balls. Notice that 5⋅4⋅3=5!/(5−3)!, which leads to the following formula: So, for example, 5P3=5!/(5−3)!=5⋅4⋅3=60. Note: Sometimes nPr is written P(n,r). You need to know both notations. 194 CU IDOL SELF LEARNING MATERIAL (SLM)

The notation P(n,r) represents the number of permutations (arrangements) of n objects taken r at a time, where r is less than or equal to n. In a permutation, the order is important P(n,r) may also be written P(n,r) or nPr Example 2: In our example with the number of two letter words from {p, e, n}, the answer is P3,2, which represents the number of permutations of 3 objects taken 2 at a time.P3,2 = 6 How many different ways can the gold, silver, and bronze medals be awarded in an Olympic event with 12 athletes competing? Solution: Since the order does matter with the 3 medals, this is a permutation problem. You will start with 12 athletes and then choose and arrange 3 different winners. 12P3=12!(12−3)!=12!9!=12⋅11⋅10⋅9⋅…9⋅…=12⋅11⋅10=1,32012P3=12!(12−3)!=12!9!=12⋅11⋅ 10⋅9⋅…9⋅…=12⋅11⋅10=1,320 You may also use the Fundamental Counting Principle to figure out how many gold possibilities there are (12), how many silver possibilities there are (11, since one already possesses gold), and how many bronze possibilities there are (10). Any permutation problem can be solved using the Fundamental Counting Principle. 12⋅11⋅10=1,320 Example 3: How many outcomes are possible when three dice are rolled, if no two of them may be the same? Solution: The first two dice together have 6 · 5 = 30 possible outcomes, from above. For each of these 30 outcomes, there are four possible outcomes for the third die, so the total number of outcomes is 30 · 4 = 6 · 5 · 4 = 120. (Note that we consider the dice to be distinguishable, 195 CU IDOL SELF LEARNING MATERIAL (SLM)

that is, a roll of 6, 4, 1 is different than 4, 6, 1, because the first and second dice are different in the two rolls, even though the numbers as a set are the same.) Example 4: Suppose blocks numbered 1 through n are in a barrel; we pull out k of them, placing them in a line as we do. How many outcomes are possible? That is, how many different arrangements of k blocks might we see? Solution: This is essentially the same as the previous example: there are k “spots” to be filled by blocks. Any of the n blocks might appear first in the line; then any of the remaining n − 1 might appear next, and so on. The number of outcomes is thus n(n−1)(n−2)· · ·(n−k+1), by the multiplication principle. In the previous example, the first “spot” was die number one, the second spot was die number two, the third spot die number three, and 6 · 5 · 4 = 6(6 − 1)(6 − 2); notice that 6 − 2 = 6 − 3 + 1. This is quite a general sort of problem: Example 5: The number of permutations of n things taken k at a time is P(n, k) = n(n − 1)(n − 2)· · ·(n − k + 1) = n! /(n − k)!. A permutation of some objects is a particular linear ordering of the objects; P(n, k) in effect counts two things simultaneously: the number of ways to choose and order k out of n objects. A useful special case is k = n, in which we are simply counting the number of ways to order all n objects. This is n(n − 1)· · ·(n − n + 1) = n!. Note that the second form of P(n, k) from the definition gives n! /(n − n)! = n!/ 0! . This is correct only if 0! = 1, so we adopt the standard convention that this is true, that is, we define 0! to be 1. Suppose we want to count only the number of ways to choose k items out of n, that is, we don’t care about order. Example 6: How many ways are there to line up six people so that a particular pair of people are not adjacent? Solution: 196 CU IDOL SELF LEARNING MATERIAL (SLM)

Denote the people A and B. The total number of orders is 6!, but this counts those orders with A and B next to each other. How many of these are there? Think of these two people as a unit; how many ways are there to line up the AB unit with the other 4 people? We have 5 items, so the answer is 5!. Each of these orders corresponds to two different orders in which A and B are adjacent, depending on whether A or B is first. So the 6! count is too high by 2 · 5! and the count we seek is 6! − 2 · 5! = 4 · 5!. Example 7: Six people are to sit at a round table; how many seating arrangements are there? Solution: It is not clear exactly what we mean to count here. If there is a “special seat”, for example, it may matter who ends up in that seat. If this doesn’t matter, we only care about the relative position of each person. Then it may or may not matter whether a certain person is on the left or right of another. So this question can be interpreted in (at least) three ways. Let’s answer them all. First, if the actual chairs occupied by people matter, then this is exactly the same as lining six people up in a row: 6 choices for seat number one, 5 for seat two, and so on, for a total of 6!. If the chairs don’t matter, then 6! Counts the same arrangement too many times, once for each person who might be in seat one. So the total in this case is 6!/6 = 5!. Another approach to this: since the actual seats don’t matter, just put one of the six people in a chair. Then we need to arrange the remaining 5 people in a row, which can be done in 5! ways. Finally, suppose all we care about is who is next to whom, ignoring right and left. Then the previous answer counts each arrangement twice, once for the counterclockwise order and once for clockwise. So the total is 5!/2 = P(5, 3). We have twice seen a general principle at work: if we can over count the desired set in such a way that every item gets counted the same number of times, we can get the desired count just by dividing by the common over count factor. This will continue to be a useful idea. A variation on this theme is to over count and then subtracts the amount of over count. 11.4 SUMMARY • Fundamental principle of counting :If an event can occur in m different ways, following which another event can occur in n different ways, then the total number of occurrence of the events in the given order is m × n. ®The number of permutations of 197 CU IDOL SELF LEARNING MATERIAL (SLM)

n different things taken r at a time, where repetition is not allowed, is denoted by nPr and is given by nPr = , where 0 ≤ r ≤ n. • n! = 1 × 2 × 3 × ...×n .n! = n × (n – 1) ! The number of permutations of n different things, taken r at a time, where repetition is allowed, is n r . • The number of permutations of n objects taken all at a time, where p1 objects. According to the Fundamental Counting Principle, if one event has m possible outcomes and a second event has n possible outcomes, the two occurrences together have mn total possible possibilities. • A permutation is the number of possible combinations for selecting and arranging k things from a set of n objects. nPk=k!(n, k)=k!⋅(n!/k!(n−k)!)=n!/(n−k)! 11.5 KEYWORD ● Permutation: a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order. ● Combination: A combination is a mathematical technique that determines the number of possible arrangements in a collection of items where the order of the selection does not matter. ● Factorial: the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n:. ● Fundamental principle of counting: The fundamental counting principle is a rule used to count the total number of possible outcomes in a situation ● Pigeon hole principle: Suppose that n+1 (or more) objects are put into n boxes. Then some box contains at least two objects. 11.6 LEARNING ACTIVITY 1. How many ways can all nine swimmers line up for a photo? ___________________________________________________________________________ _____________________________________________________________________ 2. Explain how 0!=1 ? ___________________________________________________________________________ _____________________________________________________________________ 198 CU IDOL SELF LEARNING MATERIAL (SLM)

11.7 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. Simplify each of the following expressions so that they do not have a factorial symbol 7!3! 110!105!5! 2. Simplify each of the following expressions so that they do not have a factorial symbol 52!49! 3. In how many ways can you choose 3 objects from a set of 9 objects? 4. In how many ways can you choose and arrange 4 objects from a set of 15 objects? 5. First state whether each problem is a permutation/decision tree problem or a combination problem. Long Questions 1. Suppose you need to choose a new combination for your combination lock. You have to choose 3 numbers, each different and between 0 and 40. How many permutations are there? 2. You just won a contest where you can choose 2 friends to go with you to a concert. You have 5 friends who are available and want to go. In how many ways can you choose the friends? 3. You want to construct a 3-digit number from the digits 4, 6, 8, 9. How many possible numbers are there? 4. There are 12 workshops at a conference, and Sam has to choose 3 to attend. In how many ways can he choose the 3 to attend? 5. A contest has 9 girls and 5 boys as finalists. In how many ways can 1st-, 2nd-, and 3rd-place winners be chosen? B. Multiple Choice Questions 1. In how many ways can 4 books be chosen from a group of nine? a. 126 b. 127 c. 125 d. 124 199 CU IDOL SELF LEARNING MATERIAL (SLM)

2. A restaurant offers butter, cheese, chives, and sour cream as toppings for a baked potato. How many different ways are there to order a potato? a. 15 b. 16 c. 14 d. 13 3. A person going to a party was asked to bring 3 different bags of chips. Going to the store, she finds 12 varieties. a. 220 b. 215 c. 210 d. 225 4. How many ways can you select your side dishes? a. 15 b. 10 c. 20 d. 25 5. How many ways can you select 3 side dishes? a. 10 b. 15 c. 20 d. 25 6. Find the number of distinguishable permutations of the given letters \"AABCCDDD\". a. 1690 b. 1780 c. 1680 d. 1790 Answers 1-a, 2-b, 3-a. 4-b, 5-a, 6- c 200 CU IDOL SELF LEARNING MATERIAL (SLM)