第二章-对偶理论与灵敏度分析课件.ppt

1、本章重点本章重点1、掌握写出对偶问题的方法，原问题与其对偶问题的对应关系2、掌握对偶问题的基本理论和性质 3、理解影子价格的定义和意义4、理解并掌握对偶单纯形方法的思想和步骤5、掌握线性规划灵敏度分析 (1)资源数量 bi 发生变化的分析 (2)目标函数中价值系数 cj 发生变化的分析难点难点难点难点max0,0BBNNSBNSBNSZC XC XXBXNXIXbXXXXBXNXSbXBBNIbCCBCN00了解-单纯形的矩阵描述XS为松弛变量XBXNXSbXBIB1N B1B1b N N0CNCBB1NCBB1CBB1b单纯性法计算时，总选取单位矩阵 I 为初始基，对应基变量为XS,设迭代若

2、干步后，基变量变为XB,XB 在初始单纯性表中的系数矩阵为 B。则该步的单纯性表中由 XB 系数组成的矩阵为单位矩阵 I ，对应XS 的系数矩阵在新表中应为B-1 1jjBjcC B P Y=CBB-1 称为单纯性乘子（称为单纯性乘子（对偶变量对偶变量）2.3 对偶问题提出对偶问题提出 例例2.2：某公司在计划期内要安排生产：某公司在计划期内要安排生产I、II两种产两种产品，已知生产单位产品所需的设备台时及品，已知生产单位产品所需的设备台时及A B两两种原材料的消耗如表所示，该工厂每生产一件产种原材料的消耗如表所示，该工厂每生产一件产品品I可获利可获利2元，每生产一件产品元，每生产一件产品II

3、可获利可获利3元，问元，问应该如何安排计划使该工厂获利最多？应该如何安排计划使该工厂获利最多？举例2Chapter 2 灵敏度分析灵敏度分析 先根据图表来列出模型先根据图表来列出模型 Max Z=2X1+3X2 X1+2X2 8 4X1 16 4X2 12 X1,X2 0 举例v设用设用y1,y2,y3分别表示出租单位设备台时分别表示出租单位设备台时的租金和出让单位原材料的租金和出让单位原材料A,B的附加额的附加额.现在从另一个角度来考虑企业的决策问题。假如现在从另一个角度来考虑企业的决策问题。假如企业自己不生产产品，而将现有的资源转让或出租企业自己不生产产品，而将现有的资源转让或出租给其它企

4、业，那么资源的转让价格是多少才合理？给其它企业，那么资源的转让价格是多少才合理？合理的价格应是对方用最少的资金购买本企业的全合理的价格应是对方用最少的资金购买本企业的全部资源，而本企业所获得的利润不应低于自己用于部资源，而本企业所获得的利润不应低于自己用于生产时所获得的利润生产时所获得的利润。这一决策问题可用下列线性这一决策问题可用下列线性规划数学模型来表示。规划数学模型来表示。他在做定价决策时他在做定价决策时,作如下比较作如下比较:若用一个单若用一个单位设备台时和位设备台时和 4 个单位原材料个单位原材料 A 可以生产一可以生产一件产品件产品 I,可获利可获利 2 元元,那么生产每件产品那么

5、生产每件产品 I 的设备台时和原材的设备台时和原材料出租和出让的所有收入应不低于生产一件料出租和出让的所有收入应不低于生产一件产品产品 I 的利润的利润,这就有这就有 y1+4y22 同理将生产每件产品同理将生产每件产品 II II 的设备台时和原材的设备台时和原材料的出租和出让的所有收入应不低于生产一料的出租和出让的所有收入应不低于生产一件产品件产品IIII的利润的利润,这就有这就有2y1+4y3 3 把工厂所有设备台时和资源都出租和出让把工厂所有设备台时和资源都出租和出让,其收入为其收入为 f=8y1+16y2+12y3从工厂决策者的角度来看，从工厂决策者的角度来看，f f当然是越大越好当

6、然是越大越好,但从接受者眼光来说但从接受者眼光来说f f是越少越好是越少越好,所以工所以工厂决策者只可以在满足厂决策者只可以在满足 所有产品的利所有产品的利润条件下润条件下,使其总收入尽可能的小使其总收入尽可能的小.因此因此1231213min8161242s.t.2430,1,2,3ifyyyyyyyyiv我们称这个线性规划问题为我们称这个线性规划问题为线性规划问题（这称线性规划问题（这称为原问题）的对偶问题为原问题）的对偶问题。各模型中有关数据的。各模型中有关数据的“位置位置”示意图如下。示意图如下。矩阵A矩阵AT对偶问题提出对偶问题提出v例例2.3 某工厂拥有某工厂拥有A、B、C三种类型

7、的设备，生三种类型的设备，生产甲、乙两种产品。每件产品在生产中需产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表的利润以及三种设备可利用的时数如下表所示。求获最大利润的方案。所示。求获最大利润的方案。表表2.3不难得出下面一对对偶问题。不难得出下面一对对偶问题。原问题原问题 121212212max150025003265240.375,0zxxxxxxs txx x对偶问题对偶问题 12312123min654075321500s.t.2325000,1,2,3ifyyyyyyyyyi不少于甲产品

8、的利润不少于乙产品的利润v例例2.4：资源利用问题：资源利用问题v考虑：资源拥有者为了实现一定的收入目标，考虑：资源拥有者为了实现一定的收入目标，将其所拥有的资源出售，给每一种资源如何定价？将其所拥有的资源出售，给每一种资源如何定价？11max(1,2,).0(1,2,)njjjnijjijjZc xa xb ims txjnv解：解：表示出售单位数量的表示出售单位数量的第第i种资源的价格。资源拥有者在做出售资源的决种资源的价格。资源拥有者在做出售资源的决策时，考虑出售资源的收入不应该低于生产所获策时，考虑出售资源的收入不应该低于生产所获得的收入，则有：得的收入，则有：(1,2,)iy imm

9、iynjcyaimijiij,1,0,1,1v如果资源拥有者将所有资源出售，则他得如果资源拥有者将所有资源出售，则他得到的总收入到的总收入 v f=1miiib yv资源拥有者出售每一种资源的最低估价，资源拥有者出售每一种资源的最低估价，可通过求解线性规划问题而得到。可通过求解线性规划问题而得到。miynjcyatsybfimijiijmiii,1,0,1,.min11v对同一个资源利用问题，从不同的角度考对同一个资源利用问题，从不同的角度考虑，可以得到两个相互联系的线性规划模型，虑，可以得到两个相互联系的线性规划模型，这就是线性规划的对偶问题。这就是线性规划的对偶问题。由上面的例子我们可以知

10、道原问题与对偶问由上面的例子我们可以知道原问题与对偶问题的关系题的关系1线性规划问题是对称形式线性规划问题是对称形式 Max z=CX Min f=Yb s.t.Ax b s.t.YA c x 0 y 0 “Max-”“Min-”原问题与对偶问题的关系原问题与对偶问题的关系（P）0 21121112112211 nmnmnm2m1nnnx,x,xbbxxxaaaaaaxcxcxczMax （D）0 212111211212211 mnmnm2m1nmmmy,y,y)c,c,c(aaaaaa)y,y,y(bybybymin 互为转置互为转置列向量列向量行向量行向量n个变量个变量n个约束个约束例例

11、2.5 写出下述问题的对偶问题写出下述问题的对偶问题12341241223412312342438226s.t.69,0Max Zxxxxxxxxxxxxxxxx xxxv解：上述问题的对偶问题为解：上述问题的对偶问题为1234124123434131234min 86692234.1 1,0fyyyyyyyyyyystyyyyy yyy(1)若一个模型为目标求若一个模型为目标求“极大极大”，约束为，约束为“小于等于小于等于”的不等式，则它的对偶模型的不等式，则它的对偶模型为目标求为目标求“极小极小”，约束是，约束是“大于等于大于等于”的不等式。即的不等式。即“max，”和和“min，”相相对

12、应。对应。如上面例题所示一对对称形式的对偶规划之间如上面例题所示一对对称形式的对偶规划之间具有下面的对应关系具有下面的对应关系(2)从约束系数矩阵看：一个模型中为从约束系数矩阵看：一个模型中为，则，则另一个模型中为另一个模型中为AT。一个模型是。一个模型是m个约束，个约束，n个变量，则它的对偶模型为个变量，则它的对偶模型为n个约束，个约束，m个变量。个变量。(3)从数据从数据b、C的位置看：在两个规划模型中，的位置看：在两个规划模型中，b和和C的位置对换。的位置对换。(4)两个规划模型中的变量皆非负。两个规划模型中的变量皆非负。补充例子补充例子123123123123123max2342352

13、3 7 3 46 5,0Zxxxxxxxxxxxxx x x 原问题：原问题：对偶问题：对偶问题：123123123123123 min235232343 s.t.5764,0Wyyyyyyyyyyyyy yy Chapter 2 灵敏度分析灵敏度分析2.线性规划问题是非对称形式线性规划问题是非对称形式 对于非对称形式的规划，可以按照下面的对对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划。应关系直接给出其对偶规划。（1）将模型统一为）将模型统一为“max，”或或“min，”的形式，对于其中的等式约束按下面（的形式，对于其中的等式约束按下面（2）、）、（3）中的方法处理；）中的方

14、法处理；（2）若原规划的某个约束条件为等式约束，）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量则在对偶规划中与此约束对应的那个变量取值没有非负限制；取值没有非负限制；（3）若原规划的某个变量的值没有非负限制，）若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束则在对偶问题中与此变量对应的那个约束为等式。为等式。综上所述，线性规划的原问题和对偶问题的综上所述，线性规划的原问题和对偶问题的关系，其变换形式归纳为表关系，其变换形式归纳为表2.5原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数 max目标函

15、数目标函数 min约约束束条条件件m个个m个个变变量量0 00 0=无约束无约束变变量量n个个n个个约约束束条条件件0 00 0无约束无约束=约束条件右端项约束条件右端项目标函数变量的系数目标函数变量的系数目标函数变量的系数目标函数变量的系数约束条件右端项约束条件右端项下面我们以一个例子说明上述关系123123123123123max432352 (1a)361 (2a)s.t.4 (3a)0,0,Zxxxxxxxxxxxxxxx无约束写出下述线性规划问题的对偶问题为了写出对偶问题，思路是先将其转化为对称形式，为此（1）约束条件（1a）两端同乘以-1；（2）约束条件（3a）变换为 和 （3）令

16、 （4）1234xxx1234xxx 222,0 xxx 所以 33333 ,00 xxxxx令其中，则线性规划变换成如下的对称形式123312331233123312331233max43323552 3661 s.t.4 4,0Zxxxxxxxxxxxxxxxxxxxxxxxx ,令对应上述4个约束的对偶变量分别为 写出对偶问题1233,yyyy123312331233123312331233min244231 (1b)34 (2b)s.t.563 (3b)563 (4b),0 wyyyyyyyyyyyyyyyyyyyyyyyy ,再令 将（3b）和（4b）合并，（2b）两端同乘以-1，于

17、是有22333,yyyyy123123123123123min24231345630,0,wyyyyyyyyyyyyyyy无约束例例2.6 写出下述线性规划问题的对偶问题写出下述线性规划问题的对偶问题123412341342341234min2353512242s.t.630;,0;Zxxxxxxxxxxxxxxxx xx（）（）（）无约束1231213123123123max 546223s.t.32510;0;yyyyyyyyyyyyyyyy 无约束 0,5643732532432max321321321321321xxxxxxxxxxxxxxxZ 补充例题补充例题写出下述线性规划问题的对

18、偶问题123123123123123min235 23 2 3 43s.t.5764,Wyyyyyyyyyyyyy yy 无约束解：对偶问题为解：对偶问题为 小练习写出下列问题的对偶问题写出下列问题的对偶问题作业：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-

19、”【证】因为 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)的可行解，则*CXY b由这个性质可得到下面几个结论：(1)（LP）的任一可行解的目标值是（DP）的最优值下界；（DP）的任一可行解的目标是（LP）的最优值的上界；(2

20、)在互为对偶的两个问题中，若一个问题可行且具有无界解，则另一个问题无可行解；(3)若原问题可行且另一个问题不可行，则原问题具有无界解。【性质3】最优准则定理 设X*与Y*分别是（LP）与（DP）的可行解，则当X*、Y*是（LP）与（DP）的最优解当且仅当 C X*=Y*b.【证】若X*、Y*为最优解，B为（LP）的最优基，则有Y*=CBB1，并且1*BCXC B bYb当C X*=Y*b时，由性质1，对任意可行解 有*CXY bCXYb即Y*b是（DP）中任一可行解的目标值的下界，C X*是（LP）中任一可行解的目标值的上界，从而X*、Y*是最优解。YX及【性质4】线性规划的对偶原理线性规划的

21、对偶原理（1 1）若原问题有最优解，那么对偶问题也有）若原问题有最优解，那么对偶问题也有最优解，而且二者最优值相等。（最优解，而且二者最优值相等。（强对偶强对偶性）性）（2）若原问题（对偶问题）的解为无界解，若原问题（对偶问题）的解为无界解，则其对偶问题（原问题）无可行解。（则其对偶问题（原问题）无可行解。（无无界性）界性）注：这个问题的性质不存在逆注：这个问题的性质不存在逆。(看后面例子看后面例子)【证】（1）设（LP）有最优解 X0,那么对于最优基B必有C-CBB-1A0与CBB-10，即有YAC与Y0，这里Y=CBB-1，从而Y是可行解，对目标函数有bYbBCXCCXBBB010由性质

22、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）都有可行解，则两者都有最优解，若一个问题无最都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。优解，则另一问题也无最优解。【性质5】互补松弛定理 设 X0、Y0 分别为（LP）与（DP）的可行解，XS 和 YS 分别是（L

23、P）与（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显然有Y0b=CX,由性质3知 X 与 Y是（LP）与（DP）的最优解。证毕。性质5 告诉我们已知一个问题的最优解时求另一个问题的最优解的方法

24、，即已知 Y*求 X*或已知 X*求 Y*。Y*XS=0和YS X*=0两式称为互补松弛条件。将互补松弛条件写成下式*1*10 0ijmiSinSjjy xy x由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：*TssYA YCXbAX其中(1)当 yi*0 时，,反之当 时 yi*=0；0iSx0iSx*(2)00,00jjSjjSyxxy时反之当时利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。性质5的结论和证明都是假定（P）与（D）为对称形式，事实上对于非对称形式，性质5的结论仍然有效。注：上述针对对称形式证明的对偶问题的性质，同样适应

25、于非对称形式。【补充例题】已知线性规划123123123max34210s.t.22160,1,2,3jzxxxxxxxxxxj的最优解是 求对偶问题的最优解。TX)0,2,6(【解】对偶问题是1212121212min101623224s.t.1,0wyyyyyyyyy y下面举例说明互补松弛条件的应用解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为Y=（1，1），最优值w=26。因为X10，X20，所以对偶问题的第一、二个约束的松弛变量等于零，即422322121yyyy【性质6】假设原问题是：假设原问题是：max z=CX;AX+Xs=b;X=0它的对偶问题是：它的对偶问题是：

26、min f=Yb;YA-Ys=C;Y=0 则原问题单纯形表的检验数行对应其对偶则原问题单纯形表的检验数行对应其对偶 问题的一个基解。其对应关系见如下表问题的一个基解。其对应关系见如下表BXNXSXNCBC1BBC1B1sY2sY-0 0 N N-Y-Y-这里 是对应于原问题中基变量XB 剩余变量，是对应于原问题中非基变量XN剩余变量.-1sY2sY一个问题一个问题max另一个问题另一个问题min有最优解有最优解有最优解有最优解性质性质4无无无最优解无最优解无最优解无最优解性质性质4最最优优无界解无界解（有可行解）（有可行解）无可行解无可行解性质性质2解解无可行解无可行解无界解无界解（有可行解）

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

28、对偶问题中，在互为对偶的一对原问题和对偶问题中，不管原问题是求极大或者极小，原问题可不管原问题是求极大或者极小，原问题可行解的目标函数值都一定不超过其对偶问行解的目标函数值都一定不超过其对偶问题可行解的目标函数值。题可行解的目标函数值。v解：解：A不对。因为原问题为无界解时（它当然有可行不对。因为原问题为无界解时（它当然有可行解），其对偶问题无可行解。解），其对偶问题无可行解。B此句为此句为A的逆否命题，所以也不对。的逆否命题，所以也不对。C不对。因为哪个问题是原问题，哪个问题是对偶不对。因为哪个问题是原问题，哪个问题是对偶问题是相对而言的。问题是相对而言的。例例2.8 已知线性规划问题已知线

29、性规划问题试用对偶理论证明上述线性规划问题有无界试用对偶理论证明上述线性规划问题有无界解（即有可行解但无最优解）。解（即有可行解但无最优解）。12123123123max32.21,0Zxxxxxstxxxx x x证明：所给问题的对偶问题为证明：所给问题的对偶问题为1212121212min2211s.t.300,0Wyyyyyyyyyy显然约束条件中显然约束条件中与与 矛盾，即此对偶问题无可行解，因此所给原矛盾，即此对偶问题无可行解，因此所给原问题无最优解，它只可以是无界解或者无可问题无最优解，它只可以是无界解或者无可行解。然而行解。然而X=（0，0，0）显然是它的可行）显然是它的可行解，

30、因此它必定有无界解。解，因此它必定有无界解。0,021yy1221yy12313123m ax 4.30,1,2,3iZxxxxxs txxxxi 补充例题给出线性规划（1）写出对偶问题（2）用对偶理论证明上述线性规划目标函数值无界解解：（1）对偶问题为1212212m in4311.10,1,2iwyyyyys tyyyi 上述对偶问题中 ,10y 20y 则120yy与对偶问题的第一个约束条件矛盾，所以对偶问题无可行解，因而原问题无最优解，它只可以是无界解或者无可行解，然而x=(10,4,2)显然是他的可行解，因而它必定有无界解。例例 2.9 已知线性规划问题已知线性规划问题已知其对偶问题

31、的最优解为已知其对偶问题的最优解为试用对偶理论找出原问题的最优解。试用对偶理论找出原问题的最优解。123451234512345min23523234s.t.2330,1,2,5jfxxxxxxxxxxxxxxxxj5,5/3,5/4*2*1zyy解：解：先写出它的对偶问题12121212121212max4322(1)3(2)235(3)s.t.2(4)33(5),0Zyyyyyyyyyyyyyyv将将 的值代入约束条件，得到的值代入约束条件，得到(2),(3),(4)为严格不等式为严格不等式;由互补松弛性得到由互补松弛性得到 因为因为 ;原问题的两个约束条件原问题的两个约束条件的松弛变量由

32、互补松弛性得到为的松弛变量由互补松弛性得到为 0，因此两，因此两个约束条件应该取等式个约束条件应该取等式,所以有所以有*2*1,yy0*4*3*2xxx0,*2*1yy求解后得到求解后得到所以原问题的最优解为所以原问题的最优解为X=(1,0,0,0,1)T3243*5*1*5*1xxxx1,1*5*1xx 无无约约束束321321321321321,0,04 16 3253234maxxxxxxxxxxxxxxxxZ补充例题补充例题:已知原问题的最优解为已知原问题的最优解为 X X*=（0,0,40,0,4），），Z=12,Z=12,试求试求对偶问题的最优解。对偶问题的最优解。12312312

33、3123123min24 231 (1)3 4 (2)563 (3)0,0,Wyyyyyyyyyyyyyyy无约束解解:对偶问题为将将X X*=（0,0,40,0,4）代入原问题中，有下式：）代入原问题中，有下式：Chapter 2 灵敏度分析灵敏度分析 4 4 1 246 32 20532321321321xxxxxxxxx所以，根据互补松弛条件，必有所以，根据互补松弛条件，必有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=1

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

35、称为影子价格，即对偶问题中的决策变量 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 灵敏度分析灵敏度分析影子价格的经济含义 (1)影子价格是对现有

36、资源实现最大效益时的影子价格是对现有资源实现最大效益时的一种估价一种估价 企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。Chapter 2 灵敏度分析灵敏度分析（2）影子价格表明资源增加对总效益产生的影子价格表明资源增加对总效益产生的影响影响。根据推论推论“设x0和y0分别为原规划（P）和对偶规划（D）的可行解，当cx0=bTy0时，x0、y0分别是两个问题的最优解”可知，在最优解的情况

37、下，有关系 因此，可以将z*看作是bi,i=1,2，,m的函数，对bi求偏导数可得到 这说明，如果右端常数增加一个单位，则目标函数值的增量将是*22*11*mmybybybfZmiybZii,2,1,*miyi,2,1,*Chapter 2 灵敏度分析灵敏度分析（3）根据对偶问题的互补松弛性质中 时；当 时，这表明生产过程中如果某种资源 未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。1nijjija xb0iy 0iy 1nijjija xbib（4）影子价格是企业生产过程中资源的一种隐含的潜在价值，表明单位资源的贡献，与市场价格是不同的

38、两个概念同一种资源在不同的企业、生产不同的产品或在不同时期影子价格都不一样 例如，某种钢板市场价格是每吨8000元，一个企业用来生产汽车，另一个企业用来生产空调外壳，每吨钢板的产值是不一样的（5）影子价格是一个变量由 的含义知影子价格是一种边际产出，与 bi 的基数有关，在最优基B不变的条件下 yi不变，当某种资源增加或减少后，最优基 B 可能发生了变化，这时 yi 的值也随之发生变化iibZy根据对偶问题的性质，因为1,jjjBjczcC B P当0,(1,2,)jjczjn即有1,1,2,mjjijjjiYPca ycjn 或 即其对偶问题的解为可行解，由此对偶问题和原问题均为最优解。反之

39、，如果存在一个对偶问题的可行基B，即对这时只要有即原问题的解也为可行解，即两者均为最优解。否则，保持对偶可行性，进行迭代1,2,0,jjjncz有10BXB b2.6 2.6 对偶单纯形法对偶单纯形法设原问题是（记为LP）：对偶问题是（记为DP）：0maxXbAXCXZm in0wYbYACY对偶单纯形法的条件是：初始表中对偶问题可行，即极大化问题 时 ，极小化问题时 。0j0jv对偶单纯形法的基本思想是：从原规划的一个对偶单纯形法的基本思想是：从原规划的一个基本解基本解出发，此基本解不一定可行，但它对应出发，此基本解不一定可行，但它对应着一个着一个对偶可行解对偶可行解（检验数非正），所以也可

40、（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即划的基本解是否可行，即是否有负的分量是否有负的分量，如，如果有小于零的分量，则进行迭代，求另一个基果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检本解，此基本解对应着另一个对偶可行解（检验数非正）。如果得到的基本解的分量皆非负验数非正）。如果得到的基本解的分量皆非负则该基本解为最优解。则该基本解为最优解。Chapter 2对偶单纯形法在什么情况下使用对偶单纯形法在什么情况下使用 ：应用前提：应用前提：有一个基，其对应的基有一个基，其对应的

41、基满足满足:单纯形表的检验数行全部非正（对单纯形表的检验数行全部非正（对偶可行）；偶可行）；变量取值可有负数（非可行解）。变量取值可有负数（非可行解）。注：注：通过矩阵行变换运算，使所有相应通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。变量取值均为非负数即得到最优单纯形表。v这样的优点在于这样的优点在于，v一是当问题的模型中存在一是当问题的模型中存在“=”的约束条的约束条件时，不需要引入人工变量，只要在约束件时，不需要引入人工变量，只要在约束条件方程的两边乘以条件方程的两边乘以“-1”后加入松弛变后加入松弛变量，再按单纯形法求解。量，再按单纯形法求解。v二是当约束条件方程

42、个数二是当约束条件方程个数m大于变量个数大于变量个数n的时候，将原问题变换成对偶问题求解，的时候，将原问题变换成对偶问题求解，计算量一般会小些。计算量一般会小些。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 行的基变量为换

43、出变量行的基变量为换出变量.0j 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 求线性规划求线性规划 1234123412341234min2356232s.

44、t.233,0fxxxxxxxxxxxxx x x x12341234512346max235623 223 30,1,26iZxxxxxxxxxxxxxxxi解：引入松弛变量 将上述问题转化为得对偶单纯形表2.756,xx表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

45、/(-5/2),-1/(-1/2)=8/5,所以 x2 和 x3 都可以作为换入变量。任选其中一个 x2，做线性变换得到新的单纯形表2.9表2.9得到一个基本解为X=(8/5,1/5,0,0,0,0)T,因解是可行的，所以满足最优检验下的基本可行解因而也是最优解。Chapter 2 从以上求解过程中我们可以看到，对从以上求解过程中我们可以看到，对偶单纯形法有以下的优点：偶单纯形法有以下的优点：1)初始解可以是非可行解，当检验数都为初始解可以是非可行解，当检验数都为负数时，就可以进行基的变换，负数时，就可以进行基的变换，这时不需这时不需要加入人工变量要加入人工变量，因此可以简化计算。，因此可以简

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

47、规划问题，很难找到一个初始可行基，因而划问题，很难找到一个初始可行基，因而这个方法在求解线性规划问题时很少单独这个方法在求解线性规划问题时很少单独应用。应用。从几何图形上看单纯性和对偶单纯性的区别已知Q2为最优解点x1x2O4 Q2(4,2)Q1Q3Q43ABC单纯形法：O Q1 O2 或 O Q4 O3 O2 对偶单纯性法：A B Q2 或 B Q2 注意：对偶单纯形对迭代点的要求-对偶可行性 （1）用对偶单纯形法求解线性规划是一种求解方法，而不是去求对偶问题的最优解；（2）初始表中一定要满足对偶问题可行，也就是说检验数满足最优判别准则；（3）对偶单纯形法与普通单纯形法的换基顺序不一样，普通

48、单纯形法是先确定进基变量后确定出基变量，对偶单纯形法是先确定出基变量后确定进基变量；（4）对偶单纯形法在确定出基变量时，若不遵循 规则，任选一个小于零的bi对应的基变量出基，不影响计算结果，只是迭代次数可能不一样 0|miniilbbb应当注意：2.7 灵敏度分析灵敏度分析 系数系数 br、cj 变化，最优解的最优性、变化，最优解的最优性、可行性是否变化？可行性是否变化？系数在什么范围内变化，最优解或系数在什么范围内变化，最优解或最优性不变？最优性不变？如何求新的最优解？如何求新的最优解？本本节节重重点点12121212maxZ23x28 416412,0 xxxxxx x例2.21.求解此线

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

50、改变而改变的，而是随着工艺技术条件的改变而改变的，而 br 值则是根据资源投入后能产出多大经济效果来决值则是根据资源投入后能产出多大经济效果来决定的一种决策选择。定的一种决策选择。v因此就会产生以下问题：当这些参数中的一个或因此就会产生以下问题：当这些参数中的一个或几个发生了变化时，问题的最优解会有什么变化，几个发生了变化时，问题的最优解会有什么变化，或者这些参数在一个多大的范围内变化时，问题或者这些参数在一个多大的范围内变化时，问题的最优解不变。这就是我们学习灵敏度分析所要的最优解不变。这就是我们学习灵敏度分析所要研究解决的问题。研究解决的问题。v当然通过上面的学习我们知道：当线性规划问题当