In this video, I am going to explain transportation problem. See, what is the basic concept of transportation problem? See, transportation problem is a special kind of linear programming problem in which goods are transported from one set of sources to one set of destination, subject to the supply and demand of the sources and destination, such that the total cost of transportation is minimized.
So that is the basic concept of transportation model or transportation problem. It has two phases. The first one is finding the initial basic feasible solution is the first phase.
In order to find the initial basic solution there are three methods are available. First one is northwest corner cell method, second one least cost method and third one is Ogles approximation method that is WAM method. So these are the three methods available to find the initial basic feasible solution that is the first phase and after finding the solution that is basic solution the second phase involves optimization of the initial basic feasible solution which is obtained in phase one okay after obtaining the basic feasible solution the second phase involves optimization okay so optimality can be obtained the by using uv method so in this video i am going to focus more on this that is optimizing the basic feasible solution applying uv method okay i have already uploaded a separate video for the first phase that is finding the initial basic feasible solution by applying three different methods so here i am going to solve one problem in that i am going to use the first method that is northwest corner cell method By using this method, I am going to find the initial basic feasible solution. And after finding the solution, the second step is optimizing the basic feasible solution applying UV method.
Let us see this with the help of one problem. Find the initial basic feasible solution of the following transportation problem by northwest corner cell method. And then optimize the solution using UV method.
okay this is the problem see this transportation model here three rows are there and four columns are there okay supply value is given demand value also given okay so these are the four destination and these are the three sources so with this problem they ask you to find the basic feasible solution and after finding the initial basic feasible solution by using northwest corner rule you need to find the optimality that is then optimize the solution using uv method so here i'm going to use the two phases first phase finding the feasible solution and second one is using uv method to optimize the solution so first step is finding initial basic feasible solution using northwest corner cell method see before you solve the problem first you need to check whether the problem is balanced transportation problem or unbalanced transportation problem for that you need to check the total demand and total supply if it is balanced means then you can proceed so balance mean both the supply and demand will be equal that is this total and this total will be equal if it is not so means you need to add dummy row or dummy column according to the balance then the unbalanced problem will be converted into balanced transportation problem then you can proceed with the procedure so first you need to check the total demand and total supply just check this value 250 plus 350 plus 400 000 here also find the total 200 plus 300 plus 350 plus 150 000 so it is a balanced transportation problem so here you need not add any dummy row or dummy column you can proceed with this so now i am going to use northwest corner cell method to find the initial basic feasible solution so for that you need to start from the northwest corner this is a northwest corner okay you have to start from here so in order to allocate the cell you need to find the row value and column value row value is 250 column value is 200 which one is least value 250 or 200 200 is lesser than the 250 now you have to allocate this value for this sin 200 okay the entire thing is allocated here now it will become 0 here we are having 50 so this column value is 0 no now cancel the first column because the column value is nil so now we have to cancel the first column so the first column get cancelled okay so just leave the first one now we have only three rows and three columns so in this box which one is northwest corner This is North West corner so again you have to start from here. Now find the row value and column value. So second column value is 300 and first row value is 50. So which one is least? 50 is least.
No. So allocate 50 here. Now this will be 0. Second column balance amount 250. So out of 300 we have given 50. No.
So remaining 250 is there. This row value is 0. No. Now the first row will get cancelled. Now first column.
And first row is over. Now we have only 2 rows and 3 columns. So in this box which one is north west corner? This is the north west corner no?
Again you have to start from here. Now find the value for this column and this row. So row value is 350. Column value 250. Which one is least? 250 is least no. So allocate 250. Then it will become 0. cancel this row okay so after allocating 250 balance how much 100 now we have only two rows and two columns so in this box which one is northwest this is a northwest no so select this cell and put the value allocate the value so find the row value row value is 100 column value 350 so which one is least 100 is least no so enter 100 it will become zero here we will be having 250 balance this row also get cancelled now we have only two values in this which one is northwest this is the northwest no here we have 250 and 400 which one is least 250 is least so put 250 here it will become zero here we will be having 150 so this is also cancelled so finally we have only one cell Find the row and column value.
Row value 150, column value also 150. So entire demand and supply is met. Okay. So now we need to find the answer. So according to northwest corner rule, this is the final initial basic feasible solution. Now we have to find the total cost of transportation.
Here 200, now 200 into 3. Plus. 50 x 1 plus 250 x 6 plus 100 x 5 plus 250 x 3 plus 150 x 2 plus 150 x 3 plus 150 x 2 plus 150 x 2 What is the total cost of transportation? Rupees 3700. So first phase is over. We have got the solution.
That is initial basic feasible solution using northwest corner cell. So this is the total cost of transportation according to northwest corner cell. Now we need to find the optimality. We have to check the optimality after finding this solution.
Now let us see the. second phase that is a application of uv method to optimize the solution so this is the solution we have obtained by using northwest corner rule okay so after finding the solution initial basic feasible solution now we need to apply uv method to optimize the solution to check or to find the optimization for the same solution so for that first you need to find the u value and v value here three rows are there now So this one is U1. For second row you need to find U2. For third row you need to find U3.
So U1, U2, U3 for three rows. In the same way we need to find value for four different columns. For that we need to find V1 for first column, V2 for second column, V3 for third column, V4 for fourth column. So we need to find the value for U and V3. v. There is a separate formula to find the u and v. The formula is so this is the formula to find the u and v that is u i plus v j is equal to c i j so u i means for three rows we have u i u 1 u 2 u 3 v j means column value so first column second column third column fourth column v 1 v 2 v 3 and v 4 c i j means allocated cell So here we have 6 allocated cells are there.
Okay so before you start this you need to check the m plus n minus 1 is equal to number of allocated cell. So how many cells are allocated so far? In the first row 2 cells are allocated. In the second row again 2 cells are allocated. In the third row also 2 cells are allocated.
So altogether how many cells are allocated? 6 cells are allocated. m means number of row. How many rows are there? 3 rows are there.
n denotes number of columns. How many columns are there? 4 columns are there.
Minus 1. This is the formula. Okay. So 3 plus 4, 7. 7 minus 1, 6. So this is proved. So now you can proceed.
Now you need to apply this formula to find the Cij. For the allocated cells only, you need to find the u and v j okay so this is the formula to find the c i j let us see how i am going to apply this to find the u and v value and so always you can take u 1 as 0 so u 1 can be considered as 0 okay now we have to find the value for v with the help of this formula okay so u plus v is equal to c c i j means the value the element of the allocated cell okay the first row first column is 3. The Cij value is 3. Okay. So, in order to get 3, what is the formula?
u plus v. That is the u plus v is equal to 3. Okay. So, already we have taken, we have considered u1 as 0. Then how you will get 3? 0 plus 3 is equal to 3. So, v1 will be 3. 0 plus 3 is equal to 3. Okay. With the help of this formula, we have got the value for u and v. Now with this you can find the value for all other u and v values.
Okay now u1 is 0. No. So now we have got the value for v1. Now go to the next one. So u1 is again 0. Okay then what about v2? 0 plus 1 is equal to 1. Here cij is 1. No.
Okay we have taken u1 as 0. So 0 plus 1 is equal to 1. So according to this formula so now we have got the value for v1 v2 and u1 with this you can find the value for other cells also now go to u2 so here u2 for u2 here we have two allocated cells no so look at the first again v2 is 1 then how will get 6 1 plus u2 is equal to 6 then it will be 5 so now check the value 5 plus 1 is equal to 6 Now we got the value for V2. With this you can find the value for this also. So here we have 5. Okay so U plus V is equal to 5. So already U2 is 5. Then what about V3?
V3 will be 0. So 5 plus 0 is equal to 5. We have got the value for V1, V2, V3, U1 and U2. Okay with this you can find the value for the remaining things. Now come to the third row.
Cij is 3 no. So what is the formula? U. plus v so v is already we have got the value 0 so 0 plus what will be answer 3 0 plus 3 is equal to 3 0 plus 3 is equal to 3 we have got the value for u3 also now we have to find the value for v4 with this value you can find the value for v4 cij value is 2 no so how will you get the value for this ui plus vj is equal to 2 here u3 is 3 Then what about V4? Minus 1. That is 3 minus 1 is equal to 2. We have started with U1.
We have assumed U1 is equal to 0. No. For each allocated cell, we have got the value for U1, U2, U3 and V1, V2, V3 and V4. Okay.
This is the first step. By using this formula, we have got the value for all allocated cells. That is Ui plus Vj is equal to Cij. With this you need to proceed the next step. Okay, the second step is you need to find the penalties by using this formula.
Computer That is penalties means Pij. Penalties for non-basic cells by using this formula. The formula is Ui plus Vj minus Cij. Cij means the cost, the element of unallocated cell. Ui, Vj we know very well.
U means row value, V means column value. In the first row, these are the two values. These are the two cells or unallocated cell.
Okay. You need to write in this form that is C13. Okay, C13 means first row, third column.
So, this element is called first row and third column. So, you have to write like this. Then look at the next non-allocated cell is 4. Okay, for 4 you need to write like this C14.
First row, fourth column cell also non-allocated cell. So first row is over. Look at the second one. In the second row, this cell is non-allocated. That is second row, first column.
C, second row, first column. Okay. The next unallocated cell is 9. This cell you can write like this.
C, 2, 4. That is second row, fourth column. Second row, fourth column. Okay. In the same way, you need to find the value for other. Non-allocated cells also.
So look at the third row. This one is non-allocated. You have to write like this.
That is third row, first column. Third row, first column. Next one is this value.
That is third row, second column. Third row, second column. So these are all non-allocated cell.
Ui plus Vj minus cost. Cij. Cost of.
non-allocated cell. Okay, now let us see how I am going to apply this formula. So, look at the first one, 1, 3. So, 1, 3 represent first row, first row, third column. Okay, for this cell, what is u and what is v value?
u value is, u1 is 0, v value also 0. So, what is the formula? u plus v, that is 0 plus 0 minus Cij. Cij means Cost of that particular element, that particular cell. The cell value, cost is 7. So, minus 7. Okay, what is the value?
0 plus 0, 0. 0 minus 7, minus 7. Now, go for the second one. That is 1, 4. First row, fourth column value is 4. No. So, for this, this is the Cij. Cost is 4. So, what is u and v value? u value is 0, v value minus 1. u value 0, v value minus 1 according to formula minus cost.
So, what is the answer? 0 minus 1 minus 1, minus 1 minus 4, minus 5. Go for the next one that is c21, second row, first column, non-allocated cell. So, u value v value, u value 5, v value 3. So, according to formula 5, Plus 3 minus cost of that cell 2. Cost of the cell 2. No. Write 2. 5 plus 3. 8. 8 minus 2. 6. In the same way for all other things also you need to find the penalty.
Now we have got the. is for non-allocated cells okay so the first one minus 7 minus 5 6 minus 5 minus 2 and 1 so the rule is if we get 0 or less than 0 means optimality is reached okay you can stop with this and this answer will be the final answer that is optimum solution is reached optimality is reached if you get any positive value means You need to proceed the sum in the next step. That is you have to find the maximum positive value. In this problem we have got two positive values. That is 1 and 6. So among the two values which one is the maximum value?
6 is the maximum value. No. That is C21.
C21 is it represents second row first column. So second row first column. So this cell is called new basic cell.
After finding the new cell. Starting from the new cell draw a closed loop consisting of only horizontal and vertical lines. Okay passing through some basic cells only.
So look at the loop. I am starting from here now. So now I need to move like this.
Here I can take a turn because it's an allocated cell. So from here I need to turn like this. Here I am going to take turn because this is also allocated cell. From here I can turn like this because this is also allocated cell.
Okay now I can join. So this is a closed loop I have drawn. I started from here. So all the turning point should be allocated cell only.
You cannot move like this. If you turn here means then again you cannot take any left or right. Because here we didn't have any allocated cell.
So if you turn like this means again there is no allocated cell here. So. this is a possible closed loop okay i have drawn a closed loop by using that format by using the rule where you have started from here now so this cell will be positive okay next one here now this is negative here positive here negative we have four corners okay we have started from here for first one you have to allocate positive sign alternatively you have to give positive negative positive and negative okay now we have got Four corners. No. So now from this loop just see the negative value.
So negative value allocated value is 200 and 250. So which one is least? 200 is least when compared to 250. Now we have to take 200 and add with the plus value and subtract in the negative value. Okay. Now we have to draw a new iteration. In the new iteration just write the allocated value.
for all other cells so except the loop cell the other cells are there no so just write the allocated value as it is here 100 here 250 here 150 so there will be no changes in this 100 250 150 now look at the loop cells so here we have two negative values no 200 250 which one is least 200 is least so you need to subtract 200 from here and from here And you need to add 200 with this value and with this value where we have positive values. So 200 minus 200, 250 minus 200. Here you need to add 200. Here also you need to add 200. So 200 minus 200, no value. Here 50 is there, no 50 plus 200. 250. Here we have 250 you need to subtract 200 then the value will be 50. This is unallocated cell you need to add 200 then it will become is a new iteration okay so now you have to find the u and v value with the help of this formula ui plus vj is equal to cij. So okay now we have to find u1, u2, u3, v1, v2, v3 and v4 with this formula. u1 is always 0. Assume u1 is 0. For allocated cell you need to find 1. So u plus v is equal to 1. So v2 is equal to 1. 0 plus 1 is equal to 1. Look at the next one.
So now we have got the value for v2. With this you can find the value for u2. v2 is 1. What about u2?
So 1 plus 5 is equal to 6. So now we have got the value for u2. So u2 value is 5 now. So 5. Now we can get the value for v3.
So u2 is 5. Then what about v3? Here we have 5. Cij is 5, so u3 also 0. 5 plus 0 is equal to 5. Okay, now we have got the value for v3. Now, then you can find the value for u3 also. So, v3 value is 0. How will you get 3?
So, this will be 3. We have got the value for u3. With this, you can find the value for v4. So, here u3 is 3. We need to find the value of 2. So, then v4 will be minus 1. 3 minus 1 is equal to 2. Okay, now we have got the value for u1, u2, u3.
v2 v3 and v4 now we have to find the value for v1 so look at here so v1 is 2 so we need to get 2 what about u2 u2 is 5 then what about v1 v1 will be minus 3 so 5 minus 3 is equal to 2 so with the help of this formula we have got the value for u1 u2 u3 and v1 v2 v3 and v4 now we need to find the penalties for non-allocated cell. Vij is equal to Ui plus Vij minus Cij. So we need to find penalties for all non-allocated cells by using this formula.
In the first row this non-allocated cell now this represents C11. This cell represents C13. This cell represents C14.
In the second row, this cell is a non-allocated cell. For this, you need to write C24. Then third row, this one is C31. Then last one, C32.
Now, we have to apply this formula to find the penalty for all non-allocated cells. For C11, that is 3, this cell. What is u and v value? u value is 0. Okay, v value minus 3 minus 3 minus cij cost of that element minus 3. For the first non-allocated cell ui vj minus cij that is ui is 0 vi minus 3. So, minus 3 minus cost. Cost of that non-allocated cell is 3. So, minus 3. So, what is the value?
0 minus 3 minus 3 minus 6. In the same way, you need to find the value for all non-allocated cells. For C13, UI is 0, VJ is 0, CIG minus 7. Answer is minus 7. For C14, 0 minus 1 minus 4 is equal to minus 5. For C32, 3 plus 1 is equal to 4. 4 minus 3 is equal to minus 5. plus one so if we get zero or less than zero means you can stop with this if we get any positive value here we have got one positive value no so this is a new cell this one is new cell so we have to start from here and you have to draw a closed loop c32 is this is a new cell from here you need to draw a closed loop okay i already told you know for every turning point The turning cell should be allocated cell and you have to draw only horizontal and vertical line. From here you can move here.
Here you can take a turn. From here you can move like this. This is also allocated cell.
No, from here you have to move like this. This is also allocated cell. Now you can join.
So this is a closed possible loop. You have started from here. Be positive then this will be negative. This will be positive. This will be negative.
For every turning point, you have to give sign plus and minus alternatively. Now, look at the negative values. This one is negative.
This one also negative. Now, just compare the allocated value. Which one is least?
50 or 250? 50 is least. Now, we have to subtract 50 from this cell and from this cell. Okay.
And you need to add 50 with this cell and with this cell. So, then this cell will be called as. allocated cell after adding 50 okay so except the loop cell all other allocated cell value is there now that is 200 250 150 just write these value as it is now you have to find the new value for these four cells so here you have to subtract 50 no so least value is 50 no 50 minus 50 zero so there is no allocation for this cell here already 100 is there now you need to add 50 then it will become 150. Here you need to subtract 50. 250 minus 50 then it will become 200. Here nothing is there now you need to add 50 then this cell will be allocated cell.
here 50 is there now 50 minus 50 nil okay now check whether six allocated cells are there or not 1 2 3 4 5 6 so m plus n minus 1 is equal to 6 now you can proceed now you need to find the u and v value with the help of this formula ui plus vj is equal to cij now you u1 is always 0. Assume u1 is 0. Now we need to find penalties for non-allocated cell. What is the formula? Ui plus Vj minus Cij.
Cij represent cost of unallocated cell. So Uv we have got the value for U and V. So now we have to write the unallocated cell code. That is the first unallocated cell is 3. So it represent C11, C11, C13.
C14. Then C22, C24, C31. So these are all unallocated cells.
So now just apply the formula penalties. So C11 is 3. What is U and V value? U value is 0, V value minus 2. So 0 minus 2, Cij 3, minus 3. In the same way find the value for all other unallocated cells. Now find the penalties for all unallocated cells. So first one is 0, minus 2, minus 3, minus 5. Now see the penalties, all the penalties are negative values.
Now the optimality is reached. Okay, so this is the final solution. So if we get any positive value, again we need to repeat the same procedure.
We have to draw, we have to find the new cell and we have to draw a closed loop. According to the rule and we have to proceed the same thing until we reach the optimality. Now find the total cost.
250 into 1. 250 into 1 plus 200 into 2 plus 150 into 5 plus 50 into 3. plus 200 into 3 plus 150 into 2 what is the total cost 250 into 1 250 200 into 2 400 150 into 5 750 plus 15 into 3 150 plus 200 into 3, 600 plus 150 into 2, 300. Total cost, how much? 2,450. This is the total transportation cost.
This is the optimum answer.