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 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` 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.
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 }` 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 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 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. |

LP Training > 3. Algebraic Formulation >