Sensitivity Analysis in Linear Programming
The linprog "dual-simplex-highs" algorithm returns sensitivity information in the sixth output. The sensitivity information is the rate of change in objective function value with respect to problem parameters, and the extent of the changes in parameters that give the same rate of change.
Create and solve a linear program, then examine the sensitivity information and compare it to the Lagrange multiplier information.
load sc50b.matThe problem has 48 variables, 30 inequalities, and 20 equalities.
disp(size(A))
30 48
disp(size(Aeq))
20 48
The problem has no upper bound, so set ub to [].
ub = [];
Solve the problem by calling linprog.
[x,fval,exitflag,output,lambda,sensitivity] = ...
linprog(f,A,b,Aeq,beq,lb,ub)Optimal solution found.
x = 48×1
30.0000
28.0000
42.0000
70.0000
70.0000
30.0000
28.0000
42.0000
30.0000
28.0000
42.0000
33.0000
30.8000
46.2000
77.0000
⋮
fval = -70.0000
exitflag = 1
output = struct with fields:
iterations: 17
constrviolation: 5.6843e-14
message: 'Optimal solution found.'
algorithm: 'dual-simplex-highs'
firstorderopt: 2.4869e-15
lambda = struct with fields:
lower: [48×1 double]
upper: [48×1 double]
eqlin: [20×1 double]
ineqlinLower: [30×1 double]
ineqlin: [30×1 double]
sensitivity =
SensitivityAnalysis with properties:
Variables Sensitivity:
ObjectiveCoefficient: [48×5 table]
LowerBound: [48×5 table]
UpperBound: [48×5 table]
Constraints Sensitivity:
InequalityLHS: [30×5 table]
InequalityRHS: [30×5 table]
EqualityRHS: [20×5 table]
Examine the sensitivity for the lower bound coefficients.
sensitivity.LowerBound
ans=48×5 table
LowerLimit UpperLimit ObjectiveValueAtLowerLimit ObjectiveValueAtUpperLimit ObjectiveValueChangeRate
__________ __________ __________________________ __________________________ ________________________
-Inf 30 -70 -70 0
-Inf 28 -70 -70 0
-Inf 42 -70 -70 0
-Inf 70 -70 -70 0
-Inf 70 -70 -70 0
-Inf 30 -70 -70 0
-Inf 28 -70 -70 0
-Inf 42 -70 -70 0
-Inf 30 -70 -70 0
-Inf 28 -70 -70 0
-Inf 42 -70 -70 0
-Inf 33 -70 -70 0
-Inf 30.8 -70 -70 0
-Inf 46.2 -70 -70 0
-Inf 77 -70 -70 0
-Inf 147 -70 -70 0
⋮
The ObjectiveValueChangeRate is zero in every row, which means that the resulting objective value (–70) will not change if you change lb. This conclusion is also reflected in the lambda.lower data.
lambda.lower
ans = 48×1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
⋮
Examine the sensitivity with respect to the linear equality constraints.
sensitivity.EqualityRHS
ans=20×5 table
LowerLimit UpperLimit ObjectiveValueAtLowerLimit ObjectiveValueAtUpperLimit ObjectiveValueChangeRate
__________ __________ __________________________ __________________________ ________________________
-36.364 84.848 -63.636 -84.848 -0.175
-36.364 171.43 -63.636 -100 -0.175
-36.364 30.108 -63.636 -75.269 -0.175
-36.364 46.927 -63.636 -78.212 -0.175
-93.333 40 0 -100 -0.75
-40.647 89.993 -64.665 -81.812 -0.13125
-92.562 175.42 -57.851 -93.023 -0.13125
-40.647 32.688 -64.665 -74.29 -0.13125
-40.647 50.582 -64.665 -76.639 -0.13125
-124.44 40.93 0 -93.023 -0.5625
-45.316 96.153 -65.539 -79.465 -0.098437
-176.84 182.46 -52.592 -87.96 -0.098437
-45.316 35.575 -65.539 -73.502 -0.098437
-45.316 54.731 -65.539 -75.388 -0.098437
-165.93 42.573 -4.2633e-14 -87.96 -0.42187
-50.409 103.32 -66.278 -77.628 -0.073828
⋮
Compare the rightmost column of sensitivity.EqualityRHS to the lambda.eqlin output.
lambda.eqlin
ans = 20×1
0.1750
0.1750
0.1750
0.1750
0.7500
0.1312
0.1312
0.1312
0.1312
0.5625
0.0984
0.0984
0.0984
0.0984
0.4219
⋮
The absolute values of these vectors are equal. However, compared to the Lagrange multiplier, the sensitivity information gives a clearer result for determining how the objective value will change if you change the value of the linear equality coefficient beq.
Try setting beq(1) to its current value plus 1. Because the ObjectiveValueChangeRate is –0.1750, you can expect the objective function value to change from –70 to –70.1750.
beq(1) = beq(1) + 1; [x,fval] = linprog(f,A,b,Aeq,beq,lb,ub);
Optimal solution found.
fval
fval = -70.1750
