《对偶理论与灵敏度分析》由会员分享，可在线阅读，更多相关《对偶理论与灵敏度分析（99页珍藏版）》请在金锄头文库上搜索。
1、2018/9/16,1,第二章 对偶理论与灵敏度分析,2018/9/16,2,1 线性规划问题的对偶及其变换1、线性规划对偶问题的提出线性规划对偶理论是线性规划理论中一个非常重要和有趣的概念。支持线性规划对偶理论的主要背景是，每个线性规划问题都有一个与之对应的对偶线性规划问题。线性规划问题与其对偶线性规划问题在模型的表现形式和问题的解之间存在着许多联系。我们先分析一个实际的线性规划模型与其对偶线性规划问题的经济意义。,2018/9/16,3,例 某工厂要用25个单位的A资源和15个单位的B资源生产4种产品，这4种产品的单位利润和对A资源和B资源的单位消耗量如表所示。问该工厂应如何安排生产才能使
2、工厂的总利润最大?,2018/9/16,4,现假设有一商人要向厂方购买资源A和B，问他们谈判原料价格的模型是怎样的?从拥有资源的工厂来说，是否要出售资源A和资源B取决于商人给出资源A和资源B的价格。工厂出售资源A和资源B的条件是：出售A资源和B资源的收入应不低于用同等数量资源由自己组织生产相应产品时所获得的利润。设商人开出的A资源和B资源的单位价格分别为y1和y2，则工厂在满足什么条件时可出售A资源和B资源。,2018/9/16,5,一般的，原问题：max z = CX,对偶问题：min w = Yb,2、原问题与对偶问题,AX bX 0,YA C Y 0,2018/9/16,6,一般: ma
3、x问题第i个约束取“”，则min问题第i个变量 0 ；, min问题第i个约束取“”，则max问题第i个变量 0 ；, 原问题第i个约束取等式，对偶问题第i个变量 无约束；, max问题第j个变量 0 ,则min问题第j个约束取“” ；, min问题第j个变量 0 ，则max问题第j个约束取“” ；, 原问题第j个变量无约束，对偶问题第j个约束取等式。,2018/9/16,7,2018/9/16,8,例 写出对偶问题max z = x1 + 2x2 + x32x1 + x2 62x2 + x3 8x1,x2,x3 0,2018/9/16,9,写出下述线性规划问题的对偶问题1）,2018/9/1
4、6,10,2）,2018/9/16,11,3）,2018/9/16,12,3、单纯形法的矩阵描述 （1）标准型的矩阵形式,（2）将式中矩阵写成分块矩阵形式,2018/9/16,13,（3）、将分块形式代入矩阵形式标准型，得出两个基本表达式：1）由约束条件,可得 用非基变量表示基变量的表达式：,（2-1）,2018/9/16,14,2）将式（2-1）代入目标函数的表达式，可得： 用非基变量表示目标函数的表达式：,2018/9/16,15,（4）、 单纯形表格的矩阵形式：,2018/9/16,16, 2 对偶问题的性质 Dual property,1、对称性 对偶问题的对偶为原问题.,2018/9
5、/16,17,2018/9/16,18,2018/9/16,19,推论： (1) max问题任一可行解的目标值为min问题目标值的一个下界； (2) min问题任一可行解的目标值为max问题目标值的一个上界。,2018/9/16,20,3、无界性 若原问题(对偶问题)为无界解，则对偶问题(原问题)为无可行解。,注：该性质的逆不存在。若原(对偶)问题为无可行解，对偶(原问题)问题或为无界解，或为无可行解。,2018/9/16,21,例如：,无可行解,必有无界解。,2018/9/16,22,4、最优性 设X*，Y*分别为原问题和对偶问题可行解，当CX*=Y*b时， X*，Y*分别为最优解。,201
6、8/9/16,23,5、对偶定理 若原问题有最优解，那么对偶问题也有最优解，且目标值相等。,2018/9/16,24,Y*为对偶问题的最优解，且原问题和对偶问题 的目标值相等。 证毕,6、松弛性若X*，Y*分别为原问题及对偶问题的可行解，那么Ys*X*=0，Y*Xs*=0，当且仅当X*，Y*分别为最优解。,证明：,2018/9/16,25,将b,C分别代入目标函数：,2018/9/16,26,【例】 已知线性规划,的最优解是 求对偶问题的最优解。,2018/9/16,27,【解】对偶问题是,y1=1,y2=1, 对偶问题的最优解为Y=（1，1），最优值w=26。,2018/9/16,28,【例
7、】 已知线性规划,的对偶问题的最优解为Y=（0，2），求原问题的最优解。,2018/9/16,29,【解】,2018/9/16,30,x 1=5,x 3=1, 所以原问题的最优解为 X=（5，0，1），最优值Z=12。,因为y20，所以原问题第二个松弛变量 =0，而y1=0、y2= -2，松弛变量 故x2=0,2018/9/16,31,【例】 证明下列线性规划无最优解：,2018/9/16,32,将三个约束的两端分别相加得 而第二个约束有y21，矛盾，故对偶问题无可行解，因而原问题具有无界解，即无最优解。,【证】容易看出X=（4，0，0）是一可行解，故问题可行。对偶问题,2018/9/16,3
8、3,例：已知线性规划问题Min z = 2x1+3x2+5x3+2x4+3x5s.t. x1+x2+2x3+x4+3x5 42x1-x2 +3x3 +x4+x5 3xj 0 j=1,2,3,4,5已知其对偶问题的最优解为： y1=4/5, y2=3/5, z=5。 试用对偶理论找出原问题的最优解。,2018/9/16,34,7、原问题检验数与对偶问题解的关系,(1)原问题非最优检验数的负值为对偶问题的一个基解。(2)原问题最优检验数的负值为对偶问题的最优解。 设原问题是 max z=CX; AX+XS=b; X,XS0 它的对偶问题是 min =Yb; YA-YS=C; Y,YS0 则原问题单
9、纯形表的检验数行对应其对偶问题的一个基解，其对应关系见表1。,2018/9/16,35,表1 对应关系,YS1是对应原问题中基变量XB的剩余变量， YS2是对应原问题中非基变量XN的剩余变量。,2018/9/16,36,证: 设B是原问题的一个可行基，于是A=(B,N)；原问题可以改写为,max z=CBXB+CNXN BXB+NXN+XS=b XB，XN，XS0 相应地对偶问题可表示为min =YbYB-YS1=CB (2-17)YN-YS2=CN (2-18) Y，YS1,YS20 这里YS=(YS1，YS2)。,2018/9/16,37,当求得原问题的一个解：XB=B-1b 其相应的检验
10、数为CN-CBB-1N与 -CBB-1 现分析这些检验数与对偶问题的解之间的关系：令Y=CBB-1，将它代入(2-17)式，(2-18)式得 YS1=0, -YS2=CN-CBB-1N 证毕,2018/9/16,38,8 线性规划对偶问题的经济解释影子价格线性规划对偶问题中yi的值代表对第i种资源的估价。这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影子价格”。在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企业应买进该资源用于扩大生产；而当某种资源的市场价高于企业影子价格时，企业的决策者应把已有的资源卖掉。,2018/9/16,39,对偶单纯形法的基本思想:对偶单纯
11、形法的基本思想是：从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。,3 对偶单纯形法,2018/9/16,40,如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。,2018/9/16,41,应用前提：有一个基，其
12、对应的基满足: 单纯形表的检验数行全部非正（对偶可行）； 变量取值可有负数（非可行解）。注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。,2018/9/16,42,1.建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转2；2.若b0,则得到最优解,停止;否则,若有bk0则选k行的基变量为出基变量,转33.若所有akj0( j = 1,2,n )，则原问题无可行解,停止;否则,若有akj0 则选 =minj / akjakj0=r/akr那么 xr为进基变量,转4；4.以akr为转轴元,作矩阵行变换使其变为1,该列其他元变为0,转2。,对偶单纯形法求解线性规划问题
13、 过程：,2018/9/16,43,【例】用对偶单纯形法求解min w = 2x1 + 3x2 + 4x3x1 + 2x2 + x3 12x1 - x2 + 3x3 4x1,x2,x3 0,2018/9/16,44,2018/9/16,45,x4,x5 0 最优,最优解：x1* = 2，x2* = 0，x3* = 0，x4* = 1，x5* = 0 目标值：w* = -z* = 4,2018/9/16,46,例：求解线性规划问题：,2018/9/16,47,2018/9/16,48,2018/9/16,49,单纯形法和对偶单纯形法步骤,2018/9/16,50,4 灵敏度分析一、灵敏度分析的含
14、义和内容1、什么是灵敏度分析？研究线性规划模型某些参数或限制量的变化对最优解的影响及其程度的分析过程称为灵敏度分析。,2018/9/16,51,2、灵敏度分析的内容： 目标函数的系数变化对最优解的影响； 约束方程右端系数变化对最优解的影响； 约束方程组系数阵变化对最优解的影响 ；,回答两个问题：,2018/9/16,52,这些系数在什么范围内发生变化时，最优基不变（即最优解或最优解结构不变）？ 系数变化超出上述范围时，如何用最简便的方法求出新的最优解？,二、 手工进行灵敏度分析的基本原则1、在最优表格的基础上进行；2、尽量减少附加计算工作量；,2018/9/16,53,分析 变化对最优解的影响
15、。,三、灵敏度分析,2018/9/16,54,2018/9/16,55,例1 已知下述问题的最优解及最优单纯形表,2018/9/16,56,最优单纯形表如下:,2018/9/16,57,由最优单纯形表得:,2018/9/16,58,2018/9/16,59,不可行!,用对偶单纯形法计算,2018/9/16,60,3/4,-2,2018/9/16,61,2018/9/16,62,例2 求例1 c4的变化范围,使最优解不变.,解:,2018/9/16,63,分析:,2018/9/16,64,方法:,例3 求例1 c2的变化范围,使最优解不变.,2018/9/16,65,解:,2018/9/16,66,2018/9/16,67,分析:,2018/9/16,68,2018/9/16,69,例4 求例1 a24的变化范围,使最优解不变.,解:,2018/9/16,70,例5 在例1的基础上，企业要增加一个 新产品,每件产品需2个台时，原材料A 6kg， 原材料B 3kg，利润 5元/件，问如何安排各产 品的产量，使利润最大？ 解：,2018/9/16,71,表明生产新品有利。,2018/9/16,
