运筹学名词辞条(供参考)

《运筹学名词辞条(供参考)》由会员分享，可在线阅读，更多相关《运筹学名词辞条(供参考)（11页珍藏版）》请在金锄头文库上搜索。

1、北京化工大学经济管理学院运筹学学习资料1运筹学名词辞条运筹学名词辞条( (供参考供参考) )名词及其名词及其 英文名称英文名称内内 容容提出者提出者运筹学 Operations research （注：在美国称 Operations research; 在英国称 Operational research。 英文缩写：OR） 运筹学涉及的主要领域是管理问题。研究的基本方 法是建立数学模型，较多的运用各种数学工具来解 决问题。运筹学目前尚无统一定义。通常有：“用 数学的方法研究经济、民政和国防等部门在内外环 境的约束条件下合理调配人力、物力、财力等资源， 使实际系统有效运行的技术科学。它可以用来预

2、测 发展趋势、制定行动规划或优选可方案。”1 “运用 分析、实验、量化的方法，对经济管理系统中的人、 财、物等有限资源进行统筹安排，为决策者提供依 据的最优方案，以实现最有效的管理。”2 A.P.Rowe (1938 年 7 月， 当时英国 Bawdsey 雷 达站负责人 P.Rowe 提出 为了有效防 止德国的空 袭，不能仅 依靠增加雷 达数量及改 进性能，还 应对整个作 战防空系统， 各雷达站间 的协调配合、 以及各雷达 站之间的相 互协调配合 及整个系统 运行进行综 合研究，才 能有效防备 德国人的飞 机侵入。 线性规划 Linear programming 英文缩写 LP 线性规划是指

3、研究线性约束条件下线性目标函数的 极值问题的数学理论与方法。即对于统筹规划问题， 为如何合理地、有效地利用现有有限的人力、物力、 财力资源来完成更多的任务。或者如何才能以最少 的代价去实现目标。作出的最优决策，提供科学的 依据。采用数学语言来描述：问题的目标用变量函 数的形式来表达（称为目标函数），问题的限制条 件用有关变量的等式或不等式来表达。（称为约束 条件）当变量连续取值，且目标函数与约束条件均 线性时，称这类模型为线性规划模型。有关线性规 划问题的建模、求解和应用研究构成了运筹学中一 个重要的、应用最为广泛的分支。其典型问题有： 运输问题、生产计划问题、混合配料问题等。 D.B.Dan

4、zig 1947 年 D.B.Danzig 在研究美国 的空军资源 优化配置时 提出了线性 规划的一般 数学模型。 北京化工大学经济管理学院运筹学学习资料2数学模型 Mathematical models数学模型是研究和掌握系统运动规律的有力工具， 它是分析、设计、预报或预测、控制实际系统的基 础。数学模型的种类很多，而且有各种不同的分类 方法。要对实际规划问题做定量分析，必须先加以 抽象，建立数学模型。它是用字母、数字和其他数 学符号构成的等式或不等式，或用图表、图象、框 图、数理逻辑等来描述系统的特征及其内部内部或 与外部联系的模型。它是正式系统的一种抽象。 单纯形法 Simplex me

5、thod单纯形法是求解线性规划问题的一种常用基本方法。 其思路是：根据问题的标准型，从可行域中一个基 本可行解（一个顶点）开始，转换到另一个基本可 行解（一个顶点），并且使目标函数值增大，当目 标函数值达到最大时，问题就得到了最优解。单纯 形法的特点是：（1）二元情况下满足约束条件的 集合是凸多边型，在多元情况下，满足约束条件的 集合是凸多面体(单纯形)。（2）目标函数的最大 值或最小值恰好在多边型的顶点，在多元情况下， 目标函数值一定在凸集的极点上。（3）各极点的 值代入目标函数中，进行比较就可以求得极值，即 所求得的解。 G.B.Danzig 1947 年美国 数学家 G.B.Danzig

6、 在研究美国 的空军资源 优化配置时 提出的求解 线性规划的 通用解法。 目标函数 Objective运用单纯形法解某些线性规划问题时，在一定约束 条件下要达到的目标，用数学模型表示，就称为目 标函数。 约束条件 Constraints运用单纯形法解某些线性规划问题时，该问题已知 并须遵守的前提条件称为约束条件。 可行解 feasible solutions, Alternative 一个线性规划问题有解，就能找出一组 xj（j =1.，n），满足约束条件，称这组 xj为问题的 可行解。通常线性规划问题总是含有多个可行解。 可行域 Feasible region(domain)全部可行解的集合

7、叫可行域。 线性规划图解法 Graphical solution of linear programming图解法是线性规划问题的基本解法.图解法一般只 适用于解 23 个变量的问题,解题的实用价值虽然 不大,但它阐明了线性规划解题的基本原理. 对偶理论 Duality theory每一个线性规划问题都存在一个与其对偶的问题， 在求出一个问题解的同时，也给出了另一个问题的 解。 1947 年美籍 匈牙利数学 家冯偌依曼 影子价格 Shadow price在线性规划问题中约束条件常数项增加一个单位而 产生的目标函数最优值的变化。如果约束条件常数 项表示资源，目标函数最优值表示最优收益，则影 子价

8、格是指资源增加对最优收益发生的影响，所以 又称资源的边际产出或资源的机会成本。它表示资 源在最优产品组合时所能具有的潜在价值。 北京化工大学经济管理学院运筹学学习资料3运输问题 Transportation problem一类具有特殊结构的线性规划问题。其典型问题是： 为了把某种产品从若干个产地调运到若干个销地， 已知每个产地的供应量和每个销地的需求量，如何 在许多可行的调运方案中，确定一个总运输费或总 运输量最小的方案。现已发现的问题有以下 6 类； 1、一般运输问题，又称希契科克运输问题。简称 H 问题 2、网络运输问题。简称 T 问题。3、最大 流量问题，简称 F 问题。4、最短路径问题

9、。简称 S 问题。5、任务分配问题，又称指派问题，简称 A 问题。6、生产计划问题，又称日程计划问题， 简称 CPS 问题。 目标规划 Goal programming这是线性规划的一种特殊应用，能够处理单个主目 标与多个目标并存，以及多个主目标与多个次目标 并存的问题。企业管理中经常碰到多目标决策的问 题。企业拟订生产计划时，不仅要考虑总产值，而 且要考虑利润、产品质量和设备利用率等。有些目 标之间往往互相矛盾。例如，企业利润可能同环境 保护的目标相矛盾。如何统筹兼顾多种目标，选择 合理的方案，是十分复杂的问题。应用目标规划可 能较好的解决这类问题。目标规划的应用范围很广， 包括生产计划、投

10、资计划、市场战略、人事管理、 环境保护、土地利用等。目标规划的模型分为以下 两大类：1.多目标并列模型。2.优先顺序模型。美国学者查 纳斯 （A.Charnes ）和库伯 （W.W.Coop er）在 1961 年首次提出。表上作业法 Tabular method用列表的方法求解线性规划问题中运输模型的计算 方法。当某些线性规划问题采用图上作业法难以进 行直观求解时，就可以将各元素列成相关表，给出 初始方案，然后采用检验数来判断这个方案，否则 就要采用闭回路法等方法进行调整，直至得到满意 的结果。这种列表求解方法就是表上作业法。 图上作业法 Graphical method在运输图上求解线性规

11、划运输模型的方法。交通运 输以及类似的线性规划问题，都可以首先画出流向 图，然后根据有关规则进行必要调整，直至求出最 小运输费用或最大运输效率的解。这种求解方法， 就是图上作业法。图上作业法的内外圈流向箭头， 要求达到重叠且各自之和都小于或等于全圈总程度 的一半，这时的流向图就是最佳调运方案。 灵敏度分析 Sensitivity analysis是指对于系统或事物因周围条件变化显示出来的敏 感程度的分析。即研究当线性规划问题的参数中的 一个或者几个参数发生变化时，问题的最优解会有 什么变化，或者这些参数在一个多大的范围内变动 时，问题的最优解不变。 1736 年瑞士 数学家 L.欧 拉。 西北

12、角法 是指用表上作图法解线性规划运输问题时，建立调 运初始方案的一种方法。由于这种方法是从表的左 上角（西北角）方格开始的，不考虑运费（运输成 本）的因素，根据表内供应量与需求量的要求，进北京化工大学经济管理学院运筹学学习资料4行分配，逐行逐列的予以满足，以达到供销调配平 衡。因此称、为西北角法。 最小元素法 The least cost rule指用表上作业法解线性规划运输问题时,建立调运 处始方案的一种方法.最小元素法改进了西北角法 存在的问题,在分配时考虑到运输成本问题,在保证 供销平衡的前提下,尽可能满足运费最小或较小的 格子,满足一行(或列),就划去一行(或列)。如果运费 相同时可任

13、选其中一个.用最小元素法与西北角法 比较,可使运费显著减少,可以得到交好的初始调运 方案。运输论法 它主要研究从一些货源地到另一些目的地的最优运 输方法的问题。经过适当修改后，并可用来解决一 些与运输毫无关系的问题，如向机器分派任务的问 题等。建立运输问题公式的要求同线性规划是一样 的，包括：正确定义的线性目标函数；可选择的行 动方案；线性目标函数和线性约束条件的数学表达； 相关的变量，资源在有限的范围内供给。运输问题 公式就是在这样的条件下，用迭代求解过程（运输 方法）来分配有限资源的。 闭回路调整法 Close circularadjust method 用表上作业法解线性规划运输问题中,

14、采用一定的 方法建立调运初始方案后,对方案进行检验和调整 的一种方法. 非线性规划 Nonlinear programming具有非线性约束条件或目标函数的数学模型。是运 筹学一个重要分支。非线性规划研究一个 n 元实函 数在一组等式或不等式的约束条件下的极值问题。 且目标函数和约束条件至少有一个是未知量的非线 性函数。大多数工程物理量的表达式都是非线性的， 所以，非线性规划在各类工程优化设计中得到了较 多的应用。1951 年 H.W. 库恩和 A.W. 塔克 斐波那契法 Fibonacci search使用对称搜索的方法，逐步缩短所考察的区间，他 能以尽量少的函数求值次数，达到预定某一缩短率

15、。0.618 法 （黄金分割法） Golden section search以不变的区间缩短率 0.618 代替斐波那契法每次不 同的缩短率，可看成斐波那契法近似。 欧拉回路 Euler loop连通图 G 中，若存在一条回路，经过每边一次且 仅一次，则这条回路为欧拉回路。 整数规划 Integer programming要求一部分或全部决策变量必须取整数数的规划问 题。若所有变量均要求取整数值，则称为纯整数规 划。若只有部分变量要求取整数值，则称为混合整 数规划。整数规划一词常指纯整数规划。要求变量 取整数的线性规划称为整数线性规划。 松弛问题 Slack problem不考虑整数条件，由余

16、下的目标函数值和约束条件 构成的规划问题称为该整数规划的松弛问题。 北京化工大学经济管理学院运筹学学习资料5割平面法 Cutting plane algorithm解整数线性规划的一种方法。是从松弛问题的一个 非整数的最优解出发，序贯地每次添加一个新的线 性不等式（其对应线性方程所代表的超平面即称为 割平面），求解新的松弛问题。每次增添的新的不 等式要满足两个条件：（1）前一个不等式的最优 解不满足这个不等式。即松弛问题的可行解集合被 割去了一块。（2）S 中的点都满足这个不等式， 即保证整数可行解不被割去。 1963 年 R.E. 戈莫里 分枝限界法 Branch and bound method一种解离散问题的最优化方法，可以解线性整数规 划。分枝限界法的基本思想是部分枚举法。 1965 年 R.J 达金和兰德- 多伊格 整数线性规划 Integer linear programming (ILP)若松弛问题是一个线性规划，则称该整数规划为整 数线性规划。 纯整数线性规划 Pure Inte