Transportation problem in linear programming with a twist

Question

I've been trying to solve a close to the classic transportation problem, but with a twist. The twist is that the transportation from say factory A to supermarket 1 is being done in trucks. So no matter if I transport 1 tonne or 9 tonnes from A to 1 I'll pay the same price (9 is the capacity of the truck). So far, I've re-written the optimization function in Excel as follows: min z = Price from A to 1*ROUNDUP(A1/9,0) and so on - and I believe that works in Excel.(The prices of transportation from different factories to supermarkets are different). However, I don't know how to write that as in linear programming. Can anyone help?

Answer 1

You could formulate this as follows. Introduce an (integer) variable $y_{i,j}$ indicating the number of trucks going from $i$ to $j$. Then $$\begin{align} \min&\sum_{i,j} C^{truck}_{i,j} \cdot y_{i,j}\\ &\sum_i x_{i,j} = demand_j\\ &\sum_j x_{i,j} \le capacity_i\\ & truckcapacity \cdot y_{i,j} \ge x_{i,j} \end{align}$$ This is still a linear model (although with integer variables).

Answer 2

You can define intermediate variables and declare them to be integer and that will round down the (A1/9) and then add 1 to it before multiplying it with the price. For example

You can create $x_1 = (\frac{A1}{9} + 1) $ and declare that the decision variables are x's and that you define it as Int . Sometimes it may not work in EXCEL but if you are using roundup a Simplex won't work and you may have to use GRG nonlinear.

If you follow my logic, you can use simplex as it would be a linear programming problem.

Thanks Satish