大学精品课件：第三章 对偶理论和灵敏度分析（第6节）.ppt

1、第第1页页原问题原问题对偶问题对偶问题0 .min YCYAtsYb 0 .max XbAXtsCXz miiimjjjybxcz1*1*iibzy *第第2页页对偶问题对偶问题 的最优解的经济意义是：在其它条件的最优解的经济意义是：在其它条件不变的情况下，单位资源不变的情况下，单位资源 i 变化所引起的目标函数变化所引起的目标函数最优值最优值 z*的变化。的变化。即，在资源最优利用的条件下，对第即，在资源最优利用的条件下，对第 i 种资源的估种资源的估价。因为这种估价不是资源的市场价格，而是根据价。因为这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作出的估价，为区别起资源在生产

2、中作出的贡献而作出的估价，为区别起见，称为影子价格见，称为影子价格（shadow price）。*iy第第3页页*iy1.影子价格影子价格是一种边际价格是一种边际价格 例：原问题例：原问题 对偶问题对偶问题 0,1241648232max21212121xxxxxxxxz 0,3422412168min3213121321yyyyyyyyyy 由原问题最优单纯形表可知：由原问题最优单纯形表可知：0,125.0,5.1*3*2*1 yyy第第4页页（1）5.1*1y其它条件不变的情况下：设备增其它条件不变的情况下：设备增加一台时，该厂按最优计划生产加一台时，该厂按最优计划生产可多获利可多获利 1

3、.5 元。元。x2x14x1=164x2=12x1+2x2=8(4,2)x2x14x1=16x1+2x2=9(4,2.5)4x2=1214,2,4*2*1 zxx5.15,5.2,4*2*1 zxx第第5页页（2）其它条件不变的情况下：原材料其它条件不变的情况下：原材料 A 增加增加 1kg 时，该厂按最优计划时，该厂按最优计划生产可多获利生产可多获利0.125元。元。x2x14x1=164x2=12x1+2x2=8(4,2)x2x14x1=17x1+2x2=8(4.25,1.875)4x2=1214,2,4*2*1 zxx 125.0*2y125.14,875.1,25.4*2*1 zxx第

4、第6页页（3）其它条件不变的情况下：原材料其它条件不变的情况下：原材料B 增加增加 1kg 时，该厂按最优计划时，该厂按最优计划生产可多获利生产可多获利 0 元。元。x2x14x1=164x2=12x1+2x2=8(4,2)x2x14x1=16x1+2x2=8(4,2)4x2=1314,2,4*2*1 zxx 0*3y14,2,4*2*1 zxx第第7页页2.影子价格影子价格*iy是一种机会成本是一种机会成本当第当第 i 种资源的市场价格低于影子价格时：种资源的市场价格低于影子价格时：企业自己进行生产。企业自己进行生产。当第当第 i 种资源的市场价格高于影子价格时：种资源的市场价格高于影子价格

5、时：企业将已有资源卖出。企业将已有资源卖出。第第8页页3.资源资源 i 的市场价格是已知数，而它的影子价格则的市场价格是已知数，而它的影子价格则有赖于资源有赖于资源 i 的利用情况，为未知数。的利用情况，为未知数。因企业生产任务、产品结构发生变化，资源的影子因企业生产任务、产品结构发生变化，资源的影子价格也随之改变。价格也随之改变。例如：例如：企业原来只生产企业原来只生产 2 种产品，现在生产种产品，现在生产 3 种产品，其种产品，其它条件不变。它条件不变。第第9页页 0,1241648232max21212121xxxxxxxxz 0,12416482432 max3213231321321

6、xxxxxxxxxxxxxz问题问题 1问题问题 2问题问题 1 的对偶问题：的对偶问题：问题问题 2 的对偶问题：的对偶问题：*3*2*1yyy *3*2*1yyy二者不相等。二者不相等。第第10页页4.在最优生产计划下：在最优生产计划下：如果第如果第 i 种资源未被用完，则表明该资源的影子价种资源未被用完，则表明该资源的影子价格为格为 0；如果第如果第 i 种资源的影子价格不为种资源的影子价格不为 0，则表明该资源，则表明该资源在生产中被完全用完。在生产中被完全用完。由互补松弛性质可知由互补松弛性质可知 第第11页页5.单纯型表中检验数的经济解释：单纯型表中检验数的经济解释：jBjjPBC

7、c1 根据根据原问题检验数和对偶问题解的关系（性质原问题检验数和对偶问题解的关系（性质6）：）：原问题松弛变量检验数的相反数原问题松弛变量检验数的相反数=对偶变量的值对偶变量的值原问题松弛变量检验数为：原问题松弛变量检验数为：1 BCB1 BCYB故故jjYPc miijijayc1第第12页页第第 j 种产品的产值种产品的产值生产第生产第 j 种产品所消耗各种资源的影子价格总种产品所消耗各种资源的影子价格总和，即第和，即第 j 种产品隐含成本。种产品隐含成本。jBjjPBCc1 jjYPc miijijayc1第第13页页第第 j 种产品产值种产品产值 第第 j 种产品隐含成本：生产第种产品

8、隐含成本：生产第 j 种产品有利。种产品有利。检验数大于检验数大于 0。第第 j 种产品产值种产品产值 第第 j 种产品隐含成本：生产第种产品隐含成本：生产第 j 种产品无利。种产品无利。检验数小于检验数小于 0。为产品定价时，产品的价格要大于该产品的隐含为产品定价时，产品的价格要大于该产品的隐含成本。成本。第第14页页max z=2x1+3x2 0,12 4 16 482 .212121xxxxxxts例：例：max z=2x1+3x2 0,12 4 16 48 2 .543215241321xxxxxxxxxxxxts第第15页页原问题变量原问题变量原问题松弛变量原问题松弛变量cj2300

9、0iCBXBbx1x2x3x4x50 x381210040 x41640010-0 x51204 0013c j z j23000 0410,0,0),(1321Pyyy现有生产计划中产品现有生产计划中产品 I 的隐含成本的隐含成本=第第16页页原问题变量原问题变量原问题松弛变量原问题松弛变量cj23000iCBXBbx1x2x3x4x50 x321010-1/220 x4164001043x2301001/4-c j z j2000-3/4 04143,0,0),(1321Pyyy现有生产计划中产品现有生产计划中产品 I 的隐含成本的隐含成本=第第17页页原问题变量原问题变量原问题松弛变量原

10、问题松弛变量cj23000iCBXBbx1x2x3x4x52x121010-1/2-0 x4800-41243x2301001/412c j z j00-201/4 04141,0,2),(1321Pyyy现有生产计划中产品现有生产计划中产品 I 的隐含成本的隐含成本=第第18页页原问题变量原问题变量原问题松弛变量原问题松弛变量cj23000iCBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80c j z j00-3/2-1/80 0410,81,23),(1321Pyyy现有生产计划中产品现有生产计划中产品 I 的隐含成本的隐含成本=第第

11、19页页1.单纯形法的求解过程单纯形法的求解过程（1）单纯形表的右端常数列中的数据在迭代过程）单纯形表的右端常数列中的数据在迭代过程中一直为非负：从而确保原问题每次迭代得到的中一直为非负：从而确保原问题每次迭代得到的新基解都是可行解。新基解都是可行解。第第20页页（2）单纯形表的检验数列中的数据在迭代过程中逐）单纯形表的检验数列中的数据在迭代过程中逐步满足全部非正：从而确保对偶问题的解随着迭代过步满足全部非正：从而确保对偶问题的解随着迭代过程由不可行逐渐变为可行。程由不可行逐渐变为可行。当由单纯形表的检验数行所得出的对偶问题的基解也当由单纯形表的检验数行所得出的对偶问题的基解也是可行解时，原始

12、问题和对偶问题同时达到最优。是可行解时，原始问题和对偶问题同时达到最优。第第21页页2.对偶单纯形法的求解过程对偶单纯形法的求解过程（2）单纯形表的右端常数列中的数据在迭代过程）单纯形表的右端常数列中的数据在迭代过程中逐步满足全部非负：从而确保原问题的解随着中逐步满足全部非负：从而确保原问题的解随着迭代过程由不可行变为可行。迭代过程由不可行变为可行。（1）单纯形表的检验数列中的数据在迭代过程中）单纯形表的检验数列中的数据在迭代过程中一直为非正：从而确保每次迭代得到的对偶问题一直为非正：从而确保每次迭代得到的对偶问题的新基解都是可行解。的新基解都是可行解。第第22页页当由单纯形表的右端常数列所得

13、出的原问题的基当由单纯形表的右端常数列所得出的原问题的基解也是可行解时，原始问题和对偶问题同时达到解也是可行解时，原始问题和对偶问题同时达到最优。最优。第第23页页单纯形法：迭代过程中，一直保持原问题可行，单纯形法：迭代过程中，一直保持原问题可行，对偶问题逐步由不可行变为可行。对偶问题逐步由不可行变为可行。对偶单纯形法：迭代过程中，一直保持对偶问题对偶单纯形法：迭代过程中，一直保持对偶问题可行，原问题逐步由不可行变为可行。可行，原问题逐步由不可行变为可行。第第24页页cjc1clcmcm+1ckcnCBXBbx1xlxmxm+1xkxnc1x1b1100a1,m+1a1ka1nclxlbl01

14、0al,m+1alkalncmxmbm001am,m+1amkamnc j z j00011 mmzckkzc nnzc 第第25页页1.换出变量的确定换出变量的确定总存在总存在 小于小于 0 的的 bi，liibbb 0min令其对应的变量令其对应的变量 xl 为换出变量。为换出变量。为了使原问题的解在迭代过程中由不可行变为可行为了使原问题的解在迭代过程中由不可行变为可行，首先被换出的变量应该是取值为负数的变量，因，首先被换出的变量应该是取值为负数的变量，因为它是造成原问题不可行的根本原因。为它是造成原问题不可行的根本原因。第第26页页2.换入变量的确定换入变量的确定（1）确保换入的变量取值

15、不再为负数）确保换入的变量取值不再为负数设设 xk 为换入变量，则需要以为换入变量，则需要以 al k 为枢轴元素进行旋为枢轴元素进行旋转运算，从而得到新的基解。转运算，从而得到新的基解。mlklmnmkmmlknllkmllknkmnkmmlbabbaaaaaaaaaaabxxxxxx 1 0 0 1 0 1 0 0 0 1 11,1,111,111第第27页页0 lklab0 lb0 lka而而所以所以即如选择的换入变量为即如选择的换入变量为 xk，则其第，则其第 l 行第行第 k 列的约列的约束条件系数束条件系数 al k 必须小于零。必须小于零。为了确保换入的变量为了确保换入的变量 x

16、k 取值不再为负数，即使：取值不再为负数，即使：第第28页页（2）确保得到的新解的检验数仍为非正数）确保得到的新解的检验数仍为非正数 lklmkmlkllklklknlmkmnlkljmkjmlkmklknllkjllklknlknlkjlkjlkknkjmlabababababaaaaaaaaaaaaaaaaaaaaaaaaabxxxxxx 0 -1 -0 1 0 1 0 0 -0 -1 .11,11,1,111以以 al k 为枢轴元素进行旋转运算，得到新单纯形表：为枢轴元素进行旋转运算，得到新单纯形表：第第29页页 )()(liaaliaaaaalkljiklkljijij )()(li

17、ablibaabblklllkikiiTmklkljmjlkljklkljjmkjjaaaaaaaaaacccc ,.,.,).(111 Tlkmklklkkmkllaaaaacccc ,.,1,.,).(11 第第30页页下面来确定，如何选择下面来确定，如何选择 xk 才能够使得：才能够使得：0,.,.,).(111 Tmklkljmjlkljklkljjmkjjaaaaaaaaaacccc 0,.,1,.,).(11 Tlkmklklkkmkllaaaaacccc 第第31页页 mlilkikilkklilkikillaacacaacc111 kmliikiliikilklcacacac1

18、111 lklmliikiliikiklkacacacca1111 miikiklkacca11klka 1 第第32页页Tmklkljmjlkljklkljjmkjjaaaaaaaaaacccc ,.,.,).(111 111)()(limlilkljkiklkljijiiklkljijijaacaaaacaaaacc 111111lilkljkmliiklkljimliijiliiklkljiijijaacaaacacaaacacc mliiklkljiliiklkljilkljklimliijiijijaaacaaacaacacacc111111第第33页页 mliikiliikiklk

19、ljlimliijiijijacaccaaacacc111111 lklmiikiklkljljlmiijijacaccaaacacc11 lklklkljljljacaaac lklmiikiklkljljlmiijijacaccaaacacc11lkllkljljlklkljjacaaacaa klkljjaa 第第34页页 )(-)(1ljaaljaklkljjklkj 下面来证明下面来证明0 j 下面来证明下面来证明k 如何取值，才能使如何取值，才能使01 klka 00 klka，0 klkljjaa 第第35页页0 lja0 j 000 klkljaa，又又 0 klkljjjaa

20、 0 klkljaa 第第36页页0 lja0 j 000 klkljaa，又又 0 klkljjjaa 0 klkljaa 0 lkkljjaa 要想使要想使将其两端除以将其两端除以 alj：ljjlkkaa 0min ljljjlkkaaa 第第37页页由此可得换出变量的确定方法由此可得换出变量的确定方法0min ljljjlkkaaa 注：如利用上述原则无法确定换入变量，如换出变量注：如利用上述原则无法确定换入变量，如换出变量所对应的该行元素均为非负，则问题无可行解。所对应的该行元素均为非负，则问题无可行解。第第38页页 )(-)(1ljaaljaklkljjklkj klkklklll

21、aaa 1-0 -10 llla，)(-)(1ljaaljaklkljjklkj klkljjjaa -第第39页页max z=2x1+3x2 0,12 4 16 482 .212121xxxxxxts例：例：第第40页页cj23000iCBXBbx1x2x3x4x50 x381210040 x41640010-0 x5120 4 0013c j z j230000 x32 1 010-1/220 x4164001043x2301001/4-c j z j2000-3/43402 3443 3400 3400 3410 2112 2100 2110 2100 212/143 klkljjaa

22、-klkljjaa -第第41页页cj23000iCBXBbx1x2x3x4x52x121010-1/2-0 x4800-41 2 43x2301001/412c j z j00-201/42x141001/400 x5400-21/213x22011/2-1/80c j z j00-3/2-1/8041200 41200 41242 41210 412241 klkljjaa -第第42页页1、列出初始单纯形表。、列出初始单纯形表。检查检查 b 列，如果全为非负，检验数全为非正，则列，如果全为非负，检验数全为非正，则已到到最优解；已到到最优解；检查检查 b 列，如果有负分量，检验数全为非正，

23、则列，如果有负分量，检验数全为非正，则转步骤转步骤 2；第第43页页3.确定换入变量：确定换入变量：lkkljljjaaa 0min从而确定从而确定 xk 为换入变量，转步骤为换入变量，转步骤4；4.以以 alk 枢轴元素进行旋转运算，转步骤枢轴元素进行旋转运算，转步骤 1。2.确定换出变量：确定换出变量：liibbb 0min从而确定从而确定 x l 为换出变量，转步骤为换出变量，转步骤 3；第第44页页min =2x1+3x2+4x3 0,4 3 -23 2 .321321321xxxxxxxxxts例：例：解：解：max z=-2x1-3x2-4x3 0,4-3 -23 -2 .5432

24、153214321xxxxxxxxxxxxxts第第45页页max z=-2x1-3x2-4x3 0,4 3 23 2 .5432153214321xxxxxxxxxxxxxtscj-2-3-400CBXBbx1x2x3x4x50 x4-3-1-2-1100 x5-4-2 1-301c j z j-2-3-4001-4/3-第第46页页cj-2-3-400CBXBbx1x2x3x4x50 x4-10-5/21/21-1/2-2x121-1/23/20-1/2c j z j0-4-10-1-8/5-2第第47页页cj-2-3-400CBXBbx1x2x3x4x5-3x42/501-1/5-2/5

25、1/5-2x111/5107/5-1/5-2/5c j z j00-3/5-8/5-1/5第第48页页1.对偶单纯形法的优点对偶单纯形法的优点 不需要加入人工变量，因此问题可以得到简化。不需要加入人工变量，因此问题可以得到简化。对于变量多于约束条件的线性规划问题，使用对偶单纯形法对于变量多于约束条件的线性规划问题，使用对偶单纯形法可以减少计算工作量。可以减少计算工作量。（对于约束条件很多的线性规划问题，可以先将其变换为对偶（对于约束条件很多的线性规划问题，可以先将其变换为对偶问题，再利用对偶单纯形法求解。）问题，再利用对偶单纯形法求解。）灵敏度分析、整数规划的割平面法中，使用对偶单纯形法可灵敏度分析、整数规划的割平面法中，使用对偶单纯形法可以使问题得到简化。以使问题得到简化。第第49页页2.对偶单纯形法的缺点对偶单纯形法的缺点 很难找到一个初始可行基，使其所有检验数满足很难找到一个初始可行基，使其所有检验数满足非正，因而该方法在求解线性规划问题时很少单非正，因而该方法在求解线性规划问题时很少单独应用。独应用。