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.