线性规划在数学建模中的应用.doc

《线性规划在数学建模中的应用.doc》由会员分享，可在线阅读，更多相关《线性规划在数学建模中的应用.doc（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date线性规划在数学建模中的应用线性规划在数学建模中的应用线性规划在数学建模中的应用摘要：线性规划是运筹学中发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法，英文缩写LP。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力

2、、财力等资源作出的最优决策，提供科学的依据。本文在阅读了大量材料的基础上，集中体现了线性规划是如何应用到数学建模中去的。并且在利用数学建模的思想以线性规划为工具可以解决哪些实际问题，为我们的生活提供哪些便利。本文大体上可分为三章，第一章主要对线性规划和数学建模这两个理论做简要描述。并且叙述这两个理论的发展历程，以及研究的背景及意义。第二章主要介绍线性规划在数学建模中的应用，其中包括现在性规划在物流运输中的应用，线性规划在经济生活中的应用，以及线性规划在现代管理中的应用，并且配备了相应的例子。第三章主要讨论线性规划在实际应用方面应注意哪些细节，并对第二章的数学模型进行优化，以及对最优解方面的讨论

3、。关键词：线性规划 数学模型 物流运输 经济生活 现代管理Abstract:Linear programming is developed rapidly and widely applied in operational research, the method is an important branch of mature, it is one of the scientific management of auxiliary people mathematical method. Study of linear objective function under the linear c

4、onstraint condition extremum problems of mathematics theory and method of LP abbreviations. It is an important branch of operational research, widely used in military, economic analysis, management and engineering technology, etc. For reasonable use of the limited manpower and material resources, fi

5、nancial resources and other resources to make the optimal decision, provide the scientific basis.In this paper, on the basis of reading a lot of material, how concentrated the linear programming is applied to the mathematical modeling. And in using the ideas of mathematical modeling by means of line

6、ar programming can solve practical problems, which provide which is convenient for our life. The article in general can be divided into three chapters, the first chapter mainly on linear programming and mathematical modeling the two theories are described briefly. And the development of the two theo

7、ries, as well as the research background and significance. The second chapter mainly introduces the application of linear programming in mathematical modeling, including the planning in the application of logistics transportation, now the application of linear programming in economic life, as well a

8、s the application of linear programming in the modern management, and equipped with corresponding examples. The third chapter mainly discuss details which should be paid attention to in practical application of linear programming, and optimize the mathematical model of the second chapter, and the op

9、timal solution for the discussion.Keywords: Linear programming Mathematical model Logistics transportation The economic life Modern management 第一章 绪论1.1研究背景以及意义 1.1.1研究背景 1.1.2研究意义 研究线性规划在数学建模中的应用其理论意义主要在于利用数学建模的手段，为线性规划更好的应用于显示生活中提供理论依据。而为了更好的完成这项工作，需要查阅大量的相关资料，理论意义也在于总结整理前人的研究成果，并在某种程度上加以创新，如线性规划在

10、数学建模中的约束条件，什么情况下利用线性规划进行数学建模更为合理等。研究线性规划在数学建模中的现实意义有很多，因为一个数学理论要想应用到现实中去就必须要建立数学模型去解决。而线性规划作为运筹学中的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。因此，研究线性规划在数学建模中的应用就可以将数学理论更好的，更有效的，更完美的运用到现实生活中去，为我们的生活提供便利。-第二章 线性规划理论简述2.1 理论的渊源及演进过程 （1）线性规划理论发展的萌芽期法国数学家J.- B.- J.傅里叶和C.瓦莱普森分别于

11、1832和1911年独立地提可解的问题会有一个简单多边形的可行域出线性规划的想法，但未引起注意。二十几年后，1939年苏联数学家.康托罗维奇在生产组织与计划中的数学方法一书中提出线性规划问题，也未引起重视。此后的十几年中，线性规划只是作为一个还不成形的思想并未引起世界的重视。（2）线性规划理论发展的成长期1947年美国数学家G.B.Dantzing提出求解线性规划的单纯形法，为这门学科奠定了基础。同年，1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇

12、一起获1975年诺贝尔经济学奖。（3）线性规划理论发展的成熟期 50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题。1979年苏联数学家L.G.Khachi

13、an提出解线性规划问题的椭球算法，并证明它是多项式时间算法。1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。 由于单纯形法是求解线性规划模型的常用方法，并且其在求解线性规划模型上使用相当广泛，因此国内外对于单纯形法的研究成果可体现国内外对线性规划在数学建模中的研究进程。2.2国外有关研究的综述 1983年，S.Smale再次给出了Borgwardt在1982年证明的单纯形法平均多项式时间复杂类似的结果，这些结果都表明此算法虽然在最坏情况下是“

14、差”算法，但是，它的平均复杂性是“好”的。1992年，J.J.Forrest和D.Goldfarb给出了steepest.edge规则的若干变形和与之相应的递推公式，数值实验结果表明单纯形法与当时正处于发展势头强劲之际的内点法确实存在不分高低和难分伯仲的竞争状态。2002年，R.E.Bixby在“Solving real-world linear programs:a decade and more of progress”文章中总结了对偶单纯形法从20世界90年代以后的新进展，并指出它已经成为最有效的求解线性规划问题的方法之一【1】。2.3国内研究的综述 国内有关学者们对于单纯形法的各方面研

15、究成果也不计其数，依照目前已经公开发表的资料来看： 郭秀英在“线性规划单纯形法迭代法则的改进”【2】文章中提出一种当进、出变量唯一不变时的可减少迭代次数的判断进、出变量的新法则，并验证了其有效性。陈晓杰在“生产问题中单纯形解法的改进”【3】文章中针对线性规划在生产问题中的具体应用模型，结合线性规划的三个参数之间的某些关系以及他们对非基变量检验数的影响，提出一种通过某些特定变量的进出基运算可以达到简化单纯形求解运算的可行方法。吕林霞等人在“线性规划模型的单纯形法初始可行基选择研究”【4】文章中提出可以利用矩阵初等行变换来直接判断和寻找问题初始可行基的一种可行方法。张劲松等再“含自由变量LP问题的

16、改进单纯形法”【5】文章中针对含自由变量的LP问题，通过研究自由变量在其迭代过程中的运算规律，提出一种改进算法并且验证了其可以提高运算速度和节省存贮空间的有效性。董兵等再“一种改进的单纯形最优化法”【6】文章中给出了一种求解法获得的的基解仍然非原问题可行，也非对偶可行的一类规划问题初始可行的一般方法。谢震等在“单纯形法的计算机程序化算法改进”【7】文章中，通过其对计算机程序所作的改进工作，使得单纯形法在空间上和时间上的复杂度效率均降到。 2.4本人对以上综述的评价 从资料上来看虽然线性规划模型理论起源于国外，但是其在国内得到了较好的发展。其中国内学者在简化单纯形法的求解过程方面贡献卓著，而外国

17、学者在讨论哪种方法是求解线性规划模型的最优方法上做了深入的研究。 第二章 线性规划在数学建模中的应用2.1线形规划在物流运输模型中的应用现在物流业面临的新问题是：(1)认定所给问题确实是一个线性规划问题；(2)把它建立起线性数学模型；(3)并能够完成具体实务的全部工作。第一个问题实质上是具体实务究竟满足什么条件才能应用线性规划的方法。一般地说，必须有：一定要满足将目标表为最小化或最大化的要求； 一定要有达到目标的不同方法，且必须要有选择的可能性；要求的目标是有限制条件的； 必须将约束条件用数学表示为线性等式或线性不等式，并将目标函数化为线性函数。实例2.1：车辆调度问题 物流部门承接的运输千万

18、种，并往往是几十种物资同时调运。为此，只有一种物资的数学模型求最优调运方案方法，在多种物质运输情况下就不能直接使用。原因是：在调度汽车去完成运输任务时，免不了要出现空驶现象。例如某车队有一天要完成如表2所示的运输任务，各地问的距离如表3，问应怎样安排汽车去完成这些任务才能做到最省? 分析：满车路线和方向显然是固定的，但空车的路程、方向却没有固定。如把木材从火车站运到建筑工地卸下后，空车即可去火车站装煤，也可去文具公司装纸张。空车的走法不同，空驶的数当然也不同，这就产生了车辆调度问题。车辆调度问题主要解决的是：怎样安排车辆去完成所有的运输任务并使空驶的数最小。物资调运问题是“怎样才能使物资运输的

19、数最小”；这就是说把空车看成是一批货物(卸几吨货物就看成是几吨空车)，则把车辆调度问题转化为物资调运问题。 把空车看成是货物，其发、收(产、销)点及发、收(产、销)量按如下的方法决定： (1)若某点的卸货总量大于装货总量，则该点是空车的发点，其发量等于卸货总量与装货总量之差。如学校卸货总量为4，装货为0，故学校是发点，发量为4。 (2)若某点装货总量大于卸货总量，则该点是空车的收点，其收量也是二者之差。 （3)如果某点的卸货总量等于装货总量，如此点不存在空车则不予考虑。为此，车辆调度问题可作为物资调运问题来处理。即空车的流向应怎样才能使车辆调度合理?其主要步骤如下：确定空车的收发点和收发量，并

20、列表；确定空车调运的数学模型，并求解；根据所得解并结合具体情况合理调派车辆。解：收点：火车站、文具公司、粮店；发点：建筑工地、钢厂、学校。表1 运输任务起点终点建筑工地钢厂学校火车站958文具公司374粮店71013表2 运输任务货物装货点卸货点车数木材火车站建筑工地4煤火车站钢厂2纸张文具公司学校2面粉粮店学校2表3 空车收发运距运距（单位）空车收点空车数量火车站文具公司粮店空车发送建筑工地9374钢厂52102学校84134空车数量622约束条件为：用单纯形法的程序在计算机上可得：钢厂、学校分别向火车站发2t空车，建筑工地向文具公司和粮店发2t空车。空车吨公里数最小是： 2.2利用线性规划

21、模型在经济生活中的应用星星规划问题是经济数学的一个重要分支，在实践中有着广泛的应用，不仅许多实际课题属于线性规划问题，而且运筹学忠的一些分支中的问题也可以转化为线性规划问题来计算，因此线性规划问题在最有化学科中占有重要地位。表4 各种产品的资源消耗量产品劳动力/工时设备台时原材料（kg）劳动成本（元/kg） 产值（元/kg）A152030260472B201049180512C302545385544资源限额80001200015000120000实例2：单位生产成本最大增值问题某工厂在计划期内要生产三种A，B，C产品，假定产品畅销，已知生产的固定成本为10000元，即生产期内固定资产损耗量。

22、并且生产单位所需要的劳动力、设备台时、原材料、变动成本以及差值如表4所示。厂方规定总生产成本不要超过130000元，问应该如何安排生产才能使得产出率最大？建立数学模型：设工厂在计划期内生产A，B，C三种产品的数量分别为，显然成本产出率的表达式是：（1）且A，B，C三种产品的数量受4种资源量的限制：劳动力量的限制：（2）设备台时的限制：（3）原材料的限制：（4）变动成本的限制：（5）此外A，B，C三种产品的产量不能为负数，即。综上所述，本文的问题就是在条件（2）至（5）以及未知数非负的条件下求得未知数使得（1）最大，（1）成为目标函数。（2）至（5）称为约束条件，和工业资源配置一样的还有农业生产

23、计划安排问题。2.3线性规划在现代管理中的应用表5人工工时及单位产品利润车间产品设备人工利润/百元甲AB36233.56乙CD643276 实例3：某企业有 某企业有两个车间，各生产两种产品，生产这些产品所需的设备台时，人工工时及单位产品利润如下表所示。 现在企业具有设备102台时，人工工时46，计划部门将设备及人工进行如下分配，划部门将设备及人工进行如下分配:分给甲车间设备台时48，人工工时26;分给乙车间设备台时54，人工工时20。问计划部门如此进行分配是否合理? 解 设，分别为A,B两种产品的计划产量，分别为C,D产品的计划产量。分别建立两个车间的生产组织的数学模型并求解。 甲车间的生产

24、组织模型为先将模型标准化，再用单纯性法求得最优单纯型矩阵：由此得甲车间的最优生产方案为：生产A产品4单位，生产B产品6单位，最大利润为设备台时和人工工时的影子价格分别为乙车间的生产组织模型为先将模型标准化，再用单纯形法求得最优单纯形矩阵 于是原问题的最优解为：，最优值 由还可求得三种原料的影子价格分别为： 由可知，现有原料有剩余，增加此种原料不仅不能增加总利润，相反还会占用工厂的资金。故工厂决策者可以按不低于市场价格将剩余原料转让出去，增加收入。由可知，原料增加一吨，最大利润将增加0.12万元。因此，当该工厂的产品不是国家计划产品，而市场上原料的实际价格又低于0.12万元/吨时，工厂就可以把一

25、部分资金买进原料来扩大生产，使利润增加。反之，当市场上实际价格大于影子价格时，工厂就应卖出部分原料，缩小生产规模。此时生产利润虽然会减少些，但加上卖出原料的收入，总经济收入还是会比原来多一些。对于原料也可作类似分析。第三章 结论 综上所述,线性规划理论主要有两大类:一类是一项任务确定后如何统筹安排,做到以最少的人力、物力资源去完成这项任务;另一类是在一定量的人力、物力资源条件下,应如何统筹安排使用它们,以发挥最大的效益。这两类问题是一个问题的两个方面,即寻求整个问题的某种指标的最优解。求解线性规划的有效方法有:表上作业法、椭圆算法、卡马卡算法、单纯形法等,各种算法有其特点和优点,但都不能替代理

26、论较完善、实用性强的单纯形法。如今,线性规划理论的发展非常迅速,已渗透到经济活动的各个领域:除了生产组织、资源配置、交通运输、节约下料、人事指派、投资决策外,还有城市规划、工农业布局、服务网点、设备利用、仓库储备、环境优化、国防建设等。随着计算机技术的迅猛发展,线性规划的应用日益广泛。各种新的算法不断出现,如内点法、大步长跟踪算法、鞍面算法等。在1951年,国际水平只能解约束条件为10个方程的线性规划问题,到了1963年,就能解100010000个方程的线性规划问题。1956年,解一个67个方程的线性规划问题要1小时,而到1963年只需28秒。现在,不仅解题规模大、速度快,而且已有线性规划的专

27、门程序,求解时只要通过计算机调用程序,输入数据,很快便可得出结果。例如:给70个人分配70项不同的任务,共有70!种方案,是天文数字,要从中找出最优方案,即使用每秒能运算10亿次的大型计算机处理,也要从150年前开始直到太阳熄灭才会有结果。如果用单纯形软件,在电子计算机上计算,只需要几秒钟便可得出结果。1984年,美国贝尔实验室的数学家卡玛卡把射影几何原理用于大规模的线性规划问题,取得重大突破,成功地用于美国电话电报公司改建太平洋沿岸20个国家的庞大电话网计划,求出了涉及4.2万个因素设计的最小投资数,曾引起轰动。目前,美国78%的企业应用了线性规划,且成效显著。在我国,线性规划方法已成为国家重点推广的现代管理方法之一。