Vogel’s Approximation Method (VAM) is one of the methods used to calculate the initial basic feasible solution to a transportation problem. However, VAM is an iterative procedure such that in each step, we should find the penalties for each available row and column by taking the least cost and second least cost. In this article, you will learn how to find the initial basic feasible solution to a transportation problem such that the total cost is minimized. Show Vogel’s Approximation Method StepsBelow are the steps involved in Voge’s approximation method of finding the feasible solution to a transportation problem. Step 1: Identify the two lowest costs in each row and column of the given cost matrix and then write the absolute row and column difference. These differences are called penalties. Step 2: Identify the row or column with the maximum penalty and assign the corresponding cell’s min(supply, demand). If two or more columns or rows have the same maximum penalty, then we can choose one among them as per our convenience. Step 3: If the assignment in the previous satisfies the supply at the origin, delete the corresponding row. If it satisfies the demand at that destination, delete the corresponding column. Step 4: Stop the procedure if supply at each origin is 0, i.e., every supply is exhausted, and demand at each destination is 0, i.e., every demand is satisfying. If not, repeat the above steps, i.e., from step 1. The above procedure can be understood in a better way with the help of a solved example given below. Vogel’s Approximation Method Solved ExampleQuestion: Solve the given transportation problem using Vogel’s approximation method. Solution: For the given cost matrix, Total supply = 50 + 60 + 25 = 135 Total demand = 60 + 40 + 20 + 25 = 135 Thus, the given problem is balanced transportation problem. Now, we can apply the Vogel’s approximation method to minimize the total cost of transportation. Step 1: Identify the least and second least cost in each row and column and then write the corresponding absolute differences of these values. For example, in the first row, 2 and 3 are the least and second least values, their absolute difference is 1. These row and column differences are called penalties. Step 2: Now, identify the maximum penalty and choose the least value in that corresponding row or column. Then, assign the min(supply, demand). Here, the maximum penalty is 3 and the least value in the corresponding column is 2. For this cell, min(supply, demand) = min(50, 40) = 40 Allocate 40 in that cell and strike the corresponding column since in this case demand will be satisfied, i.e., 40 – 40 = 0. Step 3: Now, find the absolute row and column differences for the remaining rows and columns. Then repeat step 2. Here, the maximum penalty is 3 and the least cost in that corresponding row is 3. Also, the min(supply, demand) = min(10, 60) = 10 Thus, allocate 10 for that cell and write down the new supply and demand for the corresponding row and column. Supply = 10 – 10 = 0 Demand = 60 – 10 = 50 As supply is 0, strike the corresponding row. Step 4: Repeat the above step, i.e., step 3. This will give the below result. In this step, the second column vanishes and the min(supply, demand) = min(25, 50) = 25 is assigned for the cell with value 2. Step 5: Again repeat step 3, as we did for the previous step. In this case, we got 7 as the maximum penalty and 7 as the least cost of the corresponding column. Step 6: Now, again repeat step 3 by calculating the absolute differences for the remaining rows and columns. Step 7: In the previous step, except for one cell, every row and column vanishes. Now, allocate the remaining supply or demand value for that corresponding cell. Total cost = (10 × 3) + (25 × 7) + (25 × 2) + (40 × 2) + (20 × 2) + (15 × 3) = 30 + 175 + 50 + 80 + 40 + 45 = 420 Vogel’s Approximation Method Problems1. Consider the transportation problem given below. Solve this problem by Vogel’s approximation method.
2. Find the solution for the following transportation problem using VAM.
3. Use Vogel’s Approximation Method to find a basic feasible solution for the following.
To learn various methods of solving transportation problems using the stepwise procedure, visit www.byjus.com today!
Vogel’s approximation method, i.e., VAM, is one of the methods to find the initial feasible solution to a transportation problem.
VAM (Vogel’s Approximation Method) is the best method of computing the initial basic feasible solution to a transportation problem. As it provided better results when compared with other methods.
In Vogel’s approximation method, a penalty is an absolute difference between the least and second least values in a row or column.
There are two phases to solve the transportation problem. In the first phase, the initial basic feasible solution has to be found and the second phase involves optimization of the initial basic feasible solution that was obtained in the first phase. There are three methods for finding an initial basic feasible solution,
This article will discuss how to optimize the initial basic feasible solution through an explained example. Consider the below transportation problem. ong>Solution: Step 1: Check whether the problem is balanced or not. Note: If the problem is not unbalanced then the concept of a dummy row or a dummy column to transform the unbalanced problem to balanced can be followed as discussed in this article. Step 2: Finding the initial basic feasible solution. Now, the total cost of transportation will be (200 * 3) + (50 * 1) + (250 * 6) + (100 * 5) + (250 * 3) + (150 * 2) = 3700. Step 3: U-V method to optimize the initial basic feasible solution. – For U-V method the values ui and vj have to be found for the rows and the columns respectively. As there are three rows so three ui values have to be found i.e. u1 for the first row, u2 for the second row and u3 for the third row. There is a separate formula to find ui and vj, Before applying the above formula we need to check whether m + n – 1 is equal to the total number of allocated cells or not where m is the total number of rows and n is the total number of columns. Now to find the value for u and v we assign any of the three u or any of the four v as 0. Let we assign u1 = 0 in this case. Then using the above formula we will get v1 = 3 as u1 + v1 = 3 (i.e. C11) and v2 = 1 as u1 + v2 = 1 (i.e. C12). Similarly, we have got the value for v2 = 1 so we get the value for u2 = 5 which implies v3 = 0. From the value of v3 = 0 we get u3 = 3 which implies v4 = -1. See the image below: Now, compute penalties using the formula Pij = ui + vj – Cij only for unallocated cells. We have two unallocated cells in the first row, two in the second row and two in the third row. Lets compute this one by one.
The Rule: If we get all the penalties value as zero or negative values that mean the optimality is reached and this answer is the final answer. But if we get any positive value means we need to proceed with the sum in the next step. Now find the maximum positive penalty. Here the maximum value is 6 which corresponds to C21 cell. Now this cell is new basic cell. This cell will also be included in the solution. The rule for drawing closed-path or loop. Starting from the new basic cell draw a closed-path in such a way that the right angle turn is done only at the allocated cell or at the new basic cell. See the below images: Assign alternate plus-minus sign to all the cells with right angle turn (or the corner) in the loop with plus sign assigned at the new basic cell. Consider the cells with a negative sign. Compare the allocated value (i.e. 200 and 250 in this case) and select the minimum (i.e. select 200 in this case). Now subtract 200 from the cells with a minus sign and add 200 to the cells with a plus sign. And draw a new iteration. The work of the loop is over and the new solution looks as shown below. Check the total number of allocated cells is equal to (m + n – 1). Again find u values and v values using the formula ui + vj = Cij where Cij is the cost value only for allocated cell. Assign u1 = 0 then we get v2 = 1. Similarly, we will get following values for ui and vj. Find the penalties for all the unallocated cells using the formula Pij = ui + vj – Cij.
There is one positive value i.e. 1 for C32. Now this cell becomes new basic cell. Now draw a loop starting from the new basic cell. Assign alternate plus and minus sign with new basic cell assigned as a plus sign. Select the minimum value from allocated values to the cell with a minus sign. Subtract this value from the cell with a minus sign and add to the cell with a plus sign. Now the solution looks as shown in the image below: Check if the total number of allocated cells is equal to (m + n – 1). Find u and v values as above. Now again find the penalties for the unallocated cells as above.
All the penalty values are negative values. So the optimality is reached. Now, find the total cost i.e. (250 * 1) + (200 * 2) + (150 * 5) + (50 * 3) + (200 * 3) + (150 * 2) = 2450 Article Tags : Practice Tags : |