《线性规划理论方法及应用研究》6500字（论文）

线性规划理论方法及应用研究目录TOC\o"1-2"\h\u18047线性规划理论方法及应用研究 16191一、线性规划理论及方法的发展进程 228534二、线性规划的主要内容 332456（一）线性规划问题及其数学模型 325297（二）线性规划模型的具体分析及应用Excel求解线性规划问题 419562三、现阶段成果的评价 811127四、发展前景的预测 925590（6）数学软件的研发和运筹学发展之间仍然存在较大的差距。 932246结语 1022575参考文献 10摘要：运筹学是包含多种学科的综合性学科，是最早形成的一门软科学。它把科学的方法、技术和工具应用到包括一个系统管理在内的各种问题上，以便为那些掌管系统的人们提供最佳的解决问题的办法。它用科学的方法研究与某一系统的最优管理有关的问题。它能帮助决策人解决那些可以用定量方法和有关理论来处理的问题。关键词：运筹学；线性规划；发展；应用在中国的战国时代，曾经有过一个流传后世并被引为经典的赛马比赛，这就是大家都熟知的田忌赛马。这个故事说明在现有的条件下，经过适当的筹划、安排，选择一个最好的方案，就会取得最好的效果。可见，筹划安排是十分重要的。这种在古代就已经产生的经过策划安排取得好的结果的思想，就是古代的运筹学思想。运筹学是包含多种学科的综合性学科，是最早形成的一门软科学。它把科学的方法、技术和工具应用到包括一个系统管理在内的各种问题上，以便为那些掌管系统的人们提供最佳的解决问题的办法。它用科学的方法研究与某一系统的最优管理有关的问题。它能帮助决策人解决那些可以用定量方法和有关理论来处理的问题。现在普遍认为，运筹学是近代应用数学的一个分支，主要是将生产、管理等事件中出现的一些带有普遍性的运筹问题加以提炼，然后利用数学方法进行解决。前者提供模型，后者提供理论和方法。运筹学主要研究经济活动和军事活动中能用数量来表达的有关策划、管理方面的问题。当然，随着客观实际的发展，运筹学的许多内容不但研究经济和军事活动，有些已经深入到日常生活当中去了。运筹学可以根据问题的要求，通过数学上的分析、运算，得出各种各样的结果，最后提出综合性的合理安排，以达到最好的效果。线性规划是运筹学的其中一个理论，如果约束条件和目标函数都是呈线性关系的就叫线性规划。要解决线性规划问题，从理论上讲都要解线性方程组，因此解线性方程组的方法，以及关于行列式、矩阵的知识，就是线性规划中非常必要的工具。线性规划及其解法—单纯形法的出现，对运筹学的发展起了重大的推动作用。许多实际问题都可以化成线性规划来解决，而单纯形法有是一个行之有效的算法，加上计算机的出现，使一些大型复杂的实际问题的解决成为现实。一、线性规划理论及方法的发展进程1939年，苏联学者Kantorovich为前苏联政府解决优化问题时提出了极值问题，并且提出了解乘数法的新方法，可惜他的工作在当时并未引起足够的重视。事实上，他所提出的问题正是线性规划的雏形。与此同时，美国的线性规划却获得了飞快的发展。1941年，Hitchcock提出运输问题；1945年，Stigler提出了营养问题；1945年，Koopmans提出了经济问题。而奠定线性规划整套理论方法的，还要说是G.B.Dantzig，他被誉为“线性规划之父”。他在1947年担任美国空军审计官的数学顾问，为找到解决问题的机制化工具，提出了“在一组线性方程或不等式约束下，求某一线性形式极小值问题的数学模型”，这便是“线性规划”（linearprogramming）这一经典优化模型。而“线性规划”这一名字的由来是在之后1948年，Koopmans和Dantzig在海滩散步时共同想出的。1947年夏天，Dantzig提出了单纯形算法。这个算法在后来被评为20世纪最伟大的算法之一。尽管单纯形法(Simplexmethod)作为解决线性规划的有效方法在学术界具有统治地位，但是1971年，Klee和Minty两位学者构造出一个例子，该例子下单纯形法的运作需要访问指数数量级别的顶点，也就是说，在最坏情况下，单纯形法是一个指数时间算法(exponential-timealgorithm)。Dantzig在得知这个消息后感叹到他的噩梦到来了，单纯形法并不是在任何情况下都是高效可行的。那么，是否有更加高效的算法，比如多项式时间算法(polynomial-timealgorithm)，来解决线性规划问题呢？8年后，即1979年，L.G.Khachiyan发明了椭球算法(ellipsoidmethod)，这是第一个解决线性规划问题的多项式时间算法。但是，这个算法虽然理论上是多项式时间运行，但是算法被证明是不切实际的，这个算法的杰出贡献是在理论层面告诉世人，线性规划是可以用多项式时间算法来解决的，同时也启发了学者在更加深入的优化领域进行算法开发。1984年，N.Karmarkar发明了内点算法(interiorpointmethod)，这是线性规划第一个实际可用的多项式时间算法。二、线性规划的主要内容（一）线性规划问题及其数学模型1.线性规划的模型决定于它的定义线性规划的定义是：求一组变量的值，在满足一组约束条件下，求得目标函数的最优解。根据这个定义,就可以确定线性规划模型的基本结构。（1）变量变量又叫未知数，它是实际系统的未知因素,也是决策系统中的可控因素，一般称为决策变量，常引用英文字母加下标来表示,如X,X，X，X等。（2）目标函数将实际系统的目标，用数学形式表现出来，就称为目标函数，线性规划的目标函数是求系统目标的数值，即极大值，如产值极大值、利润极大值或者极小值，如成本极小值、费用极小值、损耗极小值等等。（3）约束条件约束条件是指实现系统目标的限制因素。它涉及到企业内部条件和外部环境的各个方面,如原材料供应、设备能力、计划指标、产品质量要求和市场销售状态等等，这些因素都对模型的变量起约束作用，故称其为约束条件。约束条件的数学表示形式为三种，即≥、＝、≤.线性规划的变量应为正值，因为变量在实际问题中所代表的均为实物，所以不能为负。2.在经济管理中，线性规划使用较多的是下述几个方面的问题：（1）投资问题—确定有限投资额的最优分配,使得收益最大或者见效快。（2）计划安排问题—确定生产的品种和数量,使得产值或利润最大，如资源配制问题。（3）任务分配问题—分配不同的工作给各个对象（劳动力或机床)，使产量最多、效率最高，如生产安排问题。（4）下料问题—如何下料，使得边角料损失最小。（5）运输问题—在物资调运过程中，确定最经济的调运方案。（6）库存问题—如何确定最佳库存量,做到即保证生产又节约资金等等。3.应用线性规划建立数学模型的三步骤：（1）明确问题，确定问题，列出约束条件。（2）收集资料，建立模型。（3）模型求解（最优解），进行优化后分析。其中，最困难的是建立模型，而建立模型的关键是明确问题、确定目标，在建立模型过程中花时间、花精力最大的是收集资料。4.线性规划的数学模型的一般形式为:目标函数max（min）z=c1X+c2X+…+cnXn满足约束条件：a11X+a12X,+…+a1nXn≤(＝，≥）b1a21X+a22X,+…+a2nXn≤（＝,≥)b2………………….am1X+am2X+…+amnXn≤(＝，≥)bmX，X，…,Xn≥0线性规划模型的矩阵形式：目标函数max（min）Z=CX约束条件AX≤(＝,≥)b其中，C=(c1，c2，…,cn），X=(X，X，…Xn）Tb=(b1，b2，…bm)Ta11，a12，…a1nA=a21，a22,…a2n…………am1，am2,…amn（二）线性规划模型的具体分析及应用Excel求解线性规划问题我们来看生产计划问题：生产计划是控制生产装置运行的命令，要利用有限的资源获得最大的经济效益,就必须制定最佳生产计划。随着公司生产装置的不断增多，生产计划的制定变得越来越复杂.采用现代管理技术，建立数学模型，利用电子计算机求解,很容易得出最优生产计划。下面举一案例说明（本案例出自《运筹学》，林齐宁,北京邮电大学出版社，2003年，P7)某工厂计划用现有的铜、铅两种资源生产A、B两种型号的电缆。A、B两种型号的电缆单位售价分别为6万元和4万元。市场对A型电缆的需要量无限制,而对B电缆的最大需求量为7单位。生产单位产品A、B两种型号电缆对铜、铅的消耗量及可利用的铜、铅数量如下表所示：表1：基本信息表

A型电缆B型电缆资源提供限量消耗：铜（吨）2110消耗：铅（吨）118产品需要限量

7

售价(万元）64

工厂应该如何让安排生产，才能使工厂总收入最大？解答过程如下：（1）决策变量设x1，x2分别代表A、B两种型号电缆的生产量,f(x）为工厂总收入。（2）目标函数本问题的目标是工厂收益最大值Maxf（x)=6Xl+4X2（3）约束条件：A型电缆B型电缆资源提供限量消耗：铜（吨）2110消耗：铅（吨）118产品需要限量7售价(万元）64则上述问题可以用如下数学模型(线性规划模型）来表示：Obj:Maxf（x）=6Xl+4X22Xl+X2≤10铜资源约束s.t.Xl+X2≤8铅资源约束X2≤7产量数量约束Xl，X2≥0产量质量约束用Excel辅助计算求解。首先，根据问题建立电子表格模型具体步骤如下：（1）收集问题的数据。（2）在电子表格的数据单元格中输入数据。（3）确定对活动水平需要作出的决策并且指定可变单元显示这些决策。（4）确定对这些决策的约束条件并引入需具体化这些约束条件的输出单元格。（5）选择要输入目标单元格的完全绩效测度。（6）使用SUMPRODUCT函数为每个输出单元格（包括目标单元格）输入合适的值。然后,建立了起电子表格模型：再进行规划求解：规划求解的选项对话框：最后,保存求解结果:最终结果如下图所示:可以利用Excel中的“规划求解”功能可以直接到“敏感性分析”,利用该报告可以很方便地进行灵敏度分析：敏感性报告的内容由两部分组成：（1）位于报告上部的“可变单元格"部分反映了目标函数中的系数变化对最优解产生的影响.第一列“单元格”是指决策变量所在单元格地址。第二列“名字”是这些决策变量的名称.第三列“终值”是决策变量的终值,即最优解。第四列是“递减成本”,它的绝对值表示目标函数中决策变量的系数必须改进多少，才能得到该决策变量的正数解.第五列“目标式系数”是指目标函数中的系数。第六列与第七列分别是“允许的增量"和“允许的减量”它们表示目标函数中的系数在允许的增量和减量范围内变化时，最优解不变。（2）位于报告下部的“约束”部分反映了约束条件右端值变化目标值产生的影响。目标函数系数同时变动的情况：当各个系数变动的百分比之和小于100％时，最优解不发生变化;当各个系数变动的百分比之和等于100％时，最优解不发生变化；当各个系数变动的百分比之和大于100％时，不能确定最优解的变化，可能改变，也可能不变.约束右端值同时变动：当各个右端值变动的百分比之和小于100％时,影子价格有效;当各个右端值变动的百分比之和等于100%时，影子价格有效；当各个右端值变动的百分比之和大于100％时,不能保证影子价格依然有效。三、现阶段成果的评价公司生产的复杂性使得手编计划的工作极其复杂,手编计划的工作量大，而且更为重要的是很难甚至无法实现优化，会给公司造成很大的机会损失。采用线性规划模型制定公司计划和进行决策分析是可行的、必要的.在这个效率优先的时代,众多领域中，但凡涉及最优解的问题，首先考虑的方法即是线性规划。要建立一个切合实际的线型规划模型，需要工程技术人员、财务管理人员等的通力配合，否则会失去很多有用的信息。线性规划作为运筹学的一个分支发展至今，从建立模型到求的最优解的整个过程,都有一套发展较为完备的体系和理论.涉及到生产计划以及类似的问题时，线性规划显然是首选的方法。然而，线性规划并不是没有其因为方法本身或者问题本身超出方法谈到的要求所产生的某些局限性。非常明显的一点是,线性规划模型实质上还是一个静态的模型.事实上，随着约束条件的变化，目标函数中的一些指标常常并非一成不变。举例来说,在考虑生产计划，即如何选择产业结构使生产成本最低的时候，成本系数实质上是一个会根据产业结构和模式之变化而难以绝对保持静态的变量，这就势必导致模型的理想化。另一方面，生产过程也不是一个绝对静态的过程，即产业结构本身，或者说约束条件中的每一项指标，也会产生某些动态的过程，即它并非可以完全按照单纯形法中矩阵变换的简单方法去解决.一旦考虑到时间轴上的某些变化，问题的复杂程度就不是线性规划模型多能够做到了的。总的来说，线性规划模型是一种比较机械性的模型，这种机械性决定它在某种意义上不可避免的局限性。四、发展前景的预测运筹学作为一门新兴学科，一门处于年青发展时期的学科，在理论研究和应用研究的诸多方面，无论广度和深度来说都有着无限滚广阔的前景。现在的问题是，运行后学今后究竟应该朝哪个方向发展？这是运筹学界普遍关心的问题。关于运筹学将往哪个方向发展，从70年代起就在西方运筹学界引起过争论，至今还没有一个统一的结论。美国前运筹学会主S.Bonder认为，运筹学应在三个领域发展：运筹学应用、运筹科学、运筹数学，并强调在协调发展的同时重点发展前两者。这是由于运筹数学在70年代已形成一个强有力的分支，对问题的数学描述已相当完善，却忘掉了运筹学的原有特色，忽视了对多学科的横向交叉联系和解决实际问题的研究。现在，运筹学工作者面临的大量新问题是：经济、技术、社会、生态和政治因素交叉在一体的复杂系统，所以从70年代末80年代初，不少运筹学家提出“要注意研究大系统”，“要从运筹学到系统分析”。由于研究大系统的时间范围有可能很长，还必须与未来学紧密结合起来；面临的问题大多是涉及技术、经济、社会、心理等综合因素，在运筹学中除了常用的数学方法，还引入了一些非数学的方法和理论。如美国运筹学家T.L.Saaty于70年代末期提出的层次分析法（AHP），可以看作是解决非结构问题的一个尝试。针对这种状况，P.B.Checkland从方法论上对此进行了划分。他把传统的运筹学方法称为硬系统思考，认为它适合解决那种结构明确的系统的战术及技术问题，而对于结构不明确的、有人参与活动的系统就要采用软系统思考的方法。借助电子计算机，研究软系统的概念和运用方法应是今后运筹学发展的一个方向。但不管怎么争论，运筹学未来发展也必出现以下的特点：（1）运筹学的理论研究将会得到进一步系统地、深入地发展。（2）运筹学跨学科的特点必将进一步延伸和发展。（3）运筹学沿原有的分支向前发展。（4）一些非数学的方法和理论将引入运筹学这是因为研究的问题大多涉及技术、经济、社会、心理综合因素的研究，而这种问题是非结构性的问题（如研究世界性的问题、研究国家政策等），运用通常地、精巧的数学方法很难解决。（5）接均问题的过程将变为决策者和分析者共同参与、发挥其创造性的过程。（6）数学软件的研发和运筹学发展之间仍然存在较大的差距。中国运筹学学会从中国数学学会独立出来也说明了运筹学虽然已数学为基础，但同数学学科有本质的不同。运筹学家除了推动运筹学基本理论的发展，还要对社会肩负起与数学家不同的责任。而1994年美国运筹学会和管理科学学会的合并成立TNFORMF，是国际运筹学界的一件大事。目前，运筹学和管理学的合并也引起了包括中国在内的世界各国的极大关注。运筹学未来的发展会出现在更多的社会发展领域。总之，运筹学发展的前景是光明的，道路是曲折的。结语近二十年来，信息科学、生命科学等现代高科技对人类社会产生了巨大影响，运筹学工作者还关注到其中一些运筹学起作用的新的工作方向。例如，将全局最优化、图论、神经网络等运筹学理论及方法应用于分子