The LP Procedure

Example 5.5 Price Parametric Programming for the Oil Blending Problem

This example continues to examine the effects of a change in the cost of crude and the selling price of jet fuel. Suppose that you know the cost of ARABIAN_LIGHT crude is likely to increase 30 units, with the effects on oil and fuel prices as described in Example 5.4. The analysis in the last example only accounted for an increase of a little over 4 units (because the minimum $\phi$ was -4.15891). Because an increase in the cost of ARABIAN_LIGHT beyond 4.15891 units requires a change in the optimal basis, it may also require a change in the optimal production strategy. This type of analysis, where you want to find how the solution changes with changes in the objective function coefficients or right-hand-side vector, is called parametric programming.

You can answer this question by using the PRICEPHI= option in the PROC LP statement. The following program instructs PROC LP to continually increase the cost of the crudes and the return from jet fuel using the ratios given previously, until the cost of ARABIAN_LIGHT increases at least 30 units.

proc lp sparsedata primalin=solution pricephi=-30;
run;

The PRICEPHI= option in the PROC LP statement tells PROC LP to perform parametric programming on any price change vectors specified in the problem data set. The value of the PRICEPHI= option tells PROC LP how far to change the value of $\phi$ and in what direction. A specification of PRICEPHI=-30 tells PROC LP to continue pivoting until the problem has objective function equal to (original objective function value) $-$ 30 $\times$ (change vector).

Output 5.5.1 shows the result of this analysis. The first page is the Price Sensitivity Analysis Summary, as discussed in Example 5.4. The next page is an accounting for the change in basis as a result of decreasing $\phi$ beyond -4.1589. It shows that BREGA left the basis at an upper bound and entered the basis at a lower bound. The interpretation of these basis changes can be difficult (Hadley 1962; Dantzig 1963).

The last page of output shows the optimal solution at the displayed value of $\phi$ , namely -30.6878. At an increase of 30.6878 units in the cost of ARABIAN_LIGHT and the related changes to the other crudes and the jet fuel, it is optimal to modify the production of jet fuel as shown in the activity column. Although this plan is optimal, it results in a profit of 0. This may suggest that the ratio of a unit increase in the price of jet fuel per unit increase in the cost of ARABIAN_LIGHT is lower than desirable.

Output 5.5.1: Price Parametric Programming 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

Solution Summary
Terminated Successfully
Objective Value	1544

Phase 1 Iterations	0
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	arabian_heavy		UPPERBD	-165	0	-21.45
2	arabian_light	UPPBD	UPPERBD	-175	110	11.6
3	brega	UPPBD	UPPERBD	-205	80	3.35
4	heating_oil	BASIC	NON-NEG	0	77.3	0
5	jet_1	BASIC	NON-NEG	300	60.65	0
6	jet_2	BASIC	NON-NEG	300	63.33	0
7	naphtha_inter	BASIC	NON-NEG	0	21.8	0
8	naphtha_light	BASIC	NON-NEG	0	7.45	0

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

The LP Procedure

Price Sensitivity Analysis Summary
Sensitivity Vector change
Minimum Phi	-4.158907511
Entering Variable	brega
Optimal Objective	1103.0726257

Maximum Phi	29.72972973
Entering Variable	arabian_heavy
Optimal Objective	4695.9459459

Col	Variable Name	Status	Activity	Minimum Phi		Maximum Phi
Col	Variable Name	Status	Activity	Price	Reduced Cost	Price	Reduced Cost
1	arabian_heavy		0	-169.9907	-24.45065	-129.3243	0
2	arabian_light	UPPBD	110	-179.1589	10.027933	-145.2703	22.837838
3	brega	UPPBD	80	-211.2384	0	-160.4054	27.297297
4	heating_oil	BASIC	77.3	0	0	0	0
5	jet_1	BASIC	60.65	304.15891	0	270.27027	0
6	jet_2	BASIC	63.33	304.15891	0	270.27027	0
7	naphtha_inter	BASIC	21.8	0	0	0	0
8	naphtha_light	BASIC	7.45	0	0	0	0

The LP Procedure

Price Parametric Programming Log
Sensitivity Vector change
Leaving Variable	Entering Variable	Objective	Current Phi
brega	brega	1103.0726	-4.158908

The LP Procedure

Price Sensitivity Analysis Summary
Sensitivity Vector change
Minimum Phi	-30.68783069
Entering Variable	arabian_light
Optimal Objective	0

Col	Variable Name	Status	Activity	Minimum Phi
Col	Variable Name	Status	Activity	Price	Reduced Cost
1	arabian_heavy		0	-201.8254	-43.59127
2	arabian_light	ALTER	110	-205.6878	0
3	brega		0	-251.0317	-21.36905
4	heating_oil	BASIC	42.9	0	0
5	jet_1	BASIC	33.33	330.68783	0
6	jet_2	BASIC	35.09	330.68783	0
7	naphtha_inter	BASIC	11	0	0
8	naphtha_light	BASIC	3.85	0	0

What is the optimal return if $\phi$ is exactly -30? Because the change in the objective is linear as a function of $\phi$ , you can calculate the objective for any value of $\phi$ between those given by linear interpolation. For example, for any $\phi$ between -4.1589 and -30.6878, the optimal objective value is

$\phi \times (1103.0726-0)/(-4.1589-30.6878)+ b$

where

$b= 30.6878\times (1103.0726-0)/(-4.1589-30.6878)$

For $\phi =$ -30, this is 28.5988.