线性规划的单纯形方法
出处：按学科分类—自然科学总论 北京出版社《现代科技综述大辞典上》第106页（4298字）
单纯形方法是计算线性函数在凸多面体集合S上极值点的算法。
其中S=｛x｜Ax=bx≥0，x∈Rn｝，A和b分别是给定mxn短阵和m维向量。它首先是寻找S的一个顶点(基本可行解)或确定S是空集。然后从S的一个顶点按某种规则沿棱搜索至另一顶点，产生目标函数值为单调的路径，使其终止于极值点，或是终止一顶点，它是使目标函数值为无界的极射线的端点。
单纯形方法是求解线性规划问题和研究凸多面体几何的有效工具，也是研究科学决策的重要手段。
它被广泛应用于工业、军事、经济计划、交通、能源、资源分配、城市规划和科学管理等方面。也是运筹学、管理科学、数值最优化和计算机科学等学科的重要组成部分，对它们的发展也有重要的影响。
1947年丹特齐格(G．B．Dantzig)设计求解线性规划的单纯形方法。实际上先前的许多数学家和经济学家在凸多面体几何、代数、最优化和经济模型等方面研究了类似的问题和求解方法。1826年傅立叶(J．B．J．Fourier)在研究超定线性方程组的无穷模极小值时，应用从凸多面体一个顶点至另一顶点的下降法已蕴含着单纯形方法的主要思想，也是最早涉及的线性规划问题。1894年福尔卡什(Gy．Farkas)论述齐次线性不等式组解的存在性条件中已孕育着线性规划的对偶原则。1939年康托洛维奇(L．V．Kantorovich)在研究生产组织和计划中的数学方法时已应用了对偶单纯形方法。希契科克(F．L．Hichcock)和库普曼斯(Tj．C．Koopmans)也分别于1941年、1948年在对运输问题静态模型的研究中应用单纯形方法的原则。
1947年冯·纽曼(Von Neumann)研究经济增长模型时指出Max｛cx｜x≥0，Ax≤b｝和不等式组x≥0，Ax≤b，yA≥c，y≥0，cx≥yb之间的等价性。这就是1951年由盖尔(D．Gale)、库恩(H．W．Kuhn)和塔克(A．W．Tucker)严格证明的线性规划对偶定理。它不仅是单纯形方法的理论基础，也对线性和非线性规划的发展产生深刻的影响。1953年丹特齐格和奥查德－海斯(W．Orchard-Hays)设计修正单纯形法。1954年莱姆基(C．E．Lemke)和比尔(E．M．L．Beale)独立提出对偶单纯形法。1956年丹特齐格、福特(L．R．Ford)和富尔科森(D．R．Fulkerson)推出原始对偶单纯形方法。
在数值计算方面，单纯形方法主要是研究进出基变量的转轴规则、基矩阵逆的计算及其数值稳定性和算法的有效性等。它与计算机、稀疏矩阵计算的发展密切相关。
转轴规则的研究包含退化和非退化。
1952年查尼斯(A．Charnes)、丹特齐格和他的学生在研究退化问题中独立应用不同的扰动规则，并以字典序方法证明其迭代有限终止。1977年布兰德(R．G．Bland)用组合规则从最小下标中选取进出基变量方法，避免无限循环。图纶、对偶方法也被应用于研究退化问题。
对非退化问题，1977年戈德法布(D．Goldfarb)和里德(J．K．Reid)研究丹特齐格等人提出的几种主要转轴规则的结果表明它们的效率几乎是相同的。
对基矩阵逆的计算，1954年丹特齐格和奥查特－海斯给出逆的初等矩阵乘积形式，并以重新求逆避免由迭代次数增大引起舍入误差积累的数值不稳定性。1957年马尔科维奇(H．M．Markowitz)采用重新排列基矩阵行列的顺序，使重新求逆后的初等矩阵乘积形式有较好的稀疏性。1969年戈卢布(G．N．Golub)和巴特尔斯(R．H．Bartels)应用LU分解表示基矩阵(L、U分别是上、下三角矩阵)，它具有更好的稀疏性质。
1971～1972年黑勒曼(E．Hellerman)和巴里克(D．Barick)综合上述两方法的优点在重新求逆中予选部分主元，使分解有良好的数值稳定性和稀疏性。随后许多学者都致力于对转轴迭代中如何保持基矩阵分解的三角形式、稀疏性和数值稳定性等方面的研究，并取得很大的进展。
许多研究结果被应用于研制软件包。如IBM公司的MPSX｜370，CDE公司的APEX Ⅲ和斯坦福大学的MINOS等。
对求解系数矩阵有特殊结构线性规划问题单纯形方法的研究，其一是对基矩阵分解、修正等采用特殊计算技术，它比直接应用单纯形法更有效。其二是应用1960年丹特齐格和沃尔夫(P．Wolfe)的分解原则导出的分解算法，把原来问题转化为一系列独立的小问题求解。80年代以来由于并行体系结构计算机的迅速发展，分解算法及其并行化的研究受到广泛的重视。许多研究结果说明其有非常明显的实际有效性。
自50年代以来，许多学者从多方面致力于单纯形方法有效性的研究。考察求解大量实际问题的数值经验和应用蒙特卡罗方法进行数值试验的结果，表明单纯形方法平均转轴迭代的次数一般是am(2≤a≤6)。另一方面，1957年赫希(W．H．Hirsch)提出凸多面体直径d(连接任意二顶点最短路径的最大值)，并猜测d不超过其不等式个数与维数之差。
显然d是单纯形法通过顶点路径的最大数。
研究证实赫希猜测对特殊类凸多面体是正确的，一般说是不成立的。1981～1988年奥林(J．B．Orlin)、巴林斯基(M．L．Brlinski)和戈德法布等人分别证明应用对偶单纯形法和单纯形法求解最小价格网络流量和分配问题的迭代次数是多项式的。这是有重要意义的。1972年克莱(V．Klee)和明蒂(G．J．Minty)首次给出丹特齐格转轴规则单纯形法和迭代次数是指数函数的线性规划问题。相继的研究证明其它转轴规则的算法的迭代次数也是指数函数。
由算法的复杂性理论，人们怀疑线性规则是否属于P类问题?1979年哈齐扬(L．G．Khachiyan)用椭球方法证明存在求解线性规划问题的多项式时间算法。理论上确立了线性规划问题是属于P类。1984年卡玛卡(N．Karmarkar)提出多项式时间的内点方法，它在算法复杂性和实际有效性方面都有很大进展。
它对单纯形法的研究有重要的影响。
平均复杂性是刻划单纯形方法有效性的另一尺度。它是应用概率分析方法对按照某类分布输入线性规划问题的数据，计算其转轴迭代次数的期望值。1982年博格瓦特(K．H．Borgwardt)证明在一定概率模型假设下一种转轴规划单纯形法的平均迭代次数是多项式的。
1983年斯梅尔(S．Smale)应用不同概率模型和转轴规则证明对固定m，Max｛cx｜x≥0，Ax≤b｝的平均迭代次数上界是0((logn)m2+m)，同年海孟维奇(M．Haimovich)对更一般的斯梅尔模型证明博格瓦特转轴规则的平均迭代次数是线性的。随后陶德(M．J．Todd)等在较强的假设条件下证明平均复杂性是二次函数的模型。
概率分析方法对揭示单纯形方法的本性有一定的作用。然而如何使研究的模型能客观地反映实际问题还面临着不少困难。
在数值计算方面今后单纯形方法主要是研究求解超大规模线性规划问题的稀疏矩阵技术(包括舍入误差分析、病态现象和稳定性等问题)和退化问题的处理。
并行计算技术的发展为大幅度提高单纯形方法的效率带来希望，新的并行化的单纯形算法和对特殊结构问题的并行化算法的研究将受到重视。
内点方法近年来取得的进展将推动内点－单纯形混合型算法的研究。对概率分析方法的研究会有进一步的发展。
若能在强多项式复杂性的单纯形类新算法的研究取得进展，它对理论研究和实际应用将产生重要的影响。
。【参考文献】：1 Dantzig G B. Linear Programming and Extensions. Princeton Princeton University Press, 1963
2 Hellerman E ,et al. Mathematical Programming, 1971,1; 195～215
3 Klee V ,et al. 3 - rduSympos. Inequalities,AP, New York: 1972,159～175
4 Bland R G. Mathematicsof Operations Research, 1977, 2: 103～107
5 Khachiyan L G. Dokla Akad,Nauk USSR, 1979,244(5): 1093～ 1096
6 Borgwardt K H. Princeton University PressZeitscherft for Operations Research, 1982,26:157～177
7 Murtagh B A, et al. Technical Report SOL 83-20,Dept. of Operations Research, Stanford:Stanford University 1983
8 Karmarkar N. Combinatorica 1984,4:373～395
9 Ho J K, et al. Mathematical programming 1989,42:391～ 405
10 Todd M J. Mathematical Programming, K T K Scientific Publishers,Tokyo,1989,109～157
(中国科学院计算数学与科学工程计算所魏紫銮副研究员撰)