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

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

2、列而得到的新矩阵，称为矩阵A的转置矩阵，的转置矩阵，记为记为AT。mnmmnnaaaaaaaaaA212222111211mnnnmmTaaaaaaaaaA212221212111逆矩阵：逆矩阵：设有设有n阶方阵阶方阵A，如果存在，如果存在n阶方阵阶方阵B，满足满足AB=BA=E，则称，则称A阵是可逆的，阵是可逆的，B是是A的逆矩阵，记做的逆矩阵，记做B=A-1。相相 关关 概概 念念相相 关关 概概 念念矩阵的运算：矩阵的运算：矩阵的加法，矩阵的减法，矩阵的加法，矩阵的减法，矩阵的乘法矩阵的乘法mnmmnnaaaaaaaaaA212222111211mnmmnnbbbbbbbbbB21222

3、2111211对偶问题的提出对偶问题的提出美佳公司利用该公司资源生产两种家电产品。美佳公司利用该公司资源生产两种家电产品。I IIIII每天可用每天可用 能力能力设备设备A A（h h）设备设备B B（h h）调试工序（调试工序（h h）0 06 61 15 52 21 1151524245 5利润（元）利润（元）2 21 10,524261552max1212121221xxxxxxxxxzLP设：设：y1表示单位时间（表示单位时间（h）设备）设备A的出让代价；的出让代价；y2表示单位时间（表示单位时间（h）设备）设备B的出让代价的出让代价;y3表示调试工序的出让代价。表示调试工序的出让代价

4、。已知：美佳公司用已知：美佳公司用6小时设备小时设备A和和l小时调试可生小时调试可生 产产一件家电一件家电I，盈利，盈利2元；用元；用5小时设备小时设备A，2小时设备小时设备B及及14小时调试可生产一件家电小时调试可生产一件家电II，盈利，盈利1元。元。由此由此y1，y2，y3的取值应满足的取值应满足:该公司希望用最小代价把美佳公司的全部资源收买该公司希望用最小代价把美佳公司的全部资源收买过来。过来。因此，线性规划模型为：因此，线性规划模型为：1252632132yyyyy32152415minyyyz32152415minyyyz0,1252632132132yyyyyyyyLP2原问题原问

5、题对偶问题对偶问题0,524261552max1212121221xxxxxxxxxzLP32152415minyyyz0,1252632132132yyyyyyyyLP2(2 1)x1x20 56 21 115245x1x20 6 15 2 121y1y2y3(15 24 5)y1y2y30,524261552max1212121221xxxxxxxxxzLP32152415minyyyz0,1252632132132yyyyyyyyLP2对偶问题的定义对偶问题的定义原始问题原始问题max z=CXs.t.AX bX 0对偶问题对偶问题min W=bTYs.t.ATY CTY 0CTATbT

6、minmnmaxbACmn对偶理论的基本思想对偶理论的基本思想 每一个线性规划问题都存在一个与其对每一个线性规划问题都存在一个与其对偶的问题，在求出一个问题的解的时候，也偶的问题，在求出一个问题的解的时候，也同时给出了另一个问题的解。同时给出了另一个问题的解。对偶单纯形法基本原理决策变量的检验数可写成：决策变量的检验数可写成：CBB-1称为单纯形乘子称为单纯形乘子非基变量非基变量基变量基变量XB XNXS0 XS bB N IcjzjCB CN0基变量基变量非基变量非基变量XBXN XSCB XB B-1 bIB-1N B-1 Cjzj0CN-CB B-1N -CB B-1C-CB B 1A0

7、-CB B 10A y C y 0若令若令 y=CBB-1则则显然显然y=CBB-1是其对偶问题的可行解是其对偶问题的可行解，即，即原问题检验数的相反数恰好是其对偶问题的一个可行解！原问题检验数的相反数恰好是其对偶问题的一个可行解！代入代入对偶问题对偶问题min W=bT ys.t.A y C y 0得：得：C-CB B 1A0-CB B 10y AC y 0也就是说也就是说：当原问题为最优解时，这时对偶问题为：当原问题为最优解时，这时对偶问题为可行解，且两者具有相同的目标函数值，对偶问题可行解，且两者具有相同的目标函数值，对偶问题的解也为最优解的解也为最优解.将这个解代入对偶问题的目标函数值

8、，有：将这个解代入对偶问题的目标函数值，有：原问题的松弛变量对应着其对偶问题的决策变量！原问题的松弛变量对应着其对偶问题的决策变量！基变量基变量非基变量非基变量XBXN XSCB XB B-1 bIB-1N B-1 cjzj0CN-CB B-1N -CB B-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 对偶问题变量对偶问题变量对偶问

9、题剩余变量对偶问题剩余变量 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对偶问题变量对偶问题变量y1 y2 y3原问题的松弛变量原问题的松弛变量x3 x4 x5原问题变量原问题变量x1 x2原问题最终表原问题最终表对偶问题最终表对偶问题最终表 若存在对偶问题的一个可行基若存在对偶问题的一个可行基B B，只要令，只要令X XB B B B-1-1b b 0 0 ,则原问题也有可行解则原问题也有可行解,且且同为最优解同为最优解。互为

10、对偶问题变量的对应关系可以看出：互为对偶问题变量的对应关系可以看出：只需要求出原问题（对偶问题）只需要求出原问题（对偶问题）的最优解，从最优解的单纯形表的最优解，从最优解的单纯形表中就可以同时得到其对偶问题中就可以同时得到其对偶问题（原问题）的最优解。（原问题）的最优解。对偶单纯形法的基本原理对偶单纯形法的基本原理例例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 8

11、4x1 16 4x2 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 16 4x2 12x1 x2

12、 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 y2对偶问题对偶问题令令 y1=y1-y1 minW=7y1-7y1

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

14、m m原问题原问题变量变量类型与类型与 变量变量 0 0 约束约束 对偶问题对偶问题约束约束类型类型 变量变量 0 0 约束约束 的对应关系的对应关系 变量无限制变量无限制 约束约束原问题原问题约束约束类型与类型与 约束约束 变量变量 0 0 对偶问题对偶问题变量变量类型类型 约束约束 变量变量 0 0 的对应关系的对应关系 约束约束 变量变量无限制无限制minW=7y1+9y23y1+4y2 5-2y1+y2 6y1无限制无限制,y2 0maxZ=5x1+6x2 3x1 2x2=74x1+x2 9x1,x2 0原问题原问题 对偶问题对偶问题 请写出以下问题的对偶问题请写出以下问题的对偶问题m

15、axZ=180y1+60y2+240y3S.t.y1+2y2+5y3 3 2y1-3y2+3y3 9 3y1+y2=4 y1无约束无约束,y2 0,y3 0 若若x是原问题的可行解，是原问题的可行解，y是对偶问题的可行是对偶问题的可行解。则有解。则有 cxyb 二二.弱对偶性：弱对偶性：对偶问题的基本性质对偶问题的基本性质一一.对称性对称性：对偶问题的对偶是原问题对偶问题的对偶是原问题 推论推论(1)：原问题任一可行解的目标函数值是其对偶原问题任一可行解的目标函数值是其对偶问题目标函数值的下界，反之对偶问题任一可行解的问题目标函数值的下界，反之对偶问题任一可行解的目标函数值是其原问题目标函数值

16、的上界。目标函数值是其原问题目标函数值的上界。推论推论(2)：若原问题（对偶问题）为无界解，则其对若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。注偶问题（原问题）无可行解。注：其逆不成立。其逆不成立。推论推论(3)：若原问题有可行解而其对偶问题无可行解，若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界，反之对偶问题有可行解而则原问题目标函数值无界，反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。其原问题无可行解，则对偶问题的目标函数值无界。弱对偶性的三个推论弱对偶性的三个推论AZ=W B 设设x是原问题的可行解，是原问题的可行解，y是对偶问题的可

17、行解。是对偶问题的可行解。当当 cx=yb 时时 x,y 是最优解。是最优解。三三.最优性最优性 若原问题及其对偶问题均具有可行解，则若原问题及其对偶问题均具有可行解，则两者均具有最优解且它们最优解的目标函数值两者均具有最优解且它们最优解的目标函数值相等。相等。四四.强对偶性（对偶定理）强对偶性（对偶定理）五五.互补松弛性（松紧定理）互补松弛性（松紧定理）在线性规划问题的最优解中，如果对应某一约束在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变反之如果约束条件

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

19、ya则有如果有无最优解。：证明：例0324min132131321ixxxxxxxxx推论推论(3)：若原问题有可行解若原问题有可行解而其对偶问题无可行解，则而其对偶问题无可行解，则原问题目标函数值无界，反原问题目标函数值无界，反之对偶问题有可行解而其原之对偶问题有可行解而其原问题无可行解，则对偶问题问题无可行解，则对偶问题的目标函数值无界。的目标函数值无界。为其一可行解。)0,0,4(x证明：证明：1.证明原问题有可行解证明原问题有可行解0324min32131321ixxxxxxxxx0,121134max212122121yyyyyyyyyz2.写出其对偶问题：写出其对偶问题：故无最优解

20、。原问题是无界的，对偶问题不可行，因而-1y1-1y200324min32131321ixxxxxxxxx025357162954max321321321ixxxxxxxxxxz1）说明原问题和对偶问题都有最优解）说明原问题和对偶问题都有最优解.2）求原问题和对偶问题的最优目标函数值的一个上）求原问题和对偶问题的最优目标函数值的一个上界和下界界和下界.四四.强对偶性（对偶强对偶性（对偶定理）定理）若原问题及其若原问题及其对偶问题均具有可行对偶问题均具有可行解，则两者均具有最解，则两者均具有最优解且它们最优解优解且它们最优解的目标函数值相等。的目标函数值相等。：考虑问题例2 推论推论(1)：原问

21、题任原问题任一可行解的目标函数一可行解的目标函数值是其对偶问题目标值是其对偶问题目标函数值的下界，反之函数值的下界，反之对偶问题任一可行解对偶问题任一可行解的目标函数值是其原的目标函数值是其原问题目标函数值的上问题目标函数值的上界。界。025357162954max321321321ixxxxxxxxxxz1.证明原问题有可行解证明原问题有可行解解：解：)0,5,0(x原问题有可行解1）说明原问题和对偶问题都有最优解）说明原问题和对偶问题都有最优解.)0,5(y有可行解：两者都有最优解。对偶性质可知，两问题都有可行解，由2.对偶问题有可行解：对偶问题有可行解：0,93255472516min2

22、121212121yyyyyyyyyy;25)0,5,0(zx有对于原问题的可行解.80)0,5(有对于对偶问题的可行解 y8025.,*zz下界。有上最优目标函数值由弱对偶性2）求原问题和对偶问题的最优目标函数值）求原问题和对偶问题的最优目标函数值的一个上界和下界的一个上界和下界.28)4,4,0,0(02023220322432max3*432143214321zxxxxxxxxxxxxxxzLPi最优解为问题：已知例用互补松弛定理计算对偶问题的最优解用互补松弛定理计算对偶问题的最优解互补松弛定理互补松弛定理:在线性规划问在线性规划问题的最优解中，题的最优解中，mijiijjcyax1,0

23、则有如果有0,1njjjjijxcya则有如果有0,42333222122020min212121212121yyyyyyyyyyyy解：对偶问题为：42304214yyx有根据互补松弛定理，5/1,5/621yy解得33204213yyx有由)4,4,0,0(*x最优解为已知原问题最优值。为对偶问题的最优解和；285/1,5/621yy*21285/1,5/6zyy对应目标函数值为对偶问题的可行解，经检验0,42333222122020min212121212121yyyyyyyyyyyy5/1,5/621yy影子价格影子价格 式中式中b bi i是线性规划原问题约束条件的右端项，是线性规划

24、原问题约束条件的右端项，它代表第它代表第i i种资源的拥有量；对偶变量种资源的拥有量；对偶变量y yi i*的意义代的意义代表在资源最优利用条件下对单位第表在资源最优利用条件下对单位第i i种种资源的估价。资源的估价。这种估价不是资源的市场价格，而是根据资源在生这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影产中作出的贡献而作的估价，为区别起见，称为影子价格子价格(shadow price)(shadow price)。几点说明：几点说明：1资源的影子价格是未知数，有赖于企业资源状况。资源的影子价格是未知数，有赖于企业资源状况。2影子价格是一种边际价格影

25、子价格是一种边际价格,相当于在资源得到最优利用的相当于在资源得到最优利用的生产条件下，每增加一个单位时目标函数生产条件下，每增加一个单位时目标函数z的增量。的增量。3资源的影子价格实际上又是一种机会成本。资源的影子价格实际上又是一种机会成本。4生产过程中如果某种资源未得到充分利用时，该种资源的影生产过程中如果某种资源未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。生产中已耗费完毕。5对线性规划问题的求解是确定资源的最优分配方案，而对对线性规划问题的求解是确定资源的最优分配方案，而对于对偶

26、问题的求解则是确定资源的恰当估价。于对偶问题的求解则是确定资源的恰当估价。对偶单纯形法v 基本思路：在迭代过程中保持原问题的检验数为非正，逐步替换负基变量，从而得到最优解。即保持对偶问题有可即保持对偶问题有可行解行解使原问题具有可使原问题具有可行解行解检验数为非正替换负基变量对偶单纯形法计算步骤对偶单纯形法计算步骤 1.1.列出初始单纯形表，且列出初始单纯形表，且检验数非正检验数非正。为换出变量。对应的基变量按rriiixbBbBbB1110min.3为换入变量确定按srsssrjrjjjxazcaazc0min.4 2.b 2.b值有否为负，无，计算结束。有，转值有否为负，无，计算结束。有，

27、转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-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在得到原始

28、可行解时同时得到对偶可行解，已获得在得到原始可行解时同时得到对偶可行解，已获得最优解：最优解：（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例例:(初始解原始、对偶都不可行的问题初始解原始、对偶都不可行的问题)02225324.223min321321321321321xxxxxxxxxxxxtsxxxzCj322000CBXBbx1x2x3x4x5x60

29、x441111000 x552310100 x62221001 j=cj-zj322000先解决对偶可行性先解决对偶可行性0 x341111000 x59120-1100 x62110101 j=cj-zj500-200已得到对偶可行解，再用对偶单纯形法求解已得到对偶可行解，再用对偶单纯形法求解Cj322000CBXBbx1x2x3x4x5x62x317/21/2013/2-1/20-2x29/2-1/2101/2-1/200 x65/21/2001/21/21 j=cj-zj500-2000 x360012010 x270100110 x15010011 j=cj-zj000-7510在得到

30、原始可行解时同时得到对偶可行解，已获得在得到原始可行解时同时得到对偶可行解，已获得最优解：最优解：（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.对于对偶问题有可行解，而原问题无可行解的判断。对于对偶问题有可行解，而原问题无可行解的判断。项目项目原始单纯形法原始单纯形法对偶单纯形法对偶单纯形法选主元

31、素选主元素按列选主元按列选主元按行选主元按行选主元确定主元素确定主元素arj 0arj 1时，表中为时，表中为-1/4+1/4 0，x4入基，入基，x3出基。出基。b.b.当当 0 0，x x5 5入基，入基，x x2 2出基。出基。2+1+2 0 0 002+1+2 0 0 0 -1/4+1/4 -1/2-5/2x46234/5-1/51/5100-6100 0 1/5-1/5 0 -2-显然，当显然，当 1 1时，当前表检验数均取负值，即当前解为最时，当前表检验数均取负值，即当前解为最优解，且优解，且z z7 78 8 。2+1+2 0 0 002+0 0 0 0 -1/4+1/4 -1/

32、2-5/21541x551/32/301/61/6001 0 1/35/3 0 -1/3-1/6 0 2+1+2 0 0 002+0 0 0 0 -1/4+1/4 -1/2-5/21541x551/32/301/61/6001 0 1/35/3 0 -1/3-1/6 0当当1/3+5/3 0，-1/3-1/6 0 当前解为最优解，即：当前解为最优解，即：当当2 1/5时，表中为最优解，且时，表中为最优解，且z84 当当 0,则，则，x4入基，入基，x1出基出基 2+1+2 0 0 0000 0 0 0 -1/4+1/4 -1/2-5/215245x5521010001 2 12 0 0 0061显然，当显然，当 -2 时，当前表检验数均取负值，且时，当前表检验数均取负值，且z z0 0。0510152025-3-2-10123z()Z（）随）随值变化的情况图值变化的情况图作作 业业 P61：2.7 2.9