第二章对偶理论与灵敏度分析PPT讲稿.ppt

第二章第二章对对偶理偶理论论与灵敏度分析与灵敏度分析课课件件第1页，共133页，编辑于2022年，星期二本章重点本章重点1、掌握写出对偶问题的方法，原问题与其对偶问题的对应关系2、掌握对偶问题的基本理论和性质 3、理解影子价格的定义和意义4、理解并掌握对偶单纯形方法的思想和步骤5、掌握线性规划灵敏度分析 (1)资源数量 bi 发生变化的分析 (2)目标函数中价值系数 cj 发生变化的分析难点难点难点难点第2页，共133页，编辑于2022年，星期二XBXNXSbXBBNIbCCBCN00了解-单纯形的矩阵描述XS为松弛变量第3页，共133页，编辑于2022年，星期二XBXNXSbXBIB1N B1B1b N N0CNCBB1NCBB1CBB1b单纯性法计算时，总选取单位矩阵 I 为初始基，对应基变量为XS,设迭代若干步后，基变量变为XB,XB 在初始单纯性表中的系数矩阵为 B。则该步的单纯性表中由 XB 系数组成的矩阵为单位矩阵 I ，对应XS 的系数矩阵在新表中应为B-1 Y=CBB-1 称为单纯性乘子（称为单纯性乘子（对偶变量对偶变量）第4页，共133页，编辑于2022年，星期二2.3 对偶问题提出对偶问题提出 例例2.2：某公司在计划期内要安排生产：某公司在计划期内要安排生产I、II两种产两种产品，已知生产单位产品所需的设备台时及品，已知生产单位产品所需的设备台时及A B两种两种原材料的消耗如表所示，该工厂每生产一件产品原材料的消耗如表所示，该工厂每生产一件产品I可获利可获利2元，每生产一件产品元，每生产一件产品II可获利可获利3元，问应该元，问应该如何安排计划使该工厂获利最多？如何安排计划使该工厂获利最多？举例2第5页，共133页，编辑于2022年，星期二Chapter 2 灵敏度分析灵敏度分析 v先根据图表来列出模型先根据图表来列出模型 Max Z=2X1+3X2 X1+2X2 8 4X1 16 4X2 12 X1,X2 0 举例第6页，共133页，编辑于2022年，星期二v设用设用y1,y2,y3分别表示出租单位设备台时的租分别表示出租单位设备台时的租金和出让单位原材料金和出让单位原材料A,B的附加额的附加额.现现在在从从另另一一个个角角度度来来考考虑虑企企业业的的决决策策问问题题。假假如如企企业业自自己己不不生生产产产产品品，而而将将现现有有的的资资源源转转让让或或出出租租给给其其它它企企业业，那那么么资资源源的的转转让让价价格格是是多多少少才才合合理理？合合理理的的价价格格应应是是对对方方用用最最少少的的资资金金购购买买本本企企业业的的全全部部资资源源，而而本本企企业业所所获获得得的的利利润润不不应应低低于于自自己己用用于于生生产产时时所所获获得得的的利利润润。这这一一决决策策问问题题可可用用下下列列线线性性规规划划数数学学模模型型来来表表示。示。第7页，共133页，编辑于2022年，星期二 他在做定价决策时他在做定价决策时,作如下比较作如下比较:若用一个单位设若用一个单位设备台时和备台时和 4 个单位原材料个单位原材料 A 可以生产一件产品可以生产一件产品 I,可获利可获利 2 元元,那么生产每件产品那么生产每件产品 I 的设备台时和原材料出的设备台时和原材料出租和出让的所有收入应不低于生产一件产品租和出让的所有收入应不低于生产一件产品 I 的利润的利润,这就有这就有 y1+4y22第8页，共133页，编辑于2022年，星期二 同理将生产每件产品同理将生产每件产品 II II 的设备台时和原材料的设备台时和原材料的出租和出让的所有收入应不低于生产一件产品的出租和出让的所有收入应不低于生产一件产品IIII的利润的利润,这就有这就有2y1+4y3 3 把工厂所有设备台时和资源都出租和出让把工厂所有设备台时和资源都出租和出让,其收其收入为入为 f=8y1+16y2+12y3第9页，共133页，编辑于2022年，星期二从工厂决策者的角度来看，从工厂决策者的角度来看，f f当然是越大越好当然是越大越好,但但从接受者眼光来说从接受者眼光来说f f是越少越好是越少越好,所以工厂决策所以工厂决策者只可以在满足者只可以在满足 所有产品的利润条件所有产品的利润条件下下,使其总收入尽可能的小使其总收入尽可能的小.因此因此第10页，共133页，编辑于2022年，星期二v我们称这个线性规划问题为我们称这个线性规划问题为线性规划问题（这称线性规划问题（这称为原问题）的对偶问题为原问题）的对偶问题。各模型中有关数据的。各模型中有关数据的“位置位置”示意图如下。示意图如下。矩阵A矩阵AT第11页，共133页，编辑于2022年，星期二对偶问题提出对偶问题提出v例例2.3 某工厂拥有某工厂拥有A、B、C三种类型的设备，生产甲、三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。求获最三种设备可利用的时数如下表所示。求获最大利润的方案。大利润的方案。第12页，共133页，编辑于2022年，星期二表表2.3第13页，共133页，编辑于2022年，星期二不难得出下面一对对偶问题。不难得出下面一对对偶问题。v原问题原问题 第14页，共133页，编辑于2022年，星期二对偶问题对偶问题 不少于甲产品的利润不少于乙产品的利润第15页，共133页，编辑于2022年，星期二v例例2.4：资源利用问题：资源利用问题v考虑：资源拥有者为了实现一定的收入目标，考虑：资源拥有者为了实现一定的收入目标，将其所拥有的资源出售，给每一种资源如何定价？将其所拥有的资源出售，给每一种资源如何定价？第16页，共133页，编辑于2022年，星期二v解：解：表示出售单位数量的第表示出售单位数量的第i种种资源的价格。资源拥有者在做出售资源的决策时，考资源的价格。资源拥有者在做出售资源的决策时，考虑出售资源的收入不应该低于生产所获得的收入，则虑出售资源的收入不应该低于生产所获得的收入，则有：有：第17页，共133页，编辑于2022年，星期二v如果资源拥有者将所有资源出售，则他得到的总如果资源拥有者将所有资源出售，则他得到的总收入收入 v f=第18页，共133页，编辑于2022年，星期二v资源拥有者出售每一种资源的最低估价，可资源拥有者出售每一种资源的最低估价，可通过求解线性规划问题而得到。通过求解线性规划问题而得到。第19页，共133页，编辑于2022年，星期二v对同一个资源利用问题，从不同的角度考对同一个资源利用问题，从不同的角度考虑，可以得到两个相互联系的线性规划模型，虑，可以得到两个相互联系的线性规划模型，这就是线性规划的对偶问题。这就是线性规划的对偶问题。第20页，共133页，编辑于2022年，星期二由上面的例子我们可以知道原问题与对偶问题的关由上面的例子我们可以知道原问题与对偶问题的关系系1线性规划问题是对称形式线性规划问题是对称形式 Max z=CX Min f=Yb s.t.Ax b s.t.YA c x 0 y 0 “Max-”“Min-”原问题与对偶问题的关系原问题与对偶问题的关系第21页，共133页，编辑于2022年，星期二互为转置互为转置列向量列向量行向量行向量n个变量个变量n个约束个约束第22页，共133页，编辑于2022年，星期二例例2.5 写出下述问题的对偶问题写出下述问题的对偶问题第23页，共133页，编辑于2022年，星期二v解：上述问题的对偶问题为解：上述问题的对偶问题为第24页，共133页，编辑于2022年，星期二(1)若一个模型为目标求若一个模型为目标求“极大极大”，约束为，约束为“小于等小于等于于”的不等式，则它的对偶模型为目标求的不等式，则它的对偶模型为目标求“极小极小”，约束是，约束是“大于等于大于等于”的不等式。即的不等式。即“max，”和和“min，”相对应。相对应。如上面例题所示一对对称形式的对偶规划之间如上面例题所示一对对称形式的对偶规划之间具有下面的对应关系具有下面的对应关系第25页，共133页，编辑于2022年，星期二(2)从约束系数矩阵看：一个模型中为从约束系数矩阵看：一个模型中为，则另，则另一个模型中为一个模型中为AT。一个模型是。一个模型是m个约束，个约束，n个个变量，则它的对偶模型为变量，则它的对偶模型为n个约束，个约束，m个变量。个变量。(3)从数据从数据b、C的位置看：在两个规划模型中，的位置看：在两个规划模型中，b和和C的位置对换。的位置对换。(4)两个规划模型中的变量皆非负。两个规划模型中的变量皆非负。第26页，共133页，编辑于2022年，星期二补充例子补充例子原问题：原问题：第27页，共133页，编辑于2022年，星期二对偶问题：对偶问题：第28页，共133页，编辑于2022年，星期二Chapter 2 灵敏度分析灵敏度分析2.线性规划问题是非对称形式线性规划问题是非对称形式 对于非对称形式的规划，可以按照下面的对应对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划。关系直接给出其对偶规划。（1）将模型统一为）将模型统一为“max，”或或“min，”的形的形式，对于其中的等式约束按下面（式，对于其中的等式约束按下面（2）、（）、（3）中的方法处理；中的方法处理；第29页，共133页，编辑于2022年，星期二（2）若原规划的某个约束条件为等式约束，）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取则在对偶规划中与此约束对应的那个变量取值没有非负限制；值没有非负限制；（3）若原规划的某个变量的值没有非负限制，）若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等则在对偶问题中与此变量对应的那个约束为等式。式。综上所述，线性规划的原问题和对偶问题的关系，综上所述，线性规划的原问题和对偶问题的关系，其变换形式归纳为表其变换形式归纳为表2.5第30页，共133页，编辑于2022年，星期二原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数 max目标函数目标函数 min约约束束条条件件m个个m个个变变量量0 00 0=无约束无约束变变量量n个个n个个约约束束条条件件0 00 0无约束无约束=约束条件右端项约束条件右端项目标函数变量的系数目标函数变量的系数目标函数变量的系数目标函数变量的系数约束条件右端项约束条件右端项第31页，共133页，编辑于2022年，星期二下面我们以一个例子说明上述关系写出下述线性规划问题的对偶问题第32页，共133页，编辑于2022年，星期二为了写出对偶问题，思路是先将其转化为对称形式，为此（1）约束条件（1a）两端同乘以-1；（2）约束条件（3a）变换为 和 （3）令 （4）第33页，共133页，编辑于2022年，星期二则线性规划变换成如下的对称形式第34页，共133页，编辑于2022年，星期二令对应上述4个约束的对偶变量分别为 写出对偶问题第35页，共133页，编辑于2022年，星期二再令 将（3b）和（4b）合并，（2b）两端同乘以-1，于是有第36页，共133页，编辑于2022年，星期二例例2.6 写出下述线性规划问题的对偶问题写出下述线性规划问题的对偶问题第37页，共133页，编辑于2022年，星期二第38页，共133页，编辑于2022年，星期二补充例题补充例题写出下述线性规划问题的对偶问题第39页，共133页，编辑于2022年，星期二解：对偶问题为解：对偶问题为第40页，共133页，编辑于2022年，星期二 小练习写出下列问题的对偶问题写出下列问题的对偶问题第41页，共133页，编辑于2022年，星期二作业：2.1（1）（2）（3）第42页，共133页，编辑于2022年，星期二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-”第43页，共133页，编辑于2022年，星期二【证】因为 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)的可行解，则 第44页，共133页，编辑于2022年，星期二由这个性质可得到下面几个结论：(1)（LP）的任一可行解的目标值是（DP）的最优值下界；（DP）的任一可行解的目标是（LP）的最优值的上界；(2)在互为对偶的两个问题中，若一个问题可行且具有无界解，则另一个问题无可行解；(3)若原问题可行且另一个问题不可行，则原问题具有无界解。第45页，共133页，编辑于2022年，星期二【性质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*是最优解。第46页，共133页，编辑于2022年，星期二【性质4】线性规划的对偶原理线性规划的对偶原理（1 1）若原问题有最优解，那么对偶问题也有最）若原问题有最优解，那么对偶问题也有最优解，而且二者最优值相等。（优解，而且二者最优值相等。（强对偶性）强对偶性）（2）若原问题（对偶问题）的解为无界解，则若原问题（对偶问题）的解为无界解，则其对偶问题（原问题）无可行解。（其对偶问题（原问题）无可行解。（无界性）无界性）注：这个问题的性质不存在逆注：这个问题的性质不存在逆。(看后面例子看后面例子)第47页，共133页，编辑于2022年，星期二【证】（1）设（LP）有最优解 X0,那么对于最优基B必有C-CBB-1A0与CBB-10，即有YAC与Y0，这里Y=CBB-1，从而Y是可行解，对目标函数有由性质 3知 Y是最优解。（2）由弱对偶性，显然得注：这个问题的性质不存在逆第48页，共133页，编辑于2022年，星期二例如下述一对问题两者皆无可行解。原问题（对偶问题）对偶问题（原问题）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）都都有有可可行行解解，则则两两者者都都有有最最优优解解，若若一一个个问问题题无无最最优优解解，则则另一问题也无最优解。另一问题也无最优解。第49页，共133页，编辑于2022年，星期二【性质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第50页，共133页，编辑于2022年，星期二显然有 Y0XS=YS X0又因为Y、Xs、Ys、X0，所以有YXS=0和YS X=0成立。反之，当YXS=0和YS X=0时，有YA XYbYA X=C X显然有Y0b=CX,由性质3知 X 与 Y是（LP）与（DP）的最优解。证毕。第51页，共133页，编辑于2022年，星期二性质5 告诉我们已知一个问题的最优解时求另一个问题的最优解的方法，即已知 Y*求 X*或已知 X*求 Y*。Y*XS=0和YS X*=0两式称为互补松弛条件。将互补松弛条件写成下式由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：其中第52页，共133页，编辑于2022年，星期二(1)当 yi*0 时，,反之当 时 yi*=0；利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。性质5的结论和证明都是假定（P）与（D）为对称形式，事实上对于非对称形式，性质5的结论仍然有效。注：上述针对对称形式证明的对偶问题的性质，同样适应于非对称形式。第53页，共133页，编辑于2022年，星期二【补充例题】已知线性规划的最优解是 求对偶问题的最优解。【解】对偶问题是下面举例说明互补松弛条件的应用第54页，共133页，编辑于2022年，星期二解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为Y=（1，1），最优值w=26。因为X10，X20，所以对偶问题的第一、二个约束的松弛变量等于零，即第55页，共133页，编辑于2022年，星期二【性质6】假设原问题是：假设原问题是：max z=CX;AX+Xs=b;X=0它的对偶问题是：它的对偶问题是：min f=Yb;YA-Ys=C;Y=0 则原问题单纯形表的检验数行对应其对偶则原问题单纯形表的检验数行对应其对偶 问题的一个基解。其对应关系见如下表问题的一个基解。其对应关系见如下表第56页，共133页，编辑于2022年，星期二-0 0 N N-Y-Y-这里 是对应于原问题中基变量XB 剩余变量，是对应于原问题中非基变量XN剩余变量.-第57页，共133页，编辑于2022年，星期二一个问题一个问题max另一个问题另一个问题min有最优解有最优解有最优解有最优解性质性质4无无无最优解无最优解无最优解无最优解性质性质4最最优优无界解无界解（有可行解）（有可行解）无可行解无可行解性质性质2解解无可行解无可行解无界解无界解（有可行解）（有可行解）应用应用已知最优解已知最优解通过解方程通过解方程求最优解求最优解性质性质5已知检验数已知检验数检验数乘以检验数乘以1求得基本解求得基本解性质性质6对于这六个对偶性质，这些性质是研究原问题与对偶问题解的对应关系；下表也许对您了解这些性质有帮助。第58页，共133页，编辑于2022年，星期二例例2.7：判断下例说法是否正确，为什么？：判断下例说法是否正确，为什么？A 如果线性规划的原问题存在可行解，则其对如果线性规划的原问题存在可行解，则其对偶偶 问题也一定存在可行解问题也一定存在可行解 B 如果线性规划的对偶问题无可行解，则原如果线性规划的对偶问题无可行解，则原问题也一定无可行解。问题也一定无可行解。C 在互为对偶的一对原问题和对偶问题中，不在互为对偶的一对原问题和对偶问题中，不管原问题是求极大或者极小，原问题可行解的目管原问题是求极大或者极小，原问题可行解的目标函数值都一定不超过其对偶问题可行解的目标标函数值都一定不超过其对偶问题可行解的目标函数值。函数值。第59页，共133页，编辑于2022年，星期二v解：解：A不对。因为原问题为无界解时（它当然有可行解）不对。因为原问题为无界解时（它当然有可行解），其对偶问题无可行解。，其对偶问题无可行解。B此句为此句为A的逆否命题，所以也不对。的逆否命题，所以也不对。C不对。因为哪个问题是原问题，哪个问题是对偶不对。因为哪个问题是原问题，哪个问题是对偶问题是相对而言的。问题是相对而言的。第60页，共133页，编辑于2022年，星期二例例2.8 已知线性规划问题已知线性规划问题试用对偶理论证明上述线性规划问题有无界解（即试用对偶理论证明上述线性规划问题有无界解（即有可行解但无最优解）。有可行解但无最优解）。第61页，共133页，编辑于2022年，星期二证明：所给问题的对偶问题为证明：所给问题的对偶问题为第62页，共133页，编辑于2022年，星期二显然约束条件中显然约束条件中与与 矛盾，即此对偶问题无可行解，因此所给原问题矛盾，即此对偶问题无可行解，因此所给原问题无最优解，它只可以是无界解或者无可行解。无最优解，它只可以是无界解或者无可行解。然而然而X=（0，0，0）显然是它的可行解，因此）显然是它的可行解，因此它必定有无界解。它必定有无界解。第63页，共133页，编辑于2022年，星期二 补充例题给出线性规划（1）写出对偶问题（2）用对偶理论证明上述线性规划目标函数值无界第64页，共133页，编辑于2022年，星期二解解：（1）对偶问题为第65页，共133页，编辑于2022年，星期二上述对偶问题中 ,则与对偶问题的第一个约束条件矛盾，所以对偶问题无可行解，因而原问题无最优解，它只可以是无界解或者无可行解，然而x=(10,4,2)显然是他的可行解，因而它必定有无界解。第66页，共133页，编辑于2022年，星期二例例 2.9 已知线性规划问题已知线性规划问题已知其对偶问题的最优解为已知其对偶问题的最优解为试用对偶理论找出原问题的最优解。试用对偶理论找出原问题的最优解。第67页，共133页，编辑于2022年，星期二解：解：先写出它的对偶问题第68页，共133页，编辑于2022年，星期二v将将 的值代入约束条件，得到的值代入约束条件，得到(2),(3),(4)为严格不等式为严格不等式;由互补松弛性得到由互补松弛性得到 因为因为 ;原问题的两个约束条件原问题的两个约束条件的松弛变量由互补松弛性得到为的松弛变量由互补松弛性得到为 0，因此两个，因此两个约束条件应该取等式约束条件应该取等式,所以有所以有第69页，共133页，编辑于2022年，星期二求解后得到求解后得到所以原问题的最优解为所以原问题的最优解为X=(1,0,0,0,1)T第70页，共133页，编辑于2022年，星期二补充例题补充例题:已知原问题的最优解为已知原问题的最优解为 X X*=（0,0,40,0,4），），Z=12,Z=12,试求对偶试求对偶问题的最优解。问题的最优解。第71页，共133页，编辑于2022年，星期二解解:对偶问题为将将X X*=（0,0,40,0,4）代入原问题中，有下式：）代入原问题中，有下式：第72页，共133页，编辑于2022年，星期二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。第73页，共133页，编辑于2022年，星期二因为原问题和对偶问题的最优值相等，将线性规划的目标函数表达成资源的函数，故有即 yi 是第 i 种资源的变化率，称 yi 是第 i 种资源的边际价格，说明当其它资源供应量bk(ki)不变时，bi 增加一个单位时目标值 Z 增加 yi个单位2.5 2.5 影子价格影子价格第74页，共133页，编辑于2022年，星期二 影子价格(Shadow price):原始线性规划问题考虑的是充分利用现有资源，以产品的数量和单位产品的收益来决定企业的总收益，没有考虑到资源的价格，但实际在构成产品的收益中，不同的资源对收益的贡献也不同，它是企业生产过程中一种隐含的潜在价值，经济学中称为影子价格，即对偶问题中的决策变量 yi 的值。对偶变量 yi 就是第 i 个约束的影子价格（边际价格）第75页，共133页，编辑于2022年，星期二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 为影子价格向量。第76页，共133页，编辑于2022年，星期二Chapter 2 灵敏度分析灵敏度分析影子价格的经济含义 (1)影影子子价价格格是是对对现现有有资资源源实实现现最最大大效效益益时时的的一种估价一种估价 企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。第77页，共133页，编辑于2022年，星期二Chapter 2 灵敏度分析灵敏度分析（2）影影子子价价格格表表明明资资源源增增加加对对总总效效益益产产生生的的影影响响。根据推推论论“设x0和y0分别为原规划（P）和对偶规划（D）的可行解，当cx0=bTy0时，x0、y0分别是两个问题的最优解”可知，在最优解的情况下，有关系 因此，可以将z*看作是bi,i=1,2，,m的函数，对bi求偏导数可得到 这说明，如果右端常数增加一个单位，则目标函数值的增量将是第78页，共133页，编辑于2022年，星期二Chapter 2 灵敏度分析灵敏度分析（3）根据对偶问题的互补松弛性质中 时；当 时，这表明生产过程中如果某种资源 未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。第79页，共133页，编辑于2022年，星期二（4）影子价格是企业生产过程中资源的一种隐含的潜在价值，表明单位资源的贡献，与市场价格是不同的两个概念同一种资源在不同的企业、生产不同的产品或在不同时期影子价格都不一样 例如，某种钢板市场价格是每吨8000元，一个企业用来生产汽车，另一个企业用来生产空调外壳，每吨钢板的产值是不一样的（5）影子价格是一个变量由 的含义知影子价格是一种边际产出，与 bi 的基数有关，在最优基B不变的条件下 yi不变，当某种资源增加或减少后，最优基 B 可能发生了变化，这时 yi 的值也随之发生变化第80页，共133页，编辑于2022年，星期二根据对偶问题的性质，因为当即有即其对偶问题的解为可行解，由此对偶问题和原问题均为最优解。反之，如果存在一个对偶问题的可行基B，即对这时只要有即原问题的解也为可行解，即两者均为最优解。否则，保持对偶可行性，进行迭代2.6 2.6 对偶单纯形法对偶单纯形法第81页，共133页，编辑于2022年，星期二设原问题是（记为LP）：对偶问题是（记为DP）：对偶单纯形法的条件是：初始表中对偶问题可行，即极大化问题 时 ，极小化问题时 。第82页，共133页，编辑于2022年，星期二v对偶单纯形法的基本思想是：从原规划的一个对偶单纯形法的基本思想是：从原规划的一个基基本解本解出发，此基本解不一定可行，但它对应着一出发，此基本解不一定可行，但它对应着一个个对偶可行解对偶可行解（检验数非正），所以也可以说是从（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是一个对偶可行解出发；然后检验原规划的基本解是否可行，即否可行，即是否有负的分量是否有负的分量，如果有小于零的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。如果得到的基本解的个对偶可行解（检验数非正）。如果得到的基本解的分量皆非负则该基本解为最优解。分量皆非负则该基本解为最优解。第83页，共133页，编辑于2022年，星期二Chapter 2对偶单纯形法在什么情况下使用对偶单纯形法在什么情况下使用 ：应用前提：应用前提：有一个基，其对应的基有一个基，其对应的基满足满足:单纯形表的检验数行全部非正（对偶单纯形表的检验数行全部非正（对偶可行）；可行）；变量取值可有负数（非可行解）。变量取值可有负数（非可行解）。注：注：通过矩阵行变换运算，使所有相应变量通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。取值均为非负数即得到最优单纯形表。第84页，共133页，编辑于2022年，星期二v这样的优点在于这样的优点在于，v一是当问题的模型中存在一是当问题的模型中存在“=”的约束条件时，的约束条件时，不需要引入人工变量，只要在约束条件方程的不需要引入人工变量，只要在约束条件方程的两边乘以两边乘以“-1”后加入松弛变量，再按单纯形法后加入松弛变量，再按单纯形法求解。求解。v二是当约束条件方程个数二是当约束条件方程个数m大于变量个数大于变量个数n的的时候，将原问题变换成对偶问题求解，计算量时候，将原问题变换成对偶问题求解，计算量一般会小些。一般会小些。第85页，共133页，编辑于2022年，星期二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 行的基变量为换出变量行的基变量为换出变量.第86页，共133页，编辑于2022年，星期二 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。第87页，共133页，编辑于2022年，星期二v例例2.10 求线性规划求线性规划 第88页，共133页，编辑于2022年，星期二解：引入松弛变量 将上述问题转化为得对偶单纯形表2.7第89页，共133页，编辑于2022年，星期二表2.7此时基本解为X=(0,0,0,0,-2,-3),不可行，转第二步。因为min-2,-3=-3,所以x6为换出变量，又因为Min-2/-2,-5/-1=1,所以x1为换入变量。得到新的单纯形表2.8第90页，共133页，编辑于2022年，星期二表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 都可以作为换入变量。任选其中一个 x2，做线性变换得到新的单纯形表2.9第91页，共133页，编辑于2022年，星期二表2.9得到一个基本解为X=(8/5,1/5,0,0,0,0)T,因解是可行的，所以满足最优检验下的基本可行解因而也是最优解。第92页，共133页，编辑于2022年，星期二Chapter 2 从以上求解过程中我们可以看到，对偶单纯从以上求解过程中我们可以看到，对偶单纯形法有以下的优点：形法有以下的优点：1)初始解可以是非可行解，当检验数都为负数初始解可以是非可行解，当检验数都为负数时，就可以进行基的变换，时，就可以进行基的变换，这时不需要加入人这时不需要加入人工变量工变量，因此可以简化计算。，因此可以简化计算。2)当变量多于约束条件，对于这样的线性规划问当变量多于约束条件，对于这样的线性规划问题，用对偶单纯形法计算可以减少计算工作量，题，用对偶单纯形法计算可以减少计算工作量，因此对于变量较少，而约束条件很多的线性规划因此对于变量较少，而约束条件很多的线性规划问题，可以首先将它变换成为对偶问题，然后用问题，可以首先将它变换成为对偶问题，然后用对偶单纯形法来求解。对偶单纯形法来求解。第93页，共133页，编辑于2022年，星期二3)在灵敏度分析中，有时需要使用对偶单纯形在灵敏度分析中，有时需要使用对偶单纯形法，这样可以使问题处理简化。法，这样可以使问题处理简化。对偶单纯形对偶单纯形法的局限在于法的局限在于：对于大多数的线性规划问题，对于大多数的线性规划问题，很难找到一个初始可行基，因而这个方法在很难找到一个初始可行基，因而这个方法在求解线性规划问题时很少单独应用。求解线性规划问题时很少单独应用。第94页，共133页，编辑于2022年，星期二从几何图形上看单纯性和对偶单纯性的区别已知Q2为最优解点x1x2O4v Q2(4,2)Q1Q3Q43ABC单纯形法：O Q1 O2 或 O Q4 O3 O2 对偶单纯性法：A B Q2 或 B Q2 注意：对偶单纯形对迭代点的要求-对偶可行性 第95页，共133页，编辑于2022年，星期二（1）用对偶单纯形法求解线性规划是一种求解方法，而不是去求对偶问题的最优解；（2）初始表中一定要满足对偶问题可行，也就是说检验数满足最优判别准则；（3）对偶单纯形法与普通单纯形法的换基顺序不一样，普通单纯形法是先确定进基变量后确定出基变量，对偶单纯形法是先确定出基变量后确定进基变量；（4）对偶单纯形法在确定出基变量时，若不遵循 规则，任选一个小于零的bi对应的基变量出基，不影响计算结果，只是迭代次数可能不一样 应当注意：第96页，共133页，编辑于2022年，星期二 系数系数 br、cj 变化，最优解的最优性、变化，最优解的最优性、可行性是否变化？可行性是否变化？系数在什么范围内变化，最优解或最优性系数在什么范围内变化，最优解或最优性不变？不变？如何求新的最优解？如何求新的最优解？本本节节重重点点第97页，共133页，编辑于2022年，星期二例2.2第98页，共133页，编辑于2022年，星期二1.求解此线性规划的解2.当C2=2时，新的线性规划问题的解3.当C2=5时，新的线性规划问题的解4.当 b1=9时，新的线性规划问题的解5.当 b1=12时，新的线性规划问题的解第99页，共133页，编辑于2022年，星期二灵敏度分(Sensitivity Analyisi),就是分析研究LP 模型参数 aij,br,cj 的取值变化对最优解和最优基的影响。它在应用线性规划解决实际问题的过程中是非常有用的。实际LP问题的最优解，是在模型参数区某一组定值的基础上获得的，而这些定值往往是一些预测和估计的数字，因此或者有一定的误差，或者可能变动。如市场条件出现了变动，市场条件出现了变动，cj 的值就会发生变化；的值就会发生变化；aij是随是随着工艺技术条件的改变而改变的，而着工艺技术条件的改变而改变的，而 br 值则是根据资值则是根据资源投入后能产出多大经济效果来决定的一种决策选择。源投入后能产出多大经济效果来决定的一种决策选择。第100页，共133页，编辑于2022年，星期二v因此就会产生以下问题：当这些参数中的一个或因此就会产生以下问题：当这些参数中的一个或几个发生了变化时，问题的最优解会有什么变化，几个发生了变化时，问题的最优解会有什么变化，或者这些参数在一个多大的范围内变化时，问题或者这些参数在一个多大的范围内变化时，问题的最优解不变。这就是我们学习灵敏度分析所要的最优解不变。这就是我们学习灵敏度分析所要研究解决的问题。研究解决的问题。v当然通过上面的学习我们知道：当线性规划问题当然通过上面的学习我们知道：当线性规划问题中的一个或者几个参数变化时，可以用单纯形法中的一个或者几个参数变化时，可以用单纯形法从头计算，看最优解有无变化，但是这样做既麻从头计算，看最优解有无变化，但是这样做既麻烦又没有必要。烦又没有必要