第2章 对偶理论与灵敏度分析.ppt

1、第二章 对偶理论与灵敏度分析,讲授：郝海 日期：2006-10,目 录,1线性规划的对偶问题 2对偶问题的基本性质 3影子价格 4对偶单纯形法 5灵敏度分析 6对偶的经济解释,线性规划的对偶问题,一、相关概念 二、对偶问题的提出 三、对偶问题的定义 四、对偶关系对应表,相 关 概 念,转置矩阵： 将一个mn矩阵A的行换成同序数的列而得到的新矩阵，称为矩阵A的转置矩阵，记为AT。,逆矩阵：设有n阶方阵A，如果存在n阶方阵B，满足AB=BA=E，则称A阵是可逆的，B是A的逆矩阵，记做B=A-1。,相 关 概 念,相 关 概 念,矩阵的运算：矩阵的加法，矩阵的减法， 矩阵的乘法,对偶问题的提出,美佳

2、公司利用该公司资源生产两种家电产品。,设：y1表示单位时间（h）设备A的出让代价； y2表示单位时间（h）设备B的出让代价; y3表示调试工序的出让代价。 已知：美佳公司用6小时设备A和l小时调试可生 产一件家电I，盈利2元；用5小时设备A，2小时设备B及14小时调试可生产一件家电II，盈利1元。,由此y1，y2，y3的取值应满足:,该公司希望用最小代价把美佳公司的全部资源收买过来。,因此，线性规划模型为：,LP2,原问题,对偶问题,LP2,LP2,对偶问题的定义,原始问题 max z=CX s.t.AX b X 0,对偶问题 min W=bTY s.t. ATY CT Y 0,对偶理论的基本

3、思想,每一个线性规划问题都存在一个与其对偶的问题，在求出一个问题的解的时候，也同时给出了另一个问题的解。,对偶单纯形法基本原理,决策变量的检验数可写成：,CBB-1称为单纯形乘子,C -CB B 1A0,-CB B 10,若令 y= CBB-1,则,显然y= CBB-1是其对偶问题的可行解，即 原问题检验数的相反数恰好是其对偶问题的一个可行解！,代入,对偶问题 min W=bT y s.t. A y C y 0,得：,也就是说：当原问题为最优解时，这时对偶问题为可行解，且两者具有相同的目标函数值，对偶问题的解也为最优解.,将这个解代入对偶问题的目标函数值，有：,原问题的松弛变量对应着其对偶问题

4、的决策变量！,互为对偶问题变量的对应关系,对偶问题的剩余变量 y4 y5,对偶问题变量 y1 y2 y3,原问题的松弛变量 x3 x4 x5,原问题变量 x1 x2,原问题最终表,对偶问题最终表,若存在对偶问题的一个可行基B，只要令XB B-1b 0 ,则原问题也有可行解,且同为最优解。,互为对偶问题变量的对应关系可以看出：,只需要求出原问题（对偶问题）的最优解，从最优解的单纯形表中就可以同时得到其对偶问题（原问题）的最优解。,对偶单纯形法的基本原理,例1,1 2 加工能力(小时/天) A 2 2 12 B 1 2 8 C 4 0 16 D 0 4 12 2 3,写出原问题与对偶问题,设x1

5、， x2 为产品1，2的产量,maxZ= 2x1 +3x2,设 ：y1 , y2 , y3 , y4分别为单位时间内出让A, B, C, D设备的单价,minW=bTy,ATy CT,maxZ= 2x1 +3x2,原问题,对偶问题,写出下面问题的对偶规划,例2,3x1 2x2 =7,-3x1 +2x2 -7,对偶问题,令 y1 = y1 -y1 ,7y1,对偶关系对应表,原(对偶)问题 对偶(原)问题 目标函数类型 max min 目标函数系数 目标函数系数 右边项系数 与右边项的对应关系 右边项系数 目标函数系数 变量数与约束数 变量数n 约束数 n 的对应关系 约束数m 变量数m 原问题变

6、量类型与 变量 0 约束 对偶问题约束类型 变量 0 约束 的对应关系 变量无限制 约束 原问题约束类型与 约束 变量 0 对偶问题变量类型 约束 变量 0 的对应关系 约束 变量无限制,minW=7y1 +9y2,原问题,对偶问题,请写出以下问题的对偶问题,maxZ=180y1+60y2+240y3,S.t. y1+2y2+5y3 3 2y1-3y2+3y3 9 3y1+y2=4 y1无约束,y2 0,y3 0,若x是原问题的可行解，y是对偶问题的可行解。则有 cxyb,二. 弱对偶性：,对偶问题的基本性质,一 . 对称性 ：,对偶问题的对偶是原问题,推论(1)： 原问题任一可行解的目标函数

7、值是其对偶问题目标函数值的下界，反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。,推论(2)： 若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。注 ： 其逆不成立。,推论(3)：若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界，反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。,弱对偶性的三个推论,AZ=W B,设x是原问题的可行解，y是对偶问题的可行解。 当 cx= yb 时 x, y 是最优解。,三 . 最优性,若原问题及其对偶问题均具有可行解，则两者均具有最优解且它们最优解的目标函数值相等。,四 . 强对偶性（对偶定理）,五.互补

8、松弛性（松紧定理）,在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。也即：,五.互补松弛性（松紧定理）,在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。也即：,推论(3)：若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界，反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。,证明：,1.证明原问题有可行解,2.写出其对偶问题：,1 ）说明原问题和对偶问题都有最优解. 2

9、 ）求原问题和对偶问题的最优目标函数值的一个上界和下界.,四 . 强对偶性（对偶定理）若原问题及其对偶问题均具有可行解，则两者均具有最优解且它们最优解的目标函数值相等。,推论(1)： 原问题任一可行解的目标函数值是其对偶问题目标函数值的下界，反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。,1.证明原问题有可行解,解：,1 ）说明原问题和对偶问题都有最优解.,2. 对偶问题有可行解：,2）求原问题和对偶问题的最优目标函数值的一个上界和下界.,用互补松弛定理计算对偶问题的最优解,互补松弛定理:在线性规划问题的最优解中，,已知原问题,影子价格,式中bi是线性规划原问题约束条件的右端项

10、，它代表第i种资源的拥有量；对偶变量yi*的意义代表在资源最优利用条件下对单位第i种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格(shadow price)。,几点说明：,1资源的影子价格是未知数，有赖于企业资源状况。,2影子价格是一种边际价格, 相当于在资源得到最优利用的生产条件下，每增加一个单位时目标函数z的增量。,3资源的影子价格实际上又是一种机会成本。,4生产过程中如果某种资源未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。,5对线性规划问题的求解是确定资源的最优分配方案

11、，而对于对偶问题的求解则是确定资源的恰当估价。,对偶单纯形法,基本思路：在迭代过程中保持原问题的检验数为非正，逐步替换负基变量，从而得到最优解。,即保持对偶问题有可行解,使原问题具有可行解,检验数为非正,替换负基变量,对偶单纯形法计算步骤,1. 列出初始单纯形表，且检验数非正。,2. b值有否为负，无，计算结束。有，转3,5.以ars为主元素，进行迭代变换。,6 . 返 3，直到b 0为止。,用对偶单纯形法求解下述线性规划问题,例,化标准型：,整理得：,解：,在得到原始可行解时同时得到对偶可行解，已获得最优解： （y1, y2, y3, y4, y5）=（0,1/4, 1/2,0,0） max

12、 w=17/2 对偶问题的最优解为： （x1, x2, x3 ）=（ 7/2, 3/2, 15/2） min z=17/2,例:(初始解原始、对偶都不可行的问题),先解决对偶可行性,已得到对偶可行解，再用对偶单纯形法求解,在得到原始可行解时同时得到对偶可行解，已获得最优解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） minz=17 对偶问题的最优解为： （y1, y2, y3）=（7,5, 10） 即（y1, y2, y3）=（7,5, 10） maxw=17,对偶单纯形法中出现的一些情况,2.对偶单纯形法与原始单纯形法的比较：,1.对于对偶问题有

13、可行解，而原问题无可行解的判断。,对偶单纯形法的优点：,用对偶单纯形法求解线性规划问题时，当约束条件为“”时，不必引进人工变量，使计算简化。,对偶单纯形法的应用范围：,在初始单纯形表中其对偶问题应是基可行解这点，对多数线性规划问题很难实现。因此对偶单纯形法一般不单独使用，多用于灵敏度分析等用途。,灵敏度分析,当这些参数中的一个或几个发生变化时，问题的最优解会有什么变化，或者这些参数在一个多大范围内变化时，问题的最优解不变。,灵敏度分析的定义,灵敏度分析所要研究解决的问题,是指对系统或事物因周围条件变化显示出来的敏感程度的分析。,条件变化,aij，bi，cj,最优解,多大范围内变化,灵敏度分析原

14、理,单纯形法的迭代计算是从一组基向量变换为另一组基向量，表中每步迭代得到的数字只随基向量的不同选择而改变，因此有可能把个别参数的变化直接在计算得到最优解的最终单纯形表上反映出来。,数字只随基向量的不同选择而改变,最终单纯形表,1将参数的改变计算反映到最终单纯形表上来：,灵敏度分析的步骤,最终单纯形表,B-1B,3检查对偶问题是否仍为可行解； 4按下表所列情况得以结论和决定继续计算的步骤。,2检查原问题是否仍为可行解；,灵敏度分析的任务,(1)、参数A，b，C在什么范围内变动，对当前方案无影响？,(2)、参数A，b，C中的一个(几个)变动，对当前方案的影响？,(3)、如果最优方案改变，如何用简便

15、方法求新方案？,一、分析Cj的变化,Cj的变化仅仅影响到检验数(Cj-Zj)的变化。所以将Cj的变化直接反映到最终单纯形表中，只可能出现前两种情况。,Cj的变化仅仅影响到检验数(Cj-Zj)的变化,最终单纯形表,例:,(1)若家电I的利润降至1. 5元件，而家电的利润增至2元件时，美佳公司最优生产计划有何变化； (2)若家电I的利润不变，则家电II的利润在什么范围内变化时，则该公司的最优生产计划将不发生变化？,在第一章例1的美佳公司例子中:,(1) 若家电I的利润降至1. 5元件，而家电的利润增至2元件时，美佳公司最优生产计划有何变化；,最终单纯形表如下：,原问题可行，对偶问题不可行,用单纯形

16、法继续迭代求解。,将家电I，II的利润变化cj直接反映到最终单纯形表中。,-2 0 -1 1/8 -9/4,为使表中的解仍为最优解，应有,即家电II的利润C2的变化范围应满足：,2) 若家电I的利润不变，则家电II的利润在什么范围内变化时，则该公司的最优生产计划将不发生变化？,0 0 0 -1/4+1/4 -1/2-3/2 ,设家电II的利润为(1+)元，反映到最终单纯形表中为：,二、分析bi的变化,bj的变化在实际问题中反映为可用资源数量的变化。,可能出现的解的情况：,例：,若：(1)若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32小时，分析公司最优计划的变化； (2)若设备A

17、和B每天可用能力不变，则调试工序能力在什么范围内变化时，问题的最优基不变。,在上述美佳公司的例子中，,解：,1.求bj的变化量。,2.列出最终单纯表。,1/2,原问题不可行，对偶问题可行，用对偶单纯形法继续迭代求：,3.在最终单纯表中直接表现bj的变化量：bbb,35/2 11/2 -1/2,单纯形表中b列数字为：,（2）调试工序能力在什么范围内变化时，问题的最优基不变,解：,三、增加一个变量xj的分析,增加一个变量在实际问题中反映为增加一种新的产品。,可能出现的解的情况：,其分析步骤为：,例：,在美佳公司例子中，设该公司又计划推出新型号的家电III，生产一件所需设备A、B及调试工序的时间分别

18、为3小时、4小时、2小时，该产品的预期盈利为3元件。试分析该种产品是否值得投产，如投产，对该公司的最优生产计划有何变化。,解：,1.计算由于增加新产品导致的参数改变量6，p6：,6,2.在最终单纯表中直接表现c6，6，p6的变化量：,3 x6 -7 0 2 1,原问题可行，对偶问题不可行，用原始单纯形法继续迭代求解,四、分析参数aij的变化,1.变量xj在最终单纯形表中为非基变量； 分析步骤与增加变量的情况雷同。 可能出现的解的情况：,aij的变化使线性规划的约束系数矩阵A发生变化。,出现的两种情况：,2.变量xj在最终单纯形表中为基变量。,用对偶单纯形法继续解迭代求最优解,在美佳公司的例子中

19、，若家电II每件需设备A，B和调试工时变为8小时、4小时、1小时，该产品的利润变为3元/件，试重新确定该公司最优生产计划。,：将生产工时变化后的新家电II看作是一种新产品，生产量为x2。,例:,解,因x2已变换为x2 ，故用单纯形算法将x2替换出基变量中的x2 ，并在单纯形表中不再保留x2。,在最终单纯表中直接表现aij的变化量：,原问题不可行，对偶问题也不可行，采用对偶单纯形法继续迭代求解。,五、增加一个约束条件的分析,先将原问题最优解的变量值代入新增的约束条件。如满足，说明新增的约束未起到限制作用，原最优解不变。 否则，将新增的约束直接反映到最终单纯形表中再进步分析。,增加一个约束条件在实

20、际问题中相当增添一道工序。 分析的方法：,例：,仍以美佳公司为例，设家电I，II经调试后，还需经过道环境试验工序。家电I每件须环境试验3小时，家电II每件2小时，又知环境试验工序每天生产能力为12小时。试分析增加该工序后的美佳公司最优生产计划。,0 x6 12 3 2 0 0 0 1,原问题不可行，对偶问题可行， 用对偶单纯形法继续迭代求解,参数线性规划,定义：,灵敏度分析中研究cj、bi等参数在保持最优解或最优基不变时的允许变化范围或改变到某一值时对问题最优解的影响，若C按(C+ C*)或b按(b+ b*)连续变化，而目标函数值z() 是参数的线性函数，称这样的规划问题为参数线性规划问题。,参数规划的形式：,max z（ ）= (C+ C*) X s.t.AX b X 0,max z（ ）= (b+ b*) X s.t.AX b+ b* X 0,其中，b为原问题的资源向量， b*为变动