MATLAB在线性规划中的应用.docVIP

　　MATLAB在线性规划中的应用 第1章 引言 线性规划是指如何最有效或最佳地策划经济活动，也就是一定的约束条件下，求目标函数极值的问题[1]。在1823年Fourier和1911年Poussin就已经提出过相关的问题[2]，随后由L.V..Kantorovich[3] (苏联数学家)在1939年出版的白皮书《Mathematical Methods in the Organization and Planning of Production》中，对线性规划的思想做了最早的阐述。现在，线性规划已被广泛应用于军事行动、管理、工程技术和经济分析等方面，合理利用有限的人力、物力资源、财政资源等，为决策者做出最优决策提供科学依据，辅助和指导人们进行科学的管理和规划[4]。在实际应用中，人们发现经常遇到一些问题的规模比较大，由此，G. B. Dantzig又与P.ATLAB功能的强大，能够很好地处理线性规划问题，可以快速进行数值的求解，并绘制出相关线性图形，这样可以避免手工的繁琐计算，减少工作量，提高工作效率和结果的准确性，同样可以培养应用能力，非常方便实用。 ? 第2章 线性规划简介 2．1 线性规划研究的背景和意义 线性规划(Linear Programming)概念是在1947年的军事行动计划相关实践中产生的，但是在1823年Fourier和1911年Poussin就已经提出过相关问题[７]，发展至今已有近100年的历史了。简单来说，线性规划就是在满足所有的线性约束条件下，求出目标函数的极大值或极小值。线性规划是运筹学最基本、研究较早也最为深入、发展较快、运用最广泛、理论较成熟、方法较完善的一个重要分支，是运筹学其他众多问题研究的基础，它又与数学方法紧密结合，成为应用数学的一个重要分支。 线性规划是帮助人们进行科学管理的一种数学方法。其他科学领域的很多问题也因为线性规划的研究发展迅速也得到了发展研究。数学中的其他问题的研究例如非线性规划、整数规划等也因为线性规划的研究成果得到了很大的推进。。 2.2 线性规划的数学模型及其特点 线性规划是数学的一个极其重要的分支，其研究的主要问题[8]是对“资源”的合理分配，即如何利用有限的“资源”去完成更多的任务；或者确定一个任务的标准，如何统筹安排，做到利用尽可能少的“资源”去完成任务。其主要方法是对目标问题建立合理的线性规划模型，以数学方法为工具求出所建模型的最优结果。通俗地说线性规划所研究的主要问题是研究怎么从多个可能的方案中选出最合理的、能实现预定最优目标的方案，也就是我们常说的最优方案。 线性规划(Linear Programming)问题简称为LP问题，它首先必须得是个数学问题，然后还必须同时具备以下特点[9-11]： ①决策变量是一组用来表示某一方案的未知数，不同设计方案的决策变量取值也不同。在实际应用中，通常对决策变量的取值要求为非负值。 ②约束条件是一组线性的等式或线性不等式，它是用来描述决策变量在取值时必须同时满足的一些互不矛盾的限制条件。 ③目标函数是用来表示满足目标要求的一组未知数的线性函数，根据实际所求问题的不同，要求目标函数实现最大化或最小化。 而线性规划(LP)其实就是一种理论和方法，它是对研究和解决LP问题的所有工作的总称。线性规划模型首先必须是个数学模型，同时它还必须满足上述所有特点。它的一般形式的数学模型为： （2.1） 其中，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，经常被研究的情况如下： （2.2）这里的bi≥0(i=1，2，…，m)，（2.2）即为LP的规范表达式。当决策变量所受到的限制约束都可以由线性等式来表述时，即有如下表达式： （2.3）这里的bi≥0(i=1，2，…，m)，（2.3）规定了LP的标准形式。以上三种形式是LP问题的所有典范表达形式。三种形式之间不仅可以进行相互的转化，而且所求出的解也是相同的。所以，这三种形式在本质上是相互等价的。综上所述，我们可以看出，决策变量、约束条件和目标函数是LP模型必不可少的重要模块[12