Tag Archives: Minimum Cell Cost Method

example vogel method

Vogel Approximation Method (Transportation Algorithm in Linear Programming)

The Vogel Approximation Method is an improved version of the Minimum Cell Cost Method and the Northwest Corner Method that in general produces better initial basic feasible solution, which are understood as basic feasible solutions that report a smaller value in the objective (minimization) function of a balanced Transportation Problem (sum of the supply = sum of the demand).

Applying the Vogel Approximation Method requires the following steps:

Step 1: Determine a penalty cost for each row (column) by subtracting the lowest unit cell cost in the row (column) from the next lowest unit cell cost in the same row (column).

Step 2: Identify the row or column with the greatest penalty cost. Break the ties arbitrarily (if there are any). Allocate as much as possible to the variable with the lowest unit cost in the selected row or column. Adjust the supply and demand and cross out the row or column that is already satisfied. If a row and column are satisfied simultaneously, only cross out one of the two and allocate a supply or demand of zero to the one that remains.

Step 3:

  • If there is exactly one row or column left with a supply or demand of zero, stop.

  • If there is one row (column) left with a positive supply (demand), determine the basic variables in the row (column) using the Minimum Cell Cost Method. Stop.

  • If all of the rows and columns that were not crossed out have zero supply and demand (remaining), determine the basic zero variables using the Minimum Cell Cost Method. Stop.

In any other case, continue with Step 1.

Vogel Approximation Method Example

Let’s reconsider a balanced transportation problem that has 3 supply sources (silos) and 4 demand sources (mills). The numerical values in the upper right-hand corner of each box, from now on , represent the per unit transportation cost from silo i to mill j. For example, c_{ij} is the per unit transportation cost from silo 1 to mill 1.

Vogel Approximation Method

Based on what we previously described, the first step consists of calculating the penalty cost for each row and column of the tableau that represents the previous transportation problem. For example, in row 1 the lowest cost is $2 and the next lowest unit cost is $10. Thus the penalty cost for that row is $8 ($10-$2). The same calculation is replicated for each row and column of the tableau, which is trivial, and gets the following results (the penalty costs of the respective rows and columns have been marked in orange for clarity):

example vogel method

Since row 3 has the highest penalty cost ($10) and the cell corresponding to x_{31} has the lowest unit cost of that row, 5 units are allocated to x_{31} (it is unnecessary to do more even when the capacity of silo 3 would allow it given that the demand for mill 1 is only 5 units). In doing so column 1 should be crossed out (we have marked it in yellow) and next comes the calculation of the new penalty costs as shown below:

Now the highest penalty cost is $9 ($11-$2), which is found in row 1. As a result the highest quantity possible is allocated to the variable x_{12}, thus obtaining x_{12}=15, at the same time row 1 and row 2 are satisfied. Column 2 is arbitrarily crossed out and the supply of row 1 is adjusted to zero.

Continuing on in the same manner, row 2 now has the highest penalty cost that corresponds to $11 ($20-$9), therefore x_{23}=15 is allocated, so that column 3 is crossed out and there are 10 units left in row 2. Only column 4 is left and it has 15 positive supply units. By applying the Minimum Cell Cost Method to this column, we successively allocate x_{14}=0, x_{34}=5, x_{24}=10 (it is recommended to confirm these results). Also note that there are other possible solutions that depend on how the ties are broken.

The value of the objective function associated with this initial feasible solution is Z=15(2)+0(11)+15(9)+10(20)+5(4)+5(18)=$475 which is similar to what was reached using the Minimum Cell Cost Method, nevertheless, the Vogel Approximation Method generally gives a better initial solution.