! blend.txt - "blending problem" - integer programming example
!/
from http://people.brunel.ac.uk/~mastjjb/jeb/or/moreip.html
Integer programming example by J E Beasley
Blending problem
Consider the example of a manufacturer of animal feed who is producing a
feed mix for dairy cattle. In our simple example the feed mix contains
two active ingredients and a filler to provide bulk. One kg of feed mix
must contain a minimum quantity of each of four nutrients as below:
Nutrient A B C D
grams 90 50 20 2
The ingredients have the following nutrient values and cost:
A B C D Cost/kg
Ingredient 1 (gram/kg) 100 80 40 10 40
Ingredient 2 (gram/kg) 200 150 20 - 60
What should be the amounts of active ingredients and filler in one kg of
feed mix?
Blending problem solution
Variables
In order to solve this problem it is best to think in terms of one
kilogram of feed mix. That kilogram is made up of three parts -
ingredient 1, ingredient 2 and filler, so let
x1 = amount (kg) of ingredient 1 in one kg of feed mix
x2 = amount (kg) of ingredient 2 in one kg of feed mix
x3 = amount (kg) of filler in one kg of feed mix
where x1 >= 0, x2 >= 0 and x3 >= 0.
Constraints
* balancing constraint (an implicit constraint due to the definition
of the variables)
x1 + x2 + x3 = 1 (each kg composed of ingredients 1 & 2 and filler)
* nutrient constraints (per kg)
100x1 + 200x2 >= 90 (nutrient A)
80x1 + 150x2 >= 50 (nutrient B)
40x1 + 20x2 >= 20 (nutrient C)
10x1 >= 2 (nutrient D)
Note the use of an inequality rather than an equality in these constraints,
following the rule we put forward in the Two Mines example, where we assume
that the nutrient levels we want are lower limits on the amount of nutrient
in one kg of feed mix.
Objective
Presumably to minimize cost, i.e.
minimize 40x1 + 60x2
which gives us our complete LP model for the blending problem.
--------------------------------------
My adjusted formulation:
Since I haven't defined floating point arithmetic, we will let x1,x2,xf
be integer kg quantities that add up to some large number N, say, 100.
(I'm calling the filler variable xf.)
xf + x1 + x2 = N
N = 100
Values x1/N,x2/N,xf/N will thus be the fraction of ingredient in each
kg of feed. Making N larger will increase the resolution of the solution.
The nutrient constraints can now be written as follows:
100 x1 + 200 x2 >= 90 * N (nutrient A)
80 x1 + 150 x2 >= 50 * N (nutrient B)
40 x1 + 20 x2 >= 20 * N (nutrient C)
10 x1 >= 2 * N (nutrient D)
The needed grams of nutrients are multiplied by N since we are dealing
with grams of nutrients needed in N kg quantities.
The cost formula can be left unchanged except that it now computes the
cost of a N kg quantity of feed:
minimize 40 x1 + 60 x2 -- cost for N kg
!\
! x1,x2,xf,cost: - optimal relative ingredient kg quantities and cost
(x1,x2,xf,cost: %x1 %x2 %xf %cost)< ! relative int ingredients & N-kg cost
(== %N 100), ! total quantity being considered -> resolution of solution
! -- could choose higher-resolution solution here, say, parts per 1000
(iota_d %N %0-N), ! decimal numbers from 0..N (APL fn name)
(cartesian %0-N %0-N %0-N %args), ! % ranges of the 3 ingredients
! -- This generalized cartesian product forms 3-element tuples
! of all combinations of integers from 0..N.
(constraints ! -- arg vars _0, _1, _2 represent ingredients filler,1,2
((_0 + _1 + _2 = %N) ! 3 natural number vars sum to N
(100 * _1 + 200 * _2 >= 90 * %N) ! A nutrient grams required
( 80 * _1 + 150 * _2 >= 50 * %N) ! B
( 40 * _1 + 20 * _2 >= 20 * %N) ! C
( 10 * _1 >= 2 * %N) ! D
) ! each constraint formula must evaluate to true
%args %selected_args), ! %selected args are tuples that satisfy constrs
(minimize (40 * _1 + 60 * _2) %selected_args %cost (%xf %x1 %x2)).
! -- filler is free(?)