2019/6/20 目录 21对偶问题的提出 2.2线性规划的对偶理论 第2章对偶理论与灵敏度分析 2.3对偶问题的经济解释 影子价格 2.4灵敏度分析 Duality Theory and Sensitivity Analysis △ A 2.1对偶问题的提出 产品1 产品 供应量 +165+12男 max-=2x.. 菌材料 1+42 5+42 原材料B 12 片乃，乃≥0 利润 2 3 ≤b 现工厂决策者决定不生产产品，而将其所有资源出租或 2 20 出售，应如何给每种资源定价？ C,-CBNs0 =C, △ CB-≤0 性 (P) m:C腾的一国 min o=Yb X20 上对偶模型称为对称式 称的对应关系： 和得有联系有区到：联系它 原问题(P) 对偶问题(D】 是 有个变量负) 有个的束大于等于） 右个约束（小于等于） 有个变量（非负） ·任何线性提划问题都有对偶问恩。而且都有相应的经济意 价格系数 资源向量 第个变量为自由变量 第个约束为等式约束 △
2019/6/20 1 第2章 对偶理论与灵敏度分析 Duality Theory and Sensitivity Analysis 目录 2.1 对偶问题的提出 2.2 线性规划的对偶理论 2.3对偶问题的经济解释----影子价格 2.4 灵敏度分析 2.1 对偶问题的提出 产品I 产品II 供应量 设 备 原材料A 原材料B 1 4 0 2 0 4 8 16 12 利 润 2 3 现工厂决策者决定不生产产品，而将其所有资源出租或 出售，应如何给每种资源定价？ 设y1，y2和y3分别表示出租单位设备台时的租金和出让单位原材料A，B的 价格，那么出让相对于生产一单位第 j 种产品的资源消耗的价值应不低于 第 j 种产品的单位利润价值，但同时买方会把价格压到最低。则有（左式） 1 2 y y + 4 2 1 3 2 4 3 y y + min 8 16 12 1 2 3 = + + y y y 1 2 3 y y y , , 0 1 2 x x + 2 8 1 4 16 x 2 4 12 x 1 2 max z x x = + 2 3 1 2 x x, 0 st.. 1 1 0 0 N B B C C B N C B − − − − 1 Y C BB − = Y 0 YA C Yb z = max 0 z CX AX b X = min 0 Yb YA C Y = 对偶模型的一般式 = 0 . . X AX b s t max z CX （P) = 0 . . min Y YA C st Yb 上对偶模型称为对称式对偶模型。二者间有对称的对应关系： 原问题（P） 对偶问题 （D） 目标max型 目标min型 有n个变量（非负） 有n个约束（大于等于） 有m个约束 （小于等于） 有m个变量（非负） 价格系数 资源向量 资源向量 价格系数 技术系数矩阵 技术系数矩阵 第j个变量为自由变量 第j个约束为等式约束 第i个约束为等式约束 第i个变量为自由变量 • 原模型P和对偶模型D既有联系又有区别。联系在于，它们 都是关于家具厂生产经营的模型，并且使用相同的数据； 区别在于，它们所反映的实质内容是完全不同的：P是站 在家具厂经营者的立场上追求家具厂的销售收入最大;而D 则是站在家具厂谈判对手的立场上寻求应付家具厂租金最 少的策略。 • 任何线性规划问题都有对偶问题，而且都有相应的经济意 义。 • 由以上不难得到，所谓对偶规划，就是与线性规划原问题 相对应并使用同一组数据按照特定方法形成的另一种反映 不同性质问题的线性规划模型
2019/6/20 2.1对偶问题的提出-关系 2.2线性规划的对偶理论 原问愿（或对偶问愿）对偶问愿（成原间题） 日标面数】 日标函嫩 定理1对称性定理 变量m个) 的束条件 (个) Z-CX 对的定 20 变量(m个】 目标函数变 的束条件右增四 如： max Z=2x.+r. 密飞性)：设了和7分别是问题 (原) 反 5≥0，x20 C下sTh,即2cx,s2yb 无界性 无界 巴和存 关于无界性有如下结论 mimp=4男+2y: 值的个 +:22 这一性质说明了两个线性规划互为对偶时，求最大值的 对) 120,520 行 能的目标： 行解 问题无界 樵男周乱，0康幕 定理3最优性判别定理 素和”分别是P和D的可行解粗 mx Z=x+2x+3x+4x [x1+2x2+2x+3x,≤20 则X'、Y分别是问题P和D的最优解 (P) 2x,+x1+3x,+2x,≤20 4、对偶定理（强对偶性）： (20 若一对对偶问题P和D都有可行解，则它们都有最 试估计它们目标函数的界，并验证弱对偶性原理。 优解，且目标通数的最优值必相等 A兰
2019/6/20 2 2.1 对偶问题的提出—关系 原问题（或对偶问题） 对偶问题（或原问题） 目标函数 目标函数 变量(n个) ≥ 0 ≤ 0 无约束 ≥ ≤ = 约束条件 (n个) 约束条件 (m个) ≤ ≥ = ≥ 0 ≤ 0 无约束 变量(m个) 约束条件右端项 目标函数变量的系数 目标函数变量的系数 约束条件右端项 max z min 2.2 线性规划的对偶理论 线性规划的对偶理论包括四个基本定理。 定理1 对称性定理：对偶问题的对偶是原问题。 min Z’= - CX s.t. - AX≤- b X ≥0 min W= Y b s.t. YA ≥ C Y ≤ 0 max Z=C X s.t. AX≥b X ≥0 对偶的定义 对偶的定义 max W’ = -Yb s.t. YA≥ C Y ≤ 0 定理2 弱对偶原理（弱对偶性）：设 和 分别是问题（P） 和（D）的可行解，则必有 __ X __ Y = = n j m i j j ibi C X Y b c x y 1 1 __ __ ,即 推论⑴ 若 和 分别是问题（P）和（D）的可行解，则 是（D）的目标函数最小值的一个下界； 是（P）的目标 函数最大值的一个上界。 __ C X Y b __ __ X __ Y 这一性质说明了两个线性规划互为对偶时，求最大值的 线性规划的任意目标值都不会大于求最小值的线性规划 的任一目标值，不能理解为原问题的目标值不超过对偶 问题的目标值。 推论⑵ 在一对对偶问题 （P）和（D）中，若其中一 个问题可行但目标函数无界， 则另一个问题不可行；反之 不成立。这也是对偶问题的 无界性。 关于无界性有如下结论： 问题无界 无可 行解 无可 行解 问题无界 原问题 对偶问题 − − = + 0, 0 2 4 max 2 1 2 1 2 1 2 1 2 x x x x x x Z x x 无界 如： （原） − − + = + 0, 0 1 2 min 4 2 1 2 1 2 1 2 1 2 y y y y y y W y y 无可 行解 （对） 推论⑶ 在一对对偶问题（P）和（D）中，若一个可行 （如P），而另一个不可行，（如D），则该可行的问题无 界。 例 + + + + + + = + + + − 0 2 3 2 20 2 2 3 20 max 2 3 4 1 4 1 2 3 4 1 2 3 4 1 2 3 4 x x x x x x x x x Z x x x x 试估计它们目标函数的界，并验证弱对偶性原理。 （P） 定理3 最优性判别定理： 若 X* 和 Y* 分别是 P 和 D 的可行解且 CX* = Y* b， 则X* 、Y*分别是问题 P和D 的最优解。 4、对偶定理（强对偶性）： 若一对对偶问题 P 和 D 都有可行解，则它们都有最 优解，且目标函数的最优值必相等
2019/6/20 题P和D的可行解，则它们分别 或yX,=0 A-C)X=0或Y,X=0 同时成立 出对对偶问题的关系，只能有下面三种 X.,Y测余变量 常分为x和则e有0 不 ②一个问题无界，则另一个问题无可行解： 严格等式约束称为紧约束所以有如下推论： ③两个都无可行解。 A 原问题与对偶问题解的对应头杂 2.3对偶问题的经济解释—影子价格 月与的 定义：在一对P和D中，若P的某个的束条件的 变量称为第个约束条件的影价 有最元解无界无可后 又称为边际价格。 原有量优餐一定不可能不可能 max Z=CX min W=Yb 月天手不不鞋 可能 无可行黑不可能可能 可能 X20 △兰 A性 2.3对偶问题的经济解释—影子价格 2.3对偶问题的经济解释—影子价格 是一个 影子价格的经济含义 料：髻子价格是对现有变源实现最大效益时的 用源 若租费高于某设备的影子价 素标意化1个单位对日标1产生的影响，称？为 宜出租 书一 生若B是最优基。 广为影子价格向量。 宜买进。 A A性
2019/6/20 3 推论⑷ 若 P 和 D 的任意一个有最优解，则另一个 也有最优解，且目标函数的最优值相等。 综上所述，一对对偶问题的关系，只能有下面三种 情况之一出现： ① 都有最优解，分别设为X* 和 Y*，则必有CX* =Y*b； ② 一个问题无界，则另一个问题无可行解； ③ 两个都无可行解。 5、互补松弛定理： 设X*和Y*分别是问题 P 和 D 的可行解，则它们分别 是最优解的充要条件是 剩余变量 或 或 s s s s X Y Y A C X Y X Y b AX Y X . ( ) 0 0 ( ) 0 0 − = = − = = 同时成立 一般而言，我们把某一可行点（如X*和Y* ）处的严格 不等式约束（包括对变量的非负约束）称为松约束，而把 严格等式约束称为紧约束。所以有如下推论： 设一对对偶问题都有可行解，若原问题的某一约束是某 个最优解的松约束，则它的对偶约束一定是其对偶问题最 优解的紧约束。 原问题与对偶问题解的对应关系 问 题 与 解 的 对 偶 问 题 状 态 有 最 优 解 无 界 无 可 行 解 有 最 优 解 一 定 不 可 能 不 可 能 无 界 不 可 能 不 可 能 可 能 原 问 题 无 可 行 解 不 可 能 可 能 可 能 定义：在一对 P 和 D 中，若 P 的某个约束条件的 右端项常数bi 增加一个单位时，所引起的目标函数最 优值Z* 的改变量y * i 称为第 i 个约束条件的影子价格， 又称为边际价格。 = = 0 D 0 max min Y YA C X AX b P Z CX W Yb 2.3 对偶问题的经济解释——影子价格 2.3 对偶问题的经济解释——影子价格 影子价格 —— 是一个向量，它的分量表示最优目标 值随相应资源数量变化的变化率。 若x *,y * 分别为（LP）和（DP）的最优解， 那么， c T x * = b T y * 。 根据 f = b Ty *=b1y1 *+b2y2 *++bmym * 可知 f / bi = yi * yi * 表示 bi 变化1个单位对目标 f 产生的影响，称 yi * 为 bi的影子价格。 注意：若 B 是最优基， y * 为影子价格向量。 2.3 对偶问题的经济解释——影子价格 影子价格的经济含义 (1)影子价格是对现有资源实现最大效益时的 一种估价 企业可以根据现有资源的影子价格，对资源 的使用有两种考虑：第一，是否将设备用于外加 工或出租，若租费高于某设备的影子价格，可考 虑出租该设备，否则不宜出租。第二，是否将投 资用于购买设备，以扩大生产能力，若市价低于 某设备的影子价格，可考虑买进该设备，否则不 宜买进
2019/6/20 2 的最优解司知，在最优解的 况 有关 该从影子价格的 =..+6y. 价格不是 周看是，以2， ,的函数 △图 2.3灵敏度分析(Sensitivity or what-f 学用 从 变 这 语局指对系统或事物因周条件变化所表现出 代有可能把 纯形表进 之然会提出这样的量 生变 优牙保持采变 分 在这里，仅介组日标函数系数和资源约束的灵敏度分 目标函数系数的灵敏度分析 例Wyndor玻璃制品公司产品组合问题 改变目标系数（单位利润）会怎样？ 。单个系斯发生恋化 ·多个系数同时发生变化 门的单位利洞P,-S300降P,S200, 面量优解 数雀相应地发生了变化 A丝 公 4
2019/6/20 4 19 （2） 影子价格表明资源增加对总效益产生的 影响。根据推论“设x 0和y 0分别为原规划（P）和 对偶规划（D）的可行解，当cx 0=b Ty 0时，x 0、y 0 分别是两个问题的最优解”可知，在最优解的情 况下，有关系 因此，可以将z *看作是bi ,i=1,2，… ,m的函数， 对bi求偏导数可得到 这说明，如果右端常数增加一个单位，则目标函 数值的增量将是 • 影子价格反映了不同的局部或个体的增量可以获得不同的 整体经济效益。如果为了扩大生产能力，考虑增加设备， 就应该从影子价格高的设备入手。这样可以用较少的局部 努力，获得较大的整体效益。 • 需要指出，影子价格不是固定不变的，当约束条件、产品 利润等发生变化时，有可能使影子价格发生变化。另外， 影子价格的经济含义（2），是指资源在一定范围内增加 时的情况，当某种资源的增加超过了这个“一定的范围” 时，总利润的增加量则不是按照影子价格给出的数值线性 地增加。这个问题还将在灵敏度分析一节中讨论。 2.3 灵敏度分析(Sensitivity or what-if) • 灵敏度分析，是指对系统或事物因周围条件变化所表现出 的敏感性程度的分析。 • 在前面讲的线性规划问题中，通常都是假定问题中的 aij,bi,cj系数是已知的常数，但实际上这些参数都是一些 估计或预测的数字。在现实中，如果市场条件变化，cj值 就会发生变化；如果工艺技术条件改变，则aij就会变化； 如果资源的可用量发生变化，则bi也会发生变化。因此就 必然会提出这样的问题，即当这些参数中的一个或几个发 生变化时，问题的最优解会有什么变化，或者说，当这参 数在一个多大的范围内变化时问题的最优解才会保持不变。 这就是灵敏度分析所要研究解决的问题。 • 当然，如果线性规划问题中的一个或几个参数变化时，完 全可以用单纯形法从头计算，看最优解有无变化，但这样 做既麻烦又没有必要。因为由单纯形的迭代过程我们知道， 线性规划的求解是从一组基向最变换为另一组基向量，其 中每步迭代得到的数字只随着基向量的不同选择而有所改 变，因此完全有可能把个别参数的变化直接在获得最优解 的最终单纯形表上反映出来。这样就不需要从头计算，而 只需对获得最优解的单纯形表进行审查，看一些数字变化 后是否仍满足最优解的条件，如果不满足的话，再从这个 表开始进行迭代计算，求得最优解即可。这也就是灵敏度 分析。 • 在这里，仅介绍目标函数系数和资源约束的灵敏度分 析。 ▪ 单个系数发生变化 ▪ 多个系数同时发生变化 目标系数代表对未来收益情况（不可控环境因 素）的预期，相应的灵敏度分析是考察环境的不确定 性或变化对最优解有什么影响。 目标函数系数的灵敏度分析 例 Wyndor 玻璃制品公司产品组合问题 改变目标系数（单位利润）会怎样？ 门的单位利润PD =$300降到PD =$200， 而最优解保持不变！ （只是目标函数值相应地发生了变化） 3 4 5 6 7 8 9 10 11 12 B C D E F G Doors Windows Unit Profit $200 $500 Hours Hours Used Available Plant 1 1 0 2 <= 4 Plant 2 0 2 12 <= 12 Plant 3 3 2 18 <= 18 Doors Windows Total Profit Units Produced 2 6 $3,400 Hours Used Per Unit Produced
2019/6/20 例Wyndor玻璃制品公司产品组合问题 例1 Wyndor玻璃制品公司产品组合何题 改变目标系数（单位利润）会怎样？ 改变目标系数（利润）会怎样？ 不 例Wndor玻璃制品公司产品组合问题 案例l:Wyndor玻璃制品公司产品组合问题 利用Excel Solver进行灵敏度分析 目标系数（单位利润）变化对最优解的影响 wndr Dataer 例Wyndor玻璃制品公司产品组合问题 例Wyndor玻璃制品公司产品组合问题 两个目标系数（利润）同时变化又会怎样？ 灵敏度分析结果 自前绿优擦门 最后三栏表示了门窗单位利润的景优减（可增加减少量） 400. 而最优解保持不变1
2019/6/20 5 例 Wyndor 玻璃制品公司产品组合问题 改变目标系数（单位利润）会怎样？ 门的单位利润PD =$300升到 PD =$500，而最优解保持不变！ 3 4 5 6 7 8 9 10 11 12 B C D E F G Doors Windows Unit Profit $500 $500 Hours Hours Used Available Plant 1 1 0 2 <= 4 Plant 2 0 2 12 <= 12 Plant 3 3 2 18 <= 18 Doors Windows Total Profit Units Produced 2 6 $4,000 Hours Used Per Unit Produced 例1 Wyndor 玻璃制品公司产品组合问题 门的单位利润PD =$300升到 PD =$1000时，最优解发生变化！ 3 4 5 6 7 8 9 10 11 12 B C D E F G Doors Windows Unit Profit $1,000 $500 Hours Hours Used Available Plant 1 1 0 4 <= 4 Plant 2 0 2 6 <= 12 Plant 3 3 2 18 <= 18 Doors Windows Total Profit Units Produced 4 3 $5,500 Hours Used Per Unit Produced 改变目标系数（利润）会怎样？ 例 Wyndor 玻璃制品公司产品组合问题 目标系数（单位利润）变化对最优解的影响 案例1：Wyndor 玻璃制品公司产品组合问题 利用Excel Solver进行灵敏度分析 Doors Windows Unit Profit $300 $500 Hours Hours Used Available Plant 1 1 0 2 <= 4 Plant 2 0 2 12 <= 12 Plant 3 3 2 18 <= 18 Doors Windows Total Profit Units Produced 2 6 $3,600 Hours Used Per Unit Produced 例 Wyndor 玻璃制品公司产品组合问题 灵敏度分析结果 Adjustable Cells Final Reduced Objective Allowable Allowable Cell Name Value Cost Coefficient Increase Decrease $C$12 Units Produced Doors 2 0 300 450 300 $D$12 Units Produced Windows 6 0 500 1E+30 300 最后三栏表示了门窗单位利润的最优域（可增加/减少量） 当前最优解 例 Wyndor 玻璃制品公司产品组合问题 两个目标系数（利润）同时变化又会怎样？ 门的单位利润PD =$300升到 PD =$450，窗的单位利润PW=$500降到 PW=$400，而最优解保持不变！ 3 4 5 6 7 8 9 10 11 12 B C D E F G Doors Windows Unit Profit $450 $400 Hours Hours Used Available Plant 1 1 0 2 <= 4 Plant 2 0 2 12 <= 12 Plant 3 3 2 18 <= 18 Doors Windows Total Profit Units Produced 2 6 $3,300 Hours Used Per Unit Produced