运筹学对偶模型.PPT

1、1赵明霞赵明霞山西大学经济与管理学院山西大学经济与管理学院管理运筹学管理运筹学 模型与方法模型与方法2第第3 3章对偶模型章对偶模型3 3.1.1线性规划的对偶关系线性规划的对偶关系3 3.2.2线性规划的对偶性质线性规划的对偶性质3.33.3对偶单纯形法对偶单纯形法33.13.1线性规划的对偶关系线性规划的对偶关系对偶问题对偶问题例例1-1. 某工厂要安排甲、乙两种产品分别在车间某工厂要安排甲、乙两种产品分别在车间A、B生产，生产，然后都在然后都在C车间装配。生产数据如下表：车间装配。生产数据如下表：问题：工厂应分别生产多少单位甲、乙产品才能使工厂获利问题：工厂应分别生产多少单位甲、乙产品才

2、能使工厂获利最多？最多？4解：解：设设安排甲、乙两种产品产量分别为安排甲、乙两种产品产量分别为x xj j 件件 max z=3x max z=3x1 1+ 2x+ 2x2 2 s.t. x s.t. x1 1 6 6 2x 2x2 28 8 2x2x1 1+3x+3x2 21818 x xj j0 0 （j=1,2j=1,2）22,)26(*zXT，5例例3-3-1 1. . 将例将例1-11-1中三种资源用于对外加工，如何给资源定价？中三种资源用于对外加工，如何给资源定价？解：解：设设三种资源分别可获利润为三种资源分别可获利润为yj j (100 (100元元/ /工时工时) ) m mi

3、nin w w = = 6y 6y1 1 + +8y8y2 2 + +18y18y3 3 s.t. s.t. y y1 1 + +2y2y3 3 33 2 2y y2 2+ +3y3y3 3 2 2 y yj j0 0 （j=1,2j=1,2,3,3）22,)3/203/5(*wYT，6对偶关系对偶关系规范对偶关系（对称对偶）规范对偶关系（对称对偶）标准形标准形LPLP对偶关系（非对称对偶）对偶关系（非对称对偶）一般对偶关系（混合对偶）一般对偶关系（混合对偶）7规范对偶关系（对称对偶）规范对偶关系（对称对偶）其中：其中： C= C=（c c1 1，c c2 2, , ,c ,cn n) )T

4、T b= b=（b b1 1，b b2 2, , ,b ,bm m) )T T X= X=（x x1 1，x x2 2, , ,x ,xn n) )T T Y= Y=（y y1 1，y y2 2, , ,y ,ym m) )T T z= 2 xz= 2 x1 1 + x + x2 2 5 5x x2 2 15 156 6x x1 1 + 2x + 2x2 2 24 24x x1 1 + x + x2 2 5 5x x1 1，x x2 2 0 0st .st .6 6y y2 2 + y + y3 32 25 5y y1 1 + 2y + 2y2 2 + y + y3 31 1z= 15yz=

5、15y1 1 + 24y + 24y2 2 + 5y+ 5y3 3minminy y1 1 , y , y2 2 , y , y3 30 0st .st .X 0st.AX bmax z = CTXY 0st.ATY Cmin w = bTYP57表表3-2，38例例3-23-2标准形标准形LPLP对偶关系（非对称对偶）对偶关系（非对称对偶）X X 0 0st.st.AX AX = = b bmax z =max z = C CT TX XY Y 自由自由st.st.A AT TY CY Cmin w =min w = b bT TY Y w w= = 5y5y1 1 + + 6y6y2 2

6、2y2y1 1 +3y +3y2 2 5 5y y1 1 + 2 + 2y y2 2 1 13y3y1 1 + + y y2 2 2 2st .st .x x2 2 + + 3x3x3 3= =5 53x3x1 1 + 2 + 2x x2 2 + + x x3 36 6= =z= 5z= 5x x1 1 + + x x2 2 + + 2x2x3 3m maxaxx x1 1 , , x x2 2 , , x x3 30 0st .st .2x1 +P58表表3-49一般对偶关系（混合对偶）一般对偶关系（混合对偶）例例3-312341234123123124min2343252231. .322

7、0,0,0wxxxxxxxxxxxstxxxxxxx x1 1 0, x 0, x2 2 0, x 0, x3 3无约束无约束 st.st.a a1111x x1 1+a+a1212x x2 2+a+a1313x x3 3 b b1 1a a2121x x1 1+a+a2222x x2 2+a+a2323x x3 3 = b = b2 2a a3131x x1 1+a+a3232x x2 2+a+a3333x x3 3 b b3 3max z = cmax z = c1 1x x1 1 + c + c2 2x x2 2 +c +c3 3x x3 3 min w = bmin w = b1 1y

8、 y1 1 + b + b2 2y y2 2 + b + b3 3y y3 3a a1111y y1 1 + + a a2121y y2 2 + a+ a3131y y3 3 c c1 1a a1212y y1 1 + + a a2222y y2 2 + a + a3232y y3 3 c c2 2a a1313y y1 1 + + a a2323y y2 2 + a+ a3333y y3 3 = c = c3 3st.st.y y1 10, y0, y2 2无约束无约束，y y3 3 00对偶规则对偶规则 变量、约束与系数变量、约束与系数&原问题原问题有有m个约束条件，个约束条件，对偶问题对

9、偶问题有有m个变量个变量&原问题原问题的规范约束（的规范约束（max,或或min，）对应）对应对偶问题对偶问题的变量的变量0；&原原问题问题的非规范的非规范约束（约束（max,或或min，）对应）对应对偶问题对偶问题的的变量变量0；&原问题原问题的等式约束的等式约束（max,=或或min，=）对应对应对偶问题对偶问题的的变量无限制。变量无限制。&原问题原问题有有n个变量，个变量，对偶问题对偶问题有有n个约束条件个约束条件&原问题原问题的价值系数对应的价值系数对应对偶问题对偶问题的右端项的右端项&原问题原问题的右端项对应的右端项对应对偶问题对偶问题的价值系数的价值系数&原问题原问题的系数矩阵转置

10、后为的系数矩阵转置后为对偶问题对偶问题系数矩阵系数矩阵P59表表3-511123 3.2 .2线性规划的对偶性质线性规划的对偶性质11.对称性对称性：对偶问题的对偶问题是原问题。：对偶问题的对偶问题是原问题。12.弱对偶性弱对偶性：原问题的任一可行解的目标函数值，不优于其：原问题的任一可行解的目标函数值，不优于其对偶问题任一可行解的目标函数值对偶问题任一可行解的目标函数值13.最优性最优性： ,则则 分别为原问题与对偶问题的最优分别为原问题与对偶问题的最优解。解。bTTC XY,X YbTTzC XYw最优解最优解PD1314.强对偶性强对偶性：若一个问题有最优解，则另一问题也有最优解，：若一

11、个问题有最优解，则另一问题也有最优解，且二者最优目标值相等。且二者最优目标值相等。 无界性无界性：若一个问题有无界解，则另一问题无可行解。：若一个问题有无界解，则另一问题无可行解。对偶定理对偶定理：要么同时有解，且最优值相等；要么同时无解。：要么同时有解，且最优值相等；要么同时无解。 不可能一个有解，一个无解。不可能一个有解，一个无解。无界解无可行解1415.互补性互补性：原问题与对偶问题的变量或基本解之间具有互补性。：原问题与对偶问题的变量或基本解之间具有互补性。 互补变量互补变量 互补基本解互补基本解：目标值相等：目标值相等,(1,2, ),(1,2, )Sjm jSin iXYxyjnY

12、Xyxim或或决策变量非决策变量基变量非基变量P1与与D1互相对偶互相对偶PS与与DS广义对偶广义对偶1516.兼容性兼容性：原问题：原问题PS单纯形表的检验行，对应对偶问题单纯形表的检验行，对应对偶问题DS的一的一个基本解；最优单纯形表的检验行，对应对偶问题的最优解。个基本解；最优单纯形表的检验行，对应对偶问题的最优解。检验行基本解互补基本解均可行必然均为最优解。互补基本解均可行必然均为最优解。16171817.基本松紧性基本松紧性：互补变量满足：互补变量满足 对于非退化的基本解对于非退化的基本解u若若X可行，则有可行，则有u若若Y可行，则有可行，则有18.最优松紧性最优松紧性：这些性质同样

13、适用于非对称形问题这些性质同样适用于非对称形问题0, (1,2, )0, (1,2,)jmjn iix yjnxyim00,(1,2, )00, (1,2,)jmjn iixyjnxyim00,(1,2, )00, (1,2,)mjjin iyxjnyxim*100,20=0(1,2, )300,400, (1,2,)jm jm jjn iiin ixyyxjnxyyxim（）（ ），（ ）（ ）19对偶变量的经济属性对偶变量的经济属性11nmjjiijizc xb ywiizyb*1=,TimYyyyp 是第是第i种资源的种资源的边际价值边际价值p 是第是第i种资源的种资源的影子价值影子价值

14、（shadow value） 单位产值（收入），单位产值（收入）， 影子价格影子价格； 单位利润，单位利润， 影子利润影子利润。p 的值相当于在资源得到最优利用的生产条件下，的值相当于在资源得到最优利用的生产条件下，bi每增加一个单位时目标函数每增加一个单位时目标函数z z的贡献（增量）的贡献（增量）。*iyiyjc*iyjc*iy*iy22,)26(*zXT，22,)3/203/5(*wYT，20对资源对资源i现用总量的经济分析现用总量的经济分析 代表影子价格代表影子价格 ，可增加资源，可增加资源i的用量，可买进资源，对总目标贡献的用量，可买进资源，对总目标贡献 ； ，可买进资源，对总目标贡

15、献，可买进资源，对总目标贡献 ； ，应减少资源，应减少资源i的用量，可卖出资源，对总目标贡献的用量，可卖出资源，对总目标贡献 。 代表影子利润代表影子利润资源资源i单位成本单位成本 ，则资源，则资源i对总价值的单位贡献即对总价值的单位贡献即 ，即，即 为资源为资源i的影子价格。的影子价格。对资源对资源i分配方案分配方案的经济分析的经济分析*iiyp*0iiyp*=iiyp*=0iiyp*iiyp*iy*iyiq*-0iip y *iiyq*iiyq21对偶问题的经济意义对偶问题的经济意义(3-12b)：资源：资源aji对总价值的贡献，应当不少于将其用于项目对总价值的贡献，应当不少于将其用于项目

16、j时时的贡献的贡献cj; ;(3-12c)：资源：资源i对总价值的贡献必须非负，否则不用或出售。对总价值的贡献必须非负，否则不用或出售。(3-12a)：资源隐性价值：资源隐性价值w，确定转让的成交价格最低限度，确定转让的成交价格最低限度yi。111): min(3 12 )(1,2, )(3 12 ). .0(1,2,)(3 12 )miiimjiijiiDwb yaa ycjnbstyimc（最优松紧性的经济意义最优松紧性的经济意义每经营一个单位项目每经营一个单位项目xj所消耗的各种资源的影子价值总和，必所消耗的各种资源的影子价值总和，必定等于该项目创造的单位价值定等于该项目创造的单位价值c

17、j。*11008 1jm jmmjiijijiimjjixya yca yyc（）*14*13413600522322*333xyyyyyy23*42*23535400223233*023xyyyyyy当资源当资源i的供量未被耗尽时，该资源的边际价值必为的供量未被耗尽时，该资源的边际价值必为0。*8 400n iixy（ ）*8 200m jjyx（ ）*8 300in iyx（ ）24最优性检验的经济意义最优性检验的经济意义 是决策变量，说明该资源的影是决策变量，说明该资源的影子利润为负，需要改善。子利润为负，需要改善。 是剩余变量是剩余变量 说明该资源的影子利润小于项目说明该资源的影子利润

18、小于项目j的单位利润的单位利润cj，需要改善。，需要改善。0,n iiiyy0,jmjmjyy11mjiimjjimjiijia yyca yc25互补基本解均可行必然均为最优解。互补基本解均可行必然均为最优解。对偶单纯形法基本思路对偶单纯形法基本思路1 1、标准化，、标准化，允许允许bi0;0;2 2、建立典式，、建立典式，若若 ，转至，转至3 3；3 3、最优性检验、最优性检验 ，否则转至，否则转至4 4；4 4、解的判断、解的判断 原问题无可行解，对偶问题无下界；原问题无可行解，对偶问题无下界；否则，否则， 转至转至5 5 ；5 5、换基；、换基；先确定出基变量先确定出基变量 后确定入基变量后确定入基变量 主元为负数主元为负数 3 3.3 .3对偶单纯形法对偶单纯形法00b 0,0,ssjbamin0iilb bbmax/0/jljljklka aa2627例例3-428前提条件前提条件进化进化换基换基主元主元原原SM先入先入后出后出 正正数数对偶对偶SM先出先出后入后入 负负数数0000bb0b 0min0iilb bbmax/0/jljljklka aamin0jjk min0ilikiklkbbaaa原本、对偶单纯形法对比原本、对偶单纯形法对比29交替单纯形法交替单纯形法无须顾及二者的