2.2 单纯形法

,2.2单纯形方法,一.单纯形方法的理论依据与迭代步骤,基本思想:,先找出(LP)的一个基本可行解,判断它是否为最优解.,若不是,找出另一个更好的基本可行解,再进行检验.,如此迭代进行,则要么最终找到问题的最优解,要么判定原问题无界.,需解决的两个问题:,1.如何找到第一个初始的基本可行解?,2.如何判别当前基本可行解的最优性?或怎样对其进行修正?,考虑标准形式的LP问题:,(1),(3),(2),可行基B,设B由A的前m列组成,假定已找到问题(1)-(3)的一个非退化的基本可行解,即,由,或,典式,典则方程组,引入记号:,一般地,若,则上述典式对应于基本可行解,非退化基本可行解,常数项,目标函数的典式,检验数,令,对应于的检验数向量,对应于基本可行解,原标准形式(LP),基于该问题的系数,特别是的取值,有以下几种情形:,Proof:,Th1.最优性准则:若,则是原问题(LP)的最优解.,设为原问题的任一可行解,则由,由的任意性与最优解的定义,必为(LP)的最优解.,无界性,定义,Th2若向量的第k个分量,而对应的向量,则原问题(LP)无界.,Proof:,为中的第k个单位向量.,可行解,可无限下降,无下界!,换基:修改原来的基B得到一个新的基,一个新的可行解.,思想:从原来的非基变量中选取一个变量让其变为基变量.,保证新得到的解仍为基本可行解,丛原来的基变量中选一个让它变为非基变量,新基与原来的基仅有一个列向量不同,目的:保证可行性.目标函数下降,已知,对应的变量为非基变量:,变为基变量,其余的非基变量不变.,Th3.转换基依据(准则),Proof:,对于非退化的基本可行解,若,而其对应的向量中至少有一个正分量,则能找到一个新的基本可行解.,如对Th2的证明方法,令,令,只需找到这样的即可:,令,(),只须,故若,则可取任意的非负值,但若,则,则可保证.从而可行.,下证也是基本解.,只需证明线性无关!,若不然,因原来的线性无关,必可由其余m-1个向量线性表示,即个不全为零的数,而,线性相关.矛盾!,线性无关,为基本可行解!,因非退化,Remarks:,不过,若原(LP)是非退化的,则其任一个基本可行解均是非退化的,从而不会出现此问题.,1若在()中有N个比值同时达到最小值,则可选取其中任一个为“r”,但在新的基本可行解中,这些相应的分量均为零,从而是退化的基本可行解.,2检验数向量有不只一个正分量.,理论上任意可选取一个正分量作为定理中的,由Th3,目标函数的值减少,通常选取最大的那个,最大的未必对应最大的,而确定后,导致目标函数的实际减少量为!,即使所选的使这一步迭代目标函数值的下降量最大,但对从基本可行解开始以后的迭代未必为最好.,离基变量,基变量,非基变量,非基变量,基变量,基本可行解,“更好”的基本可行解,称为退出基列,称为进入基列,进基变量,Def.,单纯形方法迭代步骤:,步1:找一个初始的可行基B;,步2:求出对应的典式及检验数向量;,步3:求,步4:若,停止.已找到最优解,对应最优值为,步5:若,停止.原问题无界,步6:求,步7:以代替得到新的基,转步2.,收敛性:,Th4.:对任何非退化的LP问题,从任何基本可行解开始,经过有限次迭代,或得到一基本可行的最优解,或得出原LP无界.,单纯形法的实现:,单纯形表,计算机求解,二.初始解的确定,对于给定的LP问题，若A中已含有一个m阶的单位矩阵且b0，则已有一个明显的基本可行解。且方程组Ax=b已为典式。,将目标函数化为典式，则可直接开始单纯形迭代,1.两阶段法,思想：将LP问题的求解过程分成两个阶段：,第一阶段：判断LP是否有可行解。若没有，则无基本可行解，停止。若有，求得一个初始的基本可行解。,第二阶段：从第一阶段所得初始基本可行解开始，使用单纯形法求解原LP问题：或者求得一最优解，或者判定原LP问题无界。,设原LP问题为：,对此问题引入m个人工变量，并考虑如下的LP辅助问题：,D,D,m+n个变量的标准形式的LP!,两个问题之间的关系:,可通过求解辅助问题来寻求原LP问题的初始解,可行解,对于辅助问题:,约束方程组已为典式目标函数的表达式也易化为典式,可直接开始用单纯形法求解它!,辅助问题必存在最优解!,可行有界,求得的最优值不外乎两种可能:,Case1:,不存在,原问题不可行.stop,Case2:,依人工变量的取值情况,又可分为两种情形:,所有人工变量在辅助问题的最优基本可行解中均为非基变量,所有人工变量均取值为0,但有些人工变量仍为基变量,仍为基变量的人工变量,必有,考虑,特别是:,a)不全为0:存在.换基:,非基变量基变量,基变量非基变量,b)全为0:,重复上述过程,直至基变量中所有的人工变量均被消除,2.大M法,M相对于C,M为一充分大的正数.,为提高效率,在迭代过程中,一旦某一人工变量为非基变量,则立即删去.,三.退化的处理,OR在存在两个以上的r新的基本可行解一个或多个变量=0退化,换出的离基变量=0目标函数值不变,单纯形迭代回到前面某个基本可行解,可能不同的基表示同一顶点,换基后回到同一顶点,出现循环!,1.摄动法,2.Bland规则,b)离基变量,-下标最小的,Th.遵循上述Bland规则进行单纯形法迭代,就不会出现循环.,a)进基变量:下标最小的正检验数所对应的非基变量,3.字典序法,记为,若允许,则称为字典序非负.,If,则称是字典序负.If,则称按字典序大于,记为.,对一组,若有,使得,则称为该组向量中按字典序最小,记,Def.对,若其第一个非零分量是正数,则称为字典序正.,字典序法:,b)令这里表示的第i个行向量.,a)按,选定进基变量;,四.单纯形法的有效实现,1.修正单纯形法,标准单纯形法主要计算量为求逆,以下省去上标“k”,用上标“+”表示第k+1次迭代,设新的基阵是通过的列与的列而得到的,则由SM公式:,思想:利用ShermanMorison公式从上次迭代的基阵等直接逆推求基阵的逆等量,并避免计算,新的基本解,(1),(2),(3),记,称其为单纯形乘子,则,修正单纯形法一般迭代步的计算过程:,(1)由(2)式从计算,再由(3)式从求得.,(3)由(1)从计算.,(4)计算.若,可行域无界,终止;反之,(2)对,依次计算(检验数的第j个分量),若对,则终止,已找到最优解.,否则,按与标准单纯形法相同的准则确定入基变量的指标.以第一个使的指标作为入基变量的指标.,(5)确定出基变量如下:,计算量,运算次数比较:,单纯形表法:,修正单纯形表法:,通常,后者好!,五.稳定性与矩阵分解,对大型LP,许多次迭代误差积累太严重.,用(修正)单纯形法求解LP过程中,需直接或间接计算.若某次迭代中的条件数很大,近似奇异,则某些元素的绝对值很大.用其计算会把误差放大很大倍数.,对大型LP,A常为稀疏矩阵,若直接计算,往往破坏稀疏结构.,减少计算量,控制误差,增加算法稳定性采用B的LU或QR分解式.,LU分解法,设第k次迭代基矩阵的LU分解为,则在单纯形法中需计算的向量,这里为初等行交换矩阵,为单位下三角阵,为上三角矩阵,通过解方程组,若计算所得的基本可行解为非最优解,并确定新的入基变量为,出基变量为,它们对应的列向量分别记为.,令,记,的Hesianberg阵.,其中为形如:,为保证稳定性,必要时要进行行的交换(选主元).,为得到的LU分解式,需对作变换逐次消去第q列以后各列下次对角线上的非零元素.,对矩阵的变换包含一系列对为m阶单位下三角阵的第r列的矩阵进行修正,消去的第r个元素(设0):,若不作行交换,则,且由上式可直接求得而可由下列公式确定:,时无效,而在取较大值时不稳定,行变换,取,由上式求得,同样,上式在=0时无效,在或取最大值时不稳定,反之需作行交换,且选为主元.,确保修正过程数值上稳定的一个策略是在时不作行交换,即选为主元.,对矩阵(从的第q列,的第q行开始)逐次应用上述方法,为行交换阵!,由此即得LU分解式.,大型LP问题的分解方法,思想:把一个计算机难以求解的,或需花费很多计算时间的大型问题归结为若干较小的LP问题,从而显著的缩短计算时间.,这类方法依赖于问题的特定结构,两大类:关于变量分组,关于约束分组,Benders分解法,利用LP的对偶理论与多面体的对偶理论,DantzigWolfe分解,呈变量分离形式,网络流问题,有限资源分配问题,(1),嵌套分解法(nesteddecompositionmethod),思想:,反复使用DW分解法,动态问题,经济模型,DW分解法的有界情形,把问题(1)表达的更为一般,设为如下形式:,某个具有特定结构的多面凸集,(2),笛卡儿乘积空间,(3),Exp.:在问题(1)中令,X有界,(4),(5),它具有有限多个极点,且X可表示为这些极点的凸包:,若X的这些极点都已知,则问题(2)可改写为以为变量的下述问题:,常量常向量,主问题Masterprogram,特点:,1)问题(5)只有m+1个约束,若原来确定X要用许多个约束,则问题(5)比起原问题来,约束个数明显减少.,2)若能求出主问题的最优解,则显然得到了原问题(2)的最优解,3)这一想法粗看上去不现实,因为极点虽只有有限个,但对大型问题来说,它们的个数将是一个很大的数,主问题可能有很多的列,从而比起原问题(2)来,问题的规模非但没有减少,反而可能更大了.,4)要知道X的所有极点一般是不现实的!,DW方法的巧妙之处即在于,它利用(意识到):,a)并不需要用到主问题的所有列,而只需要知道其中很少一部分.,b)并该方法并不需要知道所有极点,而要用到的极点将在计算中自动生成.,现考虑用修正单纯形法求解主问题(5):,记已知初始基为,令,其中对应问题(5)的前一组约束标量对应问题(5)的约束,为检验当前这组解的最优性,考虑最大的检验数:,线性函数在有界多面凸集X上的最大值必在某极点上达到,(6)中的值恰好等于LP问题,的最优值,可利用单纯形法求解.,若需要比较所有的,必须知道所有的极点,则该法行不通!,(6),(7),若通过子问题(7)求得的,现在的基本可行解已经是最优解,问题(2)的最优解也就找到了.,若,与它对应的非基变量进基,的系数向量为其中就是达到(6)式中最大值的极点.显然,它就是子问题(7)的最优基本可行解,总能在用单纯形法求解子问题时得到所要的极点!,计算,令,来确定为离基变量,继续用修正单纯形法求解,得到主问题的另一个基本可行解及相对应的,完成一次迭代!,DW方法在主问题与子问题的求解之间循环反复地进行,直到求得主问题的最优解为止.,主问题的每次迭代计算出一组改进的可行解及其相应的变量,并把这组变量提供给子问题,以形成子