运筹学期末复习

将知识点进行了归纳和整理，帮助学习者理解和记忆，包含动态规划、图与网络、网络计划、排队论、对策论、决策分析。希望对有需要的人有帮助。

运筹学期末复习

• 8动态规划
  • 动态规划的基本概念和基本方程
    • 这种把一个问题可看作是一个前后关联具有链状结构的多 阶段过程就称为多阶段决策过程，也称序贯决策过程。
    • 经典问题
      • 最短路径问题
        • 解决方法
          • (1) 穷举法
          • (2) 走一步看一步
          • (3) DP法
            • 基本思想： - （1）划分阶段，将问题化为一族同类子问题，逐个求解。 - （2）每个子问题求解时，要用到前面已求出的子问题的最 优结果。 - （3）每段的最优决策选取是从全局考虑的。
      • 资源分配问题
    • 基本概念
      • 1 、阶段
        • 动态规划模型可以转化为一系列子问题，每个子问题对应于一 个阶段，通常用k = 1, 2, . . , n表示 - 可以从时间、空间或者逻辑的角度来进行阶段划分。
      • 2 、状态与状态变量
        • 每个阶段的决策问题所面临的自然状况或客观条件称为该阶段的“状态 ”, 通常用Sk来表示
      • 3 、决策
        • 第k阶段的决策为Uk ，可行集合可能与状态有关，记为Dk(sk)
      • 4 、策略
        • 一个按顺序排列的决策组成的集合，记为 {U1 s1 , U2 s2 , … , Un sn } - 由过程的第 k 阶段开始到终止状态为止的过程，称为问题的后部子过程 （或称为k子过程）。
      • 5 、状态转移方程
        • 某阶段的状态到下一阶段状态的演变过程称为“状态转移”； - 由状态变量和该阶段的决策来确定，即sk+1 = Tk(sk, Uk)； - 状态转移方程式可以是确定型函数，也可以是随机型表达式。
      • 6 、指标函数和最优值函数
        • 用来衡量所实现过程优劣的一种数量指标。 - 在不同的问题中，指标函数的含义是不同的， 距离、利润、成本、产品的产量或资源消耗等。 - 阶段指标函数：第k阶段产生的效益，d (Sk, Uk) - fk sk 为从状态Sk出发，在第k~n 阶段通过最优策略所能获得的效益： fk Sk = max/ min d （Sk, Uk） + fk+1（ Sk+1）
      • 多阶段决策过程的动态规划模型可以表示为
  • 动态规划的最优性原理
    • 动态规划的最优性原理 、 对于一个多阶段决策问题，作为整个过程的最优 策略具有这样的性质： 无论过去的状态和决策如 何，对前面的决策所形成的状态而言，余下的诸 决策必须构成最优策略。” 、简言之，一个最优策略的子策略总是最优的。
    • 阶段1到阶段5最短规划是k（5）,那么阶段2到阶段4的规划必定在k(5)中取一段，
  • 动态规划的求解方法
  • 动态规划的管理应用
• 9图与网络
  • 图论中的经典问题
    • 哥尼斯七堡
      • 抽象图
    • 中国邮递员
      • 一名邮递员负责某一片区的信件投递。他每天从邮局出发，走遍片区所有街道至少一次，然后再返回邮局。
      • 抽象图
    • 周游世界
      • 要求游戏者从某个城市出发，把所有的城市都走过一次，且仅走过一次，然后回到出发点。
        • 抽象图
    • 旅行商
  • 图的基本概念和模型
    • 图是由点（研究对象）和边（对象之间的相互关系）组成。
      • 重要的是它们之间的相互关系
    • 无向图
      • 由点和边（不带箭头）所构成的图，记作G=(V,E) ，连接点的边记作[v_i,v_j]或者[v_j,v_i]。
    • 有向图
      • 由点和弧（带箭头）所构成的图，记作D=(V,A),其中V表示D的顶点集合， A表示D的弧集合。一条从v_i指向v_j的弧，记作（v_i,v_j）。
  • 拓展应用
    • 欧拉定理
      • 如果一个图是连通图，并且奇点的个数为0或2，那么它可以一笔画出； 否则，它不可以一笔画出。
    • 多阶段决策
      • 最近邻算法
        • 每到一阶段，找下一阶段最短的路
      • 枚举法
        • 找出所有路线的权重，选择最短的一条
      • 最优性思想：最短路的子路仍然是最短路
        • 标号法
      • 有负权重的加权网络
    • 最短路问题
      • 穷举法
      • 最近邻法
      • Dijkstra算法
        • 标号算法
    • 最大流问题
      • 概念
        • 网络的流
          • 是指对网络中的每一条弧，分配一个非负数。
        • 可行流
          • 定理：网络的可行流总是存在。（比如0）
        • 最大流：所有可行流中流量最大的流
          • • 建立数学模型
          • 定理：可行流f是最大流的充要条件是不存在从v_1到v_6的关于f的增广链。
        • 非零流量弧：流量大于零的弧。
          • 非饱和弧
            • 弧上的流量小于弧的容量。
          • 饱和弧
            • 弧上的流量等于弧的容量。
        • 零流量弧：流量等于零的弧。
        • 前向弧
          • u上的弧与u方向相同
            • 反之后向弧
              • 后向弧都是非零流弧
          • 前向弧都是非饱和弧
        • 欧拉回路
          • 遍历图中每条边一次且仅一次的回路
    • 旅行商问题
      • 一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市一次并且仅一次之后，回到出发城市
    • 中国邮递员问题
      • 一名邮递员负责某一片区的信件投递。他每天从邮局出发，走遍片区所有街道至少一次，然后再返回邮局。
      • 求解
        • 当这个图是欧拉图时，任何一条欧拉回路都符合要求；
        • 当这个图不是欧拉图时，中国邮递员问题可以转化为：将一个含有奇点的图添加一些重边使得它变成欧拉图，并且添加的重边的权重和最小。
  • 树
    • 无圈的连通图叫树
    • 性质1：从一个树中去掉任意一条边，则余下的图是不连通的。
    • 性质2：在树中不相邻的两个点间添上一条边，则恰好得到一个圈。
    • 性质3：树中必存在度为1的点
    • 性质4：具有n个顶点的树恰好有n-1条边。
    • 性质5：任何具有n个顶点、n-1条边的连通图是树。
    • 最小支撑树
      • 权重之和最小的支撑子图
    • 求最小支撑树
      • 破圈法
      • 避圈法
• 10网络计划
  • 最短工期
  • 应急工期
  • 资源分配
• 11排队论
  • 概念
  • 基本问题
• 13对策论
• 14决策分析
  • 决策基本概念和决策过程
    • 决策 是为达到某种预定的目标，在若干可供选择的行动方案中，确定一个最优或合理方案的过程
    • 主观决策模型和方法
    • 定量决策模型和方法
  • 风险型决策
  • 多属性决策
    • 多属性决策是指在考虑多个属性的情况下，选择最优的备选方案或者对方案进行排序的一种决策。
    • 决策方法
      • 层次分析法：将多目标决策问题，分解为目标层、指标层 和备选层，然后定性定量给出综合最优决策！
      • topsis
        • 数学工具
  • 不确定型决策
• 浮动主题
  • 单服务台模型
    • 无限队列模型
      • • • 经典例题
    • 无限队列，有限服务模型
      • 状态转移方程
    • 有限队列模型
  • 多服务台模型
    • 标准的[M/M/c]:[∞/∞/FCFS]模型
    • 系统容量有限的[M/M/c]:[N/∞/FCFS]模型
    • 有限顾客源的[M/M/c]:[∞/m/FCFS]模型