基石

一、互补松弛性的数学证明#

线性规划标准形式原问题(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)$ ),即对应变量互补为零。

下面对定理进行证明:

1. 必要性:若 $\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$ ,必要性得证。
2. 充分性:设 $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。

综上,影子价格本质是资源的“边际贡献价值”,其数值大小直接反映了资源的稀缺程度,为企业资源配置决策提供了量化依据。