CA and CMA Final

C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073 Score 60+ thro’ SYSTEMATIC & SMART Study Page 1 of 8 CHAPTER 12 : TRANSPORTATION Transportation Problems are a special category LPPs’ where the objective is to minimise total transportation cost (subject to some constraints, if any) and where there are M delivery points located at different places requi ring the materials to be catered by N production facilities which are also lo cated at different places and costs of transportation from each production facility to respective places requiring the material varies. Question State the methods in which initial feasible solution can be arrived at in a transportation problem Answer The methods by which initial feasible solution can be arrived at in a transportation model are as under: 1. North West Corner Method. 2. Least Cost Method 3. Vogel’s Approximation Method (VAM) North West Corner Method: The steps involved are: 1. First it should be ensured that the requirements and availability are same. If not, they are to be made same by adding dummy row or column. 2. First allocation is made in to the cell in the upper left han d corner and the full requirement or availability of that cell is allotted. 3. Then we move to the next cell either sidewards or downwards depending on the initial allocation and allot that cell’s requ irement or availability in full. 4. The above step is repeated till all the quantities of requir ements and availability are exhausted. By this time we will be coming to the last row / column for final allotment. C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073 Score 60+ thro’ SYSTEMATIC & SMART Study Page 2 of 8 5. This method does not use transportation costs as basis for making allotments. Least Cost Method: Steps involved in this method ar e: 1. First it should be ensured that the requirements and availability are same. If not, they are to be made same by adding dummy row or column. 2. Least cost cell in the matrix is identified and maximum allocation is done to it so that the requirement or availability of that cell is completed. 3. Then the next least cost cell is identified and maximum allocation i s done to this cell also so that the requirement or availability of that cell is completed. 4. This process is repeated till all the quantities and requirements are exhausted. In case there is a tie between one or more cells, the cell to be allotted is identified on arbitrary basis. Vogel’s Approximation Method: This is a superior method than the North West Corner method as this uses transportation costs as basis for initial allocation and this will be nearer to optimal solution. Steps involved in this method for initial allocation are: 1. First it should be ensured that the requirements and availability are same. If not, they are to be made same by adding dummy row or column. 2. Difference between the least cost cell and second least cost cell of each row and column are to be identified. 3. Of the differences arrived at 2 above, the maximum difference amount is to be identified whether it is in column or row. If the maximum difference is in column, then in that column, the least cost cell is to b e identified and maximum allocation is made to that cell so that t he requirement or availability of that cell is completely met. Similarly, if the maximum difference is in row, then the least cost cell in that row is identified and maximum allocation is made to that cell so that t he requirement or availability of that cell is completely met. In case there is a tie in the differences in amounts of one row o r column with another row or column, then the row or column having C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073 Score 60+ thro’ SYSTEMATIC & SMART Study Page 3 of 8 the least cost cell is considered. In case there is tie here also, then the cell which utilises maximum value of resources or requirements is considered. In case there is a tie at this stage also, allocation to one of the cells is made on arbitrary basis. 4. Having made the first allocation, that row or column whose resources or requirements are exhausted is not to be considered till all allocati on is complete. 5. Steps 2 and 3 are to be repeated till allocation of all requi rements and availability is completed and at each allocation, the row or column whose requirement or availability is completed should not be considered till balance allocation is completed. The difference between the least cost cell and the second least cost cel l in a row or column indicates the penalty that we will incur for not making allocation to such cell. Hence we will be decreasing the penalty by making maximum possible allocations to the cell which has the highest pe nalty successively till all the requirements and availabilities are completed. With the above steps, the allocation will be complete. But we d o not know whether it is optimal or not. Hence, this needs to be tested for optimal ity. Following steps are involved. 1. First we need to check the number of cells that have been allotted quantities. If this number is equal to m+n-1 (where m is the nu mber of rows and n is number of columns), then we can go to the next step. If not, then we need to allot e (epsilon, an infinitely small quantity) to the least cost independent unallotted cell or cells till this requirement is met. Independent cell is the one with which we cannot form a loop with this cell and other allotted cells. 2. A zero is put against a cell or row which has maximum allocations (infact, this zero can be put against any row or column but by putt ing here, it will be easy and comfortable for further calculations.) 3. Let us refer each cell costs as C ijs’. Suppose a zero, referred as U i is put against a row. Now we need to work out U is’ and Vjs’ for rest of the columns and rows based on the allotted cells. V js’ are worked out in such a way that for any cell, C ij = Ui + V j. For the columns, where there are allotments in this particular row, C i = V j since U i is zero. This process has to be repeated till all the values of U is’ (for rows) and V js’ (for columns) are obtained on the basis of allotted cells. C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073 Score 60+ thro’ SYSTEMATIC & SMART Study Page 4 of 8 4. In case of unallotted cells, the sum of respective U is’ and V js’ are entered in respective cells in a corner. 5. Now Δ ijs’ are calculated for unallotted cells by the formula Δ ij = Cij – ( U i + V j). If all the values of Δij are either 0 or +ve, then the solution is optimal. 6. In case if we get some of the Δ ijs’ as – ve then the solution is not optimal and we need to do further calculations to make it optimal . For this we need to transfer as much quantity as possible to the most negative cell from the allotted quantities of that cells row or column. Quantity to be transferred to the vacant cell is arrived by forming a closed loop (which is the one and only one loop that can be formed) with this unallotted cell and three other allotted cells. The lo op may run through some or all allotted cells also. Maximum quantity that can be transferred is the minimum figure of the diagonal figures of th e loop. Hence this figure is to be subtracted from the diagonal figure s where they exist and added to the unallotted cell and the cell diagonally opposite to the unallotted cell. 7. Having done this, again we need to check for optimality by repe ating the steps 1 to 6 till we end at step 5. Question How do you know whether an alternative solution exists for a transportation problem? Answer The Δ ij matrix = Δ ij = C ij – (u i + v j) Where c i is the cost matrix and (u i + v j) is the cell evaluation matrix for allocated cell. If the Δij matrix has one or more ‘Zero’ elements, indicating that, if that cell is brought into the solution, the optimal cost will not chang e though the allocation changes. Thus, a ‘Zero’ element in the Δ ij matrix reveals the possibility of an alternative solution. Question Explain the term degeneracy in a transportation problem. C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073 Score 60+ thro’ SYSTEMATIC & SMART Study Page 5 of 8 Answer If a basic feasible solution of a transportation problem with m origins and n destinations has fewer than m + n – 1 positive xij (occupied cells) the problem is said to be a degenerate transportation problem. Such a situa tion may be handled by introducing an infinitesimally small allo cation e in the least cost and independent cell. While in the simple computation degeneracy does not cause any serious difficulty, it can cause computational problem in transportation problem . If we apply modified distribution method, then the dual variable ui and vj are obtained from the Cij value to locate one or more Cij value which sho uld be equated to corresponding Cij + Vij. Question Will the initial solution for a minimization problem obtained by Vogel’s approximation Method and the Least Cost Method be the same? Why? Answer The initial solution need not be the same under both methods. Vogel’s Approximation Method uses the differences between the min imum and the next minimum costs for each row and column. This is the penalty or opportunity cost of not utilising the next best alternative. The highest penalty is given the 1 st preference. This need not be the lowest cost. For example if a row has minimum cost as 3, and the next minimum as 2, penalty is 1; whereas if another row has minimum 4 and next minimum 6, penalty is 2, and this row is given preference. But least cost gives preference to the lowest cost cell, irrespective of the next cost. Vogel’s Approximation Method will result in a more optimal solution than least cost. They will be the same only when the maximum penalty and the mini mum cost coincide. C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073 Score 60+ thro’ SYSTEMATIC & SMART Study Page 6 of 8 Special Points on Transportation Problems: 1. Transportation algorithm is essentially a minimisation algorithm. But this can be used for maximisation issues also. This is done by subtracting all the elements from the biggest element in the matrix and solving the resulting matrix by applying the algorithm. 2. Cells with allocations and through which a loop can be formed with other allotted cells are called dependent cells. Cells without alloca tions and through which loop cannot be formed with other allocated cells are called independent cells. 3. If some routes are to be prohibited, then this is done by all otting very high cost M to such route thus driving it out of the solution. 4. The criteria of m+n-1 allocations is to be tested for every iteration of the algorithm. This may arise during intermediate stage also. In case allocations are lesser, then this is resolved by allotting e (epsilon, infinitely small quantity) to the least cost independent cell. 5. A transhipment problem can be formulated as transportation problem by addition of another origin and destination. CHAPTER 13: ASSIGNMENT These are also another category of LPPs’ and are similar to transportation problems. It occurs when n jobs are to be assigned to n faciliti es on a one- to -one basis with a view to optimising the resource required. The steps involved in solving these types of problems are as below: 1. First it needs to be checked whether the problem is balanced or not. If it is not balanced, then it is to be made a balanced problem by add ing dummy row(s) / column(s) similar to transportation problems. 2. Subtract the minimum element of each row from all the elements in that row. From the resulting matrix, the minimum element of each column is to be subtracted from all the elements of that column. The resulting matrix is the one which needs to be tested for optimality. 3. Optimality test is done by drawing minimum horizontal and vertical lines (not diagonal lines) over the rows and columns of the matrix in such a way that all zeros are covered. If the number of lines required C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073 Score 60+ thro’ SYSTEMATIC & SMART Study Page 7 of 8 to cover zeros is equal to the order of the matrix then it is opti mal solution. If the lines required to cover zeros is not equal to t he order of the matrix, then we need to do the following to increase the zeros in the matrix. 4. From the elements that are not covered by any lines in the matrix, t he least element is selected. This value is deducted from all elements uncovered by lines in the matrix. Further, the least element selected should be added to all the elements at intersecting points in the matrix. Care should be taken to ensure that Elements covered by lines in the matrix are retained as they are and are not changed. 5. Now optimality test as indicated in point 3 is to be carried on . If the findings go through the test, then it is ready for allocation. If not, point 4 is to be repeated and then point 3 till optimality is reached. 6. Once optimality is reached, allocations are made by encircling the zeros in rows / columns. First the rows and columns containing single zeros are encircled. Rest of the allocations are made in such a way that each column and row has only one zero encircled meaning the tie up between resources and requirements. For the sake of convenience, once an allotment is made respective row and column are shaded so that these will not be considered again for allocation. Rationale of the Assignment Algorithm: The relative cost of assigning facility i to job j is not changed by the subtraction (or addition also) of a constant from either a column or a row of the original cost matrix. An optimal assignment exists if total reduced cost of the assignment is z ero. This is the case when the minimum number of lines necessary to cover all zeros is equal to the order of the matrix. If, however, it is less than n, a further reduction of the cost matrix has to be undertaken. Question Just after row and column minimum operations, we find that a particular ro w has 2 zeroes. Does this imply that the 2 corresponding numbers in t he original matrix before any operation were equal? Why? Answer The prerequisite to assign any job is that each row and column must ha ve a C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073 Score 60+ thro’ SYSTEMATIC & SMART Study Page 8 of 8 zero value in its corresponding cells. If any row or column does not hav e any zero value then to obtain zero value, each cell values in th e row or column is subtracted by the corresponding minimum cell value of respective rows or columns by performing row or column operation. This means if any row or column have two or more cells having same minimum value then these row or column will have more than one zero. However, having two zeros doe s not necessarily imply two equal values in the original assignment matrix jus t before row and column operations. Two zeroes in a same row can also be possible by two different operations i.e. one zero from row operation and one zero from column operation. Question Under the usual notation, where a 32 means the element at the intersection of the 3rd row and 2nd column, we have, in a 4 × 4 assignment problem, a 24 and a 32 figuring in the optimal solution. What can you conclude about the remaining assignments? Why? Answer The order of matrix in the assignment problem is 4 × 4. The total assignment (allocations) will be four. In the assignment problem when any allocation is made in any cell then the corresponding row and column become unavailable for further allocation. Hence, these corresponding row and column are crossed mark to show unavailability. In the given assignment matrix two allocations have been made in a 24 (2 nd row and 4 th column) and a 32 (3 rd row and 2 nd column). This implies that 2 nd and 3 rd row and 4 th and 2 nd column are unavailable for further allocation. Therefore, the other allocations are at either at a 11 and a 43 or at a 13 and a 41. Special Points on Assignment Problems: 1. Assignment algorithm is essentially a minimisation algorithm. But this can be used for maximisation issues also. This is done by subtracting all the elements from the biggest element in the matrix and solving the resulting matrix by applying the algorithm. 2. If some persons are not to be allotted jobs, then this is done by allotting very high cost M to such person thus driving it out of the solution. 2 3