1、最突出的就是最突出的就是8080年代以来产生的年代以来产生的哈奇扬哈奇扬（）算法和卡马卡）算法和卡马卡（KarmarkarKarmarkar）算法）算法。第三阶段第三阶段从事从事OROR研究的研究的KarpKarp在网络、在网络、组合优化方面颇有建树，在研究了判断逻组合优化方面颇有建树，在研究了判断逻辑表达式伪真的证明后，发现辑表达式伪真的证明后，发现OROR中（比如中（比如组合优化中）就有很多组合优化中）就有很多NPNP完全类，从而提完全类，从而提供了计算复杂性理论的生成基础。供了计算复杂性理论的生成基础。19471947年年DantzigDantzig创立了单纯形法创立了单纯形法 1972
2、1972年，年，V VKlee&G.MintyKlee&G.Minty构造构造了一个反例了一个反例,它含有它含有n n个变量个变量,m=2n,m=2n个个不等式约束不等式约束,若用单纯形法求解若用单纯形法求解,必须必须检验约束条件中不等式组所确定的凸检验约束条件中不等式组所确定的凸多面体的多面体的所有顶点所有顶点,才能获得最优解才能获得最优解,计算次数等于计算次数等于2 2n n-1-1,因此说明了因此说明了 djsrxdjsxxrxxsxrxtsxZjjjjjjjjjd,10,3,2101.max111111 这个著名的例子是：这个著名的例子是：图图3 3 三维立方体及其摄动三维立方体及其摄
3、动X3 x1 x2 1979年春，前苏联科学家年春，前苏联科学家（L.G.khachian）证明了：）证明了：其结果建立在其他数学工作者关于其结果建立在其他数学工作者关于NLP工作的基础上工作的基础上,方法与以前解决方法与以前解决LP的的途径截然不同途径截然不同,几乎完全不管几乎完全不管LP的组合性的组合性质质.对应的对应的n n阶方阵阶方阵,而而X X(1)(1)=0,E=0,E1 1是一个以是一个以X X(1)(1)为为球心的球心的n n维超球维超球.首先提出了首先提出了将求将求LPLP最优解归最优解归结为解严格不等式组的问题结为解严格不等式组的问题,解不等式组的多解不等式组的多项式算法也
4、是一种项式算法也是一种,迭代的每一步都迭代的每一步都要产生要产生,其中其中B BK K是与第是与第K K个椭球方程个椭球方程 0.min)(XbAXtsCXZL 0.max)(YCYAtsYbWD 若若X X、Y Y分别是它们的可行解，则由弱对偶分别是它们的可行解，则由弱对偶定理，必有定理，必有CXYbCXYb；由最优性准则定理：若；由最优性准则定理：若X X*，Y Y*分别是上述问题的可行解，且分别是上述问题的可行解，且CXCX*=Y=Y*b b，则，则X X*，Y Y*分别为（分别为（L L）和（）和（D D）的最优解。）的最优解。要求解（要求解（L L），可以先解如下的线性不等式组：），
5、可以先解如下的线性不等式组：AXbAXb X0X0 YAC YAC （1 1）Y0Y0 CXYbCXYb 若已求得（若已求得（1 1）的一个最优解（）的一个最优解（X X*，Y Y*），则），则X X*就是（就是（L L）问题的一个最优解。）问题的一个最优解。若（若（1 1）无解，）无解，则问题（则问题（L L）没有最优解）没有最优解。所以，求。所以，求LPLP问题的最问题的最优解可以转化为求解线性不等式组（优解可以转化为求解线性不等式组（1 1）。而不）。而不等式组（等式组（1 1）总可以改写成如下形式：）总可以改写成如下形式：（1 1）-AX-b-AX-b -X0 -X0 YAC YAC
6、-Y0 -Y0 CX-Yb0CX-Yb0为了书写简洁为了书写简洁,总可以将总可以将(1)(1)写为下面的形式写为下面的形式:a ai iXbXbi i i=1,2,i=1,2,m,m(2)(2)证明了如果整系数不证明了如果整系数不等式组等式组 a ai iXbX0,a0,通过一个投通过一个投影变换把影变换把P P和和a a分别变成分别变成S S和和a a,使使a a是是S S的中心的中心,而且以而且以a a为中心包含为中心包含S S的最小球的半径与以的最小球的半径与以a a为中心包含在为中心包含在P P中的最大球的半径之比为中的最大球的半径之比为O(n)O(n),在变换之后的以在变换之后的以a a为心的球上为心的球上,求得求得LPLP的的解为解为b b,利用投影变换把利用投影变换把bb返回到原决策返回到原决策空间中去空间中去.计算复杂性为计算复杂性为O(nO(n4 4L L2 2)，若采用某些技巧则可达到若采用某些技巧则可达到O(nO(n3.53.5L L2 2)。（略）（略）
