This example shows how to use PROC LP to solve a linear goalprogramming problem. PROC LP has the ability to solve a series of linear programs, each with a new objective function. These objective functions are ordered by priority. The first step is to solve a linear program with the highest priority objective function constrained only by the formal constraints in the model. Then, the problem with the next highest priority objective function is solved, constrained by the formal constraints in the model and by the value that the highest priority objective function realized. That is, the second problem optimizes the second highest priority objective function among the alternate optimal solutions to the first optimization problem. The process continues until a linear program is solved for each of the objectives.
This technique is useful for differentiating among alternate optimal solutions to a linear program. It also fits into the formal paradigm presented in goal programming. In goal programming, the objective functions typically take on the role of driving a linear function of the structural variables to meet a target level as closely as possible. The details of this can be found in many books on the subject, including Ignizio (1976).
Consider the following problem taken from Ignizio (1976). A small paint company manufactures two types of paint, latex and enamel. In production, the company uses 10 hours of labor to produce 100 gallons of latex and 15 hours of labor to produce 100 gallons of enamel. Without hiring outside help or requiring overtime, the company has 40 hours of labor available each week. Furthermore, each paint generates a profit at the rate of $1.00 per gallon. The company has the following objectives listed in decreasing priority:
avoid the use of overtime
achieve a weekly profit of $1000
produce at least 700 gallons of enamel paint each week
The program to solve this problem follows.
data object; input _row_ $ latex enamel n1 n2 n3 p1 p2 p3 _type_ $ _rhs_; datalines; overtime . . . . . 1 . . min 1 profit . . . 1 . . . . min 2 enamel . . . . 1 . . . min 3 overtime 10 15 1 . . 1 . . eq 40 profit 100 100 . 1 . . 1 . eq 1000 enamel . 1 . . 1 . . 1 eq 7 ;
proc lp data=object goalprogram; run;
The data set called OBJECT
contains the model. Its first three observations are the objective rows, and the next three observations are the constraints.
The values in the righthandside variable _RHS_
in the objective rows give the priority of the objectives. The objective in the first observation with _ROW_
='OVERTIME' has the highest priority, the objective named PROFIT has the next highest, and the objective named ENAMEL has
the lowest. Note that the value of the righthandside variable determines the priority, not the order, in the data set.
Because this example is set in the formal goalprogramming scheme, the model has structural variables representing negative
(n1, n2
, and n3
) and positive (p1, p2
, and p3
) deviations from target levels. For example, n1+p1
is the deviation from the objective of avoiding the use of overtime and underusing the normal work time, namely using exactly
40 work hours. The other objectives are handled similarly.
Notice that the PROC LP statement includes the GOALPROGRAM option. Without this option, the procedure would solve three separate problems: one for each of the three objective functions.
In that case, however, the procedure would not constrain the second and third programs using the results of the preceding
programs; also, the values 1, 2, and 3 for _RHS_
in the objective rows would have no effect.
Output 6.7.1 shows the solution of the goal program, apparently as three linear program outputs. However, examination of the constraint summaries in the second and third problems shows that the constraints labeled by the objectives OVERTIME and PROFIT have type FIXEDOBJ. This indicates that these objective rows have become constraints in the subsequent problems.
Output 6.7.1: Goal Programming
Problem Summary  

Objective Function  Min overtime 
Rhs Variable  _rhs_ 
Type Variable  _type_ 
Problem Density (%)  45.83 
Variables  Number 
Nonnegative  8 
Total  8 
Constraints  Number 
EQ  3 
Objective  3 
Total  6 
Solution Summary  

Terminated Successfully 

Objective Value  0 
Phase 1 Iterations  2 
Phase 2 Iterations  0 
Phase 3 Iterations  0 
Integer Iterations  0 
Integer Solutions  0 
Initial Basic Feasible Variables  7 
Time Used (seconds)  0 
Number of Inversions  2 
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 
Variable Summary  

Col  Variable Name  Status  Type  Price  Activity  Reduced Cost 
1  latex  ALTER  NONNEG  0  0  0 
2  enamel  ALTER  NONNEG  0  0  0 
3  n1  BASIC  NONNEG  0  40  0 
4  n2  BASIC  NONNEG  0  1000  0 
5  n3  BASIC  NONNEG  0  7  0 
6  p1  NONNEG  1  0  1  
7  p2  ALTER  NONNEG  0  0  0 
8  p3  ALTER  NONNEG  0  0  0 
Constraint Summary  

Row  Constraint Name  Type  S/S Col  Rhs  Activity  Dual Activity 
1  overtime  OBJECTVE  .  0  0  . 
2  profit  FREE_OBJ  .  0  1000  . 
3  enamel  FREE_OBJ  .  0  7  . 
4  overtime  EQ  .  40  40  0 
5  profit  EQ  .  1000  1000  0 
6  enamel  EQ  .  7  7  0 
Problem Summary  

Objective Function  Min profit 
Rhs Variable  _rhs_ 
Type Variable  _type_ 
Problem Density (%)  45.83 
Variables  Number 
Nonnegative  8 
Total  8 
Constraints  Number 
EQ  3 
Objective  3 
Total  6 
Solution Summary  

Terminated Successfully 

Objective Value  600 
Phase 1 Iterations  0 
Phase 2 Iterations  3 
Phase 3 Iterations  0 
Integer Iterations  0 
Integer Solutions  0 
Initial Basic Feasible Variables  7 
Time Used (seconds)  0 
Number of Inversions  5 
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 
Variable Summary  

Col  Variable Name  Status  Type  Price  Activity  Reduced Cost 
1  latex  BASIC  NONNEG  0  4  0 
2  enamel  NONNEG  0  0  50  
3  n1  NONNEG  0  0  10  
4  n2  BASIC  NONNEG  1  600  0 
5  n3  BASIC  NONNEG  0  7  0 
6  p1  DEGEN  NONNEG  0  0  0 
7  p2  NONNEG  0  0  1  
8  p3  ALTER  NONNEG  0  0  0 
Constraint Summary  

Row  Constraint Name  Type  S/S Col  Rhs  Activity  Dual Activity 
1  overtime  FIXEDOBJ  .  0  0  . 
2  profit  OBJECTVE  .  0  600  . 
3  enamel  FREE_OBJ  .  0  7  . 
4  overtime  EQ  .  40  40  10 
5  profit  EQ  .  1000  1000  1 
6  enamel  EQ  .  7  7  0 
Problem Summary  

Objective Function  Min enamel 
Rhs Variable  _rhs_ 
Type Variable  _type_ 
Problem Density (%)  45.83 
Variables  Number 
Nonnegative  8 
Total  8 
Constraints  Number 
EQ  3 
Objective  3 
Total  6 
Solution Summary  

Terminated Successfully 

Objective Value  7 
Phase 1 Iterations  0 
Phase 2 Iterations  1 
Phase 3 Iterations  0 
Integer Iterations  0 
Integer Solutions  0 
Initial Basic Feasible Variables  7 
Time Used (seconds)  0 
Number of Inversions  8 
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 
Variable Summary  

Col  Variable Name  Status  Type  Price  Activity  Reduced Cost 
1  latex  BASIC  NONNEG  0  4  0 
2  enamel  DEGEN  NONNEG  0  0  0 
3  n1  NONNEG  0  0  0.2  
4  n2  BASIC  NONNEG  0  600  0 
5  n3  BASIC  NONNEG  1  7  0 
6  p1  DEGEN  NONNEG  0  0  0 
7  p2  NONNEG  0  0  0.02  
8  p3  NONNEG  0  0  1 
Constraint Summary  

Row  Constraint Name  Type  S/S Col  Rhs  Activity  Dual Activity 
1  overtime  FIXEDOBJ  .  0  0  . 
2  profit  FIXEDOBJ  .  0  600  . 
3  enamel  OBJECTVE  .  0  7  . 
4  overtime  EQ  .  40  40  0.2 
5  profit  EQ  .  1000  1000  0.02 
6  enamel  EQ  .  7  7  1 
The solution to the last linear program shows a value of 4 for the variable LATEX
and a value of 0 for the variable ENAMEL
. This tells you that the solution to the linear goal program is to produce 400 gallons of latex and no enamel paint.
The values of the objective functions in the three linear programs tell you whether you can achieve the three objectives. The activities of the constraints labeled OVERTIME, PROFIT, and ENAMEL tell you values of the three linear program objectives. Because the first linear programming objective OVERTIME is 0, the highest priority objective, which is to avoid using additional labor, is accomplished. However, because the second and third objectives are nonzero, the second and third priority objectives are not satisfied completely. The PROFIT objective is 600. Because the PROFIT objective is to minimize the negative deviation from the profit constraint, this means that a profit of only 400 = 1000 600 is realized. Similarly, the ENAMEL objective is 7, indicating that there is a negative deviation from the ENAMEL target of 7 units.