运筹学概念.docx

运筹学：Operational Research,是一门应用科学。从实际出发解决实际问题的方法。 建模七步：第一步，定义问题；第二步，收集数据；第三步，构造模型；第四步， 验证模型；第五步，计算结果；第六步，提交报告；第七步，投入使用 线性规划是由丹捷格（GB.Dantzig）在1947提出的，并提出了求解线性规划的单 纯形法，成为运筹学的标志性成就，被誉为线性规划之父。 线性规划模型就是目标函数为线性函数，约束条件也是线性函数的最优化模型。 线性规划模型包括三个部分：目标函数；决策变量；约束条件。 满足所有约束条件的解称为该线性规划的可行解；线性规划问题可行解的集合，称 为可行域。 把使得目标函数值最大（或最小）的可行解称为该线性规划的最优解，此目标函数 称为最优目标函数值，简称最优值。 图解法只适合于二维线性规划问题 松弛量：对一个的”约束条件中，没有使用完的资源或能力的大小称为松弛量（松 弛或空闲能力） 剩余变量，约束方程左边为一”不等式时，变成等式约束条件 如果线性规划问题有最优解，则一定有一个可行域的顶点对应一个最优解；（一定可 以在其顶点达到，但不一定只在其顶点达到，有时在两顶点的连线上得到，包括顶 点） 唯一最优解：只在其一个顶点达到 无穷多个最优解：在其两个顶点的连线上达到 无界解：可行域无界。缺少必要的约束 无可行解（无解）：可行域为空集。约束条件自相矛盾导致的建模错误 灵敏度分析：在建立数学模型和求得最优解之后，研究线性规划的一些系数ci、aij、 bj变化时，对最优解产生什么影响。或者是这些参数在什么范围内发生变化，最优 解不变。 对偶价格：在约束条件右边常量增加一个单位而使最优目标函数得到改进的数量称 之为这个约束条件的对偶价格。 对偶价格可以理解为对目标函数的贡献。如果对偶价格大于零，则其最优目标函数 值得到改进。即求最大值时，变得更大；求最小值时，变得更小。 如果对偶价格小于零，则其最优目标函数值变坏。即求最大值时，变得小了；求最 小值时，变得大了。 如果对偶价格等于零，则其最优目标函数值不变。 单纯形法的基本思路：寻找顶点中使得目标函数值最大的一个就是目标函数的最优 解 单纯形法是一种迭代方法 基：系数矩阵中的mXm的非奇异子矩阵； 基向量：基中的列； 非基向量：非基部分中的列； 基变量：基向量对应的变量； 非基变量：与非基变量对应的变量； 基本解（基解）：令非基变量都等于0得到的解为基本解。 基本可行解：基本解如果都非负，则为基本可行解，对应的基称可行基。 基本可行解中，将基变量用非基变量表示，带入目标函数，这时目标函数中就没有 基变量了，只剩下非基变量，它们的系数称为检验数 基变换：让一个非基变量入基，因此必须让一个基变量出基，以保持m个基变量不 变 图论中的图由点和点及之间的连线（带箭头、不带箭头）构成 有向图：由点和弧（带箭头的连线）构成；无向图：由点和边构成。 赋权图：边或弧相关有相应的指标（权重），例如距离、费用等等。 连通图：无向图中两点之间，至少存在一条链 回路（路的第一点和最后一点相同） 网络（有起点和发点的赋权有向图，称为网络） 树（无圈的连通图） 截集：将图G的点分成两个非空集合，分别包含起点和终点，分别记为VI, V2O 从VI的点到V2的点的所有弧的集合称为图G的一个截集。 关键路线法（CPM）、计划评审法（PERT）； PERT/CPM称为统筹方法 工序：弧表示工序，从开始指向结束。 工序内容：上面标工序代号，下面标完成工序所需的资源。（赋权弧） 紧前工序：紧靠某工序前面的工序，紧前工序完成后才能开始这一工序。在网络图 中用一个点来表示某一工序的开始和某紧前工序的结束。工序从左向右排列。 紧后工序：紧靠某工序后面的工序。 总工期：完成所有工序的总时间。 路线：从起点到终点之间相连接的节点的序列 虚工序：实际并不存在，虚设的工序。表示相邻工序之间的衔接关系。虚工序不需 要人工、物力。 画网络图注意点：两点之间只有一条弧；不能有缺口：除发点和收点外，其他各个 点的前后都应有弧连接。即从发点经过任何路线都可以到达收点，必要时可以添加 虚工序。不能产生回路，否则将使组成的工序永远不能结束。 关键路线一一从起点到终点的最长路线 基本存贮模型中考虑到库存涉及到的两种费用：存贮费用和订购费用。一次订购得 多，则订购次数少，订购费用少，但存贮费用高。所以我们需要寻找其中的平衡。 经济订购批量表明最优订购量（最大库存量）与需求呈平方根关系。 理性决策理论模型（古典决策理论模型、经济模型、理性决策模型）：假设决策者完 全理性； 行为决策理论：有限理性决策模型（西蒙模型）；成功管理决策模型（彼得斯沃特 曼模型）；社会模型（社会心理模型） MM1 ：顾客的到达服从泊松分布；服务时间服从负指数分布（此时单位时间里完 成服务的顾客数即服务率就服从泊松分布）；单通道即一个服务台；排队长度无限制; 顾客来源无限制；先到先服务。 MMC：顾客的到达服从泊松分布；每个服务台的服务时间服从负指数分布；多通 道即多个服务台；排队长度无限制，顾客来源无限制。只排一个队，先到先服务， 当其中一个服务台有空时，排在第一个的顾客就上去接受服务 MG1：表示服务时间分布是任意的概率分布。 记为MD1,因服务时间是常数，均方差为。=0 MGcc-：泊松到达、任意服务时间、c个服务台、系统中最多能容纳c个顾客、 顾客源无限制。 一位顾客在系统里的平均逗留时间恒为w =w+- q4 层次分析方法(Analytic Hierarchy Process),简称AHP法，是指依据序标度，将系 统因素按支配关系分组以形成有序的递阶层次结构，通过两两比较判断的方式确定 每一层次中因素的相对重要性，然后在递阶层次结构内进行合成以得到决策因素相 对于目标的重要性的总顺序，从而为决策提供确定性的判据。 层次结构：(1)目标层(A)；(2)准则层(C)；(3)方案层(P) 一致性检验防止循环论证。当C.R.<0.1时，认为判断矩阵的一致性是可以接受的； 当时，认为应该对判断矩阵的一致性作适当修正。 时间序列：实际问题中某一变量或指标的数值或统计观测值，按时间顺序排列成一 个数字序列。 时间序列的成分：趋势成分(Trend component): T；循环成分(Cyclical component): C；季节成分(Seasonal component): S；不规则成分(Irregular component): I The Additive model (加法模型)yt = Tt + Ct + St + It The multiplicative model (乘法模型)yt = Tt x Ct x St x It 平滑法：适用于稳定的时间序列一即没有明显的趋势、循环和季节影响。包括：移 动平均、加权移动平均、指数平滑平滑法 移动平均移动平均数=最近z期数据之和L= F =工"+1 + X-L+2 +, +匕7+工 z -L 加权移动平均£+1 = *3 + + *L其中=1./=! 指数平滑4+1 =aZ+(l a)耳。：平滑常数(OKaWl) 其他概念y(K-F)2均方误差MSE =/人m平均绝对偏差m平均绝对百分误差"人IP 1 丁 X耳MAPE= > 指数平滑时a的取值的意义