The LP Procedure 
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_ $17. 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 . ;
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 righthandside 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 righthandside variable, defined by the variable _RHS_; and the type identifier, defined by the variable _TYPE_. See Output 5.1.1.
Problem Summary  

Objective Function  Max profit 
Rhs Variable  _rhs_ 
Type Variable  _type_ 
Problem Density (%)  45.00 
Variables  Number 
Nonnegative  5 
Upper Bounded  3 
Total  8 
Constraints  Number 
EQ  5 
Objective  1 
Total  6 
The next section of output (Output 5.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.
Solution Summary  

Terminated Successfully 

Objective Value  1544 
Phase 1 Iterations  0 
Phase 2 Iterations  4 
Phase 3 Iterations  0 
Integer Iterations  0 
Integer Solutions  0 
Initial Basic Feasible Variables  5 
Time Used (seconds)  0 
Number of Inversions  3 
Epsilon  1E8 
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 5.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:
NONNEG 
if the variable is a nonnegative variable with lower bound 0 and upper bound . 
LOWERBD 
if the variable has a lower bound specified in a LOWERBD observation and upper bound . 
UPPERBD 
if the variable has an upper bound that is less than 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. 
UNRSTRT 
if the variable is an unrestricted variable having bounds of and . 
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 righthand side of the constraint exceeds the lefthand 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 lefthand side of the constraint exceeds the righthand 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.
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  NONNEG  0  7.45  0 
5  naphthai  BASIC  NONNEG  0  21.8  0 
6  heatingo  BASIC  NONNEG  0  77.3  0 
7  jet_1  BASIC  NONNEG  300  60.65  0 
8  jet_2  BASIC  NONNEG  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 remains the same but the conditions for optimality change. For example, at optimality the reduced costs of all nonupperbounded variables are nonnegative, and the reduced costs of upperbounded variables at their upper bound are nonpositive.
The next section of output (Output 5.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 righthandside 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 righthandside constant. For each unit increase in the righthandside constant, the objective changes by this amount. This quantity is also known as the shadow price. For example, the marginal value for the righthandside constant of constraint HEATING_O_CONV is 450.
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 
Copyright © SAS Institute, Inc. All Rights Reserved.