最优化课程论文

最优化方法课程设计——线性规划模型理论与发展学院：理学院班级：信息102班学号：姓名：1理论与发展线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素.在企业的各项管理活动中,例如计划、生产、运输、技术等问题，线性规划是指从各种限制条件的组合中，选择出最为合理的计算方法，建立线性规划模型从而求得最佳结果。解线性规划问题有很多种方法，内点法、单纯形法、对偶单纯形法等等，而具体求解则可用图解法等。法国数学家J.-B.-J.傅里叶和C.瓦莱－普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。1939年苏联数学家Л.В.康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题，也未引起重视。1947年美国数学家G.B.Dantzing提出求解线性规划的单纯形法，为这门学科奠定了基础。1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题。1979年苏联数学家L.G.Khachian提出解线性规划问题的椭球算法，并证明它是多项式时间算法。1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大。2模型建立（一）结构线性规划的模型决定于它的定义，线性规划的定义是：求一组变量的值，在满足一组约束条件下，求得目标函数的最优解。根据这个定义，就可以确定线性规划模型的基本结构。（1）变量。变量又叫未知数，它是实际系统的未知因素，也是决策系统中的可控因素，一般称为决策变量，常引用英文字母加下标来表示，如Xl，X2，X3，Xmn等。（2）目标函数。将实际系统的目标，用数学形式表现出来，就称为目标函数。线性规划的目标函数是求系统目标的数值，即极大值，如产值极大值、利润极大值或者极小值，如成本极小值、费用极小值、损耗极小值等等。（3）约束条件。约束条件是指实现系统目标的限制因素。（二）建立模型而应用线性规划建立数学模型的三步骤：(1)明确问题，确定问题，列出约束条件。(2)收集资料，建立模型。(3)模型求解(最优解)，进行优化后分析。其中，最困难的是建立模型，而建立模型的关键是明确问题、确定目标，在建立模型过程中花时间、花精力最大的是收集资料。所建立的数学模型具有以下特点：1、每个模型都有若干个决策变量（x1，x2，x3……，xn），其中n为决策变量个数。决策变量的一组值表示一种方案，同时决策变量一般是非负的。2、目标函数是决策变量的线性函数，根据具体问题可以是最大化（max）或最小化（min），二者统称为最优化（opt）。3、约束条件也是决策变量的线性函数。当我们得到的数学模型的目标函数为线性函数，约束条件为线性等式或不等式时称此数学模型为线性规划模型。（三）线性规划的数学模型的一般形式为：目标函数nnXcXcXcz...max(min)2211满足约束条件：11212111),(...bXaXaXann22222121),(...bXaXaXann……mnmnmmbXaXaXa),(...22110,...,,21nXXX线性规划模型的矩阵形式：目标函数cXzmax(min)约束条件bAX),(其中，),...,,(21ncccc,TnXXXX),...,,(21，Tmbbbb),...,,(21mnmmnnaaaaaaaaaA.....................2122221112113实例为了具体的了解线性规划问题，可以举一个实例，我们来看生产计划问题：生产计划是控制生产装置运行的命令，要利用有限的资源获得最大的经济效益，就必须制定最佳生产计划。随着公司生产装置的不断增多，生产计划的制定变得越来越复杂。采用现代管理技术，建立数学模型，利用电子计算机求解，很容易得出最优生产计划。下面举一案例说明：某工厂计划用现有的木材、钢铁两种资源生产A、B、C三种型号的零件。A、B、C三种型号的零件单位售价分别为2万元、3万元和4万元。市场对A型零件的需要量无限制，对B零件的最大需求量为7单位，对C零件的最大需求量是10单位。生产单位产品A、B、C两种型号零件对木材、钢铁的消耗量及可利用的木材、钢铁数量如下表所示：表1：基本信息表A型零件B型零件C型零件资源提供限量消耗：木材（吨）21112消耗：钢铁（吨）32110产品需要限量710售价（万元）642工厂应该如何让安排生产，才能使工厂总收入最大？4求解解答过程如下：(1)决策变量设321,,xxx分别代表A、B、C三种型号零件的生产量，f(x)为工厂总收入。(2)目标函数本问题的目标是工厂收益最大值321246)(maxxxxxf(3)约束条件：A型零件B型零件C型零件资源提供限量消耗：木材（吨）21112消耗：钢铁（吨）32110产品需要限量710售价（万元）642则上述问题可以用如下数学模型（线性规划模型）来表示：321246)(maxxxxxf122321xxx木材资源约束1023321xxx钢铁资源约束72x产量数量约束103x产量质量约束0,,321xxx我们可以用Excel辅助计算求解，也可用matlab，lingo等软件，这里我们用excel示例一下。首先，建立了起电子表格模型：再进行规划求解：最后，保存求解结果：最终结果如下图所示：可以还利用Excel中的“规划求解”功能可以直接到“敏感性分析”，利用该报告可以很方便地进行灵敏度分析：敏感性报告的内容由两部分组成：（1）位于报告上部的“可变单元格”部分反映了目标函数中的系数变化对最优解产生的影响。第一列“单元格”是指决策变量所在单元格地址。第二列“名字”是这些决策变量的名称。第三列“终值”是决策变量的终值，即最优解。第四列是“递减成本”，它的绝对值表示目标函数中决策变量的系数必须改进多少，才能得到该决策变量的正数解。第五列“目标式系数”是指目标函数中的系数。第六列与第七列分别是“允许的增量”和“允许的减量”它们表示目标函数中的系数在允许的增量和减量范围内变化时，最优解不变。（2）位于报告下部的“约束”部分反映了约束条件右端值变化目标值产生影响。目标函数系数同时变动的情况：当各个系数变动的百分比之和小于100%时，最优解不发生变化；当各个系数变动的百分比之和等于100%时，最优解不发生变化；当各个系数变动的百分比之和大于100%时，不能确定最优解的变化，可能改变，也可能不变。约束右端值同时变动：当各个右端值变动的百分比之和小于100%时，影子价格有效；当各个右端值变动的百分比之和等于100%时，影子价格有效；当各个右端值变动的百分比之和大于100%时，不能保证影子价格依然有效。5结果与分析公司生产的复杂性使得手编计划的工作极其复杂，手编计划的工作量大，而且更为重要的是很难甚至无法实现优化，会给公司造成很大的机会损失。采用线性规划模型制定公司计划和进行决策分析是可行的、必要的。在这个效率优先的时代，众多领域中，但凡涉及最优解的问题，首先考虑的方法即是线性规划。要建立一个切合实际的线型规划模型，需要工程技术人员、财务管理人员等的通力配合，否则会失去很多有用的信息。线性规划作为运筹学的一个分支发展至今，从建立模型到求的最优解的整个过程，都有一套发展较为完备的体系和理论。涉及到生产计划以及类似的问题时，线性规划显然是首选的方法。然而，线性规划并不是没有其因为方法本身或者问题本身超出方法谈到的要求所产生的某些局限性。非常明显的一点是，线性规划模型实质上还是一个静态的模型。事实上，随着约束条件的变化，目标函数中的一些指标常常并非一成不变。举例来说，在考虑生产计划，即如何选择产业结构使生产成本最低的时候，成本系数实质上是一个会根据产业结构和模式之变化而难以绝对保持静态的变量，这就势必导致模型的理想化。另一方面，生产过程也不是一个绝对静态的过程，即产业结构本身，或者说约束条件中的每一项指标，也会产生某些动态的过程，即它并非可以完全按照单纯形法中矩阵变换的简单方法去解决。一旦考虑到时间轴上的某些变化，问题的复杂程度就不是线性规划模型多能够做到了的。总的来说，线性规划模型是一种比较机械性的模型，这种机械性决定它在某种意义上不可避免的局限性。6参考文献【1】《运筹学》林齐宁北京邮电大学出版社2003年【2】《最优化方法》孙文瑜高等教育出版社2004年