1、 本科 毕业论文 （ 设计 ） （ 20 届） 线性规划理论及其应用 所在学院 专业班级 信息与计算科学 学生姓名 学号 指导教师 职称 完成日期 年 月 I 摘要 :线性规划是运筹学的一个重要分支，并应用到社会各个方面。本文首先介绍了线性规划理论产生的背景和意义，以及它的发展过程和发展方向 。接着叙述了解决线性规划问题的方法及其算法。我们通过分析问题建立数学模型，使用适当方法求出最优解，并对其进行分析得到该问题的最优值。最后运用线性规划理论来解决相关实际问题，即它被应用的过程。 关键词 :线性规划；数学模型；单纯形法 II The Theoretical analysis and Appli
2、cation of Linear Programming Abstract:Linear programming is an important branch of operations research, and its applied to all aspects of the society In this paper the background and sense of the linear programming theory, the development history and direction of linear programming theory are introd
3、uced Then the methods and algorithms of solving the linear programming problems are described We can build a mathematical model by analyzing the problem,obtain an optinum solution in the proper way and analyze the solution to obtain the optimal value of the linear problem Finally, the relational pra
4、ctical problem is solved by using the linear programming theory That is the process of its application Keywords: Linear programming; Mathematical models; Simplex method III 目录 1. 绪论 . 1 1.1 线性规划理论的背景 . 1 1.2 线性规划理论的意义 . 1 2. 线性规划理论概述 . 3 2.1 线性规划的发展过程及其现状 . 3 2.2 线性规划的发展方向 . 3 3. 线性规划的具体实现 . 5 3.1 线
5、性规划的基本步骤和基本原则 . 5 3.2 线性规划的模型建立和一般形式 . 5 3.3 线性规划的解法 . 6 3.3.1 单纯形法 . 6 3.3.2 对偶单纯形法 . 7 3.4 灵敏度分析 . 8 3.5 线性规划的其他算法和问题 . 9 4. 线性规划的应用 . 11 4.1 线性规划应用的现实意义 . 11 4.2 线性规划的应用实例 . 11 5. 线性规划的软件实现 . 13 5.1 线性规划在 LINDO 中的实现 . 13 5.2 线性规划在 MATLAB 中的实现 . 15 6. 结论 . 20 致谢 . 错误 !未定义书签。 参考文献 . 21 1 1. 绪论 1.1
6、线性规划理论的背景 线性规划 是 运筹学 中研究较早、发展较快、应用 广泛、方法成熟的一个重要分支 ,它是辅助人们进行科学管理的一种数学方法 。 在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料。二是生产组织与计划的改进，即合理安排人力物力资源。线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好。一般地，求线性目标函数在线性约束条 件 下的最大 化 或最小 化 的问题， 最大化问题是要在一个集合上使一个函数达到最大，最小化问题是要在一个集合上使一
7、个 函数达到最小。 统称为线性规划问题。满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素 。随着计算机技术的发展和普及，线性规划的应用越来越广泛。它已成为人们为合理利用有限资源制定最佳决策的有力工具。 12 1.2 线性规划理论的意义 随着 计算机技术的发展和普及，线性规划的应用越来越广泛。它已成为人们合理利用有限资源制定最佳决策的有力工具。 随着经济全球化的不断发展，企业面临更加激烈的市场竞争。企业必须不断提高盈利水平，增强其获利能力，在生产、销售、新产品 研发等一系列过程中只有自己的优势，提高企业效率，降低成本，形成企业的核心
8、竞争力，才能在激烈的竞争中立于不败之地。过去很多企业在生产、运输、市场营销等方面没有利用线性规划进行合理的配置，从而增加了企业的生产，使企业的利润不能达到最大化。在竞争日益激烈的今天，如果还按照过去的方式，是难以生存的，所以就有必要利用线性规划的知识对战略计划、生产，销售各个环节进行优化从而降低生产成本，提高企业的效率。在各类经济活动中，经常遇到这样的问题：在生产条件不变的情况下，如何通过统筹安排，改进生产组织或计划，合理安排人力、物力 资源，组织生产过程，使总的经济效益最好。这样的问题常常可以化成或近似地化成所谓的“线性规划” (Linear Pmgramming， 简记为 LP)问题。线性
9、规划是应用分析、量化的方法，对经济管理系统中的人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现有效管理。利用线性规划我们可以解决很多问题。如：在不违反一定资源限制下，组织安排生产，获得最好的经济效益 (产量最多、利润最大、效用最高 )。也可以在满足一定需求条件下，进行合理配置，使成本最小。同时还 可以在任2 务或目标确定后，统筹兼顾，合理安排， 用最少的资源 (如资金、设备、原材料、人工、时间等 )去完成任务。 12 3 2. 线性规划理论概述 2.1 线性规划的发展过程及其现状 法国数学家 J.- B.- J.傅里叶和 C.瓦莱普森分别于 1832 和 1911 年独立
10、地提出线性规划的想法，但未引起注意。 1939 年苏联数学家 . .康托罗维奇在生产组织与计划中的数学方法一书中提出线性规划问题，也未引起重视。 1947 年美国数学家 G.B.丹奇克 提出线性规划的一般数学模型和求 解线性规划 问题的通用方法 单纯形法 ，为这门学科奠定了基础。 1947 年美国数学家 J.von 诺伊曼提出 对偶 理论 ,开创了线性规划的许多新的研究领域，扩 大了它的应用范围和解题能力。 1951 年美国经济学家 T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获 1975 年诺贝尔经济学奖。 50 年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。
11、例如， 1954年 C.莱姆基提出对偶单纯形法， 1954 年 S.加斯和 T.萨迪等人解决了线性规划的 灵敏度分析 和参数规划问题， 1956 年 A.塔克提出互补松弛定理， 1960 年 G.B.丹齐克和 P.沃尔夫提出分解算法等。 线性规划的研究成果还直接推动了其他数学规划问题包括 整数规划 、随机规划和非线性规划 的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX， OPHEIE， UMPIRE 等，可以很方便地求解几千个变量的 线性规划问题。 1979 年苏联数学家 L. G. Khachian 提出解线性规划问题的椭球算法，并证明它是多项式时间算法。 1984
12、 年美国贝尔电话实验室的印度数学家 N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为 5000 时只要单纯形法所用时间的 1/50。现已形成线性规划多项式算法理论。 50 年代后线性规划的应用范围不断扩大。 34 2.2 线性规划的发展方向 线性规划在军事、工农业、交通和城镇规划等领域中得到广泛的应用。实际问题有的是很大的，大到具有几万、几十万甚至上百 万的变量和成千上万的约束条件。有的问题虽小些，一般也有几百几千的变量和成百上千的约束条件。显然解这类问题都离不开计算机。常用的计算机软件有 LINGO,LINDO,MATLAB等。 4 线性规划理论与大系
13、统分析理论相结合，以解决经济、社会、生态、和政治因素交织在一起的复杂社会系统问题，或者解决设计、工艺、质量、生产计划、大型试验、技术改造、成本价格、市场营销等因素交织在一起的企业管理中的复杂问题，是线性规划理论的主要方向之一。 在大系统理论中，对于一些含有几个层级的系统（系统含有分系统，分系统又含有子系统，子系统 又含有更小的子系统等），通常采用递阶分析的方法进行分解和分析。从系统观点考虑问题的多学科优化理论和方法的研究与应用，已经成为线性规划理论的重要发展方向之一 。我国的现代化建设进程中，众多大系统工程（如三峡工程、载人航天工程）中，也大量的采用了系统工程的一些科学方法，并取得了显著的成效
14、。反过来，实践的发展又不断地催生新的理论，或者不断地开拓已有应用范围，不断地创新理论和方法，是所有学科发展的生命力源泉之所在，线性规划理论的发展也不例外。 567 5 3. 线性规划的具体实现 3.1 线性规划的基本步骤和基本原则 线性规划问题的基本步骤 8 （ 1）提出并抽象问题 （ 2）建立数学模型 （ 3）求解 （ 4）检验解 （ 5）解的灵敏度分析 （ 6） 解的回归 线性规划方法的运用原则 8 （ 1）合作原则 （ 2）打破常规原则 （ 3）相互渗透原则 （ 4）客观独立性原则 （ 5）包容性原则 （ 6）平衡性原则 3.2 线性规划的模型建立和一般形式 线性规划的模型建立 129
15、从实际问题中建立数学模型一般有以下三个步骤； 1 根据影响所要达到目的的因素找到决策变量； 2 由决策变 量和所在达到目的之间的函数关系确定目标函数； 3 由决策变量所受的限制条件确定决策变量所要满足的约束条件。 所建立的数学模型具有以下特点： 1、每个模型都有若干个决策变量 1 2 3( , , , )nx x x x ，其中 n 为决策变量个数。决策变量的一组值表示一种方案，同时决策变量一般是非负的。 2、目标函数是决策变量的线性函数，根据具体问题可以是最大化 (max) 或最小化 (min) ，二者统称为最优化 ()opt 。 3、约束条件也是决策变量的线性函数。 6 当我们得到的数学模
16、型的目标函数为线性函数，约束条件为线性等式或不等式时称此数学模型为线性规划模型。 线性规划问题的数学模型的一般形式 2 （ 1）列出约束条件及目标函数 （ 2）画出约束条件所表示的可行域 （ 3）在可行域内求目标函数的最优解及最优值 3.3 线性规划的解法 求解线性规划问题的基本方法是单纯形法，现在已有单纯形法的标准软件，可在电子计算机上求解约束条件和决策变量数达 10000 个以上的线性规划问题。为了提高解题速度，又有改进单纯形法、对偶单纯形法、原始对偶方法、分解算法和各种多项式时间算法。对于只有两个变量的简单的线性规划问题，也可采用图解法求解。这种方法仅适用于只有两个变量的线性规划问题。它
17、的特点是直观而易于理解，但实用价值不大。通过图解法求解可以理解线性规划的一些基本概念。 3.3.1 单纯形法 单纯形法是求解线性规划问题的一般方法，原则上它适用于任何线性规划问题。这是丹齐克在 1947 年提出来的。 它的理论根据是：线性规划问题的可行域是 n 维向量空间 nR 中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。 大量的实际表明 ,这是一种行之有效的解法。 单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解 ,再鉴别；若仍不是，则再转换 ,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无 最优解 也可用此法判别 。 单纯形法的一般解题步骤可归纳如下： 把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。 若基本可行解不存在，即约束条件有矛盾，则问题无解。 若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。 按步骤 3 进行迭代 ,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。 若迭代过程中发现问题的目标函数值无
