# Linear optimization problem

$\mathbf{Problem}$: Varying amount of goods have to be transported along three paths: A,B,C; 780, 2425, 1000 units respectively. Three trucks are available: 1.5, 3.5 and 5 tonne capacity. First two have 250 rides limit, the third (5 tonne) can only do 200 rides.

Cost matrix, columns for 1.5, 3.5 and 5 tonne trucks, rows for path A,B,C. $$A= \left( \begin{array}{ccc} 35 & 65 & 85 \\ 60 & 90& 110 \\ 25 & 33& 40 \end{array} \right)$$ We want to minimize the cost of transport while keeping the ride limit and transporting the specified unit amount of goods.

$\mathbf{Solution}$: So I figured that we want to minimize $$\left( \begin{array}{ccc} 35 & 65 & 85 \\ 60 & 90& 110 \\ 25 & 33& 40 \end{array} \right) \left( \begin{array}{ccc} a_1 & a_2 & a_3 \\ b_1 & b_2 & b_3 \\ c_1 & c_2 & c_3 \end{array} \right)$$

subject to $$\left( \begin{array}{ccc} a_1 & a_2 & a_3 \\ b_1 & b_2 & b_3 \\ c_1 & c_2 & c_3 \end{array} \right) \left( \begin{array}{ccc} 1.5\\3.5\\5 \end{array} \right)= \left( \begin{array}{ccc} 780\\2425\\1000 \end{array} \right)$$ Also,

$$\left( \begin{array}{ccc} a_1+b_1+c_1 \\ a_2+b_2+c_2 \\ a_3+b_3+c_3 \end{array} \right)\le \left( \begin{array}{ccc} 250\\250\\200 \end{array} \right)$$

Honestly I'm just starting with this entire topic and just stumbled upon this problem. It's been pointed out that there is no reasonable way of minimizing a matrix (I agree). I can't think of a better way of formulating the cost function.

• What are you minimizing? You just have two matricies. – Ross B. Jun 12 '13 at 12:38
• I'm minimizing the product of the two matrices above. Basically I want to find coefficients $a_1, \dots, c_3$ such that the product is minimized. – shimee Jun 12 '13 at 12:39
• Not sure I understand. The product of 2 matrices is a matrix, say $(a_{i,j})$. In what sense are you minimizing it? Do you need $\sum_{i,j} |a_{i,j}|$ or $\sum_{i,j} a_{i,j}^2$ to be minimal? – gt6989b Jun 12 '13 at 12:41
• Typical linear problems are solved with the en.wikipedia.org/wiki/Simplex_algorithm. – gt6989b Jun 12 '13 at 12:46
• As already pointed out in other comments, it is necessary that you define your target function. Right now it is undefined, because there is no standard way to minimize a matrix (which is the result of your matrix product). Please edit your question so we can understand in which sense you are trying to minimize this 3x3 matrix. – Matt L. Jun 12 '13 at 13:06

## 1 Answer

I guess problem is not solvable with current constraints. Assume that all the trucks travel at their limits. The total amount that can be carried is $$250*1.5+250*3.5+200*5=2250$$ which is less that total amount required of $$780+2425+1000=4205$$

• I turned the equals into less or equal, thanks. – shimee Jun 13 '13 at 9:10
• Still the maximum limit trucks can carry is less than the quantity to be transported; so the problem doesn't have any solution. – AnilB Jun 20 '13 at 9:17