第二章对偶理论和灵敏度分析优秀PPT.ppt

《第二章对偶理论和灵敏度分析优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第二章对偶理论和灵敏度分析优秀PPT.ppt（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章对偶理论和灵敏度分析第一页，本课件共有70页1.矩阵的加法矩阵的加法相加的两个矩阵必须具有相同的行数和列数相同的行数和列数预备知识预备知识第二页，本课件共有70页2.矩阵的数量乘法矩阵的数量乘法用数乘一个矩阵，需要把矩阵中的每个元素都乘上每个元素都乘上k预备知识预备知识第三页，本课件共有70页3.矩阵的乘法矩阵的乘法左矩阵A的列数的列数必须等于等于右矩阵B的行数的行数不满足交换律不满足交换律预备知识预备知识第四页，本课件共有70页4.矩阵的转置矩阵的转置5.可逆矩阵可逆矩阵A-1A=AA-1=I预备知识预备知识第五页，本课件共有70页2.1 单纯形法的矩阵描述单纯形法的矩阵描述对于线性规

2、划问题：对于线性规划问题：令：令：第六页，本课件共有70页2.1 单纯形法的矩阵描述单纯形法的矩阵描述将原问题化为标准型（加入松弛变量），得将原问题化为标准型（加入松弛变量），得第七页，本课件共有70页得到初始的单纯形表：得到初始的单纯形表：此时前此时前m列可以凑成一个基，用列可以凑成一个基，用B表示：表示：2.1 单纯形法的矩阵描述单纯形法的矩阵描述第八页，本课件共有70页得到初始的单纯形表：得到初始的单纯形表：第第m+1列至列至n列为非基变量，用列为非基变量，用N表示：表示：2.1 单纯形法的矩阵描述单纯形法的矩阵描述第九页，本课件共有70页得到初始的单纯形表：得到初始的单纯形表：第第n+

3、1列至列至n+m列为松弛变量，用列为松弛变量，用S表示：表示：2.1 单纯形法的矩阵描述单纯形法的矩阵描述第十页，本课件共有70页因此，原单纯形表可分解为：因此，原单纯形表可分解为：用B-1左乘系数矩阵用CB左乘系数矩阵，再加到最后一行2.1 单纯形法的矩阵描述单纯形法的矩阵描述非基变量是什么？非基变量是什么？非基变量的检验数是什么？非基变量的检验数是什么？第十一页，本课件共有70页n用矩阵运算的方法也可以求解线性规划问题，其本质与用矩阵运算的方法也可以求解线性规划问题，其本质与单纯形法一样，非基变量检验数的判断方法也与单纯形单纯形法一样，非基变量检验数的判断方法也与单纯形法相同。法相同。n用

4、矩阵运算的方法求解例用矩阵运算的方法求解例1 1：2.2 改进单纯形法改进单纯形法第十二页，本课件共有70页2.2 改进单纯形法改进单纯形法通过观察检验数，发现未达到最优，需要换基，x2入基，x5出基第十三页，本课件共有70页2.2 改进单纯形法改进单纯形法由于由于 p3,p4,p2 为基向量为基向量而而 p1,p5 为非基向量为非基向量则原单纯形表变为则原单纯形表变为第十四页，本课件共有70页2.2 改进单纯形法改进单纯形法通过观察检验数，发现未达到最优，需要换基，x1入基，x3出基第十五页，本课件共有70页2.2 改进单纯形法改进单纯形法由于由于 p1,p4,p2 为基向量为基向量而而 p

5、3,p5 为非基向量为非基向量则原单纯形表变为则原单纯形表变为第十六页，本课件共有70页2.2 改进单纯形法改进单纯形法通过观察检验数，发现未达到最优，需要换基，x5入基，x4出基第十七页，本课件共有70页n求出最终的单纯形表为：求出最终的单纯形表为：2.2 改进单纯形法改进单纯形法第十八页，本课件共有70页B-1练习题练习题第十九页，本课件共有70页n对偶对偶是指同一事物（问题）从不同的角度（立场）是指同一事物（问题）从不同的角度（立场）观察，有观察，有两种相对两种相对的表述。的表述。n每一个线性规划问题，都存在一个与它密切相关的每一个线性规划问题，都存在一个与它密切相关的另一个线性规划问题

6、，我们称其中任意一个为另一个线性规划问题，我们称其中任意一个为原问原问题题，另一个则称为它的，另一个则称为它的对偶问题对偶问题。2.3 对偶问题的提出对偶问题的提出第二十页，本课件共有70页例例 某工厂在计划期内安排、两种产品，生产单位产品所需设备A、B、C台时如表所示。该工厂每生产一单位产品 I 可获利50元，每生产一单位产品 II 可获利100元，问工厂应分别生产多少 I 产品和 II 产品，才能使工厂获利最多？解：设工厂生产 I 产品 x1 件，生产 II 产品 x2 件，建模如下：假如有另外一个工厂要求租用该厂的设备A、B、C，那么每台时设备的租金应该定多少，才不至于亏损？2.3 对偶

7、问题的提出对偶问题的提出第二十一页，本课件共有70页解：设设备 A、B、C 每台时的租金分别为 y1，y2，y3 元，建模如下：比较原问题和对偶问题：原问题对偶问题2.3 对偶问题的提出对偶问题的提出第二十二页，本课件共有70页原关系对偶关系2.3 对偶问题的提出对偶问题的提出第二十三页，本课件共有70页用矩阵形式表示原问题和对偶问题的关系：用矩阵形式表示原问题和对偶问题的关系：原问题对偶问题原问题对偶问题2.3 对偶问题的提出对偶问题的提出第二十四页，本课件共有70页写出下列线性规划问题的对偶问题：写出下列线性规划问题的对偶问题：练习题练习题第二十五页，本课件共有70页n对于线性规划问题：对

8、于线性规划问题：n基基B对应的单纯形表如下：对应的单纯形表如下：n当非基变量的检验数均小于或等于当非基变量的检验数均小于或等于0的时候，该线性规划问的时候，该线性规划问题可以得到最优解，即题可以得到最优解，即2.4 对偶问题的基本性质对偶问题的基本性质第二十六页，本课件共有70页n上式中均含有乘子上式中均含有乘子 CBB-1,称它为称它为单纯形乘子单纯形乘子，并令，并令n则有则有 Y0包括基变量在内的所有检验数可以表示为：包括基变量在内的所有检验数可以表示为：原先性规划问题的最优值为原先性规划问题的最优值为2.4 对偶问题的基本性质对偶问题的基本性质第二十七页，本课件共有70页n这样，即可得到

9、原线性规划的对偶问题这样，即可得到原线性规划的对偶问题:2.4 对偶问题的基本性质对偶问题的基本性质第二十八页，本课件共有70页n对称性对称性 对偶问题的对偶是原问题对偶问题的对偶是原问题2.4 对偶问题的基本性质对偶问题的基本性质-1原问题对偶问题第二十九页，本课件共有70页n弱对偶性弱对偶性 若若 X0 是原问题的可行解，是原问题的可行解，Y0 是对偶问题是对偶问题的可行解，则存在的可行解，则存在 CX0Y0b。2.4 对偶问题的基本性质对偶问题的基本性质-2原问题对偶问题第三十页，本课件共有70页n无界性无界性 若原问题存在无界解，则其对偶问题无可行解。若原问题存在无界解，则其对偶问题无

10、可行解。n反证法：若对偶问题存在可行解反证法：若对偶问题存在可行解 Y0，根据弱对偶性，可知，根据弱对偶性，可知 CXY0b 而而 Y0b 是一个定数，这与原问题无界相矛盾。是一个定数，这与原问题无界相矛盾。n推论：推论：若对偶问题存在无界解，则其原问题无可行解。若对偶问题存在无界解，则其原问题无可行解。2.4 对偶问题的基本性质对偶问题的基本性质-3为什么？第三十一页，本课件共有70页n若若 X0 是原问题的可行解，是原问题的可行解，Y0 是对偶问题的可行解，是对偶问题的可行解，当当 CX0=Y0b 时，时，X0，Y0 分别分别是原问题和其对偶问题是原问题和其对偶问题的最优解的最优解。n根据

11、弱对偶性可知，对原问题的任一可行解根据弱对偶性可知，对原问题的任一可行解 X，均有，均有 CXY0b 由于由于 CX0=Y0b，可知，可知 CXCX0 从而可知从而可知 X0 是原问题的最优解。是原问题的最优解。同理，可证同理，可证 Y0 是其对偶问题的最优解。是其对偶问题的最优解。2.4 对偶问题的基本性质对偶问题的基本性质-4第三十二页，本课件共有70页n对偶定理对偶定理 若原问题有最优解，则对偶问题也有最优若原问题有最优解，则对偶问题也有最优解，且目标函数值相等解，且目标函数值相等。n令令 X*为原问题的最优解，则为原问题的最优解，则 同时，检验数要满足同时，检验数要满足 令令 可知可知

12、 Y*是其对偶问题的一个可行解。是其对偶问题的一个可行解。又又 根据性质根据性质4，可知，可知 Y*是其对偶问题的最优解。是其对偶问题的最优解。2.4 对偶问题的基本性质对偶问题的基本性质-5第三十三页，本课件共有70页n互补松弛性互补松弛性 若若 X*和和 Y*分别为原问题和对偶问题的分别为原问题和对偶问题的可行解，那么可行解，那么 其中其中 Xs*和和 Ys*分别为松弛变量和剩余变量解的集合。分别为松弛变量和剩余变量解的集合。2.4 对偶问题的基本性质对偶问题的基本性质-6第三十四页，本课件共有70页n例题：已知线性规划问题：例题：已知线性规划问题：n已知其对偶问题的最优解为已知其对偶问题

13、的最优解为 y1*=4/5，y2*=3/5；z=5。n试用对偶理论找出原问题的最优解试用对偶理论找出原问题的最优解。2.4 对偶问题的基本性质对偶问题的基本性质-6第三十五页，本课件共有70页n基解的互补性基解的互补性原问题的一个基解，对应其对偶问题的一个基解，原问题的一个基解，对应其对偶问题的一个基解，并且该对互补基解的目标函数值相等；并且该对互补基解的目标函数值相等；当求得原问题在基当求得原问题在基 B 下的单纯形表后，表中检验下的单纯形表后，表中检验数行相反的数（即数行相反的数（即），就是其对偶问题的一个），就是其对偶问题的一个基解。基解。2.4 对偶问题的基本性质对偶问题的基本性质-7

14、第三十六页，本课件共有70页n将下列线性规划模型（例将下列线性规划模型（例1 1）转化为对偶问题）转化为对偶问题 2.5 对偶问题的经济解释对偶问题的经济解释影子价格影子价格用大M法求解第三十七页，本课件共有70页n最终单纯形表为：最终单纯形表为：2.5 对偶问题的经济解释对偶问题的经济解释影子价格影子价格第三十八页，本课件共有70页n由例由例1 1可知：可知：2.5 对偶问题的经济解释对偶问题的经济解释影子价格影子价格设备增加1台时，总利润增加1.5元原料A的供应增加1kg，总利润增加0.125元原料B的供应增加1kg，总利润没有变化第三十九页，本课件共有70页n将例将例1 1中设备限制增加

15、中设备限制增加1 1台时，则原线性规划问题变为：台时，则原线性规划问题变为：2.5 对偶问题的经济解释对偶问题的经济解释影子价格影子价格用图解法求解第四十页，本课件共有70页n将例将例1 1中原料中原料B B的供应量增加到的供应量增加到20kg20kg，则原线性规划问，则原线性规划问题变为：题变为：2.5 对偶问题的经济解释对偶问题的经济解释影子价格影子价格用图解法求解第四十一页，本课件共有70页n对偶问题的最优解往往代表对第对偶问题的最优解往往代表对第 i 种资源的估价，这种资源的估价，这种估价是针对具体工厂的具体产品而存在的一种特殊种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为

16、价格，称它为“影子价格影子价格”。n影子价格随具体情况而异，在完全市场经济的条影子价格随具体情况而异，在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企件下，当某种资源的市场价低于影子价格时，企业应买进该资源用于扩大生产；而当某种资源的业应买进该资源用于扩大生产；而当某种资源的市场价高于企业影子价格时，则企业的决策者应市场价高于企业影子价格时，则企业的决策者应把已有资源卖掉。把已有资源卖掉。2.5 对偶问题的经济解释对偶问题的经济解释影子价格影子价格第四十二页，本课件共有70页n解决线性规划问题的另一种方法。解决线性规划问题的另一种方法。n对偶单纯形法与单纯形法的区别：对偶单纯形法与

17、单纯形法的区别：2.6 对偶单纯形法对偶单纯形法单纯形法单纯形法对偶单纯形法对偶单纯形法前提前提保持所有约束条件的常数 b0保持所有的检验数符合目标函数的要求思路思路使所有的检验数符合目标函数的要求使所有约束条件的常数 b0出发点不同第四十三页，本课件共有70页n在以下的情况中，用对偶单纯形法能更好地解决在以下的情况中，用对偶单纯形法能更好地解决线性规划问题：线性规划问题：n变量较少，而约束条件比较多的线性规划问题，可先变换成它的对偶问题，然后用对偶单纯形法求解；n目标函数最小化，且约束条件中含有“”的线性规划问题。2.6 对偶单纯形法对偶单纯形法第四十四页，本课件共有70页n解题步骤解题步骤

18、：（针对求目标函数最大值的情况）：（针对求目标函数最大值的情况）1.根据线性规划问题，列出初始单纯形表。根据线性规划问题，列出初始单纯形表。检查 b 列的数字，如果 b0，且0，则得到最优解；若 b 列的数字至少还有一个 bi0，且0，则进行以下计算。2.6 对偶单纯形法对偶单纯形法第四十五页，本课件共有70页2.确定出基变量确定出基变量n在 b 列中找到最小的一个负数，这个负数所在行的基变量定为出基变量 xk。3.确定入基变量确定入基变量n检查 xk 所在行的各系数 akj(j=1,n)：若所有 akj0，则无可行解，停止计算；若存在 akj0，计算：最小比值所对应的 xt 为入基变量。2.

19、6 对偶单纯形法对偶单纯形法为什么？为什么？第四十六页，本课件共有70页4.以以 akt 为主元进行迭代运算，得到新的单纯形表。为主元进行迭代运算，得到新的单纯形表。5.重复步骤重复步骤14，直到能够判断出解的形式。，直到能够判断出解的形式。用对偶单纯形法求解例1的对偶问题：2.6 对偶单纯形法对偶单纯形法第四十七页，本课件共有70页在约束条件的两边同时乘以（在约束条件的两边同时乘以（-1），且变为最大化，得），且变为最大化，得2.6 对偶单纯形法对偶单纯形法加入松弛变量第四十八页，本课件共有70页建立初始单纯形表：建立初始单纯形表：2.6 对偶单纯形法对偶单纯形法意味着这一行所对应的原基变量

20、为出基变量此行存在 akj0，取第四十九页，本课件共有70页进行迭代：进行迭代：2.6 对偶单纯形法对偶单纯形法第五十页，本课件共有70页2.6 对偶单纯形法对偶单纯形法第五十一页，本课件共有70页2.6 对偶单纯形法对偶单纯形法第五十二页，本课件共有70页比较原问题和对偶问题（第一步）比较原问题和对偶问题（第一步）原问题原问题对偶问题对偶问题第五十三页，本课件共有70页比较原问题和对偶问题（第二步）比较原问题和对偶问题（第二步）原问题原问题对偶问题对偶问题第五十四页，本课件共有70页比较原问题和对偶问题（第三步）比较原问题和对偶问题（第三步）原问题原问题对偶问题对偶问题第五十五页，本课件共有

21、70页比较原问题和对偶问题（第四步）比较原问题和对偶问题（第四步）原问题原问题对偶问题对偶问题第五十六页，本课件共有70页n性质性质2 2：弱对偶性弱对偶性 若若 X0 是原问题的可行解，是原问题的可行解，Y0 是对是对偶问题的可行解，则存在偶问题的可行解，则存在 CX0Y0b。n性质性质4 4：若若 X0 是原问题的可行解，是原问题的可行解，Y0 是对偶问题的可是对偶问题的可行解，当行解，当 CX0=Y0b 时，时，X0，Y0 分别分别是原问题和其对偶是原问题和其对偶问题的最优解问题的最优解。n性质性质5 5：对偶定理对偶定理 若原问题有最优解，则对偶问题也若原问题有最优解，则对偶问题也有最

22、优解，且目标函数值相等有最优解，且目标函数值相等。对照对偶问题的基本性质对照对偶问题的基本性质第五十七页，本课件共有70页n互补松弛性互补松弛性 若若 X*和和 Y*分别为原问题和对偶问题分别为原问题和对偶问题的可行解，那么的可行解，那么 其中其中 Xs*和和 Ys*分别为松弛变量和剩余变量解的集合。分别为松弛变量和剩余变量解的集合。对照对偶问题的基本性质（性质对照对偶问题的基本性质（性质6）第五十八页，本课件共有70页n基解的互补性基解的互补性原问题的一个基解，对应其对偶问题的一个基解，并原问题的一个基解，对应其对偶问题的一个基解，并且该对且该对互补基解互补基解的目标函数值相等；的目标函数值

23、相等；当求得原问题在基当求得原问题在基 B 下的单纯形表后，表中检验数行下的单纯形表后，表中检验数行相反的数（相反的数（即即），就是其对偶问题的一个基解。），就是其对偶问题的一个基解。对照对偶问题的基本性质（性质对照对偶问题的基本性质（性质7）第五十九页，本课件共有70页2.7 灵敏度分析灵敏度分析解决两个问题：解决两个问题：n当 bi、cj、aij 发生变化时，对已求得的最优解有什么影响；n当 bi、cj、aij 在什么范围内变化时，最优解或最优基不变。解决方法：解决方法：n用单纯形法从头计算，得到新的最优解；n灵敏度分析灵敏度分析计算量大，没有计算量大，没有必要必要第六十页，本课件共有70

24、页1.约束条件中常数项约束条件中常数项 b 的灵敏度分析的灵敏度分析假设约束条件中某一常数发生变化（其他常数不变），即：这样，最终单纯形表中原问题的解变为：n如果 XB 0，因检验数不变，故最优基不变，但最优解发生了变化，XB 成为新的最优解；n如果 XB 0，则可用对偶单纯形法在最终单纯形表的基础上继续迭代。第六十一页，本课件共有70页以例1为例，讨论使最优基不变的 b2 的变化范围b2。此时的最优解变此时的最优解变为多少？为多少？第六十二页，本课件共有70页以例以例1 1为例，为例，如果如果 b1 的取值由的取值由 8 变为变为 10，请求出最优解。，请求出最优解。例例1的最终单纯形表如下

25、：的最终单纯形表如下：练习题练习题第六十三页，本课件共有70页2.目标函数中变量系数目标函数中变量系数 C 的灵敏度分析的灵敏度分析若目标函数中的系数 cr 发生变化，可能会引起 CN 或 CB 的变化，即：这样，最终单纯形表中非基变量非基变量所对应的检验数变为：n如果 j0，最优解不变；n如果 j 中存在某个检验数中存在某个检验数0，则需要在最终单纯形表的基础上继续迭代。思考：如果基变量在目标函数中的系数发生变化，基变量对应思考：如果基变量在目标函数中的系数发生变化，基变量对应的检验数是否会有变化？的检验数是否会有变化？第六十四页，本课件共有70页以例1为例，讨论使最优解不变的 c2 的变化

26、范围c2。x2 为基变量，因此，代代入入公公式式因此，当因此，当30 且且 40 时，即时，即 3 c21 时，最优解不变。时，最优解不变。第六十五页，本课件共有70页以例以例1 1为例，为例，如果如果 c3 的取值由的取值由 0 变为变为 1，请求出最优解。，请求出最优解。例例1的最终单纯形表如下：的最终单纯形表如下：练习题练习题c3 为非基变量，因此为非基变量，因此根据以下公式即可求出非根据以下公式即可求出非基变量的检验数：基变量的检验数：第六十六页，本课件共有70页3.约束条件系数矩阵约束条件系数矩阵 A 的灵敏度分析的灵敏度分析在约束条件系数矩阵 A 中，若 xk 的系数列 pk 改变

27、为 pk，则：xk 在最终的单纯形表中所对应的系数列变为：最终单纯形表中，其对应的新的检验数为：n如果 k0，最优解不变；n如果 k0，则需要在最终单纯形表的基础上继续迭代。第六十七页，本课件共有70页n以例1为例，若生产产品 I 的工艺有了改进，生产单位产品 I 所需的设备台时、原料A、B的数量变为 P1=(1,2,1)T，问此时的生产计划应该如何调整。变更后的单纯形表如右图：最终单纯形表中，x1 列的系数为：x1 对应的新的检验数为大大M法法第六十八页，本课件共有70页以例以例1 1为例，为例，如果生产单位产品如果生产单位产品 II 所需的设备台时、原料所需的设备台时、原料A、B的数的数量变为量变为 P2=(1,0,4)T，问此时的生产计划应该如何调整。，问此时的生产计划应该如何调整。例例1的初始和最终单纯形表如下：的初始和最终单纯形表如下：练习题练习题第六十九页，本课件共有70页如果对约束条件进行增减，比如说，增加了某个约如果对约束条件进行增减，比如说，增加了某个约束条件，或减少了某个约束条件，对最终的单纯形束条件，或减少了某个约束条件，对最终的单纯形表会有什么影响？表会有什么影响？在最终的单纯形表中，对相应的约束条件进行增减。在最终的单纯形表中，对相应的约束条件进行增减。思考：思考：第七十页，本课件共有70页