第七章_对偶问题和对偶单纯形法

第七章对偶问题和对偶单纯形法一、问题的提出二、对偶问题和原问题的转换三、对偶规划的性质四、对偶单纯形法五、交替单纯形法一、问题的提出原问题：a和b产量各为多少可以使利润最大？25010C40012B30011A资源限量ba产品设备10050利润一、问题的提出原LP模型：Maxz=50x1+100x2s.t：1·x1+1·x2≤3002·x1+1·x2≤4000·x1+1·x2≤250x1≥0，x2≥0一、问题的提出若考虑将三种设备出租，如何合理确定各设备的租金y1、y2、y3（元/台时）？目标函数：minz=300y1+400y2+250y3约束条件：y1+2y2≥50y1+y2+y3≥100y1、y2、y3≥0一、问题的提出这样两个线性规划问题就是一对对偶问题。称其中一个为原问题（LP问题），另一个为对偶问题（DLP问题）。由于它们内在的联系，可以根据其中一个模型，写出其对偶问题的模型。二、对偶问题和原问题的转换LP问题和DLP问题的关系：规范形(LP)Maxz=cTxs.t.Ax≤bx≥0(DLP)Minf=bTys.t.ATy≥cy≥0二、对偶问题和原问题的转换1、对于规范型，直接按对应关系转换例：Maxz=20x1+8x2+6x3s.t：8x1+3x2+2x3≤2502x1+x2≤504x1+3x3≤150x1，x2，x3≥0写出该线性规划问题的对偶问题。二、对偶问题和原问题的转换则对偶问题为：Minf=250y1+50y2+150y3s.t：8y1+2y2+4y3≥203y1+y2≥82y1+3y3≥6y1，y2，y3≥0二、对偶问题和原问题的转换2、对于非规范形式，先化为规范形式例：写出线性规划模型的对偶问题Minz=3x1+4x2+6x3s.t：x1+3x2-2x3+x4＝252x1+7x3+2x4≥602x1+2x2-4x3≤30x1，x2，x4≥0，x3无非负约束二、对偶问题和原问题的转换首先转换为规范形Minz=3x1+4x2+6x3变为Max(-z)=-3x1-4x2-6x3约束条件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’-x3’’x3’-x3’’≥0则原LP模型可以化为规范形：二、对偶问题和原问题的转换Max(-z)=-3x1-4x2-6x3’+6x3’’s.t：x1+3x2-2x3’+2x3’’+x4≤25-x1-3x2+2x3’-2x3’’-x4≤-25-2x1-7x3’+7x3’’-2x4≤-602x1+2x2-4x3’+4x3’’≤30x1,x2,x3’,x3’’,x4≥0二、对偶问题和原问题的转换故DLP可写出：Minf＝25y1-25y2-60y3+30y4s.t：y1-y2-2y3+2y4≥-33y1-3y2+2y4≥-4-2y1+2y2-7y3-4y4≥-62y1-2y2+7y3+4y4≥6y1-y2-2y3≥0y1，y2，y3，y4，y5≥0二、对偶问题和原问题的转换将DLP模型整理可得：Minf＝25y5+60y3+30y4s.t：y5+2y3+2y4≥-33y5+2y4≥-4-2y5+7y3-4y4＝-6y5+2y3≥0y5无非负约束，y3≤0，y4≥0LP与DLP的一般对应关系原问题LP对偶问题DLP目标函数maxzminf目标函数变量xj（j＝1，2……n）n个n个约束条件j（j＝1，2……n）≥0≥≤0≤无约束＝约束条件i（i＝1，2……m）m个m个变量yj（i＝1，2……m）≤≥0≥≤0＝无约束目标函数变量的系数cj（j＝1，2……n）约束条件右端项cjT（j＝1，2……n）约束条件右端项bi（i＝1，2……m）目标函数变量的系数biT（i＝1，2……m）练习写出下面LP问题的DLP模型Minz=x1+2x2+5x3s.t：2x1+3x2+x3＝103x1+x2+x3≥50x1+x3≤20x1≥0，x2≤0，x3无非负约束三、对偶规划的性质1、对称性：对偶问题的对偶是原问题。2、弱对偶性：若X是原问题（max）的可行解，Y是对偶问题（min）的可行解，则存在CX≤bTY三、对偶规划的性质推论a：原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。推论b：若原问题解无界，则其对偶问题无可行解；若对偶问题解无界，则原问题无可行解。（逆命题不成立）推论c：若原问题有可行解而对偶问题无可行解，则原问题无界；反之，对偶问题有可行解而原问题无可行解，则对偶问题解无界。三、对偶规划的性质3、最优性：若x,y分别是原问题和对偶问题的可行解,且cx=bTy，那么x,y分别为原问题和对偶问题的最优解。三、对偶规划的性质4、强对偶性：若原问题和对偶问题都有可行解，则两者都有最优解，且最优目标函数值相等。三、对偶规划的性质5、互补松弛定理：在原问题的最优解中，如果对应某一约束条件的对偶变量值不为0，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为0，即若Yi*0，则有∑aijxj*＝bi若∑aijxj*bi，则有Yi*＝0对偶问题解的意义若x*,y*分别为（LP）和（DLP）的最优解，那么，cx*=bTy*。根据f=bTy*=b1y1*+b2y2*++bmym*可知f/bi=yi*yi*表示bi变化1个单位对目标f产生的影响。对偶问题解的意义因此：对偶问题的最优解就是原问题中相应资源常数项的影子价格。若B是初始基在最优表中的形式，影子价格向量Y*=B×CB确定影子价格在原问题和对偶问题中的对应关系后，可以由原问题最优单纯形表求对偶问题最优解。对偶问题解的意义如范例最优表：2-250-5000j=cj－zj21250250507550zj2501001075x25011-2000x450-1010150x10007550比值bi/ai2bx5x4x3x2x1CB基变量XB迭代次数对偶问题解的意义原问题的最优解为：x1=50x2=250x4=50对偶问题的最优解为：y1=50y2=0y3=50（影子价格）四、对偶单纯形法最优表特征：基向量为单位向量右端项非负2-500-5000j=cj－zj275005005010050zj25010010100x25011-2000x450-1010150x100010050比值bi/ai2bx5x4x3x2x1CB基变量XB迭代次数检验数非正四、对偶单纯形法单纯形法的迭代：保证基向量为单位向量保证右端项非负000010050j=cj－zj0500000zj250100100x5400010120x4300001110x300010050比值bi/ai2bx5x4x3x2x1CB基变量XB迭代次数检验数由正变为非正右端项由负变为非负保证基向量为单位向量四、对偶单纯形法对偶单纯形法的迭代：基变量XBCBx1x2x3x4x5x6b501000000x1501010-1050x4000-211050x2100010010250x6000-100-201-3000zj5010050050027500j00-500-500保证检验数非正四、对偶单纯形法在满足对偶单纯形迭代前提条件的表上确定主行和出基变量：基变量XBCBx1x2x3x4x5x6b501000000x1501010-1050x4000-211050x2100010010250x6000-100-201-3000zj5010050050027500j00-500-5001、按最小b值原则确定主行和出基变量四、对偶单纯形法确定主列和进基变量0-500-5000j2.550-2011-10x525000010100x2－01000x6－5－－j/alj2750005010050zj-30000-10000x6501-2000x450010150x10010050bx4x3x2x1CB基变量XB1、按最小比值原则确定主列和进基变量主元四、对偶单纯形法基变量XBCBx1x2x3x4x5x6b501000000x150101.500-1/20200x4000-2.5101/20-100x210001-0.5001/20100x50000.501-1/20150zj5010025002.520000j00-5000-2.5j/alj－－20－－－迭代：与原始单纯形法一样，通过行变换将主列变为主元为1的单位列。四、对偶单纯形法基变量XBCBx1x2x3x4x5x6b501000000x15010060-1/50140x30001-40-1/5040x2100010-201/25120x5000021-1/25130zj5010001000319000j＝cj－zj000-1000-3所有b值都大于0，该表中的解为可行解，故最优解为（140，120，40，0，130，0）。四、对偶单纯形法对偶单纯形法过程：1、建立初始对偶单纯形表,对应一个基本解,所有检验数均非正；2、若b’≥0,则得到最优解,停止；若有b’0则选其中最小的bl所在的第l行的基变量为出基变量；四、对偶单纯形法3、若所有alj’≥0(j=1,2,…,n)，则原问题无可行解,停止；若有alj’0则选=min{j’/alj’┃alj’0}=k’/alk’那么xk为进基变量；4、以alk’为主元,作矩阵行变换使其变为1,该列其他元变为0。所有b值非负时达到最优。四、对偶单纯形法练习：用对偶单纯形法求解Minf=2x1+3x2+4x3S.t.x1+2x2+x3≥32x1-x2+x3≥4x1,x2,x3≥0四、对偶单纯形法首先变形，使其具备对偶单纯形迭代的前提条件：Maxz=-2x1-3x2-4x3s.t.-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥0-2-3-20-1/5-8/5-9/500j＝cj－zj-28/51/58/5-11/5-3-2zj11/5-2/5-1/57/501x12/51/5-2/5-1/510x22－－8/5－j/alj-10-1-40j＝cj－zj-410-31-2zj2-1/203/2-1/21x1-1-1/211/2-5/20x4－－4/3－1j/alj00-4-3-2j＝cj－zj000000zj-410-31-20x5-301-1-2-10x400-4-3-2bx5x4x3x2x1CB基变量XB对偶单纯形法与单纯形法的比较单纯形法对偶单纯形法前提条件所有bi≥0所有j≤0最优性检验所有j≤0所有bi≥0进基、离基变量的确定先确定进基变量（最大检验数原则）；后确定离基变量（比值bi/aik(ajk0)最小原则）先确定离基变量（最小b0值原则）；后确定进基变量（比值j/alj(alj0)最小原则）原始基本解的进化从可行到最优从非可行到可行（最优）五、交替单纯形法不管是原始单纯形法，还是对偶单纯形法，初始表都有前提条件。如果两种方法的初始条件都不能满足，怎么办？五、交替单纯形法例如：Maxz=-3x1+2x2-x3s.t：-x1-x2+x3≤-42x1+3x2+x3≤203x1+x2+x3≤28x1，x2，x3≥0五、交替单纯形法基变量XBCBx1x2x3x4x5x6b-32-1000x40-1-11100-4x5023101020x6031100128zj0000000j-32-1000检验数不满足非正，不能用对偶单纯形法右端项不满足非负，不能用原始单纯形法五、交替单纯形法解