《第二章对偶理论及灵敏度分析优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第二章对偶理论及灵敏度分析优秀PPT.ppt（68页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章对偶理论及灵敏度分析第二章对偶理论及灵敏度分析2023/2/251第一页，本课件共有68页本章目录本章目录2-1 2-1 线性规划的对偶问题线性规划的对偶问题2-2 2-2 对偶问题的基本性质对偶问题的基本性质2-3 2-3 影子价格影子价格2-4 2-4 对偶单纯形法对偶单纯形法2-5 2-5 灵敏度分析灵敏度分析2-6 2-6 参数线性规划参数线性规划第二页，本课件共有68页2-1 2-1 线性规划的对偶问题线性规划的对偶问题引言引言一、一、对偶问题对偶问题二、二、对称形式对偶问题的一般形式对称形式对偶问题的一般形式三、三、非对称形式的原非对称形式的原-对偶问题对偶问题四、对偶问题的
2、写法四、对偶问题的写法返回本章目录第三页，本课件共有68页引引 言言在实际问题中，一个问题的优化往往可以从不同的两个角度提出问题。譬如，要求在有限资源条件下生产利润最大；或在一定生产能力条件下使资源消耗最少。所以，在线性规划中，对任一给定的求最大值问题，相应也存在一个求最小值的问题。且两者包括有相同的数据。若称前者为原问题，则后者便称为对偶问题；或称前者为对偶问题，而称后者为原问题。两者互为对偶，具有密切的关系。只要得到其中一个问题的解，也就能够得到另一个问题的解。因而，从中选一个问题求解就可以了。第四页，本课件共有68页一、对偶问题一、对偶问题例1 美佳公司利用该公司资源生产两种家电产品的线
3、性规划模型为：设y1，y2，y3分别表示设备A、B和调试工序单位时间的价格。则0y1+6y2+y325y1+2y2+y31对生产产品的全部资源的定价。假如另一公司想收购美佳公司的资源，美佳公司出让自己资源的条件是什么？出让代价不低于用同等资源组织生产两种产品所能获得的利润。对 生 产 产品的全部资源的定价。产品的利润产品的利润第五页，本课件共有68页原问题与对偶问题的数据比较原问题与对偶问题的数据比较 原问题对偶问题x1x2原关系min wy10515y26224y3115对偶关系max z=min wmax z21第六页，本课件共有68页二、对称形式对偶问题的一般形式二、对称形式对偶问题的一
4、般形式定定定定义义义义：满满足足下下列列条条件件的的线线性性规规划划问问题题称称为为具具有有对对称称形形式式：其其变变量量均均具具有有非非负负约约束束，其其约约束束条条件件当当目目标标函函数数求求极极大大时时取取“”号，当目标函数求极小时均取号，当目标函数求极小时均取“”号。号。则其对偶问题的则其对偶问题的一般形式为：一般形式为：若原问题的一若原问题的一般形式为：般形式为：yi(i=1,2,，m)代表第代表第i种资源的种资源的估价。估价。第七页，本课件共有68页矩阵形式表示的原问题与对偶问题矩阵形式表示的原问题与对偶问题原问题：对偶问题：令ww对偶问题令zz对对偶偶问问题题的的对对偶是原问题偶
5、是原问题第八页，本课件共有68页三、非对称形式的原三、非对称形式的原-对偶问题对偶问题考虑标准形式的线性规划：max z=CX AX=b X0max z=CX AX b AX b X0min w=bT(YY)AT(Y Y)CT Y0，Y 0令令Y=YY min w=bT Y AT Y CT Y 为自由变量这就是非对称形式的对偶关系。在这种形式中，Y 不要求非负。max z=CX AX b AX b X0YYmin w=Yb AY C Y 为自由变量第九页，本课件共有68页四、对偶问题的写法四、对偶问题的写法在写对偶问题时，要特别注意上表中原问题与其对偶问题在写对偶问题时，要特别注意上表中原问题
6、与其对偶问题的对应关系。的对应关系。第十页，本课件共有68页写对偶问题的步骤：写对偶问题的步骤：第一步第一步：根据原问题数学模型的形式统一符号。若原问题目标函数求求极极大大，则将其约束条件统一成“”“”或或或或“”的形式；若原问题目标函数为求求求求极极极极小小小小，则将其约束条件统一成“”“”或或或或“”的形式。第二步第二步：假设对偶变量。对偶变量与原问题的约束条件一一对应，每一个约束条件都有一个对偶变量与它相对应。所以，对偶变量数等于原问题的约束方程数。第第第第三三三三步步步步：根据原问题与对偶问题的关系写出对偶规划模型。第十一页，本课件共有68页例例例例:写出下面规划问题的对偶规划问题。写
7、出下面规划问题的对偶规划问题。写出下面规划问题的对偶规划问题。写出下面规划问题的对偶规划问题。原问题：原问题：max z=4x1+x2-5x3-4x4-2x5 2x2+x3+3x4+4x5=-6 3x1+x2-x3-x4 2 -4x1+2x3-2x4 -5 -6 x1 18 x2 25 x3,x4 0;x5 不受限制统一符号（因求max,故约束统一成“”的形式：max z=4x1+x2-5x3-4x4-2x5 2x2+x3+3x4+4x5=-6 -3x1-x2+x3 +x4 -2 -4x1 +2x3-2x4 -5 x1 18 -x1 6 x2 25 x3,x4 0;x1,x2,x5 不受限制y
8、1y2y3y4y6y5min w=-6y1-2y2-5y3+18y4+6y5+25y6-3y2-4y3+y4-y5=42y1-y2+y6=1y1+y2+2y3-53y1+y2-2y3-44y1=-2yi 0(i=2,3,4,5,6);y1为自由变量对对偶偶问问题题第一步：统一符号第一步：统一符号第一步：统一符号第一步：统一符号第二步：假设变量第二步：假设变量第二步：假设变量第二步：假设变量第三步：写对偶问题第三步：写对偶问题第三步：写对偶问题第三步：写对偶问题第十二页，本课件共有68页例例2 2 写出下述线性规划问题的对偶问题写出下述线性规划问题的对偶问题原问题：原问题：原问题：原问题：令令x
9、2x4，x40统一约束统一约束符号：符号：y1y2y3对偶问题：对偶问题：对偶问题：对偶问题：令令令令y y2 2y y4 4，可可可可得得得得到到到到教教教教材上的形式：材上的形式：材上的形式：材上的形式：第十三页，本课件共有68页教材上例教材上例2的解法：的解法：原问题：原问题：原问题：原问题：令x2x2；x3x3x3用两个不等式约束表示等式约束：统一约束符号：统一约束符号：第十四页，本课件共有68页假假设设变变量量：写对偶问题：写对偶问题：写对偶问题：写对偶问题：令y2y2；y3y3y3第十五页，本课件共有68页第十六页，本课件共有68页2-2 对偶问题的基本性质对偶问题的基本性质一、单
10、纯形法计算的矩阵描述原问题原问题原问题原问题对偶问题对偶问题对偶问题对偶问题X Xs s为松弛变量；为松弛变量；为松弛变量；为松弛变量；X Xs s=(=(x xn+1n+1,x xn+2n+2,x xn+mn+m););I I为为为为mm mm阶单位矩阵。阶单位矩阵。阶单位矩阵。阶单位矩阵。返回本章目录提纲：提纲：一、单纯形法计算的矩阵描述一、单纯形法计算的矩阵描述一、单纯形法计算的矩阵描述一、单纯形法计算的矩阵描述二、二、对偶问题的基本性质对偶问题的基本性质第十七页，本课件共有68页第十八页，本课件共有68页表表表表2-32-3 初始单纯形表初始单纯形表初始单纯形表初始单纯形表非基变量非基
11、变量非基变量非基变量基变量基变量基变量基变量C Cj jC CB BC CN N0 0C CB B基基基基b bX XB BX XN NX Xs s0 0X Xs sb bB BN NI Ic cj j-z-zj jC CB BC CN N0 0表表表表2-4 2-4 最终单纯形表最终单纯形表最终单纯形表最终单纯形表基变量基变量基变量基变量非基变量非基变量非基变量非基变量C Cj jC CB BC CN N0 0C CB B基基基基b bX XB BX XN NX Xs sC CB BX XB BB B-1-1b bI IB B-1-1N NB B-1-1c cj j-z-zj j0 0C C
12、N N-C-CB BB B-1-1N N-C-CB BB B-1-1第十九页，本课件共有68页基变量XB的检验数为：CBCBI 0所以，在最终单纯形表中，原变量的检验数可写为CCBB-1A0（2.17）CBB-10（2.18）CBB-1称为单纯形乘子。令Y CBB-1，则2.17、2.18式可以改写为CCBB-1A0 YACI AYC Y0可以看出，原问题得到最优解时，其检验数的相反数是对偶问题的一个可行解。代入对偶问题的目标函数得w Yb CBB-1bz即 原问题得到最优解时，对偶问题为可行解，两者具有相同的目标函数值。第二十页，本课件共有68页例例3 两个互为对偶的线性规划问题解的比较两个
13、互为对偶的线性规划问题解的比较原问题：对偶问题：第二十一页，本课件共有68页原问题的解为原问题的解为X(x1,x2,x3,x4,x5)T(7/2,3/2,15/2,0,0)T与最优解对应的目标函数值为：对偶问题的解为对偶问题的解为Y(y1,y2,y3,y4,y5)T(0,1/4,1/2,0,0)T与最优解对应的目标函数值为：第二十二页，本课件共有68页例例 3原变量原变量原变量原变量松弛变量松弛变量松弛变量松弛变量x x1 1x x2 2x x3 3x x4 4x x5 5x x3 315/215/20 00 01 15/45/4-15/2-15/2x x1 17/27/21 10 00 01
14、/41/4-1/2-1/2x x2 23/23/20 01 10 0-1/4-1/43/23/2c cj j-z-zj j0 00 00 0-1/4-1/4-1/2-1/2对偶剩余变量对偶剩余变量对偶剩余变量对偶剩余变量对偶问题变量对偶问题变量对偶问题变量对偶问题变量y y4 4y y5 5y y1 1y y2 2y y3 3对偶问题变量对偶问题变量对偶问题变量对偶问题变量对偶剩余变量对偶剩余变量对偶剩余变量对偶剩余变量y y1 1y y2 2y y3 3y y4 4y y5 5y2y21/41/4-5/4-5/41 10 0-1/4-1/41/41/4y3y31/21/215/215/20
15、01 11/21/2-3/2-3/2c cj j-z-zj j-15/2-15/20 00 0-7/2-7/2-3/2-3/2原问题松弛变量原问题松弛变量原问题松弛变量原问题松弛变量原问题变量原问题变量原问题变量原问题变量x x3 3x x4 4x x5 5x x1 1x x2 2 在最优单纯形表的检验数行，原问题变量对应的数的相反数，是对偶问题剩余变量的值；原问题松弛变量对应的数的相反数，是对偶问题变量的值。反之亦然。第二十三页，本课件共有68页二、对偶问题的基本性质二、对偶问题的基本性质1.弱对偶性：证：证：证：证：第二十四页，本课件共有68页由弱对偶性得到推论：由弱对偶性得到推论：（1）
16、原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。（2）如原问题有可行解且目标函数值无界（无界解），则其对偶问题无解；反之，对偶问题有可行解且目标函数值无界，则其原问题无可行解。（3）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之，对偶问题有可行解而其原问题无可行解，则对偶问题目标函数值无界。第二十五页，本课件共有68页2.2.最优性：最优性：最优性：最优性：3.3.强对偶性（对偶定理）强对偶性（对偶定理）：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。第二十六页，
17、本课件共有68页4.互补松弛性：互补松弛性：在在在在线线线线性性性性规规规规划划划划问问问问题题题题的的的的最最最最优优优优解解解解中中中中，如如如如果果果果对对对对应应应应某某某某一一一一约约约约束束束束条条条条件件件件的的的的对对对对偶偶偶偶变变变变量量量量值值值值为为为为非非非非零零零零，则则则则该该该该约约约约束束束束条条条条件件件件取取取取严严严严格格格格等等等等式式式式；反反反反之之之之，如如如如果果果果约束条件取严格不等式，则其对应的对偶变量一定为零。约束条件取严格不等式，则其对应的对偶变量一定为零。约束条件取严格不等式，则其对应的对偶变量一定为零。约束条件取严格不等式，则其对应
18、的对偶变量一定为零。第二十七页，本课件共有68页2-3 影子价格影子价格当线性规划原问题求得最优解xj*(j=1,2,n)时，其对偶问题也得到最优解yi*(i=1,2,m)，且两者的目标函数值相等。即bi：线性规划原问题右端项，代表第 i 种资源的拥有量；yi*：对偶变量，代表在最优资源利用条件下对单位第 i 种资源的估价，称为影子价格。影影影影 子子子子 价价价价 格格格格(Shadow Price)也称为机会成本(Opportunity Cost),它是根据具体的经济目标、技术水平和资源条件作出的对资源利用的评价。市市市市场场场场价价价价格格格格：是资源在市场上流通的实际价格，它由整个社会
19、的经济技术状况决定。返回本章目录第二十八页，本课件共有68页根据根据 求求 b bi i 的偏导数得：的偏导数得：这说明，原原原原问问问问题题题题某某某某一一一一约约约约束束束束条条条条件件件件的的的的右右右右边边边边常常常常数数数数b b b bi i i i增增增增加加加加一一一一个个个个单单单单位位位位时时时时，则则则则由由由由此此此此引引引引起起起起最最最最优优优优目目目目标标标标函函函函数数数数值值值值的的的的增增增增加加加加量量量量，就就就就等等等等于于于于与与与与该该该该约约约约束束束束相相相相对应的对偶变量的最优值对应的对偶变量的最优值对应的对偶变量的最优值对应的对偶变量的最优
20、值。这样一来，在有限资源条件下使收益最大化这一类问题中，就可以把对偶变量的最优值，看成是相应资源每一单位对于目标函数的贡献，即这些资源被充分利用时所能带来的收益。从而，yi*的值就相当于对单位 i 种资源在实现最大利润时的一种价格估计。这种估计是针对具体企业，具体产品而存在的一种特殊价格，称之为影子价格，它与市场价格不同。若仅从经济上考虑，当当当当某某某某种种种种资资资资源源源源的的的的市市市市场场场场价价价价格格格格低低低低于于于于影影影影子子子子价价价价格格格格时时时时，企企企企业业业业就就就就可可可可以以以以考考考考虑虑虑虑买买买买进进进进这这这这种种种种资资资资源源源源；当当当当市市市
21、市场场场场价价价价格格格格高高高高于于于于影影影影子子子子价价价价格格格格时时时时，企企企企业业业业则则则则可可可可以以以以出出出出售售售售这这这这种种种种资资资资源源源源。随随着着资资源源的的买买进进卖卖出出，它它的的影影子子价价格格也也将将随随之之变变化化，直直到到影影子子价价格格与与市市场场价价格格保保持持同同等等水水平平时，才处于平衡状态。时，才处于平衡状态。第二十九页，本课件共有68页影子价格是一种边际价格（图示）影子价格是一种边际价格（图示）Q1Q3Q2Q4Ox1x25x5x2 215156x6x1 12x2x2 22424x x1 1x x2 25 5z z2 2z z8.58.
22、5(3.5(3.5，1.5)1.5)(25)(25)第三十页，本课件共有68页影子价格的应用影子价格的应用（1）用影子价格判别资源的供求关系如果线性规划的原问题在得到最优解时，某个约束条件为严格的不等式，即最优解中该约束的松弛变量的值大于零，即表明该该该该种种种种资资资资源源源源有有有有剩剩剩剩余余余余，供供供供大大大大于于于于求求求求。增增增增加加加加这这这这种种种种资资资资源源源源时时时时，目目目目标标标标函函函函数数数数值值值值不不不不会有任何改善会有任何改善会有任何改善会有任何改善。如果线性规划的原问题在得到最优解时，某个约束条件为严格的等式，即最优解中该约束的松弛变量的值等于零，即表
23、明该资源恰恰用完。这种该资源恰恰用完。这种该资源恰恰用完。这种该资源恰恰用完。这种资源增加一个单位，目标函资源增加一个单位，目标函资源增加一个单位，目标函资源增加一个单位，目标函数值就改进一个影子价格数值就改进一个影子价格数值就改进一个影子价格数值就改进一个影子价格。由此可见，影影影影子子子子价价价价格格格格大大大大于于于于零零零零，说说说说明明明明资资资资源源源源紧紧紧紧缺缺缺缺；影影影影子子子子价价价价格格格格等等等等于于于于零零零零，说说说说明明明明资资资资源源源源有有有有剩剩剩剩余余余余。影影影影子子子子价价价价格格格格愈愈愈愈大大大大，说说说说明明明明该该该该资资资资源源源源愈愈愈愈
24、紧紧紧紧缺缺缺缺，该该该该种种种种资源每增加一个单位所相应增加的目标函数值愈大资源每增加一个单位所相应增加的目标函数值愈大资源每增加一个单位所相应增加的目标函数值愈大资源每增加一个单位所相应增加的目标函数值愈大。第三十一页，本课件共有68页如果如果xn+i=0,必有必有yi0，资源紧缺；，资源紧缺；如果如果xn+i0,必有必有yi0，资源剩余。，资源剩余。松弛变量松弛变量松弛变量松弛变量x xs s对偶变量对偶变量对偶变量对偶变量y yi i资源限量资源限量资源限量资源限量b bi i第三十二页，本课件共有68页（2）应用影子价格来合理分配资源算出各种资源的影子价格后，可参考影子价格高低顺序合
25、理分配资源，高者优先投资。同时，也可以参考资源的影子价格，合理地确定各种资源的价格。第三十三页，本课件共有68页2-4 对偶单纯形法对偶单纯形法引言引言引言引言前面介绍的单纯形法，是从一个基本可行解开始进行迭代运算，在迭代过程中，始终保持解的可行性，当所有检验数都非正时，就得到了原问题的最优解。根据对偶定理，原问题单纯形表中的检验数实际上是对偶问题的一组解，但不一定可行，检验数逐渐变为非正的过程，可以理解为对偶问题解的不可行性逐渐消失的过程，当对偶问题的解变为可行解时，原问题就得到了最优解。因此，我们可以选择在对偶问题的解之间进行迭代运算，在迭代过程中，始终保持最优判别条件得到满足，当求出对偶
26、问题的可行解时，也就得到了原问题的最优解。返回本章目录第三十四页，本课件共有68页例例4 4 用对偶单纯形法求解线性规划问题：用对偶单纯形法求解线性规划问题：将约束条件两边同时乘以“-1”得：标准形式标准形式得到初始基为：得到初始基为：得到初始基为：得到初始基为：基基基基变变变变量量量量为为为为y y4 4,y y5 5，非非非非基基基基变变变变量量量量为为为为y y1 1,y y2 2,y y3 3。令令令令所所所所有有有有的的的的非非非非基基基基变变变变量量量量等等等等于于于于0 0，得到该问题的一个解为：得到该问题的一个解为：得到该问题的一个解为：得到该问题的一个解为：Y=(0,0,0,
27、-2,-1)Y=(0,0,0,-2,-1)T T这这这这个个个个解解解解不不不不可可可可行行行行，称称称称为为为为正正正正则则则则解解解解。对对对对偶偶偶偶单单单单纯纯纯纯形形形形法法法法就就就就是是是是从从从从一一一一个正则解开始迭代的。个正则解开始迭代的。个正则解开始迭代的。个正则解开始迭代的。第三十五页，本课件共有68页表表2-82-8c cj j-15-15-24-24-5-50 00 0C CB B基基基基b by y1 1y y2 2y y3 3y y4 4y y5 50 0y y4 4-2-20 0-6-6-1-11 10 00 0y y5 5-1-1-5-5-2-2-1-10
28、01 1c cj jz zj j-15-15-24-24-5-50 00 01.1.确定换出变量确定换出变量确定换出变量确定换出变量y4为换出变量2.2.2.2.确定换入变量确定换入变量确定换入变量确定换入变量y2为换入变量。3.3.3.3.迭迭迭迭代代代代运运运运算算算算，得得得得新单纯形表。新单纯形表。新单纯形表。新单纯形表。-2424y y2 21/31/30 01 11/61/6-1/6-1/60 00 0y y5 5-1/31/3-5-50 0-2/3-2/3-1/3-1/31 1c cj jz zj j-15-150 0-1-1-4-40 0-2424y y2 21/41/4-5/
29、4-5/41 10 0-1/4-1/41/41/4-5-5y y3 31/21/215/215/20 01 11/21/2-3/2-3/2c cj jz zj j-15/215/20 00 0-7/2-7/2-3/2-3/2s s s sj j00，最优解，最优解，最优解，最优解Y=(0,1/4,1/2,0,0)Y=(0,1/4,1/2,0,0)T TMin w=15yMin w=15y1 1+24y+24y2 2+5y+5y3 3=17/2=17/2第三十六页，本课件共有68页2-5 灵敏度分析灵敏度分析对对一一线线性性规规划划问问题题来来说说，一一旦旦其其约约束束条条件件系系数数矩矩阵阵A
30、、约约束束条条件件右右侧侧常常数数向向量量b和和价价值值系系数数向向量量C给给定定之之后后，这这个个线线性性规规划划问问题题就就确确定定了了。反反之之，给给定定一一个个线线性性规规划划问问题题，就就有有确定的一组确定的一组A、b和和C与之对应。与之对应。在在此此之之前前，我我们们一一直直假假定定A、b和和C中中的的元元素素是是常常数数，它它们们不不发发生生变变化化。但但实实际际上上这这些些系系数数往往往往是是通通过过估估计计、预预测测或或人为决策得来的，不可能十分准确和一成不变。人为决策得来的，不可能十分准确和一成不变。例例如如：市市场场条条件件一一变变，价价值值系系数数cj就就会会跟跟着着变
31、变化化；约约束束条条件件系系数数矩矩阵阵A中中的的元元素素aij往往往往随随着着工工艺艺技技术术条条件件的的变变化化而而改变；改变；bi通常取决于现有条件和决策人的决策。通常取决于现有条件和决策人的决策。这这就就是是说说，随随着着时时间间的的推推移移或或情情况况的的变变化化，我我们们往往往往需需要要修修改改原原来来线线性性规规划划问问题题中中的的若若干干系系数数，从从而而使使原原来来的的规规划划问题有所改变。问题有所改变。就就实实际际需需要要来来讲讲，求求出出最最优优解解，还还不不能能说说问问题题已已完完全全解解决。决策者还需要知道以下一些问题。决。决策者还需要知道以下一些问题。返回本章目录第
32、三十七页，本课件共有68页1.当当这这些些系系数数中中的的一一个个或或几几个个发发生生变变化化时时，已已求求得得的的最最优优解有什么变化？解有什么变化？2.这这些些系系数数在在什什么么范范围围内内改改变变时时，规规划划问问题题的的最最优优解解或或最最优基不变？优基不变？3.若最优解变化，如何用最简便的方法找到新的最优解？若最优解变化，如何用最简便的方法找到新的最优解？FF灵灵灵灵敏敏敏敏度度度度分分分分析析析析就就就就是是是是研研研研究究究究提提提提出出出出在在在在原原原原始始始始计计计计算算算算结结结结果果果果基基基基础础础础上上上上直直直直接接接接分分分分析参数变化对最优解影响的方法析参数
33、变化对最优解影响的方法析参数变化对最优解影响的方法析参数变化对最优解影响的方法。灵敏度分析的步骤：灵敏度分析的步骤：灵敏度分析的步骤：灵敏度分析的步骤：（1 1）将参数的变化反映到最终单纯形表上；）将参数的变化反映到最终单纯形表上；（2 2）检查原问题是否仍为最优解；）检查原问题是否仍为最优解；（3 3）检查对偶问题是否仍为最优解；）检查对偶问题是否仍为最优解；（4 4）按下表所列情况得出结论，决定继续计算的步骤。）按下表所列情况得出结论，决定继续计算的步骤。第三十八页，本课件共有68页灵敏度分析的有关计算公式灵敏度分析的有关计算公式表2-9原问题原问题原问题原问题对偶问题对偶问题对偶问题对偶
34、问题结论或继续计算的步骤结论或继续计算的步骤结论或继续计算的步骤结论或继续计算的步骤可行解可行解问题的最优解或最优基不变可行解非可行解用单纯形法继续迭代求最优解非可行解可行解用对偶单纯形法继续迭代求最优解非可行解非可行解引进人工变量，重新编单纯形表计算第三十九页，本课件共有68页美美美美佳佳佳佳公公公公司司司司用用用用三三三三中中中中资资资资源源源源生生生生产产产产两两两两种种种种产产产产品品品品的的的的线线线线性性性性规规规规划划划划模模模模型型型型初初初初始始始始单单单单纯纯纯纯形形形形表：表：表：表：初始单纯形表初始单纯形表初始单纯形表初始单纯形表c cj j 2 21 10 00 00
35、 0C CB B基基基基b bx x1 1x x2 2x x3 3x x4 4x x5 50 0 x x3 315150 05 51 10 00 00 0 x x4 424246 62 20 01 10 00 0 x x5 55 51 11 10 00 01 1c cj jz zj j2 21 10 00 00 0第四十页，本课件共有68页灵敏度分析的主要内容灵敏度分析的主要内容一、一、分析分析cj变化变化二、二、分析分析bi的变化的变化三、三、增加一个变量增加一个变量x xj j的分析的分析四、四、分析参数分析参数aij的变化的变化五、五、增加一个约束条件的分析增加一个约束条件的分析第四十一
36、页，本课件共有68页（1）美佳公司家电的利润降至1.5元/件，家电的利润增至2元/件。一、分析一、分析一、分析一、分析 c cj j 的变化（例的变化（例的变化（例的变化（例 5 5 5 5）最终单纯表最终单纯表最终单纯表最终单纯表c cj j 2 21 10 00 00 0C CB B基基基基b bx x1 1x x2 2x x3 3x x4 4x x5 50 0 x x3 315/215/20 00 01 15/45/4-15/2-15/22 2x x1 17/27/21 10 00 01/41/4-1/2-1/21 1x x2 23/23/20 01 10 0-1/4-1/43/23/2
37、c cj jz zj j0 00 00 0-1/4-1/4-1/2-1/20 0 x x4 46 60 00 04/54/51 1-6-61.51.5x x1 12 21 10 0-1/5-1/50 01 12 2x x2 23 30 01 11/51/50 00 0c cj jz zj j0 00 0-1/10-1/100 0-3/2-3/2y1=0,y2=1/4,y3=1/21.521.521/8-9/4返回提要第四十二页，本课件共有68页家电的利润变化范围：若要保持最优解不变，必须(2)(2)(2)(2)家电家电家电家电的利润变为（的利润变为（的利润变为（的利润变为（1 1 1 1）元）
38、元）元）元最终单纯表最终单纯表最终单纯表最终单纯表c cj j 2 21 10 00 00 0C CB B基基基基b bx x1 1x x2 2x x3 3x x4 4x x5 50 0 x x3 315/215/20 00 01 15/45/4-15/2-15/22 2x x1 17/27/21 10 00 01/41/4-1/2-1/21 1x x2 23/23/20 01 10 0-1/4-1/43/23/2c cj jz zj j0 00 00 0-1/4-1/4-1/2-1/21+l l1+l l第四十三页，本课件共有68页二、分析二、分析 bi 的变化（的变化（例例 6）最终单纯表
39、最终单纯表最终单纯表最终单纯表c cj j 2 21 10 00 00 0C CB B基基基基b bx x1 1x x2 2x x3 3x x4 4x x5 50 0 x x3 315/215/20 00 01 15/45/4-15/2-15/22 2x x1 17/27/21 10 00 01/41/4-1/2-1/21 1x x2 23/23/20 01 10 0-1/4-1/43/23/2c cj jz zj j0 00 00 0-1/4-1/4-1/2-1/2（1）美家公司设备A和调试工序的每天能力不变，设备B每天的能力增加到32小时，分析公司最优计划的变化。35/211/2-1/20
40、 0 x x3 315150 05 51 10 00 02 2x x1 15 51 11 10 00 01 10 0 x x4 42 20 0-4-40 01 1-6-6c cj jz zj j0 0-1-10 00 0-2-2返回提要第四十四页，本课件共有68页（2 2）设设设设备备备备A A和和和和设设设设备备备备B B可可可可用用用用能能能能力力力力不不不不变变变变，则则则则调调调调试试试试工工工工序序序序能能能能力力力力在在在在什什什什么么么么范范范范围变化时，问题的最优基不变。围变化时，问题的最优基不变。围变化时，问题的最优基不变。围变化时，问题的最优基不变。最终单纯表最终单纯表最终
41、单纯表最终单纯表c cj j 2 21 10 00 00 0C CB B基基基基b bx x1 1x x2 2x x3 3x x4 4x x5 50 0 x x3 315/215/20 00 01 15/45/4-15/2-15/22 2x x1 17/27/21 10 00 01/41/4-1/2-1/21 1x x2 23/23/20 01 10 0-1/4-1/43/23/2c cj jz zj j0 00 00 0-1/4-1/4-1/2-1/2设调试工序每天可用能力为（5+l）小时。调试工序能力在调试工序能力在4 4之间之间变化时，最优基不变。变化时，最优基不变。第四十五页，本课件共
42、有68页三、增加一个变量三、增加一个变量xj的分析的分析增加一个变量在实际问题中表示增加一种新产品。分析步骤：例7 美佳佳公司计划推出新型产品家电，生产一件所需设备A、B及调试工序的时间分别为3小时、4小时、2小时，该产品的预期盈利为3元/件，试分析该产品是否值得投产；如投产，该公司生产计划有何变化。解：设该公司每天生产家电x6件，则有c6=3;P6=(3,4,2)T返回提要第四十六页，本课件共有68页例例 7 7最终单纯形表最终单纯形表最终单纯形表最终单纯形表c cj j 2 21 10 00 00 0C CB B基基基基b bx x1 1x x2 2x x3 3x x4 4x x5 50
43、0 x x3 315/215/20 00 01 15/45/4-15/2-15/22 2x x1 17/27/21 10 00 01/41/4-1/2-1/21 1x x2 23/23/20 01 10 0-1/4-1/43/23/2c cj jz zj j0 00 00 0-1/4-1/4-1/2-1/2x63-70210 0 x x3 33/43/40 07/27/21 13/83/8-9/4-9/40 02 2x x1 17/27/21 10 00 01/41/4-1/2-1/20 01 1x x6 63/43/40 01/21/20 0-1/8-1/83/43/41 1c cj jz
44、zj j0 0-1/2-1/20 0-1/8-1/8-5/4-5/40 0美美美美佳佳公公公公司司司司新新新新的的的的最最最最优优优优生生生生产产产产计计计计划划划划应应应应为为为为每每每每天天天天生生生生产产产产家家家家电电电电7/27/2件件件件，家家家家电电电电3/43/4件。可获得利润件。可获得利润件。可获得利润件。可获得利润27/227/210+33/410+33/437/437/4（元）（元）（元）（元）第四十七页，本课件共有68页四、分析参数四、分析参数aij的变化的变化aij 的变化将引起约束条件系数矩阵的变化将引起约束条件系数矩阵 A 发生变化。发生变化。例例8 在在美美佳佳
45、公公司司的的例例子子中中，若若家家电电每每件件需需设设备备A、B和和调调试试工工时时变变为为8小小时时、4小小时时、1小小时时，该该产产品品的的利利润润变变为为3元元/件，试重新确定该公司的最优生产计划。件，试重新确定该公司的最优生产计划。解解：将将生生产产工工时时变变化化后后的的新新家家电电看看作作是是一一种种新新产产品品，生产量为生产量为x2，则，则返回提要第四十八页，本课件共有68页例例8 8最终单纯形表最终单纯形表最终单纯形表最终单纯形表c cj j 2 21 13 30 00 00 0C CB B基基基基b bx x1 1x x2 2x x2 2 x x3 3x x4 4x x5 5
46、0 0 x x3 315/215/20 00 011/211/21 15/45/4-15/2-15/22 2x x1 17/27/21 10 01/21/20 01/41/4-1/2-1/21 1x x2 23/23/20 01 11/21/20 0-1/4-1/43/23/2c cj jz zj j0 00 03/23/20 0-1/4-1/4-1/2-1/20 0 x x3 3-9-90 00 01 14 4-24-242 2x x1 12 21 10 00 01/21/2-2-23 3x x2 2 3 30 01 10 0-1/2-1/23 3c cj jz zj j0 00 00 01
47、/21/2-5-5从上表看出，原问题和对偶问题均为非可行解，故先设法使原问题变为可行解。x34x424x59x34x424x5x69人人工工变变量量第四十九页，本课件共有68页表2-19c cj j2 23 30 00 00 0MMC CB B基基基基b bx x1 1x x2 2 x x3 3x x4 4x x5 5x x6 6-M-Mx x6 69 90 00 0-1-1-4-424241 12 2x x1 12 21 10 00 01/21/2-2-20 03 3x x2 2 3 30 01 10 0-1/2-1/23 30 0c cj jz zj j0 00 0-M-M-4M-4M-5
48、+24M-5+24M0 00 0 x x5 53/83/80 00 0-1/24-1/24-1/6-1/61 11/241/242 2x x1 111/411/41 10 0-1/12-1/121/61/60 01/121/123 3x x2 2 15/815/80 01 11/81/80 00 0-1/8-1/8c cj jz zj j0 00 0-5/24-5/24-1/30 0-M+5/24-M+5/24因为所有检验数因为所有检验数因为所有检验数因为所有检验数s s s sj j00，所以得到问题的最优解，即美，所以得到问题的最优解，即美，所以得到问题的最优解，即美，所以得到问题的最优解
49、，即美佳佳公司的公司的公司的公司的最优生产计划是每天生产家电最优生产计划是每天生产家电最优生产计划是每天生产家电最优生产计划是每天生产家电11/411/4件，新家电件，新家电件，新家电件，新家电15/815/8件。件。件。件。第五十页，本课件共有68页c cj j2 21 13 30 00 00 0C CB B基基基基b bx x1 1x x2 2x x2 2 x x3 3x x4 4x x5 50 0 x x3 3-9-90 00 01 14 4-24-242 2x x1 12 21 10 00 01/21/2-2-23 3x x2 2 3 30 01 10 0-1/2-1/23 3c cj
50、 jz zj j0 00 00 01/21/2-5-5如如如如果果果果不不不不加加加加人人人人工工工工变变变变量量量量，可可可可用用用用对对对对偶偶偶偶单单单单纯纯纯纯形形形形法法法法从从从从正正正正则则则则解解解解开开开开始始始始迭迭迭迭代代代代找找找找出最优解。出最优解。出最优解。出最优解。0 0 x x5 53/83/80 00 0-1/24-1/24-1/6-1/61 12 2x x1 111/411/41 10 0-1/12-1/121/61/60 03 3x x2 2 15/815/80 01 11/81/80 00 0c cj jz zj j0 00 0-5/24-5/24-1/