线性规划的单纯形法及其应用+文献综述(2)
美国数学家G.B.Dantzing1947年提出求解线性规划的单纯形法，为这门学科奠定了基础。
美国数学家J.von诺伊曼1947年提出对偶理论, 扩大了它的应用范围和解题能力，开创了线性规划的许多新的研究领域。
美国经济学家T.C.库普曼斯1951年把线性规划应用到经济领域，并且与康托罗文奇一起获得了1975年诺贝尔经济学奖。
50年代后涌现出许多人对线性规划进行了大量的理论研究，出现一大批新的算法。例如， C.莱姆基1954年提出对偶单纯形法， S.加斯和T.萨迪等人1954年解决了线性规划的灵敏度分析和参数规划问题， A.塔克1956年提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等。
苏联数学家L. G. Khachian1979年提出解线性规划问题的椭球算法，并证明它是多项式时间算法。
美国贝尔电话实验室的印度数学家N.卡马卡1984年提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数只要单纯形法所用时间的1/50。如今的理论已经形成线性规划多项式算法这一理论。1950年后线性规划的应用范围不断扩大。
单纯形法作为解决线性规划问题的最基本解法，掌握好单纯形法就能更有效快速地解决线性规划问题。这个线性规划单纯形解法的基本思路是：先求得一个初始基可行解，以这个初始基可行解在可行域中对应的极点为出发点，根据最优准则判断这个基可行解是否是最优解，如果不是转换到相邻的一个极点，即得到一个新的基可行解，并使目标函数值下降，这样重复进行有限次后，可找到最解或判断问题无最优解[2]。相对于传统的利用高斯消去法解决的单纯形法而言，美国数学家G.B.丹齐克在1953年改进的单纯形法在很大程度上减少了数据的冗杂和运算过程中的不必要数据的产生，为解决线性规划问题提供了极大便利。单纯形法有效地提高了数学规划的应用。由于线性规划的实际应用优势明显，一经提出就得到人们的青睐。这是因为，单纯形算法的计算方法简洁明了，通过单纯形法得到的结果精确有效，通过单纯形法所求出的最优解，得到人们的认可。
线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。鉴于线性规划的明显优势，这些后来兴起的问题都得到了人们的巨大的关注。为了简单地解决线性规划的问题，我们可以利用各种软件来对线性规划进行求解，例如MATLAB和LINGO。但是这两款软件并不是专门设计来解决线性规划。由于人们的需求和电子计算机的发展，涌现出现了许多专门解决线性规划的软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题。线性规划的提出最终还是为了更好地解决各个领域中存在的问题，所以线性规划的应用显得尤为重要，快速解决线性规划问题的求解也迫在眉睫，利用软件的求解能大大缩短线性规划问题解决的时间，为更好地解决线性规划问题带来无穷益处。
2 线性规划模型、单纯法及其改进
1.1线性规划模型[3]
例：实际生活中经常会遇到如何有效地分配现有资源，以期获得最佳的效果。
资源利用问题
某厂计划在一个生产周期内生产 共 种产品，要消耗 共 种资源，已知每件产品所消耗的资源数、每种资源的数量限制以及每件产品的利润如下表所示。问如何安排生产计划，才能使总利润最大？
单位消耗 产品
资源 资源限制单位利润
设安排生产产品 的生产量为 （决策变量）， 。建立的模型如下：
上一篇：LDA模型网络微博话题相关性分析