第二章对偶理论与灵敏度分析精选文档.ppt

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

1、第二章第二章对对偶理偶理论论与灵敏度分析与灵敏度分析课课件件本讲稿第一页，共一百三十三页本章重点本章重点1、掌握写出对偶问题的方法，原问题与其对偶问题的对应关系2、掌握对偶问题的基本理论和性质 3、理解影子价格的定义和意义4、理解并掌握对偶单纯形方法的思想和步骤5、掌握线性规划灵敏度分析 (1)资源数量 bi 发生变化的分析 (2)目标函数中价值系数 cj 发生变化的分析难点难点难点难点本讲稿第二页，共一百三十三页XBXNXSbXBBNIbCCBCN00了解-单纯形的矩阵描述XS为松弛变量本讲稿第三页，共一百三十三页XBXNXSbXBIB1N B1B1b N N0CNCBB1NCBB1CBB1

2、b单纯性法计算时，总选取单位矩阵 I 为初始基，对应基变量为XS,设迭代若干步后，基变量变为XB,XB 在初始单纯性表中的系数矩阵为 B。则该步的单纯性表中由 XB 系数组成的矩阵为单位矩阵 I ，对应XS 的系数矩阵在新表中应为B-1 Y=CBB-1 称为单纯性乘子（称为单纯性乘子（对偶变量对偶变量）本讲稿第四页，共一百三十三页2.3 对偶问题提出对偶问题提出 例例2.2：某公司在计划期内要安排生产：某公司在计划期内要安排生产I、II两种产两种产品，已知生产单位产品所需的设备台时及品，已知生产单位产品所需的设备台时及A B两两种原材料的消耗如表所示，该工厂每生产一件产种原材料的消耗如表所示，

3、该工厂每生产一件产品品I可获利可获利2元，每生产一件产品元，每生产一件产品II可获利可获利3元，问元，问应该如何安排计划使该工厂获利最多？应该如何安排计划使该工厂获利最多？举例2本讲稿第五页，共一百三十三页Chapter 2 灵敏度分析灵敏度分析 v先根据图表来列出模型先根据图表来列出模型 Max Z=2X1+3X2 X1+2X2 8 4X1 16 4X2 12 X1,X2 0 举例本讲稿第六页，共一百三十三页v设用设用y1,y2,y3分别表示出租单位设备台时的租分别表示出租单位设备台时的租金和出让单位原材料金和出让单位原材料A,B的附加额的附加额.现现在在从从另另一一个个角角度度来来考考虑虑

4、企企业业的的决决策策问问题题。假假如如企企业业自自己己不不生生产产产产品品，而而将将现现有有的的资资源源转转让让或或出出租租给给其其它它企企业业，那那么么资资源源的的转转让让价价格格是是多多少少才才合合理理？合合理理的的价价格格应应是是对对方方用用最最少少的的资资金金购购买买本本企企业业的的全全部部资资源源，而而本本企企业业所所获获得得的的利利润润不不应应低低于于自自己己用用于于生生产产时时所所获获得得的的利利润润。这这一一决决策策问问题可用下列线性规划数学模型来表示。题可用下列线性规划数学模型来表示。本讲稿第七页，共一百三十三页 他在做定价决策时他在做定价决策时,作如下比较作如下比较:若用一

5、个单位设若用一个单位设备台时和备台时和 4 个单位原材料个单位原材料 A 可以生产一件产品可以生产一件产品 I,可获利可获利 2 元元,那么生产每件产品那么生产每件产品 I 的设备台时和原材料出的设备台时和原材料出租和出让的所有收入应不低于生产一件产品租和出让的所有收入应不低于生产一件产品 I 的的利润利润,这就有这就有 y1+4y22本讲稿第八页，共一百三十三页 同理将生产每件产品同理将生产每件产品 II II 的设备台时和原材料的设备台时和原材料的出租和出让的所有收入应不低于生产一件产的出租和出让的所有收入应不低于生产一件产品品IIII的利润的利润,这就有这就有2y1+4y3 3 把工厂所

6、有设备台时和资源都出租和出让把工厂所有设备台时和资源都出租和出让,其其收入为收入为 f=8y1+16y2+12y3本讲稿第九页，共一百三十三页从工厂决策者的角度来看，从工厂决策者的角度来看，f f当然是越大越好当然是越大越好,但但从接受者眼光来说从接受者眼光来说f f是越少越好是越少越好,所以工厂决策所以工厂决策者只可以在满足者只可以在满足 所有产品的利润条所有产品的利润条件下件下,使其总收入尽可能的小使其总收入尽可能的小.因此因此本讲稿第十页，共一百三十三页v我们称这个线性规划问题为我们称这个线性规划问题为线性规划问题（这称线性规划问题（这称为原问题）的对偶问题为原问题）的对偶问题。各模型中

7、有关数据的。各模型中有关数据的“位置位置”示意图如下。示意图如下。矩阵A矩阵AT本讲稿第十一页，共一百三十三页对偶问题提出对偶问题提出v例例2.3 某工厂拥有某工厂拥有A、B、C三种类型的设备，生产甲、三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。求获最大利润的方案。可利用的时数如下表所示。求获最大利润的方案。本讲稿第十二页，共一百三十三页表表2.3本讲稿第十三页，共一百三十三页不难得出下面一对对偶问题。不难得出下面一对对偶问

8、题。v原问题原问题 本讲稿第十四页，共一百三十三页对偶问题对偶问题 不少于甲产品的利润不少于乙产品的利润本讲稿第十五页，共一百三十三页v例例2.4：资源利用问题：资源利用问题v考虑：资源拥有者为了实现一定的收入目标，考虑：资源拥有者为了实现一定的收入目标，将其所拥有的资源出售，给每一种资源如何定价？将其所拥有的资源出售，给每一种资源如何定价？本讲稿第十六页，共一百三十三页v解：解：表示出售单位数量的第表示出售单位数量的第i种资源的价格。资源拥有者在做出售资源的决策时，种资源的价格。资源拥有者在做出售资源的决策时，考虑出售资源的收入不应该低于生产所获得的收入，考虑出售资源的收入不应该低于生产所获

9、得的收入，则有：则有：本讲稿第十七页，共一百三十三页v如果资源拥有者将所有资源出售，则他得到的如果资源拥有者将所有资源出售，则他得到的总收入总收入 v f=本讲稿第十八页，共一百三十三页v资源拥有者出售每一种资源的最低估价，可通资源拥有者出售每一种资源的最低估价，可通过求解线性规划问题而得到。过求解线性规划问题而得到。本讲稿第十九页，共一百三十三页v对同一个资源利用问题，从不同的角度考对同一个资源利用问题，从不同的角度考虑，可以得到两个相互联系的线性规划模型，虑，可以得到两个相互联系的线性规划模型，这就是线性规划的对偶问题。这就是线性规划的对偶问题。本讲稿第二十页，共一百三十三页由上面的例子我

10、们可以知道原问题与对偶问题的关由上面的例子我们可以知道原问题与对偶问题的关系系1线性规划问题是对称形式线性规划问题是对称形式 Max z=CX Min f=Yb s.t.Ax b s.t.YA c x 0 y 0 “Max-”“Min-”原问题与对偶问题的关系原问题与对偶问题的关系本讲稿第二十一页，共一百三十三页互为转置互为转置列向量列向量行向量行向量n个变量个变量n个约束个约束本讲稿第二十二页，共一百三十三页例例2.5 写出下述问题的对偶问题写出下述问题的对偶问题本讲稿第二十三页，共一百三十三页v解：上述问题的对偶问题为解：上述问题的对偶问题为本讲稿第二十四页，共一百三十三页(1)若一个模型

11、为目标求若一个模型为目标求“极大极大”，约束为，约束为“小小于等于于等于”的不等式，则它的对偶模型为目标求的不等式，则它的对偶模型为目标求“极小极小”，约束是，约束是“大于等于大于等于”的不等式。即的不等式。即“max，”和和“min，”相对应。相对应。如上面例题所示一对对称形式的对偶规划之间如上面例题所示一对对称形式的对偶规划之间具有下面的对应关系具有下面的对应关系本讲稿第二十五页，共一百三十三页(2)从约束系数矩阵看：一个模型中为从约束系数矩阵看：一个模型中为，则另，则另一个模型中为一个模型中为AT。一个模型是。一个模型是m个约束，个约束，n个个变量，则它的对偶模型为变量，则它的对偶模型为

12、n个约束，个约束，m个变量。个变量。(3)从数据从数据b、C的位置看：在两个规划模型中，的位置看：在两个规划模型中，b和和C的位置对换。的位置对换。(4)两个规划模型中的变量皆非负。两个规划模型中的变量皆非负。本讲稿第二十六页，共一百三十三页补充例子补充例子原问题：原问题：本讲稿第二十七页，共一百三十三页对偶问题：对偶问题：本讲稿第二十八页，共一百三十三页Chapter 2 灵敏度分析灵敏度分析2.线性规划问题是非对称形式线性规划问题是非对称形式 对于非对称形式的规划，可以按照下面的对应关对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划。系直接给出其对偶规划。（1）将模型统一为）

13、将模型统一为“max，”或或“min，”的形的形式，对于其中的等式约束按下面（式，对于其中的等式约束按下面（2）、（）、（3）中的方法处理；中的方法处理；本讲稿第二十九页，共一百三十三页（2）若原规划的某个约束条件为等式约束，则）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没在对偶规划中与此约束对应的那个变量取值没有非负限制；有非负限制；（3）若原规划的某个变量的值没有非负限制，）若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为则在对偶问题中与此变量对应的那个约束为等式。等式。综上所述，线性规划的原问题和对偶问题的关系，综上所述，线性规划

14、的原问题和对偶问题的关系，其变换形式归纳为表其变换形式归纳为表2.5本讲稿第三十页，共一百三十三页原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数 max目标函数目标函数 min约约束束条条件件m个个m个个变变量量0 00 0=无约束无约束变变量量n个个n个个约约束束条条件件0 00 0无约束无约束=约束条件右端项约束条件右端项目标函数变量的系数目标函数变量的系数目标函数变量的系数目标函数变量的系数约束条件右端项约束条件右端项本讲稿第三十一页，共一百三十三页下面我们以一个例子说明上述关系写出下述线性规划问题的对偶问题本讲稿第三十二页，共一百三十三

15、页为了写出对偶问题，思路是先将其转化为对称形式，为此（1）约束条件（1a）两端同乘以-1；（2）约束条件（3a）变换为 和 （3）令 （4）本讲稿第三十三页，共一百三十三页则线性规划变换成如下的对称形式本讲稿第三十四页，共一百三十三页令对应上述4个约束的对偶变量分别为 写出对偶问题本讲稿第三十五页，共一百三十三页再令 将（3b）和（4b）合并，（2b）两端同乘以-1，于是有本讲稿第三十六页，共一百三十三页例例2.6 写出下述线性规划问题的对偶问题写出下述线性规划问题的对偶问题本讲稿第三十七页，共一百三十三页本讲稿第三十八页，共一百三十三页补充例题补充例题写出下述线性规划问题的对偶问题本讲稿第三

16、十九页，共一百三十三页解：对偶问题为解：对偶问题为本讲稿第四十页，共一百三十三页 小练习写出下列问题的对偶问题写出下列问题的对偶问题本讲稿第四十一页，共一百三十三页作业：2.1（1）（2）（3）本讲稿第四十二页，共一百三十三页2.4 对偶问题的基本性质对偶问题的基本性质【性质1】对称性对称性 对偶问题的对偶是原问题。对偶问题的对偶是原问题。(P)(D)(P)(D)Max Max Z Z=CX Min f=Yb=CX Min f=Yb s.t.AX b s.t.YA C s.t.AX b s.t.YA C X 0 Y 0 X 0 Y 0 “Max-”“Min-”“Max-”“Min-”本讲稿第四

17、十三页，共一百三十三页【证】因为 X*、Y*是可行解，故有AX*b,X*0及Y*AC，Y*0,将不等式 AX*b两边左乘Y*，得Y*AX*Y*b再将不等式Y*AC两边右乘X*，得C X*Y*AX*故 C X*Y*AX*Y*b这一性质说明了两个线性规划互为对偶时，求最大值的线性规划的任意目标值都不会大于求最小值的线性规划的任一目标值，不能理解为原问题的目标值不超过对偶问题的目标值。【性质2】弱对偶性 设X*、Y*分别为LP(max)与 DP(min)的可行解，则 本讲稿第四十四页，共一百三十三页由这个性质可得到下面几个结论：(1)（LP）的任一可行解的目标值是（DP）的最优值下界；（DP）的任一

18、可行解的目标是（LP）的最优值的上界；(2)在互为对偶的两个问题中，若一个问题可行且具有无界解，则另一个问题无可行解；(3)若原问题可行且另一个问题不可行，则原问题具有无界解。本讲稿第四十五页，共一百三十三页【性质3】最优准则定理 设X*与Y*分别是（LP）与（DP）的可行解，则当X*、Y*是（LP）与（DP）的最优解当且仅当 C X*=Y*b.【证】若X*、Y*为最优解，B为（LP）的最优基，则有Y*=CBB1，并且当C X*=Y*b时，由性质1，对任意可行解 有即Y*b是（DP）中任一可行解的目标值的下界，C X*是（LP）中任一可行解的目标值的上界，从而X*、Y*是最优解。本讲稿第四十六

19、页，共一百三十三页【性质4】线性规划的对偶原理线性规划的对偶原理（1 1）若原问题有最优解，那么对偶问题也有）若原问题有最优解，那么对偶问题也有最优解，而且二者最优值相等。（最优解，而且二者最优值相等。（强对偶性）强对偶性）（2）若原问题（对偶问题）的解为无界解，则若原问题（对偶问题）的解为无界解，则其对偶问题（原问题）无可行解。（其对偶问题（原问题）无可行解。（无界性）无界性）注：这个问题的性质不存在逆注：这个问题的性质不存在逆。(看后面例子看后面例子)本讲稿第四十七页，共一百三十三页【证】（1）设（LP）有最优解 X0,那么对于最优基B必有C-CBB-1A0与CBB-10，即有YAC与Y0

20、，这里Y=CBB-1，从而Y是可行解，对目标函数有由性质 3知 Y是最优解。（2）由弱对偶性，显然得注：这个问题的性质不存在逆本讲稿第四十八页，共一百三十三页例如下述一对问题两者皆无可行解。原问题（对偶问题）对偶问题（原问题）min w=-x1-x2 max z=y1+y2 x1 x 2 1 y1-y2 -1 -x1+x 2 1 -y1+y2 -1 x1,x 2 0 y1,y2 0 由性质 4 还可推出另一结论：若若（LP）与与（DP）都都有有可可行行解解，则则两两者者都都有有最最优优解解，若若一一个个问问题题无无最最优优解解，则另一问题也无最优解。则另一问题也无最优解。本讲稿第四十九页，共一

21、百三十三页【性质5】互补松弛定理 设 X0、Y0 分别为（LP）与（DP）的可行解，XS 和 YS 分别是（LP）与（DP）对应的松弛变量向量，则 X0 和 Y0 是最优解当且仅当YSX0=0 和 Y0XS=0【证】设X和Y是最优解,由性质3，CX0=Y0b，由于XS和YS是松弛变量，则有A X0XSbY0AYS=C将第一式左乘Y0，第二式右乘X0得Y0A X0Y0XSY0bY0A X0YS X0=C X0本讲稿第五十页，共一百三十三页显然有 Y0XS=YS X0又因为Y、Xs、Ys、X0，所以有YXS=0和YS X=0成立。反之，当YXS=0和YS X=0时，有YA XYbYA X=C X显

22、然有Y0b=CX,由性质3知 X 与 Y是（LP）与（DP）的最优解。证毕。本讲稿第五十一页，共一百三十三页性质5 告诉我们已知一个问题的最优解时求另一个问题的最优解的方法，即已知 Y*求 X*或已知 X*求 Y*。Y*XS=0和YS X*=0两式称为互补松弛条件。将互补松弛条件写成下式由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：其中本讲稿第五十二页，共一百三十三页(1)当 yi*0 时，,反之当 时 yi*=0；利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。性质5的结论和证明都是假定（P）与（D）为对称形式，事实上对于非对称形式，性质

23、5的结论仍然有效。注：上述针对对称形式证明的对偶问题的性质，同样适应于非对称形式。本讲稿第五十三页，共一百三十三页【补充例题】已知线性规划的最优解是 求对偶问题的最优解。【解】对偶问题是下面举例说明互补松弛条件的应用本讲稿第五十四页，共一百三十三页解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为Y=（1，1），最优值w=26。因为X10，X20，所以对偶问题的第一、二个约束的松弛变量等于零，即本讲稿第五十五页，共一百三十三页【性质6】假设原问题是：假设原问题是：max z=CX;AX+Xs=b;X=0它的对偶问题是：它的对偶问题是：min f=Yb;YA-Ys=C;Y=0 则原问题单

24、纯形表的检验数行对应其对偶则原问题单纯形表的检验数行对应其对偶 问问题的一个基解。其对应关系见如下表题的一个基解。其对应关系见如下表本讲稿第五十六页，共一百三十三页-0 0 N N-Y-Y-这里 是对应于原问题中基变量XB 剩余变量，是对应于原问题中非基变量XN剩余变量.-本讲稿第五十七页，共一百三十三页一个问题一个问题max另一个问题另一个问题min有最优解有最优解有最优解有最优解性质性质4无无无最优解无最优解无最优解无最优解性质性质4最最优优无界解无界解（有可行解）（有可行解）无可行解无可行解性质性质2解解无可行解无可行解无界解无界解（有可行解）（有可行解）应用应用已知最优解已知最优解通过

25、解方程通过解方程求最优解求最优解性质性质5已知检验数已知检验数检验数乘以检验数乘以1求得基本解求得基本解性质性质6对于这六个对偶性质，这些性质是研究原问题与对偶问题解的对应关系；下表也许对您了解这些性质有帮助。本讲稿第五十八页，共一百三十三页例例2.7：判断下例说法是否正确，为什么？：判断下例说法是否正确，为什么？A 如果线性规划的原问题存在可行解，则其对如果线性规划的原问题存在可行解，则其对偶偶 问题也一定存在可行解问题也一定存在可行解 B 如果线性规划的对偶问题无可行解，则原如果线性规划的对偶问题无可行解，则原问题也一定无可行解。问题也一定无可行解。C 在互为对偶的一对原问题和对偶问题中，

26、不在互为对偶的一对原问题和对偶问题中，不管原问题是求极大或者极小，原问题可行解的管原问题是求极大或者极小，原问题可行解的目标函数值都一定不超过其对偶问题可行解的目标函数值都一定不超过其对偶问题可行解的目标函数值。目标函数值。本讲稿第五十九页，共一百三十三页v解：解：A不对。因为原问题为无界解时（它当然有可行解）不对。因为原问题为无界解时（它当然有可行解），其对偶问题无可行解。，其对偶问题无可行解。B此句为此句为A的逆否命题，所以也不对。的逆否命题，所以也不对。C不对。因为哪个问题是原问题，哪个问题是对偶不对。因为哪个问题是原问题，哪个问题是对偶问题是相对而言的。问题是相对而言的。本讲稿第六十页

27、，共一百三十三页例例2.8 已知线性规划问题已知线性规划问题试用对偶理论证明上述线性规划问题有无界解试用对偶理论证明上述线性规划问题有无界解（即有可行解但无最优解）。（即有可行解但无最优解）。本讲稿第六十一页，共一百三十三页证明：所给问题的对偶问题为证明：所给问题的对偶问题为本讲稿第六十二页，共一百三十三页显然约束条件中显然约束条件中与与 矛盾，即此对偶问题无可行解，因此所给原问矛盾，即此对偶问题无可行解，因此所给原问题无最优解，它只可以是无界解或者无可行题无最优解，它只可以是无界解或者无可行解。然而解。然而X=（0，0，0）显然是它的可行解，）显然是它的可行解，因此它必定有无界解。因此它必定

28、有无界解。本讲稿第六十三页，共一百三十三页 补充例题给出线性规划（1）写出对偶问题（2）用对偶理论证明上述线性规划目标函数值无界本讲稿第六十四页，共一百三十三页解解：（1）对偶问题为本讲稿第六十五页，共一百三十三页上述对偶问题中 ,则与对偶问题的第一个约束条件矛盾，所以对偶问题无可行解，因而原问题无最优解，它只可以是无界解或者无可行解，然而x=(10,4,2)显然是他的可行解，因而它必定有无界解。本讲稿第六十六页，共一百三十三页例例 2.9 已知线性规划问题已知线性规划问题已知其对偶问题的最优解为已知其对偶问题的最优解为试用对偶理论找出原问题的最优解。试用对偶理论找出原问题的最优解。本讲稿第六

29、十七页，共一百三十三页解：解：先写出它的对偶问题本讲稿第六十八页，共一百三十三页v将将 的值代入约束条件，得到的值代入约束条件，得到(2),(3),(4)为严格不等式为严格不等式;由互补松弛性得到由互补松弛性得到 因为因为 ;原问题的两个约束条件的松原问题的两个约束条件的松弛变量由互补松弛性得到为弛变量由互补松弛性得到为 0，因此两个约束，因此两个约束条件应该取等式条件应该取等式,所以有所以有本讲稿第六十九页，共一百三十三页求解后得到求解后得到所以原问题的最优解为所以原问题的最优解为X=(1,0,0,0,1)T本讲稿第七十页，共一百三十三页补充例题补充例题:已知原问题的最优解为已知原问题的最优

30、解为 X X*=（0,0,40,0,4），），Z=12,Z=12,试求对偶试求对偶问题的最优解。问题的最优解。本讲稿第七十一页，共一百三十三页解解:对偶问题为将将X X*=（0,0,40,0,4）代入原问题中，有下式：）代入原问题中，有下式：本讲稿第七十二页，共一百三十三页Chapter 2 灵敏度分析灵敏度分析所以，根据互补松弛条件，必有所以，根据互补松弛条件，必有y y*1 1=y=y*2 2=0=0，代入对，代入对偶问题约束偶问题约束 （3 3）式，）式，y y3 3=3=3。因此，对偶问题的。因此，对偶问题的最优解为最优解为 Y Y*=（0,0,30,0,3），），W=12W=12。本

31、讲稿第七十三页，共一百三十三页因为原问题和对偶问题的最优值相等，将线性规划的目标函数表达成资源的函数，故有即 yi 是第 i 种资源的变化率，称 yi 是第 i 种资源的边际价格，说明当其它资源供应量bk(ki)不变时，bi 增加一个单位时目标值 Z 增加 yi个单位2.5 2.5 影子价格影子价格本讲稿第七十四页，共一百三十三页 影子价格(Shadow price):原始线性规划问题考虑的是充分利用现有资源，以产品的数量和单位产品的收益来决定企业的总收益，没有考虑到资源的价格，但实际在构成产品的收益中，不同的资源对收益的贡献也不同，它是企业生产过程中一种隐含的潜在价值，经济学中称为影子价格，

32、即对偶问题中的决策变量 yi 的值。对偶变量 yi 就是第 i 个约束的影子价格（边际价格）本讲稿第七十五页，共一百三十三页Chapter 2 灵敏度分析灵敏度分析影子价格 是一个向量，它的分量表示最优目标值随相应资源数量变化的变化率。若x*,y*分别为（LP）和（DP）的最优解，那么，cT x*=bT y*。根据 f=bTy*=b1y1*+b2y2*+bmym*可知 f/bi=yi*yi*表示 bi 变化1个单位对目标 f 产生的影响，称 yi*为 bi 的影子价格。注意注意：若 B 是最优基，y*=CBB-1 为影子价格向量。本讲稿第七十六页，共一百三十三页Chapter 2 灵敏度分析灵

33、敏度分析影子价格的经济含义 (1)影影子子价价格格是是对对现现有有资资源源实实现现最最大大效效益益时时的的一种估价一种估价 企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。本讲稿第七十七页，共一百三十三页Chapter 2 灵敏度分析灵敏度分析（2）影影子子价价格格表表明明资资源源增增加加对对总总效效益益产产生生的的影影响响。根据推推论论“设x0和y0分别为原规划（P）和对偶规划（D）的可

34、行解，当cx0=bTy0时，x0、y0分别是两个问题的最优解”可知，在最优解的情况下，有关系 因此，可以将z*看作是bi,i=1,2，,m的函数，对bi求偏导数可得到 这说明，如果右端常数增加一个单位，则目标函数值的增量将是本讲稿第七十八页，共一百三十三页Chapter 2 灵敏度分析灵敏度分析（3）根据对偶问题的互补松弛性质中 时；当 时，这表明生产过程中如果某种资源 未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。本讲稿第七十九页，共一百三十三页（4）影子价格是企业生产过程中资源的一种隐含的潜在价值，表明单位资源的贡献，与市场价格是不同

35、的两个概念同一种资源在不同的企业、生产不同的产品或在不同时期影子价格都不一样 例如，某种钢板市场价格是每吨8000元，一个企业用来生产汽车，另一个企业用来生产空调外壳，每吨钢板的产值是不一样的（5）影子价格是一个变量由 的含义知影子价格是一种边际产出，与 bi 的基数有关，在最优基B不变的条件下 yi不变，当某种资源增加或减少后，最优基 B 可能发生了变化，这时 yi 的值也随之发生变化本讲稿第八十页，共一百三十三页根据对偶问题的性质，因为当即有即其对偶问题的解为可行解，由此对偶问题和原问题均为最优解。反之，如果存在一个对偶问题的可行基B，即对这时只要有即原问题的解也为可行解，即两者均为最优解

36、。否则，保持对偶可行性，进行迭代2.6 2.6 对偶单纯形法对偶单纯形法本讲稿第八十一页，共一百三十三页设原问题是（记为LP）：对偶问题是（记为DP）：对偶单纯形法的条件是：初始表中对偶问题可行，即极大化问题 时 ，极小化问题时 。本讲稿第八十二页，共一百三十三页v对偶单纯形法的基本思想是：从原规划的一个对偶单纯形法的基本思想是：从原规划的一个基本解基本解出发，此基本解不一定可行，但它对应着一个出发，此基本解不一定可行，但它对应着一个对对偶可行解偶可行解（检验数非正），所以也可以说是从一个（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可对偶可行解出发；然后检验原

37、规划的基本解是否可行，即行，即是否有负的分量是否有负的分量，如果有小于零的分量，则，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。如果得到的基一个对偶可行解（检验数非正）。如果得到的基本解的分量皆非负则该基本解为最优解。本解的分量皆非负则该基本解为最优解。本讲稿第八十三页，共一百三十三页Chapter 2对偶单纯形法在什么情况下使用对偶单纯形法在什么情况下使用 ：应用前提：应用前提：有一个基，其对应的基有一个基，其对应的基满足满足:单纯形表的检验数行全部非正（对偶可行）单纯形表的检验数行全部非正（对偶可行

38、）；变量取值可有负数（非可行解）。变量取值可有负数（非可行解）。注：注：通过矩阵行变换运算，使所有相应变通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。量取值均为非负数即得到最优单纯形表。本讲稿第八十四页，共一百三十三页v这样的优点在于这样的优点在于，v一是当问题的模型中存在一是当问题的模型中存在“=”的约束条件时，的约束条件时，不需要引入人工变量，只要在约束条件方程不需要引入人工变量，只要在约束条件方程的两边乘以的两边乘以“-1”后加入松弛变量，再按单纯形后加入松弛变量，再按单纯形法求解。法求解。v二是当约束条件方程个数二是当约束条件方程个数m大于变量个数大于变量个数n的

39、的时候，将原问题变换成对偶问题求解，计算时候，将原问题变换成对偶问题求解，计算量一般会小些。量一般会小些。本讲稿第八十五页，共一百三十三页Chapter 2对偶单纯形法求解线性规划问题步骤：对偶单纯形法求解线性规划问题步骤：1.1.建立初始对偶单纯形表建立初始对偶单纯形表,对应一个对应一个基本解基本解,所有检验数均非正所有检验数均非正 ,转转2 2；2.2.若若b b0,0,则得到最优解则得到最优解,停止停止;否则否则,若有若有b bi i0,0,3.3.换出变量：设换出变量：设min bmin bi i|b|bi i0=0=b bk k，则选则选k k 行的基变量为换出变量行的基变量为换出变

40、量.本讲稿第八十六页，共一百三十三页 4.4.若所有若所有a akjkj0(0(j j=1,2,=1,2,n n)，则原，则原问题无可行解问题无可行解,停止停止;否则否则,若有若有 a akjkj0 0 则选则选 =min=min j j/a akjkja akjkj00=r r/a akrkr 那么那么 x xr r 为换入变量为换入变量,转转5 5；5.5.以以a akrkr为主元为主元,作矩阵行变换使其变为作矩阵行变换使其变为1,1,该列其他元变为该列其他元变为0 0（旋转变换旋转变换）,转转2 2。本讲稿第八十七页，共一百三十三页v例例2.10 求线性规划求线性规划 本讲稿第八十八页，

41、共一百三十三页解：引入松弛变量 将上述问题转化为得对偶单纯形表2.7本讲稿第八十九页，共一百三十三页表2.7此时基本解为X=(0,0,0,0,-2,-3),不可行，转第二步。因为min-2,-3=-3,所以x6为换出变量，又因为Min-2/-2,-5/-1=1,所以x1为换入变量。得到新的单纯形表2.8本讲稿第九十页，共一百三十三页表2.8此时基本解为X=(3/2,0,0,0,-1/2,0),不可行，转第二步。因为-1/20,所以x5为换出变量，又因为Min-4/(-5/2),-4/(-5/2),-9/(-5/2),-1/(-1/2)=8/5,所以 x2 和 x3 都可以作为换入变量。任选其中

42、一个 x2，做线性变换得到新的单纯形表2.9本讲稿第九十一页，共一百三十三页表2.9得到一个基本解为X=(8/5,1/5,0,0,0,0)T,因解是可行的，所以满足最优检验下的基本可行解因而也是最优解。本讲稿第九十二页，共一百三十三页Chapter 2 从以上求解过程中我们可以看到，对偶从以上求解过程中我们可以看到，对偶单纯形法有以下的优点：单纯形法有以下的优点：1)初始解可以是非可行解，当检验数都为负初始解可以是非可行解，当检验数都为负数时，就可以进行基的变换，数时，就可以进行基的变换，这时不需要加入这时不需要加入人工变量人工变量，因此可以简化计算。，因此可以简化计算。2)当变量多于约束条件

43、，对于这样的线性规当变量多于约束条件，对于这样的线性规划问题，用对偶单纯形法计算可以减少计算工划问题，用对偶单纯形法计算可以减少计算工作量，因此对于变量较少，而约束条件很多的作量，因此对于变量较少，而约束条件很多的线性规划问题，可以首先将它变换成为对偶问线性规划问题，可以首先将它变换成为对偶问题，然后用对偶单纯形法来求解。题，然后用对偶单纯形法来求解。本讲稿第九十三页，共一百三十三页3)在灵敏度分析中，有时需要使用对偶单纯形在灵敏度分析中，有时需要使用对偶单纯形法，这样可以使问题处理简化。法，这样可以使问题处理简化。对偶单纯形对偶单纯形法的局限在于法的局限在于：对于大多数的线性规划问题，对于大

44、多数的线性规划问题，很难找到一个初始可行基，因而这个方法在很难找到一个初始可行基，因而这个方法在求解线性规划问题时很少单独应用。求解线性规划问题时很少单独应用。本讲稿第九十四页，共一百三十三页从几何图形上看单纯性和对偶单纯性的区别已知Q2为最优解点x1x2O4v Q2(4,2)Q1Q3Q43ABC单纯形法：O Q1 O2 或 O Q4 O3 O2 对偶单纯性法：A B Q2 或 B Q2 注意：对偶单纯形对迭代点的要求-对偶可行性 本讲稿第九十五页，共一百三十三页（1）用对偶单纯形法求解线性规划是一种求解方法，而不是去求对偶问题的最优解；（2）初始表中一定要满足对偶问题可行，也就是说检验数满足

45、最优判别准则；（3）对偶单纯形法与普通单纯形法的换基顺序不一样，普通单纯形法是先确定进基变量后确定出基变量，对偶单纯形法是先确定出基变量后确定进基变量；（4）对偶单纯形法在确定出基变量时，若不遵循 规则，任选一个小于零的bi对应的基变量出基，不影响计算结果，只是迭代次数可能不一样 应当注意：本讲稿第九十六页，共一百三十三页 系数系数 br、cj 变化，最优解的最优性、可变化，最优解的最优性、可行性是否变化？行性是否变化？系数在什么范围内变化，最优解或最优性系数在什么范围内变化，最优解或最优性不变？不变？如何求新的最优解？如何求新的最优解？本本节节重重点点本讲稿第九十七页，共一百三十三页例2.2

46、本讲稿第九十八页，共一百三十三页1.求解此线性规划的解2.当C2=2时，新的线性规划问题的解3.当C2=5时，新的线性规划问题的解4.当 b1=9时，新的线性规划问题的解5.当 b1=12时，新的线性规划问题的解本讲稿第九十九页，共一百三十三页灵敏度分(Sensitivity Analyisi),就是分析研究LP 模型参数 aij,br,cj 的取值变化对最优解和最优基的影响。它在应用线性规划解决实际问题的过程中是非常有用的。实际LP问题的最优解，是在模型参数区某一组定值的基础上获得的，而这些定值往往是一些预测和估计的数字，因此或者有一定的误差，或者可能变动。如市市场条件出现了变动，场条件出现

47、了变动，cj 的值就会发生变化；的值就会发生变化；aij是随着是随着工艺技术条件的改变而改变的，而工艺技术条件的改变而改变的，而 br 值则是根据资源投值则是根据资源投入后能产出多大经济效果来决定的一种决策选择。入后能产出多大经济效果来决定的一种决策选择。本讲稿第一百页，共一百三十三页v因此就会产生以下问题：当这些参数中的一个或因此就会产生以下问题：当这些参数中的一个或几个发生了变化时，问题的最优解会有什么变化，几个发生了变化时，问题的最优解会有什么变化，或者这些参数在一个多大的范围内变化时，问题或者这些参数在一个多大的范围内变化时，问题的最优解不变。这就是我们学习灵敏度分析所要的最优解不变。

48、这就是我们学习灵敏度分析所要研究解决的问题。研究解决的问题。v当然通过上面的学习我们知道：当线性规划问题当然通过上面的学习我们知道：当线性规划问题中的一个或者几个参数变化时，可以用单纯形法中的一个或者几个参数变化时，可以用单纯形法从头计算，看最优解有无变化，但是这样做既麻从头计算，看最优解有无变化，但是这样做既麻烦又没有必要。烦又没有必要。本讲稿第一百零一页，共一百三十三页v因为我们知道单纯形法的迭代运算是从一组基向因为我们知道单纯形法的迭代运算是从一组基向量变换为另一组基向量，表中每步迭代得到的数量变换为另一组基向量，表中每步迭代得到的数字只随基向量的不同选择而改变，字只随基向量的不同选择而

49、改变，v因此有可能把个别参数的变化直接在计算得到最因此有可能把个别参数的变化直接在计算得到最优解的单纯形表上面反映出来，这样就不需要从优解的单纯形表上面反映出来，这样就不需要从头计算了，而直接对计算得到的最优解的单纯形头计算了，而直接对计算得到的最优解的单纯形表进行审查，看一些数字变化后，是否满足最优表进行审查，看一些数字变化后，是否满足最优解的条件，如果不满足的话，再从这个表开始进解的条件，如果不满足的话，再从这个表开始进行迭代计算，求出最优解。行迭代计算，求出最优解。本讲稿第一百零二页，共一百三十三页Chapter 2 灵敏度分析灵敏度分析灵敏度分析的步骤可以归纳如下：灵敏度分析的步骤可以

50、归纳如下：1)将参数的改变计算反映到最终单纯形表上来将参数的改变计算反映到最终单纯形表上来;具体的计算方法是，按照相关公式计算出由参数具体的计算方法是，按照相关公式计算出由参数的变化而引起的最终单纯形表上有关数字的变化；的变化而引起的最终单纯形表上有关数字的变化；2)检查原问题是否仍为可行解检查原问题是否仍为可行解;3)检查对偶问题是否仍为可行解检查对偶问题是否仍为可行解;4)我们可以按照书中表中罗列的几种情况得出结我们可以按照书中表中罗列的几种情况得出结论和决定继续计算的步骤论和决定继续计算的步骤 本讲稿第一百零三页，共一百三十三页本讲稿第一百零四页，共一百三十三页本讲稿第一百零五页，共一百