一、互补松弛性的数学证明 #
线性规划标准形式原问题(LP)与对偶问题(DP)定义如下:
原问题(LP):
$$LP: max z=C X$$$$s.t. \begin{cases}A X+X_{s}=b \\ X \geq 0, X_{s} \geq 0\end{cases} (X_{s} 为松弛变量 )$$
对偶问题(DP):
$$DP: min w=Y^{T} b$$$$s.t. \begin{cases}A^{T} Y-Y_{s}=C^{T} \\ Y \geq 0, Y_{s} \geq 0\end{cases} ( Y_{s} 为剩余变量 )$$
互补松驰性:设 \(\hat{X}\) (LP 可行解)、\(\hat{Y}\) (DP 可行解),则两者为最优解的充要条件为:
$$Y_{s}^{T} \hat{X}=0$$且
$$\hat{Y}^{T} X_{s}=0$$等价表述: \(\hat{x}_{j} \hat{y}_{m+j}=0(j=1, \cdots, n)\) 且 \(\hat{x}_{n+i} \hat{y}_{i}=0(i=1, \cdots, m)\) ,即对应变量互补为零。
下面对定理进行证明:
- 必要性:
若 \(\hat{X}\) 、\(\hat{Y}\) 为最优解,由强对偶性得 \(C \hat{X}=\hat{Y}^{T} b\)
由DP 约束得 \(C=\hat{Y}^{T} A-Y_{s}^{T}\) ,
代入 \(LP\) 目标函数得 \(C \hat{X}=\hat{Y}^{T} A \hat{X}-Y_{s}^{T} \hat{X}\)
由LP 约束得 \(b=A \hat{X}+X_{s}\) ,
代入DP 目标函数得 \(\hat{Y}^{T} b=\hat{Y}^{T} A \hat{X}+\hat{Y}^{T} X_{s}\)
联立消去公共项得 \(-Y_{s}^{T} \hat{X}=\hat{Y}^{T} X_{s}\) ,因变量非负,
故 \(Y_{s}^{T} \hat{X}=0\) 且 \(\hat{Y}^{T} X_{s}=0\) ,必要性得证。
- 充分性:
设 \(Y_{S}^{T} \hat{X}=0\) 且 \(\hat{Y}^{T} X_{s}=0\) ,结合目标函数变形推导。
代入变形公式得 \(C \hat{X}=\hat{Y}^{T} A \hat{X}\) 且 \(\hat{Y}^{T} b=\hat{Y}^{T} A \hat{X}\) ,
故 \(C \hat{X}=\hat{Y}^{T} b\) 由最优性判定定理, \(\hat{X}\) 、\(\hat{Y}\) 分别为两问题最优解,充分性得证
二、影子价格的定义 #
影子价格,又称边际价值,是指在线性规划问题的最优解状态下,某一约束条件所对应资源的单位增量对目标函数最优值产生的增量。其数学载体为线性规划对偶问题的最优解 \(\hat{Y}\)。
结合前文对偶问题的定义
$$DP: min w=Y^{T}b$$约束
$$s.t. \begin{cases}A^{T} Y-Y_{s}=C^{T} \\ Y \geq 0, Y_{s} \geq 0\end{cases}$$及互补松弛性质核心结论( \(\hat{Y}^{T} X_{s}=0\) ),
影子价格的内涵可进一步明晰:
若原问题最优基为 B ,则影子价格向量可表示为 \(\hat{Y}^{T}=C_{B} B^{-1}\) (其中 \(C_{B}\) 为最优基对应的目标函数系数向量)。
从数学逻辑推导,原问题最优目标函数值
$$z^{*}=C_{B} B^{-1} b=\hat{Y}^{T} b$$对资源总量 \(b_{i}\) 求偏导可得
$$\frac{\partial z^{*}}{\partial b_{i}}=\hat{y}_{i}^{*}$$这一结果恰好印证了影子价格的定义,即第 i 种资源(对应 \(b_{i}\) )每增加一个单位,目标函数最优值(如最大利润、最小成本)的增量。
在对偶问题的经济背景,影子价格可理解为企业对资源的“内部估价”: 若企业将资源对外租赁,影子价格即为保证租赁收益不低于生产收益的最低租赁单价,且在该定价下总租赁费用最低。
从互补松弛性质视角,影子价格与原问题松弛变量满足 \(\hat{Y}^{T} X_{s}=0\) ,其直观对应关系如下:
- 若某资源影子价格 \(\hat{y}_{i}>0\) ,则对应松弛变量 \(\hat{x}_{n+i}=0\) ,表明该资源已被完全利用(紧约束),是生产瓶颈,增加该资源可提升最优收益;
- 若某资源存在剩余( \(\hat{x}_{n+i}>0\) ),则其影子价格 \(\hat{y}_{i}=0\) ,表明增加该资源无法改变最优收益,此时减少资源投入或对外出售资源可能更有利。 影子价格具有针对性,随企业生产产品、工艺及资源约束的不同而变化,其经济意义需结合具体线性规划问题的背景确定。
三、在实际例子中的分析 #
3.1 问题描述
某企业计划生产甲、乙两种产品,需在A、B、C三种设备上加工,核心约束与收益参数如下:
设备工时约束:设备A计划期工时限额6小时,甲、乙产品单位加工工时均为1小时;设备B计划期工时限额8小时,甲、乙产品单位加工工时均为2小时;设备C计划期工时限额6小时,仅乙产品单位加工工时为2小时(甲产品不耗用);
收益参数:甲产品单位利润3百元/件,乙产品单位利润4百元/件;
决策目标:合理安排甲、乙产品产量,实现企业利润最大化;同时通过对偶问题求解影子价格,结合互补松弛性分析资源配置状态。
3.2 模型建立
LP 设甲产品产量为 \(x_{1}\) (件),乙产品产量为 \(x_{2}\) (件),引入松弛变量 \(x_{s1}\) , \(x_{s2}\) , \(x_{s3}\) (分别对应设备A、B、C的剩余工时),模型如下:
$$LP: max z=3 x_{1}+4x_{2}$$$$s.t. \begin{cases}x_{1}+x_{2}+x_{s1}=6 (设备 A 工时约束) \\ 2 x_{1}+2 x_{2}+x_{s2}=8 (设备 B 工时约束) \\ 2 x_{2}+x_{s3}=6 (设备 C 工时约束) \\ x_{1}, x_{2}, x_{s1}, x_{s2}, x_{s3} \geq 0\end{cases}$$
DP 设\(y_1, y_2, y_3\)分别为设备A、B、C的影子价格(即单位工时的“内部估价”),引入剩余变量 \(y_{s1}\) , \(y_{s2}\) ,结合材料1的对偶问题构建逻辑,模型如下:
$$DP: min w=6 y_{1}+8 y_{2}+6 y_{3}$$$$s.t. \begin{cases}y_{1}+2 y_{2}-y_{s1}=3( 甲产品利润约束) \\ y_{1}+2 y_{2}+2 y_{3}-y_{s2}=4( 乙产品利润约束) \\ y_{1}, y_{2}, y_{3}, y_{s1}, y_{s2} \geq 0\end{cases}$$
对偶问题的经济意义:在保证租赁设备的收益不低于生产产品收益的前提下,最小化总租赁费用,此时最优解\(y_1^*、y_2^*、y_3^*\)即为各设备工时的影子价格。
3.3模型求解
原问题最优解:
\(x_{1}^{*}=1\) (件), \(x_{2}^{*}=3\) (件),
松弛变量
\(x_{s1}^{*}=6-(1+3)=2>0\) , \(x_{s2}^{*}=8-(2 ×1+2 ×3)=0\) , \(x_{s3}^{*}=6-(2 ×3)=0\)
最优利润
\(z^{*}=3 ×1+4 ×3=15\) (百元);
对偶问题最优解:
\(y_{1}^{*}=0\) , \(y_{2}^{*}=1.5\) , \(y_{3}^{*}=0.5\) ,
剩余变量
\(y_{s1}^{*}=0\) , \(y_{s2}^{*}=0\) ;
最优目标值
\(w^{*}=6 ×0+8 ×1.5+6 ×0.5=15\) (百元),满足 \(z^{*}=w^{*}\) (强对偶性成立)。
设备A影子价格 \(y_{1}^{*}=0\) :
表明在最优生产方案下,设备A的工时存在剩余 (\(x_{s1}^{*}=2>0\) ),每增加1小时设备A工时,企业最大利润无增量。
从决策角度,设备A并非生产瓶颈,无需追加该设备资源投入,甚至可考虑闲置工时对外租赁(租赁单价低于市场同类价格即可);
设备B影子价格 \(y_{2}^{*}=1.5\) :
表明设备B工时已完全耗用( \(x_{s2}^{*}=0\) ),每增加1小时设备B工时,企业最大利润将增加1.5百元(150元)。
设备B是核心瓶颈资源,若市场上该类设备租赁单价低于150元/小时,追加租赁投入可提升企业收益;
设备C影子价格 \(y_{3}^{*}=0.5\) :
表明设备C工时已完全耗用( \(x_{s3}^{*}=0\) ),每增加1小时设备C工时,企业最大利润将增加0.5百元(50元)。
设备C是次瓶颈资源,追加投入的性价比低于设备B。
综上,影子价格本质是资源的“边际贡献价值”,其数值大小直接反映了资源的稀缺程度,为企业资源配置决策提供了量化依据。