# Linear programming in Python (2)

Here's an example of a transportation problem, with information given as a table:

Demands |
||||||

300 | 360 | 280 | 340 | 220 | ||
---|---|---|---|---|---|---|

750 | 100 | 150 | 200 | 140 | 35 | |

Supplies |
400 | 50 | 70 | 80 | 65 | 80 |

350 | 40 | 90 | 100 | 150 | 130 |

This is an example of a *balanced, non-degenerate* transportation problem. It
is *balanced* since the sum of supplies equals the sum of demands, and it is
*non-degenerate* as there is no proper subset of supplies whose sum is equal to
that of a proper subset of demands. That is, there are no balanced
"sub-problems".

In such a problem, the array values may be considered to be the costs of transporting one object from a supplier to a demand. (In the version of the problem I pose to my students it's cars between distributors and car-yards; in another version it's tubs of ice-cream between dairies and supermarkets.) The idea of course is to move all objects from supplies to demands while minimizing the total cost.

This is a standard linear optimization problem, and it can be solved by any method used to solve such problems, although generally specialized methods are used.

But the intention here is to show how easily this problem can be managed using myMathProg (and with numpy, for the simple use of printing an array):

```
1import pymprog as py
2import numpy as np
3py.begin('transport')
4M = range(3) # number of rows and columns
5N = range(5)
6A = py.iprod(M,N) # Cartesian product
7x = py.var('x', A, kind=int) # all the decision variables are integers
8costs = [[100,150,200,140,35],[50,70,80,65,80],[40,90,100,150,130]]
9supplies = [750,400,350]
10demands = [300,360,280,340,220]
11py.minimize(sum(costs[i][j]*x[i,j] for i,j in A))
12# the total sum in each row must equal the supplies
13for k in M:
14 sum(x[k,j] for j in N)==supplies[k]
15# the total sum in each column must equal the demands
16for k in N:
17 sum(x[i,k] for i in M)==demands[k]
18py.solve()
19print('\nMinimum cost: ',py.vobj())
20A = np.array([[x[i,j].primal for j in N] for i in M])
21print('\n')
22print(A)
23print('\n')
24#py.sensitivity()
25py.end()
```

with solution:

```
1GLPK Simplex Optimizer, v4.65
2n8 rows, 15 columns, 30 non-zeros
3 0: obj = 0.000000000e+00 inf = 3.000e+03 (8)
4 7: obj = 1.789500000e+05 inf = 0.000e+00 (0)
5* 12: obj = 1.311000000e+05 inf = 0.000e+00 (0)
6OPTIMAL LP SOLUTION FOUND
7GLPK Integer Optimizer, v4.65
88 rows, 15 columns, 30 non-zeros
915 integer variables, none of which are binary
10Integer optimization begins...
11Long-step dual simplex will be used
12+ 12: mip = not found yet >= -inf (1; 0)
13+ 12: >>>>> 1.311000000e+05 >= 1.311000000e+05 0.0% (1; 0)
14+ 12: mip = 1.311000000e+05 >= tree is empty 0.0% (0; 1)
15INTEGER OPTIMAL SOLUTION FOUND
16
17Minimum cost: 131100.0
18
19[[ 0. 190. 0. 340. 220.]
20 [ 0. 120. 280. 0. 0.]
21 [300. 50. 0. 0. 0.]]
```

As you see, the definition of the problem in Python is very straightforward.