页数：36页文件大小：182.4 KB来源： 运筹学ppt课件
本课件讲授线性规划的对偶理论：由资源出租定价实例引出对偶问题，归纳原问题与对偶问题的对应关系；进而讨论对称性、弱对偶性、最优性、强对偶性与互补松弛性等性质，说明影子价格的经济含义，介绍对偶单纯形法与灵敏度分析。
本章共分七节：
例：某工厂生产甲、乙两种产品，每件纯利润为 6 元和 4 元。每件产品需机器工作时间 2 小时和 3 小时，人力工作时间 4 小时和 2 小时。已知该厂每天能提供 300 小时机器工作时间和 320 小时人力工作时间，问应如何安排生产，才能使工厂获利最大。
分析：就原工厂来说，希望定价尽可能高，放弃生产的收益不能低于自己生产所得；就租贷工厂来说，希望定价尽可能低，至少不能超过生产所得的利润。设一个机器工作时间为 y1 元、一个人力工作时间为 y2 元，双方据此达成协议。
对于线性规划问题 max z = cX（约束 AX ≤ b，X ≥ 0），称线性规划问题 min w = bᵀY（约束 AᵀY ≥ cᵀ，Y ≥ 0）为其对偶问题，而前者称为原问题。
2.2 原问题与对偶问题的关系：
这些关系可用表格形式表示。
原问题（对偶问题）与对偶问题（原问题）的对应关系如下：
源文件该页为表格排版，各格文字顺序被打散，此处按对偶对应规则还原，建议对照原图核对。
例：求下列线性规划的对偶问题。
原问题：min z = 7x1 + 4x2 - 3x3，约束 -4x1 + 2x2 - 6x3 ≤ 24、-3x1 - 6x2 - 4x3 ≥ 15、5x2 + 3x3 = 30，x1 ≤ 0，x2 无约束，x3 ≥ 0。
解：按原问题与对偶问题的对应关系，设对偶变量为 y1、y2、y3，其中 y1 ≤ 0、y2 ≥ 0、y3 无约束，写出对偶问题为 max 型，其约束的符号由原问题变量的符号确定（x1 ≤ 0 对应「≤」，x2 无约束对应「=」，x3 ≥ 0 对应「≥」）。
源文件该页公式连排，对偶模型的具体系数建议对照原图核对。
2.3 对偶问题的基本性质。在下面的讨论中，假定原问题为 max z = Σcjxj（Σaijxj ≤ bi，xj ≥ 0），对偶问题为 min w = Σbiyi（Σaijyi ≥ cj，yi ≥ 0）。主要性质有：
一、对称性：原问题与对偶问题互为对偶。
原问题 max z = Σcjxj（Σaijxj ≤ bi，xj ≥ 0）的对偶问题为 min w = Σbiyi（Σaijyi ≥ cj，yi ≥ 0）；反之亦然，把后者视作原问题时，其 max 型对偶正是前者。
二、弱对偶性：如果 xj 是原问题的可行解，yj 是对偶问题的可行解，则恒有
Σnj=1 cjxj ≤ Σmi=1 biyi
证：因为 Σbiyi ≥ Σ(Σaijxj)yi = ΣΣaijxjyi，又 Σcjxj ≤ Σ(Σaijyi)xj = ΣΣaijxjyi，所以 Σcjxj ≤ Σbiyi。
三、最优性：如果 x̂j 是原问题的可行解，ŷj 是对偶问题的可行解，且有 Σcjx̂j = Σbiŷi，则 x̂j 是原问题的最优解，ŷj 是对偶问题的最优解。
证：设 x* 是原问题的最优解，y* 是对偶问题的最优解，有 Σcjx̂j ≤ Σcjx*j，Σbiy*i ≤ Σbiŷi；又由弱对偶性知 Σcjx*j ≤ Σbiy*i，故 Σcjx̂j = Σbiŷi 时两者同时取到最优。
四、无界性：
五、强对偶性（对偶定理）：如果原问题有最优解，其对偶问题也一定有最优解，且有 max z = min w。
证：将原问题加上松弛变量化成标准形式，用单纯形法求解，当所有 σ ≤ 0 时得最优解。由 σ = c - cB B⁻¹A = c - YA ≤ 0，即 Σaijyi ≥ cj，且 -Y = -cB B⁻¹ ≤ 0 即 yi ≥ 0，由此 yi 是对偶问题的可行解；又因 z = cX = Σcjxj = cB B⁻¹b = Σbiyi，故由性质三知 yi 是对偶问题的最优解，且 max z = min w。
六、互补松弛性：在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。也即：
互补松弛性的推导：由 Σcjx̂j = Σbiŷi 及 ΣΣaijx̂jŷi 的恒等变形可得
Σ(Σaijx̂j - bi)ŷi = 0，Σ(cj - Σaijŷi)x̂j = 0
因 yi ≥ 0、x̂j ≥ 0，且 (Σaijx̂j - bi) ≤ 0、(cj - Σaijŷi) ≤ 0，故每一项必须为 0：当 Σaijx̂j - bi < 0 时必有 ŷi = 0；当 ŷi > 0 时必有 Σaijx̂j = bi。
源文件该页为公式连排排版，推导中的求和下标建议对照原图核对。
例题要求：1、写出其对偶问题；2、已知所给问题的最优解为 x1 = -5，x2 = 0，x3 = -1，试用对偶理论直接求对偶问题的最优解。
原问题：min z = 2x1 - x2 + 2x3，约束 -x1 + x2 + x3 = 4、-x1 + x2 - x3 = 6，x1 ≤ 0，x2 ≥ 0，x3 无约束。
解（1）对偶问题为 max w = 4y1 + 6y2，约束 -y1 - y2 ≥ 2、y1 - y2 ≤ -1、y1 + y2 = 2，y1、y2 无约束。（2）由互补松弛性，把原问题最优解代入约束，因对应约束均取严格等式，故 y1、y2 可由方程组直接解出，即为对偶问题的最优解。
源文件该页公式连排，对偶约束符号与最终解值建议对照原图核对。
七、单纯形法的双层含义：用单纯形法求解线性规划问题时，迭代的每一步在得到该问题的一个基本可行解的同时，其检验数的相反数就构成对偶问题的一个基本解；在单纯形表中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量；将这两个解代入各自的目标函数中有 z = w。
例：如下两个线性规划问题互为对偶，分别用单纯形法求解得最终表。
两张最终表对照可见：原变量与对偶变量的基、非基身份互换，且两表目标值相等。
源文件该页为单纯形表矩阵排版，表中各列数值建议对照原图核对。
影子价格的意义：
对偶单纯形法是在保持对偶问题为可行解的基础上，通过迭代减小目标函数值，当原问题也达到可行解时，即得到了目标函数的最优值，从而得到原问题的最优解。
用对偶单纯形法求解线性规划的步骤如下：
例：用对偶单纯形法求解 min w = 15y1 + 24y2 + 5y3，约束 5y1 + 6y2 + y3 ≥ 2、y1 + 2y2 + y3 ≥ 1，yi ≥ 0。
解：令 max(-w) = -15y1 - 24y2 - 5y3，减去剩余变量并两端乘 -1 后变成标准形：
max(-w) = -15y1 - 24y2 - 5y3，约束 -5y1 - 6y2 - y3 + y4 = -2、-y1 - 2y2 - y3 + y5 = -1，yi ≥ 0
求解过程：检验数行全为非正满足对偶可行，取最小的基变量值所在行为换出，按 θ 规则确定换入列迭代，直至基变量列全为非负，即得最优解。
源文件该页为矩阵排版，中间迭代表的数值建议对照原图核对。
灵敏度分析是指对系统或事物因周围条件变化显示出来的敏感程度的分析。
在前面的线性规划问题中，都假定问题中的 aij、bi、cj 是已知常数，而实际上这些数往往是一些估计和预测的数字：如市场条件一变，cj 值就会变化；aij 是随工艺技术条件的改变而改变；而 bi 则是根据资源投入后能产生多大经济效果来决定的一种决策选择。
因此就会提出以下问题：当这些参数中的一个或几个发生变化时，问题的最优解会有什么变化，或这些参数在多大范围内变化时，问题的最优解不变。这就是灵敏度分析要解决的问题。
灵敏度分析的步骤可归纳如下：
据两者的可行情况，分别采取下列处理：
一、分析 cj 变化的影响：目标函数中系数 cj 的变化仅影响到 (cj - zj) 的变化。所以将 cj 的变化直接反映到最终单纯形表中，只可能出现表中所示的前两种情况。
例1：已知线性规划问题 max z = 2x1 + x2，约束 5x2 ≤ 15、6x1 + 2x2 ≤ 24、x1 + x2 ≤ 5（原文第一个约束写作 5x2 ≤ 15），并用单纯形法求解得最终单纯形表。试确定：当目标函数变为 max z = 5x1 + 1.5x2 时，最优解会出现什么变化。
源文件该页约束与终表数值排版不完整，建议对照原图核对。
解：将目标函数系数的变化直接反映到最终单纯形表中，得新的检验数行；表中变量 x5 的检验数为正，继续迭代计算得新的最优解。
即得新的最优解为 x1 = 4，x2 = 0，z = 20。
源文件该页两张终表数值连排，迭代过程的具体数值建议对照原图核对。
二、分析 bi 变化的影响：把 bi 的变化直接反映到最终单纯形表上，只引起基变量列数字的变化。由于其对偶问题仍为可行解，故只需检查原问题是否仍为可行解。
例：在上例中，若第 2 个约束条件右端项增大到 32，分析最优解的变化。
解：因 Δb = (0, 8, 0)ᵀ，计算 Δb′ = B⁻¹Δb，将其加到最终单纯形表的基变量 b 这一列数字上，得新的基变量值，再检查其非负性并决定是否继续用对偶单纯形法迭代。
源文件该页矩阵与数值连排，Δb′ 的具体分量建议对照原图核对。
三、增加一个变量的分析：增加一个变量相当于增加一个新产品，即 A 增加一列、c 增加一个相应的分量。
例：在例1中，若增加一个变量 x6，已知 c6 = 3，P6 = (3, 4, 2)ᵀ，试分析最优解的变化。
解：把 P′6 = B⁻¹P6 反映到最终单纯形表中，得到 x6 在终表中的列与检验数；若其检验数为正则继续迭代，说明投产新产品有利，最优解随之改变。
源文件该页 P′6 计算结果为连排排版（文中出现 (-7, 0.2)ᵀ 一类数值），建议对照原图核对。
四、分析 aij 变化的影响：假如 xj 在最终单纯形表中为基变量，则 aij 的变化将使最终单纯形表中的 B⁻¹ 变化，因此有可能出现原问题与对偶问题均为非可行解的情况。
例：在例1中，c2 = 3，x2 的系数向量变为 p2 = (8, 4, 1)ᵀ，试分析最优解的变化。
解：把 P′2 = B⁻¹P2 反映到最终单纯形表中，得表中第一行为 x3 + 4x4 - 24x5 = -9；两端乘 -1 再加人工变量 x6，得 -x3 - 4x4 + 24x5 + x6 = 9，将此式替换表中第一行。因表中原问题与对偶问题均为非可行解，通过引入人工变量将原问题转化为可行解，再用单纯形法继续求解。
接上页，引入人工变量 x6 后继续用单纯形法迭代，新的最优解为：
x1 = 11/4，x′2 = 15/8，最优值 z* = 89/8。
源文件该页为单纯形表矩阵连排，迭代过程各列数值建议对照原图核对。
五、增加一个约束条件的分析：增加一个约束条件相当于增加一道工序。分析的方法是将原问题的最优解变量取值代入这个新增加的约束条件中，如满足，说明新增约束未起到限制作用，原最优解不变；否则，将新增约束直接反映到最终单纯形表中，再分析。
例：设在例1中增加一个约束条件 3x1 + 2x2 ≤ 12，试分析最优解的变化。
解：先将原问题的最优解变量值代入，因有 3 × 7/2 + 2 × 3/2 = 27/2 > 12，故将约束条件写成 3x1 + 2x2 + x6 = 12，并取 x6 为基变量，直接反映到最终单纯形表中继续求解。
例：已知线性规划问题 max z = 3x1 + 5x2，约束 x1 ≤ 4、2x2 ≤ 12、3x1 + 2x2 ≤ 18，xj ≥ 0。要求：
解：用单纯形法求得最终单纯形表，最优解不变，z = 40。
源文件该页矩阵与终表数值连排，具体数值建议对照原图核对。
前面讨论了当线性规划模型中参数 aij、bi、cj 改变到某一数值时对最优解的影响。但实际常常要研究：这些参数在什么范围内变化时最优解不变，当参数超过这个范围时，最优解将怎样变化，这就是参数线性规划要研究的问题。
例：在例1中，第 3 个约束条件的右端项不断增大，即 x1 + x2 ≤ 5 + λ，6x1 + 2x2 ≤ 24。代入最终单纯形表中得 Δb* = B⁻¹Δb = (0, -(15/2)λ, …)ᵀ 形式的参数化基变量列。
源文件该页公式连排，参数化表达式各分量建议对照原图核对。
从表中可看出：当 0 ≤ λ ≤ 1 时，表中基变量均非负，仍为最优解；当 λ = 1 时 x3 = 0；当 λ > 1 时 x3 < 0，用对偶单纯形法继续计算，得新的最优解 X1 = 3，X2 = 3，最优值 z = 9。
目标函数 z 与 λ 的关系见图中折线，说明 z 是 λ 的分段线性函数。
源文件该页终表为矩阵连排，各基变量随 λ 变化的表达式建议对照原图核对。
当问题中有多个参数变化时，应使 z 是 λ 的线性函数。
例：求解下列线性规划问题 max z(λ) = (2 + λ)x1 + (1 + 2λ)x2，约束 5x2 ≤ 15、x1 + x2 ≤ 5、6x1 + 2x2 ≤ 24，x1, x2 ≥ 0。
求解过程：把含 λ 的系数代入最终单纯形表，检验数写作 -1/2 - (5/2)λ 与 -1/4 + (1/4)λ 的形式；当 λ ≤ 1 时表中为最优解，当 λ > 1 时继续求解，得到新的最优解。
源文件该页终表数值连排，建议对照原图核对。
例：某文教用品厂利用原材料白坯纸生产原稿纸、日记本和练习本三种产品。该厂现有工人 100 人，每天白坯纸供应限量为 3 万 kg。如果单独生产各种产品时，每人每天生产原稿纸 30 捆，或日记本 30 打，或练习本 30 箱。已知原材料消耗量为：每捆原稿纸用白坯纸 10/3 kg，每打日记本用 40/3 kg，每箱练习本用 80/3 kg；利润分别为 2 元、3 元、1 元。试决定：
解：设该厂每天生产原稿纸 x1 捆、日记本 x2 打、练习本 x3 箱，建立线性规划模型并用单纯形法求解，得到最终单纯形表。
由表中可知，劳动力的影子价格为 50 元/月，高于临时工工资 40 元/人/天，故可招收临时工。将 λ 直接反映到最终单纯形表中，分析当 λ 值增大时最优解的变化，由此看出该厂最多招收临时工的人数。
源文件该页终表数值连排且「最多招收」的具体人数缺失，建议对照原图补齐。
下载地址：{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}