So I have an issue with finding the optimal solution (the lowest costs) to a transportation problem. Given the following problem, with $A$ the depots, $B$ the destinations and $C$ the $(i,j)$ matrix with the costs of transferring from depot $i$ to destination $j$. $$A = \left(\begin{matrix} 15\\30\\55\end{matrix}\right), B=\left(\begin{matrix} 30\\10\\15\\45\end{matrix}\right),C =\left(\begin{matrix} 3 & 7 & 3 & 4\\ 5 & 7 &2&6\\8&13&9&3\end{matrix}\right)$$ My book explains that to solve this problem, you can first create a table, using several techniques (like the northwest rule, the minimal-cost rule and Vogel's method). For this example, it uses the northwest rule, giving the following table (I don't know how to make horizontal lines!): $$\begin{array}{c|c|c|c|c|c|c|c|c|} depot\ /\ destination&cost &30&cost&10&cost&15&cost&45\\15&3&15&7&&3&&4\\30&5&15&7&10&2&5&6&\\ 55&8&&13&&9&10&3&45 \end{array}$$ Next, they talk about using the dual problem to solve it, and here's where I'm at a loss: Now I'm told to check if the solution I've found matches all conditions of the dual problem. (probably not, since this is just a feasible solution, not the optimal one) If it does, I've found the optimal solution. If it doesn't, I should use pivotcolumns and trees (?!) to add additional edges to the tree, creating cycles. Next, I should add a '+' or '-' to the corresponding branches, giving the following table: $$\begin{array}{c|c|c|c|c|c|c|c|c|c|} D\ /\ D&cost &3&cost&5&cost&0&cost&-6\\0&3&15&7&&3&&4\\2&5&15^-&7&10&2&5^+&6&\\ 9&8&\ \ \ \ \ ^+&13&&9&10^-&3&45 \end{array},\ \ costs=425$$ Which (apparently) gives the optimal solution $$\begin{array}{c|c|c|c|c|c|c|c|c|c|} D\ /\ D&cost &3&cost&5&cost&0&cost&-2\\0&3&15&7&&3&&4\\2&5&5&7&10&2&15&6&\\ 5&8&10&13&&9&&3&45 \end{array},\ \ costs=385$$
Now, my book isn't all too clear on this method, so I'm sorry for any confusion caused by the lack of information. Could you please explain this method, or give me it's name so I can look it up online?