| The LP Procedure |
Example 3.7: Goal-Programming a Product Mix Problem
This example shows how to use PROC LP to solve a linear goal-programming 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
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 right-hand-side 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 right-hand-side variable determines the priority, not the order, in the data set.
Because this example is set in the formal goal-programming 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 3.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.
The LP Procedure
Problem Summary
Objective Function Min profit
Rhs Variable _rhs_
Type Variable _type_
Problem Density (%) 45.83
Variables Number
Non-negative 8
Total 8
Constraints Number
EQ 3
Objective 3
Total 6
|
The LP Procedure
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 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 LP Procedure
Variable Summary
Variable Reduced
Col Name Status Type Price Activity Cost
1 latex BASIC NON-NEG 0 4 0
2 enamel NON-NEG 0 0 50
3 n1 NON-NEG 0 0 10
4 n2 BASIC NON-NEG 1 600 0
5 n3 BASIC NON-NEG 0 7 0
6 p1 DEGEN NON-NEG 0 0 0
7 p2 NON-NEG 0 0 1
8 p3 ALTER NON-NEG 0 0 0
|
The LP Procedure
Constraint Summary
Constraint S/S Dual
Row Name Type Col Rhs Activity 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
|
The LP Procedure
Problem Summary
Objective Function Min enamel
Rhs Variable _rhs_
Type Variable _type_
Problem Density (%) 45.83
Variables Number
Non-negative 8
Total 8
Constraints Number
EQ 3
Objective 3
Total 6
|
The LP Procedure
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 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 LP Procedure
Variable Summary
Variable Reduced
Col Name Status Type Price Activity Cost
1 latex BASIC NON-NEG 0 4 0
2 enamel DEGEN NON-NEG 0 0 0
3 n1 NON-NEG 0 0 0.2
4 n2 BASIC NON-NEG 0 600 0
5 n3 BASIC NON-NEG 1 7 0
6 p1 DEGEN NON-NEG 0 0 0
7 p2 NON-NEG 0 0 0.02
8 p3 NON-NEG 0 0 1
|
The LP Procedure
Constraint Summary
Constraint S/S Dual
Row Name Type Col Rhs Activity 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.
Copyright © 2008 by SAS Institute Inc., Cary, NC, USA. All rights reserved.