运筹学名词辞条

1、运筹学名词辞条（供参考）名词及其 英文名称内容提出者运筹学运筹学涉及的主要领域是管理问题。研究的基本方A.P.Rowe(1938 年 7 月，Operations research法是建立数学模型，较多的运用各种数学工具来解（注：在美国称决问题。运筹学目前尚无统一定义。通常有：“用数当时英国Operations学的方法研究经济、民政和国防等部门在内外环境Bawdsey 雷达research;的约束条件下合理调配人力、物力、财力等资源，站负责人在英国称使实际系统有效运行的技术科学。它可以用来预测P.Rowe提出Operational发展趋势、制定行动规划或优选可方案。”1 “运用为了有效防res

2、earch o分析、实验、量化的方法，对经济管理系统中的人、止德国的空英文缩写：OR）财、物等有限资源进行统筹安排，为决策者提供依袭，不能仅依据的最优方案，以实现最有效的管理。”靠增加雷达数量及改进 性能，还应对 整个作战防 空系统，各雷达站间的协 调配合、以及 各雷达站之 间的相互协调配合及整 个系统运行 进行综合研 究，才能有效防备德国人 的飞机侵入。线性规划线性规划是指研究线性约束条件下线性目标函数的D.B.DanzigLinear programming极值问题的数学理论与方法。即对于统筹规划问题，英文缩写LP为如何合理地、有效地利用现有有限的人力、物力、1947 年财力资源来完成更多

3、的任务。或者如何才能以最少D.B.Danzig的代价去实现目标。作出的最优决策，提供科学的在研究美国依据。米用数学语言来描述：问题的目标用变量函的空军资源数的形式来表达（称为目标函数），问题的限制条优化配置时件用有关变量的等式或不等式来表达。（称为约束提出了线性条件）当变量连续取值，且目标函数与约束条件均规划的一般线性时，称这类模型为线性规划模型。有关线性规 划问题的建模、求解和应用研究构成了运筹学中一 个重要的、应用最为广泛的分支。其典型问题有： 运输问题、生产计划问题、混合配料问题等。数学模型。数学模型Mathematical models数学模型是研究和掌握系统运动规律的有力工具， 它是

4、分析、设计、预报或预测、控制实际系统的基 础。数学模型的种类很多，而且有各种不同的分类 方法。要对实际规划问题做定量分析，必须先加以 抽象，建立数学模型。它是用字母、数字和其他数 学符号构成的等式或不等式，或用图表、图象、框 图、数理逻辑等来描述系统的特征及其内部内部或 与外部联系的模型。它是正式系统的一种抽象。单纯形法Simplex method单纯形法是求解线性规划问题的一种常用基本方 法。其思路是：根据问题的标准型，从可行域中一 个基本可行解（一个顶点）开始，转换到另一个基 本可行解（一个顶点），并且使目标函数值增大， 当目标函数值达到最大时，问题就得到了最优解。单纯形法的特点是：（1）

5、二元情况下满足约束条件 的集合是凸多边型，在多元情况下，满足约束条件 的集合是凸多面体（单纯形）。（2）目标函数的最大 值或最小值恰好在多边型的顶点，在多元情况下， 目标函数值一定在凸集的极点上。（3）各极点的值 代入目标函数中，进行比较就可以求得极值，即所 求得的解。G.B.Danzig1947年美国 数学家G.B.Danzig 在研究美国 的空军资源 优化配置时 提出的求解 线性规划的 通用解法。目标函数Objective运用单纯形法解某些线性规划问题时，在一定约束 条件下要达到的目标，用数学模型表示，就称为目 标函数。约束条件Constraints运用单纯形法解某些线性规划问题时，该问题

6、已知 并须遵守的前提条件称为约束条件。可行解feasible solutions,Alternative一个线性规划问题有解，就能找出一组x.（j =1.， 一，、 .一 _n），满足约束条件，称这组x.为问题的可行解。通 常线性规划问题总是含有多个可行解。可行域 Feasible region(domain)全部可行解的集合叫可行域。线性规划图解法Graphical solution of linear programming图解法是线性规划问题的基本解法.图解法一般只 适用于解23个变量的问题，解题的实用价值虽然不 大，但它阐明了线性规划解题的基本原理.对偶理论 Duality theor

7、y每一个线性规划问题都存在一个与其对偶的问题， 在求出一个问题解的同时，也给出了另一个问题的 解。1947年美籍匈牙利数学家冯偌依曼影子价格Shadow price在线性规划问题中约束条件常数项增加一个单位而 产生的目标函数最优值的变化。如果约束条件常数 项表示资源，目标函数最优值表示最优收益，则影 子价格是指资源增加对最优收益发生的影响，所以 又称资源的边际产出或资源的机会成本。它表示资 源在最优产品组合时所能具有的潜在价值。运输问题Transportation problem一类具有特殊结构的线性规划问题。其典型问题是： 为了把某种产品从若干个产地调运到若干个销地， 已知每个产地的供应量和

8、每个销地的需求量，如何 在许多可行的调运方案中，确定一个总运输费或总 运输量最小的方案。现已发现的问题有以下6类；1、 一般运输问题，又称希契科克运输问题。简称H问 题2、网络运输问题。简称T问题。3、最大流量问 题，简称F问题。4、最短路径问题。简称S问题。 5、任务分配问题，又称指派问题，简称A问题。6、 生产计划问题，又称日程计划问题，简称CPS问题。目标规划Goal programming这是线性规划的一种特殊应用，能够处理单个主目 标与多个目标并存，以及多个主目标与多个次目标 并存的问题。企业管理中经常碰到多目标决策的问 题。企业拟订生产计划时，不仅要考虑总产值，而 且要考虑利润、产

9、品质量和设备利用率等。有些目 标之间往往互相矛盾。例如，企业利润可能同环境 保护的目标相矛盾。如何统筹兼顾多种目标，选择 合理的方案，是十分复杂的问题。应用目标规划可 能较好的解决这类问题。目标规划的应用范围很广， 包括生产计划、投资计划、市场战略、人事管理、 环境保护、土地利用等。目标规划的模型分为以下 两大类：1.多目标并列模型。2.优先顺序模型。美国学者查 纳斯(A.Charnes) 和库伯(W.W.Coop er)在 1961 年首次提出。表上作业法Tabular method用列表的方法求解线性规划问题中运输模型的计算 方法。当某些线性规划问题采用图上作业法难以进 行直观求解时，就可

10、以将各元素列成相关表，给出 初始方案，然后采用检验数来判断这个方案，否则 就要采用闭回路法等方法进行调整，直至得到满意 的结果。这种列表求解方法就是表上作业法。图上作业法Graphical method在运输图上求解线性规划运输模型的方法。交通运 输以及类似的线性规划问题，都可以首先画出流向 图，然后根据有关规则进行必要调整，直至求出最 小运输费用或最大运输效率的解。这种求解方法， 就是图上作业法。图上作业法的内外圈流向箭头， 要求达到重叠且各自之和都小于或等于全圈总程度 的一半，这时的流向图就是最佳调运方案。灵敏度分析Sensitivity analysis是指对于系统或事物因周围条件变化显

11、示出来的敏 感程度的分析。即研究当线性规划问题的参数中的 一个或者几个参数发生变化时，问题的最优解会有 什么变化，或者这些参数在一个多大的范围内变动 时，问题的最优解不变。1736年瑞士 数学家L.欧 拉。西北角法是指用表上作图法解线性规划运输问题时，建立调 运初始方案的一种方法。由于这种方法是从表的左 上角(西北角)方格开始的，不考虑运费(运输成 本)的因素，根据表内供应量与需求量的要求，进 行分配，逐行逐列的予以满足，以达到供销调配平 衡。因此称、为西北角法。取小元素法The least cost rule指用表上作业法解线性规划运输问题时，建立调运 处始方案的一种方法.最小元素法改进了西

12、北角法 存在的问题，在分配时考虑到运输成本问题,在保证 供销平衡的前提下,尽可能满足运费最小或较小的 格子，满足一行（或列），就划去一行（或列）。如果运费 相同时可任选其中一个用最小元素法与西北角法 比较，可使运费显著减少，可以得到交好的初始调运 方案。运输论法它主要研究从一些货源地到另一些目的地的最优运 输方法的问题。经过适当修改后，并可用来解决一 些与运输毫无关系的问题，如向机器分派任务的问 题等。建立运输问题公式的要求同线性规划是一样 的，包括：正确定义的线性目标函数；可选择的行 动方案；线性目标函数和线性约束条件的数学表达； 相关的变量，资源在有限的范围内供给。运输问题 公式就是在这样

13、的条件下，用迭代求解过程（运输 方法）来分配有限资源的。闭回路调整法Close circularadjust method用表上作业法解线性规划运输问题中，米用一定的 方法建立调运初始方案后，对方案进行检验和调整 的一种方法.非线性规划Nonlinear programming具有非线性约束条件或目标函数的数学模型。是运 筹学一个重要分支。非线性规划研究一个n元实函 数在一组等式或不等式的约束条件下的极值问题。 且目标函数和约束条件至少有一个是未知量的非线 性函数。大多数工程物理量的表达式都是非线性的， 所以，非线性规划在各类工程优化设计中得到了较 多的应用。1951 年 H.W.库恩和A.W

14、.塔克斐波那契法Fibonacci search使用对称搜索的方法，逐步缩短所考察的区间，他 能以尽量少的函数求值次数，达到预定某一缩短率。0.618 法（黄金分割法）Golden section search以不变的区间缩短率0.618代替斐波那契法每次不 同的缩短率，可看成斐波那契法近似。欧拉回路Euler loop连通图G中，若存在一条回路，经过每边一次且仅 一次，则这条回路为欧拉回路。整数规划Integer programming要求一部分或全部决策变量必须取整数数的规划问 题。若所有变量均要求取整数值，则称为纯整数规 划。若只有部分变量要求取整数值，则称为混合整 数规划。整数规划一词

15、常指纯整数规划。要求变量 取整数的线性规划称为整数线性规划。松弛问题Slack problem不考虑整数条件，由余下的目标函数值和约束条件 构成的规划问题称为该整数规划的松弛问题。割平面法Cuttingplanealgorithm解整数线性规划的一种方法。是从松弛问题的一个 非整数的最优解出发，序贯地每次添加一个新的线 性不等式（其对应线性方程所代表的超平面即称为 割平面），求解新的松弛问题。每次增添的新的不 等式要满足两个条件：（1）前一个不等式的最优解 不满足这个不等式。即松弛问题的可行解集合被割 去了一块。（2）S中的点都满足这个不等式，即 保证整数可行解不被割去。1963 年 R.E.

16、戈莫里分枝限界法Branch and bound method一种解离散问题的最优化方法，可以解线性整数规 划。分枝限界法的基本思想是部分枚举法。1965 年 R.J 达金和兰德-多 伊格整数线性规划Integer linear programming (ILP)若松弛问题是一个线性规划，则称该整数规划为整 数线性规划。纯整数线性规划Pure Integer linear programming指全部决策变量必须取整数值的整数线性规划。混合整数线性规划Mixed ILP指决策变量中有一部分必须取整数值，另一部分可 以不取整数值的整数线性规划。0-1型整数线性规划Zero-one ILP指决策变

17、量中只能取值0或1的整数规划。马氏决策规划Markov decision programming在赋值马氏过程中，如果在某状态选用不同的决策 能够改变相应的状态转移矩阵及报酬矩阵，就产生 了动态随机系统求最优策略的问题。马氏决策规划 就是研究这类问题的。最小树问题Minimum tree problem连通且不含圈的无向图称为树，如城市煤气、自来水 管道网络，铁路的专用线网等，都可以用树的形式 来表示。同一网络中可以构成许多个部分的树。如 果在网络中每条边上赋予相应的权（权可以表示距 离、时间、费用等），最小树问题就是在所有部分 树中寻找一个总权数为最小的问题。最短路问题Shortest-ro

18、ute problems一般提法：设G=（V，E）为连通图，图中各边（vi， v.）有权l.（l.=无穷大表示v.，v.间无边），v，vj_jji js t为图中任意两点，求一条道路u，使它是从vs到vt 的所有路中总权最小的路。SDijkstra 算法Dijkstra algorithm用于求解指定两点，vt间的最短路，或从指定点vs 到其余各点的最短路，是求无负权网络最短路问题 的最好方法。1959 年 DijkstraFloyd算法Floyd algorithm直接求出网络中任意两点间的最短路。1962 年 Floyd最大流问题Maximal-Flow problems管道网络中每边的最

19、大通过能力即容量是有限的， 实际流量也并不一定等于容量，上述问题就是要讨 论如何充分利用装置能力，以取得最好效果（流量 最大）。图与网络分析Graph theory and network analysis运筹学中把一些研究对象用节点表示，对象之间的 关系用连线边表示。用点、边的的集合构成图。图 论是研究有节点和边所组成图形的数学理论和方 法。图是网络分析的基础，根据具体研究的网络对 象（如：铁路网、电力网、通信网等），赋予图中 各边某个具体的参数，如时间、流量、费用、距离 等，规定图中各节点代表具体网络中任何一种流动 的起点，中转点或终点，然后利用图论方法来研究 各类网络结构和流量的优化分析

20、。网络分析还包括 利用网络图形来描述一响工程中各项作业的进度和 结构关系，以便对工程进度进行油画控制。网络计划Network planning50年代以来，国外陆续出现了一些计划管理的新方 法，如关键路线法，计划评审法等，这些方法都是 建立在网络模型基础上，成为网络计划技术。网络Network在图论中，现给定一个有向图D=（V，A），在V 中指定了一点，称为发点，和另一点，称为收点， 其余的点称为中间点。对于每一个弧，都对应一个 弧的容量，这样的D称为网络。网络方法和网络计 划Network method and network planning绘制网络图的规则及计算相关参数的方法称为网络 方

21、法。把以网络图表示的，用网络方法编制的计划 称为网络计划。网络分析Network analysis把一项工程系统或组织计划问题用网络的形式来描 述，通过分析和计算,使其最优化。网络理论Network theory1845 年 G.R.基尔霍夫。网络技术Netwok techniques利用网络图形描述一项工程或计划进度各个环节和 要素之间的关系，以便寻求系统最优解或最优控制 的技术，又称网络分析。1845 年 G.R.基尔霍夫.关键线路法Critical path method 简称CPM借助网络表示各项工作及所需时间，表示出各项工 作间的相互关系，找出编制与执行计划的关键路线， 这种方法称为

22、关键路线法。1956年美国杜邦公司在 制定协调企 业不同业务 部门的系统 规划技术计划评审法Program evaluation and review technique 简称PERT应用网络方法和网络形式，注重于对各项任务安排 的评价和审查，这种方法称为计划评审法。1958年美国海军武器局 在制定研制 “北极星”导 弹计划。网络图Network graphic是指由工序，事项及标有完成各项工序所需时间等 参数所构成的有向图。1958年美国海军武器局 在制定研制 “北极星”导 弹计划。多重图和简单图Multiple graph and simple graph若两个点之间多余一条边，称之为多重

23、边，含多重 边的图称为多重图。无环，无多重边的图称为简单 图。连通图一个图中，若任何两点之间，至少有一条链，则称 这个图为连通图。无向图在图论中，由点V及边E组成的，没有标明某点到 另一点的方向，即匕，*和*, VJ是相同的。这种 图称为无向图。有向图Directed graph在图论中，点与点之间有方向的线称为弧。由点集 V和弧集A组成的图D=（V，A）称为有向图。最短路径问题Shortest path problem在网络图上，对每条边有一个权，要求从始点到终点 的所有路径中找出一条总权数为最小的路径.动态规划Dynamic programming 缩写DP研究多阶段（多步）决策过程最优化

24、问题的一种数 学方法，是最优控制和运筹学的重要数学工具。为 了寻找系统最优决策，可将系统运行过程划分为若 干相继的阶段（或若干步），并在每个阶段（或每 一步）都作出决策。这种决策过程就称为多阶段（多 步）决策过程。多阶段决策过程的每一阶段的输出 状态就是下一阶段的输出状态。某一阶段作出的最 优决策，对于下一阶段未必是最有利的。多阶段决 策的最优化问题必须从系统整体出发，要求各阶段 选定的决策系列所构成的系列最终能使目标函数达 到极值。50年代初，美 国数学家R.贝尔曼。决策Decision指按一定的标准和要求，确定一个奋斗的目标，并 从两个以上的为达到目标的实施方案中，选定一个 合适方案的科学

25、的过程。决策论Decision theory根据系统的状态信息和评价准则选取最优策略的数 学理论。决策论是运筹学的一个分支和决策分析的 理论基础。它是关于不确定性决策问题的合理性分 析过程及有关概念的理论。现代决策理论Modern decision theory是“传统决策理论”的对称。这种理论的核心是用“令 人满意的准则”代替了古典最大化原则。美国卡内基 梅隆大学 教授赫伯特. 西蒙古典决策理论Classical decision theory也称“传统决策理论”。它的出发点是把人视为绝对 理性的人，他在决策时遵循的是最大化原则。战略决策Strategy decision按决策对象和层次划分

26、的一种决策。战略决策是企 业与经常变化中的外部环境之间，谋求达到动态平 衡，协调发展的一种决策。风险型决策Risk decision也称“统计型决策”，它是从同时具备下列五个条件 的问题中选定最优方案的决策。（1）有一个明确的 目标；（2）有两个以上可供选择的行动方案；（3） 存在两种以上不以主观意志为转移的客观状态;（4） 不同行动方案在不同状态下的损失和利益可计算；（5）自然状态出现的概率可估计。益损矩阵Opportunity loss matrix由益损值构成的矩阵，就叫决策的益损矩阵或风险 矩阵。最大可能法Maximum permissible method选择一个概率最大的自然状态进

27、行决策，其它自然 状态可以不管，这样的方法就是最大可能法。期望值法Expected value method把每个行动的期望值求出来，并加以比较的方法就 称为期望值法。决策树法Decision trees method风险型决策问题的一种基本决策方法。由于这种决 策方法的思路如同树枝形状，因此称为决策树法。局中人Player“对策问题”的基本要素之一。是指在一局对策中具 有决策权当事人。策略Policy对策问题的基本要素之一。是指局中人的可行的通 盘筹划行动方案。马氏决策规划Markovdecisionprogramming 英文缩写：MDP是序贯决策的主要研究领域。它是Markov过程与 确

28、定性动态规划相结合的产物，故又称Markov型 随机动态规划，属于运筹学中数学规划的一个分支。 在赋值马氏过程中，如果在某状态选用不同的决策 能够改变相应的状态转移矩阵及报酬矩阵，就产生 了动态随机系统求最优策略的问题。马氏决策规划 就是研究这类问题的。50年代贝尔 曼研究动态 规划和沙浦 利研究随机 对策时出现 Markov决策 基本思想。悲观准则（max-min 准则）Max-min criterion这种方法的基本思想是假定决策者从每一个决策方 案可能出现的最差结果出发，且最佳选择是从最不 利的结果中学则最有利的结果。乐观准则（max-max 准则）Max-max criterion这种

29、方法的出发点是假定决策者对未来的结果持乐 观的态度，总是假设出现对自己有利的状况。折衷准则Rlurwicz criterion折衷准则是介于悲观准则和乐观准则之间的一个准 贝h其特点是对客观状况的估计即不完全乐观，也 不完全悲观，而采用一个乐观系数来反映决策者对 状态估计的乐观程度。等可能准则（Laplace 准则） Laplace criterion这种准则的思想在于将各种可能出现的状态“一视 同仁”，即认为它们出现的可能性都是相等的。然后 再按照期望收益最大的原则选择最优方案。遗憾准则（min-max 准则）Regret criterion在决策过程中，当某一种状态可能出现时，决策者 必然

30、要选择使收益最大的方案。但如果决策者由于 决策失误而没有选择使收益最大的方案，则会感到 遗憾和后悔。遗憾准则的基本思想就是在于尽量减 少决策者的遗憾，使决策者不后悔或少后悔。对策论（博弈论）Game theory研究具有对抗局势的模型。是关于两个或多个局中 人按一定规则处于竞争状态下的决策行为数学理 论。对策论是运筹学一个分支。起源于对室内游戏 （如象棋、扑克等）局中人的行为和得失的研究， 后来发展成为研究带有竞争因素社会现象的一种数 学方法。1921年法国 数学家E.博 雷尔。合作对策Cooperative games对策论中部分局中人形成联盟的对策问题。它是现 代对策论中最活跃的研究课题之

31、一。非合作对策Noncooperative games对策论中局中人在选择各自策略时不结成任何联盟 的对策问题。纳什平衡Nash equilibrium非合作对策中所有对策人都根据各自的信息选择策 略，力图使自己的目标函数值达到最大的一种平衡 解。经济学家J.纳什。帕雷托最优Pareto optimality使用于多目标最优化的解。在多目标最优化问题中 需要同时使多个有矛盾的目标函数优化。诸目标函 数可代表不同的决策标准（例如：成本、环境质量、 风险等）或不同利益集团对同一决策标准所持的不 同观点。由于目标函数之间的矛盾性质，一般说来 使每个目标函数值同时达到各自最优值的解是不存 在的。多目标

32、最优问题的解为帕雷托最优解的条件 是解的任何一个目标函数值在不使其他目标函数值 恶化的条件下已经不可能进一步改进。1896年意大利经济学家V.F.帕雷托斯塔克尔贝格对策Stackelberg strategy对策论中的多级递阶决策问题。又称主从对策。社 会现象的结局通常使由许多决策人的行动共同决定 的。而这些决策人分居不同的层次，形成所谓多级 递阶决策系统。上层决策人具有一定权威，起着主 导作用，有时代表全局的利益。他们对整个系统的 控制可以通过操纵一些“杠杆”变量来影响下级的行 为而实现。例如：国家通过调节利率、税收、投资 等决策量来控制各部门、各单位的行为来实现全局 最优。经济学家H.vo

33、n斯塔克尔贝格。统筹法Overall planning method网络理论在计划与管理工作中的具体应用方法，主 要是指计划协调技术（PERT）和关键线路法（CPM） 中国数学家华罗庚在生产企业推广计划协调技术（PERT）和关键线路法（CPM）时采用“统筹法” 这个名词。统筹法主要用于计划管理和进度管理。指派问题Assignment problem在满足特定指派要求条件下，使指派方案总体效果 最佳。口：有若干项工作需要分配给若干人（或部 门）来完成；有若干项合同需要选择若干个投标者 来承包：有若干班级需要安排在若干教室里上课等 等。匈牙利解法Hungarian method解指派问题的一种算法。1955年，库恩 (w.w.Kuhn)存储论Inventory theory研究