互补松弛定理作用 :

① 简化求对偶问题最优解过程 : 已知一个线性规划问题的最优解 , 可以 简化求另外一个问题最优解的过程 , 避免使用两次单纯形法求解 ;

② 影子价格问题 : 使用互补松弛定理可以进行一些 经济解释 , 如影子价格问题 ;

影子价格 是 对偶问题的 经济解释 ;

影子价格定义 :

在一对 P \rm P P 和 D \rm D D 中 ,

如果 P \rm P P 的某个 约束条件 的 右端常数项 b i \rm b_i bi​ ( 第 i \rm i i 种资源的拥有量 ) 增加一个单位时 ,

所引起 P \rm P P 目标函数 最优值 z ∗ \rm z^* z∗ 的该变量称为 第 i \rm i i 种资源的 影子价格 ,

其值等于 D \rm D D 问题 中的 对偶变量 y i ∗ \rm y_i^* yi∗​ ;

原问题 P \rm P P : m a x Z = C X s . t { A X ≤ b X ≥ 0 \begin{array}{lcl} \rm maxZ = C X \\\\ \rm s.t\begin{cases} \rm AX \leq b \\\\ \rm X \geq 0 \end{cases}\end{array} maxZ=CXs.t⎩⎪⎨⎪⎧​AX≤bX≥0​​ ;              \ \ \ \ \ \ \ \ \ \ \,            对偶问题 D \rm D D : m i n W = b T Y s . t { A T Y ≥ C T Y ≥ 0 \begin{array}{lcl} \rm minW = b^T Y \\\\ \rm s.t\begin{cases} \rm A^TY \geq C^T \\\\ \rm Y \geq 0 \end{cases}\end{array} minW=bTYs.t⎩⎪⎨⎪⎧​ATY≥CTY≥0​​

由对偶问题的基本性质得到如下结论 :

z ∗ = ∑ j = 1 n c j x j = ∑ i = 1 m b i y i \rm z^* = \sum_{j = 1}^n c_jx_j = \sum_{i = 1}^m b_iy_i z∗=j=1∑n​cj​xj​=i=1∑m​bi​yi​

c j \rm c_j cj​ 表示每个产品带来的利润 ,

x j \rm x_j xj​ 表示产品的个数 ;

影子价格 是 对偶问题 的变量值 ;

生产问题 ( 原问题 ) :

m a x Z = 2 x 1 + 3 x 2 s . t { 2 x 1 + 2 x 2 ≤ 12 x 1 + 2 x 2 ≤ 8 4 x 1 ≤ 16 4 x 2 ≤ 12 x 1 , x 2 ≥ 0 \begin{array}{lcl} \rm maxZ = 2x_1 + 3x_2 \\\\ \rm s.t\begin{cases} \rm 2 x_1 + 2x_2 \leq 12 \\\\ \rm x_1 + 2x_2 \leq 8 \\\\ \rm 4 x_1 \leq 16 \\\\ \rm 4x_2 \leq 12 \\\\ \rm x_1, x_2 \geq 0 \end{cases}\end{array} maxZ=2x1​+3x2​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​2x1​+2x2​≤12x1​+2x2​≤84x1​≤164x2​≤12x1​,x2​≥0​​

上述线性规划的最优解是 : ( 4 2 ) \begin{pmatrix} \quad \rm 4 \quad 2 \quad \\ \end{pmatrix} (42​) ;

甲产品生产 4 4 4 个单位 , 乙产品生产 2 2 2 个单位 ;

设备出租问题 ( 对偶问题 ) :

m i n W = 12 y 1 + 8 y 2 + 16 y 3 + 12 y 4 s . t { 2 y 1 + y 2 + 4 y 3 + 0 y 4 ≥ 2 2 y 1 + 2 y 2 + 0 y 3 + 4 y 4 ≥ 3 y 1 , y 2 , y 3 , y 4 ≥ 0 \begin{array}{lcl} \rm minW = 12y_1 + 8y_2 + 16y_3 + 12y_4 \\\\ \rm s.t\begin{cases} \rm 2 y_1 + y_2 + 4y_3 + 0y_4 \geq 2 \\\\ \rm 2 y_1 + 2y_2 + 0y_3 + 4y_4 \geq 3 \\\\ \rm y_1, y_2 , y_3 , y _4 \geq 0 \end{cases}\end{array} minW=12y1​+8y2​+16y3​+12y4​s.t⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​2y1​+y2​+4y3​+0y4​≥22y1​+2y2​+0y3​+4y4​≥3y1​,y2​,y3​,y4​≥0​​

上述线性规划最优解是 : ( 1 2 1 0 0 ) \begin{pmatrix} \quad \rm \cfrac{1}{2} \quad 1 \quad 0 \quad 0 \quad \\ \end{pmatrix} (21​100​) , 或 ( 0 2 3 1 8 0 ) \begin{pmatrix} \quad \rm 0 \quad \cfrac{2}{3} \quad \cfrac{1}{8} \quad 0 \quad \\ \end{pmatrix} (032​81​0​)

上述原问题线性规划中的影子价格 :

z ∗ = 2 x 1 + 3 x 2 = 12 y 1 + 8 y 2 + 16 y 3 + 12 y 4 \rm z^* = 2 x_1 + 3x_2 = 12y_1 + 8y_2 + 16y_3 + 12y_4 z∗=2x1​+3x2​=12y1​+8y2​+16y3​+12y4​

原问题分析 :

约束方程的 4 4 4 个不等式 , 就是 A B C D \rm ABCD ABCD 四个设备的台时数 ,

甲产品带来利润 2 2 2 , 乙产品带来利润 3 3 3 ;

假设 P \rm P P 问题的目标函数是 m a x Z = 2 x 1 + 3 x 2 \rm max Z = 2 x_1 + 3x_2 maxZ=2x1​+3x2​ ,

m a x Z \rm maxZ maxZ 是利润 ,

x 1 \rm x_1 x1​ 代表甲产品的数量 , x 1 \rm x_1 x1​ 的系数 2 2 2 代表甲产品多生产一个单位能够带来的利润增加 2 2 2 ,

x 2 \rm x_2 x2​ 代表乙产品的数量 , x 2 \rm x_2 x2​ 的系数 3 3 3 代表乙产品多生产一个单位能够带来的利润增加 3 3 3 ;

对偶问题分析 :

12 y 1 \rm 12 y_1 12y1​ 中的系数 12 12 12 增大一个单位 , 能够对目标函数值贡献多少 , 该贡献值与 y 1 \rm y_1 y1​ 值相关 ;

将对偶问题最优解 ( 1 2 1 0 0 ) \begin{pmatrix} \quad \rm \cfrac{1}{2} \quad 1 \quad 0 \quad 0 \quad \\ \end{pmatrix} (21​100​) 代入到 12 y 1 + 8 y 2 + 16 y 3 + 12 y 4 \rm 12y_1 + 8y_2 + 16y_3 + 12y_4 12y1​+8y2​+16y3​+12y4​ 中 ,

得到 12 × 1 2 + 8 × 1 + 16 × 0 + 12 × 0 \rm 12 \times \cfrac{1}{2} + 8 \times 1 + 16 \times 0 + 12 \times 0 12×21​+8×1+16×0+12×0

12 × 1 2 12 \times \cfrac{1}{2} 12×21​ 含义 : 当第一个系数 12 12 12 ( 设备 A \rm A A 的台时数 ) 增大时 , 整个目标函数增大 , 每增大一个单位 , 目标函数增加 1 2 \cfrac{1}{2} 21​ ;

8 × 1 8 \times 1 8×1 含义 : 当第二个系数 8 8 8 ( 设备 B \rm B B 的台时数 ) 增大时 , 整个目标函数增大 , 每增大一个单位 , 目标函数增加 1 1 1 ;

16 × 0 16 \times 0 16×0 含义 : 当第三个系数 16 16 16 ( 设备 C \rm C C 的台时数 ) 增大时 , 整个目标函数不变 , 每增大一个单位 , 目标函数增加 0 0 0 ;

12 × 0 12 \times 0 12×0 含义 : 当第四个系数 21 21 21 ( 设备 D \rm D D 的台时数 ) 增大时 , 整个目标函数不变 , 每增大一个单位 , 目标函数增加 0 0 0 ;