大学精品课件：2对偶理论.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 LP 在线性规划问题中，存在一个有趣的问题，即每一个线性规在线性规划问题中，存在

2、一个有趣的问题，即每一个线性规划问题都伴随有另一个线性规划问题，称它为对偶线性规划问划问题都伴随有另一个线性规划问题，称它为对偶线性规划问题。题。【例例2.1】某企业用四种资源生产三种产品，工艺系数、资源限量某企业用四种资源生产三种产品，工艺系数、资源限量及价值系数如下表：及价值系数如下表：建立总收益最大的数学模型。建立总收益最大的数学模型。产品产品资源资源A B C资源限量资源限量9 8 65005 4 74508 3 23007 6 4550单件产品利润单件产品利润100 80 702.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LP【解解】设设x1，x2，x3分

3、别为产品分别为产品A，B，C的产量，则线性规划数的产量，则线性规划数学模型为：学模型为：0,5504673002384507455006897080100max3,21321321321321321xxxxxxxxxxxxxxxxxxZ 现在从另一个角度来考虑企业的决策问题。假如企业自己不现在从另一个角度来考虑企业的决策问题。假如企业自己不生产产品，而将现有的资源转让或出租给其它企业，那么资源生产产品，而将现有的资源转让或出租给其它企业，那么资源的转让价格是多少才合理？合理的价格应是对方用最少的资金的转让价格是多少才合理？合理的价格应是对方用最少的资金购买本企业的全部资源，而本企业所获得的利润

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

5、7个单位，利润是个单位，利润是100,企业出售这些数量的资源所企业出售这些数量的资源所得的利润不能少于得的利润不能少于100，即，即10078594321yyyy同理，对产品同理，对产品B和和C有有70427680634843214321yyyyyyyy价格不可能小于零，即有价格不可能小于零，即有yi0,i=1,4.从而企业的资源从而企业的资源价格模型为价格模型为2.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LP4,1,07042768063481007859550300450500min4321432143214321iyyyyyyyyyyyyyyyyywi这是一

6、个线性规划数学模型，称这一线性规划模型是前这是一个线性规划数学模型，称这一线性规划模型是前面生产计划模型的对偶线性规划模型面生产计划模型的对偶线性规划模型,这一问题称为对偶这一问题称为对偶问题。生产计划的线性规划问题称为原始线性规划问题问题。生产计划的线性规划问题称为原始线性规划问题或原问题。或原问题。2.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LP上面两种形式的线性规划称为规范形式。上面两种形式的线性规划称为规范形式。原问题和对偶问题是互为对偶的两个线性规划问题，已知一个问原问题和对偶问题是互为对偶的两个线性规划问题，已知一个问题就可写出另一个问题。题就可写出另

7、一个问题。规范形式规范形式（Canonical Form）的定义：的定义：目标函数求极大值时，所有约束条件目标函数求极大值时，所有约束条件为为号号，变量非负变量非负；目标函数求极小值时，所有约束条件目标函数求极小值时，所有约束条件为为号号，变量非负变量非负。规范形式的线性规划的对偶问题亦是规范形式。规范形式的线性规划的对偶问题亦是规范形式。以上是依据经济问题推导出对偶问题，还可以用代数方法以上是依据经济问题推导出对偶问题，还可以用代数方法推导出对偶问题。推导出对偶问题。2.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LP0)1.2(maxXbAXCXZ0)2.2(mi

8、nXbAXCXZ0,0maxSNBSNBSNNBBXXXbEXNXBXXXCXCZXBXNXSbXBBNEbCCBCN00XBXNXSbXBEB1NB1B1b0CNCBB1NCBB1CBB1b表表2-2表表232.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LP设线性规划模型是式（设线性规划模型是式（2.1）的规范形式由表）的规范形式由表2-3知，当检验数知，当检验数0011BCABCCBB时得到最优解时得到最优解，是是 的检验数的检验数,和和 ,令令 ,由由 得得ABCCB1），（NBXXXBBCCBB1NBCCBN11BCYB0011BCABCCBB与0YCYA在

9、在 两边有乘两边有乘b,则有则有 ,又因又因Y0无上界无上界,从从而只存在最小值，得到另一个线性规划问题而只存在最小值，得到另一个线性规划问题1BCYBZbBCYbB12.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LP0minYCYAYbw即是原线性规划问题式（即是原线性规划问题式（2.1）的对偶线性规划问题，反之，式）的对偶线性规划问题，反之，式（2.3）的对偶问题是式（）的对偶问题是式（2.1）原问题和对偶问题是互为对偶）原问题和对偶问题是互为对偶的两个线性规划问题，规范形式的线性规划的对偶仍然是规范的两个线性规划问题，规范形式的线性规划的对偶仍然是规范形式，参

10、数矩阵的对应关系参看表形式，参数矩阵的对应关系参看表2-4因此已知一个规范形式因此已知一个规范形式问题就可写出另一个对偶问题问题就可写出另一个对偶问题2.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LP【例例2.2】写出下列线性规划的对偶问题写出下列线性规划的对偶问题0,15744325min321321321321xxxxxxxxxxxxZ【解解】这是一个规范形式的线性规划，设这是一个规范形式的线性规划，设Y=（y1，y2），），则有则有)3,2,5()57,4(571114),(414),(max212121212121yyyyyyyyYAyyyyYbw，2.1

11、线性规划的对偶模型线性规划的对偶模型 Dual model of LP从而对偶问题为从而对偶问题为0,03527544max2121212121yyyyyyyyyyZ对偶变量对偶变量yi也可写成也可写成xi的形式。的形式。)3,2,5()57,4(571114),(414),(max212121212121yyyyyyyyYAyyyyYbw，2.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LP【例例2.3】写出下列线性规划的对偶问题写出下列线性规划的对偶问题0,01038576534max2121212121xxxxxxxxxxZ【解解】这是一个规范形式的线性规划，它

12、的对偶问题求这是一个规范形式的线性规划，它的对偶问题求最小值，有三个变量且非负，有两个最小值，有三个变量且非负，有两个“”约束，即约束，即3,2,1,03324751086min321321321iyyyyyyyyyywi2.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LP若给出的线性规划不是规范形式，可以先化成规范形式再写对若给出的线性规划不是规范形式，可以先化成规范形式再写对偶问题。也可直接按表偶问题。也可直接按表2-1中的对应关系写出非规范形式的对偶中的对应关系写出非规范形式的对偶问题。问题。将上述原问题与对偶问题的对应关系列于表将上述原问题与对偶问题的对应关系

13、列于表2-1例如，原问题是求最小值，按表例如，原问题是求最小值，按表2-1有下列关系：有下列关系：1.第第i个约束是个约束是“”约束时，第约束时，第i个对偶变量个对偶变量yj0 2第第i个约束是个约束是“=”约束时，第约束时，第i个对偶变量个对偶变量yi无约束；无约束；3当当xj0时，第时，第j个对偶约束为个对偶约束为“”约束，当约束，当xj无约束时无约束时，第，第j个对偶约束为个对偶约束为“=”约束。约束。2.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LP原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数max目标函数

14、系数（资源限量）目标函数系数（资源限量）约束条件系数矩阵约束条件系数矩阵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-42.1 线性规划的对偶模型线性规划

15、的对偶模型 Dual model of LP【例例2.4】写出下列线性规划的对偶问题写出下列线性规划的对偶问题 0,0,1482105618827945min43213214243214321xxxxxxxxxxxxxxxxxZ无约束【解解】目标函数求最小值，应将目标函数求最小值，应将表表24的右边看作原问题，左边的右边看作原问题，左边是对偶问题，原问题有是对偶问题，原问题有3个约束个约束4个变量，则对偶问题有个变量，则对偶问题有3 个变量个变量4个约束，对照表个约束，对照表21的对应关系，的对应关系，对偶问题为：对偶问题为：123131231312max1810147226885wyyyyy

16、yyyyyyy2.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LP=1549y10，y20，y3无约束1.本节本节以实例引出对偶问题以实例引出对偶问题;2.介绍了如何写规范与非规范问题的对偶问题介绍了如何写规范与非规范问题的对偶问题;3.深刻领会影子价格的含义，学会用影子价格作经济活动分析。深刻领会影子价格的含义，学会用影子价格作经济活动分析。作业：教材作业：教材P61 T 1、22.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LP下一节：对偶性质下一节：对偶性质2.2 对偶性质对偶性质Dual property 0maxXbAXCXZ对偶问

17、题是（记为对偶问题是（记为DP）：）：0minYCYAYbw这里这里A是是mn矩阵矩阵X是是n1列向量，列向量，Y是是1m行向量。假设行向量。假设Xs与与Ys分别是（分别是（LP）与（与（DP）的松驰变量。的松驰变量。【性质性质1】对称性对称性 对偶问题的对偶是原问题。对偶问题的对偶是原问题。【证证】设原问题是设原问题是0,maxXbAXCXZ设原问题是（记为设原问题是（记为LP）：）：2.2 对偶性质对偶性质Dual property2.2.1 对偶性质对偶性质0,minYCYAYbw它与下列线性规划问题是等价的：它与下列线性规划问题是等价的：0,)max(YCYAYbw再写出它的对偶问题。

18、再写出它的对偶问题。0,minXbAXCXw它与下列线性规划问题是等价的它与下列线性规划问题是等价的0,maxXbAXCXZ即是原问题。即是原问题。由表由表2-4知，它的对偶问题是知，它的对偶问题是2.2 对偶性质对偶性质Dual property【证证】因为因为X、Y是可行解，故有是可行解，故有AXb,X0及及YAC，Y0,将不等式将不等式 AXb【性质性质2】弱对偶性弱对偶性 设设X、Y分别为分别为LP(max)与与DP(min)的可行解，则的可行解，则 bYCX00两边左乘两边左乘Y，得，得Y0AXY0b再将不等式再将不等式YAC两边右乘两边右乘X，得，得C XYAX故故 C XYAXY

19、b这一性质说明了两个线性规划互为对偶时，求最大值的这一性质说明了两个线性规划互为对偶时，求最大值的线性规划的任意目标值都不会大于求最小值的线性规划线性规划的任意目标值都不会大于求最小值的线性规划的任一目标值，不能理解为原问题的目标值不超过对偶的任一目标值，不能理解为原问题的目标值不超过对偶问题的目标值。问题的目标值。2.2 对偶性质对偶性质Dual property由这个性质可得到下面几个结论：由这个性质可得到下面几个结论：（1）（）（LP）的任一可行解的目标值是（的任一可行解的目标值是（DP）的最优值下界；的最优值下界；（DP）的任一可行解的目标是（的任一可行解的目标是（LP）的最优值的上界

20、；的最优值的上界；（2）在互为对偶的两个问题中，若一个问题可行且具有无界解，）在互为对偶的两个问题中，若一个问题可行且具有无界解，则另一个问题无可行解；则另一个问题无可行解；(3)若原问题可行且另一个问题不可行，则原问题具有无界解。若原问题可行且另一个问题不可行，则原问题具有无界解。注意上述结论（注意上述结论（2）及（）及（3）的条件不能少。一个问题有可行解时，）的条件不能少。一个问题有可行解时，另一个问题可能有可行解（此时具有无界解）也可能无可行解。另一个问题可能有可行解（此时具有无界解）也可能无可行解。2.2 对偶性质对偶性质Dual property例如：例如：0,22212min212

21、12121xxxxxxxxz无可行解，而对偶问题无可行解，而对偶问题0,221122max21212121yyyyyyyyw有可行解，由结论（有可行解，由结论（3）知必有无界解。）知必有无界解。2.2 对偶性质对偶性质Dual property【性质性质3】最优准则定理最优准则定理 设设X0与与Y0分别是（分别是（LP）与（与（DP）的的可行解，则当可行解，则当X0、Y0是（是（LP）与（与（DP）的最优解当且仅当的最优解当且仅当C X0=Y0b.【证证】若若X0、Y0为最优解，为最优解，B为（为（LP）的最优基，则有的最优基，则有Y0=CBB1，并且并且bYbBCCXB010当当C X0=Y

22、0b时，由性质时，由性质1，对任意可行解，对任意可行解 有有YX及bYCXbYXC00即即Y0b是（是（DP）中任一可行解的目标值的下界，中任一可行解的目标值的下界，C X0是（是（LP）中中任一可行解的目标值的上界，从而任一可行解的目标值的上界，从而X0、Y0是最优解。是最优解。2.2 对偶性质对偶性质Dual property【性质性质4】若互为对偶的两个问题其中一个有最优解，则另一若互为对偶的两个问题其中一个有最优解，则另一个也有最优解，且最优值相同。个也有最优解，且最优值相同。【证证】设（设（LP）有最优解有最优解X0,那么对于最优基那么对于最优基B必有必有C-CBB-1A0与与CBB

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

24、，则是它的松弛变量的可行解，则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 对偶性质对偶性质Dual property显然有显然有 Y0XS=YS X0又因为又因为Y、Xs、Ys、X0，所以有所以有YXS=0和和YS X=0成立。成立。反之，反之，当当YXS=0和和YS X=0时，有时，有YA X

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

26、式等于零，则必定每一分量为零，因而有下列关系：因而有下列关系：2.2 对偶性质对偶性质Dual property(1)当yi*0时，,反之当 时yi*=0；0iSx0iSx*(2)00,00jjSjjSyxxy时反之当时利用上述关系，建立对偶问题（或原问题）的约束线性方程组，利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。方程组的解即为最优解。性质性质5的结论和证明都是假定（的结论和证明都是假定（P）与（与（D）为对称形式，事实为对称形式，事实上对于非对称形式，性质上对于非对称形式，性质5的结论仍然有效。的结论仍然有效。【例例2.5】已知线性规划已知线性规划3,2

27、,1,0162210243max321321321jxxxxxxxxxxzj的最优解是的最优解是 求对偶问题的最优解。求对偶问题的最优解。TX)0,2,6(2.2 对偶性质对偶性质Dual property【解解】对偶问题是对偶问题是0,1422321610min2121212121yyyyyyyyyyw因为因为X10，X20，所以对偶问题的第一、所以对偶问题的第一、二个约束的松弛变量等于零，即二个约束的松弛变量等于零，即422322121yyyy解此线性方程组得解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为从而对偶问题的最优解为Y=（1，1），），最优值最优值w=26。2.2 对

28、偶性质对偶性质Dual property【例例2.6】已知线性规划已知线性规划 无约束321321321321,0,06422minxxxxxxxxxxxxz的对偶问题的最优解为的对偶问题的最优解为Y=（0，2），），求原问题的最求原问题的最优解。优解。【解解】对偶问题是对偶问题是021264max2121212121yyyyyyyyyyw无约，2.2 对偶性质对偶性质Dual property解方程组得：解方程组得：x 1=5,x 3=1,所以原问题的最优解为所以原问题的最优解为X=（5，0，1），），最优值最优值Z=12。643131xxxx因为因为y20，所以原问题第二个松弛变量所以原问

29、题第二个松弛变量 =0，则，则y1=0、y2=2知，松弛变量知，松弛变量 故故x2=0，则原问题的约束条件为线性方程组：则原问题的约束条件为线性方程组：,1,021SSyy2Sx2.2 对偶性质对偶性质Dual property【例例2.7】证明下列线性规划无最优解：证明下列线性规划无最优解：3,2,1,0324min32131321jxxxxxxxxxZj【证证】容易看出容易看出X=（4，0，0）是一可行解，故问题可行。对是一可行解，故问题可行。对偶问题偶问题0,0121134max212122121yyyyyyyyyw将三个约束的两端分别相加得将三个约束的两端分别相加得而第二个约束有而第二

30、个约束有y21，矛盾，故对偶问矛盾，故对偶问题无可行解，题无可行解，因而原问题具有无界因而原问题具有无界解，即无最优解。解，即无最优解。212y2.2 对偶性质对偶性质Dual property【性质性质6】LP(max)的检验数的相反数对应于的检验数的相反数对应于DP(min)的一组基本解的一组基本解.其中第其中第j个决策变量个决策变量xj的检验数的相反数对应于（的检验数的相反数对应于（DP）中第中第j个松弛变量个松弛变量 的解，第的解，第i个松弛变量个松弛变量 的检验数的相反数对应于第的检验数的相反数对应于第i个对偶变量个对偶变量yi的解。反的解。反之，（之，（DP）的检验数（注意：不乘负

31、号）对应于的检验数（注意：不乘负号）对应于（LP）的一组基本解。的一组基本解。证明略。证明略。jSyiSx2.2 对偶性质对偶性质Dual property【例例2.8】线性规划线性规划0,442226max32131321321xxxxxxxxxxxz（1）用单纯形法求最优解；）用单纯形法求最优解；（2）写出每步迭代对应对偶问题的基本解；）写出每步迭代对应对偶问题的基本解；（3）从最优表中写出对偶问题的最优解；）从最优表中写出对偶问题的最优解；（4）用公式）用公式Y=CBB-1求对偶问题的最优解。求对偶问题的最优解。【解解】（1）加入松弛变量）加入松弛变量x4、x5后，单纯形迭代如表后，单纯

32、形迭代如表2-2所示。所示。2.2 对偶性质对偶性质Dual propertyXBx1x2x3x4x5b表表（1）x4x5211024100124j62100表表（2）x1x5101/21/2131/21/20113j01530表表（3）x1x2100146011246j001122表表2-22.2 对偶性质对偶性质Dual property最优解最优解X=（4，6，0），），最优值最优值Z=6426=12；（2）设对偶变量为）设对偶变量为y1、y2,松弛变量为松弛变量为y3、y4、y5,Y=（y1、y2、y3、y4、y5），），由性质由性质6得到对偶问题的基本解得到对偶问题的基本解 （y1、

33、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 property（3）因为表）因为表22（3）为最优解，故）为最优解，故 Y（3）=（2，2，0，0，11）为对偶问题最优解；为对偶问题最优解；（4）表）表22（3）中的最优基）中的最优基 B-1 为表为表22（3）中）中x4，x 5两列的系

34、数，即两列的系数，即0211BCB=（6，2），），因而因而21101B)2,2(2110)2,6(),(121BCyyYB2.2 对偶性质对偶性质Dual property本节您学了六个对偶性质；这些性质是研究原问题与对偶问题解本节您学了六个对偶性质；这些性质是研究原问题与对偶问题解的对应关系；表的对应关系；表26也许对您了解这些性质有帮助。也许对您了解这些性质有帮助。表表26一个问题一个问题max另一个问题另一个问题min有最优解有最优解有最优解有最优解性质性质4无无无最优解无最优解无最优解无最优解性质性质4最最优优无界解无界解（有可行解）（有可行解）无可行解无可行解性质性质2解解无可行解

35、无可行解无界解无界解（有可行解）（有可行解）应用应用已知最优解已知最优解通过解方程通过解方程求求最优解最优解性质性质5已知检验数已知检验数检验数乘以检验数乘以1求得基本解求得基本解性质性质62.2 对偶性质对偶性质Dual property 影子价格影子价格(Shadow price):原始线性规划问题考虑的是充分原始线性规划问题考虑的是充分利用现有资源，以产品的数量和单位产品的收益来决定企业的利用现有资源，以产品的数量和单位产品的收益来决定企业的总收益，没有考虑到资源的价格，但实际在构成产品的收益中，总收益，没有考虑到资源的价格，但实际在构成产品的收益中，不同的资源对收益的贡献也不同，它是企

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

37、个单位时目标值Z增加增加yi个单位个单位2.2 对偶性质对偶性质Dual property在例在例2.8中，中，2.2 对偶性质对偶性质Dual property0,442226max32131321321xxxxxxxxxxxzY=（2，2，0，0，11）为对偶问题最优解为对偶问题最优解第一种资源的影子价格为第一种资源的影子价格为y1=2，第二种资源的影子价格为第二种资源的影子价格为y2=2，即当第一种资源增加一个单位时，即当第一种资源增加一个单位时，Z增加增加2个单位，个单位，当第二种资源增加一个单位时，当第二种资源增加一个单位时，Z增加增加2个单位个单位正确理解影子价格，利用影子价格作下

38、列经济活动分析正确理解影子价格，利用影子价格作下列经济活动分析（1）调节生产规模例如，目标函数）调节生产规模例如，目标函数Z表示利润（或产值），表示利润（或产值），当第当第i种资源的影子价格大于零（或高于市场价格）时，表示有种资源的影子价格大于零（或高于市场价格）时，表示有利可图，企业应购进该资源扩大生产规模，当影子价格等于零利可图，企业应购进该资源扩大生产规模，当影子价格等于零（或低于市场价格），企业不能增加收益，这时应将资源卖掉（或低于市场价格），企业不能增加收益，这时应将资源卖掉或出让，缩小生产规模或出让，缩小生产规模（2）生产要素对产出贡献的分解通过影子价格分析每种资源）生产要素对产出

39、贡献的分解通过影子价格分析每种资源获得多少产出例如，企业获得获得多少产出例如，企业获得100万元的利润，生产过程中产万元的利润，生产过程中产品的直接消耗的资源有材料品的直接消耗的资源有材料A、材料材料B、设备和工时，这些资源设备和工时，这些资源各产生多少利润，由影子价格可以大致估计出来各产生多少利润，由影子价格可以大致估计出来（3）由性质）由性质2.5知，第知，第i个松弛变量大于零时第个松弛变量大于零时第i个对偶变量等于个对偶变量等于零，并不能说明该资源在生产过程中没有作出贡献，只能理解零，并不能说明该资源在生产过程中没有作出贡献，只能理解为第为第i种资源有剩余时再增加该资源量不能给企业带来利

40、润或产种资源有剩余时再增加该资源量不能给企业带来利润或产值的增加值的增加2.2 对偶性质对偶性质Dual property例如，第一种资源的影子价格为例如，第一种资源的影子价格为y1=2，第二种资源的影子价格为第二种资源的影子价格为y2=2，即当第一种资源增加一个单位时，即当第一种资源增加一个单位时，Z增加增加2个单位，当第二个单位，当第二种资源增加一个单位时，种资源增加一个单位时，Z增加增加2个单位。个单位。企业可利用影子价格调节生产规模。例如，目标函数企业可利用影子价格调节生产规模。例如，目标函数Z表示表示利润（或产值利润（或产值)，当第，当第i种资源的影子价格大于零种资源的影子价格大于零

41、(或高于市场价或高于市场价格）时，表示有利可图，企业应购进该资源扩大生产规模，当格）时，表示有利可图，企业应购进该资源扩大生产规模，当影子价格等于零（或低于市场价格），企业不能增加收益，这影子价格等于零（或低于市场价格），企业不能增加收益，这时应将资源卖掉或出让，缩小生产规模。应当注意，时应将资源卖掉或出让，缩小生产规模。应当注意，是是在最优基在最优基B不变的条件下有上述经济含义，当某种资源增加或不变的条件下有上述经济含义，当某种资源增加或减少后，最优基减少后，最优基B可能发生了变化，这时可能发生了变化，这时yi的值也随之变化。的值也随之变化。iibZy2.1 线性规划的对偶模型线性规划的对偶

42、模型 Dual model of LP在例在例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元的利润；如果要出售该资源，元的利润；如果要出售该资源，其价格至少在成本价上加其价格至少在成本价上加10.6元。元。2.y3=0说明增加第三种资源不会增加利润，因为第三种资源说明增加第三种资源不会增加利润，因为第三

43、种资源还还 没有用完。没有用完。问题：问题：1.第三、四种资源的售价是多少，是否不值钱？第三、四种资源的售价是多少，是否不值钱？2.如果要增加利润，企业应增加哪几种资源，各增加多如果要增加利润，企业应增加哪几种资源，各增加多少后再进行调整？少后再进行调整？2.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LP（4）影子价格是企业生产过程中资源的一种隐含的潜在价值，）影子价格是企业生产过程中资源的一种隐含的潜在价值，表明单位资源的贡献，与市场价格是不同的两个概念同一种表明单位资源的贡献，与市场价格是不同的两个概念同一种资源在不同的企业、生产不同的产品或在不同时期影子价格都

44、资源在不同的企业、生产不同的产品或在不同时期影子价格都不一样不一样 例如，某种钢板市场价格是每吨例如，某种钢板市场价格是每吨8000元，一个企业元，一个企业用来生产汽车，另一个企业用来生产空调外壳，每吨钢板的产用来生产汽车，另一个企业用来生产空调外壳，每吨钢板的产值是不一样的值是不一样的（5）影子价格是一个变量由）影子价格是一个变量由 的含义知影子价格是的含义知影子价格是一种边际产出，与一种边际产出，与bi的基数有关，在最优基的基数有关，在最优基B不变的条件下不变的条件下yi不不变，当某种资源增加或减少后，最优基变，当某种资源增加或减少后，最优基B可能发生了变化，这可能发生了变化，这时时yi的

45、值也随之发生变化的值也随之发生变化iibZy2.2 对偶性质对偶性质Dual property作业：教材作业：教材P62 T3、4、5 2.2 对偶性质对偶性质Dual property1.本节介绍的本节介绍的6个性质都是原问题与对偶问题的有关解的对应关个性质都是原问题与对偶问题的有关解的对应关系；系；2.性质性质5和性质和性质6可用来已知一个问题的最优解求另一个问题的最可用来已知一个问题的最优解求另一个问题的最优解；优解；3.第第2章的大部分概念都集中在这一节。章的大部分概念都集中在这一节。下一节：对偶单纯形法下一节：对偶单纯形法2.3 对偶单纯形法对偶单纯形法Dual Simplex Me

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

47、对偶问将线性规划的约束化为等式，求出一组基本解，因为对偶问题可行，即全部检验数题可行，即全部检验数j0（max）或）或j0（min）,当基本解可行时，则达到最优解；当基本解可行时，则达到最优解；若基本解不可行，即有某个基变量的解若基本解不可行，即有某个基变量的解bi0，则进行换基计算；则进行换基计算；(2)先确定出基变量。先确定出基变量。l 行对应的变量行对应的变量x出出基；基；min|0liiibb b(3)再选进基变量。求最小比值再选进基变量。求最小比值0|minljljjjkaa(4)求新的基本解，用初等变换将主元素求新的基本解，用初等变换将主元素alk化为化为l,k列其它元素化为列其它

48、元素化为零，得到新的基本解，转到第一步重复运算。零，得到新的基本解，转到第一步重复运算。2.3 对偶单纯形法对偶单纯形法Dual Simplex Method【例例2.9】用对偶单纯形法求解用对偶单纯形法求解0,34534min321321321321xxxxxxxxxxxxz【解解】先将约束不等式化为等式，再两边同乘以（先将约束不等式化为等式，再两边同乘以（1），得到），得到5,2,1,034534min53214321321jxxxxxxxxxxxxzjx4、x5 为基变量，用对偶单纯形法，迭代过程如表为基变量，用对偶单纯形法，迭代过程如表2-7所示。所示。2.3 对偶单纯形法对偶单纯形法

49、Dual Simplex MethodXBx1x2x 3x 4x 5b表表(1)x 4x5-1-1-11-14100153j41300表表（2）x2x51-21013-110158j30210表表（3）x2x101105/2-3/2-1/2-1/21/21/214j0013/25/23/2表表2-72.3 对偶单纯形法对偶单纯形法Dual Simplex Method最优解：最优解：X(4，1，0)T；Z=17 应当注意应当注意：（1）用对偶单纯形法求解线性规划是一种求解方法，而不是去）用对偶单纯形法求解线性规划是一种求解方法，而不是去求对偶问题的最优解；求对偶问题的最优解；（2）初始表中一定

50、要满足对偶问题可行，也就是说检验数满足）初始表中一定要满足对偶问题可行，也就是说检验数满足最优判别准则；最优判别准则；（3）最小比值中）最小比值中 的绝对值是使得比值非负，在极小的绝对值是使得比值非负，在极小化问题时化问题时j0，分母分母aij0 这时必须取绝对值。在极大化这时必须取绝对值。在极大化问题中，问题中，j0分母分母aij0，总满足非负，这时绝对值总满足非负，这时绝对值符号不起作用，可以去掉。如在本例中将目标函数写成符号不起作用，可以去掉。如在本例中将目标函数写成ijjaijja这里这里j0在求在求k时就可以不带绝对值符号。时就可以不带绝对值符号。32134maxxxxz2.3 对偶