第二章对偶理论和灵敏度分析

第二章对偶理论和灵敏度分析第一页，共七十页，2022年，8月28日矩阵的加法相加的两个矩阵必须具有相同的行数和列数预备知识第二页，共七十页，2022年，8月28日矩阵的数量乘法用数乘一个矩阵，需要把矩阵中的每个元素都乘上k预备知识第三页，共七十页，2022年，8月28日矩阵的乘法左矩阵A的列数必须等于右矩阵B的行数不满足交换律预备知识第四页，共七十页，2022年，8月28日矩阵的转置可逆矩阵A-1A=AA-1=I预备知识第五页，共七十页，2022年，8月28日2.1单纯形法的矩阵描述对于线性规划问题：令：第六页，共七十页，2022年，8月28日2.1单纯形法的矩阵描述将原问题化为标准型（加入松弛变量），得第七页，共七十页，2022年，8月28日得到初始的单纯形表：此时前m列可以凑成一个基，用B表示：2.1单纯形法的矩阵描述第八页，共七十页，2022年，8月28日得到初始的单纯形表：第m+1列至n列为非基变量，用N表示：2.1单纯形法的矩阵描述第九页，共七十页，2022年，8月28日得到初始的单纯形表：第n+1列至n+m列为松弛变量，用S表示：2.1单纯形法的矩阵描述第十页，共七十页，2022年，8月28日因此，原单纯形表可分解为：用B-1左乘系数矩阵用－CB左乘系数矩阵，再加到最后一行2.1单纯形法的矩阵描述非基变量是什么？非基变量的检验数是什么？第十一页，共七十页，2022年，8月28日用矩阵运算的方法也可以求解线性规划问题，其本质与单纯形法一样，非基变量检验数的判断方法也与单纯形法相同。用矩阵运算的方法求解例1：2.2改进单纯形法第十二页，共七十页，2022年，8月28日2.2改进单纯形法通过观察检验数，发现未达到最优，需要换基，x2入基，x5出基第十三页，共七十页，2022年，8月28日2.2改进单纯形法由于p3,p4,p2为基向量而p1,p5为非基向量则原单纯形表变为第十四页，共七十页，2022年，8月28日2.2改进单纯形法通过观察检验数，发现未达到最优，需要换基，x1入基，x3出基第十五页，共七十页，2022年，8月28日2.2改进单纯形法由于p1,p4,p2为基向量而p3,p5为非基向量则原单纯形表变为第十六页，共七十页，2022年，8月28日2.2改进单纯形法通过观察检验数，发现未达到最优，需要换基，x5入基，x4出基第十七页，共七十页，2022年，8月28日求出最终的单纯形表为：2.2改进单纯形法第十八页，共七十页，2022年，8月28日B-1练习题第十九页，共七十页，2022年，8月28日对偶是指同一事物（问题）从不同的角度（立场）观察，有两种相对的表述。每一个线性规划问题，都存在一个与它密切相关的另一个线性规划问题，我们称其中任意一个为原问题，另一个则称为它的对偶问题。

2.3对偶问题的提出第二十页，共七十页，2022年，8月28日例

某工厂在计划期内安排Ⅰ、Ⅱ两种产品，生产单位产品所需设备A、B、C台时如表所示。该工厂每生产一单位产品I可获利50元，每生产一单位产品II可获利100元，问工厂应分别生产多少I产品和II产品，才能使工厂获利最多？

解：设工厂生产I产品x1件，生产II产品x2件，建模如下：假如有另外一个工厂要求租用该厂的设备A、B、C，那么每台时设备的租金应该定多少，才不至于亏损？2.3对偶问题的提出第二十一页，共七十页，2022年，8月28日解：设设备A、B、C每台时的租金分别为y1，y2，y3元，建模如下：比较原问题和对偶问题：原问题对偶问题2.3对偶问题的提出第二十二页，共七十页，2022年，8月28日原关系对偶关系2.3对偶问题的提出第二十三页，共七十页，2022年，8月28日用矩阵形式表示原问题和对偶问题的关系：原问题对偶问题原问题对偶问题2.3对偶问题的提出第二十四页，共七十页，2022年，8月28日写出下列线性规划问题的对偶问题：练习题第二十五页，共七十页，2022年，8月28日对于线性规划问题：基B对应的单纯形表如下：当非基变量的检验数均小于或等于0的时候，该线性规划问题可以得到最优解，即2.4对偶问题的基本性质第二十六页，共七十页，2022年，8月28日上式中均含有乘子

CBB-1

,称它为单纯形乘子，并令则有Y≥0包括基变量在内的所有检验数可以表示为：原先性规划问题的最优值为2.4对偶问题的基本性质第二十七页，共七十页，2022年，8月28日这样，即可得到原线性规划的对偶问题:2.4对偶问题的基本性质第二十八页，共七十页，2022年，8月28日对称性对偶问题的对偶是原问题2.4对偶问题的基本性质-1原问题对偶问题第二十九页，共七十页，2022年，8月28日弱对偶性若X0

是原问题的可行解，Y0

是对偶问题的可行解，则存在CX0≤Y0b。2.4对偶问题的基本性质-2原问题对偶问题第三十页，共七十页，2022年，8月28日无界性若原问题存在无界解，则其对偶问题无可行解。反证法：若对偶问题存在可行解Y0，根据弱对偶性，可知CX≤Y0b而Y0b是一个定数，这与原问题无界相矛盾。推论：若对偶问题存在无界解，则其原问题无可行解。2.4对偶问题的基本性质-3为什么？第三十一页，共七十页，2022年，8月28日若X0

是原问题的可行解，Y0

是对偶问题的可行解，当CX0=Y0b时，X0，Y0分别是原问题和其对偶问题的最优解。根据弱对偶性可知，对原问题的任一可行解X，均有CX≤Y0b由于CX0=Y0b，可知CX≤CX0从而可知X0是原问题的最优解。同理，可证Y0是其对偶问题的最优解。2.4对偶问题的基本性质-4第三十二页，共七十页，2022年，8月28日对偶定理若原问题有最优解，则对偶问题也有最优解，且目标函数值相等。令X*为原问题的最优解，则同时，检验数要满足令

可知Y*是其对偶问题的一个可行解。又根据性质4，可知Y*是其对偶问题的最优解。2.4对偶问题的基本性质-5第三十三页，共七十页，2022年，8月28日互补松弛性若X*和Y*分别为原问题和对偶问题的可行解，那么

其中Xs*和Ys*分别为松弛变量和剩余变量解的集合。2.4对偶问题的基本性质-6第三十四页，共七十页，2022年，8月28日例题：已知线性规划问题：已知其对偶问题的最优解为y1*=4/5，y2*=3/5；z=5。试用对偶理论找出原问题的最优解。2.4对偶问题的基本性质-6第三十五页，共七十页，2022年，8月28日基解的互补性原问题的一个基解，对应其对偶问题的一个基解，并且该对互补基解的目标函数值相等；当求得原问题在基B下的单纯形表后，表中检验数行相反的数（即－σ），就是其对偶问题的一个基解。2.4对偶问题的基本性质-7第三十六页，共七十页，2022年，8月28日将下列线性规划模型（例1）转化为对偶问题

2.5对偶问题的经济解释—影子价格用大M法求解第三十七页，共七十页，2022年，8月28日最终单纯形表为：

2.5对偶问题的经济解释—影子价格第三十八页，共七十页，2022年，8月28日由例1可知：

2.5对偶问题的经济解释—影子价格设备增加1台时，总利润增加1.5元原料A的供应增加1kg，总利润增加0.125元原料B的供应增加1kg，总利润没有变化第三十九页，共七十页，2022年，8月28日将例1中设备限制增加1台时，则原线性规划问题变为：

2.5对偶问题的经济解释—影子价格用图解法求解第四十页，共七十页，2022年，8月28日将例1中原料B的供应量增加到20kg，则原线性规划问题变为：

2.5对偶问题的经济解释—影子价格用图解法求解第四十一页，共七十页，2022年，8月28日对偶问题的最优解往往代表对第i种资源的估价，这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影子价格”。影子价格随具体情况而异，在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企业应买进该资源用于扩大生产；而当某种资源的市场价高于企业影子价格时，则企业的决策者应把已有资源卖掉。2.5对偶问题的经济解释—影子价格第四十二页，共七十页，2022年，8月28日解决线性规划问题的另一种方法。对偶单纯形法与单纯形法的区别：2.6对偶单纯形法单纯形法对偶单纯形法前提保持所有约束条件的常数b≥0保持所有的检验数σ符合目标函数的要求思路使所有的检验数σ符合目标函数的要求使所有约束条件的常数b≥0出发点不同第四十三页，共七十页，2022年，8月28日在以下的情况中，用对偶单纯形法能更好地解决线性规划问题：变量较少，而约束条件比较多的线性规划问题，可先变换成它的对偶问题，然后用对偶单纯形法求解；目标函数最小化，且约束条件中含有“≥”的线性规划问题。2.6对偶单纯形法第四十四页，共七十页，2022年，8月28日解题步骤：（针对求目标函数最大值的情况）根据线性规划问题，列出初始单纯形表。检查b列的数字，如果b≥0，且σ≤0，则得到最优解；若b列的数字至少还有一个bi≤0，且σ≤0，则进行以下计算。2.6对偶单纯形法第四十五页，共七十页，2022年，8月28日确定出基变量在b列中找到最小的一个负数，这个负数所在行的基变量定为出基变量xk。确定入基变量检查xk所在行的各系数akj(j=1,…,n)：若所有akj≥0，则无可行解，停止计算；若存在akj＜0，计算：

最小比值所对应的xt

为入基变量。2.6对偶单纯形法为什么？第四十六页，共七十页，2022年，8月28日以akt

为主元进行迭代运算，得到新的单纯形表。重复步骤1~4，直到能够判断出解的形式。用对偶单纯形法求解例1的对偶问题：2.6对偶单纯形法第四十七页，共七十页，2022年，8月28日在约束条件的两边同时乘以（-1），且变为最大化，得2.6对偶单纯形法加入松弛变量第四十八页，共七十页，2022年，8月28日建立初始单纯形表：2.6对偶单纯形法意味着这一行所对应的原基变量为出基变量此行存在akj＜0，取第四十九页，共七十页，2022年，8月28日进行迭代：2.6对偶单纯形法第五十页，共七十页，2022年，8月28日2.6对偶单纯形法第五十一页，共七十页，2022年，8月28日2.6对偶单纯形法第五十二页，共七十页，2022年，8月28日比较原问题和对偶问题（第一步）原问题对偶问题第五十三页，共七十页，2022年，8月28日比较原问题和对偶问题（第二步）原问题对偶问题第五十四页，共七十页，2022年，8月28日比较原问题和对偶问题（第三步）原问题对偶问题第五十五页，共七十页，2022年，8月28日比较原问题和对偶问题（第四步）原问题对偶问题第五十六页，共七十页，2022年，8月28日性质2：弱对偶性

若X0

是原问题的可行解，Y0

是对偶问题的可行解，则存在CX0≤Y0b。性质4：若X0

是原问题的可行解，Y0

是对偶问题的可行解，当CX0=Y0b时，X0，Y0分别是原问题和其对偶问题的最优解。性质5：对偶定理若原问题有最优解，则对偶问题也有最优解，且目标函数值相等。对照对偶问题的基本性质第五十七页，共七十页，2022年，8月28日互补松弛性若X*和Y*分别为原问题和对偶问题的可行解，那么其中Xs*和Ys*分别为松弛变量和剩余变量解的集合。对照对偶问题的基本性质（性质6）第五十八页，共七十页，2022年，8月28日基解的互补性原问题的一个基解，对应其对偶问题的一个基解，并且该对互补基解的目标函数值相等；当求得原问题在基B下的单纯形表后，表中检验数行相反的数（即－σ），就是其对偶问题的一个基解。对照对偶问题的基本性质（性质7）第五十九页，共七十页，2022年，8月28日2.7灵敏度分析解决两个问题：当bi、cj、aij

发生变化时，对已求得的最优解有什么影响；当bi、cj、aij

在什么范围内变化时，最优解或最优基不变。解决方法：用单纯形法从头计算，得到新的最优解；灵敏度分析计算量大，没有必要第六十页，共七十页，2022年，8月28日1.约束条件中常数项b的灵敏度分析假设约束条件中某一常数发生变化（其他常数不变），即：这样，最终单纯形表中原问题的解变为：如果XB’≥0，因检验数不变，故最优基不变，但最优解发生了变化，XB’成为新的最优解；如果XB’＜0，则可用对偶单纯形法在最终单纯形表的基础上继续迭代。第六十一页，共七十页，2022年，8月28日以例1为例，讨论使最优基不变的b2

的变化范围△b2。此时的最优解变为多少？第六十二页，共七十页，2022年，8月28日以例1为例，如果b1

的取值由8变为10，请求出最优解。例1的最终单纯形表如下：练习题第六十三页，共七十页，2022年，8月28日2.目标函数中变量系数C的灵敏度分析若目标函数中的系数cr

发生变化，可能会引起CN或CB的变化，即：这样，最终单纯形表中非基变量所对应的检验数变为：如果σj‘≤0，最优解不变；如果σj‘中存在某个检验数＞0，则需要在最终单纯形表的基础上继续迭代。思考：如果基变量在目标函数中的系数发生变化，基变量对应的检验数是否会有变化？第六十四页，共七十页，2022年，8月28日以例1为例，讨论使最优解不变的c2

的变化范围△c2。x2为基变量，因此，代入公式因此，当σ3‘≤0且

σ4‘≤0时，即－3≤△