运筹学对偶理论.ppt

《运筹学对偶理论.ppt》由会员分享，可在线阅读，更多相关《运筹学对偶理论.ppt（104页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学对偶理论运筹学对偶理论2.1线性规划的对偶模型线性规划的对偶模型DualModelofLP对偶理论对偶理论制作与教学在在线线性性规规划划问问题题中中，存存在在一一个个有有趣趣的的问问题题，即即每每一一个个线线性性规规划划问问题题都都伴伴随随有有另另一一个个线线性性规规划划问问题题，称称它它为为对对偶偶线线性性规规划划问问题。题。【例【例2.1】某企业用四种资源生产三种产品，工艺系数、资源限量某企业用四种资源生产三种产品，工艺系数、资源限量及价值系数如下表：及价值系数如下表：建立总收益最大的数学模型。建立总收益最大的数学模型。产品产品资源资源ABC资源限量资源限量9865005474508

2、32300764550单件产品利润单件产品利润10080702.1线性规划的对偶模型线性规划的对偶模型DualmodelofLP对偶理论对偶理论制作与教学【解】设【解】设x1，x2，x3分别为产品分别为产品A，B，C的产量，则线性规划数学的产量，则线性规划数学模型为：模型为：现现在在从从另另一一个个角角度度来来考考虑虑企企业业的的决决策策问问题题。假假如如企企业业自自己己不不生生产产产产品品，而而将将现现有有的的资资源源转转让让或或出出租租给给其其它它企企业业，那那么么资资源源的的转转让让价价格格是是多多少少才才合合理理？合合理理的的价价格格应应是是对对方方用用最最少少的的资资金金购购买买本本

3、企企业业的的全全部部资资源源，而而本本企企业业所所获获得得的的利利润润不不应应低低于于自自己己用用于于生生产产时时所所获获得得的的利利润润。这这一一决决策策问问题题可可用用下下列列线线性性规规划划数数学学模模型型来来表示。表示。2.1线性规划的对偶模型线性规划的对偶模型DualmodelofLP对偶理论对偶理论制作与教学设设y1，y2，y3及及y4分分别别表表示示四四种种资资源源的的单单位位增增值值价价格格（售售价成本增值），总增值最低可用价成本增值），总增值最低可用min w=500y1+450y2+300y3+550y4表表示示。企企业业生生产产一一件件产产品品A用用了了四四种种资资源源的

4、的数数量量分分别别是是9，5，8和和7个个单单位位，利利润润是是100,企企业业出出售售这这些些数数量量的的资资源源所得的利润不能少于所得的利润不能少于100，即，即同理，对产品同理，对产品B和和C有有价价格格不不可可能能小小于于零零，即即有有yi0,i=1,4.从从而而企企业业的的资资源源价格模型为价格模型为2.1线性规划的对偶模型线性规划的对偶模型DualmodelofLP对偶理论对偶理论制作与教学这这是是一一个个线线性性规规划划数数学学模模型型，称称这这一一线线性性规规划划模模型型是是前前面面生生产产计计划划模模型型的的对对偶偶线线性性规规划划模模型型,这这一一问问题题称称为为对对偶偶问

5、问题题。生生产产计计划划的的线线性性规规划划问问题题称称为为原原始始线线性性规规划划问问题题或原问题。或原问题。2.1线性规划的对偶模型线性规划的对偶模型DualmodelofLP对偶理论对偶理论制作与教学上面两种形式的线性规划称为规范形式。上面两种形式的线性规划称为规范形式。原问题和对偶问题是互为对偶的两个线性规划问题，已知一个问原问题和对偶问题是互为对偶的两个线性规划问题，已知一个问题就可写出另一个问题。题就可写出另一个问题。规范形式规范形式（CanonicalForm）的定义：）的定义：目标函数求极大值时，所有约束条件目标函数求极大值时，所有约束条件为为号号，变量非负变量非负；目标函数求

6、极小值时，所有约束条件目标函数求极小值时，所有约束条件为为号号，变量非负变量非负。规范形式的线性规划的对偶问题亦是规范形式。规范形式的线性规划的对偶问题亦是规范形式。以上是依据经济问题推导出对偶问题，还可以用代数方法以上是依据经济问题推导出对偶问题，还可以用代数方法推导出对偶问题。推导出对偶问题。2.1线性规划的对偶模型线性规划的对偶模型DualmodelofLP对偶理论对偶理论制作与教学原始问题Max z=CTXs.t.AX bX 0对偶问题Min w=bT ys.t.AT y C y 0maxbACTCATbT minmnmn 对偶的定义对偶的定义对偶理论对偶理论制作与教学 规范对偶问题规

7、范对偶问题min z=CTXs.t.AXbX 0max w=bTys.t.ATyC y0max z=CTXs.t.AX bX 0min w=bTys.t.ATy C y0对偶理论对偶理论制作与教学XBXNXSbXBBNEbCCBCN00XBXNXSbXBEB1NB1B1b0CNCBB1NCBB1CBB1b表表2-2表表232.1线性规划的对偶模型线性规划的对偶模型DualmodelofLP对偶理论对偶理论制作与教学设线性规划模型是式（设线性规划模型是式（2.1）的规范形式由表）的规范形式由表2-3知，当检验数知，当检验数时得到最优解时得到最优解，是是的检验数的检验数,和和,令令,由由得得在在两

8、边有乘两边有乘b,则有则有,又因又因Y0无上界无上界,从从而只存在最小值，得到另一个线性规划问题而只存在最小值，得到另一个线性规划问题2.1线性规划的对偶模型线性规划的对偶模型DualmodelofLP对偶理论对偶理论制作与教学即是原线性规划问题式（即是原线性规划问题式（2.1）的对偶线性规划问题，反之，式）的对偶线性规划问题，反之，式（2.3）的对偶问题是式（）的对偶问题是式（2.1）原问题和对偶问题是互为对偶）原问题和对偶问题是互为对偶的两个线性规划问题，规范形式的线性规划的对偶仍然是规范形的两个线性规划问题，规范形式的线性规划的对偶仍然是规范形式，参数矩阵的对应关系参看表式，参数矩阵的对

9、应关系参看表2-4因此已知一个规范形式问因此已知一个规范形式问题就可写出另一个对偶问题题就可写出另一个对偶问题2.1线性规划的对偶模型线性规划的对偶模型DualmodelofLP对偶理论对偶理论制作与教学【例【例2.2】写出下列线性规划的对偶问题】写出下列线性规划的对偶问题【解】这是一个规范形式的线性规划，设【解】这是一个规范形式的线性规划，设Y=（y1，y2），），则有则有2.1线性规划的对偶模型线性规划的对偶模型DualmodelofLP对偶理论对偶理论制作与教学从而对偶问题为从而对偶问题为对偶变量对偶变量yi也可写成也可写成xi的形式。的形式。2.1线性规划的对偶模型线性规划的对偶模型D

10、ualmodelofLP对偶理论对偶理论制作与教学【例【例2.3】写出下列线性规划的对偶问题写出下列线性规划的对偶问题【解解】这这是是一一个个规规范范形形式式的的线线性性规规划划，它它的的对对偶偶问问题题求求最小值，有三个变量且非负，有两个最小值，有三个变量且非负，有两个“”约束，即约束，即2.1线性规划的对偶模型线性规划的对偶模型DualmodelofLP对偶理论对偶理论制作与教学若给出的线性规划不是规范形式，可以先化成规范形式再写对偶若给出的线性规划不是规范形式，可以先化成规范形式再写对偶问题。也可直接按表问题。也可直接按表2-1中的对应关系写出非规范形式的对偶问中的对应关系写出非规范形式

11、的对偶问题。题。将上述原问题与对偶问题的对应关系列于表将上述原问题与对偶问题的对应关系列于表2-1例如，原问题是求最小值，按表例如，原问题是求最小值，按表2-1有下列关系：有下列关系：1.第第i个约束是个约束是“”约束时，第约束时，第i个对偶变量个对偶变量yj02第第i个约束是个约束是“=”约束时，第约束时，第i个对偶变量个对偶变量yi无约束；无约束；3当当xj0时时，第第j个个对对偶偶约约束束为为“”约约束束，当当xj无无约约束束时时，第第j个个对偶约束为对偶约束为“=”约束。约束。2.1线性规划的对偶模型线性规划的对偶模型DualmodelofLP对偶理论对偶理论制作与教学原问题（或对偶问

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

13、个变量个变量0第第i个变量无约束个变量无约束表表2-42.1线性规划的对偶模型线性规划的对偶模型DualmodelofLP对偶理论对偶理论制作与教学当原问题为求极小值时，对偶问题为求极大值。原始问题中目标函数的系数变成对偶问题中约束条件的右端；原始问题中约束条件的右端变成对偶问题中目标函数的系数。原始问题约束条件系数矩阵的转置对应对偶问题中约束条件的系数矩阵。原始问题的约束条件个数决定对偶问题变量的个数；原始问题变量个数，决定对偶问题的约束个数。原始问题的约束方程的匹配形式决定对偶问题变量的符号；原始问题决策变量的符号决定所对应对偶问题的约束方程的匹配形式。对偶理论对偶理论制作与教学【例【例2

14、.4】写出下列线性规划的对偶问题】写出下列线性规划的对偶问题【解解】目目标标函函数数求求最最小小值值，应应将将表表24的的右右边边看看作作原原问问题题，左左边边是是对对偶偶问问题题，原原问问题题有有3个个约约束束4个个变变量量，则则对对偶偶问问题题有有3个个变变量量4个个约约束束，对对照照表表21的的对对应应关关系系，对偶问题为：对偶问题为：2.1线性规划的对偶模型线性规划的对偶模型DualmodelofLP=y10，y20，y3无约束对偶理论对偶理论制作与教学min z=2x1+4x2-x3s.t.3x1-x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2

15、-x3 15max w=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y4 2 -y1+2y2+y3+3y4 4 2y1-3y2+2y3-y4 -1 y1 0,y2 ,y3 0,y4 0=unr=x10 x20 x3:unrq原始问题变量的个数(3)等于对偶问题约束条件的个数(3)；原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。q原始问题变量的性质影响对偶问题约束条件的性质，用 表示 原始问题约束条件的性质影响对偶问题变量的性质，用 表示练习练习对偶理论对偶理论制作与教学1.本节以实例引出对偶问题本节以实例引出对偶问题;2.介绍了如何写规范与非规范问题的对偶问题介

16、绍了如何写规范与非规范问题的对偶问题;作业：教材作业：教材P61T1、22.1线性规划的对偶模型线性规划的对偶模型DualmodelofLP下一节：对偶性质下一节：对偶性质2.2对偶性质对偶性质Dualproperty对偶理论对偶理论制作与教学对偶问题是（记为对偶问题是（记为DP）：）：这这里里A是是mn矩矩阵阵X是是n1列列向向量量，Y是是1m行行向向量量。假假设设Xs与与Ys分别是（分别是（LP）与（）与（DP）的松驰变量。）的松驰变量。【性质【性质1】对称性对称性对偶问题的对偶是原问题。对偶问题的对偶是原问题。【证】设原问题是【证】设原问题是设原问题是（记为设原问题是（记为LP）：）：2

17、.2对偶性质对偶性质Dualproperty2.2.1对偶性质对偶性质对偶理论对偶理论制作与教学它与下列线性规划问题是等价的：它与下列线性规划问题是等价的：再写出它的对偶问题。再写出它的对偶问题。它与下列线性规划问题是等价的它与下列线性规划问题是等价的即是原问题。即是原问题。由表由表2-4知，它的对偶问题是知，它的对偶问题是2.2对偶性质对偶性质Dualproperty对偶理论对偶理论制作与教学【证】因为【证】因为X、Y是可行解，故有是可行解，故有AXb,X0及及YAC，Y0,将不等式将不等式AXb【性质【性质2】弱对偶性弱对偶性设设X、Y分别为分别为LP(max)与与DP(min)的可行解，

18、则的可行解，则两边左乘两边左乘Y，得，得Y0AXY0b再将不等式再将不等式YAC两边右乘两边右乘X，得，得C XYAX故故C XYAXYb这这一一性性质质说说明明了了两两个个线线性性规规划划互互为为对对偶偶时时，求求最最大大值值的的线线性性规规划划的的任任意意目目标标值值都都不不会会大大于于求求最最小小值值的的线线性性规规划划的的任任一一目目标标值值，不不能能理理解解为为原原问问题题的的目目标标值值不不超超过过对对偶偶问题的目标值。问题的目标值。2.2对偶性质对偶性质Dualproperty对偶理论对偶理论制作与教学由这个性质可得到下面几个结论：由这个性质可得到下面几个结论：（1）（LP）的的

19、任任一一可可行行解解的的目目标标值值是是（DP）的的最最优优值值下下界界；（DP）的任一可行解的目标是（）的任一可行解的目标是（LP）的最优值的上界；）的最优值的上界；（2）在在互互为为对对偶偶的的两两个个问问题题中中，若若一一个个问问题题可可行行且且具具有有无无界界解解，则另一个问题无可行解；则另一个问题无可行解；(3)若原问题可行且另一个问题不可行，则原问题具有无界解。若原问题可行且另一个问题不可行，则原问题具有无界解。注注意意上上述述结结论论（2）及及（3）的的条条件件不不能能少少。一一个个问问题题无无可可行行解解时时，另一个问题可能有可行解（此时具有无界解）也可能无可行解。另一个问题可

20、能有可行解（此时具有无界解）也可能无可行解。2.2对偶性质对偶性质Dualproperty对偶理论对偶理论制作与教学例如：例如：无可行解，而对偶问题无可行解，而对偶问题有可行解，由结论（有可行解，由结论（3）知必有无界解。）知必有无界解。2.2对偶性质对偶性质Dualproperty对偶理论对偶理论制作与教学【性性质质3】最最优优准准则则定定理理设设X0与与Y0分分别别是是（LP）与与（DP）的的可行解，则当可行解，则当X0、Y0是（是（LP）与（）与（DP）的最优解当且仅当）的最优解当且仅当C X0=Y0b.【证】若【证】若X0、Y0为最优解，为最优解，B为（为（LP）的最优基，则有）的最优

21、基，则有Y0=CBB1，并且，并且当当C X0=Y0b时，由性质时，由性质1，对任意可行解，对任意可行解有有即即Y0b是是（DP）中中任任一一可可行行解解的的目目标标值值的的下下界界，C X0是是（LP）中中任一可行解的目标值的上界，从而任一可行解的目标值的上界，从而X0、Y0是最优解。是最优解。2.2对偶性质对偶性质Dualproperty对偶理论对偶理论制作与教学【性性质质4】若若互互为为对对偶偶的的两两个个问问题题其其中中一一个个有有最最优优解解，则则另另一一个也有最优解，且最优值相同。个也有最优解，且最优值相同。【证证】设设（LP）有有最最优优解解X0,那那么么对对于于最最优优基基B必

22、必有有C-CBB-1A0与与CBB-10，即即有有YAC与与Y0，这这里里Y=CBB-1，从从而而Y是是可可行行解，对目标函数有解，对目标函数有由性质由性质3知知Y是最优解。是最优解。由由性性质质4还还可可推推出出另另一一结结论论：若若（LP）与与（DP）都都有有可可行行解解，则则两两者者都都有有最最优优解解，若若一一个个问问题题无无最最优优解解，则则另另一一问问题题也也无无最最优优解。解。2.2对偶性质对偶性质Dualproperty对偶理论对偶理论制作与教学【性性质质5】互互补补松松弛弛定定理理设设X0、Y0分分别别为为（LP）与与（DP）的的可可行行解解，XS和和YS是是它它的的松松弛弛

23、变变量量的的可可行行解解，则则X0和和Y0是是最最优优解解当当且且仅当仅当YSX0=0和和Y0XS=0【证证】设设X和和Y是是最最优优解解,由由性性质质3，C X0=Y0b，由由于于XS和和YS是是松松弛变量，则有弛变量，则有A X0XSbY0AYS=C将第一式左乘将第一式左乘Y0，第二式右乘，第二式右乘X0得得Y0A X0Y0XSY0bY0A X0YS X0=C X02.2对偶性质对偶性质Dualproperty对偶理论对偶理论制作与教学显然有显然有Y0XS=YS X0又因为又因为Y、Xs、Ys、X0，所以有，所以有YXS=0和和YS X=0成立。成立。反之，反之，当当YXS=0和和YS X

24、=0时，有时，有YA XYbYA X=C X显显然然有有Y0b=C X,由由性性质质3知知Y与与X是是（LP）与与（DP）的的最最优优解解。证毕。证毕。2.2对偶性质对偶性质Dualproperty对偶理论对偶理论制作与教学性性质质5告告诉诉我我们们已已知知一一个个问问题题的的最最优优解解时时求求另另一一个个问问题题的的最最优优解解的方法，即已知的方法，即已知Y*求求X*或已知或已知X*求求Y*。Y*XS=0和和YS X*=0两式称为互补松弛条件。将互补松弛条件写成下式两式称为互补松弛条件。将互补松弛条件写成下式由由于于变变量量都都非非负负，要要使使求求和和式式等等于于零零，则则必必定定每每一

25、一分分量量为为零零，因而有下列关系：因而有下列关系：2.2对偶性质对偶性质Dualproperty对偶理论对偶理论制作与教学(1)当yi*0时，,反之当 时yi*=0；利利用用上上述述关关系系，建建立立对对偶偶问问题题（或或原原问问题题）的的约约束束线线性性方方程程组组，方程组的解即为最优解。方程组的解即为最优解。性性质质5的的结结论论和和证证明明都都是是假假定定（P）与与（D）为为对对称称形形式式，事事实实上上对于非对称形式，性质对于非对称形式，性质5的结论仍然有效。的结论仍然有效。2.2对偶性质对偶性质Dualproperty对偶理论对偶理论制作与教学互补松弛关系max z=CTXs.t.

26、AX+u=b X,u0min w=bTys.t.ATy-v=C y,v0max z=CTXs.t.AX b X 0min w=bTys.t.ATy C y0对偶引进松弛变量引进松弛变量XTv=0 yTu=0互补松弛关系互补松弛关系X，uy，v对偶理论对偶理论制作与教学max z=CTXs.t.AX+u=bX,u 0min w=bTys.t.ATy-v=Cy,v 0XTv=0yTu=0mn=yvAT-ICn=AuIbnmmX对偶理论对偶理论制作与教学y1 yi ym vm+1 vm+j vn+m x1 xj xn un+1 un+i un+m 对偶问题的变量 对偶问题的松弛变量xjvm+j=0y

27、iun+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于0，另一个一定等于0对偶理论对偶理论制作与教学【例【例2.5】已知线性规划已知线性规划的最优解是的最优解是求对偶问题的最优解。求对偶问题的最优解。2.2对偶性质对偶性质Dualproperty对偶理论对偶理论制作与教学【解】对偶问题是【解】对偶问题是因因为为X10，X20，所所以以对对偶偶问问题题的的第第一一、二个约束的松弛变量等于零，即二个约束的松弛变量等于零，即解解此此线线性性方方程程组组得得y1=1,y2=1,从从而而对对偶偶问问题题的的最最优优解解为为Y=（1，1），最优值），最优值w=26。2.2对偶性质对偶性

28、质Dualproperty对偶理论对偶理论制作与教学【例【例2.6】已知线性规划已知线性规划的的对对偶偶问问题题的的最最优优解解为为Y=（0，2），求求原原问问题题的的最最优解。优解。【解】对偶问题是【解】对偶问题是2.2对偶性质对偶性质Dualproperty对偶理论对偶理论制作与教学解方程组得：解方程组得：x1=5,x3=1,所以原问题的最优解为所以原问题的最优解为X=（5，0，1），最优值），最优值Z=12。因为因为y20，所以原问题第二个松弛变量，所以原问题第二个松弛变量=0，则，则y1=0、y2=2知，松弛变量知，松弛变量故故x2=0，则，则原问题的约束条件为线性方程组：原问题的约束

29、条件为线性方程组：2.2对偶性质对偶性质Dualproperty对偶理论对偶理论制作与教学【例【例2.7】证明下列线性规划无最优解：证明下列线性规划无最优解：【证证】容容易易看看出出X=（4，0，0）是是一一可可行行解解，故故问问题题可可行行。对对偶问题偶问题将三个约束的两端分别相加得将三个约束的两端分别相加得而第二个约束有而第二个约束有y21，矛盾，故对偶问，矛盾，故对偶问题无可行解，题无可行解，因而原问题具有无界因而原问题具有无界解，即无最优解。解，即无最优解。2.2对偶性质对偶性质Dualproperty对偶理论对偶理论制作与教学【性性质质6】LP(max)的的检检验验数数的的相相反反数

30、数对对应应于于DP(min)的一组基本解的一组基本解.其其中中第第j个个决决策策变变量量xj的的检检验验数数的的相相反反数数对对应应于于（DP）中中第第j个个松松弛弛变变量量的的解解，第第i个个松松弛弛变变量量的的检检验验数数的的相相反反数数对对应应于于第第i个个对对偶偶变变量量yi的的解解。反反之之，（DP）的的检检验验数数（注注意意：不不乘乘负负号号）对应于（对应于（LP）的一组基本解。）的一组基本解。证明略。证明略。2.2对偶性质对偶性质Dualproperty对偶理论对偶理论制作与教学【例【例2.8】线性规划线性规划（1）用单纯形法求最优解；）用单纯形法求最优解；（2）写出每步迭代对应

31、对偶问题的基本解；）写出每步迭代对应对偶问题的基本解；（3）从最优表中写出对偶问题的最优解；）从最优表中写出对偶问题的最优解；（4）用公式）用公式Y=CBB-1求对偶问题的最优解。求对偶问题的最优解。【解】（【解】（1）加入松弛变量）加入松弛变量x4、x5后，单纯形迭代如表后，单纯形迭代如表2-2所示。所示。2.2对偶性质对偶性质Dualproperty对偶理论对偶理论制作与教学XBx1x2x3x4x5b表表（1）x4x5211024100124j62100表表（2）x1x5101/21/2131/21/20113j01530表表（3）x1x2100146011246j001122表表2-22

32、.2对偶性质对偶性质Dualproperty对偶理论对偶理论制作与教学最优解最优解X=（4，6，0），最优值），最优值Z=6426=12；（2）设设对对偶偶变变量量为为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）

33、，），则则Y（3）=（2，2，0，0，11）2.2对偶性质对偶性质Dualproperty对偶理论对偶理论制作与教学（3）因为表）因为表22（3）为最优解，故）为最优解，故Y（3）=（2，2，0，0，11）为对偶问题最优解；）为对偶问题最优解；（4）表）表22（3）中的最优基）中的最优基B-1为表为表22（3）中）中x4，x5两列的系数，即两列的系数，即CB=（6，2），因而），因而2.2对偶性质对偶性质Dualproperty对偶理论对偶理论制作与教学本节您学了六个对偶性质；这些性质是研究原问题与对偶问题解本节您学了六个对偶性质；这些性质是研究原问题与对偶问题解的对应关系；表的对应关系；表2

34、6也许对您了解这些性质有帮助。也许对您了解这些性质有帮助。表表26一个问题一个问题max另一个问题另一个问题min有最优解有最优解有最优解有最优解性质性质4无无无最优解无最优解无最优解无最优解性质性质4最最优优无界解无界解（有可行解）（有可行解）无可行解无可行解性质性质2解解无可行解无可行解无界解无界解（有可行解）（有可行解）应用应用已知最优解已知最优解通过解方程通过解方程求最优解求最优解性质性质5已知检验数已知检验数检验数乘以检验数乘以1求得基本解求得基本解性质性质62.2对偶性质对偶性质Dualproperty对偶理论对偶理论制作与教学影影子子价价格格(Shadowprice):原原始始线

35、线性性规规划划问问题题考考虑虑的的是是充充分分利利用用现现有有资资源源，以以产产品品的的数数量量和和单单位位产产品品的的收收益益来来决决定定企企业业的的总总收收益益，没没有有考考虑虑到到资资源源的的价价格格，但但实实际际在在构构成成产产品品的的收收益益中中，不不同同的的资资源源对对收收益益的的贡贡献献也也不不同同，它它是是企企业业生生产产过过程程中中一一种种隐隐含含的的潜潜在在价价值值，经经济济学学中中称称为为影影子子价价格格，即即对对偶偶问问题题中中的的决决策策变量变量yi的值。的值。2.2.2影子价格影子价格因为原问题和对偶问题的最优值相等，将线性规划的目标函数因为原问题和对偶问题的最优值

36、相等，将线性规划的目标函数表达成资源的函数，故有表达成资源的函数，故有即即yi是第是第i 种资源的变化率，说明当其它资源供应量种资源的变化率，说明当其它资源供应量bk(ki)不变不变时，时，bi增加一个单位时目标值增加一个单位时目标值Z增加增加yi个单位个单位2.2对偶性质对偶性质Dualproperty对偶理论对偶理论制作与教学在例在例2.8中，中，2.2对偶性质对偶性质DualpropertyY=（2，2，0，0，11）为对偶问题最优解）为对偶问题最优解第一种资源的影子价格为第一种资源的影子价格为y1=2，第二种资源的影子价格为，第二种资源的影子价格为y2=2，即当第一种资源增加一个单位时

37、，即当第一种资源增加一个单位时，Z增加增加2个单位，个单位，当第二种资源增加一个单位时，当第二种资源增加一个单位时，Z增加增加2个单位个单位对偶理论对偶理论制作与教学正确理解影子价格，利用影子价格作下列经济活动分析正确理解影子价格，利用影子价格作下列经济活动分析（1）调节生产规模例如，目标函数）调节生产规模例如，目标函数Z表示利润（或产值），表示利润（或产值），当第当第i种资源的影子价格大于零（或高于市场价格）时，表示有种资源的影子价格大于零（或高于市场价格）时，表示有利可图，企业应购进该资源扩大生产规模，当影子价格等于零利可图，企业应购进该资源扩大生产规模，当影子价格等于零（或低于市场价格）

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

39、量大于零时第i个对偶变量等于个对偶变量等于零，并不能说明该资源在生产过程中没有作出贡献，只能理解零，并不能说明该资源在生产过程中没有作出贡献，只能理解为第为第i种资源有剩余时再增加该资源量不能给企业带来利润或产种资源有剩余时再增加该资源量不能给企业带来利润或产值的增加值的增加2.2对偶性质对偶性质Dualproperty对偶理论对偶理论制作与教学例例如如，第第一一种种资资源源的的影影子子价价格格为为y1=2，第第二二种种资资源源的的影影子子价价格格为为y2=2，即即当当第第一一种种资资源源增增加加一一个个单单位位时时，Z增增加加2个个单单位位，当当第第二二种资源增加一个单位时，种资源增加一个单

40、位时，Z增加增加2个单位。个单位。企企业业可可利利用用影影子子价价格格调调节节生生产产规规模模。例例如如，目目标标函函数数Z表表示示利利润润（或或产产值值)，当当第第i种种资资源源的的影影子子价价格格大大于于零零(或或高高于于市市场场价价格格）时时，表表示示有有利利可可图图，企企业业应应购购进进该该资资源源扩扩大大生生产产规规模模，当当影影子子价价格格等等于于零零（或或低低于于市市场场价价格格），企企业业不不能能增增加加收收益益，这这时时应应将将资资源源卖卖掉掉或或出出让让，缩缩小小生生产产规规模模。应应当当注注意意，是是在在最最优优基基B不不变变的的条条件件下下有有上上述述经经济济含含义义，

41、当当某某种种资资源源增增加加或或减减少后，最优基少后，最优基B可能发生了变化，这时可能发生了变化，这时yi的值也随之变化。的值也随之变化。2.2对偶性质对偶性质Dualproperty对偶理论对偶理论制作与教学在例在例2.1中，原问题的最优解中，原问题的最优解X（24.24，0，46.96）对偶问题的最优解对偶问题的最优解Y（10.6，0.91，0，0）最优值最优值z=w=5712.12分析分析：1.y1=10.6说明在现有的资源限量的条件下，增加一个单位说明在现有的资源限量的条件下，增加一个单位第一种资源可以给企业带来第一种资源可以给企业带来10.6元的利润；如果要出售该资源，元的利润；如果

42、要出售该资源，其价格至少在成本价上加其价格至少在成本价上加10.6元。元。2.y3=0说明增加第三种资源不会增加利润，因为第三种资源还说明增加第三种资源不会增加利润，因为第三种资源还没有用完。没有用完。问题：问题：1.第三、四种资源的售价是多少，是否不值钱？第三、四种资源的售价是多少，是否不值钱？2.如果要增加利润，企业应增加哪几种资源，各增加多如果要增加利润，企业应增加哪几种资源，各增加多少后再进行调整？少后再进行调整？2.2对偶性质对偶性质Dualproperty对偶理论对偶理论制作与教学（4）影子价格是企业生产过程中资源的一种隐含的潜在价值，）影子价格是企业生产过程中资源的一种隐含的潜在

43、价值，表明单位资源的贡献，与市场价格是不同的两个概念同一种表明单位资源的贡献，与市场价格是不同的两个概念同一种资源在不同的企业、生产不同的产品或在不同时期影子价格都资源在不同的企业、生产不同的产品或在不同时期影子价格都不一样不一样例如，某种钢板市场价格是每吨例如，某种钢板市场价格是每吨8000元，一个企业用元，一个企业用来生产汽车，另一个企业用来生产空调外壳，每吨钢板的产值来生产汽车，另一个企业用来生产空调外壳，每吨钢板的产值是不一样的是不一样的（5）影子价格是一个变量由）影子价格是一个变量由的含义知影子价格是的含义知影子价格是一种边际产出，与一种边际产出，与bi的基数有关，在最优基的基数有关

44、，在最优基B不变的条件下不变的条件下yi不不变，当某种资源增加或减少后，最优基变，当某种资源增加或减少后，最优基B可能发生了变化，这可能发生了变化，这时时yi的值也随之发生变化的值也随之发生变化2.2对偶性质对偶性质Dualproperty对偶理论对偶理论制作与教学作业：教材作业：教材P62T3、4、52.2对偶性质对偶性质Dualproperty1.本节介绍的本节介绍的6个性质都是原问题与对偶问题的有关解的对应关个性质都是原问题与对偶问题的有关解的对应关系；系；2.性质性质5和性质和性质6可用来已知一个问题的最优解求另一个问题的最可用来已知一个问题的最优解求另一个问题的最优解；优解；3.第第

45、2章的大部分概念都集中在这一节。章的大部分概念都集中在这一节。下一节：对偶单纯形法下一节：对偶单纯形法4.深刻领会影子价格的含义，学会用影子价格作经济活动分析。深刻领会影子价格的含义，学会用影子价格作经济活动分析。2.3对偶单纯形法对偶单纯形法DualSimplexMethod对偶理论对偶理论制作与教学 单纯形表最优基必须同时满足两个条件右端列中的所有i0 可行性条件全部检验数j0 最优性条件（1）（2）对偶理论对偶理论制作与教学单纯形法的迭代过程单纯形法的迭代过程 i 0 j0 i0 j 0 i0 j0 对偶单纯形法的迭代过程对偶单纯形法的迭代过程 i0 j0 对偶理论对偶理论制作与教学设原

46、问题是（记为设原问题是（记为LP）：）：对偶问题是（记为对偶问题是（记为DP）：）：根根据据对对偶偶性性质质6，可可以以构构造造一一个个求求线线性性规规划划的的另另一一种种方方法法，即即对对偶单纯形法。偶单纯形法。对偶单纯形法的计算步骤：对偶单纯形法的计算步骤：对对偶偶单单纯纯形形法法的的条条件件是是：初初始始表表中中对对偶偶问问题题可可行行，即即极极大大化化问问题时题时j0，极小化问题时，极小化问题时j0。2.3对偶单纯形法对偶单纯形法DualSimplexMethod对偶理论对偶理论制作与教学(1)将将线线性性规规划划的的约约束束化化为为等等式式，求求出出一一组组基基本本解解，因因为为对对

47、偶偶问问题可行，即全部检验数题可行，即全部检验数j0（max）或或j0（min）,当当基基本本解解可可行行时时，则则达达到到最最优优解解；若基本解不可行，即有某个基变量的解若基本解不可行，即有某个基变量的解bi0，则进行换基计算；，则进行换基计算；(2)先确定出基变量。先确定出基变量。l 行对应的变量行对应的变量x出基；出基；(3)再选进基变量。求最小比值再选进基变量。求最小比值(4)求求新新的的基基本本解解，用用初初等等变变换换将将主主元元素素alk化化为为l,k列列其其它它元元素素化化为为零，得到新的基本解，转到第一步重复运算。零，得到新的基本解，转到第一步重复运算。2.3对偶单纯形法对偶

48、单纯形法DualSimplexMethod对偶理论对偶理论制作与教学【例【例2.9】用对偶单纯形法求解】用对偶单纯形法求解【解】先将约束不等式化为等式，再两边同乘以（【解】先将约束不等式化为等式，再两边同乘以（1），得到），得到x4、x5为基变量，用对偶单纯形法，迭代过程如表为基变量，用对偶单纯形法，迭代过程如表2-7所示。所示。2.3对偶单纯形法对偶单纯形法DualSimplexMethod对偶理论对偶理论制作与教学XBx1x2x3x4x5b表表(1)x4x5-1-1-11-14100153j41300表表（2）x2x51-21013-110158j30210表表（3）x2x101105/2

49、-3/2-1/2-1/21/21/214j0013/25/23/2表表2-72.3对偶单纯形法对偶单纯形法DualSimplexMethod最优解：最优解：X(4，1，0)T；Z=17对偶理论对偶理论制作与教学应当注意应当注意：（1）用用对对偶偶单单纯纯形形法法求求解解线线性性规规划划是是一一种种求求解解方方法法，而而不不是是去去求对偶问题的最优解；求对偶问题的最优解；（2）初初始始表表中中一一定定要要满满足足对对偶偶问问题题可可行行，也也就就是是说说检检验验数数满满足足最优判别准则；最优判别准则；（3）最小比值中）最小比值中的绝对值是使得比值非负，在极小的绝对值是使得比值非负，在极小化问题时

50、化问题时j0，分母，分母aij0这时必须取绝对值。在极大化这时必须取绝对值。在极大化问题中，问题中，j0分母分母aij0，总满足非负，这时绝对值总满足非负，这时绝对值符号不起作用，可以去掉。如在本例中将目标函数写成符号不起作用，可以去掉。如在本例中将目标函数写成这里这里j0在求在求k时就可以不带绝对值符号。时就可以不带绝对值符号。2.3对偶单纯形法对偶单纯形法DualSimplexMethod对偶理论对偶理论制作与教学（6）对偶单纯形法在确定出基变量时，若不遵循）对偶单纯形法在确定出基变量时，若不遵循 规则，任选一个小于零的规则，任选一个小于零的bi对应的基变量出基，不影响计算结果，对应的基变