MATLAB在线性规划中的应用

-本文为网络收集精选范文、公文、论文、和其他应用文档，如需本文，请下载-MATLAB在线性规划中的应用本文从网络收集而来，上传到平台为了帮到更多的人，如果您需要使用本文档，请点击下载按钮下载本文档（有偿下载），另外祝您生活愉快，工作顺利，万事如意！第1章 引言线性规划是指如何最有效或最佳地策划经济活动，也就是一定的约束条件下，求目标函数极值的问题1。在1823年Fourier和1911年Poussin就已经提出过相关的问题2，随后由.Kantorovich3 (苏联数学家)在1939年出版的白皮书Mathematical Methods in the Organization and Planning of Production中，对线性规划的思想做了最早的阐述。现在，线性规划已被广泛应用于军事行动、管理、工程技术和经济分析等方面，合理利用有限的人力、物力资源、财政资源等，为决策者做出最优决策提供科学依据，辅助和指导人们进行科学的管理和规划4。在实际应用中，人们发现经常遇到一些问题的规模比较大，由此，G. B. Dantzig又与5教授一起主要研究这类问题，并且针对其求解过程提出了分解方法。自从1967年，在I. I. Dikin研究分析二次规划并讨论了其与线性规划的特定关系之后，研究学者们相继发现在其他学科领域的许多复杂的问题，也都可以经过适当的变形转换后成为一个简单的线性规划问题，从而方便快捷解答。这就让线性规划在应用范围上得到了很大的扩展。大量的实际问题从科学研究和生产生活管理中被提出来，其决策变量和约束条件的数量多到十几个、几十个、几百个，甚至不计其数，这些问题就不是人们可以很容易解决的了。但是伴随着电子计算机的迅速发展和介入，和不断提高的计算技术，线性规划的应用范围也跟着就日趋扩大，从而解决了之前人们可望而不可及的一些实际问题和模型，使人们获得巨大的经济效益6。常规的手工解法解决线性规划问题是复杂和耗时的，而MATLAB功能的强大，能够很好地处理线性规划问题，可以快速进行数值的求解，并绘制出相关线性图形，这样可以避免手工的繁琐计算，减少工作量，提高工作效率和结果的准确性，同样可以培养应用能力，非常方便实用。第2章 线性规划简介21 线性规划研究的背景和意义线性规划(Linear Programming)概念是在1947年的军事行动计划相关实践中产生的，但是在1823年Fourier和1911年Poussin就已经提出过相关问题，发展至今已有近100年的历史了。简单来说，线性规划就是在满足所有的线性约束条件下，求出目标函数的极大值或极小值。线性规划是运筹学最基本、研究较早也最为深入、发展较快、运用最广泛、理论较成熟、方法较完善的一个重要分支，是运筹学其他众多问题研究的基础，它又与数学方法紧密结合，成为应用数学的一个重要分支。线性规划是帮助人们进行科学管理的一种数学方法。其他科学领域的很多问题也因为线性规划的研究发展迅速也得到了发展研究。数学中的其他问题的研究例如非线性规划、整数规划等也因为线性规划的研究成果得到了很大的推进。 线性规划的数学模型及其特点线性规划是数学的一个极其重要的分支，其研究的主要问题8是对“资源”的合理分配，即如何利用有限的“资源”去完成更多的任务；或者确定一个任务的标准，如何统筹安排，做到利用尽可能少的“资源”去完成任务。其主要方法是对目标问题建立合理的线性规划模型，以数学方法为工具求出所建模型的最优结果。通俗地说线性规划所研究的主要问题是研究怎么从多个可能的方案中选出最合理的、能实现预定最优目标的方案，也就是我们常说的最优方案。线性规划(Linear Programming)问题简称为LP问题，它首先必须得是个数学问题，然后还必须同时具备以下特点9-11：决策变量是一组用来表示某一方案的未知数，不同设计方案的决策变量取值也不同。在实际应用中，通常对决策变量的取值要求为非负值。约束条件是一组线性的等式或线性不等式，它是用来描述决策变量在取值时必须同时满足的一些互不矛盾的限制条件。目标函数是用来表示满足目标要求的一组未知数的线性函数，根据实际所求问题的不同，要求目标函数实现最大化或最小化。而线性规划(LP)其实就是一种理论和方法，它是对研究和解决LP问题的所有工作的总称。线性规划模型首先必须是个数学模型，同时它还必须满足上述所有特点。它的一般形式的数学模型为：（）其中，xj(j=1,2，n)是问题的决策变量，记为 。 即是所寻求的目标函数，记为 为价值向量，其中cj(j=1,2，n)称作价值系数。由所有aij构成的被称为系数约束矩阵， Pj，j=1，2,，n为其中的列向量。向量 称为右端向量，bi，i=1，2,，m为右端顶。cj、bi、aij是LP问题的参数，通常情况下它的值可以被预测估计。xj(j=1,2，n)0是LP问题所限制的非负约束。 与 相互等价。所以，在这里我们规定LP问题的常用形式为求最大值，并且mn。 在实际应用中，很多时候人们为了方便就只研究问题的特殊情况，然后就会把一般复杂的情况转变为特殊情况来求解。比如LP，经常被研究的情况如下： （） 这里的bi0(i=1，2，m)，（）即为LP的规范表达式。 当决策变量所受到的限制约束都可以由线性等式来表述时，即有如下表达式： （） 这里的bi0(i=1，2，m)，（）规定了LP的标准形式。 以上三种形式是LP问题的所有典范表达形式。三种形式之间不仅可以进行相互的转化，而且所求出的解也是相同的。所以，这三种形式在本质上是相互等价的。 综上所述，我们可以看出，决策变量、约束条件和目标函数是LP模型必不可少的重要模块12。所以，在实际的操作中，想要建立出它的数学模型，就必须有以下三个关键步骤13： 首先，必须找出问题的决策变量，可以通过观察对所求目的产生作用的有关因素来寻找。 其次，明确问题的约束条件，这个可以通过限制决策变量的全部情况来确定。 最后，确定问题的目标函数，这个可以通过决策变量与问题的目标要求之间的线性关系来确定。 在实际工作与生活当中，线性规划问题普遍存在也有着广泛的应用，企业在经营管理中运用线性规划方法，可以方便快捷地解决问题例如在生产计划安排中，选择什么样的生产计划才能提高产值和利润等。生活中还有许多问题诸如生产调度、运输与物质调配、人员安排、投资组合、交通调度、配料、管道设计、背包负荷装载、电子线路设计中的连线问题、食物营养调配问题等都可以用线性规划的数学模型来描述，因此线性规划在实际生活中具有很强的实用性，它可以提供在日常生产生活中的配置问题的最优化方案。 23 求解线性规划问题一般常用的方法 求解线性规划问题一般常用的方法主要有以下三种： 图解法 图解法是指利用几何特征来求出线性规划问题中最优解的方法。图解法简单直观，但是它只适用于求解线性规划问题中含两个变量、最多三个变量的问题。由于大多数线性规划问题的变量个数n3，因此图解法应用不多。 单纯形法 单纯形法是求解线性规划求解的主要方法，在实际中也得到最广泛的应用。 单纯形法求解线性规划问题的思路：在一般线性规划问题具有的方程个数小于线性方程组的变量数时，方程有不定的解。单纯形法求解线性规划的基本思想是依据问题，从一个基本可行解出发，然后判断该解使目标函数值是增大还是变小，从而改进目标函数的取值，直到目标函数求得最优基本可行解。 大M法 当线性规划的变量及约束方程比较多时，不容易求得初始基本可行解，而且还可能存在基本可行解不存在的情况。这时的解决方法是加入人造基变量，即采用大M法。这里所谓的人造基变量是指为了能应用单纯形法来迭代并求极值而引进的变量。 第3章 基于MATLAB的线性规划问题求解 MATLAB简介 MATLAB的全称是Matrix Laboratory（矩阵实验室）。诞生于20世纪70年代，最初的MATLAB软件包是1967年由穆勒()用Fortran语言编写的14。在1984年，美国Mathworks公司正式推出的MATLAB是一种集数值计算、符号运算、可视化建模、仿真和图形化处理等多功能于一体的杰出的图形化语言。MATLAB由于其内容丰富、使用上的方便、功能强大以及良好的用户界面，自推出以来，就被广泛应用在数学、建筑、商业、信息科学等领域，深受工程技术人员和科学研究人员的喜爱，现已被国际公认为最优秀的科技应用软件之一，被誉为“巨人肩上的工具”15。用MATLAB编写程序就像在纸上写出求解问题与用到的公式，所以它也被称为演算纸式科学算法语言，用户只需要列出数学表达式，它的结果就会以数值或图形的方式显示出来16。 MATLAB的特点是：强大的科学计算功能，附带的30多种面向不同领域的工具箱支持，以及图形图像处理功能等。界面友好，运算符灵活，用户使用方便，具有较高的编程效率。程序可移植性和开放性好，跨平台兼容。语言简单，代码灵活，扩充能力强。拥有广泛解决多学科专业领域内复杂问题的能力17。 MATLAB包含有30多个工具箱，其中优化工具箱（Optimization Toolbox）是应用最广泛，同时影响也是最大的，可以解决的实际工程问题很多。它的主要功能如下18： 求解线性规划和二次规划问题。 求解函数的最大、最小值。 求解大规模优化问题。 求解多目标优化问题。 求解非线性规划问题。 求解非线性的最小二乘。 其他问题。 MATLAB在线性规划中的应用 用于线性规划的MATLAB主要函数是Linprog。 假设线性规划问题的数学模型为 式中，f、x、b、beq、lb和ub为向量，A 和Aeq为矩阵。 需要注意的是，MATLAB中都是逐行给向量和矩阵赋值，行之间用分号“；”分隔开，每行元素之间可用“，”也可以用空格分隔开，矩阵右上角用符号“”表示转置运算。 Linprog函数的调用格式如下。 x,fval =linprog( f ,A, b )，求解线性规划问题的min fTx，约束条件为 ，同时返回解x处的目标函数值fval。 x,fval =linprog( f ,A, b，Aeq, beq)，求解线性规划问题的min fTx，约束条件为 ，但增加等式约束的条件，即 ；若不等式不存在，则令A= 、b= ，同时返回解x处的目标函数值fval。 x,fval =linprog( f ,A, b，Aeq, beq，lb, ub)，求解线性规划问题的min fTx，约束条件为 及 ，并定义变量x的下界lb和上界ub，使得x始终在该范围之内；若等式不存在，则令Aeq= 、beq= ，同时返回解x处的目标函数值fval。 x,fval =linprog( f ,A, b，Aeq, beq，lb, ub，x0 )，求解线性规划问题的min fTx，约束条件为 及 ，定义变量x的下界lb和上界ub，设x0为初值，同时返回解x处的目标函数值fval。 x,fval =linprog( f ,A, b，Aeq, beq，lb, ub，x0 ，options)，求解线性规划问题的min fTx，约束条件为 及 ，定义变量x的下界lb和上界ub，设x0为初值，用options指定的优化参数进行最小化，同时返回解x处的目标函数值fval。 x=linprog()，只是输出解x的值，不输出目标函数值fval。 第4章 范例分析 简单的线性规划问题 例1、求解下面的线性规划问题 解： MATLAB求解程序清单为 f= 2， 1，3， 5 ； A= 1，2，4 1；2，3， 1，1；1，0，1，1 ； b= 6，12，4 ； lb= 0，0，0，0 ； x，fval =linprog( f ，A， b， ， ，lb) 结果输出为 x=00000 26667 00000 40000 fval=226667 说明 x解为最优解，最优值为226667。 例2、求解下面的线性规划问题 解：将该模型按照MATLAB的要求转换为目标函数最小化，即 MATLAB求解程序清单为 f= 6， 4 ； A=2，3；4，2； b=100，120； lb= 0， 0 ； x，fval =linprog( f ，A， b， ， ，lb) 结果输出为 x=200000 200000 fval=200000 说明 x解为最优解，最优值为200000。 工程应用实例 例3、配棉问题 配棉问题即根据棉纱的质量指标，采用各种价格不同的棉花，按一定比例配制成纱，使其既达到质量指标，又使总成本最低，棉纱的质量指标一般由棉结和品质指标来决定，棉结粒数越少越好，品质指标越大越好。 第5章 结论 线性规划为硬性约束，在一定的条件下存在最优解，它在辅助企业经营决策、计划优化，对于企业优化配置资源，降低成本，完成效益最大化等方面都具有重要的作用。使用MATLAB优化函数linprog能帮助我们快速准确地求出满足全部约束条件的最优解。MATLAB因其强大的功能，极高的编程效率和计算效率，已逐渐成为国际控制界公认的计算标准，在许多领域都得到较为广泛的应用。使用MATLAB工具箱，只须要编写很简