最优化LP对偶单纯形法

1、对偶单纯形法对偶单纯形法 cyAtsybDxbAxtsxcPTTT.max)(. 0,.min)(和和设设 是一个基，是一个基， 满足约束满足约束 的对偶向量的对偶向量 称为称为对偶基本解对偶基本解。BABTBcyA y若对偶基本解若对偶基本解 也是可行的，即松弛向量也是可行的，即松弛向量 ，称，称 为为对偶基本可行解对偶基本可行解。 y0 yAcsTy若若 的所有分量均不为零，称的所有分量均不为零，称 是非退化的是非退化的。 Nsy若若 对应的原始基本解和对偶基本解都是非退化的，对应的原始基本解和对偶基本解都是非退化的，称称 为为非退化基非退化基。BABA定理定理(最优条件最优条件)若若 对

2、应的原始基本解对应的原始基本解 和对偶基本解和对偶基本解 都是可行都是可行的，则这两个基本解分别是原始问题和对偶问题的的，则这两个基本解分别是原始问题和对偶问题的最优解，最优解， 为为最优基最优基。BABAxy,01 bAxxxBNB证明：证明：,BTBcAy . 0 BTBTcAAc .是原问题的最优解是原问题的最优解x,xccAbybTBTBTT .是对偶问题的最优解是对偶问题的最优解y原始单纯形方法分析原始单纯形方法分析在算法中，当前基在算法中，当前基 保持原始基本解保持原始基本解 可行。可行。BAx在该方法中，对偶基本解在该方法中，对偶基本解 仅在算法仅在算法BTBcAy 停止时才变成

3、可行的。停止时才变成可行的。算法中的检验数算法中的检验数 就是松弛向量就是松弛向量 。在任一基。在任一基 ， s, 0, 0 BNx BA)(,sx或或 总是互补的总是互补的。当算法停止时，当算法停止时， 成为原始最优解，成为原始最优解， 成为对偶可行，成为对偶可行，xy因此也是对偶最优的，二者最优值相等因此也是对偶最优的，二者最优值相等。对偶单纯形主要思想对偶单纯形主要思想原始单纯形：保持原始基本解原始单纯形：保持原始基本解 可行和互补松弛可行和互补松弛条件条件 可行可行; ; 对偶单纯形：保持原始基本解对偶单纯形：保持原始基本解 可行和互补松弛可行和互补松弛条件条件 可行。可行。xyyxy

4、AcxTTT 0)( xbxAyT 0)()(最最优优性性条条件件)1()(LPxczT min0,. xbAxtsNBx非非基基变变量量指指标标集集基基变变量量指指标标集集对对应应的的原原始始基基本本解解,:,:对偶可行对偶可行BTBcAy .:1NBNAAA ,1NNBxAbAxB NTNNNTBTBxcxAcbcz min. 0, 0 NBxxs.ts.t. . bcTBNNTBTNxAcc)( , 01 AAccBTBTT 检验数检验数是是对对偶偶最最优优解解。原原始始最最优优解解，是是，则则若若的的一一个个基基本本解解对对应应于于基基设设定定理理yxxBx0, . cyAcAyTBT

5、B 可行，满足可行，满足对偶解对偶解基基变变换换)2(:不不可可行行x注意到：注意到：0)( )2(; 0)1(1 oBbA . 0)(., oBxtso,)()(1NoNooBxabAxB , 01 oa）（都不能改善都不能改善增加任何一个非基变量增加任何一个非基变量)(Nexe 不可行。不可行。的不可行性，即原问题的不可行性，即原问题基本解基本解x, 0,2 ojaNj使得使得）（jx基变量基变量开始慢慢增加对应的非开始慢慢增加对应的非从从0为非负数。为非负数。个分量也会增加，直到个分量也会增加，直到的第的第则基本解则基本解ox能能增增加加到到多多少少？jx, 0 要保持要保持则对应的则对

6、应的计算最小比值计算最小比值,0:min ojojjNjaa 0:minarg ojojjNjaae 就就是是进进基基变变量量。对偶单纯形分析对偶单纯形分析给定基给定基 ，写出，写出LP的典式，则有：的典式，则有：BA(1) , ,最优解，停止。最优解，停止。, 0 Bx(2) 且且 ，原问题不可行。，原问题不可行。 0)( oBx0 oa(3) , ,但但 。 0)( oBx0, ojaNj使得使得根据算法思想，需要保持对偶可行性：根据算法思想，需要保持对偶可行性：选择这些负数选择这些负数 之一为转轴中心，之一为转轴中心， 为出基变量。为出基变量。ojaBoxo ,0:minarg ojoj

7、jNjaae Nexe ,为进基变量为进基变量 . 0, 5 . 1, 1, 1.2min212121xxxxxtsxx用对偶单纯性算法计算用对偶单纯性算法计算5 , 2 , 1 B基为基为初始对偶基本可行解的初始对偶基本可行解的第一个对偶基本可行解的求法第一个对偶基本可行解的求法,11NNBBBxAAbAx NNBTBTNBTBxAAccbAcz)(min11 . 0, 0 NBxxs.ts.t. .则典式为则典式为任选基矩阵任选基矩阵,BA.;, 0bfscAyNjBTBBj为对偶为对偶则则若若 . )(;, 000 NjjjMxxxNj充分大充分大和一个约束和一个约束增加一个变量增加一个变量若若 .10, 0|minbfsJordanGausseNeee到扩充问题的对偶到扩充问题的对偶变换，得变换，得作为主元进行作为主元进行的的列列行第行第以第以第令令 第一个对偶基本可行解的求法第一个对偶基本可行解的求法.10, 0|minbfsJordanGausseNeee到到扩扩充充问问题题的的对对偶偶变变换换，得得作作为为主主元元进进行行的的列列行行第第以以第第令令 对对于于扩扩充充问问题题，得得到到扩扩充充问问题题无无可可行行解解，. 1则则原原问问题题无无可可行行解解。是是