运筹学-第二章线性规划的对偶理论与灵敏度分析_胡运权.

《运筹学-第二章线性规划的对偶理论与灵敏度分析_胡运权.》由会员分享，可在线阅读，更多相关《运筹学-第二章线性规划的对偶理论与灵敏度分析_胡运权.（49页珍藏版）》请在文档大全上搜索。

1、例一例一 美佳公司计划制造美佳公司计划制造、两种家电产品。已知各制造一件时分别占用的设两种家电产品。已知各制造一件时分别占用的设备备A A、B B的台时、调试时间及的台时、调试时间及A A、B B设备和调试工序每天可用于这两种家电的能力、设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如下表所示。问该公司应制造各售出一件时的获利情况如下表所示。问该公司应制造、两种家电备多少两种家电备多少件使获取的利润为最大。件使获取的利润为最大。设：设： x x1 1 A A产品的生产量产品的生产量 x x2 2 B B产品的生产量产品的生产量利润利润 z= 2 xz= 2 x1 1 + x

2、+ x2 2 约束约束条件条件5 5x x2 2 15 156 6x x1 1 + 2x + 2x2 2 24 24x x1 1 + x + x2 2 5 5x x1 1，x x2 2 0 0stst . .5 5x x2 2 + + x x3 3 = = 15 156 6x x1 1 + 2x + 2x2 2 + x+ x4 4 = = 24 24x x1 1 + x + x2 2 + + x x5 5 = = 5 5x x1 1，x x2 2 ，x x3 3 ，x x4 4 ，x x5 5 0 0约束约束条件条件stst . .利润利润 max z= 2 xmax z= 2 x1 1 +

3、x + x2 2 + 0 x+ 0 x3 3 + 0 x + 0 x4 4 + 0 x + 0 x5 5 一、标准化一、标准化二、写出初始单纯形表（二、写出初始单纯形表（必定存在有单位矩阵必定存在有单位矩阵）C C 2 1 2 1 0 0 0 0 0 0C CB BX XB Bb x1 x2 x3 x4 x50 0 0 0 x x3 3 x x4 4 x x5 5151524245 5 0 5 1 0 0 0 5 1 0 0 6 6 2 2 0 1 0 0 1 0 1 1 1 1 0 0 10 0 1 2 1 0 0 0 2 1 0 0 0三、最优解检验（三、最优解检验（唯一解、无限多解、无界

4、解和无解唯一解、无限多解、无界解和无解）X X* *=(7/2,3/2,=(7/2,3/2,15/215/2, ,0 0, ,0 0) )Z Z* *= 17/2= 17/2C C 2 1 2 1 0 0 0 0 0 0C CB BX XB Bb x1 x2 x3 x4 x50 0 2 2 x x3 3 x x1 1 x x2 215/215/27/27/23/23/2 0 0 1 5/4 -15/2 0 0 1 5/4 -15/2 1 0 1 0 0 1/4 -1/2 0 1/4 -1/2 0 1 0 1 0 -1/4 3/20 -1/4 3/2 0 0 00 0 0 -1/4 -1/2 -

5、1/4 -1/2 5 5x x2 2 15 156 6x x1 1 + 2x + 2x2 2 24 24x x1 1 + x + x2 2 5 5x x1 1，x x2 2 0 0约束约束条件条件把解把解X=(7/2,3/2)X=(7/2,3/2)代入原问题代入原问题( (因为因为为附加变量为附加变量) )四、分析四、分析5 53 32 215/215/224245 5P O 一个问题？一个问题？ 市场上设备市场上设备A A、设备设备B B和调试工序每小时值多少钱？和调试工序每小时值多少钱？在什么价位时，才能使美佳公司愿意出让自己的资源？在什么价位时，才能使美佳公司愿意出让自己的资源？6 6y

6、 y2 2 + y + y3 3分分析析设：设： y y1 1 设备设备A A值的值的价值价值 y y2 2 设备设备B B值的值的价值价值 y y3 3 调试工序调试工序值的值的价值价值2 25 5y y1 1 + 2y + 2y2 2 + y + y3 31 1z= 15 yz= 15 y1 1 + 24y + 24y2 2 + 5y+ 5y3 3总价值总价值minminy y1 1 , y , y2 2 , y , y3 30 0stst . .6 6y y2 2 + y + y3 32 25 5y y1 1 + 2y + 2y2 2 + y + y3 31 1z= 15 yz= 15

7、y1 1 + 24y + 24y2 2 + 5y+ 5y3 3minminy y1 1 , y , y2 2 , y , y3 30 0stst . .z z = -15 y= -15 y1 1 - 24y - 24y2 2 - - 5y 5y3 3maxmaxstst . .6 6y y2 2 + y + y3 3 y y4 4= =2 25 5y y1 1 + 2y + 2y2 2 + y + y3 3 y y5 51 1= =y y1 1, y, y2 2, y, y3 3, y, y4 4, y, y5 5 0 0C C-15 -24 -5 -15 -24 -5 0 0 -M -M0

8、0 -M -MC CB BY YB Bb y1 y2 y3 y4 y5 y6 y7 - -M M-M-My y6 6y y7 72 21 1 0 6 1 -1 0 1 0 0 6 1 -1 0 1 0 5 2 5 2 1 1 0 -1 0 1 0 -1 0 1 M-15 8M-24 2M-5 -M -M 0 0M-15 8M-24 2M-5 -M -M 0 0问题求解问题求解6 6y y2 2 + y + y3 32 25 5y y1 1 + 2y + 2y2 2 + y + y3 31 1z= 15 yz= 15 y1 1 + 24y + 24y2 2 + 5y+ 5y3 3minminy

9、y1 1 , y , y2 2 , y , y3 30 0stst . .z z = -15 y= -15 y1 1 - 24y - 24y2 2 - - 5y 5y3 3maxmaxstst . .6 6y y2 2 + y + y3 3 y y4 4= =2 25 5y y1 1 + 2y + 2y2 2 + y + y3 3 y y5 51 1= =y y1 1, y, y2 2, y, y3 3, y, y4 4, y, y5 5 0 0C C-15 -24 -5 -15 -24 -5 0 00 0C CB BY YB Bb y1 y2 y3 y4 y5-24-24-5-5y y2 2

10、y y3 31/41/41/21/2-5/4 1 0 -1/4 1/4-5/4 1 0 -1/4 1/415/2 0 1 15/2 0 1 1/2 -3/2 1/2 -3/2 -15/2 0 0 -7/2 -3/2 -15/2 0 0 -7/2 -3/2 Y=(0, Y=(0, , , , 0, 0) , 0, 0)z z=-17/2=-17/2z z = 17/2= 17/2问题求解问题求解Y=(0, Y=(0, , , , 0, 0 ) , 0, 0 )问题分析问题分析问题问题的解的解6 6y y2 2 + y + y3 32 25 5y y1 1 + 2y + 2y2 2 + y + y

11、3 31 1z= 15yz= 15y1 1 + 24y + 24y2 2 + 5y+ 5y3 3minminy y1 1 , y , y2 2 , y , y3 30 0stst . .问题：问题：原问题：原问题：利润利润 z= 2 xz= 2 x1 1 + x + x2 2 约束约束条件条件5 5x x2 2 15 156 6x x1 1 + 2x + 2x2 2 24 24x x1 1 + x + x2 2 5 5x x1 1，x x2 2 0 0stst . .问题问题的解的解X X* *=(7/2,3/2,15/2,0,0)=(7/2,3/2,15/2,0,0)Z Z* *= 17/2