02 第二章 对偶理论与灵敏度分析.pptx

第1页：第二章封面与§1矩阵描述

第二章 对偶理论与灵敏度分析　§1 单纯形法的矩阵描述

设 max z = CX，AX = b，X ≥ 0，A 为 m×n 阶矩阵，RankA = m，取 B 为可行基，N 为非基。

第2页：矩阵描述的推导

本页为单纯形法矩阵描述的推导页，源文件仅提取到页码等少量文字。内容为把约束 AX = b 按基 B 与非基 N 分块，并写出 X_B = B⁻¹b − B⁻¹NX_N，建议对照原课件图片核对。

第3页：目标函数的矩阵表达

本页为矩阵描述的承接页，源文件仅提取到页码等少量文字。内容为把目标函数写成 z = C_BB⁻¹b + (C_N − C_BB⁻¹N)X_N，并给出检验数表达式，建议对照原课件图片核对。

第4页：求解步骤

求解步骤：本页为标题页，源文件未展开具体步骤文字，矩阵描述下的求解步骤见后续页与图示。

第5页：§2对偶问题的提出与例1

§2 对偶问题的提出　[eg.1] 制定生产计划。

原问题 M1：max z = 2x1 + 3x2，约束 x1 + 2x2 ≤ 8，4x1 ≤ 16，4x2 ≤ 12，x1、x2 ≥ 0。

第6页：例1的对偶问题M2

现在考虑出租：设 y1 为设备单位台时的租金，y2、y3 为材料 A、B 转让附加费（kg⁻¹），则 M2 为 M1 的对偶问题，反之亦然。

M2：min w = 8y1 + 16y2 + 12y3

• y1 + 4y2 ≥ 2
• 2y1 + 4y3 ≥ 3
• y1、y2、y3 ≥ 0

图中同时标注两种产品的资源消耗：设备台时 8（Ⅰ为 1、Ⅱ为 2），材料A 16kg（Ⅰ为 4、Ⅱ为 0），材料B 12kg（Ⅰ为 0、Ⅱ为 4），利润分别为 2 与 3。

第7页：原问题与对偶问题的对应关系

一般的，原问题：max z = CX，AX ≤ b，X ≥ 0；对偶问题：min w = Yb，YA ≥ C，Y ≥ 0。

第8页：§3对偶问题的化法与例2

§3 对偶问题的化法　1、典型情况　[eg.2]

原问题：max z = x1 + 2x2 + x3，约束 2x1 + x2 ≤ 6，2x2 + x3 ≤ 8，x1、x2、x3 ≥ 0。

对偶问题：min w = 6y1 + 8y2，约束 2y1 ≥ 1，y1 + 2y2 ≥ 2，y2 ≥ 1，y1、y2 ≥ 0。

第9页：例3含等式的对偶

2、含等式的情况　[eg.3] max z = x1 + 2x2 + 4x3，约束 2x1 + x2 + 3x3 = 3，x1 + 2x2 + 5x3 ≤ 4，x1、x2、x3 ≥ 0。

等式可拆为 2x1 + x2 + 3x3 ≤ 3 与 −2x1 − x2 − 3x3 ≤ −3，于是对偶为：min w = 3y1′ − 3y1″ + 4y2，约束 2y1′ − 2y1″ + y2 ≥ 1，y1′ − y1″ + 2y2 ≥ 2，3y1′ − 3y1″ + 5y2 ≥ 4，y1′、y1″、y2 ≥ 0。

令 y1 = y1′ − y1″，则简化为：min w = 3y1 + 4y2，约束 2y1 + y2 ≥ 1，y1 + 2y2 ≥ 2，3y1 + 5y2 ≥ 4，y2 ≥ 0，y1 无约束。

一般规律：原问题第 i 个约束取等式，对偶问题第 i 个变量无约束。

第10页：例4含≥的max问题

3、含「≥」的 max 问题　[eg.4] max z = x1 + 2x2 + 4x3，约束 2x1 + x2 + 3x3 ≥ 3，x1 + 2x2 + 5x3 ≤ 4，x1、x2、x3 ≥ 0。

「≥」约束改写为 −2x1 − x2 − 3x3 ≤ −3，对偶为：min w = −3y1′ + 4y2，约束 −2y1′ + y2 ≥ 1，−y1′ + 2y2 ≥ 2，−3y1′ + 5y2 ≥ 4，y1′、y2 ≥ 0。

令 y1 = −y1′，则：min w = 3y1 + 4y2，约束 2y1 + y2 ≥ 1，y1 + 2y2 ≥ 2，3y1 + 5y2 ≥ 4，y1 ≤ 0，y2 ≥ 0。

第11页：对偶化法的六条一般规则

一般规则：

第12页：例5混合约束的对偶

[eg.5] min z = 2x1 + 3x2 − 5x3 + x4

• x1 + x2 − 3x3 + x4 ≥ 5
• 2x1 + 2x3 − x4 ≤ 4
• x2 + x3 + x4 = 6
• x1 ≤ 0，x2、x3 ≥ 0，x4 无约束

对偶问题：max w = 5y1 + 4y2 + 6y3

• y1 + y2 ≥ 2
• y1 + y3 ≤ 3
• −3y1 + 2y2 + y3 ≤ −5
• y1 − y2 + y3 = 1
• y1 ≥ 0，y2 ≤ 0，y3 无约束

第13页：对称性

§4 对偶问题的性质　1、对称性：对偶问题的对偶为原问题。

第14页：弱对偶性

2、弱对偶性：本页源文件仅提取到页码等少量文字，内容为弱对偶性的表述（原问题任一可行解的目标值不大于对偶问题任一可行解的目标值），建议对照原课件图片核对完整表述。

第15页：弱对偶性的证明

本页为弱对偶性证明的承接页，源文件仅提取到页码等少量文字。内容为由 CX ≤ YAX ≤ Yb 推出弱对偶关系，建议对照原课件图片核对推导过程。

第16页：推论与无界性

推论：

1. max 问题任一可行解的目标值为 min 问题目标值的一个下界；
2. min 问题任一可行解的目标值为 max 问题目标值的一个上界。

3、无界性　若原问题（对偶问题）为无界解，则对偶问题（原问题）为无可行解。

注：该性质的逆不存在。若原（对偶）问题为无可行解，对偶（原）问题或为无界解，或为无可行解。

第17页：最优性

4、最优性　设 X*、Y* 分别为原问题和对偶问题的可行解，当 CX* = Y*b 时，X*、Y* 分别为最优解。

第18页：对偶定理

5、对偶定理　若原问题有最优解，那么对偶问题也有最优解，且目标值相等。

第19页：松弛性

由对偶定理的推导可得：Y* 为对偶问题的最优解，且原问题和对偶问题的目标值相等。证毕。

6、松弛性　若 X*、Y* 分别为原问题及对偶问题的可行解，那么 Y_s*X* = 0，Y*X_s* = 0，当且仅当 X*、Y* 分别为最优解。

证明：（见下页）

第20页：松弛性证明的代入

证明：将 b、C 分别代入目标函数进行展开，推导互补松弛条件 Y_s*X* = 0 与 Y*X_s* = 0。

本页为公式推导页，源文件文字提取较少，建议对照原课件图片核对展开式。

第21页：松弛性的分量形式

其中：用分量表示，互补松弛条件可写成 y_si*x_i* = 0（i = 1,…,n）与 y_j*x_sj* = 0（j = 1,…,m）。

本页为公式推导页，源文件文字提取较少，建议对照原课件图片核对分量下标。

第22页：检验数与解的关系

7、检验数与解的关系

1. 原问题非最优检验数的负值为对偶问题的一个基解；
2. 原问题最优检验数的负值为对偶问题的最优解。

分析：max z = CX + 0X_s = (C 0)(X X_s)T，AX + X_s = b，X、X_s ≥ 0；min w = Yb + YS₀，YA − Y_s = C，Y、Y_s ≥ 0。

检验数 σ = (C 0) − C_BB⁻¹(A I) = (C − C_BB⁻¹A −C_BB⁻¹) = (σ_c σ_s)，其中 σ_c = C − C_BB⁻¹A 为 X 对应的检验数，σ_s = −C_BB⁻¹ 为 X_s 对应的检验数。

第23页：例6用松弛性求最优解

[eg.6] 已知 min w = 20y1 + 20y2 的最优解为 y1* = 1.2、y2* = 0.2，试用松弛性求其对偶问题的最优解。

对偶问题的约束为：

• y1 + 2y2 ≥ 1　①（剩余变量 −ys1）
• 2y1 + y2 ≥ 2　②（剩余变量 −ys2）
• 2y1 + 3y2 ≥ 3　③（剩余变量 −ys3）
• 3y1 + 2y2 ≥ 4　④（剩余变量 −ys4）
• y1、y2 ≥ 0

对偶问题（原问题）为：max z = x1 + 2x2 + 3x3 + 4x4，约束 x1 + 2x2 + 2x3 + 3x4 ≤ 20 + xs1，2x1 + x2 + 3x3 + 2x4 ≤ 20 + xs2，变量均非负。

互补松弛条件：y1*xs1* = 0，y2*xs2* = 0，ys1*x1* = 0，ys2*x2* = 0，ys3*x3* = 0，ys4*x4* = 0。

第24页：例6求解过程与结果

因 y1* = 1.2、y2* = 0.2 > 0，故 xs1* = xs2* = 0。

• 由① y1* + 2y2* = 1.6 > 1，故 ys1* > 0，从而 x1* = 0；
• 由② 2y1* + y2* = 2.6 > 2，故 ys2* > 0，从而 x2* = 0；
• 由③ 2y1* + 3y2* = 3 = 右边，故 ys3* = 0，x3* 待定；
• 由④ 3y1* + 2y2* = 4 = 右边，故 ys4* = 0，x4* 待定。

于是有 2x3* + 3x4* = 20，3x3* + 2x4* = 20，解得 x3* = 4，x4* = 4。

• 最优解：x1* = 0，x2* = 0，x3* = 4，x4* = 4，xs1* = 0，xs2* = 0
• 最大值：z* = 28 = w*

第25页：§5对偶问题的经济含义

§5 对偶问题的经济含义 —— 影子价格　最优情况下：z* = w* = b1y1* + … + biyi* + … + bmym*。

[eg.7] max z = 2x1 + 3x2，约束 x1 + 2x2 ≤ 8，4x1 ≤ 16，4x2 ≤ 12，x1、x2 ≥ 0，最优顶点为 Q2(4,2)。

b1 增至 9 时最优顶点移到 Q2′(4，2.5)，z*′ = 15.5；b2 增至 17 时移到 Q2″(4.25，1.875)，z*″ = 14.125。

第26页：§6对偶单纯形法步骤

§6 对偶单纯形法

单纯形法

由 X_B = B⁻¹b ≥ 0 出发，迭代使 σj ≤ 0（j = 1,…,m）。

对偶单纯形法

由 σj ≤ 0（j = 1,…,n）出发，迭代使 X_B = B⁻¹b ≥ 0。

步骤：

1. 保持 σj ≤ 0（j = 1,…,n），确定 X_B，建立计算表格；
2. 判别 X_B = B⁻¹b ≥ 0 是否成立：① 若成立，X_B 为最优基变量；② 若不成立，转（3）。

第27页：基变换与消元运算

（3）基变换：① 确定出基变量，② 确定入基变量，重复（2）—（4）步，求出结果。

（4）消元运算，得到新的 X_B。

第28页：例8化为标准型

[eg.8] 用对偶单纯形法求解：min w = 2x1 + 3x2 + 4x3，约束 x1 + 2x2 + x3 ≥ 1，2x1 − x2 + 3x3 ≥ 4，x1、x2、x3 ≥ 0。

解：化为 max z = −2x1 − 3x2 − 4x3 + 0x4 + 0x5，约束 −x1 − 2x2 − x3 + x4 = −1，−2x1 + x2 − 3x3 + x5 = −4，x1、x2、x3、x4、x5 ≥ 0。

第29页：例8迭代与最优解

初始表中 x4 = −1、x5 = −4 均小于 0，故非最优；以 −2 为主元作基变换，x1 入基、x5 出基，迭代后基变量为 x4 与 x1。

因 x1、x4 > 0，故得最优解。

• 最优解：x1* = 2，x2* = 0，x3* = 0，x4* = 1，x5* = 0
• 目标值：w* = −z* = 4

本页单纯形表在源文件中数字粘连严重，无法安全切分为标准单元格，已按文字表述保留，建议对照原课件图片人工还原表格。

第30页：§7灵敏度分析

§7 灵敏度分析　分析参数变化对最优解的影响。

第31页：灵敏度分析例1引入

本页为灵敏度分析示例的引入页，源文件仅提取到页码等少量文字。内容为引出例1的最优解与最优单纯形表，建议对照原课件图片核对。

第32页：例1的已知最优解与最优表

例1　已知下述问题的最优解及最优单纯形表（具体模型与表见下页图示），在此基础上分析各参数变化对最优解的影响。

第33页：例1最优单纯形表

最优单纯形表如下：基变量为 x2（c_B = 3）与 x1（c_B = 2），取值分别为 4 与 4，检验数行依次为 0、0、−3/2、−1/8 等，x3、x4、x5 列为 1/4、0、−1/2、1/2 等。

本页单纯形表在源文件中数字粘连严重，无法安全切分为标准单元格，已按文字表述保留，建议对照原课件图片人工还原表格。

第34页：由最优表得到的矩阵关系

由最优单纯形表得：可从中读出 B⁻¹、C_BB⁻¹ 以及各非基变量列的系数，作为后续灵敏度分析的依据。

本页为推导页，源文件文字提取较少，建议对照原课件图片核对矩阵元素。

第35页：参数变化后的检验数

本页为灵敏度分析的承接页，源文件仅提取到页码等少量文字。内容为参数变化后重新计算检验数 σj 的表达式，建议对照原课件图片核对。

第36页：不可行时的对偶单纯形法

参数变化后出现不可行的情形（基变量取值 B⁻¹b 出现负数），此时检验数仍满足最优性条件，故改用对偶单纯形法继续计算。

第37页：对偶单纯形法重算表

用对偶单纯形法计算：表中列出 x3、x2、x1 等行与 θ 列，主元位置标注为 [−2]，基变量取值为 4 + Δ 与 2 − 8Δ 的形式，用以判断保持可行性的范围。

本页单纯形表在源文件中数字粘连严重，无法安全切分为标准单元格，已按文字表述保留，建议对照原课件图片人工还原表格。

第38页：取值范围的导出

本页为灵敏度分析迭代结果的承接页，源文件仅提取到页码等少量文字。内容为整理对偶单纯形法迭代后得到的参数取值范围，建议对照原课件图片核对。

第39页：例2求Δc4变化范围

例2　求例1中 Δc4 的变化范围，使最优解不变。

解：以例1的最优单纯形表为基础（表中基变量为 x2、x1，取值 4 与 4，检验数行含 0、−3/2、−1/8 等），把 c4 的改变量 Δc4 代入检验数，令非基变量检验数仍满足最优性条件，解出 Δc4 的允许区间。

本页单纯形表在源文件中数字粘连严重，无法安全切分为标准单元格，区间端点请以原课件图片为准。

第40页：例2的分析

分析：Δc4 只影响非基变量 x4 的检验数，基变量取值 B⁻¹b 不受影响，因此只需令 x4 的检验数仍满足最优性符号要求，即可求出保持最优解不变的 Δc4 范围。

第41页：例3求Δc2变化范围

方法：例3　求例1中 Δc2 的变化范围，使最优解不变。以例1的最优单纯形表为基础（基变量 x2、x1，取值 4 与 4），把 c2 的改变量代入检验数重新计算。

第42页：例3的求解过程

解：由最优表，c2 属于基变量价值系数，其变化会同时影响各非基变量检验数 σj = cj − C_BB⁻¹P_j。把 c2 + Δc2 代入 C_B，令 σ3、σ4、σ5 均 ≤ 0，联立解得 Δc2 的上、下界，即为保持原最优解不变的范围。

本页单纯形表在源文件中数字粘连严重，区间端点请以原课件图片为准。

第43页：例3结果的过渡页

本页为灵敏度分析的过渡页，源文件仅提取到页码等少量文字。内容为整理 Δc2 的取值范围并转入下一项参数分析，建议对照原课件图片核对。

第44页：变化后的可行性分析

分析：判断参数变化后基变量取值 B⁻¹b 是否仍非负：若仍非负，则最优基不变、最优解不变；若出现负数，则需用对偶单纯形法继续迭代。

第45页：约束系数变化的引入

本页为灵敏度分析的过渡页，源文件仅提取到页码等少量文字。内容为由价值系数变化转入约束系数 a_ij 变化的分析，建议对照原课件图片核对。

第46页：例4求Δa24变化范围

例4　求例1中 Δa24 的变化范围，使最优解不变。

解：a24 为非基变量 x4 在第二个约束中的系数，其变化只影响 x4 的检验数 σ4 = c4 − C_BB⁻¹P₄。代入最优表中的 B⁻¹ 与 C_B，令 σ4 ≤ 0，即可解出 Δa24 的允许范围。

第47页：例5增加新产品Ⅲ

例5　在例1的基础上，企业要增加一个新产品Ⅲ，每件产品需 2 个台时、原材料 A 6kg、原材料 B 3kg、利润 5 元/件。问如何安排各产品的产量，使利润最大？

解：在原最优表中增加 x′3（产品Ⅲ）一列，计算其检验数后判断是否需要投产。

第48页：投产新品的判断结论

计算新增变量 x′3 的检验数 σ′3 = c′3 − C_BB⁻¹P′₃ = 5/4 > 0，表明生产新品有利，应把 x′3 作为入基变量继续迭代。

第49页：新增列的单纯形表

在原最优表中增加 x′3 列：系数列含 1/4、3/2、0 等，θ 值分别为 8/3、4/2 等，检验数为 5/4。基变量为 x2（取值 4）与 x1（取值 4），c_B 列为 3 与 2。

本页单纯形表在源文件中数字粘连严重，无法安全切分为标准单元格，已按文字表述保留，建议对照原课件图片人工还原表格。

第50页：投产新品后的迭代结果

以 [2] 为主元作旋转运算，x′3 入基，迭代后检验数行更新为 0、−7/16、−5/8、−3/4 等，基变量取值相应调整，得到包含新产品Ⅲ的最优生产方案。

本页单纯形表在源文件中数字粘连严重，无法安全切分为标准单元格，已按文字表述保留，建议对照原课件图片人工还原表格。

第51页：小结：对偶问题及其化法

小结

1、对偶问题及其化法

• 原问题决策变量决定对偶问题约束条件关系；
• 原问题约束条件决定对偶问题决策变量取值方向。

第52页：小结：检验数的计算方法

2、检验数的计算方法：σj = cj − C_BB⁻¹P_j，由最优检验数的负值即得对偶问题的最优解。

第53页：小结：对偶问题性质与对偶单纯形法

3、对偶问题的性质：● 弱对偶性　● 无界性　● 最优性　● 松弛性　● 检验数与对偶问题的解

4、对偶单纯形法：保持检验数满足最优性条件，通过基变换逐步消除基变量取值的负数，直至 X_B = B⁻¹b ≥ 0。

第54页：小结：灵敏度分析

5、灵敏度分析：分别考察价值系数 cj、资源右端常数 bi、约束系数 aij 的变化以及增加新产品、新约束时对最优解与最优值的影响。

第55页：第二章收尾页

本页为第二章的收尾页，源文件仅提取到页码等少量文字，正文内容以图片形式呈现，建议对照原课件图片补充本页要点。