线性规划问题的求解方法及在经济上的应用

《线性规划问题的求解方法及在经济上的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要线性规划是运筹学的一个基本分支，其应用极其广泛，其作用已为越来越多的人所重视，越来越急速地参透于工农业生产，商业活动，军事行动和科学研究的各个方面。它是应用分析、量化的方法、对经济管理系统中的人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现有效管理。它广泛应用现有的科学技术和数学方法，解决实际中的问题，帮助决策人员选择最优方针和决策。线性规划的理论和方法在实际应用中非常广泛，具有很高的实用价值。本文由以下三部分组成的：第一部分初步介绍了线性规划产生的历史背景，发展概况，线性规划问题的数学模型及标准形式和线性规划问题中的基本概念；第二部

2、分介绍了线性规划问题中多使用的求解方法其中包括图解法，单纯形法，两阶段法和对偶单纯形法，并对这四种方法进行了举例说明；第三部分介绍了线性规划的实际应用尤其是在经济上的应用。关键词：线性规划；图解法；单纯形法；对偶单纯形法；经济应用目录31第一章引言31.1线性规划发展概述31.2线性规划问题中的基本概念：41.3线性规划问题的数学模型及标准形式：7第二章线性规划问题的求解方法102.1图解法102.2单纯形法132.3对偶单纯形法19第三章线性规划在经济上的应用23结束语29参考文献30致谢3131第一章引言线性规划是运筹学中研究较早、发展较快、应用广泛、方法

3、较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法。在各类生产管理和经营活动中,经常会遇到两类问题:一类是(资源有限)如何合理的使用现有的劳动力、设备、资金等资源,以得到最大的效益；另一类是(目标一定)为了达到一定的目标应如何组织生产或合理安排工艺流程或调整产品的成分等以使所消耗的资源(人力、设备台时、资金、原材料等)为最少，这样的问题常常可以化成或近似地化成所谓的“线性规划”，简记为LP问题。线性规划的基本特点是：目标函数和所有的约束条件都是线性的，所追求的是在满足约束条件的前提下,实现目标函数的最优化。线性规划已不仅仅是一种数学理论和方法，而且成

4、了现代化管理的重要手段，是帮助管理者与经营者做出科学决策的一个有效的数学技术。1.1线性规划发展概述法国数学家J.-B.-J.傅里叶和C.瓦莱-普森分别于1832和1911年独立地提出线性规划的想法,但未引起注意。1939年苏联数学家Л.В.康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题也未引起重视。1947年美国数学家G.B.丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法单纯形法，为这门学科奠定了基础。1947年美国数学家J.von诺伊曼提出对偶理论，31开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。1951

5、年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如：1954年C.莱姆基提出对偶单纯形法。1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题。1956年A.塔克提出互补松弛定理,1960年G.B.丹齐克和P.沃尔夫提出分解算法等。1979年苏联数学家L.G.Khachian提出解线性规划问题的椭球算法，并证明它是多项式时间算法。1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用

6、这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大，建立线性规划模型的方法。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划，随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX,OPHEIE,UMPIRE等可以很方便地求解几千个变量的线性规划问题。1.2线性规划问题中的基本概念：线性规划问题31求解线性规划问题，就是从满足约束条件（1-2），（1-3）的方程组中找出一个解，使目标函数（1-1）达到最大值。可行解：满

7、足上述约束条件（1-2），（1-3）的解称为线性规划的可行解。可行域：所有可行解的集合称为可行域。最优解:使目标函数（1-2）达到最大值的可行解，称为为线性规划的最优解。线性规划最优解的几种情况：   ①线性规划有最优解时，可能有唯一最优解，也可能有无穷多个最优解，但当最优解不唯一时，一定有无穷多个最优解。   ②线性规划没有最优解时，也有两种情况，一是可行域为空集，二是目标函数值无界（求最大时无上界，求最小时无下界）。   ③有界可行集必有最优解。   ④当线性规划有最优解时，一定可以在可行域的某个极点上取到，当有唯一解时，最优解就是可行域的某个极点。当有无

8、穷多个解时，其中至少有一个是可行域的一