North-West Corner Method versus Stepping-Stone Method - Coursework Example

TRANSPORTATION AND ASSIGNMENT MODELS Introduction The methods that we are going to analyze are the Stepping stone model, the Modified distribution model (MODI), North West corner method, Vogel’s Approximation method and the assignment model. They are also referred to as special purpose algorithms for solving linear programming problems. They are simple and easy to understand. They are a branch of management science called cost management. The methods apply statistical and mathematical knowledge to optimize costs. These models are used to solve linear programming problems. Suppose a firm have several production plants in different locations and several warehouses in different locations. Transporting goods from each production plant to the warehouse will be faced with several obstacles like plant production capacity, warehouse capacity/demand, and transport costs. Given these constraints, managers are faced with the difficult task of scheduling transport routes, journeys and quantities to achieve minimum costs. In this study, we are going to adapt several methods to understand the techniques involved and the results achieved. We shall study the variations of the methods plus their results. The models assume that transportation costs are constant, monthly demand and factory average production are fixed (Havlisek, January 2007). Let us consider a digital firm that has several production units and different warehouses where distribution activities are carried out i.e. unit1, unit2, unit3 and warehouse A, warehouse B & warehouse C. The number of paths is 9 i.e. 3*3 =9. Each path has its own cost as illustrated below: TRANSPORTATION COSTS FOR DIGITAL FIRM 3 WAREHOUSES-3 PRODUCTION PLANTS WAREHOUSE 1 2 3 PLANT A 4 5 6 B 9 6 8 C 5 5 3 Table 1 The quantity of goods (for this case) is equal for both supply (production capacity) and demand (warehouse capacity). It is represented in the following example: AMOUNT OF GOODS TO BE TRANSPORTED Warehouse plant capacity 1 2 3 Plant A 600 500 800 1900 B 500 900 400 1800 C 900 700 500 2100 warehouse capacity 2000 2100 1700 5800 Table 2 The paths to be taken for the transportation of the goods from the production plants to the destined warehouses are as follows: plant A Warehouse 1 plant B Warehouse 2 plant C Warehouse 3 Table 3 The diagram above shows all the possible routes that can be used to transport goods from the three production plants to the warehouses. Each route has its own specific cost per unit of goods transported. Various combinations of these routes to supply goods to the warehouses have different total costs. The objective of these models is thus to minimize such costs using the optimum combination of routes. Using the above assumptions, we are going to analyze how we can achieve optimum costs using the following methods: METHOD 1: North-West Corner Method versus Stepping-Stone Method Both of these methods are used together to achieve a common purpose. The objective function of the problems is usually to minimize transport costs. It is a step-by-step analysis that sets up a viable solution and then works on improving the results to an optimum level. It might be complex when done manually but very simple when the algorithm is computerized. The method is good since you can use any number of variables i.e. n production plants and n warehouses (where n is an integer from 1 to 100+). The steps involved are as follows: Step 1: form a matrix with rows representing the production plants available and columns representing the warehouses, add a row and a column each end to represent the totals i.e. production capacity of each plant and demand capacity of each warehouse. Step 2: for the first plant and the first warehouse, allocate the total production until the warehouse capacity is depleted or the plant capacity is depleted whichever comes first. If there is a remainder of goods, move to the second warehouse and allocate the goods until the warehouse is depleted and so on. Step3: repeat step two for all the plants until all the warehouses are allocated the maximum available goods. Step 4: multiply each amount in each tablet with its transport cost and sum to get the initial feasible solution. This solution could be the optimal solution or not. The second method is applied to improve this result until an optimum solution is achieved i.e. stepping-stone method. The above steps help you to initialize the problem to a more simpler task of improving the results. All goods are allocated to a specific path to fulfill all the warehouses. However, optimization remains the main problem at this stage. The method analyses the fitness of each tablet and the effect of altering its contents. A negative effect on cost remains our main target (Charnes, October 1954). Let us now analyze the Stepping Stone Method. The main steps are: Select an empty cell in the matrix to test Starting with this cell, trace a loop with straight lines making corners only at filled cells back to the original cell (movements must be vertical or horizontal but one can step over a cell). Allocate alternating positive and negative signs on this path starting with a positive on the empty cell Use the signs together with the unit costs all around the loop to calculate the positive and negative signs (summing the values). Repeat the above steps for each empty cell that you want to analyze in the table If all the change values are positive, the problem is at its optimum solution, if there are negative changes, select the minimum Add up all the values on the loop/path of that square to make it a used square. This improves the solution to a lower cost. Repeating the steps above helps investigate if there is still more improvements. In case of more negative indices (improvements), make the squares filled until all the unfilled squares give a positive index. The main concept of the Stepping-Stone method is taking a quantity from a used square and placing it in an unused square, then analyzing the effect to the total cost, if good, you proceed and change. The costs incurred in the additional unit are added to the total cost, the costs incurred in the previous location of the unit subtracted, and the change observed. However, an empty cell could have the same cost as an existing allocation. This is termed as alternate optimal solution. The management gains flexibility in such a case since it can make choices within an optimal solution (Martin, 2000). There are alterations that appear in these methods, for example; if the demand is not equal to the supply (which is normally the case). We consider two treatments. One of them is adding a dummy production unit to represent the supply constraint i.e. slack variable for it to match with the warehouse demand while the other treatment is to add a dummy warehouse to fill as a slack variable for the excess production capacity. Once the production units match with the warehouse units, the models can be successfully applied. The transportation costs to and from the dummies are assumed to be zero since the dummies do not exist in reality. They are only used to map sources and destinations. Another problem often encountered in solving these problems is the degeneracy problem this occurs when the algorithm cannot solve for an optimum solution of the transport problem. The technical case is when the number of occupied cells in less than the sum of the number of rows plus the number of columns minus one. It means that there are no enough occupied squares to trace a path/loop for each unused cell. However, if such a case occurs, we insert a zero in an unoccupied space so that we can achieve a closed loop/path for the stepping-stone. Furthermore, if one is not careful, one can form the degenerate problem himself when trying to improve on a solution. This occurs when addition/subtraction results in nullification of two or more values in the filled cells. One should proceed with improvement through placing a zero in an unfilled cell to assume a stepping stone for path completion. Method 2: North-West Corner Method versus Modified Distribution Method (MODI) This method is similar to the stepping stone method except that it is easier for manual calculation. One does not have to go improving the solution step by step until the final solution. The steps are easier. In fact, the first possible solution is usually the optimal solution. This method saves time since it does not require the calculation of indices in all the unused cells. However, the concept is the same as that of the stepping stone method. The mathematical equations represent the squares/paths in the stepping stone method. The steps involved in this method are as follows (Bassin, 1981): For each and every filled cell, compute the values for each row R, and column K, and then set the Cij. After you write all the equations for each filled cell, set R1 =0. Solve the consecutive equations for all R and K values. Calculate the improvement values for each unused square using the following formula: Improvement index I =C - R – K For each i and j value. Allocate all the available amount of goods to the cell with the highest improvement value (least index). Repeat step (II to V) and allocate all possible amounts to all positive improvements. For example, all negative indices. The best improvement value is directly taken and implemented in the table. This method is highly recommended for manual analysis while the stepping-stone is recommended for algorithmic calculation i.e. computerized solutions (Dantzig, 1998). Method 3: Vogel’s Approximation Method This method is very easy to use. The first approximation is usually the optimal solution or the closest estimate. The approach used is the regret criterion. You first calculate the possible regrets and then allocate the goods to avoid the high regrets. The main points of this method are as follows: Determine the regret for each row and column. Select the row/column with the highest regret. Allocate all the possible amount of goods to the column/row with the highest regret. Repeat the above steps until all the goods are depleted and the warehouses are full. Method 4: The Assignment Model This is another linear programming model that is used to solve transportation problems. The supply and demand at each source and destination is limited to one unit. The models solves problems in two approaches: one of them is the balanced model where supply equals demand while the other is the unbalanced model where supply does not equal demand. This problem usually adopts a technique that utilizes the concept of regrets. There is only one variable which is usually the distance travelled associated with the travelling costs. The difference is that the assignment model does not display the demand and supply quantities since they are all equal to one. In case of a situation of more tasks that agents, we assign a dummy agent with the ability to carry out multiple tasks at a time. The dummy agent can handle all the excess of tasks to the agents i.e. there will be only one dummy agent. All others are rationed into 1:1 i.e. in a construction problem; each project should have one and only one manager (Budnick 25 May 2011). References Bassin, W., M., (1981). Quantitative business Analysis: linear programming: transportation and assignment models. Budnick, F., S., (25 May 2011). Finite Mathematics with Applications, digital edition pp. 243: Extensions of linear programming. Charnes, A., & Cooper, W., W., (October, 1954). The stepping stone method of explaining linear programming calculations in transport problems: management science: Carnegie Institute of technology. Dantzig, G., B., (1998). Linear Programming and extensions, eleventh edition: A transportation problem. Havlisek, J., (1 January 2007). Linear programming: transport and assignment models: transportation problem. Accessed on 9 December 2011 at http://orms.pef.czu.cz/text/transProblem.html Martin, R., K., (2000). Quantitative methods for businesss, eleventh edition: linear programming Read More