ASSIGNMENT THEORY
1) When do we say that an Assignment problem is unbalanced? How do you balance it? Ans: (a) Unbalanced Assignment Problem: Whenever the pay-off matrix of an assignment problem is not a square matrix i.e. no. of rows is not equal to the no. of columns, the assignment problem is called an unbalanced assignment problem. E.g. 5 workers are to be assigned to 6 machines or 6 salesmen to be assigned to 5 territories etc. In such cases, dummy rows or columns are added to the matrix to make it a square matrix. E.g. in the first case above, dummy row is required to be added and in the second case, a dummy column required to be added a square (6 x 6) matrix. The elements of the dummy rows or column are all taken as zero. The usual Hungarian method can then the applied on this balanced or square matrix to obtain the optimal solution. (b) In case the problem is unbalanced maximization problem, we first convert the maximization problem into minimization problem by subtracting each element of the matrix from maximum element. 3) Explain the Hungarian Method for solving on Assignment Problem. Ans. Hungarian Method for solving on Assignment Problem: In the following procedure Step 1 is applied on the given assignment matrix and each of the subsequent steps is applied on the matrix obtained in the earlier step. Step 1: Subtract smallest element in each row from every element of that row.
Step 2: Subtract smallest element in each column from every element of that column.
Step 3: (a) Examine the rows of the matrix successively until a row containing exactly one zero is found. E nclose this zero in a box ( ) as an assignment will be made at this position. Cancel (x) all other zeros appearing in the corresponding column. Proceed in this way till all the rows are examined. (b) On the similar lines examine the columns successively making an assignment for the single zero whenever it is found and canceling all zeros appearing in the Corresponding row. Repeat (a) and (b) successively until all the zeros of the matrix are either assigned or cancelled.
Step 4: If the number of assignments in the matrix is same as the order of the matrix (i.e. N Assignments for N x N matrix), the optimum solution is reached. If not, proceed to step
Step 5: Draw minimum number of vertical and horizontal lines necessary to cover all the zeros (assigned and cancelled) of the matrix obtained in step 3. This can be done as follows: (i) Marks (? ) all rows that do not have assignments. (ii) Marks (? ) all columns, which have zeros in the marked rows. (iii) Marks (? ) all rows, which have assignments in the marked columns Repeat (ii) and (iii) till further marking is not possible. Then draw lines through unmarked rows and marked columns.
Step 6: Select smallest element from all the uncovered elements. Subtract this smallest element from all the uncovered elements and add it to the elements, which lie at the intersection of horizontal and vertical lines. Remaining elements of the matrix are unchanged. Step 7: Repeat step 3 and 4 until an optimum solution is reached. Q4) What are the various variations in an Assignment Problem? Maximization Sometimes, an assignment problem deals with the maximization of an objective function rather than to minimize it. For example, it may be required to assign persons to jobs in such a way that the expected profit is maximum. Such a problem can be solved easily by first converting it into a minimization type of a problem, and then applying the usual procedure of assignment algorithm. This conversion can be very easily done by subtracting from the highest element, all the elements of the given profit matrix; or equivalently, by placing minus – sign before each element of the profit-matrix in order to make it a cost matrix. Sometimes, technical, legal or other restrictions do not permit the assignment of a particular facility to a particular job. Such difficulty can be overcome by assigning a very high cost (say, infinite cost) to the corresponding cell, so that the activity will be automatically excluded from the optimum solution. 6) Why Transportation Method is inconvenient to solve an Assignment Problem? Assignment Problem is a special case of a transportation problem. But, the solution by this method would be severely degenerate, since the optimality test in the transportation method requires that there must be n + n – 1, i.e., 2 n – 1 basic variables. For an assignment made, there will be only n basic variables in the solution. Hence, in order to proceed with this method, a very large number of epsilons, “ e “ (i.e., dummy allocations) will be needed to be introduced in the solution which will make the transportation method computationally cumbersome and inefficient.
7) Multiple Optimal Solutions in an Assignment Problem Sometimes, it is possible to have two or more ways to cross out all zero elements in the final reduced problem in a given problem. This implies that there is more than the required number of independent zero elements. In such cases, there will be multiple optimal solutions with the same total assignment.
8) Restrictions on Assignments It is sometimes possible that a particular person is incapable of doing certain work or a specific job cannot be performed on a particular machine. The solution of the assignment problem should take into account these restrictions so that the infeasible assignments can be avoided. This can be achieved by assigning a very high cost ( written as M or ¥ ) to the cells where assignments are prohibited. This also prohibits the entry of this pair or resource – activity into the final solution.
9) Opportunity Costs They are the costs associated with a sacrificed opportunity in order to make a particular decision 10) Dummy Job It is an imaginary job, which has a zero cost or a zero time, and it is introduced to make an unbalanced Assignment problem into a balanced one. TRANSPORTATION THEORY
Q.1 What is Transportation Problem?
Ans. The structure of transportation problem involves a large number of shipping routes from several supply origins to several demand destinations. The objective is to determine the number of units which should be shipped from each origin to each destination in order to satisfy the required quantity of goods or services at each demand destination, which the limited quantity of goods or services available at each supply origin, at the minimum transportation cost and / or time. The transportation algorithm is applied to minimize the total cost of transporting a homogeneous commodity from supply origins to demand destinations. However, it can also be applied to the maximization of some total value or utility, for example, financial resources are distributed in such a way that the profitable return is maximized.
Q.3 Explain Transportation algorithm. Ans. The solution algorithm to a transportation problem may be summarized into the following steps: Step 1: Formulate the problem and set up in the matrix form The formulation of the transportation problem is similar to the LP problem formulation. Here the objective function is the total transportation cost and the constraints are the supply and demand available at each source and Destination, respectively.
Step 2: Obtain an initial basic feasible solution: Use any of the following three different methods to obtain an initial solution: (i) North-West Corner Method (ii) Least Cost Method and (iii) Vogel’s approximation (or Penalty) Method. The initial solution obtained by any of the three methods must satisfy the following conditions: (i) The solution must be feasible, i.e. it must satisfy all the supply and demand constraints (also called rim Conditions). (ii) The number of positive allocations must be equal to m + n – 1, when m is the number of rows and n is the Number of columns. Any solution that satisfies the above conditions is called non-degenerate basic feasible solution, otherwise, degenerate solution. Step 3: Test the initial solution for optimality: Use the Modified Distribution (MODI) method to test the optimality of the solution obtained in Step 2. If the current solution is optimal, then stop. Otherwise, determine a new improved solution.
Step 4: Updating the solution: Repeat Step 3 until an optimal solution is reached. Q.4 Explain North-West Corner Method (NWCM), or, DENTZY’S Method Ans. It is a simple and efficient method to obtain an initial solution. This method does not take into account the cost of transportation on any route of transportation. The method can be summarized as follows:
Step 1: Start with the cell at the upper left (north-west) corner of the transportation matrix and allocate as much as possible equal to the minimum of the rim values for the first row and first column, i.e. min. (a1 , b1)
Step 2: (a) If allocation made in Step 1 is equal to the supply available at first source (a1 , in first row), then move vertically down to the cell (2,1) in the second row and first column and apply Step 1 again for next allocation. (b) If allocation made in Step 1 is equal to the demand of the first destination (b1 in first column), then move horizontally to the cell (1, 2) in the first row and second column and apply Step 1 again for next allocation. (c) If a1 = b1 , allocate x11 = a1 or b1 and move diagonally to the cell (2, 2).
Step 3: Continue the procedure step by step till an allocation is made in the south-east corner cell of the transportation table. Remark: If during the process of making allocation at a particular cell, supply equals demand, then next allocation of magnitude zero can be made in a cell either in the next row or column. This condition is known as degeneracy.
Q.5 Explain Least Cost Method (LCM). Ans. Since the objective is to minimize the total transportation cost, we must try to transport as much as possible through those routes (cells) where the unit transportation cost is lowest. This method takes into account the minimum unit cost of transportation for obtaining initial solution and can be summarized as follows: Step 1: Select the cell with the lowest unit cost in the entire transportation table and allocate as much as possible to this cell and eliminate (line out) that row or column in which either supply or demand is exhausted. If both a row and a column are satisfied simultaneously, only one may be crossed out. In case the smallest unit cost cell is not unique, then select the cell where maximum allocation can be made.
Step 2: After adjusting the supply and demand for all uncrossed-out rows and columns repeat the procedure with the next lowest unit cost among the remaining rows and columns of the transportation table and allocate as much as possible to this cell and eliminate (line out) that row and column in which either supply or demand is exhausted. Step 3: Repeat the procedure until the entire available supply at various sources and demand at various destinations is satisfied. The solution so obtained need not be non-degenerate.
Q.6 Explain Vogel’s Approximation Method (VAM). Ans. Vogel’s approximation (penalty or regret) method is a heuristic method and is preferred to the other two methods described above. In this method, each allocation is made on the basis of the
opportunity (or penalty or extra) cost that would have been incurred if allocations in certain cells with minimum unit transportation cost were missed. In this method allocations are made so that the penalty cost is minimized. The advantage of this method is that it gives an initial solution which is nearer to an optimal solution or is the optimal solution itself. The steps in VAM are as follows:
Step 1: Calculate penalties for each row (column) by taking the difference between the smallest and next smallest unit transportation cost in the same row (column). This difference indicates the penalty or extra cost which has to be paid if one fails to allocate to the cell with the minimum unit transportation cost.
Step 2: Select the row or column with the largest penalty and allocate as much as possible in the cell having the least cost in the selected row or column satisfying the rim conditions. If there is a tie in the values of penalties, it can be broken by selecting the cell where maximum allocation can be made. Step 3: Adjust the supply and demand and cross out the satisfied row or column. If a row and a column are satisfied simultaneously, only one of them is crossed out and the remaining row (column) is assigned a zero supply (demand). Any row or column with zero supply or demand should not be used in computing future penalties. Step 4: Repeat Steps 1 to 3 until the entire available supply of various sources and demand at various destinations are satisfied. Q.7 what are the various possible types of solutions in a Transportation problem? For a balanced transportation problem, the matrix of allocations represents either a) a solution b) not a solution
When a solution is available to a transportation problem, the row totals and the column totals must match with the availabilities at the origins and destinations. Here, there are two types of solutions a) Infeasible solution This happens when some of the allocations are negative b) Feasible solution It consists of a set of non – negative individual allocations ( xij ?? 0) which simultaneously removes Deficiencies In feasible solution, we have two types: i) Non ? basic Feasible Solution This happens when number of positive allocations is > m + n – 1. [Note carefully that The sign of inequality does not have an equal to (=) sign]
ii) Basic Feasible Solution This is obtained when the number of positive allocations is ? m + n – 1
In basic feasible solution, there are further two types: a) Degenerate Basic Feasible Solution Number of positive allocations < m + n – 1
b) Non – degenerate Basic Feasible Solution Number of positive allocations ? m + n – 1 Q.8 Optimum Solution A feasible solution is optimum (not necessarily basic) if it minimizes the total transportation cost Q.9 Loops in a Transportation Table An ordered set of at least four cells in a transportation table is said to form a loop provided: a) Any two adjacent cells of the ordered pair lie either in the same row or in the same column b) An even number of at least four cells must participate in a closed loop c) All cells that receive a plus or a minus sign, except the starting unoccupied cell, must necessarily be occupied cells d) Closed loops may or may not necessarily be square in shape e) “Loop lines” are horizontal or vertical, but never diagonal f) Note: clockwise or anti-clockwise movement of loops does not affect the solution g) If need be, step over empty or occupied cells h) Loops have only right-angled turns with corners being occupied cells (except starting point)
Q.10 Unbalanced Transportation Problem In a balanced transportation problem, aggregate supply equals the aggregate demand. However, in practice, they may not necessarily be equal. When the aggregate supply exceeds the aggregate demand, the excess supply is assumed to go To inventory and costs nothing. A column of slack variables is added to the transportation table which represents a dummy destination with a requirement equal to the amount of excess supply, and the Transportation costs equal to zero. When the aggregate demand exceeds the aggregate supply, adding a dummy origin restores balance. Each added cell in the dummy has a zero cost.
Sometimes, in certain transportation problems, a penalty clause is included in the contract. That is, a penalty has to be paid for NOT SATISFYING a certain demand at a particular destination(s).In such cases, the cost in the dummy cells should NOT be zero, but it should contain the values of the penalty cost.
Q.11 Prohibited Routes in Transportation It may happen that, in certain transportation problems, some route(s) may not be available for transportation. This could be due to a variety of reasons like unfavorable weather conditions on a particular route, or, strike on a Particular route, etc. In such cases, there is a restriction on the routes available for transportation. To handle a Situation of this type, we assign a very large cost (represented by M or ?) to each of such routes which are not available. Then the problem is solved in the usual way. The effect of adding a large cost element would be that such routes would automatically be eliminated in the final solution.
Q.12 Multiple Optimal Solutions The optimal solution to a given transportation problem may or may not be unique. In terms of the MODI method, The solution to a transportation problem is optimal and unique if all the ? values are negative. If, ij however, some cell(s) has ? ij value(s) equal to zero, then multiple optimal solutions exist. In other words, there exists transportation pattern(s) other than the one obtained which can satisfy all the rim requirements at the same minimum cost. To obtain the alternative optimal solution, trace a closed loop beginning with the cell having ? ij = 0. Get a revised solution in the same way as done earlier. This revised solution would entail the same minimum transportation cost. In fact, for every “zero” value of ? ij in the optimal solution, a revised solution can be obtained. Q.13 Basic and non – basic variables in transportation The allocations or values in the occupied or filled cells are called basic variables. The remaining cells which are empty, the allocations are zero. The variables are called non-basic. Q.14 Rim requirements The requirements of demand and supply which have to be satisfied to obtain a feasible solution are called as the rim requirements. Q.15 Degeneracy in Transportation A basic feasible solution of a transportation problem has m + n – 1 occupied cells. However, it may happen that the number of occupied cells is less than m + n – 1, in some other transportation problem. Such a solution is called as a Degenerate Solution. Degeneracy in transportation can happen in two ways: c) A transportation problem may become degenerate in the first instance when an initial feasible solution is obtained. d) The problem may become degenerate when two or more cells are vacated simultaneously in the Process of transferring units along the closed path.
A degenerate transportation problem cannot be tested for optimality. In the MODI method, it is not possible to calculate all the ui and vj. To overcome this problem, an infinitesimally small amount, close to zero, is assigned to one (or more) empty cell and treat the cell as an occupied cell. This amount is represented by Greek letter ? (epsilon) and is taken to be such an insignificant value that it will not affect the total cost. Thus, ? is big enough to cause the particular route to which it is assigned to be considered as a basic variable, but, at the same time, it is not large enough to cause a change in the total cost and the other non – zero amounts. Although ? is, theoretically, non – zero, The operations with it in the context of problem at hand are as under: k+? k-? 0+? =k? =k? =? +? –? kx? =? =0 =0 to an independent empty cell.
When the initial basic feasible solution is degenerate, we assign ? An
Independent empty cell is the one (originating) from which a closed loop cannot be traced. An ? may Be assigned to any of the independent cells, but preferably to the one with minimum per unit cost. After Introducing ? , the problem is solved further in the usual manner.
Q.16 Maximization problem in transportation In a minimization type of a transportation problem, the table contains unit costs. In a maximization type of a Transportation problem, the table contains unit profits. The objective function is maximization of profits. One of the methods of solving this type of transportation problem is to first convert it into a minimization type of a Problem. Here, all the values of the profit matrix are subtracted from the highest profit value in the matrix .Once this is done, the optimal solution is obtained as in the case of the minimization type of a problem. However, the value of the objective function is determined with reference to the original profit matrix. If the maximization type of the transportation problem is an unbalanced one then, before converting it into a minimization type of a problem, the necessary dummy row/column must be first introduced for a source/ Destination. Similarly, if a maximization type of problem has a prohibited route, then the payoff element for such a Route should be substituted by “ – M “ before converting it into a minimization type of a problem. Q.17 (Important aspect of a transportation problem)
Sometimes a transportation problem is given in a mixed form, which consists of fixed cost, variable cost of Production, transportation, sales price, etc. In solving such a problem, following aspects must be considered: e) Fixed cost cannot be considered f) Variable cost consists of conversion cost and transportation cost g) Ex-factory cost remains the same, irrespective of their sales outlet h) Sales price at each sales outlet is assumed to be constant, so that the only variable cost is that of Transportation e) Minimization of “cost operation” ,or, “maximization of profit” really means optimization (minimization) of total transportation cost.
doc_787391436.doc
1) When do we say that an Assignment problem is unbalanced? How do you balance it? Ans: (a) Unbalanced Assignment Problem: Whenever the pay-off matrix of an assignment problem is not a square matrix i.e. no. of rows is not equal to the no. of columns, the assignment problem is called an unbalanced assignment problem. E.g. 5 workers are to be assigned to 6 machines or 6 salesmen to be assigned to 5 territories etc. In such cases, dummy rows or columns are added to the matrix to make it a square matrix. E.g. in the first case above, dummy row is required to be added and in the second case, a dummy column required to be added a square (6 x 6) matrix. The elements of the dummy rows or column are all taken as zero. The usual Hungarian method can then the applied on this balanced or square matrix to obtain the optimal solution. (b) In case the problem is unbalanced maximization problem, we first convert the maximization problem into minimization problem by subtracting each element of the matrix from maximum element. 3) Explain the Hungarian Method for solving on Assignment Problem. Ans. Hungarian Method for solving on Assignment Problem: In the following procedure Step 1 is applied on the given assignment matrix and each of the subsequent steps is applied on the matrix obtained in the earlier step. Step 1: Subtract smallest element in each row from every element of that row.
Step 2: Subtract smallest element in each column from every element of that column.
Step 3: (a) Examine the rows of the matrix successively until a row containing exactly one zero is found. E nclose this zero in a box ( ) as an assignment will be made at this position. Cancel (x) all other zeros appearing in the corresponding column. Proceed in this way till all the rows are examined. (b) On the similar lines examine the columns successively making an assignment for the single zero whenever it is found and canceling all zeros appearing in the Corresponding row. Repeat (a) and (b) successively until all the zeros of the matrix are either assigned or cancelled.
Step 4: If the number of assignments in the matrix is same as the order of the matrix (i.e. N Assignments for N x N matrix), the optimum solution is reached. If not, proceed to step
Step 5: Draw minimum number of vertical and horizontal lines necessary to cover all the zeros (assigned and cancelled) of the matrix obtained in step 3. This can be done as follows: (i) Marks (? ) all rows that do not have assignments. (ii) Marks (? ) all columns, which have zeros in the marked rows. (iii) Marks (? ) all rows, which have assignments in the marked columns Repeat (ii) and (iii) till further marking is not possible. Then draw lines through unmarked rows and marked columns.
Step 6: Select smallest element from all the uncovered elements. Subtract this smallest element from all the uncovered elements and add it to the elements, which lie at the intersection of horizontal and vertical lines. Remaining elements of the matrix are unchanged. Step 7: Repeat step 3 and 4 until an optimum solution is reached. Q4) What are the various variations in an Assignment Problem? Maximization Sometimes, an assignment problem deals with the maximization of an objective function rather than to minimize it. For example, it may be required to assign persons to jobs in such a way that the expected profit is maximum. Such a problem can be solved easily by first converting it into a minimization type of a problem, and then applying the usual procedure of assignment algorithm. This conversion can be very easily done by subtracting from the highest element, all the elements of the given profit matrix; or equivalently, by placing minus – sign before each element of the profit-matrix in order to make it a cost matrix. Sometimes, technical, legal or other restrictions do not permit the assignment of a particular facility to a particular job. Such difficulty can be overcome by assigning a very high cost (say, infinite cost) to the corresponding cell, so that the activity will be automatically excluded from the optimum solution. 6) Why Transportation Method is inconvenient to solve an Assignment Problem? Assignment Problem is a special case of a transportation problem. But, the solution by this method would be severely degenerate, since the optimality test in the transportation method requires that there must be n + n – 1, i.e., 2 n – 1 basic variables. For an assignment made, there will be only n basic variables in the solution. Hence, in order to proceed with this method, a very large number of epsilons, “ e “ (i.e., dummy allocations) will be needed to be introduced in the solution which will make the transportation method computationally cumbersome and inefficient.
7) Multiple Optimal Solutions in an Assignment Problem Sometimes, it is possible to have two or more ways to cross out all zero elements in the final reduced problem in a given problem. This implies that there is more than the required number of independent zero elements. In such cases, there will be multiple optimal solutions with the same total assignment.
8) Restrictions on Assignments It is sometimes possible that a particular person is incapable of doing certain work or a specific job cannot be performed on a particular machine. The solution of the assignment problem should take into account these restrictions so that the infeasible assignments can be avoided. This can be achieved by assigning a very high cost ( written as M or ¥ ) to the cells where assignments are prohibited. This also prohibits the entry of this pair or resource – activity into the final solution.
9) Opportunity Costs They are the costs associated with a sacrificed opportunity in order to make a particular decision 10) Dummy Job It is an imaginary job, which has a zero cost or a zero time, and it is introduced to make an unbalanced Assignment problem into a balanced one. TRANSPORTATION THEORY
Q.1 What is Transportation Problem?
Ans. The structure of transportation problem involves a large number of shipping routes from several supply origins to several demand destinations. The objective is to determine the number of units which should be shipped from each origin to each destination in order to satisfy the required quantity of goods or services at each demand destination, which the limited quantity of goods or services available at each supply origin, at the minimum transportation cost and / or time. The transportation algorithm is applied to minimize the total cost of transporting a homogeneous commodity from supply origins to demand destinations. However, it can also be applied to the maximization of some total value or utility, for example, financial resources are distributed in such a way that the profitable return is maximized.
Q.3 Explain Transportation algorithm. Ans. The solution algorithm to a transportation problem may be summarized into the following steps: Step 1: Formulate the problem and set up in the matrix form The formulation of the transportation problem is similar to the LP problem formulation. Here the objective function is the total transportation cost and the constraints are the supply and demand available at each source and Destination, respectively.
Step 2: Obtain an initial basic feasible solution: Use any of the following three different methods to obtain an initial solution: (i) North-West Corner Method (ii) Least Cost Method and (iii) Vogel’s approximation (or Penalty) Method. The initial solution obtained by any of the three methods must satisfy the following conditions: (i) The solution must be feasible, i.e. it must satisfy all the supply and demand constraints (also called rim Conditions). (ii) The number of positive allocations must be equal to m + n – 1, when m is the number of rows and n is the Number of columns. Any solution that satisfies the above conditions is called non-degenerate basic feasible solution, otherwise, degenerate solution. Step 3: Test the initial solution for optimality: Use the Modified Distribution (MODI) method to test the optimality of the solution obtained in Step 2. If the current solution is optimal, then stop. Otherwise, determine a new improved solution.
Step 4: Updating the solution: Repeat Step 3 until an optimal solution is reached. Q.4 Explain North-West Corner Method (NWCM), or, DENTZY’S Method Ans. It is a simple and efficient method to obtain an initial solution. This method does not take into account the cost of transportation on any route of transportation. The method can be summarized as follows:
Step 1: Start with the cell at the upper left (north-west) corner of the transportation matrix and allocate as much as possible equal to the minimum of the rim values for the first row and first column, i.e. min. (a1 , b1)
Step 2: (a) If allocation made in Step 1 is equal to the supply available at first source (a1 , in first row), then move vertically down to the cell (2,1) in the second row and first column and apply Step 1 again for next allocation. (b) If allocation made in Step 1 is equal to the demand of the first destination (b1 in first column), then move horizontally to the cell (1, 2) in the first row and second column and apply Step 1 again for next allocation. (c) If a1 = b1 , allocate x11 = a1 or b1 and move diagonally to the cell (2, 2).
Step 3: Continue the procedure step by step till an allocation is made in the south-east corner cell of the transportation table. Remark: If during the process of making allocation at a particular cell, supply equals demand, then next allocation of magnitude zero can be made in a cell either in the next row or column. This condition is known as degeneracy.
Q.5 Explain Least Cost Method (LCM). Ans. Since the objective is to minimize the total transportation cost, we must try to transport as much as possible through those routes (cells) where the unit transportation cost is lowest. This method takes into account the minimum unit cost of transportation for obtaining initial solution and can be summarized as follows: Step 1: Select the cell with the lowest unit cost in the entire transportation table and allocate as much as possible to this cell and eliminate (line out) that row or column in which either supply or demand is exhausted. If both a row and a column are satisfied simultaneously, only one may be crossed out. In case the smallest unit cost cell is not unique, then select the cell where maximum allocation can be made.
Step 2: After adjusting the supply and demand for all uncrossed-out rows and columns repeat the procedure with the next lowest unit cost among the remaining rows and columns of the transportation table and allocate as much as possible to this cell and eliminate (line out) that row and column in which either supply or demand is exhausted. Step 3: Repeat the procedure until the entire available supply at various sources and demand at various destinations is satisfied. The solution so obtained need not be non-degenerate.
Q.6 Explain Vogel’s Approximation Method (VAM). Ans. Vogel’s approximation (penalty or regret) method is a heuristic method and is preferred to the other two methods described above. In this method, each allocation is made on the basis of the
opportunity (or penalty or extra) cost that would have been incurred if allocations in certain cells with minimum unit transportation cost were missed. In this method allocations are made so that the penalty cost is minimized. The advantage of this method is that it gives an initial solution which is nearer to an optimal solution or is the optimal solution itself. The steps in VAM are as follows:
Step 1: Calculate penalties for each row (column) by taking the difference between the smallest and next smallest unit transportation cost in the same row (column). This difference indicates the penalty or extra cost which has to be paid if one fails to allocate to the cell with the minimum unit transportation cost.
Step 2: Select the row or column with the largest penalty and allocate as much as possible in the cell having the least cost in the selected row or column satisfying the rim conditions. If there is a tie in the values of penalties, it can be broken by selecting the cell where maximum allocation can be made. Step 3: Adjust the supply and demand and cross out the satisfied row or column. If a row and a column are satisfied simultaneously, only one of them is crossed out and the remaining row (column) is assigned a zero supply (demand). Any row or column with zero supply or demand should not be used in computing future penalties. Step 4: Repeat Steps 1 to 3 until the entire available supply of various sources and demand at various destinations are satisfied. Q.7 what are the various possible types of solutions in a Transportation problem? For a balanced transportation problem, the matrix of allocations represents either a) a solution b) not a solution
When a solution is available to a transportation problem, the row totals and the column totals must match with the availabilities at the origins and destinations. Here, there are two types of solutions a) Infeasible solution This happens when some of the allocations are negative b) Feasible solution It consists of a set of non – negative individual allocations ( xij ?? 0) which simultaneously removes Deficiencies In feasible solution, we have two types: i) Non ? basic Feasible Solution This happens when number of positive allocations is > m + n – 1. [Note carefully that The sign of inequality does not have an equal to (=) sign]
ii) Basic Feasible Solution This is obtained when the number of positive allocations is ? m + n – 1
In basic feasible solution, there are further two types: a) Degenerate Basic Feasible Solution Number of positive allocations < m + n – 1
b) Non – degenerate Basic Feasible Solution Number of positive allocations ? m + n – 1 Q.8 Optimum Solution A feasible solution is optimum (not necessarily basic) if it minimizes the total transportation cost Q.9 Loops in a Transportation Table An ordered set of at least four cells in a transportation table is said to form a loop provided: a) Any two adjacent cells of the ordered pair lie either in the same row or in the same column b) An even number of at least four cells must participate in a closed loop c) All cells that receive a plus or a minus sign, except the starting unoccupied cell, must necessarily be occupied cells d) Closed loops may or may not necessarily be square in shape e) “Loop lines” are horizontal or vertical, but never diagonal f) Note: clockwise or anti-clockwise movement of loops does not affect the solution g) If need be, step over empty or occupied cells h) Loops have only right-angled turns with corners being occupied cells (except starting point)
Q.10 Unbalanced Transportation Problem In a balanced transportation problem, aggregate supply equals the aggregate demand. However, in practice, they may not necessarily be equal. When the aggregate supply exceeds the aggregate demand, the excess supply is assumed to go To inventory and costs nothing. A column of slack variables is added to the transportation table which represents a dummy destination with a requirement equal to the amount of excess supply, and the Transportation costs equal to zero. When the aggregate demand exceeds the aggregate supply, adding a dummy origin restores balance. Each added cell in the dummy has a zero cost.
Sometimes, in certain transportation problems, a penalty clause is included in the contract. That is, a penalty has to be paid for NOT SATISFYING a certain demand at a particular destination(s).In such cases, the cost in the dummy cells should NOT be zero, but it should contain the values of the penalty cost.
Q.11 Prohibited Routes in Transportation It may happen that, in certain transportation problems, some route(s) may not be available for transportation. This could be due to a variety of reasons like unfavorable weather conditions on a particular route, or, strike on a Particular route, etc. In such cases, there is a restriction on the routes available for transportation. To handle a Situation of this type, we assign a very large cost (represented by M or ?) to each of such routes which are not available. Then the problem is solved in the usual way. The effect of adding a large cost element would be that such routes would automatically be eliminated in the final solution.
Q.12 Multiple Optimal Solutions The optimal solution to a given transportation problem may or may not be unique. In terms of the MODI method, The solution to a transportation problem is optimal and unique if all the ? values are negative. If, ij however, some cell(s) has ? ij value(s) equal to zero, then multiple optimal solutions exist. In other words, there exists transportation pattern(s) other than the one obtained which can satisfy all the rim requirements at the same minimum cost. To obtain the alternative optimal solution, trace a closed loop beginning with the cell having ? ij = 0. Get a revised solution in the same way as done earlier. This revised solution would entail the same minimum transportation cost. In fact, for every “zero” value of ? ij in the optimal solution, a revised solution can be obtained. Q.13 Basic and non – basic variables in transportation The allocations or values in the occupied or filled cells are called basic variables. The remaining cells which are empty, the allocations are zero. The variables are called non-basic. Q.14 Rim requirements The requirements of demand and supply which have to be satisfied to obtain a feasible solution are called as the rim requirements. Q.15 Degeneracy in Transportation A basic feasible solution of a transportation problem has m + n – 1 occupied cells. However, it may happen that the number of occupied cells is less than m + n – 1, in some other transportation problem. Such a solution is called as a Degenerate Solution. Degeneracy in transportation can happen in two ways: c) A transportation problem may become degenerate in the first instance when an initial feasible solution is obtained. d) The problem may become degenerate when two or more cells are vacated simultaneously in the Process of transferring units along the closed path.
A degenerate transportation problem cannot be tested for optimality. In the MODI method, it is not possible to calculate all the ui and vj. To overcome this problem, an infinitesimally small amount, close to zero, is assigned to one (or more) empty cell and treat the cell as an occupied cell. This amount is represented by Greek letter ? (epsilon) and is taken to be such an insignificant value that it will not affect the total cost. Thus, ? is big enough to cause the particular route to which it is assigned to be considered as a basic variable, but, at the same time, it is not large enough to cause a change in the total cost and the other non – zero amounts. Although ? is, theoretically, non – zero, The operations with it in the context of problem at hand are as under: k+? k-? 0+? =k? =k? =? +? –? kx? =? =0 =0 to an independent empty cell.
When the initial basic feasible solution is degenerate, we assign ? An
Independent empty cell is the one (originating) from which a closed loop cannot be traced. An ? may Be assigned to any of the independent cells, but preferably to the one with minimum per unit cost. After Introducing ? , the problem is solved further in the usual manner.
Q.16 Maximization problem in transportation In a minimization type of a transportation problem, the table contains unit costs. In a maximization type of a Transportation problem, the table contains unit profits. The objective function is maximization of profits. One of the methods of solving this type of transportation problem is to first convert it into a minimization type of a Problem. Here, all the values of the profit matrix are subtracted from the highest profit value in the matrix .Once this is done, the optimal solution is obtained as in the case of the minimization type of a problem. However, the value of the objective function is determined with reference to the original profit matrix. If the maximization type of the transportation problem is an unbalanced one then, before converting it into a minimization type of a problem, the necessary dummy row/column must be first introduced for a source/ Destination. Similarly, if a maximization type of problem has a prohibited route, then the payoff element for such a Route should be substituted by “ – M “ before converting it into a minimization type of a problem. Q.17 (Important aspect of a transportation problem)
Sometimes a transportation problem is given in a mixed form, which consists of fixed cost, variable cost of Production, transportation, sales price, etc. In solving such a problem, following aspects must be considered: e) Fixed cost cannot be considered f) Variable cost consists of conversion cost and transportation cost g) Ex-factory cost remains the same, irrespective of their sales outlet h) Sales price at each sales outlet is assumed to be constant, so that the only variable cost is that of Transportation e) Minimization of “cost operation” ,or, “maximization of profit” really means optimization (minimization) of total transportation cost.
doc_787391436.doc