The LP Procedure

Example 5.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

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 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 5.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 5.7.1: Goal Programming

The LP Procedure

Problem Summary
Objective Function	Min overtime
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

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	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

Variable Summary
Col	Variable Name	Status	Type	Price	Activity	Reduced Cost
1	latex	ALTER	NON-NEG	0	0	0
2	enamel	ALTER	NON-NEG	0	0	0
3	n1	BASIC	NON-NEG	0	40	0
4	n2	BASIC	NON-NEG	0	1000	0
5	n3	BASIC	NON-NEG	0	7	0
6	p1		NON-NEG	1	0	1
7	p2	ALTER	NON-NEG	0	0	0
8	p3	ALTER	NON-NEG	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

Non-negative	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	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

Variable Summary
Col	Variable Name	Status	Type	Price	Activity	Reduced 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

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

Non-negative	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	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

Variable Summary
Col	Variable Name	Status	Type	Price	Activity	Reduced 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

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.