对偶理论及灵敏度分析上课

1、对偶理论与灵敏度分析对偶理论与灵敏度分析 1线性规划的对偶问题线性规划的对偶问题 2对偶问题的基本性质对偶问题的基本性质 3影子价格影子价格 4对偶单纯形法对偶单纯形法 5灵敏度分析灵敏度分析 6对偶的经济解释对偶的经济解释线性规划的对偶问题线性规划的对偶问题一、相关概念一、相关概念二、对偶问题的提出二、对偶问题的提出三、对偶问题的定义三、对偶问题的定义四、对偶关系对应表四、对偶关系对应表相相 关关 概概 念念转置矩阵：转置矩阵： 将一个将一个mn矩阵矩阵A的行换成同序数的列而的行换成同序数的列而得到的新矩阵，称为矩阵得到的新矩阵，称为矩阵A的转置矩阵，记为的转置矩阵，记为AT。逆矩阵：逆矩阵

2、：设有设有n阶方阵阶方阵A，如果存在，如果存在n阶方阵阶方阵B，满足，满足AB=BA=E，则称，则称A阵是可逆的，阵是可逆的，B是是A的逆矩阵，记做的逆矩阵，记做B=A-1。矩阵的运算：矩阵的运算：矩阵的加法，矩阵的减法，矩阵的乘法矩阵的加法，矩阵的减法，矩阵的乘法对偶问题的提出对偶问题的提出美佳公司利用该公司资源生产两种家电产品。美佳公司利用该公司资源生产两种家电产品。I IIIII每天可用每天可用 能力能力设备设备A A（h h）设备设备B B（h h）调试工序（调试工序（h h）0 06 61 15 52 21 1151524245 5利润（元）利润（元）2 21 10,52426155

3、2max1212121221xxxxxxxxxzLP设：设：y1表示单位时间（表示单位时间（h）设备）设备A的出让代价；的出让代价； y2表示单位时间（表示单位时间（h）设备）设备B的出让代价的出让代价; y3表示调试工序的出让代价。表示调试工序的出让代价。已知：美佳公司用已知：美佳公司用6小时设备小时设备A和和l小时调试可生小时调试可生 产一件产一件家电家电I，盈利，盈利2元；用元；用5小时设备小时设备A，2小时设备小时设备B及及14小时小时调试可生产一件家电调试可生产一件家电II，盈利，盈利1元。元。由此由此y1，y2，y3的取值应满足的取值应满足: 该公司希望用最小代价把美佳公司的全部资

4、源收买过该公司希望用最小代价把美佳公司的全部资源收买过来。来。因此，线性规划模型为：因此，线性规划模型为：1252632132yyyyy32152415minyyyz32152415minyyyz0,1252632132132yyyyyyyyLP2原问题原问题对偶问题对偶问题0,524261552max1212121221xxxxxxxxxzLP32152415minyyyz0,1252632132132yyyyyyyyLP2(2 1) x1x20 5 21 115245x1x20 6 15 2 121y1y2y3(15 24 5) y1y2y30,524261552max1212121221

5、xxxxxxxxxzLP32152415minyyyz0,1252632132132yyyyyyyyLP2对偶问题的定义对偶问题的定义原始问题原始问题max z=CXs.t.AX bX 0对偶问题对偶问题min W=bTYs.t. ATY CTY 0CTATbTminmnmaxbACmn例例1 1 2 加工能力加工能力(小时小时/天天) A 2 2 12 B 1 2 8 C 4 0 16 D 0 4 12 2 3销售收入销售收入产品产品设备设备写出原问题与对偶问题写出原问题与对偶问题设设x1 ， x2 为产品为产品1，2的产量的产量 2x1 +2x2 12 x1 +2x2 84x1 16 4x

6、2 12x1 x2 0maxZ= 2x1 +3x2 (2 3) Cx1x2X2 2 1 2 4 0 0 4 Ax1x2X 1281612b设设 ：y1 , y2 , y3 , y4分别为单位时间内出让分别为单位时间内出让A, B, C, D设备设备的单价的单价y1 y2y3 y4 2y1 +y2 +4y3 22y1 +2y2 +y4 3y1 y4 0minW=12y1+8y2 +16y3+12y4minW=bTyy1 y2 y3 y4(12 8 16 12 )bTATy CT2 1 4 02 2 0 4AT 23CTmaxZ= 2x1 +3x2 2x1 +2x2 12 x1 +2x2 84x1

7、 16 4x2 12x1 x2 0 2x1 +2x2 12 x1 +2x2 84x1 16 4x2 12x1 x2 0maxZ= 2x1 +3x2 2y1 +y2 +4y3 22y1 +2y2 +y4 3y1 y4 0minW=12y1+8y2 +16y3+12y4原问题原问题 对偶问题对偶问题 写出下面问题的对偶规划写出下面问题的对偶规划例例2maxZ= 5x1 +6x2 3x1 2x2 =74x1 +x2 9x1 , x2 03x1 2x2 =73x1 2x2 73x1 2x2 7-3x1 +2x2 -73x1 2x2 7-3x1 +2x2 -74x1 +x2 9x1 , x2 0y1y1

8、 y2对偶问题对偶问题令令 y1 = y1 -y1 minW=7y1 -7y1 +9y23y1 -3y1 +4y2 5 -2y1 +2y1 +y2 6y1 , y1 , y2 0minW=7y1 +9y23y1+4y2 5 -2y1 +y2 6y1自由自由 , y2 03y1-2y17y1对偶关系对应表对偶关系对应表 原原( (对偶对偶) )问题问题 对偶对偶( (原原) )问题问题目标函数类型目标函数类型 max minmax min目标函数系数目标函数系数 目标函数系数目标函数系数 右边项系数右边项系数与右边项的对应关系与右边项的对应关系 右边项系数右边项系数 目标函数系数目标函数系数变量

9、数与约束数变量数与约束数 变量数变量数n n 约束数约束数 n n的对应关系的对应关系 约束数约束数m m 变量数变量数m m原问题原问题变量变量类型与类型与 变量变量 0 0 约束约束 对偶问题对偶问题约束约束类型类型 变量变量 0 0 约束约束 的对应关系的对应关系 变量无限制变量无限制 约束约束原问题原问题约束约束类型与类型与 约束约束 变量变量 0 0 对偶问题对偶问题变量变量类型类型 约束约束 变量变量 0 0 的对应关系的对应关系 约束约束 变量变量无限制无限制minW=7y1 +9y23y1+4y2 5 -2y1 +y2 6y1无限制无限制 , y2 0maxZ= 5x1 +6x

10、2 3x1 2x2 =74x1 +x2 9x1 , x2 0原问题原问题 对偶问题对偶问题 请写出以下问题的对偶问题请写出以下问题的对偶问题maxZ=180y1+60y2+240y3S.t. y1+2y2+5y3 3 2y1-3y2+3y3 9 3y1+y2=4 y1无约束无约束,y2 0,y3 0 对偶理论的基本思想对偶理论的基本思想 每一个线性规划问题都存在一个与其对偶的每一个线性规划问题都存在一个与其对偶的问题，在求出一个问题的解的时候，也同时给出问题，在求出一个问题的解的时候，也同时给出了另一个问题的解。了另一个问题的解。对偶单纯形法基本原理决策变量的检验数可写成：决策变量的检验数可写

11、成：CBB-1称为单纯形乘子称为单纯形乘子非基变量非基变量基变量基变量XB XNXS0 XS bB N IcjzjCB CN0基变量基变量非基变量非基变量XBXN XSCB XB B -1 bIB -1N B -1 Cjzj0= CN -CB B -1B CN -CB B -1N -CB B -1C -CB B 1A0-CB B 10A y C y 0若令若令 y= CBB-1则则显然显然y= CBB-1是其对偶问题的可行解是其对偶问题的可行解，即，即原问题检验数的相反数恰好是其对偶问题的一个可行解！原问题检验数的相反数恰好是其对偶问题的一个可行解！代入代入对偶问题对偶问题min W=bT y

12、s.t. A y C y 0得：得：C -CB B 1A0-CB B 10y AC y 0也就是说也就是说：当原问题为最优解时，这时对偶问题为可行：当原问题为最优解时，这时对偶问题为可行解，且两者具有相同的目标函数值，对偶问题的解也为解，且两者具有相同的目标函数值，对偶问题的解也为最优解最优解.将这个解代入对偶问题的目标函数值，有：将这个解代入对偶问题的目标函数值，有： 原问题的松弛变量对应着其对偶问题的决策变量！原问题的松弛变量对应着其对偶问题的决策变量！基变量基变量非基变量非基变量XBXN XSCB XB B -1 bIB -1N B -1 cjzj0CN -CB B -1N -CB B

13、-1zXCbBCbywBBB1互为对偶问题变量的对应关系互为对偶问题变量的对应关系原问题变量原问题变量松弛变量松弛变量 x1 x2x3 x4 x5 x3 15/2x1 7/2x2 3/20 01 00 11 5/4 -15/2 0 1/4 -1/2 0 -1/4 3/2cj-zj0 0 0 -1/4 -1/2 对偶问题变量对偶问题变量对偶问题剩余变量对偶问题剩余变量 y1 y2 y3 y4 y5 y2 1/4y3 1/2 5/4 1 0 15/2 0 1-1/4 1/41 /2 -3/2cj-zj-15/2 0 0-7/2 -3/2对偶问题的剩余变量对偶问题的剩余变量y4 y5对偶问题变量对偶

14、问题变量y1 y2 y3原问题的松弛变量原问题的松弛变量x3 x4 x5原问题变量原问题变量x1 x2原问题最终表原问题最终表对偶问题最终表对偶问题最终表 若存在对偶问题的一个可行基若存在对偶问题的一个可行基B B，只要令，只要令X XB B B B- -1 1b b 0 0 , ,则原问题也有可行解则原问题也有可行解, ,且且同为最优解同为最优解。互为对偶问题变量的对应关系可以看出：互为对偶问题变量的对应关系可以看出：只需要求出原问题（对偶问题）的只需要求出原问题（对偶问题）的最优解，从最优解的单纯形表中就最优解，从最优解的单纯形表中就可以同时得到其对偶问题（原问题）可以同时得到其对偶问题（

15、原问题）的最优解。的最优解。对偶单纯形法的基本原理对偶单纯形法的基本原理若若x是原问题的可行解，是原问题的可行解，y是对偶问题的可行解，是对偶问题的可行解，则有则有 cxyb 二二. 弱对偶性：弱对偶性：对偶问题的基本性质对偶问题的基本性质一一 . 对称性对称性 ：对偶问题的对偶是原问题对偶问题的对偶是原问题 设设x是原问题的可行解，是原问题的可行解，y是对偶问题的可行解。是对偶问题的可行解。 当当 cx= yb 时时 x, y 是最优解。是最优解。三三 . 最优性最优性 若原问题及其对偶问题均具有可行解，则两者若原问题及其对偶问题均具有可行解，则两者均具有最优解且它们最优解的目标函数值相等。

16、均具有最优解且它们最优解的目标函数值相等。四四 . 强对偶性（对偶定理）强对偶性（对偶定理）五五.互补松弛性（松紧定理）互补松弛性（松紧定理） 在线性规划问题的最优解中，如果对应某一约束条件在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。果约束条件取严格不等式，则其对应的对偶变量一定为零。也即：也即：njsiijijixbxay10,0即则有若0,0,1injsiijijyxbxa则有即若0isiyx因此，一定有五五.互补松弛性（松紧定理）互补松

17、弛性（松紧定理） 在线性规划问题的最优解中，如果对应某一约束条件在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。果约束条件取严格不等式，则其对应的对偶变量一定为零。也即：也即：mijiijjcyax1,0则有如果有0,1njjjjijxcya则有如果有28)4 , 4 , 0 , 0(02023220322432max3*432143214321zxxxxxxxxxxxxxxzLPi最优解为问题：已知例用互补松弛定理计算对偶问题的最优解用互补松弛

18、定理计算对偶问题的最优解互补松弛定理互补松弛定理:在线性规划问题在线性规划问题的最优解中，的最优解中，mijiijjcyax1,0则有如果有0,1njjjjijxcya则有如果有0,42333222122020min212121212121yyyyyyyyyyyy解：对偶问题为：42304214yyx有根据互补松弛定理，5/1,5/621yy解得33204213yyx有由)4 , 4 , 0 , 0(*x最优解为已知原问题最优值。为对偶问题的最优解和；285/1, 5/621yy*21285/1,5/6zyy对应目标函数值为对偶问题的可行解，经检验0,42333222122020min2121

19、21212121yyyyyyyyyyyy5/1, 5/621yy影子价格影子价格 式中式中b bi i是线性规划原问题约束条件的右端项，它代是线性规划原问题约束条件的右端项，它代表第表第i i种资源的拥有量；对偶变量种资源的拥有量；对偶变量y yi i* *的意义代表在资源的意义代表在资源最优利用条件下对单位第最优利用条件下对单位第i i种种资源的估价。这种估价不资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格而作的估价，为区别起见，称为影子价格(shadow (shadow price)

20、price)。几点说明：几点说明：1资源的影子价格是未知数，有赖于企业资源状况。资源的影子价格是未知数，有赖于企业资源状况。2影子价格是一种边际价格影子价格是一种边际价格, 相当于在资源得到最优利用的生产相当于在资源得到最优利用的生产条件下，每增加一个单位时目标函数条件下，每增加一个单位时目标函数z的增量。的增量。3资源的影子价格实际上又是一种机会成本。资源的影子价格实际上又是一种机会成本。4生产过程中如果某种资源未得到充分利用时，该种资源的影子价生产过程中如果某种资源未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已格为零；又当资源的影子价格不为零时

21、，表明该种资源在生产中已耗费完毕。耗费完毕。 5对线性规划问题的求解是确定资源的最优分配方案，而对于对对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定资源的恰当估价。偶问题的求解则是确定资源的恰当估价。对偶单纯形法v 基本思路：在迭代过程中保持原问题的检验数为非正，逐步替换负基变量，从而得到最优解。即保持对偶问题有可行解即保持对偶问题有可行解使原问题具有可行解使原问题具有可行解检验数为非正替换负基变量对偶单纯形法计算步骤对偶单纯形法计算步骤 1. 1. 列出初始单纯形表，且列出初始单纯形表，且检验数非正检验数非正。 为换出变量。对应的基变量按rriiixbBbBbB1

22、110min.3为换入变量确定按srsssrjrjjjxazcaazc0min.4 2. b 2. b值有否为负，无，计算结束。有，转值有否为负，无，计算结束。有，转3 35.以以ars为主元素，进行迭代变换。为主元素，进行迭代变换。6 . 返返 3，直到，直到b 0为止。为止。用对偶单纯形法求解下述线性规划问题用对偶单纯形法求解下述线性规划问题例例化标准型：化标准型：整理得：整理得：解：解：Cj1524500CByBby1y2y3y4y50y420-6-1100y51-5-2-101 j=cj-zj24y21/3011/6-1/600y5-1/3-50-2/3-1/31 j=cj-zj-15

23、-24-500-150-1-4024y21/4-5/410-1/41/4-5y31/215/2011/2-3/2 j=cj-zj-15/200-7/2-3/2在得到原始可行解时同时得到对偶可行解，已获得最优在得到原始可行解时同时得到对偶可行解，已获得最优解：解：（y1, y2, y3, y4, y5）= =（0,1/4, 1/2,0,00,1/4, 1/2,0,0） max w=17/2max w=17/2对偶问题的最优解为：对偶问题的最优解为：（x1, x2, x3 ）= =（ 7/2, 3/2, 15/27/2, 3/2, 15/2） min z=17/2min z=17/2对偶单纯形法的

24、优点：对偶单纯形法的优点： 用对偶单纯形法求解线性规划问题时，当约束条用对偶单纯形法求解线性规划问题时，当约束条件为件为“”时，不必引进人工变量，使计算简化。时，不必引进人工变量，使计算简化。对偶单纯形法的应用范围：对偶单纯形法的应用范围： 在初始单纯形表中其对偶问题应是基可行解这点，对在初始单纯形表中其对偶问题应是基可行解这点，对多数线性规划问题很难实现。因此对偶单纯形法一般不单多数线性规划问题很难实现。因此对偶单纯形法一般不单独使用，多用于灵敏度分析等用途。独使用，多用于灵敏度分析等用途。灵敏度灵敏度分析当这些参数中的一个或几个发生变化时，问题当这些参数中的一个或几个发生变化时，问题的最优

25、解会有什么变化，或者这些参数在一个多大的最优解会有什么变化，或者这些参数在一个多大范围内变化时，问题的最优解不变。范围内变化时，问题的最优解不变。灵敏度分析的定义灵敏度分析的定义灵敏度分析所要研究解决的问题灵敏度分析所要研究解决的问题是指对系统或事物因周围条件变化显是指对系统或事物因周围条件变化显示出来的敏感程度的分析。示出来的敏感程度的分析。条件变化条件变化aij，bi，cj最优解最优解多大范围内变化多大范围内变化1将参数的改变计算反映到最终单纯形表上来：将参数的改变计算反映到最终单纯形表上来：灵敏度分析的步骤灵敏度分析的步骤最终单纯形表最终单纯形表B-1B3检查对偶问题是否仍为可行解；检查

26、对偶问题是否仍为可行解；4按下表所列情况得以结论和决定继续计算的步骤。按下表所列情况得以结论和决定继续计算的步骤。2检查原问题是否仍为可行解；检查原问题是否仍为可行解；灵敏度分析的任务灵敏度分析的任务(1)、参数、参数A，b，C在什么范围内变动，对当前方在什么范围内变动，对当前方案无影响？案无影响？(2)、参数、参数A，b，C中的一个中的一个(几个几个)变动，对当前方变动，对当前方案的影响？案的影响？(3)、如果最优方案改变，如何用简便方法求新方、如果最优方案改变，如何用简便方法求新方案？案？一、分析一、分析Cj的变化的变化 Cj的变化仅仅影响到检验数的变化仅仅影响到检验数(Cj-Zj)的变化

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

28、例在第一章例1的美佳公司例子中的美佳公司例子中:(1) 若家电若家电I的利润降至的利润降至1. 5元件，而家电的利润增至元件，而家电的利润增至2元件时，美佳公司最优元件时，美佳公司最优生产计划有何变化；生产计划有何变化； 最终单纯形表如下：最终单纯形表如下：原问题可行，对偶问题不可行原问题可行，对偶问题不可行,用单纯形法继续迭代求解。用单纯形法继续迭代求解。将家电将家电I，II的利润变化的利润变化cj直接反映到最终单纯形表中。直接反映到最终单纯形表中。-2 0 -1 1/8 -9/4为使表中的解仍为最优解，应有为使表中的解仍为最优解，应有即家电即家电II的利润的利润C2的变化范围应满足：的变化

29、范围应满足： 2) 若家电若家电I的利润不变，则家电的利润不变，则家电II的利润在什么范围内变化时，则该公司的最优的利润在什么范围内变化时，则该公司的最优生产计划将不发生变化？生产计划将不发生变化？ 0 0 0 -1/4+1/4 -1/2-3/2 设家电设家电II的利润为的利润为(1+)元，反映到最终单纯形表中为：元，反映到最终单纯形表中为：二、分析二、分析b bi i的变化的变化bj的变化在实际问题中反映为可用资源数量的变化。的变化在实际问题中反映为可用资源数量的变化。可能出现的解的情况：可能出现的解的情况：例：例：若：若：(1)若设备若设备A和调试工序的每天能力不变，而设备和调试工序的每天

30、能力不变，而设备B每天的能力增每天的能力增加到加到32小时，分析公司最优计划的变化；小时，分析公司最优计划的变化； (2)若设备若设备A和和B每天可用能力不变，则调试工序能力在什么范围每天可用能力不变，则调试工序能力在什么范围内变化时，问题的最优基不变。内变化时，问题的最优基不变。在上述美佳公司的例子中，在上述美佳公司的例子中，解：解：1.求求bj的变化量。的变化量。2.列出最终单纯表。列出最终单纯表。1/2原问题不可行，对偶问题可行，用对偶单纯形法继续迭代求原问题不可行，对偶问题可行，用对偶单纯形法继续迭代求：3.在最终单纯表中直接表现在最终单纯表中直接表现bj的变化量：的变化量：bbb35

31、/211/2-1/2单纯形表中单纯形表中b列数字为：列数字为：（2）调试工序能力在什么范围内变化时，问题的最优基不变）调试工序能力在什么范围内变化时，问题的最优基不变解：解：6. 对偶的经济解释对偶的经济解释(1)原始问题是利润最大化的生产计划问题原始问题是利润最大化的生产计划问题0. .max212122112222221211112121112211mnnnnmmnnmnmmnnnnnnnnxxxxxxbxxaxaxabxxaxaxabxxaxaxat sxcxcxcz单位产品的利润（单位产品的利润（元元/件）件）产品产量（件）产品产量（件）总利润（元）总利润（元）资源限量（吨）资源限量（吨）单位产品消耗的资源（吨单位产品消耗的资源（吨/件）件）剩余的资源（剩余的资源（吨）吨）消耗的资源（吨）消耗的资源（吨）(2)对偶问题对偶问题0wwwwwwcwwawawacwwawawacwwawawa. t . swbwbwbyminnm2m1mm21nnmmmn2n21n122mm2m22211211mm1m221111mm2211资源限量（吨）资源限量（吨）资源价格（