规划的综合方法

规划的综合方法 一、线性规划法 线性规划（Linear programming,简称 LP）是运筹学中研究较早、 发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进 行科学管理的一种数学方法。 研究线性约束条件下线性目标函数的极 值问题的数学理论和方法。英文缩写 LP。它是运筹学的一个重要分 支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。 为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供 科学的依据。 线性规划方法是在第二次世界大战中发展起来的一种重要的数 量方法，线性规划方法是企业进行总产量计划时常用的一种定量方 法。线性规划是运筹学的一个最重要的分支，理论上最完善，实际应 用得最广泛。主要用于研究有限资源的最佳分配问题， 即如何对有限 的资源作出最佳方式地调配和最有利地使用， 以便最充分地发挥资源 的效能去获取最佳的经济效益。由于有成熟的计算机应用软件的支 持，采用线性规划模型安排生产计划，并不是一件困难的事情。在总 体计划中，用线性规划模型解决问题的思路是， 在有限的生产资源和 市场需求条件约束下，求利润最大的总产量计划。该方法的最大优点 是可以处理多品种问题。 数学模型： 1）列出约束条件及目标函数 2）画出约束条件所表示的可行域 3）在可行域内求目标函数的最优解及最优值 从实际问题中建立数学模型一般有以下三个步骤； 1.根据影响所要达到目的的因素找到决策变量； 2.由决策变量和所在达到目的之间的函数关系确定目标函数； 3.由决策变量所受的限制条件确定决策变量所要满足的约束条件。 所建立的数学模型具有以下特点： 1、每个模型都有若干个决策变量（x1，x2，x3……，xn），其中 n 为决策变量个数。决策变量的一组值表示一种方案， 同时决策变量一 般是非负的。 2、目标函数是决策变量的线性函数，根据具体问题可以是最大化 （max）或最小化（min），二者统称为最优化（opt）。 3、约束条件也是决策变量的线性函数。 当我们得到的数学模型的目标函数为线性函数， 约束条件为线性等式 或不等式时称此数学模型为线性规划模型。 发展： 法国数学家 J.- B.- J.傅里叶和 C.瓦莱－普森分别于 1832 和 1911 年独 立地提出线性规划的想法，但未引起注意。 1939 年苏联数学家 Л.В.康托罗维奇在《生产组织与计划中的数学方 法》一书中提出线性规划问题，也未引起重视。 1947 年美国数学家 G.B.Dantzing 提出求解线性规划的单纯形法，为 这门学科奠定了基础。 1947 年美国数学家 J.von 诺伊曼提出对偶理论,开创了线性规划的许 多新的研究领域，扩大了它的应用范围和解题能力。 1951 年美国经济学家 T.C.库普曼斯把线性规划应用到经济领域，为 此与康托罗维奇一起获 1975 年诺贝尔经济学奖。 50 年代后对线性规划进行大量的理论研究，并涌现出一大批新的算 法。例如，1954 年 C.莱姆基提出对偶单纯形法，1954 年 S.加斯和 T. 萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956 年 A. 塔克提出互补松弛定理，1960 年 G.B.丹齐克和 P.沃尔夫提出分解算 法等。 线性规划的研究成果还直接推动了其他数学规划问题包括整数 规划、随机规划和非线性规划的算法研究。 由于数字电子计算机的发 展，出现了许多线性规划软件，如 MPSX，OPHEIE，UMPIRE 等， 可以很方便地求解几千个变量的线性规划问题。 1979 年苏联数学家 L. G. Khachian 提出解线性规划问题的椭球算法， 并证明它是多项式时间算法。 1984 年美国贝尔电话实验室的印度数学家 N.卡马卡提出解线性规划 问题的新的多项式时间算法。 用这种方法求解线性规划问题在变量个 数为 5000 时只要单纯形法所用时间的 1/50。现已形成线性规划多项 式算法理论。50 年代后线性规划的应用范围不断扩大。 实际运用线性规划模型进行总生产计划时需要注意的一些问题 1、线性规划模型考虑的因素可能不全面，实际中有些情况没有被考 虑到，这就使得线性规划模型过于理想化； 2、实际运用线性规划模型时， 虽然一些因素或约束条件被考虑到了， 但是由于这些因素或约束条件不易量化或求得 （如进行总生产计划常 需考虑到的能源单耗就不易求得） 时，线性规划模型的运用和有效性 因而受到了一定的限制； 3、对一些基础管理不善的企业而言，模型中的单位产品资源消耗系 数 a 很难得到； 4、目标函数中的产为成本系数 c 实际上是个变量，他随计划的数量 结构和品种结构而变。 这些问题给机械行业应用线性规划模型带来许 多困难，如处理不好，求得的结果的可靠性会很低的。 二、多目标决策法 多目标决策是对多个相互矛盾的目标进行科学、 合理的选优，然 后作出决策的理论和方法。它是 20 世纪 70 年代后迅速发展起来的 管理科学的一个新的分支。 多目标决策与只为了达到一个目标而从许 多可行方案中选出最佳方案的一般决策有所不同。在多目标决策中， 要同时考虑多种目标，而这些目标往往是难以比较的， 甚至是彼此矛 盾的； 一般很难使每个目标都达到最优， 作出各方面都很满意的决策。 因此多目标决策实质上是在各种目标之间和各种限制之间求得一种 合理的妥协，这就是多目标最优化的过程。 国外一般认为，多目标优化问题最早是在 19 世纪末由意大利经 济学家帕累托（V.Pareto）从政治经济学的角度提出来的，他把许多 本质上不可比较的目标，设法变换成一个单一的最优目标来进行求 解。到了 20 世纪 40 年代，冯诺曼等人由从对策论的角度提出在彼此 有矛盾的多个决策人之间如何进行多目标决策问题。1950 年代初， 考普曼（T.C.koopmans）从生产和分配的活动分析中提出多目标最优 化问题，并引入了帕累托最优的概念。1960 年代初，菜恩思 （F.Charnes）和考柏（J.Cooper）提出了目标规划方法来解决多目标 决策问题。目标规划是线性规划的修正和发展， 这一方法不只是对一 些目标求得最优， 而是尽量使求得的最优解与原定的目标值之间的偏 差为最小。1970 年代中期，甘尼（ R.L.Keeney）和拉发用比较完整的 描述多属性效用理论来求解多目标决策问题。1970 年代末，萨蒂 （A.L.Saaty）提出了影响广泛的 AHP(the analytical hierarchy process) 法，并在 1980 年代初纂写了有关 AHP 法的专著。自 1970 年代以来， 有关研究和讨论多目标决策的方法也随之出现。 总之，多目标决策问题正愈来愈多的受到人们的重视， 尤其是在 经济、管理、系统工程、控制论和运筹学等领域中得到了更多的研究 和关注。 多目标决策法的基本原理 从人们在多目标条件下合理进行决策的过程和机制从上分析， 多 目标决策的理论主要有：多目标决策过程的分析和描述； 冲突性的分 解和理想点转移的理论；多属性效用理论；需求的多重性和层次性理 论等。它们是构成多目标决策分析方法的理论基础。 在多目标决策中，有一部分方案经比较后可以淘汰，称为劣解； 但还有一批方案既不能淘汰， 又不