线性规划发展史及简单的线性规划-课件【PPT演讲稿】.ppt

文档介绍：§ 线性规划发展史及其简单的应用主讲:王春梅线性规划的简介及其发展?线性规划的简介线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法,英文缩写 LP。它是运筹学的一个重要分支,广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策,提供科学的依据。一般地,求线性目标函数在线性约束条件下的最大值或最小值的问题, 统称为线性规划问题。满足线性约束条件的解叫做可行解, 由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素. ?数学模型?(1)列出约束条件及目标函数?(2)画出约束条件所表示的可行域?(3)在可行域内求目标函数的最优解及最优值发展?法国数学家 J.- B.- J. 傅里叶和 -普森分别于 1832 和 1911 年独立地提出线性规划的想法,但未引起注意。? 1939 《生产组织与计划中的数学方法》一书中提出线性规划问题,也未引起重视。? 1947 年美国数学家 提出求解线性规划的单纯形法, 为这门学科奠定了基础。? 1947 年美国数学家 诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域,扩大了它的应用范围和解题能力。? 1951 年美国经济学家 . 库普曼斯把线性规划应用到经济领域,为此与康托罗维奇一起获 1975 年诺贝尔经济学奖。? 50年代后对线性规划进行大量的理论研究, 并涌现出一大批新的算法。例如, 1954 年 , 1954 年 , 1956 年 , 1960 年 . 丹齐克和 。?线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展,出现了许多线性规划软件,如 MPSX , OPHEIE , UMPIRE 等,可以很方便地求解几千个变量的线性规划问题。? 1979 年苏联数学家 L. G. Khachian 提出解线性规