线性规划理论及其应用开题报告

《线性规划理论及其应用开题报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、开题报告线性规划理论及其应用一、选题的背景、意义[1][2]1.选题的背景线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法。在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束

2、条件下的最大化或最小化的问题，最大化问题是要在一个集合上使一个函数达到最大，最小化问题是要在一个集合上使一个函数达到最小。统称为线性规划问题。满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素。随着计算机技术的发展和普及，线性规划的应用越来越广泛。它已成为人们为合理利用有限资源制定最佳决策的有力工具。2.选题的意义随着计算机技术的发展和普及，线性规划的应用越来越广泛。它已成为人们为合理利用有限资源制定最佳决策的有力工具。随着经济全球化的不断发展，企业面临更

3、加激烈的市场竞争。企业必须不断提高盈利水平，增强其获利能力，在生产、销售、新产品研发等一系列过程中只有自己的优势，提高企业效率，降低成本，形成企业的核心竞争力，才能在激烈的竞争中立于不败之地。过去很多企业在生产、运输、市场营销等方面没有利用线性规划进行合理的配置，从而增加了企业的生产，使企业的利润不能达到最大化。在竞争日益激烈的今天，如果还按照过去的方式，是难以生存的，所以就有必要利用线性规划的知识对战略计划、生产，销售各个环节进行优化从而降低生产成本，提高企业的效率。在各类经济活动中，经常遇到这样的问题：在生产条件

4、不变的情况下，如何通过统筹安排，改进生产组织或计划，合理安排人力、物力资源，组织生产过程，使总的经济效益最好。这样的问题常常可以化成或近似地化成所谓的“线性规划”(LinearProgramming，简记为LP)问题。线性规划是应用分析、量化的方法，对经济管理系统中的人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现有效管理。利用线性规划我们可以解决很多问题。如：在不违反一定资源限制下，组织安排生产，获得最好的经济效益(产量最多、利润最大、效用最高)。也可以在满足一定需求条件下，进行合理配置，使成

5、本最小。同时还可以在任务或目标确定后，统筹兼顾，合理安排，用最少的资源(如资金，设备，原材料、人工、时间等)去完成任务。二、研究的基本内容与拟解决的主要问题2.1线性规划理论发展过程及方向2.1.1线性规划发展过程[3][4]法国数学家J.-B.-J.傅里叶和C.瓦莱－普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。1939年苏联数学家Л.В.康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题，也未引起重视。1947年美国数学家G.B.丹奇克提出线性规划的一般数学模型和求解线性规划

6、问题的通用方法──单纯形法，为这门学科奠定了基础。1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P

7、.沃尔夫提出分解算法等。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题。1979年苏联数学家L.G.Khachian提出解线性规划问题的椭球算法，并证明它是多项式时间算法。1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现

8、已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大。2.1.2线性规划理论的发展方向[5][6][7]线性规划在军事、工农业、交通和城镇规划等领域中得到广泛的应用。实际问题有的是很大的，大到具有几万、几十万甚至上百万的变量和成千上万的约束条件。有的问题虽小些，一般也有几百几千的变量和成百上千的约束条件。显然解这类问题都离不开计算