《线性规划理论及其应用[开题报告]》由会员分享，可在线阅读，更多相关《线性规划理论及其应用[开题报告]（15页珍藏版）》请在金锄头文库上搜索。
1、毕业论文开题报告信息与计算科学 线性规划理论及其应用 一、选题的背景、意义121. 选题的背景线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分 支,它是辅助人们进行科学管理的一种数学方法。在经济管理、交通运输、工农业生 产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两 种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源 .线性规划所研究的是：在一定条 件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大化或最小化的问题， 最大化问题是要在
2、一个集合上使一个函数 达到最大，最小化问题是要在一个集合上使一个函数达到最小。 统称为线性规划问题。 满足线性约束条件的解叫做可行解， 由所有可行解组成的集合叫做可行域。 决策变量、 约束条件、目标函数是线性规划的三要素。随着计算机技术的发展和普及，线性规划 的应用越来越广泛。它已成为人们为合理利用有限资源制定最佳决策的有力工具。2. 选题的意义随着计算机技术的发展和普及，线性规划的应用越来越广泛。它已成为人们为合 理利用有限资源制定最佳决策的有力工具。随着经济全球化的不断发展，企业面临更加 激烈的市场竞争。企业必须不断提高盈利水平，增强其获利能力，在生产、销售、新产品研 发等一系列过程中只有
3、自己的优势，提高企业效率，降低成本，形成企业的核心竞争力，才 能在激烈的竞争中立于不败之地。过去很多企业在生产、运输、市场营销等方面没有利用线 性规划进行合理的配置，从而增加了企业的生产，使企业的利润不能达到最大化。在竞争日 益激烈的今天，如果还按照过去的方式，是难以生存的，所以就有必要利用线性规划的知识 对战略计划、生产，销售各个环节进行优化从而降低生产成本，提高企业的效率。在各类经济活动中，经常遇到这样的问题：在生产条件不变的情况下，如何通过统筹安排，改进生产 组织或计划，合理安排人力、物力资源，组织生产过程，使总的经济效益最好。这样的问题 常常可以化成或近似地化成所谓的“线性规划” （L
4、inear Programming,简记为LP）问题。 线性规划是应用分析、量化的方法，对经济管理系统中的人、财、物等有限资源进行统筹安 排，为决策者提供有依据的最优方案，以实现有效管理。利用线性规划我们可以解决很多问 题。如：在不违反一定资源限制下，组织安排生产，获得最好的经济效益（产量最多、利润 最大、效用最高）。也可以在满足一定需求条件下，进行合理配置，使成本最小。同时还可 以在任务或目标确定后，统筹兼顾，合理安排，用最少的资源（如资金，设备，原材料、人 工、时间等）去完成任务。二、研究的基本内容与拟解决的主要问题2.1 线性规划理论发展过程及方向2.1.1 线性规划发展过程 34法国数
5、学家J. - B.- J.傅里叶和C.瓦莱一普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。1939年苏联数学家 刀.B.康托罗维奇在生产组织与计划中的数学方法一书中提出线性规划问题，也未引起重视。1947年美国数学家G.B.丹奇克提出线性规划的一般数学模型和求解线性规划问题的通用方法一一单纯形法，为这门学科奠定了基础。1947年美国数学家J.von诺伊曼提出对偶理论，开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。50年代后对线性规划进行大量的
6、理论研究，并涌现出一大批新的算法。例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P. 沃尔夫提出分解算法等。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX, OPHEIE, UMPIRE等，可以很方便地求解几千个变量的线性规划问题。1979年苏联数学家L. G. Khachian提出解线性规划问题的椭球算法，并证明它 是多项式时间算法。1984年美国贝尔电话
7、实验室的印度数学家 N.卡马卡提出解线性规划问题的新的 多项式时间算法。用这种方法求解线性规划问题在变量个数为 5000 时只要单纯形法 所用时间的 1/50。现已形成线性规划多项式算法理论。 50年代后线性规划的应用范 围不断扩大。212线性规划理论的发展方向67线性规划在军事、工农业、交通和城镇规划等领域中得到广泛的应用。实际问题有的是 很大的，大到具有几万、几十万甚至上百万的变量和成千上万的约束条件。有的问题虽小些， 一般也有几百几千的变量和成百上千的约束条件。显然解这类问题都离不开计算机。常用的 计算机软件有LINGO,LINDO,MATLAB等。线性规划理论与大系统分析理论相结合，以
8、解决经济、社会、生态、和政治因素交织在 一起的复杂社会系统问题，或者解决设计、工艺、质量、生产计划、大型试验、技术改造、 成本价格、市场营销等因素交织在一起的企业管理中的复杂问题，是线性规划理论的主要方 向之一。在大系统理论中，对于一些含有几个层级的系统（系统含有分系统，分系统又含有子系 统，子系统又含有更小的子系统等），通常采用递阶分析的方法进行分解和分析。从系统观 点考虑问题的多学科优化理论和方法的研究与应用，已经成为线性规划理论的重要发展方向 之一。我国的现代化建设进程中，众多大系统工程（如三峡工程、载人航天工程）中，也 大量的采用了系统工程的一些科学方法，并取得了显著的成效。反过来，实
9、践的发展又不断 地催生新的理论，或者不断地开拓已有应用范围，不断地创新理论和方法，是所有学科发展 的生命力源泉之所在，线性规划理论的发展也不例外。2.2线性规划的具体实现2.21线性规划问题的基本步骤（1）提出并抽象问题（2）建立数学模型（3）求解（4）检验解（5）解得灵敏度分析(6) 解得回归2.2.2线性规划方法的运用原则 (1 )合作原则(2) 打破常规原则(3) 相互渗透原则(4) 客观独立性原则(5) 包容性原则(6) 平衡性原则2.2.3线性规划问题的数学模型的一般形式 (1) 列出约束条件及目标函数(2) 画出约束条件所表示的可行域( 3 )在可行域内求目标函数的最优解及最优值2
10、.2.4 线性规划的模型建立 129从实际问题中建立数学模型一般有以下三个步骤；1. 根据影响所要达到目的的因素找到决策变量；2. 由决策变量和所在达到目的之间的函数关系确定目标函数；3. 由决策变量所受的限制条件确定决策变量所要满足的约束条件。所建立的数学模型具有以下特点：1、每个模型都有若干个决策变量(x , x , x, x )，其中n为决策变量个数。123n决策变量的一组值表示一种方案，同时决策变量一般是非负的。2、目标函数是决策变量的线性函数，根据具体问题可以是最大化(max)或最小化(min)，二者统称为最优化(opt)。3、约束条件也是决策变量的线性函数。当我们得到的数学模型的目
11、标函数为线性函数，约束条件为线性等式或不等式时 称此数学模型为线性规划模型。2.2.5 线性规划的解法求解线性规划问题的基本方法是单纯形法，现在已有单纯形法的标准软件，可在电子计算机上求解约束条件和决策变量数达 10000 个以上的线性规划问题。为了提 高解题速度，又有改进单纯形法、对偶单纯形法、原始对偶方法、分解算法和各种多 项式时间算法。对于只有两个变量的简单的线性规划问题，也可采用图解法求解。这 种方法仅适用于只有两个变量的线性规划问题。它的特点是直观而易于理解，但实用 价值不大。通过图解法求解可以理解线性规划的一些基本概念。2.2.5.1 单纯形法 12单纯形法是求解线性规划问题的一般
12、方法，原则上它适用于任何线性规划问题。这是 丹齐克在1947年提出来的. 它的理论根据是：线性规划问题的可行域是 n 维向量空间 R 中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可 n行解称为基本可行解。大量的实际表明 ,这是一种行之有效的解法.单纯形法的基本思想 是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定 法则转换到另一改进的基本可行解 ,再鉴别；若仍不是，则再转换 ,按此重复进行。因 基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解 也可用此法判别。单纯形法的一般解题步骤可归纳如下： 把线性规划问题的约束方程
13、组表达成典范型方程组，找出基本可行解作为初始基本可行解。若基本可行解不存在，即约束 条件有矛盾，则问题无解。若基本可行解存在，从初始基本可行解作为起点，根据 最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另 一基本可行解。按步骤3进行迭代，直到对应检验数满足最优性条件（这时目标函 数值不能再改善），即得到问题的最优解。若迭代过程中发现问题的目标函数值无 界，则终止迭代。下面把单纯形法的计算步骤及迭代过程归结如下图：并得出单纯形表：C - C B -1A C B - 1bBBB-1 AB-1b这样就可以得出一般线性规划问题的解。有关单纯形法的进一步讨论，当线性规划问题化
14、为标准形式后约束条件的系数矩阵中含 有单位矩阵，以此作初始基，用人工变量法（大M法）求解。用大M法处理人工变量，在用 手工计算求解时不会碰到麻烦，但用电子计算机求解时，由于计算机取值时的误差，有可能 使计算结果发生错误。为了克服这个困难，可以对添加人工变量后的线性规划问题分两个阶 段来计算，称两阶段法。2.2.5.2 对偶单纯形法6每一个线性规划问题都有另一个与其相互关联的问题，这个新问题具有非常重要的性 质，用这些性质可以更加有效地获得原来问题的解。为区别起见，我们称原来的问题为原问 题，称与原问题相关联的问题为对偶问题。1. 对偶理论以如下的线性规划问题和其对偶问题：Ax bx 0wA 0
15、这里P表示原问题，D表示对偶问题。2. 对偶单纯形法对偶单纯形算法可以概括如下：（1）找出原问题的一个基B，构成起始对偶基可行解，是c对所有的j有c 一 z = c - C B-ia 0j j j Bj构成原始对偶单纯形法表；假如b = B-1b0，则当前的解是最优解，停止计算。否则选择枢行r，其br0，则对偶问题无界，原问题无解，停止计算。否则选择枢 rj列 k ；（4）以 y 为枢元素变换对偶单纯形表，然后转达步骤（2）。rk2.2.5.3 灵敏度分析26灵敏度分析一词的含义是指对系统或事物因周围条件变化显示出来的敏感程度 的分析。灵敏度分析意义很大。其一，很多实际问题中数据常常是不够精确的，很多 是估计出来的，因此调整数据是常事。其二，当一个用于决策的问题得出最优解后， 决策者为了通观全局，常常要研究其中某些因素（数据）的改变对当前最优决策所造 成的影响。其三，当作多种方案比较时，这些不同方案常常是某些数据不同而已。灵 敏度分析的步骤可归纳如下：1. 将参数的改变通过计算反映到最终单纯形表来。具体方法是，按照下列公式计算出由参数 a ，b
