《发展史》由会员分享，可在线阅读，更多相关《发展史（10页珍藏版）》请在金锄头文库上搜索。
1、3.3.2 线性规划发展史 及其简单的应用,主讲：王春梅,线性规划的简介及其发展,线性规划的简介 线性规划是运筹学中研究较早、发展较快、应用广泛、 方法较成熟的一个重要分支，它是辅助人们进行科学管理 的一种数学方法。研究线性约束条件下线性目标函数的极 值问题的数学理论和方法，英文缩写LP。它是运筹学的一 个重要分支，广泛应用于军事作战、经济分析、经营管理 和工程技术等方面。为合理地利用有限的人力、物力、财 力等资源作出的最优决策，提供科学的依据。一般地，求 线性目标函数在线性约束条件下的最大值或最小值的问题， 统称为线性规划问题。满足线性约束条件的解叫做可行解， 由所有可行解组成的集合叫做可行
2、域。决策变量、约束条 件、目标函数是线性规划的三要素.,数学模型 （1）列出约束条件及目标函数 （2）画出约束条件所表示的可行域 （3）在可行域内求目标函数的最优解及 最优值,发展,法国数学家J.- B.- J.傅里叶和C.瓦莱普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。 1939年苏联数学家.康托罗维奇在生产组织与计划中的数学方法一书中提出线性规划问题，也未引起重视。 1947年美国数学家G.B.Dantzing提出求解线性规划的单纯形法，为这门学科奠定了基础。 1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和
3、解题能力。 1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。,50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等。 线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几
4、千个变量的线性规划问题。,1979年苏联数学家L. G. Khachian提出解线性规划问题的椭球算法，并证明它是多项式时间算法。 1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大。,简单线性规划讲解,例1.解下列线性规划问题： （1）求z=2x+y的最大值，使x、y满足约束条件,（2）求z=3x+5y的最大值和最小值，使x、y满足约束条件,练习： 1.设变量x、y满足约束条件 ,则目标函数 z=4x+y的最大值是多少？,2.设变量x、y满足约束条件 ,则目标函数 z=x-3y的最小值是多少？,
