第七章对偶问题和对偶单纯形法.ppt课件.ppt

1、第七章 对偶问题和对偶单纯形法一、问题的提出一、问题的提出二、对偶问题和原问题二、对偶问题和原问题的转换的转换三、对偶规划的性质三、对偶规划的性质四、对偶单纯形法四、对偶单纯形法五、交替单纯形法五、交替单纯形法一、问题的提出一、问题的提出v原问题：原问题：a和和b产量各为多少可以使产量各为多少可以使利润最大？利润最大？25010C40012B30011A资源限量资源限量ba 产品产品设备设备 10050利润利润一、问题的提出一、问题的提出v原原LP 模型：模型：v Max z= 50 x1+100 x2 s.t：1x1+1x2300 2x1+1 x2400 0 x1+1 x2250 x1 0，

2、 x2 0一、问题的提出一、问题的提出v若考虑将三种设备出租，如何合理确定若考虑将三种设备出租，如何合理确定各设备的租金各设备的租金y1、 y2 、 y3 （元（元/台时）？台时）？v目标函数：目标函数：min z= 300y1+400 y2+250 y3v约束条件：约束条件：y1+2y2 50v y1+ y2+ y3 100v y1、 y2、y3 0一、问题的提出一、问题的提出v这样两个线性规划问题就是一对对偶问这样两个线性规划问题就是一对对偶问题。题。v称其中一个为原问题（称其中一个为原问题（LP问题），另一问题），另一个为对偶问题（个为对偶问题（DLP问题）。问题）。v由于它们内在的联系

3、，可以根据其中一由于它们内在的联系，可以根据其中一个模型，写出其对偶问题的模型。个模型，写出其对偶问题的模型。二、对偶问题和原问题的转换二、对偶问题和原问题的转换vLP问题和问题和DLP问题的关系：问题的关系： 规范形规范形(LP) Max z = cT x s.t. Ax b x 0(DLP) Min f = bT ys.t. AT y c y 0二、对偶问题和原问题的转换二、对偶问题和原问题的转换v1、对于规范型，直接按对应关系转换、对于规范型，直接按对应关系转换v例：例： Max z= 20 x1+ 8 x2 +6 x3 s.t： 8x1+ 3x2 +2x3 250 2x1+x2 50

4、4x1+3x3 150 x1 ，x2 ，x3 0v写出该线性规划问题的对偶问题。写出该线性规划问题的对偶问题。二、对偶问题和原问题的转换二、对偶问题和原问题的转换v则对偶问题为：则对偶问题为：vMin f=250 y1+ 50 y2 + 150 y3v s.t： 8y1+ 2y2 +4y3 20v 3y1+y2 8v 2 y1+3y3 6v y1 ，y2 ，y3 0二、对偶问题和原问题的转换二、对偶问题和原问题的转换v2、对于非规范形式，先化为规范形式、对于非规范形式，先化为规范形式v例：例： 写出线性规划模型的对偶问题写出线性规划模型的对偶问题vMin z= 3x1+ 4 x2 +6 x3

5、v s.t： x1+ 3x2 -2x3 + x4 25v 2x1+7x3 + 2x4 60v 2x1+2x2-4x3 30v x1 ，x2 ，x4 0 ，x3 无非负约束无非负约束二、对偶问题和原问题的转换二、对偶问题和原问题的转换v首先转换为规范形首先转换为规范形vMin z= 3x1+ 4 x2 +6 x3v变为变为Max(-z)= -3x1- 4 x2 -6 x3 v约束条件约束条件x1+ 3x2 -2x3 + x4 25v等同于等同于x1+ 3x2 -2x3 + x4 25和和v x1+ 3x2 -2x3 + x4 25联立联立二、对偶问题和原问题的转换二、对偶问题和原问题的转换v2x

6、1+7x3 + 2x4 60可转化为可转化为v-2x1-7x3 - 2x4 - 60vx3 无非负约束，则令无非负约束，则令x3 x3- x3vx3- x3 0v则原则原LP模型可以化为规范形：模型可以化为规范形：二、对偶问题和原问题的转换二、对偶问题和原问题的转换vMax (-z)= -3x1- 4 x2 -6 x3+6 x3 v s.t： x1+ 3x2 -2 x3+2 x3 + x4 25v -x1- 3x2 +2 x3-2 x3 - x4 -25v -2x1-7 x3+ 7x3 - 2x4 -60v 2x1+2x2-4 x3+4 x3 30v x1 ,x2 ,x3, x3 ,x4 0二

7、、对偶问题和原问题的转换二、对偶问题和原问题的转换v故故DLP可写出：可写出：vMin f25 y1-25 y2 -60 y3 +30 y4v s.t： y1- y2 -2 y3 +2y4 -3v 3y1-3y2 +2y4 -4v -2y1+2y2 -7y3 -4 y4 -6v 2y1-2y2 +7y3 +4y4 6v y1-y2 -2y3 0v y1 ，y2 ，y3 ，y4 ，y5 0二、对偶问题和原问题的转换二、对偶问题和原问题的转换v将将DLP模型整理可得：模型整理可得：vMin f25 y5+60 y3 +30 y4v s.t： y5+2 y3 +2y4 -3v 3y5+2y4 -4v

8、 -2y5+7y3 -4y4 -6v y5+2y3 0v y5 无非负约束，无非负约束， y3 0，y4 0LP与DLP的一般对应关系原问题原问题LP对偶问题对偶问题DLP目标函数目标函数maxzminf目标函数目标函数变量变量xj（j1，2n）n个个n个个约束条件约束条件j （j1，2n）00无约束无约束约束条件约束条件i （i1，2m）m个个m个个变量变量yj（i1，2m）00无约束无约束目标函数变量的系数目标函数变量的系数cj（j1，2n）约束条件右端项约束条件右端项cjT（j1，2n）约束条件右端项约束条件右端项bi（i1，2m）目标函数变量的系数目标函数变量的系数biT（i1，2m）

9、练习练习v写出下面写出下面LP问题的问题的DLP模型模型vMin z= x1+ 2 x2 +5 x3 v s.t： 2x1+ 3x2 +x3 10v 3x1+x2 + x3 50v x1+x3 20v x1 0 ，x2 0 ，x3 无非负约束无非负约束三、对偶规划的性质三、对偶规划的性质v1、对称性：、对称性：v对偶问题的对偶是原问题。对偶问题的对偶是原问题。v2、弱对偶性：、弱对偶性：v若若X是原问题（是原问题（max）的可行解，）的可行解，Y是对是对偶问题（偶问题（min）的可行解，则存在）的可行解，则存在CXbTY三、对偶规划的性质三、对偶规划的性质v推论推论 a ： 原问题任一可行解的

10、目标函数值是其对偶原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。的目标函数值是其原问题目标函数值的上界。v推论推论b：若原问题解无界，则其对偶问题无可行解；：若原问题解无界，则其对偶问题无可行解；若对偶问题解无界，则原问题无可行解。（逆命题若对偶问题解无界，则原问题无可行解。（逆命题不成立）不成立）v推论推论c：若原问题有可行解而对偶问题无可行解，：若原问题有可行解而对偶问题无可行解，则原问题无界；反之，对偶问题有可行解而原问题则原问题无界；反之，对偶问题有可行解而原问题无可行

11、解，则对偶问题解无界。无可行解，则对偶问题解无界。三、对偶规划的性质三、对偶规划的性质v3、最优性：、最优性：v若若x,y分别是原问题和对偶问题的可行解分别是原问题和对偶问题的可行解,且且cx=bTy ，那么，那么x,y分别为原问题和对分别为原问题和对偶问题的最优解。偶问题的最优解。三、对偶规划的性质三、对偶规划的性质v4、强对偶性：、强对偶性：v若原问题和对偶问题都有可行解，则两若原问题和对偶问题都有可行解，则两者都有最优解，且最优目标函数值相等。者都有最优解，且最优目标函数值相等。三、对偶规划的性质三、对偶规划的性质v5、互补松弛定理：、互补松弛定理：v在原问题的最优解中，如果对应某一约束

12、条在原问题的最优解中，如果对应某一约束条件的对偶变量值不为件的对偶变量值不为0，则该约束条件取严格，则该约束条件取严格等式；反之，如果约束条件取严格不等式，等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为则其对应的对偶变量一定为0，即，即v若若Yi*0，则有，则有aijxj*biv若若aijxj*bi ，则有，则有Yi*0对偶问题解的意义对偶问题解的意义若若x*,y* 分别为（分别为（LP）和（）和（DLP）的最优解，）的最优解， 那么，那么， cx* = bT y* 。 根据根据 f = bTy*=b1y1*+b2y2*+bmym* 可知可知 f / bi = yi* yi*表

13、示表示 bi 变化变化1个单位对目标个单位对目标 f 产生的影响。产生的影响。对偶问题解的意义对偶问题解的意义因此：对偶问题的最优解就是原问题中相应因此：对偶问题的最优解就是原问题中相应资源常数项的影子价格。资源常数项的影子价格。若若B是初始基在最优表中的形式，影子价格是初始基在最优表中的形式，影子价格向量向量 Y* = BCB确定影子价格在原问题和对偶问题中的对应确定影子价格在原问题和对偶问题中的对应关系后，可以由原问题最优单纯形表求对偶关系后，可以由原问题最优单纯形表求对偶问题最优解。问题最优解。对偶问题解的意义对偶问题解的意义v如范例最优表：如范例最优表：2-250-5000 j=cjz

14、j21250250507550zj2501001075x25011-2000 x450-1010150 x10007550比值比值bi/ai2bx5x4x3x2x1CB基变基变量量XB迭代迭代次数次数对偶问题解的意义对偶问题解的意义v原问题的最优解为：原问题的最优解为：vx1=50 x2=250 x4=50v对偶问题的最优解为：对偶问题的最优解为：vy1=50 y2=0 y3=50 （影子价格）（影子价格）四、对偶单纯形法四、对偶单纯形法v最优表特征：最优表特征：基向量为基向量为单位向量单位向量右端项右端项非负非负2-500-5000 j=cjzj275005005010050zj250100

15、10100 x25011-2000 x450-1010150 x100010050比值比值bi/ai2bx5x4x3x2x1CB基变基变量量XB迭代迭代次数次数检验数非正检验数非正四、对偶单纯形法四、对偶单纯形法v单纯形法的迭代：单纯形法的迭代：保证基向量保证基向量为单位向量为单位向量保证右端保证右端项非负项非负000010050 j=cjzj0500000zj250100100 x5400010120 x4300001110 x300010050比值比值bi/ai2bx5x4x3x2x1CB基变基变量量XB迭代迭代次数次数检验数由正检验数由正变为非正变为非正右端项右端项由负变由负变为非负为非

16、负保证基向量保证基向量为单位向量为单位向量四、对偶单纯形法四、对偶单纯形法v对偶单纯形法的迭代：对偶单纯形法的迭代：基变基变量量XBCBx1x2x3x4x5x6b501000000 x1501010-1050 x4000-211050 x2100010010250 x6000-100-201-3000zj5010050050027500 j00-500-500保证检验保证检验数非正数非正四、对偶单纯形法四、对偶单纯形法v在满足对偶单纯形迭代前提条件的表上确定在满足对偶单纯形迭代前提条件的表上确定主行和出基变量：主行和出基变量：基变基变量量XBCBx1x2x3x4x5x6b501000000 x

17、1501010-1050 x4000-211050 x2100010010250 x6000-100-201-3000zj50100500500 27500 j00-500-5001、按、按最小最小b值原则值原则确定主确定主行和出行和出基变量基变量四、对偶单纯形法四、对偶单纯形法v确定主列和进基变量确定主列和进基变量0-500-5000 j2.550-2011-10 x525000010100 x201000 x65 j /alj2750005010050zj-30000-10000 x6501-2000 x450010150 x10010050bx4x3x2x1CB基变基变量量XB1、按、按

18、最最小比值原小比值原则则确定主确定主列和进基列和进基变量变量主元主元四、对偶单纯形法四、对偶单纯形法基变量基变量XBCBx1x2x3x4x5x6b501000000 x150101.500-1/20200 x4000-2.5101/20-100 x210001-0.5001/20100 x50000.501-1/20150zj5010025002.520000 j00-5000-2.5 j /alj20v迭代：与原始单纯形法一样，通过行变换将迭代：与原始单纯形法一样，通过行变换将主列变为主元为主列变为主元为1的单位列。的单位列。四、对偶单纯形法四、对偶单纯形法基变基变量量XBCBx1x2x3x

19、4x5x6b501000000 x15010060-1/50140 x30001-40-1/5040 x2100010-201/25120 x5000021-1/25130zj5010001000319000 jcjzj000-1000-3v所有所有b值都大于值都大于0，该表中的解为可行解，故，该表中的解为可行解，故最优解为（最优解为（140，120，40，0，130，0）。）。四、对偶单纯形法四、对偶单纯形法对偶单纯形法过程：对偶单纯形法过程：1、建立初始对偶单纯形表、建立初始对偶单纯形表,对应一个基对应一个基本解本解,所有检验数均非正；所有检验数均非正；2、若、若b0,则得到最优解则得到最

20、优解,停止；若有停止；若有b 0 则选其中最小的则选其中最小的bl所在的第所在的第l行的基变行的基变量为出基变量；量为出基变量；四、对偶单纯形法四、对偶单纯形法3、若所有、若所有alj0( j = 1,2,n )，则原问，则原问题无可行解题无可行解,停止；若有停止；若有alj0 则选则选 =min j / aljalj0)最小原则）最小原则）先确定离基变量先确定离基变量（最小（最小b0值原则）；值原则）；后确定进基变量后确定进基变量（比值（比值 j /alj (alj0)最最小原则）小原则）原始基本解原始基本解的进化的进化从可行到最优从可行到最优从非可行到可行从非可行到可行（最优）（最优）五、

21、交替单纯形法五、交替单纯形法v不管是原始单纯形法，还是对偶单纯形不管是原始单纯形法，还是对偶单纯形法，初始表都有前提条件。法，初始表都有前提条件。v如果两种方法的初始条件都不能满足，如果两种方法的初始条件都不能满足，怎么办？怎么办？五、交替单纯形法五、交替单纯形法v例如：例如： Max z= -3x1+2x2-x3 v s.t： -x1-x2+x3 - 4v 2x1+3x2 +x320v 3x1+x2+x3 28v x1 ，x2 ，x3 0五、交替单纯形法五、交替单纯形法基变量基变量XBCBx1x2x3x4x5x6b-32-1000 x40-1-11100-4x5023101020 x6031

22、100128zj0000000 j-32-1000检验数不满足非正，检验数不满足非正，不能用对偶单纯形法不能用对偶单纯形法右端项不满足非负，右端项不满足非负，不能用原始单纯形法不能用原始单纯形法五、交替单纯形法五、交替单纯形法v解决办法：先变为原始可行或对偶可行解决办法：先变为原始可行或对偶可行v对上例的处理是：先用对偶单纯形法，对上例的处理是：先用对偶单纯形法，将其变为原始可行，再用原始单纯形法将其变为原始可行，再用原始单纯形法迭代求解。迭代求解。五、交替单纯形法五、交替单纯形法基变基变量量XBCBx1x2x3x4x5x6b-32-1000 x40-1-11100-4x5023101020

23、x6031100128zj0000000 j-32-1000 j /alj3-2五、交替单纯形法五、交替单纯形法82484b00210-5 j00100 x524112020 x60000 x6-2-222zj8/3340-10 x5-1-1112x20-12-3比值比值x4x3x2x1CB基变基变量量XB右端项已满足非负，右端项已满足非负，应用原始单纯形法应用原始单纯形法五、交替单纯形法五、交替单纯形法基变基变量量XBCBx1x2x3x4x5x6b比值比值-32-1000 x222/311/301/3020/3x40-1/304/311/308/3x607/302/30-1/3164/3zj4/322/302/3040/3 j-10/30-5/30-2/30v满足最优性条件，已达最优。满足最优性条件，已达最优。作业作业v教材教材125页：页：8（1）、）、9题。题。