previous				contents				next

3. Abstracting the Structure of the Problem

3.1 Concepts

We shall now consider the structure of our simple oil blending model. What are the classes of object with which we are dealing and whose behaviour is essentially similar? They are the:

• components: LGO, HGO, WAXD, ARES and VRES
• qualities: SG, VBI, Sulphur

We might also consider that there was a class of objects:

• products: HFO

because a similar matrix would exist for other products. We shall disregard this for now.

We shall use individual lower case letters as subscripts to denote these classes of object. To be specific we shall use:

• r for components;
• q for qualities

• the cost of component r, COST_r
• the value of quality q of component r, QUAL_qr
• the maximum value of quality q in the blend, QMAX_q
• the demand for product, DEMAND
• the availability of component r, AVAIL_r

What are our decision variables? These are:

• the quantity of component r to use in the blend, x_r.

To complete our armoury of notation we shall use the symbols S_j to mean 'sum over j' and "i to mean 'for all i'.

3.2 Writing the Structure Symbolically

Then we can write our problem informally as

minimize

S_r Cost of r * Quantity of r used

subject to:

1. the quality constraints for each q

S_r Quality q of r * Quantity of r used

£ Max quality * Total quantity made

2. the demand constraint

S_r Quantity of r used = Demand

3. the availability constraints for each r

Quantity of r used £ Availability of r

We can write this more formally as:

minimize

S_r COST_r x_r

subject to

1. the quality constraints

Sr  QUALqr xr   £   QMAXq  Sr xr		" q

2. the demand constraint

S_r x_r = DEMAND

3. the availability constraints

xr  £  AVAILr			"r

If we are being formal we should also constrain each x_r variable to be non-negative:

xr  ³   0				" r

although in practice this is assumed by convention.

3.3 Improving the Quality Constraints

This mathematical formulation may appear more verbose than our simple matrix. Indeed, it occupies much more space when presented with the data as an input file for an algebraic modelling language such as XPRESS. But this is an unfair comparison. Our mathematical formulation remains the same whether we are working with 5 or 50 components and 3 or 30 qualities. It also holds true for blends of any product and for making batches of the product today, tomorrow and at any time.

More important than this, it provides a much better way of thinking about our problem. We can manipulate the mathematical formulation and consider how to improve it. If we wish to add minimum quality constraints all that we need do is to add the data items:

• the minimum value of quality q in the blend, QMIN_q

and the minimum quality constraints:

Sr  QUALqr xr   ³   QMINq  Sr xr		" q

It is now a trivial piece of manipulation to write the quality constraints as:

Sr  (QUALqr - QMAXq )  xr   £   0		"q
  
Sr  (QUALqr - QMINq )  xr   ³   0		"q

Now that we are being precise we should record the units in which we measure the data items, decision variables and constraints. Let us say that we are working in tonnes, i.e. AVAIL_r , DEMAND and x_r are all measured in tonnes. We shall use $ as our currency so COST_r is measured in $/tonne. The objective is thus measured in $ while the availability and demand constraints are measured in tonnes. We need to check that for each row (i.e. constraint or the objective), each term (i.e. coefficient multiplied by decision variable) has the same units and that these correspond to the units we have declared for the row. For these rows they do.

What should we do about qualities? What are the units of quality q? Specific gravity is the dimensionless ratio of the density of the material divided by the density of water. VBI is a numerical index which is derived by taking the logarithm of the logarithm of a number measured in centiStokes, which has dimensions Mass Length^-1 Time^-1. Sulphur is usually measured as a % by weight, i.e. is dimensionless but calculated as tonnes of Sulphur / 100 tonnes of material.

In order to avoid getting bogged down in technical details, when dealing with qualities we shall use the term "units of quality q" as the equivalent of $ for costs. Then the units of QUAL_qr , QMAX_q , and QMIN_q are units of quality q.

But what are the units of the quality constraints? More seriously, are the quality constraints correct? In section 7 of Practical LP we saw that some qualities blended by weight while others blended by volume. VBI and Sulphur content are examples of qualities which blend by weight, so the quality constraints we have defined are correct for those qualities. But specific gravity blends by volume, so the constraints which we require are

Sr  (QUALqr - QMAXq )  vr   £   0		" q
  
Sr  (QUALqr - QMINq )  vr   ³   0		" q

where v_r is the volume of component r in the blend.

Now v_r = x_r / (r _WATER * SG_r ) so we have

Sr  { (QUALqr - QMAXq ) / (r WATER  * SGr ) } xr    £   0		" q
  
Sr  { (QUALqr - QMINq ) / (r WATER  * SGr ) } xr    ³   0		" q

or, cancelling out the r _WATER

Sr  { (QUALqr - QMAXq ) / SGr  }  xr    £   0			" q
  
Sr  { (QUALqr - QMINq) / SGr } xr    ³   0			" q

These are the form of quality constraint which we require for qualities which blend by volume. The fact that we happened to be considering specific gravity is irrelevant to the appearance of SG_r as the divisor of the term S_r (QUAL_qr - QMAX_q ) and S_r (QUAL_qr - QMIN_q ): SG_r divides these terms in the quality constraints for all qualities which blend by volume.

The advantages of an algebraic notation should now have become more clear. It would have been far harder to have developed these constraints correctly if we had been working with specific instances of the constraints rather than algebra. The notation is a prop to our thoughts.

previous				contents				next