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

1、第七章 对偶问题和对偶单纯形法一、问题的提出二、对偶问题和原问题的转换三、对偶规划的性质四、对偶单纯形法五、交替单纯形法一、问题的提出原问题：a和b产量各为多少可以使利润最大？25010C40012B30011A资源限量ba 产品设备 10050利润一、问题的提出原LP 模型： Max z= 50 x1+100 x2 s.t：1x1+1x2300 2x1+1 x2400 0 x1+1 x2250 x1 0， x2 0一、问题的提出若考虑将三种设备出租，如何合理确定各设备的租金y1、 y2 、 y3 （元/台时）？目标函数：min z= 300y1+400 y2+250 y3约束条件：y1+2y

2、2 50 y1+ y2+ y3 100 y1、 y2、y3 0一、问题的提出这样两个线性规划问题就是一对对偶问题。称其中一个为原问题（LP问题），另一个为对偶问题（DLP问题）。由于它们内在的联系，可以根据其中一个模型，写出其对偶问题的模型。二、对偶问题和原问题的转换LP问题和DLP问题的关系： 规范形(LP) Max z = cT x s.t. Ax b x 0(DLP) Min f = bT ys.t. AT y c y 0二、对偶问题和原问题的转换1、对于规范型，直接按对应关系转换例： Max z= 20 x1+ 8 x2 +6 x3 s.t： 8x1+ 3x2 +2x3 250 2x1

3、+x2 50 4x1+3x3 150 x1 ，x2 ，x3 0写出该线性规划问题的对偶问题。二、对偶问题和原问题的转换则对偶问题为：Min f=250 y1+ 50 y2 + 150 y3 s.t： 8y1+ 2y2 +4y3 20 3y1+y2 8 2 y1+3y3 6 y1 ，y2 ，y3 0二、对偶问题和原问题的转换2、对于非规范形式，先化为规范形式例： 写出线性规划模型的对偶问题Min z= 3x1+ 4 x2 +6 x3 s.t： x1+ 3x2 -2x3 + x4 25 2x1+7x3 + 2x4 60 2x1+2x2-4x3 30 x1 ，x2 ，x4 0 ，x3 无非负约束二、

4、对偶问题和原问题的转换首先转换为规范形Min z= 3x1+ 4 x2 +6 x3变为Max(-z)= -3x1- 4 x2 -6 x3 约束条件x1+ 3x2 -2x3 + x4 25等同于x1+ 3x2 -2x3 + x4 25和 x1+ 3x2 -2x3 + x4 25联立二、对偶问题和原问题的转换2x1+7x3 + 2x4 60可转化为-2x1-7x3 - 2x4 - 60 x3 无非负约束，则令x3 x3- x3x3- x3 0则原LP模型可以化为规范形：二、对偶问题和原问题的转换Max (-z)= -3x1- 4 x2 -6 x3+6 x3 s.t： x1+ 3x2 -2 x3+2

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

6、：Min f25 y5+60 y3 +30 y4 s.t： y5+2 y3 +2y4 -3 3y5+2y4 -4 -2y5+7y3 -4y4 -6 y5+2y3 0 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）练习写出下面LP问题的DLP模型Min z

7、= x1+ 2 x2 +5 x3 s.t： 2x1+ 3x2 +x3 10 3x1+x2 + x3 50 x1+x3 20 x1 0 ，x2 0 ，x3 无非负约束三、对偶规划的性质1、对称性：对偶问题的对偶是原问题。2、弱对偶性：若X是原问题（max）的可行解，Y是对偶问题（min）的可行解，则存在CXbTY三、对偶规划的性质推论 a ： 原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。推论b：若原问题解无界，则其对偶问题无可行解；若对偶问题解无界，则原问题无可行解。（逆命题不成立）推论c：若原问题有可行解而对偶问题无可

8、行解，则原问题无界；反之，对偶问题有可行解而原问题无可行解，则对偶问题解无界。三、对偶规划的性质3、最优性：若x,y分别是原问题和对偶问题的可行解,且cx=bTy ，那么x,y分别为原问题和对偶问题的最优解。三、对偶规划的性质4、强对偶性：若原问题和对偶问题都有可行解，则两者都有最优解，且最优目标函数值相等。三、对偶规划的性质5、互补松弛定理：在原问题的最优解中，如果对应某一约束条件的对偶变量值不为0，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为0，即若Yi*0，则有aijxj*bi若aijxj*bi ，则有Yi*0对偶问题解的意义若x*,y* 分别为（LP

9、）和（DLP）的最优解， 那么， cx* = bT y* 。 根据 f = bTy*=b1y1*+b2y2*+bmym* 可知 f / bi = yi* yi*表示 bi 变化1个单位对目标 f 产生的影响。对偶问题解的意义因此：对偶问题的最优解就是原问题中相应资源常数项的影子价格。若B是初始基在最优表中的形式，影子价格向量 Y* = BCB确定影子价格在原问题和对偶问题中的对应关系后，可以由原问题最优单纯形表求对偶问题最优解。对偶问题解的意义如范例最优表：2-250-5000j=cjzj21250250507550zj2501001075x25011-2000 x450-1010150 x1

10、0007550比值bi/ai2bx5x4x3x2x1CB基变量XB迭代次数对偶问题解的意义原问题的最优解为：x1=50 x2=250 x4=50对偶问题的最优解为：y1=50 y2=0 y3=50 （影子价格）四、对偶单纯形法最优表特征：基向量为单位向量右端项非负2-500-5000j=cjzj275005005010050zj25010010100 x25011-2000 x450-1010150 x100010050比值bi/ai2bx5x4x3x2x1CB基变量XB迭代次数检验数非正四、对偶单纯形法单纯形法的迭代：保证基向量为单位向量保证右端项非负000010050j=cjzj05000

11、00zj250100100 x5400010120 x4300001110 x300010050比值bi/ai2bx5x4x3x2x1CB基变量XB迭代次数检验数由正变为非正右端项由负变为非负保证基向量为单位向量四、对偶单纯形法对偶单纯形法的迭代：基变量XBCBx1x2x3x4x5x6b501000000 x1501010-1050 x4000-211050 x2100010010250 x6000-100-201-3000zj5010050050027500j00-500-500保证检验数非正四、对偶单纯形法在满足对偶单纯形迭代前提条件的表上确定主行和出基变量：基变量XBCBx1x2x3x4

12、x5x6b501000000 x1501010-1050 x4000-211050 x2100010010250 x6000-100-201-3000zj5010050050027500j00-500-5001、按最小b值原则确定主行和出基变量四、对偶单纯形法确定主列和进基变量0-500-5000j2.550-2011-10 x525000010100 x201000 x65j /alj2750005010050zj-30000-10000 x6501-2000 x450010150 x10010050bx4x3x2x1CB基变量XB1、按最小比值原则确定主列和进基变量主元四、对偶单纯形法基变

13、量XBCBx1x2x3x4x5x6b501000000 x150101.500-1/20200 x4000-2.5101/20-100 x210001-0.5001/20100 x50000.501-1/20150zj5010025002.520000j00-5000-2.5j /alj20迭代：与原始单纯形法一样，通过行变换将主列变为主元为1的单位列。四、对偶单纯形法基变量XBCBx1x2x3x4x5x6b501000000 x15010060-1/50140 x30001-40-1/5040 x2100010-201/25120 x5000021-1/25130zj501000100031

14、9000jcjzj000-1000-3所有b值都大于0，该表中的解为可行解，故最优解为（140，120，40，0，130，0）。四、对偶单纯形法对偶单纯形法过程：1、建立初始对偶单纯形表,对应一个基本解,所有检验数均非正；2、若b0,则得到最优解,停止；若有b 0 则选其中最小的bl所在的第l行的基变量为出基变量；四、对偶单纯形法3、若所有alj0( j = 1,2,n )，则原问题无可行解,停止；若有alj0 则选=minj / aljalj0)最小原则）先确定离基变量（最小b0值原则）；后确定进基变量（比值j /alj (alj0)最小原则）原始基本解的进化从可行到最优从非可行到可行（最优

15、）五、交替单纯形法不管是原始单纯形法，还是对偶单纯形法，初始表都有前提条件。如果两种方法的初始条件都不能满足，怎么办？五、交替单纯形法例如： Max z= -3x1+2x2-x3 s.t： -x1-x2+x3 - 4 2x1+3x2 +x320 3x1+x2+x3 28 x1 ，x2 ，x3 0五、交替单纯形法基变量XBCBx1x2x3x4x5x6b-32-1000 x40-1-11100-4x5023101020 x6031100128zj0000000j-32-1000检验数不满足非正，不能用对偶单纯形法右端项不满足非负，不能用原始单纯形法五、交替单纯形法解决办法：先变为原始可行或对偶可行对上例的处理是：先用对偶单纯形法，将其变为原始可行，再用原始单纯形法迭代求解。五、交替单纯形法基变量XBCBx1x2x3x4x5x6b-32-1000 x40-1-11100-4x5023101020 x6031100128zj0000000j-32-1000j /alj3-2五、交替单纯形法82484b00210-5j00100 x52411