大学精品课件：Ch2对偶理论.ppt

1、Chapter 2 对偶理论对偶理论Dual Theory2.1 线性规划的对偶模型线性规划的对偶模型 Dual Model of LP2.2 对偶性质对偶性质 Dual property 2.3 对偶单纯形法对偶单纯形法 Dual Simplex Method2.4 灵敏度与参数分析灵敏度与参数分析 Sensitivity and Parametric Analysis运筹学运筹学Operations Research2.1 线性规划的对偶模型线性规划的对偶模型 Dual Model of LPChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Pa

2、ge 3 2023年年3月月1日星期三日星期三 在线性规划问题中，存在一个有趣的问题，即每一个线性规在线性规划问题中，存在一个有趣的问题，即每一个线性规划问题都伴随有另一个线性规划问题，称它为对偶线性规划问划问题都伴随有另一个线性规划问题，称它为对偶线性规划问题。题。【例例21】某企业用四种资源生产三种产品，工艺系数、资源限某企业用四种资源生产三种产品，工艺系数、资源限量及价值系数如下表：量及价值系数如下表：建立总收益最大的数学模型。建立总收益最大的数学模型。产品产品资源资源A B C资源限量资源限量9 8 65005 4 74508 3 23007 6 4550单件产品利润单件产品利润100

3、 80 702.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LPChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 4 2023年年3月月1日星期三日星期三【解解】设设x1，x2，x3分别为产品分别为产品A，B，C的产量，则线性规划数的产量，则线性规划数学模型为：学模型为：0,5504673002384507455006897080100max3,21321321321321321xxxxxxxxxxxxxxxxxxZ 现在从另一个角度来考虑企业的决策问题。假如企业自己不现在从另一个角度来考虑企业的决策问题。假如企业

4、自己不生产产品，而将现有的资源转让或出租给其它企业，那么资源生产产品，而将现有的资源转让或出租给其它企业，那么资源的转让价格是多少才合理？合理的价格应是对方用最少的资金的转让价格是多少才合理？合理的价格应是对方用最少的资金购买本企业的全部资源，而本企业所获得的利润不应低于自己购买本企业的全部资源，而本企业所获得的利润不应低于自己用于生产时所获得的利润。这一决策问题可用下列线性规划数用于生产时所获得的利润。这一决策问题可用下列线性规划数学模型来表示。学模型来表示。2.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LPChapter2 对偶理论对偶理论Dual Theory

5、制作与教学武汉理工大学管理学院 熊伟 Page 5 2023年年3月月1日星期三日星期三设设y1，y2，y3及及y4分别表示四种资源的单位增值价格（售分别表示四种资源的单位增值价格（售价成本增值），总增值最低可用价成本增值），总增值最低可用min w=500y1+450y2+300y3+550y4 表示。企业生产一件产品表示。企业生产一件产品A用了四种资源的数量分别是用了四种资源的数量分别是9，5，8和和7个单位，利润是个单位，利润是100,企业出售这些数量的资源所企业出售这些数量的资源所得的利润不能少于得的利润不能少于100，即，即10078594321yyyy同理，对产品同理，对产品B和和

6、C有有70427680634843214321yyyyyyyy价格不可能小于零，即有价格不可能小于零，即有yi0,i=1,4.从而企业的资源从而企业的资源价格模型为价格模型为2.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LPChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 6 2023年年3月月1日星期三日星期三4,1,07042768063481007859550300450500min4321432143214321iyyyyyyyyyyyyyyyyywi这是一个线性规划数学模型，称这一线性规划模型是前这是一

7、个线性规划数学模型，称这一线性规划模型是前面生产计划模型的对偶线性规划模型面生产计划模型的对偶线性规划模型,这一问题称为对偶这一问题称为对偶问题。生产计划的线性规划问题称为原始线性规划问题问题。生产计划的线性规划问题称为原始线性规划问题或原问题。或原问题。2.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LPChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 7 2023年年3月月1日星期三日星期三上面两种形式的线性规划称为规范形式。上面两种形式的线性规划称为规范形式。原问题和对偶问题是互为对偶的两个线性规划问题，已知

8、一个问原问题和对偶问题是互为对偶的两个线性规划问题，已知一个问题就可写出另一个问题。题就可写出另一个问题。规范形式规范形式（Canonical Form）的定义：）的定义：目标函数求极大值时，所有约束条件目标函数求极大值时，所有约束条件为为号号，变量非负变量非负；目标函数求极小值时，所有约束条件目标函数求极小值时，所有约束条件为为号号，变量非负变量非负。规范形式的线性规划的对偶问题亦是规范形式。规范形式的线性规划的对偶问题亦是规范形式。以上是依据经济问题推导出对偶问题，还可以用代数方法以上是依据经济问题推导出对偶问题，还可以用代数方法推导出对偶问题。推导出对偶问题。2.1 线性规划的对偶模型线

9、性规划的对偶模型 Dual model of LP0)1.2(maxXbAXCXZ0)2.2(minXbAXCXZChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 8 2023年年3月月1日星期三日星期三0,0maxSNBSNBSNNBBXXXbEXNXBXXXCXCZXBXNXSbXBBNEbCCBCN00XBXNXSbXBEB1NB1B1b0CNCBB1NCBB1CBB1b表表2-2表表232.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LPChapter2 对偶理论对偶理论Dual Theory制作与教学武汉

10、理工大学管理学院 熊伟 Page 9 2023年年3月月1日星期三日星期三设线性规划模型是式（设线性规划模型是式（2.1）的规范形式由表）的规范形式由表2-3知，当检验数知，当检验数0011BCABCCBB时得到最优解时得到最优解，是是 的检验数的检验数,和和 ,令令 ,由由 得得ABCCB1），（NBXXXBBCCBB1NBCCBN11BCYB0011BCABCCBB与0YCYA在在 两边有乘两边有乘b,则有则有 ,又因又因Y0无上界无上界,从从而只存在最小值，得到另一个线性规划问题而只存在最小值，得到另一个线性规划问题1BCYBZbBCYbB12.1 线性规划的对偶模型线性规划的对偶模型

11、Dual model of LPChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 10 2023年年3月月1日星期三日星期三0minYCYAYbw即是原线性规划问题式（即是原线性规划问题式（2.1）的对偶线性规划问题，反之，式）的对偶线性规划问题，反之，式（2.3）的对偶问题是式（）的对偶问题是式（2.1）原问题和对偶问题是互为对偶）原问题和对偶问题是互为对偶的两个线性规划问题，规范形式的线性规划的对偶仍然是规范的两个线性规划问题，规范形式的线性规划的对偶仍然是规范形式，参数矩阵的对应关系参看表形式，参数矩阵的对应关系参看表2-4因此已知一

12、个规范形式因此已知一个规范形式问题就可写出另一个对偶问题问题就可写出另一个对偶问题2.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LPChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 11 2023年年3月月1日星期三日星期三【例例22】写出下列线性规划的对偶问题写出下列线性规划的对偶问题0,15744325min321321321321xxxxxxxxxxxxZ【解解】这是一个规范形式的线性规划，设这是一个规范形式的线性规划，设Y=（y1，y2），），则有则有)3,2,5()57,4(571114),(414),

13、(max212121212121yyyyyyyyYAyyyyYbw，2.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LPChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 12 2023年年3月月1日星期三日星期三从而对偶问题为从而对偶问题为0,03527544max2121212121yyyyyyyyyyZ对偶变量对偶变量yi也可写成也可写成xi的形式。的形式。)3,2,5()57,4(571114),(414),(max212121212121yyyyyyyyYAyyyyYbw，2.1 线性规划的对偶模型线性规划

14、的对偶模型 Dual model of LPChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 13 2023年年3月月1日星期三日星期三若给出的线性规划不是规范形式，可以先化成规范形式再写对若给出的线性规划不是规范形式，可以先化成规范形式再写对偶问题。也可直接按表偶问题。也可直接按表2-1中的对应关系写出非规范形式的对偶中的对应关系写出非规范形式的对偶问题。问题。将上述原问题与对偶问题的对应关系列于表将上述原问题与对偶问题的对应关系列于表2-1例如，原问题是求最小值，按表例如，原问题是求最小值，按表2-1有下列关系：有下列关系：1.第第i个

15、约束是个约束是“”约束时，第约束时，第i个对偶变量个对偶变量yj0 2第第i个约束是个约束是“=”约束时，第约束时，第i个对偶变量个对偶变量yi无约束；无约束；3当当xj0时，第时，第j个对偶约束为个对偶约束为“”约束，当约束，当xj无约束时无约束时，第，第j个对偶约束为个对偶约束为“=”约束。约束。2.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LPChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 14 2023年年3月月1日星期三日星期三原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原

16、问题）目标函数目标函数max目标函数系数（资源限量）目标函数系数（资源限量）约束条件系数矩阵约束条件系数矩阵A(AT)目标函数目标函数min资源限量（目标函数系数）资源限量（目标函数系数）约束条件系数矩阵约束条件系数矩阵AT(A)变变量量n个变量个变量第第j个变量个变量0第第j 个变量个变量0第第j个变量无约束个变量无约束约约束束 n个约束个约束第第j个约束为个约束为第第j个约束为个约束为第第j个约束为个约束为=约约束束m个约束个约束第第i个约束个约束第第i个约束个约束第第i个约束为个约束为=变变量量m个变量个变量第第i个变量个变量0第第i个变量个变量0第第i个变量无约束个变量无约束 表表2-

17、42.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LPChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 15 2023年年3月月1日星期三日星期三【例例2-3】写出下列线性规划的对偶问题写出下列线性规划的对偶问题 0,0,1482105618827945min43213214243214321xxxxxxxxxxxxxxxxxZ无约束【解解】目标函数求最小值，应将目标函数求最小值，应将表表24的右边看作原问题，左边的右边看作原问题，左边是对偶问题，原问题有是对偶问题，原问题有3个约束个约束4个变量，则对偶问题有个变

18、量，则对偶问题有3 个变量个变量4个约束，对照表个约束，对照表21的对应关系，的对应关系，对偶问题为：对偶问题为：123131231312max1810147226885wyyyyyyyyyyyy2.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LP=1549y10，y20，y3无约束Chapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 16 2023年年3月月1日星期三日星期三1.本节以实例引出对偶问题本节以实例引出对偶问题;2.介绍了如何写规范与非规范问题的对偶问题介绍了如何写规范与非规范问题的对偶问题;3.深刻领会

19、影子价格的含义，学会用影子价格作经济活动分析。深刻领会影子价格的含义，学会用影子价格作经济活动分析。作业：教材习题作业：教材习题 2.1,2.22.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LP下一节：对偶性质下一节：对偶性质2.2 对偶性质对偶性质Dual property Chapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 18 2023年年3月月1日星期三日星期三0maxXbAXCXZ对偶问题是（记为对偶问题是（记为DP）：）：0minYCYAYbw这里这里A是是mn矩阵矩阵X是是n1列向量，列向量，Y是是1

20、m行向量。假设行向量。假设Xs与与Ys分别是（分别是（LP）与（）与（DP）的松驰变量。）的松驰变量。【性质性质1】对称性对称性 对偶问题的对偶是原问题。对偶问题的对偶是原问题。【证证】设原问题是设原问题是0,maxXbAXCXZ设原问题是（记为设原问题是（记为LP）：）：2.2 对偶性质对偶性质Dual property2.2.1 对偶性质对偶性质Chapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 19 2023年年3月月1日星期三日星期三0,minYCYAYbw它与下列线性规划问题是等价的：它与下列线性规划问题是等价的：0,)max(YC

21、YAYbw再写出它的对偶问题。再写出它的对偶问题。0,minXbAXCXw它与下列线性规划问题是等价的它与下列线性规划问题是等价的0,maxXbAXCXZ即是原问题。即是原问题。由表由表2-4知，它的对偶问题是知，它的对偶问题是2.2 对偶性质对偶性质Dual propertyChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 20 2023年年3月月1日星期三日星期三【证证】因为因为X、Y是可行解，故有是可行解，故有AXb,X0及及YAC，Y0,将不等式将不等式 AXb【性质性质2】弱对偶性弱对偶性 设设X、Y分别为分别为LP(max)与与

22、DP(min)的可行解，则的可行解，则 bYCX00两边左乘两边左乘Y，得，得Y0AXY0b再将不等式再将不等式YAC两边右乘两边右乘X，得，得C XYAX故故 C XYAXYb这一性质说明了两个线性规划互为对偶时，求最大值的这一性质说明了两个线性规划互为对偶时，求最大值的线性规划的任意目标值都不会大于求最小值的线性规划线性规划的任意目标值都不会大于求最小值的线性规划的任一目标值，不能理解为原问题的目标值不超过对偶的任一目标值，不能理解为原问题的目标值不超过对偶问题的目标值。问题的目标值。2.2 对偶性质对偶性质Dual propertyChapter2 对偶理论对偶理论Dual Theory

23、制作与教学武汉理工大学管理学院 熊伟 Page 21 2023年年3月月1日星期三日星期三由这个性质可得到下面几个结论：由这个性质可得到下面几个结论：（1）（）（LP）的任一可行解的目标值是（）的任一可行解的目标值是（DP）的最优值下界；）的最优值下界；（DP）的任一可行解的目标是（）的任一可行解的目标是（LP）的最优值的上界；）的最优值的上界；（2）在互为对偶的两个问题中，若一个问题可行且具有无界解，）在互为对偶的两个问题中，若一个问题可行且具有无界解，则另一个问题无可行解；则另一个问题无可行解；(3)若原问题可行且另一个问题不可行，则原问题具有无界解。若原问题可行且另一个问题不可行，则原问

24、题具有无界解。注意上述结论（注意上述结论（2）及（）及（3）的条件不能少。一个问题无可行解时，）的条件不能少。一个问题无可行解时，另一个问题可能有可行解（此时具有无界解）也可能无可行解。另一个问题可能有可行解（此时具有无界解）也可能无可行解。2.2 对偶性质对偶性质Dual propertyChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 22 2023年年3月月1日星期三日星期三例如：例如：0,22212min21212121xxxxxxxxz无可行解，而对偶问题无可行解，而对偶问题0,221122max21212121yyyyyyyyw

25、有可行解，由结论（有可行解，由结论（3）知必有无界解。）知必有无界解。2.2 对偶性质对偶性质Dual propertyChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 23 2023年年3月月1日星期三日星期三【性质性质3】最优准则定理最优准则定理 设设X0与与Y0分别是（分别是（LP）与（）与（DP）的）的可行解，则当可行解，则当X0、Y0是（是（LP）与（）与（DP）的最优解当且仅当）的最优解当且仅当C X0=Y0b.【证证】若若X0、Y0为最优解，为最优解，B为（为（LP）的最优基，则有）的最优基，则有Y0=CBB1，并且，并且bY

26、bBCCXB010当当C X0=Y0b时，由性质时，由性质1，对任意可行解，对任意可行解 有有YX及bYCXbYXC00即即Y0b是（是（DP）中任一可行解的目标值的下界，）中任一可行解的目标值的下界，C X0是（是（LP）中）中任一可行解的目标值的上界，从而任一可行解的目标值的上界，从而X0、Y0是最优解。是最优解。2.2 对偶性质对偶性质Dual propertyChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 24 2023年年3月月1日星期三日星期三【性质性质4】若互为对偶的两个问题其中一个有最优解，则另一若互为对偶的两个问题其中一

27、个有最优解，则另一个也有最优解，且最优值相同。个也有最优解，且最优值相同。【证证】设（设（LP）有最优解）有最优解X0,那么对于最优基那么对于最优基B必有必有C-CBB-1A0与与CBB-10，即有，即有YAC与与Y0，这里，这里Y=CBB-1，从而，从而Y是是可行解，对目标函数有可行解，对目标函数有bYbBCXCCXBBB010由性质由性质3知知Y是最优解。是最优解。由性质由性质 4 还可推出还可推出另一结论另一结论：若（：若（LP）与（）与（DP）都有可行解，）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。解

28、。2.2 对偶性质对偶性质Dual propertyChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 25 2023年年3月月1日星期三日星期三【性质性质5】互补松弛定理互补松弛定理 设设X0、Y0分别为（分别为（LP）与（）与（DP）的可）的可行解，行解，XS和和YS是它的松弛变量的可行解，则是它的松弛变量的可行解，则X0和和Y0是最优解当且是最优解当且仅当仅当YSX0=0和和Y0XS=0【证证】设设X和和Y是最优解是最优解,由性质由性质3，C X0=Y0b，由于，由于XS和和YS是松弛变量，则有是松弛变量，则有A X0XSbY0AYS=

29、C将第一式左乘将第一式左乘Y0，第二式右乘，第二式右乘X0得得Y0A X0Y0XSY0bY0A X0YS X0=C X02.2 对偶性质对偶性质Dual propertyChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 26 2023年年3月月1日星期三日星期三显然有显然有 Y0XS=YS X0又因为又因为Y、Xs、Ys、X0，所以有，所以有YXS=0和和YS X=0成立。成立。反之，反之，当当YXS=0和和YS X=0时，有时，有YA XYbYA X=C X显然有显然有Y0b=C X,由性质由性质3知知Y与与X是（是（LP）与（）与（DP

30、）的最）的最优解。证毕。优解。证毕。2.2 对偶性质对偶性质Dual propertyChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 27 2023年年3月月1日星期三日星期三性质性质5告诉我们已知一个问题的最优解时求另一个问题的最优解告诉我们已知一个问题的最优解时求另一个问题的最优解的方法，即已知的方法，即已知Y*求求X*或已知或已知X*求求Y*。Y*XS=0和和YS X*=0两式称为互补松弛条件。将互补松弛条件写成下式两式称为互补松弛条件。将互补松弛条件写成下式*1*100ijmiSinSjjy xy x由于变量都非负，要使求和式等于

31、零，则必定每一分量为零，由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：因而有下列关系：2.2 对偶性质对偶性质Dual propertyChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 28 2023年年3月月1日星期三日星期三(1)当yi*0时，,反之当 时yi*=0；0iSx0iSx*(2)00,00jjSjjSyxxy时反之当时利用上述关系，建立对偶问题（或原问题）的约束线性方程组，利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。方程组的解即为最优解。性质性质5的结论和证明都是假定

32、（的结论和证明都是假定（P）与（）与（D）为对称形式，事实）为对称形式，事实上对于非对称形式，性质上对于非对称形式，性质5的结论仍然有效。的结论仍然有效。【例例2-4】已知线性规划已知线性规划3,2,1,0162210243max321321321jxxxxxxxxxxzj的最优解是的最优解是 求对偶问题的最优解。求对偶问题的最优解。TX)0,2,6(2.2 对偶性质对偶性质Dual propertyChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 29 2023年年3月月1日星期三日星期三【解解】对偶问题是对偶问题是0,142232161

33、0min2121212121yyyyyyyyyyw因为因为X10，X20，所以对偶问题的第一、，所以对偶问题的第一、二个约束的松弛变量等于零，即二个约束的松弛变量等于零，即422322121yyyy解此线性方程组得解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为从而对偶问题的最优解为Y=（1，1），最优值），最优值w=26。2.2 对偶性质对偶性质Dual propertyChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 30 2023年年3月月1日星期三日星期三【例例2-5】已知线性规划已知线性规划 无约束32132132132

34、1,0,06422minxxxxxxxxxxxxz的对偶问题的最优解为的对偶问题的最优解为Y=（0，2），求原问题的最），求原问题的最优解。优解。【解解】对偶问题是对偶问题是021264max2121212121yyyyyyyyyyw无约，2.2 对偶性质对偶性质Dual propertyChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 31 2023年年3月月1日星期三日星期三解方程组得：解方程组得：x 1=5,x 3=1,所以原问题的最优解为所以原问题的最优解为X=（5，0，1），最优值），最优值Z=12。643131xxxx因为因为y

35、20，所以原问题第二个松弛变量，所以原问题第二个松弛变量 =0，则，则y1=0、y2=2知，松弛变量知，松弛变量 故故x2=0，则原问题的约束条件为线性方程组：则原问题的约束条件为线性方程组：,1,021SSyy2Sx2.2 对偶性质对偶性质Dual propertyChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 32 2023年年3月月1日星期三日星期三【例例2-6】证明下列线性规划无最优解：证明下列线性规划无最优解：3,2,1,0324min32131321jxxxxxxxxxZj【证证】容易看出容易看出X=（4，0，0）是一可行解，

36、故问题可行。对）是一可行解，故问题可行。对偶问题偶问题0,0121134max212122121yyyyyyyyyw将三个约束的两端分别相加得将三个约束的两端分别相加得而第二个约束有而第二个约束有y21，矛盾，故对偶问，矛盾，故对偶问题无可行解，题无可行解，因而原问题具有无界因而原问题具有无界解，即无最优解。解，即无最优解。212y2.2 对偶性质对偶性质Dual propertyChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 33 2023年年3月月1日星期三日星期三【性质性质6】LP(max)的检验数的相反数对应于的检验数的相反数对应

37、于DP(min)的一组基本解的一组基本解.其中第其中第j个决策变量个决策变量xj的检验数的相反数对应于（的检验数的相反数对应于（DP）中第中第j个松弛变量个松弛变量 的解，第的解，第i个松弛变量个松弛变量 的检验数的相反数对应于第的检验数的相反数对应于第i个对偶变量个对偶变量yi的解。反的解。反之，（之，（DP）的检验数（注意：不乘负号）对应于）的检验数（注意：不乘负号）对应于（LP）的一组基本解。）的一组基本解。证明略。证明略。jSyiSx2.2 对偶性质对偶性质Dual propertyChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page

38、34 2023年年3月月1日星期三日星期三【例例2-7】线性规划线性规划0,442226max32131321321xxxxxxxxxxxz（1）用单纯形法求最优解；）用单纯形法求最优解；（2）写出每步迭代对应对偶问题的基本解；）写出每步迭代对应对偶问题的基本解；（3）从最优表中写出对偶问题的最优解；）从最优表中写出对偶问题的最优解；（4）用公式）用公式Y=CBB-1求对偶问题的最优解。求对偶问题的最优解。【解解】（1）加入松弛变量）加入松弛变量x4、x5后，单纯形迭代如表后，单纯形迭代如表2-2所示。所示。2.2 对偶性质对偶性质Dual propertyChapter2 对偶理论对偶理论D

39、ual Theory制作与教学武汉理工大学管理学院 熊伟 Page 35 2023年年3月月1日星期三日星期三XBx1x2x3x4x5b表表（1）x4x5211024100124j62100表表（2）x1x5101/21/2131/21/20113j01530表表（3）x1x2100146011246j001122表表2-22.2 对偶性质对偶性质Dual propertyChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 36 2023年年3月月1日星期三日星期三最优解最优解X=（4，6，0），最优值），最优值Z=6426=12；（2）设对

40、偶变量为）设对偶变量为y1、y2,松弛变量为松弛变量为y3、y4、y5,Y=（y1、y2、y3、y4、y5），由性质），由性质6得到对偶问题的基本解得到对偶问题的基本解 （y1、y2、y3、y4、y5）=（4，5，1，2，3），即），即 表表22（1）中）中=（6，2，1，0，0），），则则Y（1）=（0，0，-6，2，1）表表22（2）中）中=（0，1，5，3，0），），则则Y（2）=（3，0，0，1，5）表表22（3）中）中=（0，0，11，2，2），），则则Y（3）=（2，2，0，0，11）2.2 对偶性质对偶性质Dual propertyChapter2 对偶理论对偶理论Dual Th

41、eory制作与教学武汉理工大学管理学院 熊伟 Page 37 2023年年3月月1日星期三日星期三（3）因为表）因为表22（3）为最优解，故）为最优解，故 Y（3）=（2，2，0，0，11）为对偶问题最优解；）为对偶问题最优解；（4）表）表22（3）中的最优基）中的最优基 B-1 为表为表22（3）中）中x4，x 5两列的系数，即两列的系数，即2110BCB=（6，2），因而），因而21101B)2,2(2110)2,6(),(121BCyyYB2.2 对偶性质对偶性质Dual propertyChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Pag

42、e 38 2023年年3月月1日星期三日星期三本节您学了六个对偶性质；这些性质是研究原问题与对偶问题解本节您学了六个对偶性质；这些性质是研究原问题与对偶问题解的对应关系；表的对应关系；表26也许对您了解这些性质有帮助。也许对您了解这些性质有帮助。表表26一个问题一个问题max另一个问题另一个问题min有最优解有最优解有最优解有最优解性质性质4无无无最优解无最优解无最优解无最优解性质性质4最最优优无界解无界解（有可行解）（有可行解）无可行解无可行解性质性质2解解无可行解无可行解无界解无界解（有可行解）（有可行解）应用应用已知最优解已知最优解通过解方程通过解方程求最优解求最优解性质性质5已知检验数

43、已知检验数检验数乘以检验数乘以1求得基本解求得基本解性质性质62.2 对偶性质对偶性质Dual propertyChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 39 2023年年3月月1日星期三日星期三 影子价格影子价格(Shadow price):原始线性规划问题考虑的是充分原始线性规划问题考虑的是充分利用现有资源，以产品的数量和单位产品的收益来决定企业的利用现有资源，以产品的数量和单位产品的收益来决定企业的总收益，没有考虑到资源的价格，但实际在构成产品的收益中，总收益，没有考虑到资源的价格，但实际在构成产品的收益中，不同的资源对收益的

44、贡献也不同，它是企业生产过程中一种隐不同的资源对收益的贡献也不同，它是企业生产过程中一种隐含的潜在价值，经济学中称为含的潜在价值，经济学中称为影子价格影子价格，即对偶问题中的决策，即对偶问题中的决策变量变量yi的值。的值。2.2.2 影子价格影子价格因为原问题和对偶问题的最优值相等，将线性规划的目标函因为原问题和对偶问题的最优值相等，将线性规划的目标函数表达成资源的函数，故有数表达成资源的函数，故有111,mBBBiiiiiZC XC B bYbb yZyimb即即yi是第是第 i 种资源的变化率，说明当其它资源供应量种资源的变化率，说明当其它资源供应量bk(ki)不不变时，变时，bi增加一个

45、单位时目标值增加一个单位时目标值Z增加增加yi个单位个单位2.2 对偶性质对偶性质Dual propertyChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 40 2023年年3月月1日星期三日星期三在例在例2-7中，中，2.2 对偶性质对偶性质Dual property0,442226max32131321321xxxxxxxxxxxzY=（2，2，0，0，11）为对偶问题最优解）为对偶问题最优解第一种资源的影子价格为第一种资源的影子价格为y1=2，第二种资源的影子价格为，第二种资源的影子价格为y2=2，即当第一种资源增加一个单位时，即当

46、第一种资源增加一个单位时，Z增加增加2个单位，个单位，当第二种资源增加一个单位时，当第二种资源增加一个单位时，Z增加增加2个单位个单位Chapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 41 2023年年3月月1日星期三日星期三正确理解影子价格，利用影子价格作下列经济活动分析正确理解影子价格，利用影子价格作下列经济活动分析（1）调节生产规模例如，目标函数）调节生产规模例如，目标函数Z表示利润（或产值），表示利润（或产值），当第当第i种资源的影子价格大于零（或高于市场价格）时，表示有种资源的影子价格大于零（或高于市场价格）时，表示有利可图，企业

47、应购进该资源扩大生产规模，当影子价格等于零利可图，企业应购进该资源扩大生产规模，当影子价格等于零（或低于市场价格），企业不能增加收益，这时应将资源卖掉（或低于市场价格），企业不能增加收益，这时应将资源卖掉或出让，缩小生产规模或出让，缩小生产规模（2）生产要素对产出贡献的分解通过影子价格分析每种资源）生产要素对产出贡献的分解通过影子价格分析每种资源获得多少产出例如，企业获得获得多少产出例如，企业获得100万元的利润，生产过程中产万元的利润，生产过程中产品的直接消耗的资源有材料品的直接消耗的资源有材料A、材料、材料B、设备和工时，这些资源、设备和工时，这些资源各产生多少利润，由影子价格可以大致估计

48、出来各产生多少利润，由影子价格可以大致估计出来（3）由性质）由性质2.5知，第知，第i个松弛变量大于零时第个松弛变量大于零时第i个对偶变量等于个对偶变量等于零，并不能说明该资源在生产过程中没有作出贡献，只能理解零，并不能说明该资源在生产过程中没有作出贡献，只能理解为第为第i种资源有剩余时再增加该资源量不能给企业带来利润或产种资源有剩余时再增加该资源量不能给企业带来利润或产值的增加值的增加2.2 对偶性质对偶性质Dual propertyChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 42 2023年年3月月1日星期三日星期三例如，第一种资

49、源的影子价格为例如，第一种资源的影子价格为y1=2，第二种资源的影子价格为，第二种资源的影子价格为y2=2，即当第一种资源增加一个单位时，即当第一种资源增加一个单位时，Z增加增加2个单位，当第二个单位，当第二种资源增加一个单位时，种资源增加一个单位时，Z增加增加2个单位。个单位。企业可利用影子价格调节生产规模。例如，目标函数企业可利用影子价格调节生产规模。例如，目标函数Z表示表示利润（或产值利润（或产值)，当第，当第i种资源的影子价格大于零种资源的影子价格大于零(或高于市场价或高于市场价格）时，表示有利可图，企业应购进该资源扩大生产规模，当格）时，表示有利可图，企业应购进该资源扩大生产规模，当

50、影子价格等于零（或低于市场价格），企业不能增加收益，这影子价格等于零（或低于市场价格），企业不能增加收益，这时应将资源卖掉或出让，缩小生产规模。应当注意，时应将资源卖掉或出让，缩小生产规模。应当注意，是是在最优基在最优基B不变的条件下有上述经济含义，当某种资源增加或不变的条件下有上述经济含义，当某种资源增加或减少后，最优基减少后，最优基B可能发生了变化，这时可能发生了变化，这时yi的值也随之变化。的值也随之变化。iibZy2.2 对偶性质对偶性质Dual propertyChapter2 对偶理论对偶理论Dual Theory制作与教学武汉理工大学管理学院 熊伟 Page 43 2023年年3