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.    
 A: 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 ... ;-) 
