运筹学中的计算复杂性.ppt

第一阶段从形式语言形式语言 类的理论 第二阶段1971年 COOK在逻辑、递归理论的研究中发现了NP完全类，证明了适定性问题是NP完备的。,1、OR是计算复杂性的生成基础,从计算复杂性发展历史来看：,专题二 计算复杂性和运筹学,第三阶段从事OR研究的Karp在网络、组合优化方面颇有建树，在研究了判断逻辑表达式伪真的证明后，发现OR中（比如组合优化中）就有很多NP完全类，从而提供了计算复杂性理论的生成基础。,1、问题的提出,1947年Dantzig创立了单纯形法,1972年，VKlee & G.Minty构造了一个反例,它含有n个变量,m=2n个不等式约束,若用单纯形法求解,必须检验约束条件中不等式组所确定的凸多面体的所有顶点,才能获得最优解,计算次数等于2n -1,因此说明了单纯形法不是“好算法”!,二、椭球算法,这个著名的例子是：,图3 三维立方体及其摄动,1979年春，前苏联科学家（L.G.khachian）证明了： LP有一个多项式时间算法！ 其结果建立在其他数学工作者关于NLP工作的基础上,方法与以前解决LP的途径截然不同,几乎完全不管LP的组合性质.,那麽，能否找到一种解LP的多项式算法？,2、椭球算法的思想,对应的n阶方阵,而X(1)=0,E1是一个以X(1)为球心的n维超球.,首先提出了将求LP最优解归结为解严格不等式组的问题,解不等式组的多项式算法也是一种迭代算法,迭代的每一步都要产生一个点X(K)和以该点为中心的一个椭球EK=(X(K),BK),其中BK是与第K个椭球方程,(X-X(K)TBK(X-X(K)1,3、LP与线性不等式的关系,设要求的LP问题是:,对偶问题,若X、Y分别是它们的可行解，则由弱对偶定理，必有CXYb；由最优性准则定理：若X*，Y*分别是上述问题的可行解，且CX*=Y*b，则X*，Y*分别为（L）和（D）的最优解。,要求解（L），可以先解如下的线性不等式组：,若已求得（1）的一个最优解（X*，Y*），则X*就是（L）问题的一个最优解。若（1）无解，则问题（L）没有最优解。所以，求LP问题的最优解可以转化为求解线性不等式组（1）。而不等式组（1）总可以改写成如下形式：,证明了如果整系数不等式组 aiXbi+2*2-L i=1,m (3)有解,则整系数不等式组(2)也有解。其中，,其中,ai是系数矩阵的第i个行向量ai=(ai1,ai2, ain),bi是右端向量的第i个分量.,（4）,L大致等于把不等式组（2）的所有系数都化为二进制数时的位数，称L为问题（2）的输入长度，可大体上说明问题（2）的规模大小。,综上，求解LP（L）可以转化成求解不等式组：,（*）,4、(哈奇扬)算法的计算步骤,5、(哈奇扬)算法的几何解释,作一个椭球，将可行域所有顶点包住，看球心是否在可行域内部？如果不是，用分离定理作超平面，再作一个缩小了的椭球，把问题化为一个不等式组是否有解的问题。,（1）n=2时，严格不等式组为 ai1x1+ai2x2 bi i=1，m 其解集合为若干个半平面的公共部分。 用 表示原点（0，0）与点X=（x1，x2）之间的距离，即 = ，而 R代表以原点为圆心，R为半径的圆。,可以证明，如果有解，则在圆 2L内一定有的解，且的解集合在圆2L内的部分P的面积至少是 2-（n+1）L。,的解集合在圆 2L内的部分P的面积至少是 2-（n+1）L。,（L为输入长度，n为未知数个数，本例中n=2），如果迭代了6n2L次还没有找到的解，就可以判定一定没有解。,算法也是一种迭代算法，,在迭代过程中的每一个阶段都有一个以某一个点Xi为中心的椭圆Ei，第一个椭圆E1就是圆 2L ，它的中心X（1）是原点，迭代过程就是从X（1），E1得到X（2），E2，其特点是，事先可以肯定：最多迭代6n2L次。,（2）从X（i），Ei得到X（i+1），Ei+1的过程： 首先将X（i）代入不等式组中去试验，看是否满足，是，则X（i）就是的解，计算停止。 若不是，将X（i）=（x1（i），x2（i）代入中，至少有一个不等式不成立，不妨设为第r个，则有,ar1x1+ar2x2br,第一步，过椭圆的中心X（i）画一条直线l与直线ar1x1+ar2x2=br平行，就把椭圆Ei分成了两个“半椭圆”，设与Ei交于A、B两点。 第二步，再画直线l1 与l平行,且与椭圆Ei相切。要求l1和l要在直线ar1x1+ar2x2=br的两侧，设l1 与Ei相切于C点。 第三步，作椭圆Ei+1，满足： 经过A、B、C三个点； 与l1 相切于C点； 包含Ei被直线l 割出的介于l 与l1 的半个椭圆。,利用来构造新的椭圆：,ar1x1+ar2x2=br,A,B,C,l,图3 从X（i），Ei得到X（i+1），Ei+1的过程,l1,p,X(i+1),Xi,（4）综上，可以证明这种迭代方法最多只要进行6n2L次，其计算复杂性为O（6n2L2）。, Ei+1的面积=CEi的面积，其中0 C1，且 （n为不等式组中未知数的个数） 每一个Ei都包含解集合在圆 2L的部分P。,（3）用上述办法做出来的一系列椭圆有下面的关系：,（1）是理论上的重大突破；,6、对椭球算法的评价,（2）由此提出了许多新的研究课题,解决了LP理论上一个长期悬而未决的问题是否存在解LP的多项式算法？, 单纯形法不是多项式算法，为什麽用于解具体的LP却很有效？ Smale从概率论角度证明了单纯形法所需的计算步数的概率平均为O(m)，从而对算法分析产生深远影响。, 算法虽然是多项式算法，为什麽解具体问题并不十分有效？而且远不如单纯形法？ 解决问题的途径： A . 走 的路，继续进行改进试图寻找与L无关的强多项式算法； B . 改造单纯形法，试图使之成为好算法。 比如：设计各种行列法则，以寻求到达最优点的最短路；,二、Karmarkar算法,1、问题的提出,有无可能从目前的初始可行解通过可行域内部到达最优点，而不要先到边界上去？ 1955年 Frish找到了一个单调下降趋于零的非负序列，选目标函数及约束条件如下：,去掉变量的非负条件，走的路穿过多面体内部通向最优解，可惜的是：走得太慢，算法无效！但是人们发现，加上 函数，能改变方向进入内部，若能克服步长太小走得太慢的问题，把方向对准，步长加大，就有可能得到改善。,另外, 如果约束条件很多，接近一个球，而把初始点放在球心，则一步就可以到达最优点，因此可以想办法把约束条件规范化。,Karmarkar的贡献,1、找到了一种将约束标准化的投影变换； 2、定义了一个势函数 logxj ；,两者相结合生成一种新算法！,2、一些基本概念和重要结果,（1）Karmarkar 标准型,给定精度2-q，若找到了可行解X*，使得CX*2 - qCX0，则停止计算，X*就是最优解。,假设,目标函数的最小值Z*=0；,R=S，单纯形S的中心 X0=（1，1，1）T/n =e/n R使得AX0=0；,或,Karmarkar 标准型,其中： X=（ ）T， e = (1 , 1 , , 1 )T,(2) Karmarkar 方法的势函数:,(3)投影变换,S到S的投影变换T: X=D-1X / eTD-1X 或,其中 D=,给定可行域（超凸多面体）P的一个内点a=(a1,an)T,即aP,且a0,首先通过一个投影变换把P和a分别变成S和a,使a是S的中心,