# Two problems related to the Hitchcock transport problem.

I try to solve the following two problems related to the "Hitchcock Transportation Problem" which reads as follows :$$min \sum_{i=1}^N\sum_{j=1}^Mc_{ij}x_{ij}$$subject to$$\sum_{j=1}^Mx_{ij}=a_i\space\space (i=1...N)\space and\space\sum_{i=1}^Nx_{ij}=b_j\space\space(j=1...M)\space and\space x_{ij}\ge0$$where $a_i$ is the amount of goods in the warehouse $i$ and $b_j$ is the amount of goods needed in store $j$, the amount of goods transported form $i$ to $j$ is $x_{ij}$ and the costs for doing this are $c_{ij}$. We suppose that $\sum_{i=1}^Na_i=\sum_{j=1}^Mb_j$. Now i want to show:

1) If $\bar x$ is a solution of the problem then for all $i_1,i_2\in \{1,..,N\}$ and for all $j_1,j_2\in\{1,..,M\}$ $$\bar x_{i_1j_1}>0\space,\bar x_{i_2j_2}>0\Rightarrow c_{i_1j_1}+c_{i_2j_2}\le c_{i_1j_2}+c_{i_2j_1}$$2) If the transport costs are given by $c_{ij}=|j-i|^2$ then for all $i_1,i_2\in \{1,..,N\}$ and for all $j_1,j_2\in\{1,..,M\}$$i_1<i_2\space and \space \bar x_{i_1j_1}>0\space,\bar x_{i_2j_2}>0 \Rightarrow j_1\le j_2$$I would be thankful for any help. • What is the definition of$i_1,i_2$and$j_1,j_2$? – callculus Apr 3 '16 at 20:44 • @callculus$i$means one of the N warehouses, so$i_1,i_2$are two arbitrary warehouses out of the N, the same for$j$, so$j_1$and$j_2$are two arbitrary stores out of the M stores. – user326049 Apr 4 '16 at 9:22 ## 1 Answer Recall: •$x_{i,j}$is the amount of product transported from source$i$to destination$j$•$c_{i,j}$is the cost associated with transporting one unit from source$i$to destination$j$For 1.), we can construct a proof by contradiction. Here is a sketch of this proof: Assume to the contrary that$c_{i_1,j_1}+c_{i_2,j_2} > c_{i_1,j_2}+c_{i_2,j_1}$. Then we can construct a new solution as follows: • Keep all$x_k (k <> i_1, i_2, j_1, j_2)$as they are in the current optimal solution. • Reduce$x_{i_1,j_1}$and$x_{i_2,j_2}$by the amount$y = min(x_{i_1,j_1}$,$x_{i_2,j_2})$each. This makes sure that they stay non-negative. Note that y is positive as both$x_{i_1,j_1}$and$x_{i_2,j_2}$are positive. • Raise$x_{i_1,j_2}$by y • Raise$x_{i_2,j_1}$by y This new solution fulfills all constraints and the objective value is strictly lower. Contradiction! Interpretation: The assumption says: It is cheaper to supply one unit each from$i_1$to$j_2$and one unit from$i_2$to$j_1 $then to supply one unit from$i_1$to$j_1$and one unit from$i_2$to$j_2$. If this is the case, then reduce the two streams which are together more expensive by$y$units each and instead increase the two cheaper streams by$y\$ units each. As the two sources are kept the same and the two destinations as well, all source constraints and destination constraints must still hold.

2.) is a direct consequence from one. Just use the definition and the given cost function.

Remark: This reads like a classic student exercise on the Hitchcock transport problem ... ;-)