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.

  • $\begingroup$ What is the definition of $i_1,i_2$ and $j_1,j_2$ ? $\endgroup$ – callculus Apr 3 '16 at 20:44
  • $\begingroup$ @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. $\endgroup$ – user326049 Apr 4 '16 at 9:22


  • $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 ... ;-)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.