C. Example model description

Model description written in GNU MathProg

Below here is a complete example of the model description written in the GNU MathProg modeling language.

# A TRANSPORTATION PROBLEM
#
# This problem finds a least cost shipping schedule that meets
# requirements at markets and supplies at factories.
#
#  References:
#              Dantzig G B, "Linear Programming and Extensions."
#              Princeton University Press, Princeton, New Jersey, 1963,
#              Chapter 3-3.

set I;
/* canning plants */

set J;
/* markets */

param a{i in I};
/* capacity of plant i in cases */

param b{j in J};
/* demand at market j in cases */

param d{i in I, j in J};
/* distance in thousands of miles */

param f;
/* freight in dollars per case per thousand miles */

param c{i in I, j in J} := f * d[i,j] / 1000;
/* transport cost in thousands of dollars per case */

var x{i in I, j in J} >= 0;
/* shipment quantities in cases */

minimize cost: sum{i in I, j in J} c[i,j] * x[i,j];
/* total transportation costs in thousands of dollars */

s.t. supply{i in I}: sum{j in J} x[i,j] <= a[i];
/* observe supply limit at plant i */

s.t. demand{j in J}: sum{i in I} x[i,j] >= b[j];
/* satisfy demand at market j */

data;

set I := Seattle San-Diego;

set J := New-York Chicago Topeka;

param a := Seattle     350
           San-Diego   600;

param b := New-York    325
           Chicago     300
           Topeka      275;

param d :              New-York   Chicago   Topeka :=
           Seattle     2.5        1.7       1.8
           San-Diego   2.5        1.8       1.4  ;

param f := 90;

end;

Generated LP problem

Below here is the result of the translation of the example model produced by the solver glpsol and written in the CPLEX LP format with the option --wcpxlp.

\* Problem: transp *\

Minimize
 cost: + 0.225 x(Seattle,New~York) + 0.153 x(Seattle,Chicago)
 + 0.162 x(Seattle,Topeka) + 0.225 x(San~Diego,New~York)
 + 0.162 x(San~Diego,Chicago) + 0.126 x(San~Diego,Topeka)

Subject To
 supply(Seattle): + x(Seattle,New~York) + x(Seattle,Chicago)
 + x(Seattle,Topeka) <= 350
 supply(San~Diego): + x(San~Diego,New~York) + x(San~Diego,Chicago)
 + x(San~Diego,Topeka) <= 600
 demand(New~York): + x(Seattle,New~York) + x(San~Diego,New~York) >= 325
 demand(Chicago): + x(Seattle,Chicago) + x(San~Diego,Chicago) >= 300
 demand(Topeka): + x(Seattle,Topeka) + x(San~Diego,Topeka) >= 275

End

Optimal LP solution

Below here is the optimal solution of the generated LP problem found by the solver glpsol and written in plain text format with the option --output.

Problem:    transp
Rows:       6
Columns:    6
Non-zeros:  18
Status:     OPTIMAL
Objective:  cost = 153.675 (MINimum)

   No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 cost         B        153.675
     2 supply[Seattle]
                    B            300                         350
     3 supply[San-Diego]
                    NU           600                         600         < eps
     4 demand[New-York]
                    NL           325           325                       0.225
     5 demand[Chicago]
                    NL           300           300                       0.153
     6 demand[Topeka]
                    NL           275           275                       0.126

   No. Column name  St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 x[Seattle,New-York]
                    B              0             0               
     2 x[Seattle,Chicago]
                    B            300             0               
     3 x[Seattle,Topeka]
                    NL             0             0                       0.036
     4 x[San-Diego,New-York]
                    B            325             0               
     5 x[San-Diego,Chicago]
                    NL             0             0                       0.009
     6 x[San-Diego,Topeka]
                    B            275             0               

End of output

Acknowledgements

The author would like to thank the following people, who kindly read, commented, and corrected the draft of this manual:

Juan Carlos Borras <borras@cs.helsinki.fi>

Harley Mackenzie <hjm@bigpond.com>

Robbie Morrison <robbie@actrix.co.nz>