常见运筹学概念和操作

1、管理科学（运筹学）是对于定量因素有关的管理问题通过应用科学的方法进行辅助管理决策 制定的一门学科。起初用于第二次世界大战，而推动其发展的重大因素之一是计算机革命的爆发。解决问题的一般步骤：1，定义问题和收集数据（考虑的问题和达成的目标）构建模型（数学模型）从模型中形成一个对问题进行求解的基于计算机的程序测试模型并在必要时进行修正应用模型分析问题以及提出管理意见帮助实施被管理者采纳的小组意见建立模型的重要因素：1，约束条件：数学模型中对决策变量可能取值进行限制的不等式或等式。2，参数：数学模型中的变量。3，目标函数：是数学模型中根据决策变量作出的绩效度量的数学表达式。关于敏感性分析：数学模型只是

2、问题的一个近似求解，因而敏感性分析是由于估计值发生偏差时，带来的 模型变化。数学模型编入电子表格，这种数学模型通常成为电子表格模型。线性规划【用线性数学模型表示的活动计划】的基本概念1，显示数据的单元格称为数据单元格。2，可变单元格包含要做的决策。3，输出单元格显示依赖于可变单元格的输出结果。4，目标单元格是一种特殊的可变单元格，其包含了对所有可变单元格所作出决策的评估 用电子表格为问题建立数学模型（线性规划模型）过程中要解决的三个问题：1，要做出的决策是什么？（表现的是什么）2，在作出这些决策上有哪些约束条件？（约束是什么）3，这些决策的全部绩效测度是什么？（达到的目的是什么）电子表格上的线

3、性规划模型的特征：1，需要作出许多活动水平的决策，因此可变单元格被用来显示这些水平。2，这些活动的水平能够取满足许多约束条件的任何值（包括小数值）3，每个约束条件对活动水平的决策可行值进行了限制，约束条件的左边往往是一个输出 单元格，中间是一个数学符号（=,=等），右边是数据单元格。4，活动水平的决策是以进入目标单元格的一个完全绩效测度为基础的，目标是最大化目 标单元格或是最小化目标单元格，这由绩效测度的性质决定。5，每个输出单元格（包括目标单元格）的excel等式可以表达一个SUMPRODUCT函数， 这里加和的每一项是一个数据单元格与一个可变单元格的乘积。特征2与5是区分线性规划模型和其他

4、可变电子表格上建模的数学模型的关键。约束边界线：即形成一个约束条件所允许的边界的直线，它通常是由它的方程式确定的，切 对于一含有不等号的约束条件，它的约束边界方程将不等号换成等号即可。约束边界线的位 置由它与两轴相交的交点确定。如3*x+4*y=10。只改变约束条件的右边会得到平行的约束 边界线，检验（0，0）是否满足约束条件可以表明位于约束边界线的哪一边满足约束条件。斜截式，斜率。可行域：可行域内的点是那些符合所有约束条件的解。目标函数线：是它上面点的都有相同目标函数值的一条直线。如何有效的建立一个电子表格模型：首先输入数据，先输入和仔细编排所有数据，然后尽量使模型的结构符合数据的编排。 可

5、以先建立一个小型表格。组织和清楚的标识数据，行列都有表示。每个数据输入唯一的一个单元格，为了方便更改数据。公式与数据分离。避免在公式中直接使用数字，这样可以是表格易于说明，切模型易 于修改。保持简单化。使用区域名称。但也不能滥用。（命名方法，注意事项：不允许使用空格，但可以用 下划线）使用相对与绝对坐标（它的使用方法$）使用边框，阴影和颜色来区分单元格类型在电子表格中显示整个模型。即要包含整个内容，而不要依赖so lver对话框去包含某 些要素。关于四类线性规划问题：资源分配问题：资源分配问题是将有限的资源分配到各种活动中去的线性规划问题。 这一类问题的共性是在线性规划模型中每一个函数限制为资

6、源限制，并且，每一种资 源都可以表现为如下形式，使用的资源数量=可用的资源数量。广义上的资源角度来说：使用的数量=可获得的数量解决资源分配问题的第一步是明确活动和资源，对每一个活动，需要作出活动数量的 决策，也就是要确定活动水平。一下三类数据是必须的：每种资源的可供量；每一种 活动所需要的各种资源的数量，对于每一种资源与活动的组合，单位活动所消耗的资 源量必须首先估计出来；每一种活动对总的绩效测度的单位贡献。它包含了生产分配和财务问题。它的一般建模步骤：首先确认问题的活动类型，问题的决策也就是决定各种活动的水平明确合适的绩效测度以求解问题估计每一种活动对于总绩效测度的单位贡献明确分配给各种活动

7、的有限资源对于每一种资源，明确可获得的数量以及各种活动的单位使用量将数据输入电子表格，可以在活动栏与可获得的资源栏之间要保留两个空栏的参数表 指定可变单元格来显示活动水平的决策量在第六步中产生的两个空栏，左边一栏做为输出单元格的总数栏，右边一栏为所有的 资源输入=符号，使用SUMPRODUCT函数指派目标单元格以显示总的绩效测度，也使用SUMPRODUCT函数成本收益平衡问题：成本收益平衡问题是一类线性规划问题，在这类问题中，通过选 择各种活动水平的组合，从而以最小的成本来实现最低可接受的各种收益水平。这类 问题的共性是，所有的函数约束条件均为收益约束，并具有如下的形式，完成的水平= 可接受的

8、最低水平它也需要三种数据：每种收益的最低可接受水平；每一种活动对一种收益的贡献；每 种活动的单位成本。解决任何成本收益平衡问题的第一步是明确活动和收益。线性规划建模的类型并不是由应用决定，而是由作出决策的各种限制条件决定的。其他的建模步骤跟资源问题大致相同。网络配送问题：它出现了一种新的限制条件一一确定需求的约束，确定的需求限制在 网络配送中占有重要的地位，且必须确定需求以及相应的确定需求的约束条件。首先必须明确这一网络配送问题的活动与需求，线性规划中确定需求的限制是以“=” 表示的等式，每种这样的限制都可以解释为一定数量的确定的需求：提供的数量=需 求的数量，纯网络配送问题的特点之一就是其建

9、模的主要函数约束是确定需求的约 束。但是，其他类型的线性规划问题也可能包含这一类的约束条件。4.混合型问题类型形式解释主要用于资源问题LHS=RHS对于特定的资源使用的数量 =RHS对于特定的收获达到的水平 =最低可接受水平成本收益平衡问题混合问题确定要求约束LHS=RHS对于一些数量提供的数量=需求的数量网络配送问题混合问题LHS=左式（一个 SUMPRODUCT 函数）RHS=右式（常数）混合线性规划问题建模过程的总结：【首先明确问题的各种活动，活动的水平即为要做出的决策】从管理的角度，为问题的解确定一个总绩效测度；对于每一种活动，估计活动对总技校测度的单位贡献；确定分配给各种活动的有限资

10、源，明确每一种资源可获得的数量以及活动的单位使用量； 确定各种活动的可获得的收益，并明确各种收益管理层所制定的最低可接受水平以及每种活 动的单位收益贡献；判别确定的需要，对于一些类型的数量，提供的数量必须等于需求的数量，明确每一种要求 的数量，以及每一活动对该要丢的数量的单位贡献；将36步所收集的数据输入到电子表格的数据单元格中；指明可变单元格一显示活动水平的各项决策；使用输出单元格来说明资源，收益以及确定需求的约束；指定目标单元格来显示总的绩效测度。检验模型的错误与遗漏的过程就是模型的确认。模型的扩展就叫模型的变异。如何会出现WHAT-IF问题：如果模型的参数的估计有误怎么办；如果作出不同的

11、似是而非的假设，问题的结果将会如何变化；如果管理方面所要求的某一选项没有被考虑在内，会产生怎么样的结果。线性规划的目的：对未来进行各种各样的假想，在这些假设下，测试各种管理方法可能产生 的结果，而通过对各种各样结果的深入分析来知道管理者作出最终的决定。WHAT-IF的基本作用：线性规划模型的许多参数在建模时是难精确的，只能是对一些数据的估计，通过 WHAT-IF分析可以表明，系数估计值必须精确到怎么样的程度，才能避免得出 错误的最优解，而且，可以找出哪些系数是需要重新精确定义的灵敏度参数。如果在研究结果之后，问题的条件发生了变化，通过WHAT-IF分析，即使不求 解，也可以表明模型参数的变化是

12、否会改变最优解。（通常称灵敏度分析；如果 模型的主要参数是管理层的政策决策而不是管理层所无法控制的外部数据，就可 以用这种前摄性分析方法）当模型特定的参数反映管理政策决策时，WHAT-IF分析可以表明改变这些决策 对结果的影响，从而有效指导管理者作出最终的决定。SOLVER TABLE可以解决一系列数据单元格的数值改变的问题；当在SOLVER TABLE的 第一栏里填入相关数据单元格的试验值时，请将第一行置空，以便在其他栏第一行的单元格 内填入可变单元格和（或）相应输出单元格的公式。【具体练习】能使最优解保持在相同的范围称为保持最优解的允许变化范围，简称最优域。目标函数中系数的允许变化范围是指

13、系数在次范围内变化最优解保持不变。EXCELSOLVER得出的灵敏度报告显示了目标函数允许的变化范围。如果参数的微小变动能引起最优解的变化，就认为它是敏感参数。二维SOLVER TABLE的使用，虽然他只能显示一组试算值的变化给单元格带来的影响， 但是使用符号“&”可以在表格中的一个单元格内可以显示多个单元格。任何需要在公式中显示的文本必须在两侧加以引号（比如“（” &A22& ，” &B12& “）”） &符号这此表示连接。多系数变化可以用一下三种方法来做，在电子表格上作相应的变动；使用二维SOLVER表 格；应用百分百法则。目标函数系数同时变化的百分之百法则：如果目标函数的系数同时变动，计

14、算出每一系数 变动量占该系数允许变化范围允许变动量的百分比，而后，将各个系数的变动百分比相加， 如果所得的和不超过100%，最优解不会改变，如果超过100%，则不能确定最优解是否改 变。注：1.百分百法则可以用于确定在保持最优解不变的条件下，目标函数系数的变动范围当模型中有大量的决策变量时，用电子表格系统的测试目标函数一部分或全部系数的 同步变动是相当不实际的，因为即使有代表性的变动组合数也是大量的。SOLVER表格只能 用来检验一次最多两个系数的变化。但是，百分百法则通过将允许的增加或减少值在各个系 数之间分摊，从而可以直接显示出每个系数的允许变动量。在线性规划的研究结束后，也可以节省修正模

15、型的时间。影子价格：在给定线性规划模型的最优解和目标函数相应值的条件下，影子价格就是约束常 数增加微小的量1，使得目标函数值增加的量，一般约束条件的影子价格显示了约束条件右 端值的改变给目标单元格带来的增长率。它在右端值在允许变化范围内保持正确。函数约束的右端值允许变化范围就是保持约束条件的影子价格有效时右端值变化的范围。考虑约束条件变化带来的影响时，常用三种方法：运用灵敏度报告只能用来分析左端值的 变化，而用电子表格和SOLVER表格分析左端系数和右端值的变化时过程是一样的。而着 重分析右端值。通过在一个单元格内输入有关另一个单元格的公式，一维SOLVER表格可以解决相关的 单元格的试算值。

16、虽然一维SOLVER表格只能用来研究一个数据格的试算值变化的情况， 但是可以通过上述方法来解决二维问题。约束右端值同时变化的百分百法则：同时改变几个或所有函数约束的约束右端值，如果这 些变化的幅度不大，那么可以用影子价格预测变动产生的影响。为了判别这些变动的幅度是 否允许，计算每一变动占可行域所允许的增加值或减少值的百分比，如果所有的百分比之和 不超过100%，那么，影子价格还是有效的，如果所有的百分比之和超过100%，那就无法 确定影子价格是否有效了。运输问题和指派问题都属于网络配送问题。运输问题的基本概念：运输问题最关心的是以最低的总配送成本把出发地的任何产品运送到每一个目的地；需求假设：

17、每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地， 与之类似，每一个目的地都有一个固定的需求量，整个需求量都必须有出发地满足。可行特征解：当且仅当供应量的总和等于需求量的总和时，运输问题才有可行解。成本假设：从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性 比例关系，因此这个成本就等于配送的单位乘以所配送的数量。模型：如果问题可以完全描述成以参数形式，明确出发地，目的地，供应量，需求量和 单位成本，符合需求假设和成本假设，那么这个问题（不管涉不涉及运输）都适用于运输问 题模型，最终目的都是要使配送的总成本最小。注：供应量，需求量和单位成本提供了运输问题所需要的

18、一切数据。运输问题的电子表格模型用两张分开的表格显示单位成本数据和可变单元格，在两张表中使 用相同的行号和列号。在可变单元格旁边表明了的约束条件。整数解的性质：只要它的供应量和需求量都是整数，任何有可行解的运输问题必然有所有 决策变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件。我们在execl中用到的SOLVER来解决运输问题的另一种方法是单纯形法，其中有运输单纯 形法和网络单纯形法，它们的运行速度很快，而网络的越来越有竞争力。运输问题变体类型：供应总量超过了需求总量。于是每一个供应量代表了从这个出发地中配送出去的 最大数量（而不是一个固定的值）需求总量超过了供应总量。于是

19、每一个需求量代表了在这个目的地中接收到的最 大数量（而不是一个固定的值）一个目的地同时存在着最小需求和最大需求，于是所有在这两个数值之间的数量 都是可以接受的在配送中不能使用特定的出发地一一目的地组合目标是使与配送数量有关的总利润最大而不是最小此上问题均有一般的解法，以后讨论。指派问题一般模型的假设：被指派者的数量和任务的数量是相同的每一个被指派者只完成一项任务每一项任务只能由一个被指派者完成每一个被指派者和每一项任务的组合都会有一个相关的成本问题的目标是要确定怎样进行指派才能使得总成本达到最小 网络表示法提供了另一种表示指派问题的方法 指派问题的变形：有一些被指派者并不能进行某一项任务虽然每

20、一个被指派者完成一项任务，但是任务比被指派者多。所以其中某些任务并 没有得到执行虽然每一项任务只由一个被指派者完成，但是这里被指派者比要完成的任务数量多。 所以，其中有一些被指派者没有指派到任务每一个被指派者可以同时被指派给多个任务每一项任务都可以由多个被指派者完成解决指派问题时有时会用到一种更为快捷的方法：匈牙利方法。网络最优化问题的求解，许多网络最优化问题实质上是线性规划问题的特殊类型，主要是构 建出一个模型，即有弧的模型。（最重要的即为画出网络模型）最小费用流问题是线性规划问题的特殊类型，也叫做网络配送问题。它的目标是通过配送网 络的运输成本最小。可以用网络图完整的表示最小成本问题。基本

21、术语：所有最小费用流问题都是用带有通过其中的流的网络表示的网络中的圆圈被称为节点如果节点产生的净流量（流出减去流入）是一个确定的正数的话，这个节点就是供 应点如果节点产生的净流量是一个确定的负数的话，那么这个节点就是需求点如果节点产生的净流量恒为零，那么这个节点就称为转运点，我们把流出节点的量 等于流入节点的量称为流量守恒网络中的箭头称为弧允许通过某一条弧的最大流量称为该弧的容量最小费用流问题的假设：至少一个节点是供应点至少一个节点是需求点所有剩下的节点都是转运点通过弧的流只允许沿着箭头的方向流动，通过弧的最大流量取决于该弧的容量（如 果流是双向的话，则需要用一对箭头指向相反方向的弧来表示）网

22、络中有足够的弧提供足够的容量，使得所有在供应点中产生的流都能够到达需求 点在流的单位成本已知的前提下，通过每一条弧的流的成本和流量成正比最小费用流问题的目标是在满足给定需求的条件下，使得通过网络供应的总成本最 下这类问题的解需要确定通过每一条弧的流有多大。具有可行解的特征：在以上的假设下，当且仅当供应点所提供的流量总和等于需求点所需要 的流量总和时，最小费用流问题有可行解。具有整数解的特征：只要其所有的供应，需求和弧的容量都是整数值，那么任何最小费用流 问题的可行解就一定有所有流量都是整数的最优解。容量限制在任何有流量限制的弧的最小费用流问题中都存在。最小费用流问题的任一个节点都需要净流量限制

23、Sumif的使用方法这里不加介绍。在这里也有网络单纯形法，它可以用来解决那些对于单纯形法来说太大而无法解决的大型问 题。最小费用流问题最重要的应用可能是在配送网络的运营上。几类典型的最小费用流问题的应用：应用的类型供应点转运点需求点配送网络的运作货源中间存储设备客户固体废弃物管理固体废弃物源处理设备固体废弃物掩埋地供应网络的运作供应商中间仓库加工设备工厂协调产品组合工厂某一特定产品的生产某一特定产品的市场现金流管理某一特定时间的现金 来源短期投资期权在特定时间对现金的 需求最小费用流问题的特殊类型：运输问题，没有转运点和弧的容量限制指派问题，供应量为一的供应点，每项任务都是需求量为一的需求点转

24、运问题，在出发点与目的地之间会有转运点，除此斗鱼运输问题一样最大流问题最短路问题对于此些做法，可以用网络单纯形法，它可以跟快捷的进行计算求解。对于最大流问题，它的目标是使目标单元格最大流量最大化。最大流问题的假设：网络中所有流起源于一个节点，这个节点叫做源，所有的流终止于另一个节点，这个 节点叫做收点其余所有的节点叫做转运点通过每一个弧的流只允许沿着弧的箭头所指方向流动。由源出发的所有的弧背向源， 而所有终于收点的弧都指向收点。最大流问题的目标是使得从源到收点的总流量最大。这个流量的大小可以用两种等价 的方法来衡量，分别叫做从源点出发的流量和进入收点的流量最大流问题与最小费用流问题的区别：供应点的供应量和需求点的需求量都是固定的，而源和收点则不同最小费用流问题中，不管是供应点的数量还是需求点的数量都可能多于一个，而在最 大流问题中只能有一个源和收点（若有多个，可用其变形）注：当网络中实际行进在多个节点结束时，我们在每一个这样的节点和虚拟目标地之间插入 一个长度为0的弧，从而使得网络中仍然只有一个目标地 最大流的一些实际应用：通过配送网络的流量最大通