第二章对偶理论和灵敏度分析优秀课件.ppt
第二章对偶理论和灵敏度分析第1页，本讲稿共70页1.矩阵的加法矩阵的加法相加的两个矩阵必须具有相同的行数和列数相同的行数和列数预备知识预备知识第2页，本讲稿共70页2.矩阵的数量乘法矩阵的数量乘法用数乘一个矩阵，需要把矩阵中的每个元素都乘上每个元素都乘上k预备知识预备知识第3页，本讲稿共70页3.矩阵的乘法矩阵的乘法左矩阵A的列数的列数必须等于等于右矩阵B的行数的行数不满足交换律不满足交换律预备知识预备知识第4页，本讲稿共70页4.矩阵的转置矩阵的转置5.可逆矩阵可逆矩阵A-1A=AA-1=I预备知识预备知识第5页，本讲稿共70页2.1 单纯形法的矩阵描述单纯形法的矩阵描述对于线性规划问题：对于线性规划问题：令：令：第6页，本讲稿共70页2.1 单纯形法的矩阵描述单纯形法的矩阵描述将原问题化为标准型（加入松弛变量），得将原问题化为标准型（加入松弛变量），得第7页，本讲稿共70页得到初始的单纯形表：得到初始的单纯形表：此时前此时前m列可以凑成一个基，用列可以凑成一个基，用B表示：表示：2.1 单纯形法的矩阵描述单纯形法的矩阵描述第8页，本讲稿共70页得到初始的单纯形表：得到初始的单纯形表：第第m+1列至列至n列为非基变量，用列为非基变量，用N表示：表示：2.1 单纯形法的矩阵描述单纯形法的矩阵描述第9页，本讲稿共70页得到初始的单纯形表：得到初始的单纯形表：第第n+1列至列至n+m列为松弛变量，用列为松弛变量，用S表示：表示：2.1 单纯形法的矩阵描述单纯形法的矩阵描述第10页，本讲稿共70页因此，原单纯形表可分解为：因此，原单纯形表可分解为：用B-1左乘系数矩阵用CB左乘系数矩阵，再加到最后一行2.1 单纯形法的矩阵描述单纯形法的矩阵描述非基变量是什么？非基变量是什么？非基变量的检验数是什么？非基变量的检验数是什么？第11页，本讲稿共70页n用矩阵运算的方法也可以求解线性规划问题，其本质与用矩阵运算的方法也可以求解线性规划问题，其本质与单纯形法一样，非基变量检验数的判断方法也与单纯形单纯形法一样，非基变量检验数的判断方法也与单纯形法相同。法相同。n用矩阵运算的方法求解例用矩阵运算的方法求解例1 1：2.2 改进单纯形法改进单纯形法第12页，本讲稿共70页2.2 改进单纯形法改进单纯形法通过观察检验数，发现未达到最优，需要换基，x2入基，x5出基第13页，本讲稿共70页2.2 改进单纯形法改进单纯形法由于由于 p3,p4,p2 为基向量为基向量而而 p1,p5 为非基向量为非基向量则原单纯形表变为则原单纯形表变为第14页，本讲稿共70页2.2 改进单纯形法改进单纯形法通过观察检验数，发现未达到最优，需要换基，x1入基，x3出基第15页，本讲稿共70页2.2 改进单纯形法改进单纯形法由于由于 p1,p4,p2 为基向量为基向量而而 p3,p5 为非基向量为非基向量则原单纯形表变为则原单纯形表变为第16页，本讲稿共70页2.2 改进单纯形法改进单纯形法通过观察检验数，发现未达到最优，需要换基，x5入基，x4出基第17页，本讲稿共70页n求出最终的单纯形表为：求出最终的单纯形表为：2.2 改进单纯形法改进单纯形法第18页，本讲稿共70页B-1练习题练习题第19页，本讲稿共70页n对偶对偶是指同一事物（问题）从不同的角度（立场）观是指同一事物（问题）从不同的角度（立场）观察，有察，有两种相对两种相对的表述。的表述。n每一个线性规划问题，都存在一个与它密切相关的另一个每一个线性规划问题，都存在一个与它密切相关的另一个线性规划问题，我们称其中任意一个为线性规划问题，我们称其中任意一个为原问题原问题，另一个则，另一个则称为它的称为它的对偶问题对偶问题。2.3 对偶问题的提出对偶问题的提出第20页，本讲稿共70页例例 某工厂在计划期内安排、两种产品，生产单位产品所需设备A、B、C台时如表所示。该工厂每生产一单位产品 I 可获利50元，每生产一单位产品 II 可获利100元，问工厂应分别生产多少 I 产品和 II 产品，才能使工厂获利最多？解：设工厂生产 I 产品 x1 件，生产 II 产品 x2 件，建模如下：假如有另外一个工厂要求租用该厂的设备A、B、C，那么每台时设备的租金应该定多少，才不至于亏损？2.3 对偶问题的提出对偶问题的提出第21页，本讲稿共70页解：设设备 A、B、C 每台时的租金分别为 y1，y2，y3 元，建模如下：比较原问题和对偶问题：原问题对偶问题2.3 对偶问题的提出对偶问题的提出第22页，本讲稿共70页原关系对偶关系2.3 对偶问题的提出对偶问题的提出第23页，本讲稿共70页用矩阵形式表示原问题和对偶问题的关系：用矩阵形式表示原问题和对偶问题的关系：原问题对偶问题原问题对偶问题2.3 对偶问题的提出对偶问题的提出第24页，本讲稿共70页写出下列线性规划问题的对偶问题：写出下列线性规划问题的对偶问题：练习题练习题第25页，本讲稿共70页n对于线性规划问题：对于线性规划问题：n基基B对应的单纯形表如下：对应的单纯形表如下：n当非基变量的检验数均小于或等于当非基变量的检验数均小于或等于0的时候，该线性规划问题可以的时候，该线性规划问题可以得到最优解，即得到最优解，即2.4 对偶问题的基本性质对偶问题的基本性质第26页，本讲稿共70页n上式中均含有乘子上式中均含有乘子 CBB-1,称它为称它为单纯形乘子单纯形乘子，并令，并令n则有则有 Y0包括基变量在内的所有检验数可以表示为：包括基变量在内的所有检验数可以表示为：原先性规划问题的最优值为原先性规划问题的最优值为2.4 对偶问题的基本性质对偶问题的基本性质第27页，本讲稿共70页n这样，即可得到原线性规划的对偶问题这样，即可得到原线性规划的对偶问题:2.4 对偶问题的基本性质对偶问题的基本性质第28页，本讲稿共70页n对称性对称性 对偶问题的对偶是原问题对偶问题的对偶是原问题2.4 对偶问题的基本性质对偶问题的基本性质-1原问题对偶问题第29页，本讲稿共70页n弱对偶性弱对偶性 若若 X0 是原问题的可行解，是原问题的可行解，Y0 是对偶问题的是对偶问题的可行解，则存在可行解，则存在 CX0Y0b。2.4 对偶问题的基本性质对偶问题的基本性质-2原问题对偶问题第30页，本讲稿共70页n无界性无界性 若原问题存在无界解，则其对偶问题无可行解。若原问题存在无界解，则其对偶问题无可行解。n反证法：若对偶问题存在可行解反证法：若对偶问题存在可行解 Y0，根据弱对偶性，可知，根据弱对偶性，可知 CXY0b 而而 Y0b 是一个定数，这与原问题无界相矛盾。是一个定数，这与原问题无界相矛盾。n推论：推论：若对偶问题存在无界解，则其原问题无可行解。若对偶问题存在无界解，则其原问题无可行解。2.4 对偶问题的基本性质对偶问题的基本性质-3为什么？第31页，本讲稿共70页n若若 X0 是原问题的可行解，是原问题的可行解，Y0 是对偶问题的可行解，是对偶问题的可行解，当当 CX0=Y0b 时，时，X0，Y0 分别分别是原问题和其对偶问题是原问题和其对偶问题的最优解的最优解。n根据弱对偶性可知，对原问题的任一可行解根据弱对偶性可知，对原问题的任一可行解 X，均有，均有 CXY0b 由于由于 CX0=Y0b，可知，可知 CXCX0 从而可知从而可知 X0 是原问题的最优解。是原问题的最优解。同理，可证同理，可证 Y0 是其对偶问题的最优解。是其对偶问题的最优解。2.4 对偶问题的基本性质对偶问题的基本性质-4第32页，本讲稿共70页n对偶定理对偶定理 若原问题有最优解，则对偶问题也有最优解，若原问题有最优解，则对偶问题也有最优解，且目标函数值相等且目标函数值相等。n令令 X*为原问题的最优解，则为原问题的最优解，则 同时，检验数要满足同时，检验数要满足 令令 可知可知 Y*是其对偶问题的一个可行解。是其对偶问题的一个可行解。又又 根据性质根据性质4，可知，可知 Y*是其对偶问题的最优解。是其对偶问题的最优解。2.4 对偶问题的基本性质对偶问题的基本性质-5第33页，本讲稿共70页n互补松弛性互补松弛性 若若 X*和和 Y*分别为原问题和对偶问题的分别为原问题和对偶问题的可行解，那么可行解，那么 其中其中 Xs*和和 Ys*分别为松弛变量和剩余变量解的集合。分别为松弛变量和剩余变量解的集合。2.4 对偶问题的基本性质对偶问题的基本性质-6第34页，本讲稿共70页n例题：已知线性规划问题：例题：已知线性规划问题：n已知其对偶问题的最优解为已知其对偶问题的最优解为 y1*=4/5，y2*=3/5；z=5。n试用对偶理论找出原问题的最优解试用对偶理论找出原问题的最优解。2.4 对偶问题的基本性质对偶问题的基本性质-6第35页，本讲稿共70页n基解的互补性基解的互补性原问题的一个基解，对应其对偶问题的一个基解，并原问题的一个基解，对应其对偶问题的一个基解，并且该对互补基解的目标函数值相等；且该对互补基解的目标函数值相等；当求得原问题在基当求得原问题在基 B 下的单纯形表后，表中检验数行相下的单纯形表后，表中检验数行相反的数（即反的数（即），就是其对偶问题的一个基解。），就是其对偶问题的一个基解。2.4 对偶问题的基本性质对偶问题的基本性质-7第36页，本讲稿共70页n将下列线性规划模型（例将下列线性规划模型（例1 1）转化为对偶问题）转化为对偶问题 2.5 对偶问题的经济解释对偶问题的经济解释影子价格影子价格用大M法求解第37页，本讲稿共70页n最终单纯形表为：最终单纯形表为：2.5 对偶问题的经济解释对偶问题的经济解释影子价格影子价格第38页，本讲稿共70页n由例由例1 1可知：可知：2.5 对偶问题的经济解释对偶问题的经济解释影子价格影子价格设备增加1台时，总利润增加1.5元原料A的供应增加1kg，总利润增加0.125元原料B的供应增加1kg，总利润没有变化第39页，本讲稿共70页n将例将例1 1中设备限制增加中设备限制增加1 1台时，则原线性规划问题变为：台时，则原线性规划问题变为：2.5 对偶问题的经济解释对偶问题的经济解释影子价格影子价格用图解法求解第40页，本讲稿共70页n将例将例1 1中原料中原料B B的供应量增加到的供应量增加到20kg20kg，则原线性规划，则原线性规划问题变为：问题变为：2.5 对偶问题的经济解释对偶问题的经济解释影子价格影子价格用图解法求解第41页，本讲稿共70页n对偶问题的最优解往往代表对第对偶问题的最优解往往代表对第 i 种资源的估价，这种资源的估价，这种估价是针对具体工厂的具体产品而存在的一种特种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为殊价格，称它为“影子价格影子价格”。n影子价格随具体情况而异，在完全市场经济的条件下，影子价格随具体情况而异，在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企业应买进该当某种资源的市场价低于影子价格时，企业应买进该资源用于扩大生产；而当某种资源的市场价高于企业资源用于扩大生产；而当某种资源的市场价高于企业影子价格时，则企业的决策者应把已有资源卖掉。影子价格时，则企业的决策者应把已有资源卖掉。2.5 对偶问题的经济解释对偶问题的经济解释影子价格影子价格第42页，本讲稿共70页n解决线性规划问题的另一种方法。解决线性规划问题的另一种方法。n对偶单纯形法与单纯形法的区别：对偶单纯形法与单纯形法的区别：2.6 对偶单纯形法对偶单纯形法单纯形法单纯形法对偶单纯形法对偶单纯形法前提前提保持所有约束条件的常数 b0保持所有的检验数符合目标函数的要求思路思路使所有的检验数符合目标函数的要求使所有约束条件的常数 b0出发点不同第43页，本讲稿共70页n在以下的情况中，用对偶单纯形法能更好地解决线性在以下的情况中，用对偶单纯形法能更好地解决线性规划问题：规划问题：n变量较少，而约束条件比较多的线性规划问题，可先变换成它的对偶问题，然后用对偶单纯形法求解；n目标函数最小化，且约束条件中含有“”的线性规划问题。2.6 对偶单纯形法对偶单纯形法第44页，本讲稿共70页n解题步骤解题步骤：（针对求目标函数最大值的情况）：（针对求目标函数最大值的情况）1.根据线性规划问题，列出初始单纯形表。根据线性规划问题，列出初始单纯形表。检查 b 列的数字，如果 b0，且0，则得到最优解；若 b 列的数字至少还有一个 bi0，且0，则进行以下计算。2.6 对偶单纯形法对偶单纯形法第45页，本讲稿共70页2.确定出基变量确定出基变量n在 b 列中找到最小的一个负数，这个负数所在行的基变量定为出基变量 xk。3.确定入基变量确定入基变量n检查 xk 所在行的各系数 akj(j=1,n)：若所有 akj0，则无可行解，停止计算；若存在 akj0，计算：最小比值所对应的 xt 为入基变量。2.6 对偶单纯形法对偶单纯形法为什么？为什么？第46页，本讲稿共70页4.以以 akt 为主元进行迭代运算，得到新的单纯形表。为主元进行迭代运算，得到新的单纯形表。5.重复步骤重复步骤14，直到能够判断出解的形式。，直到能够判断出解的形式。用对偶单纯形法求解例1的对偶问题：2.6 对偶单纯形法对偶单纯形法第47页，本讲稿共70页在约束条件的两边同时乘以（在约束条件的两边同时乘以（-1），且变为最大化，得），且变为最大化，得2.6 对偶单纯形法对偶单纯形法加入松弛变量第48页，本讲稿共70页建立初始单纯形表：建立初始单纯形表：2.6 对偶单纯形法对偶单纯形法意味着这一行所对应的原基变量为出基变量此行存在 akj0，取第49页，本讲稿共70页进行迭代：进行迭代：2.6 对偶单纯形法对偶单纯形法第50页，本讲稿共70页2.6 对偶单纯形法对偶单纯形法第51页，本讲稿共70页2.6 对偶单纯形法对偶单纯形法第52页，本讲稿共70页比较原问题和对偶问题（第一步）比较原问题和对偶问题（第一步）原问题原问题对偶问题对偶问题第53页，本讲稿共70页比较原问题和对偶问题（第二步）比较原问题和对偶问题（第二步）原问题原问题对偶问题对偶问题第54页，本讲稿共70页比较原问题和对偶问题（第三步）比较原问题和对偶问题（第三步）原问题原问题对偶问题对偶问题第55页，本讲稿共70页比较原问题和对偶问题（第四步）比较原问题和对偶问题（第四步）原问题原问题对偶问题对偶问题第56页，本讲稿共70页n性质性质2 2：弱对偶性弱对偶性 若若 X0 是原问题的可行解，是原问题的可行解，Y0 是是对偶问题的可行解，则存在对偶问题的可行解，则存在 CX0Y0b。n性质性质4 4：若若 X0 是原问题的可行解，是原问题的可行解，Y0 是对偶问题的可行是对偶问题的可行解，当解，当 CX0=Y0b 时，时，X0，Y0 分别分别是原问题和其对偶是原问题和其对偶问题的最优解问题的最优解。n性质性质5 5：对偶定理对偶定理 若原问题有最优解，则对偶问题也有若原问题有最优解，则对偶问题也有最优解，且目标函数值相等最优解，且目标函数值相等。对照对偶问题的基本性质对照对偶问题的基本性质第57页，本讲稿共70页n互补松弛性互补松弛性 若若 X*和和 Y*分别为原问题和对偶问题的分别为原问题和对偶问题的可行解，那么可行解，那么 其中其中 Xs*和和 Ys*分别为松弛变量和剩余变量解的集合。分别为松弛变量和剩余变量解的集合。对照对偶问题的基本性质（性质对照对偶问题的基本性质（性质6）第58页，本讲稿共70页n基解的互补性基解的互补性原问题的一个基解，对应其对偶问题的一个基解，并原问题的一个基解，对应其对偶问题的一个基解，并且该对且该对互补基解互补基解的目标函数值相等；的目标函数值相等；当求得原问题在基当求得原问题在基 B 下的单纯形表后，表中检验数行下的单纯形表后，表中检验数行相反的数（相反的数（即即），就是其对偶问题的一个基解。），就是其对偶问题的一个基解。对照对偶问题的基本性质（性质对照对偶问题的基本性质（性质7）第59页，本讲稿共70页2.7 灵敏度分析灵敏度分析解决两个问题：解决两个问题：n当 bi、cj、aij 发生变化时，对已求得的最优解有什么影响；n当 bi、cj、aij 在什么范围内变化时，最优解或最优基不变。解决方法：解决方法：n用单纯形法从头计算，得到新的最优解；n灵敏度分析灵敏度分析计算量大，没有计算量大，没有必要必要第60页，本讲稿共70页1.约束条件中常数项约束条件中常数项 b 的灵敏度分析的灵敏度分析假设约束条件中某一常数发生变化（其他常数不变），即：这样，最终单纯形表中原问题的解变为：n如果 XB 0，因检验数不变，故最优基不变，但最优解发生了变化，XB 成为新的最优解；n如果 XB 0，则可用对偶单纯形法在最终单纯形表的基础上继续迭代。第61页，本讲稿共70页以例1为例，讨论使最优基不变的 b2 的变化范围b2。此时的最优解变此时的最优解变为多少？为多少？第62页，本讲稿共70页以例以例1 1为例，为例，如果如果 b1 的取值由的取值由 8 变为变为 10，请求出最优解。，请求出最优解。例例1的最终单纯形表如下：的最终单纯形表如下：练习题练习题第63页，本讲稿共70页2.目标函数中变量系数目标函数中变量系数 C 的灵敏度分析的灵敏度分析若目标函数中的系数 cr 发生变化，可能会引起 CN 或 CB 的变化，即：这样，最终单纯形表中非基变量非基变量所对应的检验数变为：n如果 j0，最优解不变；n如果 j 中存在某个检验数中存在某个检验数0，则需要在最终单纯形表的基础上继续迭代。思考：如果基变量在目标函数中的系数发生变化，基变量对应的检思考：如果基变量在目标函数中的系数发生变化，基变量对应的检验数是否会有变化？验数是否会有变化？第64页，本讲稿共70页以例1为例，讨论使最优解不变的 c2 的变化范围c2。x2 为基变量，因此，代代入入公公式式因此，当因此，当30 且且 40 时，即时，即 3 c21 时，最优解不变。时，最优解不变。第65页，本讲稿共70页以例以例1 1为例，为例，如果如果 c3 的取值由的取值由 0 变为变为 1，请求出最优解。，请求出最优解。例例1的最终单纯形表如下：的最终单纯形表如下：练习题练习题c3 为非基变量，因此为非基变量，因此根据以下公式即可求出非根据以下公式即可求出非基变量的检验数：基变量的检验数：第66页，本讲稿共70页3.约束条件系数矩阵约束条件系数矩阵 A 的灵敏度分析的灵敏度分析在约束条件系数矩阵 A 中，若 xk 的系数列 pk 改变为 pk，则：xk 在最终的单纯形表中所对应的系数列变为：最终单纯形表中，其对应的新的检验数为：n如果 k0，最优解不变；n如果 k0，则需要在最终单纯形表的基础上继续迭代。第67页，本讲稿共70页n以例1为例，若生产产品 I 的工艺有了改进，生产单位产品 I 所需的设备台时、原料A、B的数量变为 P1=(1,2,1)T，问此时的生产计划应该如何调整。变更后的单纯形表如右图：最终单纯形表中，x1 列的系数为：x1 对应的新的检验数为大大M法法第68页，本讲稿共70页以例以例1 1为例，为例，如果生产单位产品如果生产单位产品 II 所需的设备台时、原料所需的设备台时、原料A、B的数量变的数量变为为 P2=(1,0,4)T，问此时的生产计划应该如何调整。，问此时的生产计划应该如何调整。例例1的初始和最终单纯形表如下：的初始和最终单纯形表如下：练习题练习题第69页，本讲稿共70页如果对约束条件进行增减，比如说，增加了某个约束条件，如果对约束条件进行增减，比如说，增加了某个约束条件，或减少了某个约束条件，对最终的单纯形表会有什么影响或减少了某个约束条件，对最终的单纯形表会有什么影响？在最终的单纯形表中，对相应的约束条件进行增减。在最终的单纯形表中，对相应的约束条件进行增减。思考：思考：第70页，本讲稿共70页
