Solutions to Transport Problems Using Dynamic Programming

[evinda]

Hello! (Wave)Suppose that we have $M$ production stations $A_1, \dots, A_M$ of a product and $N$ destination stations $B_1, \dots, B_N$ of the product.

We suppose that $x_{ij}$ units of the product are transferred from $A_i$ to $B_j$ where $i=1, \dots, M, j=1, \dots, N$. The cost of transportation of $x_{ij}$ units of the product is $c_{ij} x_{ij}$ where $c_{ij}>0$.We want to see what quantities the stations $A_1, \dots, A_M$ have to produce and simultaneously how these quantities have to be distributed to the stations $B_1, \dots, B_N$ so that the cost of transport gets minimized.

Solution of the problem of transport using techniques of dynamic programmingWe suppose that $M=2$.

Then $a_1, a_2$ are the available quantities of the product at the stations $A_1, A_2$ respectively.We define $f_n^{\star}(x_{1n}, x_{2n})$ the cost of the optimal strategy for the transport of the product from the two production stations with quantities $x_{1n}, x_{2n}$ respectively to the $n$ destination stations.Then if we subtract $y_1$ units from the production station $A_1$ and $y_2$ units from $A_2$, for the equipment of the $n$-th destination station $B_n$, then there will be $(x_{1n}-y_1, x_{2n}-y_2)$ quantities left for the equipment of the remaining $n-1$ destination stations.The mathematical formulation of the above is:$$f_n^{\star} (x_{1n}, x_{2n})= \min_{y \in S_n} \left( c_{1n} y+ c_{2n}(b_n-y)+f_{n-1}^{\star}(x_{1n}-y, x_{2n}-(b_n-y))\right)\\ S_n=\{y: y \geq \max \{ 0, b_n-x_{2n}\} \text{ and } y\leq \min \{x_{1n}, b_n \} \} \text{ and } x_{1n} \leq a_1, x_{2n} \leq a_2$$Could you explain to me how we get this formula? (Thinking)

 

[Valkarie]

The formula describes the optimal transport strategy for the two production stations with quantities $x_{1n}, x_{2n}$ respectively to the $n$ destination stations. The cost of the optimal strategy is expressed as a minimum value over all possible values of $y$ which are in the range of $S_n$ (which are the valid sets of $y$ that can be chosen).The cost of the optimal strategy is calculated by taking the cost of transporting $y$ units from station $A_1$ ($c_{1n} y$) plus the cost of transporting $(b_n-y)$ units from station $A_2$ ($c_{2n}(b_n-y)$) plus the cost of transporting the remaining quantities to the other $n-1$ destination stations ($f_{n-1}^{\star}(x_{1n}-y, x_{2n}-(b_n-y))$). The range of valid values of $y$ is given by $S_n$, which is the set of all $y$ such that $y \geq \max \{ 0, b_n-x_{2n}\}$ and $y\leq \min \{x_{1n}, b_n \}$ and $x_{1n} \leq a_1, x_{2n} \leq a_2$.