Operations Research 06C: Transportation Minimum Cost Method


In this video, we’ll talk about how to find
a basic feasible solution or BFS to the balanced transportation problem using the minimum cost
method. There are three steps. In Step 1, we need to find the cell with the
smallest unit cost in the transportation tableau. Ties are broken arbitrarily, which means,
if there are two or more cells with the same smallest unit cost, randomly select one of
them. Then, allocate as much as possible to the
selected cell, and adjust the associated amounts of supply and demand by subtracting the allocated
amount. In Step 2, we cross out the row or column
with 0 supply or demand. If both a row and a column have a 0, arbitrarily
cross out one only. In Step 3, if exactly one cell is left uncrossed,
cross out the cell and stop. Otherwise, we need to go back to step 1 and
repeat the process. For example, this is a transportation tableau. The unit transportation cost is shown in the
top right corner of each cell, like 2, 3, 5, 6, and so on. The total supply for the first row is 5, for
the second row is 10, and so on. The total demand for the first column is 12,
for the second column is 8, and so on. Now, in the first step, we need to find the
cell with the minimum unit cost, which is this cell with a unit cost of 1. We need to allocate as much as possible to
this cell, and subtract the allocated amount from supply s2 and demand d2. The largest amount we can allocate is 8, because
if we allocate more than 8, d2 will be changed to a negative number. We put a number 8 here, and subtract it from
d2 and s2. d2 will be 0, and s2 will be 2. This is the new tableau. In Step 2, we cross out the row or column
with 0 supply or demand. In this case, only d2 is 0. We’ll cross out the second column and remove
d2. Now we need to check Step 3. Do we have only one cell left? No, we have many cells left. We need to go to Step 1 and repeat the process. Now, we need to find the cell with the minimum
cost in the remaining tableau. We have a tie, 2 and 2. I randomly select this cell. The largest amount we can allocate to this
cell is 2, because if we allocate more than 2, s2 will be negative. We put 2 here, and subtract it from s2 and
d1. s2 will be 0, and d1 will be 10. This is the new tableau. We need to cross out the second row and remove
s2 because s2 is 0. Let’s continue with this process. Find the cell with the minimum cost in the
remaining tableau, which is this cell. The largest amount we can allocate is 5. We put 5 here, and subtract it from s1 and
d1. s1 will be 0, and d1 will be 5. This is the new tableau. We need to cross out the first row and remove
s1 because s1=0. Continue with this process. Find the cell with the minimum cost in the
remaining tableau, which is this cell. The largest amount we can allocate is 5. We put 5 here, and subtract it from s3 and
d1. s3 will be 10, and d1 will be 0. This is the new tableau. d1=0, we will cross out the first column and
remove d1. Repeat the process. Find the cell with the minimum cost in the
remaining tableau, which is this cell. The largest amount we can allocate is 4. We put 4 here, and subtract it from s3 and
d3. s3 will be 6, and d3 will be 0. This is the new tableau. d3=0, we will cross out this column and remove
d3. We have only one cell left. We will just allocate the remaining amount,
which is 6, to this cell, and cross out this row and this column, and remove s3 and d4. This is the final tableau. Remember, this is just a basic feasible solution. It is not the final optimal solution to the
balanced transportation problem yet. How do we interpret this basic feasible solution? It means x11=5, x21=2, and so on. All other xij in the blank cells are equal
to 0. If you wonder if this really is a bfs, you
can check whether it satisfies all the equality constraints. Let’s bring back the original supply and demand. The sum of the first row, 5=5. The sum of the second row, 2+8=10. The sum of the third row, 5+4+6=15. The sum of the first column, 5+2+5=12. The sum of the second column, 8=8. The sum of the third column, 4=4. The sum of the last column, 6=6. So, all the constraints are satisfied. This is indeed a bfs. The advantage of using the minimum cost method
is that it utilizes the cost information and the generated bfs may be closer to the optimal
solution. But this method requires a little bit more
computational effort than the northwest corner method. Sometimes it may still generate a bfs with
extremely high cost, which is far away from the optimal solution. Okay. That’s how we find a bfs to the balanced transportation
problem using the minimum cost method. Thanks for watching.