線形計画法における感度解析
linprog の "dual-simplex-highs" アルゴリズムは 6 番目の出力で感度情報を返します。感度情報は、問題のパラメーターに対する目的関数値の変化率、および同じ変化率になるパラメーターの変化の範囲です。
線形計画法を作成して解いてから、感度情報を調べ、ラグランジュ乗数の情報と比較します。
load sc50b.matこの問題には 48 の変数、30 の不等式、20 の等式があります。
disp(size(A))
30 48
disp(size(Aeq))
20 48
この問題に上限はないため、ub を [] に設定します。
ub = [];
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]
下限の係数の感度を調べます。
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
⋮
ObjectiveValueChangeRate がすべての行でゼロであり、lb を変更しても得られる目的値 (–70) は変わらないことを示しています。この結論は lambda.lower のデータにも反映されています。
lambda.lower
ans = 48×1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
⋮
線形等式制約に対する感度を調べます。
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
⋮
sensitivity.EqualityRHS の右端の列を lambda.eqlin の出力と比較します。
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
⋮
それらのベクトルの絶対値は等しくなっています。ただし、ラグランジュ乗数に比べて感度情報の方が、線形等式の係数 beq を変更した場合に目的値がどのように変わるかを判断するためのより明確な結果が得られます。
beq(1) を現在の値に 1 を加えた値に設定してみます。ObjectiveValueChangeRate は –0.1750 であるため、目的関数値が –70 から –70.1750 に変わると予測できます。
beq(1) = beq(1) + 1; [x,fval] = linprog(f,A,b,Aeq,beq,lb,ub);
Optimal solution found.
fval
fval = -70.1750
