CU-BBA-SEM-V-Operation Research-Second Draft

5.2 NWCM The North-West Corner Rule is a method adopted to compute the initial feasible solution of the transportation problem. The name North-west corner is given to this method because the basic variables are selected from the extreme left corner. Table 5.1: Sources and destinations Explanation: Given three sources O1, O2 and O3 and four destinations D1, D2, D3 and D4. For the sources O1, O2 and O3, the supply is 300, 400 and 500 respectively. The destinations D1, D2, D3 and D4 have demands 250, 350, 400 and 200 respectively. Solution: According to the North West Corner method, (O1, D1) has to be the starting point i.e. the north-west corner of the table. Each and every value in the cell is considered as the cost per transportation. Compare the demand for column D1 and supply from the source O1 and allocate the minimum of two to the cell (O1, D1) as shown in the figure. The demand for Column D1 is completed so the entire column D1 will be cancelled. The supply from the source O1 remains 300 – 250 = 50. 101 CU IDOL SELF LEARNING MATERIAL (SLM)

Table 5.2: Sources and destinations excluding column D1 Now from the remaining table i.e. excluding column D1, check the north-west corner i.e. (O1, D2) and allocate the minimum among the supply for the respective column and the rows. The supply from O1 is 50 which is less than the demand for D2 (i.e. 350), so allocate 50 to the cell (O1, D2). Since the supply from row O1 is completed, cancel the row O1. The demand for column D2 remains 350 – 50 = 300. Table 5.3: Sources and destinations excluding column D1 and row O1 From the remaining table the north-west corner cell is (O2, D2). The minimum among the supply from source O2 (i.e. 400) and demand for column D2 (i.e. 300) is 300, so allocate 300 102 CU IDOL SELF LEARNING MATERIAL (SLM)

to the cell (O2, D2). The demand for the column D2 is completed so cancel the column and the remaining supply from source O2 is 400 – 300 = 100. Table 5.4: Sources and destinations excluding column D1, D2 and row O1 Now from remaining table find the north-west corner i.e. (O2, D3) and compare the O2 supply (i.e. 100) and the demand for D2 (i.e. 400) and allocate the smaller (i.e. 100) to the cell (O2, D2). The supply from O2 is completed so cancel the row O2. The remaining demand for column D3 remains 400 – 100 = 300. Table 5.5: Sources and destinations excluding column D1, D2 and rows O1, O2 Proceeding in the same way, the final values of the cells will be: 103 CU IDOL SELF LEARNING MATERIAL (SLM)

Table 5.6: Sources and destinations excluding column D1, D2, D3, D4 and row O1, O2 Note: In the last remaining cell the demand for the respective columns and rows are equal which was cell (O3, D4). In this case, the supply from O3 and the demand for D4 was 200 which was allocated to this cell. At last, nothing remained for any row or column. Now just multiply the allocated value with the respective cell value (i.e. the cost) and add all of them to get the basic solution i.e. (250 * 3) + (50 * 1) + (300 * 6) + (100 * 5) + (300 * 3) + (200 * 2) = 4400 5.3 LCM AND VAM Least Cost Method (LCM) The Least Cost Method is another method used to obtain the initial feasible solution for the transportation problem. Here, the allocation begins with the cell which has the minimum cost. The lower cost cells are chosen over the higher-cost cell with the objective to have the least cost of transportation. The Least Cost Method is considered to produce more optimal results than the North-west Corner because it considers the shipping cost while making the allocation, whereas the North- West corner method only considers the availability and supply requirement and allocation begins with the extreme left corner, irrespective of the shipping cost. Let’s understand the concept of Least Cost method through a problem given below: 104 CU IDOL SELF LEARNING MATERIAL (SLM)

Table 5.7: Source supply matrix In the given matrix, the supply of each source A, B, C is given Viz. 50 units, 40 units, and 60 units respectively. The weekly demand for three retailers D, E, F i.e. 20 units, 95 units and 35 units is given respectively. The shipping cost is given for all the routes. The minimum transportation cost can be obtained by following the steps given below: Table 5.8: Obtaining the minimum transport cost from the source supply matrix 1. The minimum cost in the matrix is Rs 3, but there is a tie in the cell BF, and CD, now the question arises in which cell we shall allocate. Generally, the cost where maximum quantity can be assigned should be chosen to obtain the better initial 105 CU IDOL SELF LEARNING MATERIAL (SLM)

solution. Therefore, 35 units shall be assigned to the cell BF. With this, the demand for retailer F gets fulfilled, and only 5 units are left with the source B. 2. Again the minimum cost in the matrix is Rs 3. Therefore, 20 units shall be assigned to the cell CD. With this, the demand of retailer D gets fulfilled. Only 40 units are left with the source C. 3. The next minimum cost is Rs 4, but however, the demand for F is completed, we will move to the next minimum cost which is 5. Again, the demand of D is completed. The next minimum cost is 6, and there is a tie between three cells. But however, no units can be assigned to the cells BD and CF as the demand for both the retailers D and F are saturated. So, we shall assign 5 units to Cell BE. With this, the supply of source B gets saturated. 4. The next minimum cost is 8, assign 50 units to the cell AE. The supply of source A gets saturated. 5. The next minimum cost is Rs 9; we shall assign 40 units to the cell CE. With this both the demand and supply of all the sources and origins gets saturated. The total cost can be calculated by multiplying the assigned quantity with the concerned cost of the cell. Therefore, Total Cost = 50*8 + 5*6 + 35*3 +20*3 +40*9 = Rs 955. Note: The supply and demand should be equal and in case supply are more, the dummy source is added in the table with demand being equal to the difference between supply and demand, and the cost remains zero. Similarly, in case the demand is more than supply, then a dummy destination or origin is added to the table with the supply equal to the difference in quantity demanded and supplied and the cost being zero. VAM-The Vogel’s Approximation Method or VAM is an iterative procedure calculated to find out the initial feasible solution of the transportation problem. Like the Least cost Method, here also the shipping cost is taken into consideration, but in a relative sense. The following is the flow chart showing the steps involved in solving the transportation problem using the Vogel’s Approximation Method: 106 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 5.1: Vogel’s Approximation Method The concept of Vogel’s Approximation Method can be well understood through an illustration given below: First of all the difference between two least cost cells are calculated for each row and column, which can be seen in the iteration given for each row and column. Then the largest difference is selected, which is 4 in this case. So, allocate 20 units to cell BD, since the minimum cost is to be chosen for the allocation. Now, only 20 units are left with the source B. 107 CU IDOL SELF LEARNING MATERIAL (SLM)

Table 5.9: Iteration given for each row and column Column D is deleted, again the difference between the least cost cells is calculated for each row and column, as seen in the iteration below. The largest difference value comes to be 3, so allocate 35 units to cell AF and 15 units to the cell AE. With this, the Supply and demand of source A and origin F gets saturated, so delete both the row A and Column F. Table 5.10: Deleting column D Now, single column E is left, since no difference can be found out, so allocate 60 units to the cell CE and 20 units to cell BE, as only 20 units are left with source B. Hence the demand and supply are completely met. 108 CU IDOL SELF LEARNING MATERIAL (SLM)

Table 5.11: Single column E is left Now the total cost can be computed, by multiplying the units assigned to each cell with the cost concerned. Therefore, Total Cost = 20*3 + 35*1 + 15*4 + 60*4 + 20*8 = Rs 555 Note: Vogel’s Approximation Method is also called as Penalty Method because the difference costs chosen are nothing but the penalties of not choosing the least cost routes. 5.4 OPTIMALITY TESTS Optimality test can be performed if two conditions are satisfied i.e. 1. There are m + n – 1 allocation, whose m is number of rows, n is number of columns. Here m + n – 1 =6. But the number of allocation is five. 2. These m + n – 1 allocation should be at independent positions. I.e. it should not be possible to increase or decrease any allocation without either changing the position of the allocations or violating the row or column restrictions. A simple rule for allocations to be in independent positions is that it is impossible to travel from any allocation, back to itself by a series of horizontal and vertical steps from one occupied cell to another, without a direct reversal of route. It can be seen that in the present example, allocations are at independent positions as no closed loop can be formed at the allocated cells. Therefore the first condition is not satisfied and therefore in order to satisfy the first condition, we will have to allocate a small amount E at the vacant cells having the lowest cost 109 CU IDOL SELF LEARNING MATERIAL (SLM)

of transportation. It can be seen that t can be allocated at cell (2, 2) having cost of 7 units and still the allocations will remain at independent position as described below: Table 5.12: Allocations Now the number of allocation is m + n- =6 and they are at independent positions. Write down the cost matrix at allocated cells. Table 5.13: Cost Matrix Initial cost matrix for allocated cells. Also write the values of ui and vj as explained earlier. Table 5.14: ui + vj matrix for non-allocated cells Table 5.15: Cell evaluation matrix 110 CU IDOL SELF LEARNING MATERIAL (SLM)

It can be seen from table above that cell evaluation at cell (1, 4) is negative i.e. -4, therefore by allocating at cell (1, 4) transportation cost be further reduced. Let us write down the original allocations and the proposed new allocation. Table 5.16: A loop is formed It can be seen from table above that if we allocate at cell (1, 4) a loop is formed as shown and we allocate 10 units so that allocation at cell (2, 4) vanishes as shown below in table Table 5.17: Allocation at cell (2, 4) vanishes New allocation Table will become Table 5.18: New allocation table Transportation cost = 5X2+10X11+10X7+15X9+5X4+18+5 =435 units. i.e., Transportation cost has come down from 475 units to 435 units. Check for Optimality: Let us see whether this solution is optimal! or not? For that again two conditions have to be checked i.e. No. of allocation = m + n – 1 =6 (satisfied) Allocation at independent position (satisfied since closed loop for allocated cells is not formed) Write cost at the allocated cells and values of ui and vj 111 CU IDOL SELF LEARNING MATERIAL (SLM)

Table 5.19: Write cost at the allocated cells and values of ui and vj Table 5.20: Cell evaluation matrix Table 5.21: Optimal solution 5.5 MODI METHOD The Modified Distribution Method or MODI is an efficient method of checking the optimality of the initial feasible solution. The concept of MODI can be further comprehended through an illustration given below: 1. Initial basic feasible solution is given below: 2. Now, calculate the values of ui and vj by using the equation: 112 CU IDOL SELF LEARNING MATERIAL (SLM)

ui+vj = Cij Table 5.22: Calculating ui and yj Substituting the value of u1 as 0 U1+V1 = C11, 0+V1 = 6 or V1 = 6 U1 +V2 = C12, 0+V2 = 4 or V2 = 4 U2+V2 = C22, U2+4 = 8 or U2 = 4 U3+ V2 = C32, U3+4 = 4 or U3 = 0 U3+V3 = C33, 0+V3 = 2 or V3 =2 113 CU IDOL SELF LEARNING MATERIAL (SLM)

Table 5.23: Substituting the value of u1 as 0 3. Next step is to calculate the opportunity cost of the unoccupied cells (AF, BD, BF, CD) by using the following formula: Cij – (ui+Vi) AF = C13 – (U1+V3), 1- (0+2) = -1 or 1 BD = C21 – (U2+v1), 3- (4+6) = -7 or 7 BF = C23 – (U2+V3), 7- (4+2) = 1 or -1 CD = C31- (U3+V1), 4- (0+6) = -2 or 2 4. Choose the largest positive opportunity cost, which is 7 and draw a closed path, as shown in the matrix below. Start from the unoccupied cell and assign “+” or “–“sign alternatively. Therefore, the most favoured cell is BD, assign as many units as possible. Table 5.24: Draw a closed path The matrix below shows the maximum allocation to the cell BD, and that number of units are added to the cell with a positive sign and subtracted from the cell with a negative sign. 114 CU IDOL SELF LEARNING MATERIAL (SLM)

Table 5.25: Maximum allocation to the cell BD Again, repeat the steps from 1 to 4 i.e. find out the opportunity costs for each unoccupied cell and assign the maximum possible units to the cell having the largest opportunity cost. This process will go on until the optimum solution is reached. The Modified distribution method is an improvement over the stepping stone method since; it can be applied more efficiently when a large number of sources and destinations are involved, which becomes quite difficult or tedious in case of stepping stone method. Modified distribution method reduces the number of steps involved in the evaluation of empty cells, thereby minimizes the complexity and gives a straightforward computational scheme through which the opportunity cost of each empty cell can be determined. 5.6 STEPPING STONE TECHNIQUE The Stepping Stone Method is used to check the optimality of the initial feasible solution determined by using any of the methods Viz. North-West Corner, Least Cost Method or Vogel’s Approximation Method. Thus, the stepping stone method is a procedure for finding the potential of any non-basic variables (empty cells) in terms of the objective function. Through the Stepping stone method, we determine what effect on the transportation cost would be in case one unit is assigned to the empty cell. With the help of this method, we come to know whether the solution is optimal or not. The series of steps are involved in checking the optimality of the initial feasible solution using the stepping stone method: 1. The prerequisite condition to solve for the optimality is to ensure that the number of occupied cells is exactly equal to m+n-1, where ‘m’ is the number of rows, while ‘n’ is equal to the number of columns. 115 CU IDOL SELF LEARNING MATERIAL (SLM)

2. Firstly, the empty cell is selected and then the closed path is created which starts from the unoccupied cell and returns to the same unoccupied cell, called as a “closed loop”. For creating a closed loop the following conditions should be kept in mind: i. In a closed loop, cells are selected in a sequence such that one cell is unused/unoccupied, and all other cells are used/occupied. ii. A pair of Consecutive used cells lies either in the same row or the same column. iii. No three consecutive occupied cells can either be in the same row or column. iv. The first and last cells in the closed loop lies either in the same row or column. v. Only horizontal and vertical movement is allowed. 3. Once the loop is created, assign “+” or “– “sign alternatively on each corner cell of the loop, but begin with the “+” sign for the unoccupied cell. 4. Repeat these steps again until all the unoccupied cells get evaluated. 5. Now, if all the computed changes are positive or are equal to or greater than zero, then the optimal solution has been reached. 6. But in case, if any, value comes to be negative, then there is a scope to reduce the transportation cost further. Then, select that unoccupied cell which has the most negative change and assign as many units as possible. Subtract the unit that is added to the unoccupied cell from the other cells with a negative sign in a loop, to balance the demand and supply requirements. Example, suppose the following matrix shows the initial feasible solution and stepping stone method is adopted to check its optimality: Table 5.26: Initial feasible solution 116 CU IDOL SELF LEARNING MATERIAL (SLM)

Table 5.27: Empty cells AF, BD, BF, CD Table 5.28: The most favoured cell is BD, since it has the highest opportunity cost i.e. 7 With the new matrix so formed, again the empty cells will be evaluated through a loop formation and signs will be assigned accordingly. The cell with the highest opportunity cost will be assigned the units, and this process will repeat until the best optimum solution is obtained or the opportunity cost of all the unoccupied cells comes to be negative. 5.7 SUMMARY  Transportation problem is the most useful special class of linear programming problem which can be applied for different sources of supply to different destinations of demand in such a way that the total transportation cost should be minimized.  Usually, the initial basic feasible solution of any transportation problem is obtained by using well known methods such as North-West corner method (NWCM) or Least- 117 CU IDOL SELF LEARNING MATERIAL (SLM)

Cost Method (LCM) or Vogel’s Approximation Method (VAM), and then finally the optimality of the given transportation problem is checked by MODI.  In this unit, we have developed a new method to find the initial basic feasible solution as well as the optimal solution or near to the optimal solution of transportation.  Also, the new algorithm provided gives the idea for the optimality in comparison with MODI method as the flow of step by step procedure.  Everything has been explained through examples explaining the new algorithm.  Optimality test can be performed if two conditions are satisfied i.e. i. There is m + n – 1 allocation, whose m is number of rows, n is number of columns. Here m + n – 1 =6. But the number of allocation is five. ii. These m + n – 1 allocation should be at independent positions. I.e. it should not be possible to increase or decrease any allocation without either changing the position of the allocations or violating the row or column restrictions.  A simple rule for allocations to be in independent positions is that it is impossible to travel from any allocation, back to itself by a series of horizontal and vertical steps from one occupied cell to another, without a direct reversal of route. It can be seen that in the present example, allocations are at independent positions as no closed loop can be formed at the allocated cells.  The Modified Distribution Method or MODI is an efficient method of checking the optimality of the initial feasible solution.  The Stepping Stone Method is used to check the optimality of the initial feasible solution determined by using any of the methods Viz. North-West Corner, Least Cost Method or Vogel’s Approximation Method. Thus, the stepping stone method is a procedure for finding the potential of any non-basic variables (empty cells) in terms of the objective function.  Through the Stepping stone method, we determine what effect on the transportation cost would be in case one unit is assigned to the empty cell. With the help of this method, we come to know whether the solution is optimal or not. 5.8 KEYWORDS  NWCM (North West Corner Method)- North West corner method is used in transportation problems to calculate basic feasible solutions. The basic variables are selected from the north-west corner of the transportation matrix.  LCM (Least Cost Method)-The Least Cost Method is another method used to obtain the initial feasible solution for the transportation problem. Here, the allocation begins 118 CU IDOL SELF LEARNING MATERIAL (SLM)

with the cell which has the minimum cost. The lower cost cells are chosen over the higher-cost cell with the objective to have the least cost of transportation.  VAM (Vogel’s Approximation Method)- Vogel’s approximation method tackles the problem of finding a good initial solution by taking into account the costs associated with each route alternative.  Optimality Tests- Optimally tests in a transmission problem are carried out on a non- degenerate initial feasible solution to ascertain if the IFS obtained is optimal. Optimally test in a TP is carried out by determining the opportunity costs of all empty cells in a transportation matrix. Nature of the opportunity cost indicates the optimality. There is no other set of transportation routes that will reduce the total transportation cost.  MODI Method- The MODI (modified distribution) method allows to compute improvement indices quickly for each unused square without drawing all of the closed paths. Because of this, it can often provide considerable time savings over other methods for solving transportation problems. 5.9 LEARNING ACTIVITY 1. Find Solution using the North-West Corner method. ___________________________________________________________________________ ___________________________________________________________________________ 2. Use the Least Cost Method to find a Basic Feasible Solution. 119 CU IDOL SELF LEARNING MATERIAL (SLM)

___________________________________________________________________________ ___________________________________________________________________________ 5.10 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. Write a short note on NWCM. 2. What is the benefit of using LCM? 3. Why is VAM also known as the Penalty Method? 4. What are the two conditions that satisfy the optimality test? 5. What is the concept of the MODI method? Long Questions 1. Explain stepping stone technique. 2. How is the modified distribution method better than the stepping stone method? 3. What are the steps involved in solving the transportation problem using the Vogel’s Approximation Method? 4. Explain the concept of MODI method with an example? 5. Which method do you think is most reliable in solving transport problems? Give your opinions. B Multiple Choice Questions 1. Where would you select the basic variables in NWCM? a. From the extreme left corner 120 b. From the extreme right corner c. From the middle CU IDOL SELF LEARNING MATERIAL (SLM)

d. From the diagonal corner 2. Which one produces optimal results? a. NWCM b. Least Cost Method c. Both d. None of these 3. Which is a condition to perform an optimality test? a. m+n+1 allocation b. m+n+2 allocation c. m+n-1 allocation d. m+n-2 allocation 4. Which method takes less time often to solve transport problems? a. NWCM b. LCM c. Optimally Test d. MODI 5. Which stepis not involved in checking the optimality of the initial feasible solution using the stepping stone method? a. The prerequisite condition to solve for the optimality is to ensure that the number of occupied cells is exactly equal to m+n-1 b. Closed loop c. Once the loop is created, assign “+” or “–“ sign alternatively on each corner cell of the loop d. Repeat these steps again until all the occupied cells get evaluated Answers 1-a 2-b 3-c 4-d 5-d 5.11 REFERENCES References 121 CU IDOL SELF LEARNING MATERIAL (SLM)

 Sudhakar V.J., ArunSankar.N., Karpagam.T., A New Approach for finding an optimal solution for Transportation problems, European Journal of Scientific Research, ISSN 1450-216X Vol.68 No.2(2012), pp 254-257  Hitchcock FL (1941).The distribution of a product from several sources to Numerous Localities, Journal of Mathematical Physics 20 1941 224-230.  Checking for Optimality | Transportation Problem (yourarticlelibrary.com) Textbooks  405_Chap 1 - 12-01_Srinivasan_Operations-Research_-Principles-and-Applications- Prentice-Hall-of-India-2010.pdf  Operations Research Theory and Applications by J.K. Sharma, Macmillan India Ltd  Lai Y.J., Hwang C.L., 1992. Mathematical Programming Methods and Applications, Springer, Berlin. Websites  What is North-West Corner Rule? definition and meaning - Business Jargons  Transportation Problem (TP) and Assignment Problem (AP) (daimsr.in)  Transportation Problem | Set 1 (Introduction) –GeeksforGeeks 122 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 6 – ASSIGNMENTS PROBLEMS STRUCTURE 6.0 Learning Objectives 6.1 Introduction 6.2 Concepts and Solutions 6.3 Unbalanced Problems 6.4 Travelling Salesman Problem 6.5 Air Crew Problem 6.6 Summary 6.7 Keywords 6.8 Learning Activity 6.9 Unit End Questions 6.10 References 6.0 LEARNING OBJECTIVES After studying this unit, you will be able to:  Formulate an assignment problem.  Determine the optimal solutions of assignment problems using the Hungarian method.  Solve the travelling salesman problem as an assignment problem.  Sort out air crew problem. 6.1 INTRODUCTION The assignment problem deals with allocating various resources (items) to various activities (receivers) on a one to one basis, i.e., the number of operations are to be assigned to an equal number of operators where each operator performs only one operation. For example, suppose an accounts officer has 4 subordinates and 4 tasks. The subordinates differ in efficiency and take different time to perform each task. If one task is to be assigned to one person in such a way that the total person hours are minimised, the problem is called an assignment problem. Though the assignment problem is a special case of transportation problem, it is not solved using the methods described in earlier units. We use another method called the Hungarian method for solving an assignment problem. It is shorter and easier compared to any method of finding the optimal solution of a transportation problem. In this unit, we discuss various 123 CU IDOL SELF LEARNING MATERIAL (SLM)

types of assignment problems, including travelling salesman problems and apply the Hungarian method for solving these problems. The Assignment problem is an exceptionally uncommon instance of Transportation problem for linear programming problem, in which number of offices are to be doled out to an equivalent number of employment, where every administrator can do just a single operation at any given moment. There are such a large number of down to earth circumstances in which the issue moves toward becoming to dole out or allot every asset to just a single action (occupation) and the other way around with the end goal that the powerful estimation has been figured out. The Assignment problem produces when the assets those are accessible, for example, men, and machines and so on.Have fluctuating levels of productivity for performing distinctive exercises. That is the reason the aggregate cost, benefitor time of performing distinctive exercises is additionally not equivalent. In this way the issue turns out to be very logical that how the assignments ought to be made such that it will optimize the given objective. In reasonable circumstances, where the assignment problem mightbe valuable: 1. Specialists to machines 2. Assistants to different checkout counters 3. Business people to various deals zones 4. Classes to different checkout counters 5. Vehicles to highways 6. Contracts to bidders. Koing (1931) has created and presented a strategy for solving Assignment problems. He gave his name as Hungarian technique. His fundamentals expect to find the optimal solution of an Assignment Problem without making an immediate correlation of each arrangement. His strategy takes a shot at the essential of diminishing the given cost grid to a framework of chance cost. The Hungarian technique portrays the calculation, gives ideal arrangement from a limited arrangement of arrangements which takes care of the task issue in polynomial time and which foreseen later primal-double strategies. James Munkers (1957) surveyed the calculation and observed that itis (unequivocally) polynomial. From that point forward the calculation has been referred to likewise as Kuhn- Munkers calculation or Munkers assignment algorithm. Thompson (1981) presented a Repetitive method for solving assignment problems which is a bounded non-simplex method for tackling Assignment Problems. It has been demonstrated that the line duals are non-expanding and the segment duals non-diminishing. Li ET. al. (1997) built up another calculation for the Assignment Problem which additionally called another option to the Hungarian Method. So far in the literature, there are four 124 CU IDOL SELF LEARNING MATERIAL (SLM)

techniques: Enumeration method, Simplex method, Transportation method and Hungarian technique for illuminating Assignment Problem. 6.2 CONCEPTS AND SOLUTIONS An assignment problem may be considered as a special type of transportation problem in which the number of sources and destinations are equal. The capacity of each source as well as the requirement of each destination is taken as 1. In the case of an assignment problem, the given matrix must necessarily be a square matrix which is not the condition for a transportation problem. Suppose there are n persons and n jobs and the assignment of jobs has to be done on a one-to-one basis. This assignment problem can be stated in the form of an n×n matrix of real numbers (known as the cost matrix) as given in the following table: Person Job …n 1 1 2 …j … C1n C11 C12 … C1j 2 . . i Ci1 Ci2 … Cij … Cin . . n Cn1 Cn2 … Cnj … Cnn Table 6.1: The cost matrix Where cij represents the amount of time taken by the ith person to complete the jthjob. Let xij denote the jth job assigned to the ith person. Then, mathematically, the assignment problem can be stated as follows: subject to: 125 CU IDOL SELF LEARNING MATERIAL (SLM)

xij = 1 If the ith person is assigned the jth job xij = 0 If the ith person is not assigned the jth job Xi1 + xi2 + …… + xin = 1, I = 1, 2…., n (one job is done by the ith person) Xij + x2j + …. + xnj = 1, j= 1, 2..., n (only one person is assigned the jth job) The constant cij in the above problem represents time. It may be cost or some other parameter which is to be minimised in the assignment problem under consideration. Note that an assignment problem is a special type of transportation problem and may be solved as one. However, we use another method known as the Hungarian method for solving it. This method is shorter and easier compared to any other method of finding the optimal solution of a transportation problem. Let us explain the Hungarian method of finding the optimal solution of an assignment problem. Hungarian Method for Solving Assignment Problem: The Hungarian method of assignment provides us with an efficient method of finding the optimal solution without having to make a-direct comparison of every solution. It works on the principle of reducing the given cost matrix to a matrix of opportunity costs. Opportunity cost shows the relative penalties associated with assigning resources to an activity as opposed to making the best or least cost assignment. If we can reduce the cost matrix to the extent of having at least one zero in each row and column, it will be possible to make an optimal assignment. The Hungarian method can be summarized in the following steps: Step 1: Develop the Cost Table from the given Problem: If the no of rows are not equal to the no of columns and vice versa, a dummy row or dummy column must be added. The assignment cost for dummy cells is always zero. Step 2: Find the Opportunity Cost Table: i. (a) Locate the smallest element in each row of the given cost table and then subtract that from each element of that row, and ii. (b) In the reduced matrix obtained from 2 (a) locate the smallest element in each column and then subtract that from each element. Each row and column now have at least one zero value. Step 3: Make Assignment in the Opportunity Cost Matrix: The procedure of making assignment is as follows: 126 CU IDOL SELF LEARNING MATERIAL (SLM)

i. (a) Examine rows successively until a row with exactly one unmarked zero is obtained. Make an assignment single zero by making a square around it. ii. (b) For each zero value that becomes assigned, eliminate (Strike off) all other zeros in the same row and/ or column. iii. (c) Repeat step 3 (a) and 3 (b) for each column also with exactly single zero value all that has not been assigned. iv. (d) If a row and/or column has two or more unmarked zeros and one cannot be chosen by inspection, then choose the assigned zero cell arbitrarily. v. (e) Continue this process until all zeros in row column are either enclosed (Assigned) or struck off (x) Step 4: Optimality Criterion: If the number of assigned cells is equal to the number of rows and columns then it is the optimal solution. The total cost associated with this solution is obtained by adding original cost figures in the occupied cells. If a zero cell was chosen arbitrarily in step (3), there exists an alternative optimal solution. But if no optimal solution is found, then go to step (5). Step 5: Revise the Opportunity Cost Table: Draw a set of horizontal and vertical lines to cover all the zeros in the revised cost table obtained from step (3), by using the following procedure: i. (a) For each row in which no assignment was made, mark a tick (√) ii. (b) Examine the marked rows. If any zero occurs in those columns, tick the respective rows that contain those assigned zeros. iii. (c) Repeat this process until no more rows or columns can be marked. iv. (d) Draw a straight line through each marked column and each unmarked row. If a no of lines drawn is equal to the no of (or columns) the current solution is the optimal solution, otherwise go to step 6. Step 6: Develop the New Revised Opportunity Cost Table: i. (a) From among the cells not covered by any line, choose the smallest element, call this value K ii. (b) Subtract K from every element in the cell not covered by line. iii. (c) Add K to very element in the cell covered by the two lines, i.e., intersection of two lines. iv. (d) Elements in cells covered by one line remain unchanged. 127 CU IDOL SELF LEARNING MATERIAL (SLM)

Step 7: Repeat Step 3 to 6 Unlit an Optimal Solution is Obtained: We now illustrate the procedure with the help of an example. Example 1: A computer centre has four expert programmers and needs to develop four application programmes. The head of the computer centre, estimates the computer time (in minutes) required by the respective experts to develop the application programmes as follows: Table 6.2: Time required to develop the application programmes Find the assignment pattern that minimises the time required to develop the application programmes. Solution: Let us subtract the minimum element of each row from every element of that row. Note that the minimum element in the first row is 80. So 80 is to be subtracted from every element of the first row, i.e., from 120, 100, 80 and 90, respectively. As a result, the elements of the first row of the resulting matrix would be 40, 20, 0, 10, respectively. Similarly, we obtain the elements of the other rows of the resulting matrix. Thus, the resulting matrix is: AB C D 1 40 20 0 10 2 10 20 40 0 3 10 40 20 0 4 10 10 0 10 Table 6.3: Resulting matrix Let us now subtract the minimum element of each column from every element of that column in the resulting matrix. The minimum element in the first column is 10. So 10 is to be subtracted from every element of the first column, i.e., from 40, 10, 10, and 10, respectively. As a result, the elements of the first column of the resulting matrix are 30, 0, 0, 0, 128 CU IDOL SELF LEARNING MATERIAL (SLM)

respectively. Similarly, we obtain the elements of the other columns of the resulting matrix. Thus, the resulting matrix is: AB C D 1 30 10 0 10 2 0 10 40 0 3 0 30 20 0 4 0 0 0 10 Table 6.4: Resulting matrix Now, starting from the first row onward, we draw a rectangle around the 0 in each row having a single zero and cross all other zeros in the corresponding column. Here, in the very first row we find a single zero. So, we draw a rectangle around it and cross all other zeros in the corresponding column. We get AB C D 1 30 10 0 10 2 0 10 40 0 3 0 30 20 0 4 0 0 0 10 Table 6.5: Resulting matrix In the second, third and fourth row, there is no single zero. Hence, we move column-wise. In the second column, we have a single zero. Hence, we draw a rectangle around it and cross all other zeros in the corresponding row. We get AB C D 1 30 10 0 10 2 0 10 40 0 129 CU IDOL SELF LEARNING MATERIAL (SLM)

3 0 30 20 0 4 0 0 0 10 Table 6.6: Resulting matrix In the matrix above, there is no row or column, which has a single zero. Therefore, we first move row-wise to locate the row having more than one zero. The second row has two zeroes. So, we draw a rectangle arbitrarily around one of these zeroes and cross the other one. Let us draw a rectangle around the zero in the cell (2, A) and cross the zero in the cell (2, D). We cross out the other zeroes in the first column. Note that we could just as well have selected the zero in the cell (2, D), drawn a rectangle around it and crossed all other zeroes. This would have led to an alternative solution. In this way, we are left with only one zero in every row and column around which a rectangle has been drawn. This means that we have assigned only one operation to one operator. Thus, we get the optimum solution as follows: AB C D 1 30 10 0 10 2 0 10 40 0 3 0 30 20 0 4 0 0 0 10 Table 6.7: Resulting matrix Note that the assignment of jobs should be made on the basis of the cells corresponding to the zeroes around which rectangles have been drawn. Therefore, the optimum solution for this problem is: 1  C, 2  A, 3  D, 4  B This means that programmer 1 is assigned programme C, programmer 2 is assigned programme A, and so on. The minimum time taken in developing the programmes is = 80 + 80 + 100 + 90 = 350 min. 6.3 UNBALANCED PROBLEMS The assignment problem wherein the number of rows is not equal to the number of columns is said to be an unbalanced assignment problem. Such a problem is handled by introducing dummy row(s) if the number of rows is less than the number of columns and dummy 130 CU IDOL SELF LEARNING MATERIAL (SLM)

column(s) if the number of columns is less than the number of rows. All the elements of such a dummy row/column are taken as zero. The augmented problem is then solved by the Hungarian method as explained earlier. Example: To stimulate interest and provide an atmosphere for intellectual discussion, the faculty of mathematical sciences in an institute decides to hold special seminars on four contemporary topics – Statistics, Operations Research, Discrete Mathematics, Matrices. Each such seminar is to be held once a week. However, scheduling these seminars (one for each topic and not more than one seminar per day) has to be done carefully so that the number of students unable to attend is kept to a minimum. A careful study indicates that the number of students who cannot attend a particular seminar on a specific day is as follows: Monday Statistics Operations Discrete Matrices Tuesday Research Mathematics Wednesday 50 20 Thursday 40 40 60 30 Friday 60 30 40 20 30 20 30 30 10 30 20 30 20 10 Table 6.8: Number of students who cannot attend a particular seminar on a specific day Find an optimal schedule for the seminars. Also find the number of students who will be missing at least one seminar. Solution: Here the number of rows is 5 and the number of columns is 4. Therefore, the given assignment problem is unbalanced. As the number of columns is one less than the number of rows, we introduce one dummy column to convert the given assignment problem into a balanced problem. The number of students in each cell of this column is taken as zero. Thus, the problem takes the following form: Monday Statistics Operations Discrete Matrices Dummy Tuesday Research Mathematics Wednesday 50 20 0 Thursday 40 40 60 30 0 60 30 40 20 0 30 20 30 30 0 30 20 131 CU IDOL SELF LEARNING MATERIAL (SLM)

Friday 10 20 10 30 0 Table 6.9: The problem takes this form Now, on applying the Hungarian method (Steps 1 to 4), we get Statistics Operations Discrete Matrices Dummy Research Mathematics Monday 40 20 50 00 Tuesday 30 10 30 10 0 Wednesday 50 0 20 0 0 Thursday 20 10 10 10 0 Friday 0 0 0 10 0 Table 6.10: Applying the Hungarian method Since the number of assigned zeroes < number of rows, we apply Step 5 of the Hungarian method and draw the minimum number of horizontal/vertical lines that cover all the zeroes as shown in the following table: Statistics Operations Discrete Matrices Dummy Research Mathematics Monday 40 20 50 00 Tuesday 30 10 30 10 0 Wednesday 50 0 20 0 0 Thursday 20 10 10 10 0 Friday 0 0 0 10 0 Table 6.11: Lines covering all zeros We select the minimum element from amongst the uncovered elements, which is 10 in this case. We subtract this element, i.e., 10 from each uncovered element and add it to the elements which lie at the intersection of the horizontal/vertical lines. Other covered elements will remain unaltered. Thus, the resulting matrix is: 40 20 50 0 10 132 CU IDOL SELF LEARNING MATERIAL (SLM)

20 0 20 0 0 50 0 20 0 10 10 0 0 0 0 0 0 0 10 10 Table 6.12: Resulting matrix Now, on applying the Hungarian method, we have 40 20 50 0 10 20 0 20 0 0 50 0 20 0 10 10 0 0 0 0 0 0 0 10 10 Table 6.13: Applying the Hungarian method Since each row and each column of the matrix has one and only one assigned 0, optimum assignment is made in the cells containing those zeroes around which rectangles have been drawn as Monday Matrices, Wednesday  Operations Research, Thursday  Discrete Mathematics, Friday  Statistics The total number of students who will be missing at least one seminar = 20 + 20 + 20 + 10 = 7 Alternative Optimal Solutions Such solutions exist if while assigning zeroes, i.e., while carrying out Step 4 of the Hungarian method, we neither find any row nor any column, which has a single zero. Then we first move row-wise and then column-wise to locate a row/column having two zeroes. We draw a rectangle arbitrarily around any one of these zeroes and cross the other. Alternatively, the zero around which the rectangle has been drawn could have been crossed and the rectangle could have been drawn around the other zero. This will lead to two alternative optimum solutions. While assigning zeroes, i.e., while carrying out Step 4 of the Hungarian method, we may neither find any row nor any column, which has single or two zeroes. Then we first move row-wise and then column-wise to locate a row/column having three or more zeroes. This will lead to three or more alternative solutions. 133 CU IDOL SELF LEARNING MATERIAL (SLM)

6.4 TRAVELLING SALESMAN PROBLEM Consider a travelling salesman who has to visit a certain number of cities in his assigned territory. For each city of his territory, he wishes to visit each city once and only once and arrive back in the city from where he started. He knows the distances (or cost or time) of journey between every pair of cities, and wishes to determine the tour schedule that represents the least distance/cost/time. Such types of problems can be solved by the assignment algorithm. The difference between a travelling salesman problem and an assignment problem is that in an assignment problem, different destinations are assigned to different sources but in a travelling salesman problem, a destination is assigned to a source. Then this destination becomes another source to which we assign another destination, which in turn becomes another source, and so on. Let us explain this point further with the help of an example. Example: A travelling salesman has to visit five cities. He wishes to start from a particular city, visit each city once and then return to his starting point. The travelling time (in hours) for each city from a particular city is given below: To  ABCDE From A∞5 8 4 5 B5∞7 4 5 C87∞8 6 D44 8∞8 E556 8∞ Table 6.14: Travelling time (in hours) for each city What is the sequence of visits of the salesman so that the total travelling time is minimised? Solution: Applying the Hungarian method to this problem, we get To  ABCDE From A∞0 2 0 0 B0∞1 0 0 134 CU IDOL SELF LEARNING MATERIAL (SLM)

C21∞3 0 D00 3∞4 E000 4∞ Table 6.15: Applying the Hungarian method As per the above assignment, the salesman should travel from A to D, D to B, B to A, i.e., A D  B  A The above solution is not a complete solution of the travelling salesman problem as the salesman returns to A without travelling through all the cities. So, we proceed as follows: Since the assignment of zeroes has not given the solution of the travelling salesman problem, we bring the next minimum non-zero element into the solution. Thus, we obtain the next best solution by bringing 1 into the solution. Had there not been 1 in any cell, we would have taken the minimum, but greater than 1 value from amongst all the values of the table. Here, we have 1 and it appears in two places in this problem. One of these is chosen arbitrarily. Let us choose the cell (B, C) and form a rectangle around the value in this cell and cross out the zeroes in its row and column. Now, we apply the Hungarian method for the assignment of zeroes. Thus, we have To  ABCDE From A∞0 2 0 0 B0∞1 0 0 C21∞3 0 D00 3∞4 E000 4∞ Table 6.16: Applying Hungarian method for the assignment of zeroes Alternatively, we get To  ABCDE From A∞0 2 0 0 135 CU IDOL SELF LEARNING MATERIAL (SLM)

B0∞1 0 0 C21∞3 0 D00 3∞4 E000 4∞ Table 6.17: Alternative table In the case of the first alternative, the optimum assignment is ADA but this is not the solution to the travelling salesman problem. In the case of the second alternative, the optimum assignment is A-E-C-B-D-A This is the complete solution for the problem as starting from A, the salesman returns to A visiting all the other cities. The minimum time taken by him to travel to all the cities is 5 + 6 + 7 + 4 + 4 = 26 hrs. 6.5 AIR CREW PROBLEM The crew assignment problem for airlines refers to the allocation of cockpit and cabin crew members to pairings during a predefined rostering period, usually one month. A pairing is a sequence of flight legs; it starts from home base and ends at the home base and it is constructed in such a way that labour regulations are respected. A pairing may span from one to a few days long. The set of flight legs in a day constitute a duty. A crew assignment system is responsible for allocating crew members to preconstructed pairings that cover all flight legs of an airline company for a given rostering period. A system of this kind has to guarantee that no regulation is violated. The full crew assignment process is usually performed separately for the cabin and cockpit crew, since their duty is governed by different constraints and regulations. Cockpit crew assignment can sometimes be broken into smaller independent subproblems corresponding to different fleets and groups of crew members of the same rank (e.g. captains, first officers, and flight engineers). However, this is always not possible, if there exist constraints (e.g., crew composition ones) that relate different ranks to each other, or even if vertical constraints are to be satisfied. A vertical constraint is one that relates roster attributes of different crew members. Apart from ensuring the validity of all rules and regulations, a crew assignment system must follow a specific assignment methodology as well. Three main methodologies exist: 136 CU IDOL SELF LEARNING MATERIAL (SLM)

Fair Assignment: The workload is allocated to crew members in a fair way. Flight time, days of, stand-by duties, early/late flights and any other work affecting attributes are being distributed evenly. Bid Lines: Anonymous schedules for the whole rostering period (lines of work) are constructed and published, so that crew members bid on them and the system assigns them according to bids (usually respecting the seniority criterion). Preferential Bidding: The crew members express general and specific performances (e.g. avoiding early flights, wishing to fly a certain flight next Tuesday, etc.) and the system tries to award such kind of bids, either by following a direct assignment methodology keeping in mind the expressed preferences or by generating personalized lines of work and then attempting to find a subset of them that covers all pairings and satisfies the crews as much as possible. Example: Best-ride airlines that operate seven days a week have the following time-table. Table 6.18: Time table for Best-ride airlines that operate seven days a week Crews must have a minimum layover of 5 hours between flights. Obtain the pairing of flights that minimizes layover time away from home. For any given pairing, the crew will be based at the city that results in the smaller layover. For each pair also mention the city where the crew should be based. Solution To determine optimal assignments, first we calculate layover times from the above time table. Calculating values for table 1 (layover time) First Row First cell Arrival time (Mumbai) = 8.00 AM & Departure time (Mumbai) = 8.00 AM Difference between arrival and departure = 24 hours (layover time) 137 CU IDOL SELF LEARNING MATERIAL (SLM)

Second cell Arrival time (Mumbai) = 8.00 AM & Departure time (Mumbai) = 9.00 AM Difference between arrival and departure = 25 hours (layover time) Third cell Arrival time (Mumbai) = 8.00 AM & Departure time (Mumbai) = 12.00 Noon Difference between arrival and departure = 28 hours (layover time) Fourth cell Arrival time (Mumbai) = 8.00 AM & Departure time (Mumbai) = 5.00 PM Difference between arrival and departure = 9 hours (layover time) Similarly, values for other rows can be calculated. Table 6.19: Calculating values for layover time 138 First Column First cell Arrival time (Delhi) = 9.00 AM & Departure time (Delhi) = 7.00 AM Difference = 22 hours Second cell Arrival time (Delhi) = 9.00 AM & Departure time (Delhi) = 8.00 AM Difference = 23 hours Third cell Arrival time (Delhi) = 9.00 AM & Departure time (Delhi) = 1.00 PM Difference = 28 hours CU IDOL SELF LEARNING MATERIAL (SLM)

Fourth cell Arrival time (Delhi) = 9.00 AM & Departure time (Delhi) = 6.00 PM Difference = 9 hours Similarly, values for other columns can be calculated. Table 6.20: Crew based at Mumbai The composite layover time matrix is obtained by selecting the smaller element from the two corresponding elements of table 1 & 2. The layover time marked with (*) represents that the crew is based at Mumbai, otherwise based at Delhi. For example, corresponding to flight no.1 and 101 in table 1 & 2, we select the minimum between (24, 22), i.e., 22 for Mumbai. Therefore, this element is marked with (*). In this way, table is completed and shown below. Table 6.21: Composite layover time matrix Now the above problem can be easily solved by the Hungarian method. The following matrix shows the assignments. 139 CU IDOL SELF LEARNING MATERIAL (SLM)

Table 6.22: Assignments Draw the minimum number of vertical and horizontal lines necessary to cover all the zeros in the reduced matrix. Table 6.23: Drawing minimum number of vertical and horizontal lines necessary to cover all the zeros Select the smallest element from all the uncovered elements, i.e., 9. Subtract this element from all the uncovered elements and add it to the elements, which lie at the intersection of two lines. Repeating step 3 of the Hungarian algorithm, we obtain a solution which is shown in the following table. Table 6.24: Repeating step 3 of the Hungarian algorithm Table 6.25 the optimal solution is 21 + 8 + 18 + 5 = 52 hours. 140 6.6 SUMMARY CU IDOL SELF LEARNING MATERIAL (SLM)

 In an assignment problem, the number of operations is assigned to an equal number of operators where each operator performs only one operation. So, an assignment problem may be considered as a special type of transportation problem in which the capacity of each of the sources as well as the requirement of each of the destinations is taken as 1. In an assignment problem, the given matrix must necessarily be a square matrix, which is not the condition for a transportation problem. Such problems are solved using the Hungarian method, which is shorter and easier compared to any other method of finding the optimal solution.  There may be assignment problems where maximisation is required to be done instead of minimisation. To handle such a problem, we find the opportunity loss matrix by subtracting the value of each cell from the largest value chosen from amongst all the given cells. When the value of a cell is subtracted from the highest value, it gives the loss of amount caused by not getting the opportunity which would have given the highest value. The matrix obtained is known as the opportunity loss matrix and is handled in the same way as the minimisation problem.  The assignment problem wherein the number of rows is not equal to the number of columns is said to be an unbalanced problem. Such a problem is handled by introducing dummy row(s) if the number of rows is less than the number of columns and dummy column(s) if the number of columns is less than the number of rows. All elements for such a dummy row/column are taken as zero. The augmented problem is then solved by the Hungarian method.  While assigning zeros in an assignment problem, if we neither find any row nor any column which has single zero, then we first move row-wise and then column-wise to locate a row/column having two (if not two, then three or more) zeroes. Then a rectangle is formed arbitrarily around one of these zeroes and the others are crossed. Alternatively, the zero around which the rectangle has been made could have been crossed and the rectangle could have been formed around any of the other zeroes. This leads to alternative optimum solutions.  Sometimes, there may be restrictions on assigning a particular activity to a particular resource. Then a very large cost (or time or anything else which is to be minimised) is considered and represented by ∞ or M for such a restricted pair.  The travelling salesman problem wherein there are a certain number of cities to be visited by a salesman in his assigned territory can also be solved as an assignment problem. The only difference between the travelling salesman problem and an assignment problem is that in an assignment problem different destinations are assigned to different sources. 141 CU IDOL SELF LEARNING MATERIAL (SLM)

 But in a travelling salesman problem, a destination is assigned to a source and then that destination becomes another source to which another destination is assigned, and so on. This is because, in a travelling salesman problem, for each city of his territory, the salesman wishes to visit each city once and only once and arrive back at the city from where he started. He wishes to determine the tour schedule that represents the least distance/cost/time.  A typical problem arising in airline crew management consists in optimally assigning the required crew members to each flight segment of a given time period, while complying with a variety of work regulations and collective agreements. This problem called the Crew Assignment Problem (CAP) is currently decomposed into two independent sub-problems which are modelled and solved sequentially: (a) the well- known Crew Pairing Problem followed by (b) the Working Schedules Construction Problem. In the first sub-problem, a set of legal minimum-cost pairings is constructed, covering all the planned flight segments. In the second sub-problem, pairings, rest periods, training periods, annual leaves, etc. are combined to form working schedules which are then assigned to crew members. 6.7 KEYWORDS  Assignment Problem- The assignment problem represents a special case of linear programming problem used for allocating resources (mostly workforce) in an optimal way; it is a highly useful tool for operation and project managers for optimizing costs.  Hungarian Method- The Hungarian Method is an algorithm developed by Harold Kuhn to solve assignment problems in polynomial time. The assignment problem is a special case of the transportation problem in which the number of providers and consumers are equal and supply (ai) and demand (bj) amounts are defined as 1.  Unbalanced Assignment Problems- Unbalanced Assignment problem is an assignment problem where the number of facilities is not equal to the number of jobs. To solve an unbalanced assignment problem, a balanced one, a dummy facility(s) or a dummy job(s) (as the case may be) is introduced with zero cost or time.  Air Crew Assignment Problem- The Airline Crew Assignment Problem (ACA) consists of assigning lines of work to a set of crew members such that a set of activities is partitioned and the costs for that assignment are minimized.  Travelling Salesman Problem- The 'Travelling salesman problem' is very similar to the assignment problem except that in the former, there are additional restrictions that a salesman starts from his city, visits each city once and returns to his home city, so that the total distance (cost or time) is minimum. 142 CU IDOL SELF LEARNING MATERIAL (SLM)

6.8 LEARNING ACTIVITY 1. Find solution to the travelling salesman problem (Min Case). ___________________________________________________________________________ _______________________________________________________________ 2. Solve the following assignment problem. Cell values represent the cost of assigning job A, B, C and D to the machines I, II, III and IV. ___________________________________________________________________________ ___________________________________________________________________________ 6.9 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. What is the purpose of assignment problems in operational research? 2. What is the principle behind using the Hungarian method? 143 CU IDOL SELF LEARNING MATERIAL (SLM)

3. How would you handle it if the number of rows is not equal to the number of columns in an unbalanced assignment problem? 4. Write a brief note on alternative optimal solutions. 5. How does a crew assignment problem help an airline? Long Questions 1. What are the steps involved in solving assignment problems through the Hungarian method? 2. How does the travelling salesman problem assist in making hassle free journeys in a short time? 3. What are the methodologies used in air crew problems? 4. How would you solve an unbalanced problem? 5. Give an overview on all the assignment problems. B. Multiple Choice Questions 1. Who has given the name Hungarian technique? a. Koing b. James Munkers c. Kuhn Munkers d. Thompson 2. How would you state Suppose if there are n persons and n jobs and the assignment of jobs has to be done on a one-to-one basis? a. nxm matrix b. nxn matrix c. nxa matrix d. nxb matrix 3. Which is not a step involving Hungarian method? a. Develop the Cost Table from the given Problem b. Find the Opportunity Cost Table c. Make no Assignment in the Opportunity Cost Matrix d. Optimality Criterion 4. What are the procedures involved to draw a set of horizontal and vertical lines to cover all the zeros in the revised cost table in the Hungarian method? 144 CU IDOL SELF LEARNING MATERIAL (SLM)

a. For each row in which no assignment was made, mark a tick (√) b. Examine the marked rows c. Repeat this process until no more rows or columns can be marked d. All of these 5. Which assignment problems would you use to solve a transport issue of an airline? a. Air crew problem b. Hungarian method c. Travelling salesman problem d. None of these Answers 1-a 2-b 3-c 4-d 5-a 6.10 REFERENCES References  www.researchgate.net/publication/322465781_OPTIMAL_SOLUTION_OF_AN_AS SIGNMENT_PROBLEM_AS_A_SPECIAL_CASE_OF_TRANSPORTATION_PR OBLEM  Crew Assignment via Constraint Programming: Integrating Column Generation and Heuristic Tree Search | SpringerLink  C. Barnhart, E.L. Johnson, G.L. Nemhauser, M.W.P. Savelsbergh and P.H. Vance, Branch-and-price: Column generation for solving huge integer programs, Operations Research 46(3) (1998) 316-329.  Modeling and solving a Crew Assignment Problem in air transportation - ScienceDirect Textbooks  Crew Assignment Problem (universalteacherpublications.com)  Operations Research in the Airline Industry  Editors: Gang Yu (Ed.)  Operations Research by Released May 2013 Publisher(s): Pearson India ISBN: 9789332517813 Websites 145 CU IDOL SELF LEARNING MATERIAL (SLM)

 Unit-5.pdf (egyankosh.ac.in)  Operations Research (nitjsr.ac.in)  Travelling salesman problem using Hungarian method Rules & Example-1 (atozmath.com) 146 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 7 – GAME THEORY STRUCTURE 7.0 Learning Objectives 7.1 Introduction 7.2 Concepts 7.3 Solutions Of 2-Person Games 7.4 Pure and Mixed Strategy Games 7.5 Odds method 7.6 Dominance Method 7.7 Sub Games Method 7.8 Equal Gains Method 7.9 Summary 7.10 Keywords 7.11 Learning Activity 7.12 Unit End Questions 7.13 References 7.0 LEARNING OBJECTIVES After studying this unit, you will be able to:  Get to know the concept of a game theory  Gain insights on the assumptions in the theory of games  Implement the managerial applications of the theory of games in reality  Categorise various types of games 7.1 INTRODUCTION Game theory is a type of decision theory in which one’s choice of action is determined after taking into account all possible alternatives available to an opponent playing the same game, rather than just by the possibilities of several outcome results. Game theory does not insist on how a game should be played but tells the procedure and principles by which action should be selected. Thus it is a decision theory useful in competitive situations. Game is defined as 147 CU IDOL SELF LEARNING MATERIAL (SLM)

an activity between two or more persons according to a set of rules at the end of which each person receives some benefit or suffers loss. The set of rules defines the game. Going through the set of rules once by the participants defines a play. Game Theory is a body of knowledge which is concerned with the study of decision making in situations where two or more rational opponents are involved under conditions of competition and conflicting interests. It deals with human processes in which an individual decision making unit is not in complete control of the other decision making units. Here ε unit may be an individual group, organisation, society or a country. Game Theory is a type of decision theory which is based on reasoning in which the choice of action is determined after considering the possible alternatives available to the opponents playing the same game. The aim is to choose the best course of action, because every player has got an alternative course of action. History of Game Theory The individual closely associated with the creation of the theory of games is John von Neumann, one of the greatest mathematicians of this century. Although others preceded him in formulating a theory of games - notably Emile Borel - it was von Neumann who published in 1928 the paper that laid the foundation for the theory of two-person zero-sum games. The theory of Games was born in 1944 with the publication of Theory of Games and Economic Behaviour by Hungarian-born American mathematician John von Neumann and his Princeton University colleague Oskar Morgenstern, a German-born American economist. In their book, they observed that economics is much like a game, wherein players anticipate each other’s moves, and therefore requires a new kind of mathematics, which they called game theory. Their choice of title was a little unfortunate, since it quickly got shortened to “Game Theory,” Nobel Laureate and a Father of Game Theory, Lloyd S. Shapley (92), who shared the 2012 Nobel Memorial Prize in Economic Science for work on game theory that has been used to study subjects as diverse as matching couples and allocating costs 7.2 CONCEPTS Properties of a Game i. a) There are finite numbers of competitors called ‘players’ ii. b) Each player has a finite number of possible courses of action called ‘strategies’ iii. c) All the strategies and their effects are known to the players but the player does not know which strategy is to be chosen. 148 CU IDOL SELF LEARNING MATERIAL (SLM)

iv. d) A game is played when each player chooses one of his strategies. The strategies are assumed to be made simultaneously with an outcome such that no player knows his opponents strategy until he decides his own strategy. v. e) The game is a combination of the strategies and in certain units which determines the gain or loss. vi. f) The figures shown as the outcomes of strategies in a matrix form are called ‘pay-off matrix’. g) The player playing the game always tries to choose the best course of action which results in optimal pay off called ‘optimal strategy’. vii. h) The expected pay off when all the players of the game follow their optimal strategies is known as ‘value of the game’. The main objective of a problem of a game is to find the value of the game. Characteristics of Game Theory 1. Competitive game: A competitive situation is called a competitive game if it has the following four properties. There are a finite number of competitors such that n ≥ 2. In case n = 2, it is called a two-person game and in case n > 2, it is referred to as a n- person game. Each player has a list of a finite number of possible activities. A play is said to occur when each player chooses one of his activities. The choices are assumed to be made simultaneously i.e. no player knows the choice of the other until he has decided on his own. Every combination of activities determines an outcome which results in a gain of payments to each player, provided each player is playing uncompromisingly to get as much as possible. Negative gain implies the loss of the same amount. 2. Strategy: The strategy of a player is the predetermined rule by which the player decides his course of action from his own list during the game. The two types of strategy are: Pure strategy and Mixed strategy i. Pure Strategy: If a player knows exactly what the other player is going to do, a deterministic situation is obtained and the objective function is to maximize the gain. Therefore, the pure strategy is a decision rule always to select a particular course of action. ii. Mixed Strategy: If a player is guessing as to which activity is to be selected by the other on any particular occasion, a probabilistic situation is obtained and the objective function is to maximize the expected gain. Thus the mixed strategy is a selection among pure strategies with fixed probabilities. 3. Number of persons: A game is called ‘n’ person game if the number of persons playing is ‘n’. The person means an individual or a group aiming at a particular objective. 149 CU IDOL SELF LEARNING MATERIAL (SLM)

Two-person, zero-sum game: A game with only two players (player A and player B) is called a ‘two-person, zero-sum game’, if the losses of one player are equivalent to the gains of the other so that the sum of their net gains is zero. Two-person, zero-sum games are also called rectangular games as these are usually represented by a payoff matrix in a rectangular form. 4. Number of activities: The activities may be finite or infinite. 5. Payoff: The quantitative measure of satisfaction a person gets at the end of each play is called a payoff 6. Payoff matrix: Suppose player A has ‘m’ activities and the player B has ‘n’ activities. Then a payoff matrix can be formed by adopting the following rules Row designations for each matrix are the activities available to player A Column designation for each matrix are the activities available to player B Cell entry Viji is the payment to player A in A’s payoff matrix when A chooses the activity i and B chooses the activity j. With a zero-sum, two-person game, the cell entry in the player B’s payoff matrix will be negative of the corresponding cell entry Vij in the player A’s payoff matrix so that sum of payoff matrices for player A and player B is ultimately zero. 7. Value of the game: Value of the game is the maximum guaranteed game to player A (maximizing player) if both the players use their best strategies. It is generally denoted by ‘V’ and it is unique. 7.3 SOLUTIONS OF 2-PERSON GAMES Game theory provides a mathematical framework for analysing the decision-making processes and strategies of adversaries (or players) in different types of competitive situations. The simplest type of competitive situations is two-person, zero-sum games. These games involve only two players; they are called zero-sum games because one player wins whatever the other player loses. The irreconcilable, conflicting interests between the two players in a zero-sum game resemble parlour games and military encounters between enemy states. Players make moves and countermoves, until the rules of engagement declare the game is ended. The rules of engagement determine what each player can or must do at each stage (the available and/or required moves given the circumstances of the game at this stage) as the game unfolds. For example, in the game rock, paper, scissors both players simultaneously make one move, with rock beating scissors beating paper beating rock. While this game consists of only one move, games like chess require many moves to resolve the conflict. Example: Odds and Evens 150 CU IDOL SELF LEARNING MATERIAL (SLM)