$ondollar title Bay Ferry (MCF) Example 10.6 of Rardin (1998)

$offsymxref offsymlist offuelxref offuellist offupper
option limrow = 0, limcol = 0;

sets
i  "nodes" /1*7/,
o  "origins" /1, 4, 5/;
alias (i,j);
alias (i,k);

set arc(i,j) "arc set of the digraph"
/1.2, 2.1, 2.3, 2.6, 3.2, 3.4, 4.3, 4.5, 5.4, 5.6, 6.2, 6.5, 6.7, 7.6/;

parameter c(i,j) "unit costs of flow"
/1.2 3.5, 2.1 3.5, 2.3 3.0, 3.2 3.0, 3.4 5.0, 4.3 5.0,
4.5 25.0, 5.4 25.0, 5.6 4.0, 6.5 4.0, 6.7 2.5, 7.6 2.5/;

table b(o,k) "trips from origin o to destination k"
      1      2      3      4      5      6      7
1           900    750    40     10     600    550
4    100    2000  1100          150    1400   1250
5    110    4000  2200   200           3300   2440;
b('1','1') = - sum(k, b('1',k));
b('4','4') = - sum(k, b('4',k));
b('5','5') = - sum(k, b('5',k));

parameter u(i,j) "capacity of arc (i,j)"
/2.6 2000, 6.2 2000/;
      
free variable drive "total driving";

positive variables
x(o,i,j)   "flow originating at o on arc (i,j)";

equations
obj      "minimize total driving",
bal(o,k) "balance of origin o flow at node k",
cap(i,j) "common capacities on arcs (i,j)";

obj..
drive =e= sum(o, sum((i,j)$arc(i,j), c(i,j)*x(o,i,j)) );

bal(o,k)..
sum(i$arc(i,k), x(o,i,k)) - sum(j$arc(k,j), x(o,k,j)) =e= b(o,k);

cap(i,j)$(u(i,j) gt 0)..
sum(o, x(o,i,j)) =l= u(i,j);

model bayferry /all/;

solve bayferry using lp minimizing drive;