(* :Author A.I. McLeod *)
(* :http://www.stats.uwo.ca/mcleod *)
(* :aim@uwo.ca *)
(* :Summary:
This package solves the generalized cargo loading problem. This
problem is formulated mathematically as the maximization of a linear
function subject to a single linear constraint (<=). The coefficients in
the objective function and constraint are all assumed to be real
positive numbers. The decision variables obey the nonnegativity
condition and are integer valued. An additional constraint that can
be imposed is that each decision variables is less than or equal
to some prescribed number. The problem may be formulated as an integer
programming problem:
maximize v x subject to x>=0 and w x <= k and x <= q
The syntax for the Mathematica function Cargo is Cargo[k, v, w, q],
where k is a number appearing on the right-hand side of the constraint and
v, w and q denote respectively vectors of length n containing the
coefficients in the objective function, linear constraint and quantities
available. The function returns a vector of length n+1 containing
respectively the optimal value of the objective function and decision
variables.
*)
BeginPackage["Cargo`"]
Cargo::usage = "Cargo[k,v,w,q] solves the integer programming problem,
\n\n maximize v x subject to x>=0 and w x <= k and x <= q,\n\n where k is the right-hand side in the linear inequality constraint and v, w
and q denote vectors of length n containing respectively the coefficients in the objective
function, linear constraint and quantities available. The function returns a
vector of length n+1 containing the optimal values of first the objective function
and then the n decision variables."
Begin["`Private`"]
NumberVectorQ[x_] := VectorQ[x] && And @@ NumberQ /@ x;
Cargo[k_Integer?Positive, v_?NumberVectorQ, w_?NumberVectorQ, q_?NumberVectorQ] :=
Module[{f},
(* check that all vectors are the same length *)
If[Map[Length, {v,w,q}]===RotateLeft[Map[Length, {v,w,q}]],
Null,Print["Error: vector arguments lengths unequal"];Return[Null] ];
(* check that all coefficients are positive *)
If[Apply[And, Flatten[Positive[{v,w,q}]]],Null,
Print["Error: coefficient negative or zero"];Return[Null] ];
f[k2_, 0] = {0};
f[k2_, i_] :=
Module[ {z, t, opt},
opt = Array[0&, {i+1}];
Do[opt=If[
(z = x v[[i]] + First[t=f[k2-w[[i]] x, i-1]]) > First[opt],
Join[{z},Rest[t],{x}], opt],
{x,0,Min[q[[i]], Floor[k2/w[[i]]]]}
];
(* note: this assignment reduces cpu time by a factor of 6*)
Return[f[k2,i]=opt]
];
f[k, Length[v]]
]
End[ ]
EndPackage[ ]
Null