运筹学中的计算复杂性(2)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一阶段,从形式语言形式语言,类的理论,第二阶段,1971,年,COOK,在逻辑、递归理论的研究中发现了,NP,完全类，证明了适定性问题是,NP,完备的。,1,、,OR,是计算复杂性的生成基础,从计算复杂性发展历史来看：,专题二,计算复杂性和运筹学,1,2,、,OR,对计算复杂性产生极大影响,最突出的就是,80,年代以来产生的,哈奇扬（,）算法和卡马卡（,Karmarkar,）算法,。,第三阶段,从事,OR,研究的,Karp,在网络、组合优化方面颇有建树，在研究了判断逻辑表达式伪真的证明后，发现,OR,中（比如组合优化中）就有很多,NP,完全类，从而提供了计算复杂性理论的生成基础。,2,1,、问题的提出,1947,年,Dantzig,创立了单纯形法,1972,年，,V,Klee&G.Minty,构造了一个反例,它含有,n,个变量,m=2n,个不等式约束,若用单纯形法求解,必须检验约束条件中不等式组所确定的凸多面体的,所有顶点,才能获得最优解,计算次数等于,2,n,-1,因此说明了,单纯形法不是,“,好算法,”,!,二、椭球算法,3,这个著名的例子是：,4,图,3,三维立方体及其摄动,X,3,x,1,x,2,5,1979,年春，前苏联科学家,（,L.G.khachian,）证明了：,LP,有一个多项式时间算法！,其结果建立在其他数学工作者关于,NLP,工作的基础上,方法与以前解决,LP,的途径截然不同,几乎完全不管,LP,的组合性质,.,那麽，能否找到一种,解,LP,的多项式算法,？,6,2,、椭球算法的思想,对应的,n,阶方阵,而,X,(1),=0,E,1,是一个以,X,(1),为球心的,n,维超球,.,首先提出了,将求,LP,最优解归结为解严格不等式组的问题,解不等式组的多项式算法也是一种,迭代算法,迭代的每一步都要产生,一个点,X,(K),和以该点为中心的一个椭球,E,K,=(X,(K),B,K,),其中,B,K,是与第,K,个椭球方程,(X-X,(K),),T,B,K,(X-X,(K),)1,7,3,、,LP,与线性不等式的关系,设要求的,LP,问题是,:,对偶问题,8,若,X,、,Y,分别是它们的可行解，则由弱对偶定理，必有,CXYb,；由最优性准则定理：若,X,*,，,Y,*,分别是上述问题的可行解，且,CX,*,=Y,*,b,，则,X,*,，,Y,*,分别为（,L,）和（,D,）的最优解。,要求解（,L,），可以先解如下的线性不等式组：,AXb,X0,YAC,（,1,）,Y0,CXYb,9,若已求得（,1,）的一个最优解（,X,*,，,Y,*,），则,X,*,就是（,L,）问题的一个最优解。,若（,1,）无解，则问题（,L,）没有最优解,。所以，求,LP,问题的最优解可以转化为求解线性不等式组（,1,）。而不等式组（,1,）总可以改写成如下形式：,（,1,）,-AX-b,-X0 YAC -Y0 CX-Yb0,10,为了书写简洁,总可以将,(1),写为下面的形式,:,a,i,Xb,i,i=1,2,m,(2),证明了如果整系数不等式组,a,i,X0,首先,通过一个投影变换把,P,和,a,分别变成,S,和,a,使,a,是,S,的中心,而且以,a,为中心包含,S,的最小球的半径与以,a,为中心包含在,P,中的最大球的半径之比为,O(n),然后,在变换之后的以,a,为心的球上,求得,LP,的解为,b,接着,利用投影变换把,b,返回到原决策空间中去,.,3,、,Karmarkar,算法的基本思想,30,计算复杂性为,O(n,4,L,2,),，,若采用某些技巧则可达到,O(n,3.5,L,2,),。,4,、,Karmarkar,算法的基本步骤,（略）,5,、简单的算法分析和算法评价,31,