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

线性规划在数学建模中的应用摘要：线性规划是运筹学中发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法，英文缩写LP。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。本文在阅读了大量材料的基础上，集中体现了线性规划是如何应用到数学建模中去的。并且在利用数学建模的思想以线性规划为工具可以解决哪些实际问题，为我们的生活提供哪些便利。本文大体上可分为三章，第一章主要对线性规划和数学建模这两个理论做简要描述。并且叙述这两个理论的发展历程，以及研究的背景及意义。第二章主要介绍线性规划在数学建模中的应用，其中包括现在性规划在物流运输中的应用，线性规划在经济生活中的应用，以及线性规划在现代管理中的应用，并且配备了相应的例子。第三章主要讨论线性规划在实际应用方面应注意哪些细节，并对第二章的数学模型进行优化，以及对最优解方面的讨论。关键词：线性规划数学模型物流运输经济生活现代管理Abstract:Linearprogrammingisdevelopedrapidlyandwidelyappliedinoperationalresearch,themethodisanimportantbranchofmature,itisoneofthescientificmanagementofauxiliarypeoplemathematicalmethod.StudyoflinearobjectivefunctionunderthelinearconstraintconditionextremumproblemsofmathematicstheoryandmethodofLPabbreviations.Itisanimportantbranchofoperationalresearch,widelyusedinmilitary,economicanalysis,managementandengineeringtechnology,etc.Forreasonableuseofthelimitedmanpowerandmaterialresources,financialresourcesandotherresourcestomaketheoptimaldecision,providethescientificbasis.Inthispaper,onthebasisofreadingalotofmaterial,howconcentratedthelinearprogrammingisappliedtothemathematicalmodeling.Andinusingtheideasofmathematicalmodelingbymeansoflinearprogrammingcansolvepracticalproblems,whichprovidewhichisconvenientforourlife.Thearticleingeneralcanbedividedintothreechapters,thefirstchaptermainlyonlinearprogrammingandmathematicalmodelingthetwotheoriesaredescribedbriefly.Andthedevelopmentofthetwotheories,aswellastheresearchbackgroundandsignificance.Thesecondchaptermainlyintroducestheapplicationoflinearprogramminginmathematicalmodeling,includingtheplanningintheapplicationoflogisticstransportation,nowtheapplicationoflinearprogrammingineconomiclife,aswellastheapplicationoflinearprogramminginthemodernmanagement,andequippedwithcorrespondingexamples.Thethirdchaptermainlydiscussdetailswhichshouldbepaidattentiontoinpracticalapplicationoflinearprogramming,andoptimizethemathematicalmodelofthesecondchapter,andtheoptimalsolutionforthediscussion.Keywords:LinearprogrammingMathematicalmodelLogisticstransportationTheeconomiclifeModernmanagement第一章绪论1.1研究背景以及意义1.1.1研究背景1.1.2研究意义研究线性规划在数学建模中的应用其理论意义主要在于利用数学建模的手段，为线性规划更好的应用于显示生活中提供理论依据。而为了更好的完成这项工作，需要查阅大量的相关资料，理论意义也在于总结整理前人的研究成果，并在某种程度上加以创新，如线性规划在数学建模中的约束条件，什么情况下利用线性规划进行数学建模更为合理等。研究线性规划在数学建模中的现实意义有很多，因为一个数学理论要想应用到现实中去就必须要建立数学模型去解决。而线性规划作为运筹学中的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。因此，研究线性规划在数学建模中的应用就可以将数学理论更好的，更有效的，更完美的运用到现实生活中去，为我们的生活提供便利。第二章线性规划理论简述2.1理论的渊源及演进过程（1）线性规划理论发展的萌芽期法国数学家J.-B.-J.傅里叶和C.瓦莱－普森分别于1832和1911年独立地提可解的问题会有一个简单多边形的可行域出线性规划的想法，但未引起注意。二十几年后，1939年苏联数学家Л.В.康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题，也未引起重视。此后的十几年中，线性规划只是作为一个还不成形的思想并未引起世界的重视。（2）线性规划理论发展的成长期1947年美国数学家G.B.Dantzing提出求解线性规划的单纯形法，为这门学科奠定了基础。同年，1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。（3）线性规划理论发展的成熟期50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题。1979年苏联数学家L.G.Khachian提出解线性规划问题的椭球算法，并证明它是多项式时间算法。1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。由于单纯形法是求解线性规划模型的常用方法，并且其在求解线性规划模型上使用相当广泛，因此国内外对于单纯形法的研究成果可体现国内外对线性规划在数学建模中的研究进程。2.2国外有关研究的综述1983年，S.Smale再次给出了Borgwardt在1982年证明的单纯形法平均多项式时间复杂类似的结果，这些结果都表明此算法虽然在最坏情况下是“差”算法，但是，它的平均复杂性是“好”的。1992年，J.J.Forrest和D.Goldfarb给出了steepest.edge规则的若干变形和与之相应的递推公式，数值实验结果表明单纯形法与当时正处于发展势头强劲之际的内点法确实存在不分高低和难分伯仲的竞争状态。2002年，R.E.Bixby在“Solvingreal-worldlinearprograms:adecadeandmoreofprogress”文章中总结了对偶单纯形法从20世界90年代以后的新进展，并指出它已经成为最有效的求解线性规划问题的方法之一【1】。2.3国内研究的综述国内有关学者们对于单纯形法的各方面研究成果也不计其数，依照目前已经公开发表的资料来看：郭秀英在“线性规划单纯形法迭代法则的改进”【2】文章中提出一种当进、出变量唯一不变时的可减少迭代次数的判断进、出变量的新法则，并验证了其有效性。陈晓杰在“生产问题中单纯形解法的改进”【3】文章中针对线性规划在生产问题中的具体应用模型，结合线性规划的三个参数之间的某些关系以及他们对非基变量检验数的影响，提出一种通过某些特定变量的进出基运算可以达到简化单纯形求解运算的可行方法。吕林霞等人在“线性规划模型的单纯形法初始可行基选择研究”【4】文章中提出可以利用矩阵初等行变换来直接判断和寻找问题初始可行基的一种可行方法。张劲松等再“含自由变量LP问题的改进单纯形法”【5】文章中针对含自由变量的LP问题，通过研究自由变量在其迭代过程中的运算规律，提出一种改进算法并且验证了其可以提高运算速度和节省存贮空间的有效性。董兵等再“一种改进的单纯形最优化法”【6】文章中给出了一种求解法获得的的基解仍然非原问题可行，也非对偶可行的一类规划问题初始可行的一般方法。谢震等在“单纯形法的计算机程序化算法改进”【7】文章中，通过其对计算机程序所作的改进工作，使得单纯形法在空间上和时间上的复杂度效率均降到。2.4本人对以上综述的评价从资料上来看虽然线性规划模型理论起源于国外，但是其在国内得到了较好的发展。其中国内学者在简化单纯形法的求解过程方面贡献卓著，而外国学者在讨论哪种方法是求解线性规划模型的最优方法上做了深入的研究。第二章线性规划在数学建模中的应用2.1线形规划在物流运输模型中的应用现在物流业面临的新问题是：(1)认定所给问题确实是一个线性规划问题；(2)把它建立起线性数学模型；(3)并能够完成具体实务的全部工作。第一个问题实质上是具体实务究竟满足什么条件才能应用线性规划的方法。一般地说，必须有：①一定要满足将目标表为最小化或最大化的要求；②一定要有达到目标的不同方法，且必须要有选择的可能性；③要求的目标是有限制条件的；④必须将约束条件用数学表示为线性等式或线性不等式，并将目标函数化为线性函数。实例2.1：车辆调度问题物流部门承接的运输千万种，并往往是几十种物资同时调运。为此，只有一种物资的数学模型求最优调运方案方法，在多种物质运输情况下就不能直接使用。原因是：在调度汽车去完成运输任务时，免不了要出现空驶现象。例如某车队有一天要完成如表2所示的运输任务，各地问的距离如表3，问应怎样安排汽车去完成这些任务才能做到最省?分析：满车路线和方向显然是固定的，但空车的路程、方向却没有固定。如把木材从火车站运到建筑工地卸下后，空车即可去火车站装煤，也可去文具公司装纸张。空车的走法不同，空驶的数当然也不同，这就产生了车辆调度问题。车辆调度问题主要解决的是：怎样安排车辆去完成所有的运输任务并使空驶的数最小。物资调运问题是“怎样才能使物资运输的数最小”；这就是说把空车看成是一批货物(卸几吨货物就看成是几吨空车)，则把车辆调度