运筹学

内容纲要

@[toc]

网络计划

  • 工序:工程的组成部分
  • 工时:完成工序所需要的时间
  • 紧前、紧后、平行关系:确定各个环节之间的相互联系
  • 总工期:汇总
  1. 网络图
    网络图是由结点、弧、权所构成的有向图。

  2. 关键路线
    完成各个工序需要时间最长的路线

遵循原则

  1. 方向、时序与结点编号
  2. 紧前、紧后工序
  3. 虚工序:只表示逻辑关系,不消耗人力物力
  4. 相邻两结点只出现一条弧,无平行边
  5. 不能有缺口和回路

公时确定

  • 期望时间:(a + 4m + b) / 6
  • 最早开始时间:通常按箭头事项计算事项最早时间,等于从始点事项起到本事项最长路线的时间长度。

关键线路

像关键工序要时间,非关键工序要资源

  1. 直接成本:人工、原材料、燃料
  2. 间接成本:管理人员工资、行政办公费、采购费


动态规划

基本概念

  • 动态规划研究的对象是多阶段决策问题
  1. 状态变量
    • 若第k阶段旅行者的出发点记为s~g~,称s~k~为第k阶段的状态变量
  2. 状态集合
    • 第k阶段状态变量S~k~,可取顶点的全体记为S~k~,为状态集合
  3. 决策变量
    • 第K阶段的旅行者从状态X~k~出发,本阶段所选择的到达点记为x~k~(s~k~),称为决策变量,简写Xk。
  4. 决策集合
    • 当s~k~选定,决策变量x~k~取点的全体记为D~k(sk),称为决策集合
  5. 状态转移方程
    • 第k+1阶段的状态s~k+1~与第k阶段的状态s~k~、决策x~k~之间有函数关系`S~k+1~ = T~k~(s~k~, x~k~).
  6. 权函数
    • w~k~(s~k~, x~k~).
  7. 指标函数
  8. 递归方程

特征

  1. 描述性
  2. 无后效性
  3. 可知性

步骤

  1. 划分阶段
  2. 定义决策变量、决策集合
  3. 确定权函数
  4. 建立状态转移方程
  5. 确定指标函数
  6. 建立递归方程
    • 逆序求解

模型与求解


排队论

基本概念

  • 排队系统又称随机服务系统,是通过研究各种服务系统在排队等待现象中的概率特性,从而解决服务系统最优设计与最优控制的一门学科。

  • 提出某种服务需求的对象称为顾客

  • 实现服务的工具、设备和人员统称为服务机构

    要求服务的顾客的数量超过服务机构的能力。

  • 排队规则:

    1. 损失制
    2. 等待制
    3. 混合制
  • 模型表示
    用(X / Y / Z / A / B / C)表示
    X:顾客到达时间
    Y:服务时间的分布
    Z:服务台个数
    A:系统容量N
    B:顾客源数量m
    C:服务规则

M——到达过程为泊松分布或负指数分布
D——定长输入
Ek——k阶爱尔朗分布
G——一般互相独立随机分布

  • 逗留时间:一个顾客在系统中的停留时间,Ws
  • 等待时间:一个顾客在系统中排队等待的时间,Wq

到达规律

  1. 无后效性:任一时段的到达数不受前一时段的影响
  2. 平稳性:顾客到达是均匀的
  3. 稀有性:瞬时只有1个顾客到达


生灭过程

  • 机制:当它处于状态i时,只能转移到i+1或i-1两个状态,前者代表新生,后者代表死亡
    1. 圆表示状态
    2. 圆中标号表示状态符号,表示系统中稳定的顾客数
    3. 箭头表示从一个状态到另一个状态的转移












存储论

基本概念

  1. 存储费:货物占用资金应付的利息及使用仓库、保管货物等支出费用
  2. 订货费:订购费用+可变费用
  3. 生产费:补充存储时所需费用,一项是固定费用,另一项是与生产产品的数量有关的费用


博弈论

三个要素

  • 局中人S1
  • 策略集S2
  • 支付函数A

矩阵博弈(零和博弈)

  1. 局中人只有两个
  2. 双方利益完全对抗
  3. 有限个可供选择的策略
  4. 两个局中人得失之和为零

纯策略与混合策略

  • 纯策略是指确定的选择某策略
  • 混合策略指以某一概率分布选择各策略

留下评论

您的电子邮箱地址不会被公开。