线性规划理论及其应用[开题报告].doc

1、毕业论文 开题报告 信息与计算科学 线性规划理论及其应用 一、选题的背景、意义 12 1.选题的背景 线性规划是 运筹学 中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支 ,它是辅助人们进行科学管理的一种数学方法 。 在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料 .二是生产组织与计划的改进，即合理安排人力物力资源 .线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果 达到最好 .一般地，求线性目标函数在线性约束条 件 下的最大 化 或最小 化

2、 的问题， 最大化问题是要在一个集合上使一个函数达到最大，最小化问题是要在一个集合上使一个函数达到最小。 统称为线性规划问题。满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素 。随着计算机技术的发展和普及，线性规划的应用越来越广泛。它已成为人们为合理利用有限资源制定最佳决策的有力工具。 2.选题的意义 随着计算机技术的发展和普及，线性规划的应用越来越广泛。它已成为人们为合理利用有限资源制定 最佳决策的有力工具。 随着经济全球化的不断发展，企业面临更加激烈的市场竞争。企业必须不断提高盈利水平，增强其获利能力，在生产、销售、新产品研发

3、等一系列过程中只有自己的优势，提高企业效率，降低成本，形成企业的核心竞争力，才能在激烈的竞争中立于不败之地。过去很多企业在生产、运输、市场营销等方面没有利用线性规划进行合理的配置，从而增加了企业的生产，使企业的利润不能达到最大化。在竞争日益激烈的今天，如果还按照过去的方式，是难以生存的，所以就有必要利用线性规划的知识对战略计划、生产，销售各个环节进行优化从而降低生产成本 ，提高企业的效率。在各类经济活动中，经常遇到这样的问题：在生产条件不变的情况下，如何通过统筹安排，改进生产组织或计划，合理安排人力、物力资源，组织生产过程，使总的经济效益最好。这样的问题常常可以化成或近似地化成所谓的“线性规划

4、” (Linear Programming， 简记为 LP)问题。线性规划是应用分析、量化的方法，对经济管理系统中的人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现有效管理。利用线性规划我们可以解决很多问题。如：在不违反一定资源限制下，组织安排生产，获得最好的经济效益 (产量最多、利润最大、效用最高 )。也可以在满足一定需求条件下，进行合理配置，使成本最小。同时还 可以在任务或目标确定后，统筹兼顾，合理安排，用最少的资源 (如资金，设备，原材料、人工、时间等 )去完成任务。 二、研究的基本内容与拟解决的主要问题 2.1 线性规划理论发展过程及方向 2.1.1 线性规划发展

5、过程 34 法国数学家 J.- B.- J.傅里叶和 C.瓦莱普森分别于 1832 和 1911 年独立地提出线性规划的想法，但未引起注意。 1939 年苏联数学家 . 康托罗维奇在生产组织与计划中的数学方法一 书中提出线性规划问题，也未引起重视。 1947 年美国数学家 G.B.丹奇克 提出线性规划的一般数学模型和求 解线性规划 问题的通用方法 单纯形法 ，为这门学科奠定了基础。 1947 年美国数学家 J.von 诺伊曼提出 对偶 理论 ,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。 1951 年美国经济学家 T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一

6、起获 1975 年诺贝尔经济学奖。 50 年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如， 1954年 C.莱姆基提出对偶单纯形法， 1954 年 S.加斯和 T.萨迪等人解决了线性规划的 灵敏度分析 和参数规划问题， 1956 年 A.塔克提出互补松弛定理， 1960 年 G.B.丹齐克和 P.沃尔夫提出分解算法等。 线性规划的研究成果还直接推动了其他数学规划问题包括 整数规划 、随机规划和非线性规划 的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX， OPHEIE， UMPIRE 等，可以很方便地求解几千个变量的线性规划问题。 1979 年苏联数学

7、家 L. G. Khachian 提出解线性规划问题的椭球算法，并证明它是多项式时间算法。 1984 年美国贝尔电话实验室的印度数学家 N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为 5000 时只要单纯形法所用时间的 1/50。现已形成线性规划多项式算法理论。 50 年代后线性规划的应用范围不 断扩大。 2.1.2 线性规划理论的发展方向 567 线性规划在军事、工农业、交通和城镇规划等领域中得到广泛的应用。实际问题有的是很大的，大到具有几万、几十万甚至上百万的变量和成千上万的约束条件。有的问题虽小些，一般也有几百几千的变量和成百上千的约束条件。显然

8、解这类问题都离不开计算机。常用的计算机软件有 LINGO,LINDO,MATLAB 等。 线性规划理论与大系统分析理论相结合，以解决经济、社会、生态、和政治因素交织在一起的复杂社会系统问题，或者解决设计、工艺、质量、生产计划、大型试验、技术 改造、成本价格、市场营销等因素交织在一起的企业管理中的复杂问题，是线性规划理论的主要方向之一。 在大系统理论中，对于一些含有几个层级的系统（系统含有分系统，分系统又含有子系统，子系统又含有更小的子系统等），通常采用递阶分析的方法进行分解和分析。从系统观点考虑问题的多学科优化理论和方法的研究与应用，已经成为线性规划理论的重要发展方向之一 。我国的现代化建设进

9、程中，众多大系统工程（如三峡工程、载人航天工程）中，也大量的采用了系统工程的一些科学方法，并取得了显著的成效。反过来，实践的发展又不断地催生新的理论，或者 不断地开拓已有应用范围，不断地创新理论和方法，是所有学科发展的生命力源泉之所在，线性规划理论的发展也不例外。 2.2 线性规划的具体实现 2.2.1 线性规划问题的基本步骤 8 （ 1）提出并抽象问题 （ 2）建立数学模型 （ 3）求解 （ 4）检验解 （ 5）解得灵敏度分析 （ 6） 解得回归 2.2.2 线性规划方法的运用原则 8 （ 1）合作原则 （ 2）打破常规原则 （ 3）相互渗透原则 （ 4）客观独立性原则 （ 5）包容性原则

10、（ 6）平衡性原则 2.2.3 线性规划问题的数学模型的一般形式 2 （ 1）列出约束条件及 目标函数 （ 2）画出约束条件所表示的可行域 （ 3）在可行域内求目标函数的最优解及最优值 2.2.4 线性规划的模型建立 129 从实际问题中建立数学模型一般有以下三个步骤； 1.根据影响所要达到目的的因素找到决策变量； 2.由决策变量和所在达到目的之间的函数关系确定目标函数； 3.由决策变量所受的限制条件确定决策变量所要满足的约束条件。 所建立的数学模型具有以下特点： 1、每个模型都有若干个决策变量 1 2 3( , , , )nx x x x ，其中 n 为决策变量个数。决策变量的一组值表示一种

11、方案，同时决策变量一般是非负的。 2、目标函数是决策变量的线性函数，根据具体问题可以是最大化 (max) 或最小化 (min) ，二者统称为最优化 ()opt 。 3、约束条件也是决策变量的线性函数。 当我们得到的数学模型的目标函数为线性函数，约束条件为线性等式或不等式时称此数学模型为线性规划模型。 2.2.5 线性规划 的解法 求解线性规划问题的基本方法是单纯形法，现在已有单纯形法的标准软件，可在电子计算机上求解约束条件和决策变量数达 10000 个以上的线性规划问题。为了提高解题速度，又有改进单纯形法、对偶单纯形法、原始对偶方法、分解算法和各种多项式时间算法。对于只有两个变量的 简单的线性

12、规划 问题，也可采用图解法求解。这种方法仅适用于只有两个变量的线性规划问题。它的特点是直观而易于理解，但实 用价值不大。通过图解法求解可以理解线性规划的一些基本概念。 2.2.5.1 单纯形法 12 单纯形法是求解线性规划问题的一般方法，原则上它适用于任何线性规划问题。这是丹齐克在 1947 年提出来的 . 它的理论根据是：线性规划问题的可行域是 n 维向量空间nR 中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。 大量的实际表明 ,这是一种行之有效的解法 .单纯形法的基本思想是：先找 出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定

13、法则转换到另一改进的基本可行解 ,再鉴别；若仍不是，则再转换 ,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无 最优解也可用此法判别 。 单纯形法的一般解题步骤可归纳如下： 把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。 若基本可行解不存在，即约束条件有矛盾，则问题无解。 若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标 函数值更优的另一基本可行解。 按步骤 3 进行迭代 ,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。 若迭代过程

14、中发现问题的目标函数值无界，则终止 迭代 。 下面把单纯形法的计算步骤及迭代过程归结如下图： 并得出 单纯形表： 1111BBC C B A C B bB A B b这样就可以得出一般线性规划问题的解。 有关单纯形法的进一步讨论，当线性规划问题化为标准形式后约束条件的系数矩阵中含有单位矩阵，以此作初始基，用人工变量法（大 M 法）求解。用大 M 法处理人工变量，在用手工计算求解时不会碰到麻烦，但用电子计算机求解时，由于计算机取值时的误差，有可能使计算结果发生错误。为了克服这个困难，可以对添加人工变量后的线性规划问题分两个阶段来计算，称两阶段法。 2.2.5.2 对偶单纯形法 6 每一个线性规划

15、问题都有另一个与其相互关联的问题，这个新问题具有非常重要的 性质，用这些性质可以更加有效地获得原来问题的解。为区别起见，我们称原来的问题为原问题，称与原问题相关联的问题为对偶问题。 1.对偶理论 以如下的线性规划问题和其对偶问题： :min. 0P cxAx bstx:max. 0D wbwA cstw这里 P 表示原问题， D 表示对偶问题。 2.对偶单纯形法 对偶单纯形算法可以概括如下： (1)找出原问题的一个基 B ，构成起始对偶基可行解，是 c 对所有的 j 有 1 0 j j j B jc z c C B a 构成原始对偶单纯形法表； (2)假如 1 0b B b ,则当前的解是最优

16、解，停止计算。否则选择枢行 r ，其 0rb ， 例如选择你最小者： minriibb (3)假如对所有列 ,0rjjy ，则对偶问题无界，原问题无解，停止计算。否则选择枢列 k ； （ 4）以 rky 为枢元素变换对偶单纯形表，然后转达步骤（ 2）。 2.2.5.3 灵敏度分析 26 灵敏度 分析一词的含义是指对系统或事物因周围条件变化显示出来的敏感程度的分析。灵敏度分析意义很大。其一，很多实际问题中数据常常是不够精确的，很多是估计出来的，因此调整数据是常事。其二，当一个用于决策的问题得出最优解后，决策者为了通观全局，常常要研究其中某些因素（数据）的改变对当前最优决策所造成的影响。其三，当作

17、多种方案比较时，这些不同方案常常是某些数据不同而已。灵敏度分析的步骤可归纳如下： 1.将参数的改变通过计算反映到最终单纯形表来。具体方法是，按照下列公式计算出由参数 ija ， ib ， jc 的变化而引起的最终单纯形表上有关数字的变化。 1b B b 1jjp B p 1()mj j j ij iic z c a y 2. 检查原问题是否仍为可行解。 3. 检查对偶问题是否仍为可行解。 4. 按下表所列情况得出结论或决定继续计算的步骤。 原问题 对偶问题 结论或继续计算的步骤 可行解 可 行解 问题的最优解或最优基不变 可行解 非可行解 用单纯形法继续迭代求最优解 非可行解 可行解 用对偶单

18、纯形法继续迭代求最优解 非可行解 非可行解 引用人工变量，编制新的单纯形表重新计算 2.2.6 线性规划的其他算法和问题 16 1.分解算法 分解算法是一种处理大型问题的方法，它把一个大型问题分解成若干个规模较小的问题来求解，这种方法不仅可以减少存储量，也能减少计算量。因为线性规划的计算量对于约束条件的个数 m 很敏感，统计表明，计算量大约与 3m 成正比，因此，若把一个大型问题转化为求解若干个小型问题，由于每个小型问题的约束条件个数较少，可使总的计算量大大减少。 2. Karmarkar 算法 1984 年 N.Karmarkar 提出了一个属于多项式时间算法的内点法，并证明其计算复杂性是

19、0，这是一种能解决大型线性规划问题的强有力的算法。它的应用十分广泛，如 应用这一系统规模的多项式时间算法用于电力系统，可以使实时电价计算等问题变的简单。 3.整数线性规划问题 在线性规划问题中，当某些变量（或全部变量）取整数值时，该规划问题就称为整数规划问题。整数规划可以 看成是线性规划问题中对变量进行整数约束的一种特殊形式，因此，可以认为，整数规划问题一般要比相应的线性规划问题约束得更紧。整数规划中，如果所有的变量都要求取整数值，则称此规划问题为纯整数规划；如果部分变量要求取整数值，则称此规划问题为混合整数规划；如果要求变量的取值为 0 或 1，则称此规划问题为 0-1 规划。 4.影子价格

20、与影子成本 10 根据线性规划问题对偶变量和影子价格的经济意义，给出了影子成本的概念，讨论了影子成本与对偶价格的关系。通过灵敏度分析给出了影子成本的动态表示，并进一步阐明了影子价格和影子成本的 惟一性以及影子成本在经济管理中的应用。 5. 有界变量线性规划问题 实际应用中的许多线性规划问题，其决策变量具有上、下界限制。这类问题称为有界变量线性规划问题。它的一般数学模型可写为 0min x cx ， .stAx b ， l x u, 其中， 1 2 1 2( , , . . . , ) , ( , , . . . , )TTnnl l l l U U U U分别为 12( , ,., )Tnx

21、x x x 的下界和上界；A 认为 mn 阶矩阵， 1nm，并设 A 的秩为 m . 2.3 线性规划理论的应用 2.3.1 线性规划在企业中运用的必要性 11 随着经济全球化的不断发展，企业面临更加激烈的市场竞争。企业必须不断提高盈利水平，增强其获利能力，在生产、销售、新产品研发等一系列过程中只有自己的优势 ，提高企业效率，降低成本，形成企业的核心竞争力，才能在激烈的竞争中立于不败之地。过去很多企业在生产、运输、市场营销等方面没有利用线性规划进行合理的配置，从而增加了企业的生产，使企业的利润不能达到最大化。在竞争日益激烈的今天，如果还按照过去的方式，是难以生存的，所以就有必要利用线性规划的知

22、识对战略计划、生产，销售各个环节进行优化从而降低生产成本，提高企业的效率。在各类经济活动中，经常遇到这样的问题：在生产条件不变的情况下，如何通过统筹安排，改进生产组织或计划，合理安排人力、物力资源，组织生产过程，使总的经济效 益最好。这样的问题常常可以化成或近似地化成所谓的“线性规划” (Linear Pmgramming， 简记为 LP)问题。线性规划是应用分析、量化的方法，对经济管理系统中的人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现有效管理。利用线性规划我们可以解决很多问题。如：在不违反一定资源限制下，组织安排生产，获得最好的经济效益 (产量最多、利润最大、效用

23、最高 )。也可以在满足一定需求条件下，进行合理配置，使成本最小。同时还 可以在任务或目标确定后，统筹兼顾，合理安排，用最少的资源 (如资金，设备，原材 料、人工、时间等 )去完成任务。 2.3.2 线性规划的应用实例 数学与经济的结合由来已久。从经济学作为一门学科的发展看，数学在其中的位置越来越重要，它 不仅帮助人们在经营中获利，而且给予人们以能力， 包括直观思维、逻辑思维、精确计算等等，以至于今 天，不懂数学就无法研究经济。前苏联数学家坎托 罗维奇因对物资最优调拨理论的贡献获 1975年诺 贝尔奖，他被公认为最优规划理论的创始人，经济数学理论的奠基人。坎托罗维奇创造的线性规划方法 被广泛地应

24、用于经济领域并为经济发展作出了卓越 贡献。 12 线性规划作为运筹学的一个重要分 支，在经济管理中有着极其广泛的应用，比如 设计一个物流网络的问题。 13以下是一些常用的应用举例。 1.线性规划在薪酬管理中的应用 14 知识经济时代，现代化的大型企业或企业集团不断涌现，大企业的内部管理模式更加复杂，必须提高企业内部的控制力、执行力、及对市场变化能够快速做出的反应能力。线性规划是人们进行科学管理的一种数学方法，通过在薪酬管理宏观和微观两方面的应用，提高企业管理水平，实现最佳经济效益。 2.线性规划在企业生产计划中的应用 15 在企业生产过程中，生产计划安排直接影响到企业的经济效益，而解 决生产计划问题的有效方法之一就是建立线性规划模型，线性规划为企业制定生产计划提供了一种简单又科学的方法，具有一定的实用价值。 3.线性规划在服装生产任务分配中的应用 16 针对不确定条件下实际的服装生产任务分配问题，采用线性规划优化的方法予以解决。为此，建立了服装生产任务分配的数学模型，在保证交货期的前提下，将线性规划法对生产任务进行优化分配，使加工成本最小。生产实例表明，所提出的优化方法能够使服装生产系统得到整体优化，表明其 有效性和可行性。