《运筹学线性规划实验报告》5800字（论文）

绪论1.1研究背景在中国的战国时代，曾经有过一个流传后世并被引为经典的赛马比赛，这就是大家都熟知的田忌赛马。这个故事说明在现有的条件下，经过适当的筹划、安排，选择一个最好的方案，就会取得最好的效果。可见，筹划安排是十分重要的。这种在古代就已经产生的经过策划安排取得好的结果的思想，就是古代的运筹学思想。运筹学因为涉及学科较多，将所有方法和技巧都囊括在系统管理中，通过正确的管理方法为人们提供解决办法，所以这种形式决定了它具有很强的综合性。在通过前期理论研究与方法优化，让人们在具体的实践过程中有具体的数据和科学的方法为依据，使得问题得以改善和解决，这种科学的管理方法也广为推广和使用，解决了人们生活中的许多具体问题。运筹学是一个数学学科的细分，将具体生活中反复出现的涉及运筹的问题进行综合分析再加以整理，再用科学的方法去解决问题，具备普世意义，不仅解决了生产生活中的难题，同时将问题进行归纳，总结方法。运筹学研究的方向随着科学的发展和社会的进步，不再仅限经济与军事，而是在经过时间的推移，渗透到人们的生活中，从曾经用数字表现经济管理方针中出现的问题，到如今生活中处处体现运筹学。因为它的综合性与广泛性，切实将数学中的数字运用，在经过计算后得出的结论进行科学的分析与总结，从而全方位更完善地提出方法。而线性规划就属于运筹学中的细分内容，当出现的限制因素与需要解决问题的目标存在线性关系，那么我们将这样的情况称为线性规划。那么，要解决线性问题最重要的方法需要依靠方程组，同时也会涉及到其他数学学科相关知识，这是解决线性规划的关键。总而言之，线性规划以及解决线性规划问题的方法都是统筹学中必不可少的重要组成部分，也是我们生活中解决问题不可或缺的办法。单纯形法让数学学科中出现的复杂问题简单化，同时也能将方法融入到具体的计算与实践中，使其具有可实施性。1.2线性规划理论及方法的发展进程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.3线性规划问题及其数学模型1.3.1线性规划的模型决定于它的定义究竟什么是线性规划呢？从本质上来说，也就是将变化的量值，赋予所以可行的前提，最后求得的解也是最完美的解。这也奠定了线性规划模型在这一基础上的雏形。首先，这种变量由于其特殊性，处于一直变化的状态，那么它在实际系统中就是未知的，但也是这种未知决定了预知范围内的可控因素；其次，将这种目标函数通过数学形式表现出来，求出具体的数值，也就是极值，这种极值随着目标要求而变大或变小。当所需目标为最大时，使生产总值最大，利益最大化时，这个极值即为最大值，当所需目标为最小时，使消耗值最小，所需成本为最小时，这个极值为最小。最后，所有具体目标的实现也需要分析其内部原因与外部因素导致的结果，所有环节中产生的问题都成为影响最后结果的关键。需要结合实际问题进行具体分析，从而使问题得到解决，而这种不可控因素会对结果产生一定的影响，我们也称之为约束条件。而这种线性规划在实际运用中为具体的值，所以它的变量一定是正值1.3.2线性规划在实际管理过程中的经济问题（1）投入：做好前期计划与资源分配，正确分析投入比与产出比，让利益最大化。（2）实际计划：根据实际计划决定具体生产，其目的是追求最终的产值。（3）具体实践：将需要完成的任务进行具体分配，桉需分配或按劳分配，使最终产值最大。（4）物料使用：有关具体下料问题，使在具体使用过程中利用最多损耗最小，坚持不浪费原则。（5）物资调度：在具体运输过程中，制定经济可行方针，节省资源。（6）清理库存：根据前期的计划安排确定好库存，维护好正常的生产运转，同时能够节省资源。1.3.3线性规划建立数学模型的具体实施举措（1）发现问题，解决问题，列举所有可行方针政策以及限制因素；（2）整理数据，确定模型建立方法；（3）求出最优解，并根据模型结果进行优化那么，在这个过程中最关键也是最重要的一步就是建立模型的过程，而建立模型的前提条件是需要找到问题，明确目标，那么这就需要各种理论数据作为支撑，所以数据资料的收集尤其重要，所有过程环环相扣，相辅相成，缺一不可。1.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,…amn1.4线性规划理论的评价公司任何复杂的生产计划决定了其注定无法保持单纯，复杂的计划随之而来的会产生巨大的工作量，也导致这一目标完全无法落实到现实，最后反而功亏一篑，无功而返。从这一论点出发，我们也发现线性规划理论在实际的运用中起到的无法忽视的作用。注定了这一理论基础在实践过程中是非常必要的.在这个效率优先的时代,众多领域中，但凡涉及最优解的问题，首先考虑的方法即是线性规划。要建立一个切合实际的线型规划模型，需要工程技术人员、财务管理人员等的通力配合，否则会失去很多有用的信息。线性规划作为运筹学的一个分支发展至今，从建立模型到求的最优解的整个过程,都有一套发展较为完备的体系和理论.涉及到生产计划以及类似的问题时，线性规划显然是首选的方法。然而，线性规划并不是没有其因为方法本身或者问题本身超出方法谈到的要求所产生的某些局限性。非常明显的一点是,线性规划模型实质上还是一个静态的模型.事实上，随着约束条件的变化，目标函数中的一些指标常常并非一成不变。举例来说,在考虑生产计划，即如何选择产业结构使生产成本最低的时候，成本系数实质上是一个会根据产业结构和模式之变化而难以绝对保持静态的变量，这就势必导致模型的理想化。另一方面，由于生产过程中外部条件与内部因素的影响，导致一些新的动态产生，所以生产过程不存在完全的静止，任何的影响都会赋予它新的变化。即它并非可以完全按照单纯形法中矩阵变换的简单方法去解决.一旦考虑到时间轴上的某些变化，问题的复杂程度就不是线性规划模型多能够做到了的。总的来说，线性规划模型具有单一性，相对其他模型缺少灵活性，所以也导致了其在解决实际问题中缺少坚实的理论基础做后盾，从而不够全面开阔。一2研究方法2.1综述法通过网络途径搜索、收集运筹学线性规划相关的历史文献资料，梳理线性规划理论及方法的发展进程，深入理解线性规划问题及其数学模型的相关内容。2.2实验法运用实验的方法解决中产生的问题，从而找到运筹学线性规划理论以及数学模型的建设方法，那么这里需要能够灵活运用软件来处理相关数学模型，将理论建立在数学模型的实践中，运用这样的方法来找到问题的答案，并对目标变量系数的灵敏度分析和约束方程中常数项进行灵敏度分析，用分析出来的数据解答复杂的实际问题。3实例分析【实验目的及要求】目的：通过实验掌握实际问题建立线性规划模型的方法，熟练运用运筹学软件3.0，在软件中处理模型，运用单纯形法求解线性规划问题，并对目标变量系数的灵敏度分析和约束方程中常数项进行灵敏度分析，用分析出来的数据解答复杂的实际问题。要求：（1）根据实际问题，建立线性规划模型，并用软件求解。（2）对结果进行分析。【实验原理】线性规划单纯形表上作业法、灵敏度分析。【实验环境】（使用的系统平台和用到的软件）使用管理运筹学软件3.0分析。【实验内容】【实验过程】（实验的具体步骤、记录、数据、分析）（1）实际问题实验室原计划生产两种不同的产品，不同的产品需要消耗的原料不同，下图为不同产品三种原料资源限制。实验室生产不同的产品所用原料不同，获得的利润也不同。当每单位生产产品1和产品2分别可以获利50元和100元，那么实验室需要分别生产多少产品才能使利益最大化？产品I产品II资源限制原料A11300kg原料B21400kg原料C01250kg（2）运筹学模型这个问题可以用数学线性规划模型来描述。把实验室生产的产品I数量和产品II数量用变量x1,x2来表示，称x1,x2为决策变量。把实验室所要求的最大利润的目标用x1,x2的线性函数形式来表示：maxz=50x1+100x2。其中，z为目标函数。整理问题中的一些约束条件，得到的规划模型：maxz=50x1+100x2，约束条件：x1+x2≤300，2x1+x2≤400，x2≤250，x1≥0，x2≥0。（3）软件求解1）在软件中建立线性规划模型打开管理运筹学软件3.0，选择“线性规划-线性规划”，把线性规划模型导入到软件内，导入内容包括四个部分：数据、决策变量、目标函数、约束条件。如图所示：2）线性规划单纯形表上作业在工具菜单中点击“解决”，出现规划求解窗口，点击“开始”，进行单纯形法分析，点击“下一步”，进行迭代分析。如图所示：为了方便运算，引入了松弛变量x3，x4，x5,软件把模型标准化了，标准形式为maxz=50x1+100x2，+0·x3+0·x4+0·x5，约束条件：x1+x2+x3=300，2x1+x2+x4=400，x2+x5=250，x1≥0，x2≥0，x3≥0，x4≥0，x5≥0。图中迭代次数为1时，没有进行迭代，求得初始基本可行解为x1=0，x2=0，x3=300，x2=400，x5=500，此时，z=0，即天天工厂没有生产产品也没有获利。迭代次数为1时，进行第一次迭代，获得的基本可行解为x1=0，x2=250，x3=50，x4=150，x5=0，此时，z=25000，cj-zj＞0，此解不是最优解。迭代次数为2时，进行第二次迭代，获得的基本可行解为x1=50，x2=250，x30，x4=50，x5=0，此时，z=27500，cj-zj≤0，此解是最优解。即天天工厂生产50单位产品I和250单位产品II时获利最大，最大利润为27500元。3）优化结果及灵敏度分析完成线性规划单纯形表作，点击“×”，弹出结果输出窗口。设目标变量系数分别为c1，c2,约束方程中常数项分别为b1，b2，b3。如图所示：图中包括目标函数最优分析、对偶问题分析、目标变量系数的灵敏度分析和约束方程中常数项的灵敏度分析。目标变量系数的灵敏度分析，给出了目标系数的当前值和上下限，当0≤c1≤100，c2≥50时最优解不变；约束方程中常数项的灵敏度分析，给出了约束条件的当前值和上下限，当250≤b1≤325,b2≥350,200≤b1≤300时最优解不变。4结果分析与总结从以上分析中，可以发现工厂生产50单位产品I和250单位产品II时获利最大，最大利润为27500元。如果工厂每单位产品I获利0~100元，每单位产品II获利50元以上时，获利最大组合不变；消耗A原料250~325kg，消耗B原料350kg以上，消耗C材料200~300kg时，获利最大组合不变。此次实验是对管理运筹学软件3.0的实践运用，实验素材选取于课本，是对课本知识的检验。管理运筹学是一门偏难的学科，如何结合实际生活是学习的重点，学习非常有挑战性。通过这次实验的模型的建立与求解，对实际问题进行数理分析等等实践操作，我更加认识到这门学科十分深奥。运筹学作为数学学科基础，但归根结底还是与数学这一学科有着很大区别，因此运筹学也作为