| rev |
line source |
|
alpar@9
|
1 # A TRANSPORTATION PROBLEM
|
|
alpar@9
|
2 #
|
|
alpar@9
|
3 # This problem finds a least cost shipping schedule that meets
|
|
alpar@9
|
4 # requirements at markets and supplies at factories.
|
|
alpar@9
|
5 #
|
|
alpar@9
|
6 # References:
|
|
alpar@9
|
7 # Dantzig G B, "Linear Programming and Extensions."
|
|
alpar@9
|
8 # Princeton University Press, Princeton, New Jersey, 1963,
|
|
alpar@9
|
9 # Chapter 3-3.
|
|
alpar@9
|
10
|
|
alpar@9
|
11 set I;
|
|
alpar@9
|
12 /* canning plants */
|
|
alpar@9
|
13
|
|
alpar@9
|
14 set J;
|
|
alpar@9
|
15 /* markets */
|
|
alpar@9
|
16
|
|
alpar@9
|
17 param a{i in I};
|
|
alpar@9
|
18 /* capacity of plant i in cases */
|
|
alpar@9
|
19
|
|
alpar@9
|
20 param b{j in J};
|
|
alpar@9
|
21 /* demand at market j in cases */
|
|
alpar@9
|
22
|
|
alpar@9
|
23 param d{i in I, j in J};
|
|
alpar@9
|
24 /* distance in thousands of miles */
|
|
alpar@9
|
25
|
|
alpar@9
|
26 param f;
|
|
alpar@9
|
27 /* freight in dollars per case per thousand miles */
|
|
alpar@9
|
28
|
|
alpar@9
|
29 param c{i in I, j in J} := f * d[i,j] / 1000;
|
|
alpar@9
|
30 /* transport cost in thousands of dollars per case */
|
|
alpar@9
|
31
|
|
alpar@9
|
32 var x{i in I, j in J} >= 0;
|
|
alpar@9
|
33 /* shipment quantities in cases */
|
|
alpar@9
|
34
|
|
alpar@9
|
35 minimize cost: sum{i in I, j in J} c[i,j] * x[i,j];
|
|
alpar@9
|
36 /* total transportation costs in thousands of dollars */
|
|
alpar@9
|
37
|
|
alpar@9
|
38 s.t. supply{i in I}: sum{j in J} x[i,j] <= a[i];
|
|
alpar@9
|
39 /* observe supply limit at plant i */
|
|
alpar@9
|
40
|
|
alpar@9
|
41 s.t. demand{j in J}: sum{i in I} x[i,j] >= b[j];
|
|
alpar@9
|
42 /* satisfy demand at market j */
|
|
alpar@9
|
43
|
|
alpar@9
|
44 data;
|
|
alpar@9
|
45
|
|
alpar@9
|
46 set I := Seattle San-Diego;
|
|
alpar@9
|
47
|
|
alpar@9
|
48 set J := New-York Chicago Topeka;
|
|
alpar@9
|
49
|
|
alpar@9
|
50 param a := Seattle 350
|
|
alpar@9
|
51 San-Diego 600;
|
|
alpar@9
|
52
|
|
alpar@9
|
53 param b := New-York 325
|
|
alpar@9
|
54 Chicago 300
|
|
alpar@9
|
55 Topeka 275;
|
|
alpar@9
|
56
|
|
alpar@9
|
57 param d : New-York Chicago Topeka :=
|
|
alpar@9
|
58 Seattle 2.5 1.7 1.8
|
|
alpar@9
|
59 San-Diego 2.5 1.8 1.4 ;
|
|
alpar@9
|
60
|
|
alpar@9
|
61 param f := 90;
|
|
alpar@9
|
62
|
|
alpar@9
|
63 end;
|
