|
alpar@1
|
1 |
/* FCTP, Fixed-Charge Transportation Problem */
|
|
alpar@1
|
2 |
|
|
alpar@1
|
3 |
/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
|
|
alpar@1
|
4 |
|
|
alpar@1
|
5 |
/* The Fixed-Charge Transportation Problem (FCTP) is obtained from
|
|
alpar@1
|
6 |
classical transportation problem by imposing a fixed cost on each
|
|
alpar@1
|
7 |
transportation link if there is a positive flow on that link. */
|
|
alpar@1
|
8 |
|
|
alpar@1
|
9 |
param m, integer, > 0;
|
|
alpar@1
|
10 |
/* number of sources */
|
|
alpar@1
|
11 |
|
|
alpar@1
|
12 |
param n, integer, > 0;
|
|
alpar@1
|
13 |
/* number of customers */
|
|
alpar@1
|
14 |
|
|
alpar@1
|
15 |
set I := 1..m;
|
|
alpar@1
|
16 |
/* set of sources */
|
|
alpar@1
|
17 |
|
|
alpar@1
|
18 |
set J := 1..n;
|
|
alpar@1
|
19 |
/* set of customers */
|
|
alpar@1
|
20 |
|
|
alpar@1
|
21 |
param supply{i in I}, >= 0;
|
|
alpar@1
|
22 |
/* supply at source i */
|
|
alpar@1
|
23 |
|
|
alpar@1
|
24 |
param demand{j in J}, >= 0;
|
|
alpar@1
|
25 |
/* demand at customer j */
|
|
alpar@1
|
26 |
|
|
alpar@1
|
27 |
param varcost{i in I, j in J}, >= 0;
|
|
alpar@1
|
28 |
/* variable cost (a cost per one unit shipped from i to j) */
|
|
alpar@1
|
29 |
|
|
alpar@1
|
30 |
param fixcost{i in I, j in J}, >= 0;
|
|
alpar@1
|
31 |
/* fixed cost (a cost for shipping any amount from i to j) */
|
|
alpar@1
|
32 |
|
|
alpar@1
|
33 |
var x{i in I, j in J}, >= 0;
|
|
alpar@1
|
34 |
/* amount shipped from source i to customer j */
|
|
alpar@1
|
35 |
|
|
alpar@1
|
36 |
s.t. f{i in I}: sum{j in J} x[i,j] = supply[i];
|
|
alpar@1
|
37 |
/* observe supply at source i */
|
|
alpar@1
|
38 |
|
|
alpar@1
|
39 |
s.t. g{j in J}: sum{i in I} x[i,j] = demand[j];
|
|
alpar@1
|
40 |
/* satisfy demand at customer j */
|
|
alpar@1
|
41 |
|
|
alpar@1
|
42 |
var y{i in I, j in J}, binary;
|
|
alpar@1
|
43 |
/* y[i,j] = 1 means some amount is shipped from i to j */
|
|
alpar@1
|
44 |
|
|
alpar@1
|
45 |
s.t. h{i in I, j in J}: x[i,j] <= min(supply[i], demand[j]) * y[i,j];
|
|
alpar@1
|
46 |
/* if y[i,j] is 0, force x[i,j] to be 0 (may note that supply[i] and
|
|
alpar@1
|
47 |
demand[j] are implicit upper bounds for x[i,j] as follows from the
|
|
alpar@1
|
48 |
constraints f[i] and g[j]) */
|
|
alpar@1
|
49 |
|
|
alpar@1
|
50 |
minimize cost: sum{i in I, j in J} varcost[i,j] * x[i,j] +
|
|
alpar@1
|
51 |
sum{i in I, j in J} fixcost[i,j] * y[i,j];
|
|
alpar@1
|
52 |
/* total transportation costs */
|
|
alpar@1
|
53 |
|
|
alpar@1
|
54 |
data;
|
|
alpar@1
|
55 |
|
|
alpar@1
|
56 |
/* These data correspond to the instance bal8x12 from [Balinski]. */
|
|
alpar@1
|
57 |
|
|
alpar@1
|
58 |
/* The optimal solution is 471.55 */
|
|
alpar@1
|
59 |
|
|
alpar@1
|
60 |
param m := 8;
|
|
alpar@1
|
61 |
|
|
alpar@1
|
62 |
param n := 12;
|
|
alpar@1
|
63 |
|
|
alpar@1
|
64 |
param supply := 1 15.00, 2 20.00, 3 45.00, 4 35.00,
|
|
alpar@1
|
65 |
5 25.00, 6 35.00, 7 10.00, 8 25.00;
|
|
alpar@1
|
66 |
|
|
alpar@1
|
67 |
param demand := 1 20.00, 2 15.00, 3 20.00, 4 15.00,
|
|
alpar@1
|
68 |
5 5.00, 6 20.00, 7 30.00, 8 10.00,
|
|
alpar@1
|
69 |
9 35.00, 10 25.00, 11 10.00, 12 5.00;
|
|
alpar@1
|
70 |
|
|
alpar@1
|
71 |
param varcost
|
|
alpar@1
|
72 |
: 1 2 3 4 5 6 7 8 9 10 11 12 :=
|
|
alpar@1
|
73 |
1 0.69 0.64 0.71 0.79 1.70 2.83 2.02 5.64 5.94 5.94 5.94 7.68
|
|
alpar@1
|
74 |
2 1.01 0.75 0.88 0.59 1.50 2.63 2.26 5.64 5.85 5.62 5.85 4.94
|
|
alpar@1
|
75 |
3 1.05 1.06 1.08 0.64 1.22 2.37 1.66 5.64 5.91 5.62 5.91 4.94
|
|
alpar@1
|
76 |
4 1.94 1.50 1.56 1.22 1.98 1.98 1.36 6.99 6.99 6.99 6.99 3.68
|
|
alpar@1
|
77 |
5 1.61 1.40 1.61 1.33 1.68 2.83 1.54 4.26 4.26 4.26 4.26 2.99
|
|
alpar@1
|
78 |
6 5.29 5.94 6.08 5.29 5.96 6.77 5.08 0.31 0.21 0.17 0.31 1.53
|
|
alpar@1
|
79 |
7 5.29 5.94 6.08 5.29 5.96 6.77 5.08 0.55 0.35 0.40 0.19 1.53
|
|
alpar@1
|
80 |
8 5.29 6.08 6.08 5.29 5.96 6.45 5.08 2.43 2.30 2.33 1.81 2.50 ;
|
|
alpar@1
|
81 |
|
|
alpar@1
|
82 |
param fixcost
|
|
alpar@1
|
83 |
: 1 2 3 4 5 6 7 8 9 10 11 12 :=
|
|
alpar@1
|
84 |
1 11.0 16.0 18.0 17.0 10.0 20.0 17.0 13.0 15.0 12.0 14.0 14.0
|
|
alpar@1
|
85 |
2 14.0 17.0 17.0 13.0 15.0 13.0 16.0 11.0 20.0 11.0 15.0 10.0
|
|
alpar@1
|
86 |
3 12.0 13.0 20.0 17.0 13.0 15.0 16.0 13.0 12.0 13.0 10.0 18.0
|
|
alpar@1
|
87 |
4 16.0 19.0 16.0 11.0 15.0 12.0 18.0 12.0 18.0 13.0 13.0 14.0
|
|
alpar@1
|
88 |
5 19.0 18.0 15.0 16.0 12.0 14.0 20.0 19.0 11.0 17.0 16.0 18.0
|
|
alpar@1
|
89 |
6 13.0 20.0 20.0 17.0 15.0 12.0 14.0 11.0 12.0 19.0 15.0 16.0
|
|
alpar@1
|
90 |
7 11.0 12.0 15.0 10.0 17.0 11.0 11.0 16.0 10.0 18.0 17.0 12.0
|
|
alpar@1
|
91 |
8 17.0 10.0 20.0 12.0 17.0 20.0 16.0 15.0 10.0 12.0 16.0 18.0 ;
|
|
alpar@1
|
92 |
|
|
alpar@1
|
93 |
end;
|