3.2 The Simple Oil Blending Model Revisited

Recapitulation

We have already explored the behaviour of LP models using as our example a simple oil blending model. We shall now continue from where we left off, showing how we can simplify the task of building and using models by abstracting their mathematical structure.

Our model was represented by the LP matrix in Fig 1.

Fig 1: Turbo Simplex Matrix - Minimise Cost of Blend

{ Simple Oil Blending Model - Version 6 }

{ In this model we have restricted the availability of each component }

{ Note that, rather than representing PROPORTIONS of the blend, the }
{ component variables now represent actual QUANTITIES. The total    }
{ quantity of the blend required is 200 units. We have adjusted the }
{ constraints to account for this }


TITLE Simple_Oil_Blending_Model_V6 ;

MIN  OBJ =   25.0 LGO + 22.0 HGO + 20.0 WAXD + 15.0 ARES + 12.0 VRES ;

SUBJECT TO

SGRAV :       0.83 LGO  + 0.88 HGO  + 0.92 WAXD
            + 0.97 ARES + 1.03 VRES - 200.0 ACTUALSG
            = 0.0;

VBI :         15.0 LGO + 26.0 HGO + 30.0 WAXD
            + 40.0 ARES + 48.0 VRES - 200.0 ACTUALVI
            = 0.0 ;

SULPHUR:      1.0 LGO + 2.2 HGO + 2.8 WAXD
            + 4.1 ARES + 5.0 VRES - 200.0 ACTUALSU
            = 0.0 ;


MBALANCE:     1.0 LGO  + 1.0 HGO + 1.0 WAXD
            + 1.0 ARES + 1.0 VRES
            = 200.0 ;

BOUNDS

            ACTUALSG <= 0.98 ;
            ACTUALVI <= 37.0 ;
            ACTUALSU <= 3.7 ;
            LGO <= 20.0 ;
            HGO <= 50.0 ;
            WAXD <= 40.0 ;
            ARES <= 200.0 ;
            VRES <= 100.0 ;
END


MPS Format

In this format it is actually quite comprehensible. But consider how meaningful it would have been if there had been 30 component materials or if the model had been buried as a fragment within a larger matrix. Worse, consider how it would have appeared if it had been expresed in the industry-standard MPS format:

Fig 2: MPS Matrix - Minimise Cost of Blend

NAME          SIMPLE
ROWS
  N OBJ
  E SGRAV
  E VBI
  E SULPHUR
  E MBALANCE
COLUMNS
    LGO       OBJ               25.0   SGRAV             0.83
    LGO       VBI               15.0   SULPHUR            1.0
    LGO       MBALANCE           1.0
    HGO       OBJ               22.0   SGRAV             0.88
    HGO       VBI               26.0   SULPHUR            2.2
    HGO       MBALANCE           1.0
    WAXD      OBJ               20.0   SGRAV             0.92
    WAXD      VBI               30.0   SULPHUR            2.8
    WAXD      MBALANCE           1.0
    ARES      OBJ               15.0   SGRAV             0.97
    ARES      VBI               40.0   SULPHUR            4.1
    ARES      MBALANCE           1.0
    VRES      OBJ               12.0   SGRAV             1.03
    VRES      VBI               48.0   SULPHUR            5.0
    VRES      MBALANCE           1.0
    ACTUALSG  SGRAV           -200.0
    ACTUALVI  VBI             -200.0
    ACTUALSU  SULPHUR         -200.0
RHS
    RHS1      MBALANCE         200.0
BOUNDS
 UP BOUND1    LGO               20.0
 UP BOUND1    HGO               50.0
 UP BOUND1    WAXD              40.0
 UP BOUND1    ARES             200.0
 UP BOUND1    VRES             100.0
 UP BOUND1    ACTUALSG          0.98
 UP BOUND1    ACTUALVI          37.0
 UP BOUND1    ACTUALSU           3.7
ENDATA

Bizarre though it may seem, this is the format which is universally recognised: individual LP codes may have their own formats (such as Turbo Simplex's, which is what we have been using), but every LP code will read MPS format.

Why is MPS format so unhelpful? Because it was designed for IBM's MPS LP code in the early 1960s and the LP community had got so used to the structure of LP matrices in the LP codes of the 1950s that they weren't prepared to accept significant change. The bulk of the information appears in the section headed COLUMNS, where a list is given for each column of the rows in which it has non-zero coefficients and those coefficients. This structure happens to be the one which is the most natural for the LP code to process. It was very important to have the matrix in this format in the 1950s because computers had very little memory (typically 8k) and so could not hold the entire problem in core. They used magnetic tape as backing store and had to update the inverse by reading from and writing to backing store. A sequential structure based on columns was essential.


Improving the Formulation

Even using the relatively meaningful Turbo Simplex format, consider how much typing is involved in making changes to the matrix or in performing algebraic manipulations. Suppose that we wish to increase the total quantity of HFO which we are to blend from 200 to 250. We must then change the number "200" to "250" in each of the four constraints. If we don't make the change consistently, the matrix will no longer represent our true problem. It will still have an optimal solution, which we will be inclined to believe is the optimum solution to our problem. But it won't be, because the matrix is wrong.

We might consider modifying the structure of the matrix in order to reduce the opportunities for making mistakes when changing the data. We could do this by eliminating the decision variables ACTUALSG, ACTUALVI and ACTUALSU from the matrix. Our new matrix is shown in Fig 3.

Fig 3: Revised Turbo Simplex Matrix - Minimise Cost of Blend

{ Simple Oil Blending Model - Version 7 }

{ In this model we have eliminated the ACTUALSG, ACTUALVI and ACTUALSU }
{ variables by modifying the quality constraints. The total quantity  }
{ of the blend required remains 200 units.                            }

TITLE Simple_Oil_Blending_Model_V7 ;

MIN  OBJ =  25.0 LGO + 22.0 HGO + 20.0 WAXD + 15.0 ARES + 12.0 VRES ;

SUBJECT TO

SGRAV :       0.83 LGO  + 0.88 HGO  + 0.92 WAXD
            + 0.97 ARES + 1.03 VRES
            <= 0.98 (LGO + HGO + WAXD + ARES + VRES);

VBI :         15.0 LGO + 26.0 HGO + 30.0 WAXD
            + 40.0 ARES + 48.0 VRES
            <= 37.0 (LGO + HGO + WAXD + ARES + VRES);

SULPHUR:      1.0 LGO + 2.2 HGO + 2.8 WAXD
            + 4.1 ARES + 5.0 VRES
            <= 3.7 (LGO + HGO + WAXD + ARES + VRES);


MBALANCE:     1.0 LGO  + 1.0 HGO + 1.0 WAXD
            + 1.0 ARES + 1.0 VRES
            = 200.0 ;

BOUNDS

            LGO <= 20.0 ;
            HGO <= 50.0 ;
            WAXD <= 40.0 ;
            ARES <= 200.0 ;
            VRES <= 100.0 ;
END

The optimal values of the decision variables are the same as in the previous version, as are the reduced costs. But the shadow price of the MBALANCE row is different. Why should this be? The MBALANCE row itself has not changed, but the shadow price has altered from -30.1053 to -16.4737.

The answer is quite subtle, but it is also important, particularly if we are to make use of the marginal information which an optimal solution provides.

Recall how we defined a shadow price. We said that it was the marginal change to the objective function per unit increase in the right hand side of the constraint. If we increase the right hand side of the MBALANCE row by 1 in Version 7 of the matrix, it means that we must make an additional 1 unit of HFO and the qualities of that additional 1 unit must be SG ≤ 0.98; VBI ≤ 37.0; SUL ≤ 3.7. This is because our new quality constraints work correctly whatever the total quantity of HFO made, i.e. whatever the sum (LGO + HGO + WAXD + ARES + VRES).

Contrast this with Version 6 of the matrix. There we require that when we produce 201 units of HFO, the value of ACTUALSG must still be less than 0.98, and similarly for the other qualities. But the coefficient of ACTUALSG in the SGRAV row is still 200 while the sum (LGO + HGO + WAXD + ARES + VRES) now equals 201. Thus the name for the decision variable ACTUALSG is deceiving us. When we increase the right hand side of the MBALANCE row by 1 we are actually requiring the SG of the blend to be less than 0.98 * 200 / 201 = 0.975.

It is because the quality constraints become tighter as we increase the right hand side of the BALANCE row that the marginal cost of doing this in version 6 of the matrix is 30.1 units rather than the 16.5 with version 7.

In a very real sense, version 7 of the matrix is a better formulation than version 6: the marginal information is more useful, meaning what we would hope it to mean. It is also better for another reason: if the quality data render the problem infeasible, the LP code will be obliged to violate a quality constraint when producing an infeasible solution rather than "cheating" by violating the MBALANCE row. This is because the quality constraints apply whatever the quantity of HFO is which the model happens to make.

previous contents next

Comments