previous				contents				next

7. A Multi-Mix Blending Problem

7.1 The Problem

Our simple blending problem was concerned with making a single product, HFO, from various components. In practice, blenders have to make more than one product from a given pool of materials. A complication arises when some materials are available in different quantities at different prices. In particular, the manager may assign a lower price to the use of existing stocks of materials than to the use of material that has to be newly purchased.

Multi-mix blending problems are defined by the following data:

Subscripts

p		Product
q		Quality
r		Material
s		Source

Sets

SQL		Set of qualities with a lower limit
SQU		Set of qualities with an upper limit
SRp		Set of materials that can be used to make product p
SPr		Set of products in which material r can be used.

Constants

AVAILrs      	Availability of material r from source s (tonnes)
DEMANDp 	Demand for product (tonnes)
COSTrs      	Price of raw material ($/tonne)
QMAXpq      	Maximum permitted amount of q in product p (units of quality q)
QMINpq      	Minimum permitted amount of q in product p (units of quality q)
QUALqr      	Amount of q per tonne of r (units of quality q).

7.2 The Natural Formulation

The natural formulation for this problem is to write x_rs for the amount of raw material purchased (tonnes) and y_pr for the amount of raw material used (tonnes).

Then we must

minimize costs ($)

S _r S _s COST_rs x_rs

subject to

1. quality constraints (units of quality q * tonnes)

Sr ÎSRp ( QUALqr - QMAXpq ) ypr   £   0		" p, q ÎSQU
  
Sr ÎSRp ( QUALqr - QMINpq ) ypr   ³   0		" p, q ÎSQL

2. the availability constraints (tonnes)

xrs   £   AVAILrs 				" r, s

3. the material balance constraints (tonnes)

S r xrs  -   SpÎSPr  ypr   =   0			" r
  
Sr ÎSRp   ypr   =   DEMANDp			" p

together with the constraints that all variables are nonnegative.

7.3 An Alternative Formulation

It is of some interest to note that this problem has an apparently simpler formulation in terms of a single type of variable. If z_prs is the number of tonnes of material r bought from source s and used to make product p, the problem is to

minimize

S _p S _r S _s COST_rs z_prs

subject to the constraints

Sr ÎSRp S s ( QUALqr - QMAXpq ) zprs   £   0		" p, q Î SQU
  
S r ÎSRp S s ( QUALqr - QMINpq )  zprs   ³   0		" p, q Î SQL
  
S p  zprs   £   AVAILrs				" r, s
  
S r ÎSRp   zprs   =   DEMANDp			" p

7.4 Why the Natural Formulation is Better

This alternative formulation omits one set of material balance constraints. But it has more decision variables, and, more seriously, more non-zero coefficients than the recommended formulation.

One consequence of this is that the model makes decisions about the source s of material r used in making product p which are entirely arbitrary (and will actually reflect the naming convention used in the matrix). If calculations are made of the cost of making the individual products, these will show some products to be more profitable than others simply because they have used the high-cost source of material r rather than the low-cost source. This allocation has been entirely arbitrary but it could lead to erroneous decisions as to which plants are profitable and which loss-making.

This illustrates the importance of building a model which reflects the data which are available. More generally, it shows that one should not believe something must be true just because the computer says so.

previous				contents				next