Example 3.1: An Oil Blending Problem

The LP Procedure

Example 3.1: An Oil Blending Problem

The blending problem presented in the introduction is a good example for demonstrating some of the features of the LP procedure. Recall that a step in refining crude oil into finished oil products involves a distillation process that splits crude into various streams. Suppose that there are three types of crude available: Arabian light, Arabian heavy, and Brega. These are distilled into light naphtha, intermediate naphtha, and heating oil. Using one of two recipes, these in turn are blended into jet fuel.

Assume that you can sell as much fuel as is produced. What production strategy maximizes the profit from jet fuel sales? The following SAS code demonstrates a way of answering this question using linear programming. The SAS data set is a representation of the formulation for this model given in the introductory section.

   data;
      input _row_ $14.
            a_light a_heavy brega naphthal naphthai heatingo jet_1
            jet_2  _type_ $ _rhs_;
      datalines;
   profit           -175 -165 -205   0  0  0  300  300  max     .
   naphtha_l_conv   .035 .030 .045  -1  0  0   0    0   eq      0
   naphtha_i_conv   .100 .075 .135   0 -1  0   0    0   eq      0
   heating_o_conv   .390 .300 .430   0  0 -1   0    0   eq      0
   recipe_1            0    0    0   0 .3 .7  -1    0   eq      0
   recipe_2            0    0    0  .2  0 .8   0   -1   eq      0
   available         110  165   80  .  .  .   .    .   upperbd .
   ;
   proc lp;
   run;

The _ROW_ variable contains the names of the rows in the model; the variables A_LIGHT to JET_2 are the names of the structural variables in the model; the _TYPE_ variable contains the keywords that tell the LP procedure how to interpret each row in the model; and the _RHS_ variable gives the value of the right-hand-side constants.

The structural variables are interpreted as the quantity of each type of constituent or finished product. For example, the value of A_HEAVY in the solution is the amount of Arabian heavy crude to buy while the value of JET_1 in the solution is the amount of recipe 1 jet fuel that is produced. As discussed previously, the values given in the model data set are the technological coefficients whose interpretation depends on the model. In this example, the coefficient -175 in the PROFIT row for the variable A_LIGHT gives a cost coefficient (because the row with_ROW_=PROFIT has _TYPE_=MAX) for the structural variable A_LIGHT. This means that for each unit of Arabian heavy crude purchased, a cost of 175 units is incurred.

The coefficients 0.035, 0.100, and 0.390 for the A_LIGHT variable give the percentages of each unit of Arabian light crude that is distilled into the light naphtha, intermediate naphtha, and heating oil components. The 110 value in the row _ROW_=AVAILABLE gives the quantity of Arabian light that is available.

PROC LP produces the following Problem Summary output. Included in the summary is an identification of the objective, defined by the first observation of the problem data set; the right-hand-side variable, defined by the variable _RHS_; and the type identifier, defined by the variable _TYPE_. See Output 3.1.1.

Output 3.1.1: Problem Summary for the Oil Blending Problem

The LP Procedure

Problem Summary
Objective Function	Max profit
Rhs Variable	_rhs_
Type Variable	_type_
Problem Density (%)	45.00

Variables	Number

Non-negative	5
Upper Bounded	3

Total	8

Constraints	Number

EQ	5
Objective	1

Total	6

The next section of output (Output 3.1.2) contains the Solution Summary, which indicates whether or not an optimal solution was found. In this example, the procedure terminates successfully (with an optimal solution), with 1544 as the value of the objective function. Also included in this section of output is the number of phase 1 and phase 2 iterations, the number of variables used in the initial basic feasible solution, and the time used to solve the problem. For several options specified in the PROC LP statement, the current option values are also displayed.

Output 3.1.2: Solution Summary for the Oil Blending Problem

The LP Procedure

Solution Summary
Terminated Successfully
Objective Value	1544

Phase 1 Iterations	0
Phase 2 Iterations	7
Phase 3 Iterations	0
Integer Iterations	0
Integer Solutions	0
Initial Basic Feasible Variables	2
Time Used (seconds)	0
Number of Inversions	2

Epsilon	1E-8
Infinity	1.797693E308
Maximum Phase 1 Iterations	100
Maximum Phase 2 Iterations	100
Maximum Phase 3 Iterations	99999999
Maximum Integer Iterations	100
Time Limit (seconds)	120

The next section of output (Output 3.1.3) contains the Variable Summary. A line is displayed for each variable in the mathematical program with the variable name, the status of the variable in the solution, the type of variable, the variable's price coefficient, the activity of the variable in the solution, and the reduced cost for the variable. The status of a variable can be

BASIC: if the variable is a basic variable in the solution
DEGEN: if the variable is a basic variable whose activity is at its input lower bound
ALTER: if the variable is nonbasic and is basic in an alternate optimal solution
LOWBD: if the variable is nonbasic and is at its lower bound
UPPBD: if the variable is nonbasic and is at its upper bound

The TYPE column shows how PROC LP interprets the variable in the problem data set. Types include the following:

NON-NEG: if the variable is a nonnegative variable with lower bound 0 and upper bound +INFINITY
LOWERBD: if the variable has a lower bound specified in a LOWERBD observation and upper bound +INFINITY
UPPERBD: if the variable has an upper bound that is less than +INFINITY and lower bound 0 This upper bound is specified in an UPPERBD observation
UPLOWBD: if the variable has a lower bound specified in a LOWERBD observation and an upper bound specified in an UPPERBD observation
INTEGER: if the variable is constrained to take integer values. If this is the case, then it must also be upper and lower bounded
BINARY: if the variable is constrained to take value 0 or 1
UNRSTRCT: if the variable is an unrestricted variable having bounds of -INFINITY and +INFINITY
SLACK: if the variable is a slack variable that PROC LP has appended to a LE constraint. For variables of this type, the variable name is the same as the name of the constraint (given in the ROW variable) for which this variable is the slack. A nonzero slack variable indicates that the constraint is not tight. The slack is the amount by which the right-hand side of the constraint exceeds the left-hand side.
SURPLUS: if the variable is a surplus variable that PROC LP has appended to a GE constraint. For variables of this type, the variable name is the same as the name of the constraint (given in the ROW variable) for which this variable is the surplus. A nonzero surplus variable indicates that the constraint is not tight. The surplus is the amount by which the left-hand side of the constraint exceeds the right-hand side.

The Variable Summary gives the value of the structural variables at optimality. In this example, it tells you how to produce the jet fuel to maximize your profit. You should buy 110 units of A_LIGHT and 80 units of BREGA. These are used to make 7.45 units of NAPHTHAL, 21.8 units of NAPHTHAI, and 77.3 units of HEATINGO. These in turn are used to make 60.65 units of JET_1 using recipe 1 and 63.33 units of JET_2 using recipe 2.

Output 3.1.3: Variable Summary for the Oil Blending Problem

The LP Procedure

Variable Summary
Col	Variable Name	Status	Type	Price	Activity	Reduced Cost
1	a_light	UPPBD	UPPERBD	-175	110	11.6
2	a_heavy		UPPERBD	-165	0	-21.45
3	brega	UPPBD	UPPERBD	-205	80	3.35
4	naphthal	BASIC	NON-NEG	0	7.45	0
5	naphthai	BASIC	NON-NEG	0	21.8	0
6	heatingo	BASIC	NON-NEG	0	77.3	0
7	jet_1	BASIC	NON-NEG	300	60.65	0
8	jet_2	BASIC	NON-NEG	300	63.33	0

The reduced cost associated with each nonbasic variable is the marginal value of that variable if it is brought into the basis. In other words, the objective function value would (assuming no constraints were violated) increase by the reduced cost of a nonbasic variable if that variable's value increased by one. Similarly, the objective function value would (assuming no constraints were violated) decrease by the reduced cost of a nonbasic variable if that variable's value were decreased by one. Basic variables always have a zero reduced cost. At optimality, for a maximization problem, nonbasic variables that are not at an upper bound have nonpositive reduced costs (for example, A_HEAVY has a reduced cost of -21.45). The objective would decrease if they were to increase beyond their optimal values. Nonbasic variables at upper bounds have nonnegative reduced costs, showing that increasing the upper bound (if the reduced cost is not zero) does not decrease the objective. For a nonbasic variable at its upper bound, the reduced cost is the marginal value of increasing its upper bound, often called its shadow price.

For minimization problems, the definition of reduced costs remain the same but the conditions for optimality change. For example, at optimality the reduced costs of all non upper-bounded variables are nonnegative, and the reduced costs of upper-bounded variables at their upper bound are nonpositive.

The next section of output (Output 3.1.4) contains the Constraint Summary. For each constraint row, free row, and objective row, a line is displayed in the Constraint Summary. Included on the line are the constraint name, the row type, the slack or surplus variable associated with the row, the right-hand-side constant associated with the row, the activity of the row (not including the activity of the slack and surplus variables), and the dual activity (shadow prices).

A dual variable is associated with each constraint row. At optimality, the value of this variable, the dual activity, tells you the marginal value of the right-hand-side constant. For each unit increase in the right-hand-side constant, the objective changes by this amount. This quantity is also known as the shadow price. For example, the marginal value for the right-hand-side constant of constraint HEATING_O_CONV is -450.0.

Output 3.1.4: Constraint Summary for the Oil Blending Problem

The LP Procedure

Constraint Summary
Row	Constraint Name	Type	S/S Col	Rhs	Activity	Dual Activity
1	profit	OBJECTVE	.	0	1544	.
2	naphtha_l_conv	EQ	.	0	0	-60
3	naphtha_i_conv	EQ	.	0	0	-90
4	heating_o_conv	EQ	.	0	0	-450
5	recipe_1	EQ	.	0	0	-300
6	recipe_2	EQ	.	0	0	-300

Chapter Contents
Previous
Next
Top