对偶问题及对偶单纯形法(完整)

第1页DualityTheory线性规划的对偶问题对偶问题的经济解释——影子价格对偶单纯形法第四章线性规划的对偶理论灵敏度分析对偶问题的基本性质第2页线性规划的对偶问题DualityTheory对偶问题的经济解释——影子价格对偶单纯形法灵敏度分析对偶问题的基本性质第四章线性规划的对偶理论第3页例如：平面中矩形的面积与周长的关系周长一定面积最大的矩形是正方形:面积一定周长最短的矩形是正方形一、对偶问题的提出对同一问题从不同角度考虑，有两种对立的描述。例1、应如何安排生产计划，使一天的总利润最大？某企业生产甲、乙两种产品，要用A、B、C三种不同的原料。每生产1吨甲产品，需耗用三种原料分别为1，1，0单位；生产1吨乙产品，需耗用三种原料分别为1，2，1单位。每天原料供应的能力分别为6，8，3单位。又知道每生产1吨甲产品企业利润为300元，每生产1吨乙产品企业利润为400元。386供应量34011211甲乙单位利润（百元）CBA原料产品386供应量34011211甲乙单位利润（百元）CBA原料产品第4页例1、应如何安排生产计划，使一天的总利润最大？maxx1≥0,x2≥0s.t.x1+x2≤6z=3x1+4x2x1+2x2≤8x2≤3386供应量34011211甲乙单位利润（百元）CBA原料产品386供应量34011211甲乙单位利润（百元）CBA原料产品设xj表示第j种产品每天的产量假设该企业决策者决定不生产甲、乙产品，而是将厂里的现有资源外售。决策者应怎样制定每种资源的收费标准才合理？第5页例1、应怎样制定收费标准才合理？386供应量34011211甲乙单位利润（百元）CBA原料产品386供应量34011211甲乙单位利润（百元）CBA原料产品设yj表示第j种原料的收费单价分析问题：1、出让每种资源的收入不能低于自己生产时的可获利润；2、定价不能太高，要使对方能够接受。把生产一吨甲产品所用的原料出让，所得净收入应不低于生产一吨甲产品的利润：乙产品同理：123yy12324yyy把企业所有原料出让的总收入：123683wyyy只能在满足≥所有产品的利润的条件下,其总收入尽可能少,才能成交.123min683wyyy12123123324,,0yyyyyyyys.t.第6页一、对偶问题的提出任何一个求极大的线性规划问题都有一个求极小的线性规划问题与之对应，反之亦然.把其中一个叫原问题，则另一个就叫做它的对偶问题，这一对互相联系的两个问题就称为一对对偶问题。12max34zxx12122126283,0xxxxxxxs.t.LP1123min683wyyy12123123324,,0yyyyyyyys.t.LP2原问题（P）对偶问题（D）第7页二、原问题与对偶问题的对应关系12max34zxx12122126283,0xxxxxxxs.t.P123min683wyyy12123123324,,0yyyyyyyys.t.Dyj表示对第j种资源的估价321yyy矩阵形式：12max(34)xzx12121161280130xxxxs.t.123min683ywyy123123110312140yyyyyys.t.maxz=CXs.t.AX≤bX≥0minw=bTYs.t.ATY≥CTY≥0第8页(一)对称型对偶问题其中yi≥0（i=1,2,…,m）称为对偶变量。变量均具有非负约束，且约束条件：当目标函数求极大时均取“≤”号，当目标函数求极小时均取“≥”号。maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2(P)……am1x1+am2x2+…+amnxn≤bmxj≥0（j=1,2,…,n）minw=b1y1+b2y2+…+bmyms.t.a11y1+a21y2+…+am1ym≥c1a12y1+a22y2+…+am2ym≥c2(D)……a1ny1+a2ny2+…+amnym≥cnyi≥0（i=1,2,…,m）maxz=CXs.t.AX≤bX≥0minw=bTYs.t.ATY≥CTY≥0第9页(二)非对称型对偶问题分析：化为对称形式。maxx1≥0,x2≤0,x3无约束s.t.a11x1+a12x2+a13x3≤b1z=c1x1+c2x2+c3x3a31x1+a32x2+a33x3≥b3a21x1+a22x2+a23x3=b2令33333(0,0)xxxxx22xx，1111221331331axaxaxaxb1233,,,0xxxx11223333zcxcxcxcx2112222332332axaxaxaxb3113223333333axaxaxaxb3113223333333axaxaxaxb2112222332332axaxaxaxb2112222332332axaxaxaxb2112222332332axaxaxaxbmaxs.t.第10页1312322323333ayayayayc(二)非对称型对偶问题1111221331331axaxaxaxb1233,,,0xxxx11223333zcxcxcxcx3113223333333axaxaxaxb2112222332332axaxaxaxb2112222332332axaxaxaxb2112222332332axaxaxaxbmaxs.t.对偶变量1y3y2y2y1112122123131ayayayayc1223,,,0yyyy11222233wbybybyby1312322323333ayayayayc1212222223232ayayayaycmins.t.对偶问题：第11页1212223232ayayayc1212223232ayayayc(二)非对称型对偶问题1312322323333ayayayayc1112122123131ayayayayc1223,,,0yyyy11222233wbybybyby1312322323333ayayayayc1212222223232ayayayaycmins.t.令33yy222yyy-，1312323333ayayayc1112123131ayayayc10y，112233wbybyby1312323333ayayaycmins.t.2y无约束，30y1212223232ayayayc1312323333ayayayc1112123131ayayayc10y，112233wbybybymins.t.2y无约束，30y1312323333ayayayc第12页3个≥≤=约束条件变量maxx1≥0,x2≤0,x3无约束s.t.a11x1+a12x2+a13x3≤b1z=c1x1+c2x2+c3x3a31x1+a32x2+a33x3≥b3a21x1+a22x2+a23x3=b2maxx1≥0,x2≤0,x3无约束s.t.a11x1+a12x2+a13x3≤b1z=c1x1+c2x2+c3x3a31x1+a32x2+a33x3≥b3a21x1+a22x2+a23x3=b2(二)非对称型对偶问题1212223232ayayayc1312323333ayayayc1112123131ayayayc10y，112233wbybybymins.t.2y无约束，30y原问题对偶问题目标函数max目标函数min目标函数的系数约束条件右端常数约束条件右端常数目标函数的系数3个≤≥=3个≥0≤0无符号限制约束条件变量3个≥0≤0无符号限制321yyy原问题（对偶问题）对偶问题（原问题）第13页3个≥≤=约束条件变量(一)对称型对偶问题原问题（对偶问题）对偶问题（原问题）目标函数max目标函数min目标函数的系数约束条件右端常数约束条件右端常数目标函数的系数3个≤≥=3个≥0≤0无符号限制约束条件变量3个≥0≤0无符号限制12max34zxx12122126283,0xxxxxxxs.t.123min683wyyy12123123324,,0yyyyyyyys.t.2个2个第14页二、原问题与对偶问题的对应关系n个≥≤=约束条件变量原问题（对偶问题）对偶问题（原问题）目标函数max目标函数min目标函数的系数约束条件右端常数约束条件右端常数目标函数的系数m个≤≥=m个≥0≤0无符号限制约束条件变量n个≥0≤0无符号限制n个≥≤=约束条件变量原问题（对偶问题）对偶问题（原问题）原问题（对偶问题）对偶问题（原问题）原问题（对偶问题）对偶问题（原问题）目标函数max目标函数min目标函数的系数约束条件右端常数约束条件右端常数目标函数的系数m个≤≥=m个≥0≤0无符号限制约束条件变量n个≥0≤0无符号限制第15页例2、写出下述线性规划问题的对偶问题解：设对偶变量为123435xxxx12340,0,xxxx,无约束1234235zxxxxmaxs.t.134224xxx2346xxx1222yy10,y123546wyyymins.t.123,,yyy，则对偶问题为20,y3y无约束133yy123325yyy1231yyy第16页例3、写出下述线性规划问题的对偶问题解：设对偶变量为123435xxxx12340,0,xxxx,无约束1234235zxxxxmins.t.134224xxx2346xxx1222yy10,y123546wyyymaxs.t.123,,yyy，则对偶问题为20,y3y无约束133yy123325yyy1231yyy第17页练习、写出下述线性规划问题的对偶问题1234235zxxxxmaxs.t.1234124123412344325327423460,,0,xxxxxxxxxxxxxxx无约束12343234zxxxxmins.t.1234234123412342343345237420,0,xxxxxxxxxxxxxxx,无约束123546wyyymins.t.1231231312312343222333452710,0,yyyyyyyyyyyyyy无约束123546wyyymins.t.1231231312312343222333452710,0,yyyyyyyyyyyyyy无约束123352wyyymaxs.t.1312312312312323232337344440,0,yyyyyyyyyyyyyy