运筹学基础（02375） · 第四章：库存与经济订货量至第八章：图论与网络优化

返回分篇目录

本页保留旧课程笔记与旧链接，修复公式并补充适用条件。系统课程与习题见大三数学。

按问题定位：预测/回归 · 最小最大遗憾 · 经济订货量 EOQ · 线性规划 · 运输与网络计划 · 最短路/流 · 平稳分布 · 盈亏平衡/排队。

第四章：库存与经济订货量

库存与经济订货量概念

• 库存的作用：库存的作用最基本的一个方面，就是保证工业企业的生产能够正常地、连续地、均衡地进行
• 库存费用分析：订货费=（年需要量/订货量）× 一次订货费，当企业的年需求量一定，每次的订货批量增加时，全年的订货费将会减少，库存费用=订货费+保管费，在保证正常供应条件下（不考虑缺货费用），随着订货量的增大，计划期限内（一般以年为限）采购次数减少，采购费用下降，但保管费用却相应上升
• 平均库存量：在需求以恒定速率消耗、瞬时补货、不允许缺货且不设安全库存的基本 EOQ 模型中，平均库存为批量 $N/2$。若始终保留安全库存 $S$，则为 $S+N/2$；有限速率生产补货需另用生产批量模型，不能直接套用。
• 经济订货量：经济订货量（the economic order quantity，缩写为 EOQ）是使总的存货费用达到最低的为某个台套或某个存货单元确定的最佳的订货批量。使保管和订货费用达到最小值的订货量

库存成本与订货量

以下订货/保管成本使用同一年度：$D$ 为年需求量，$N>0$ 为每次订货量，$P_0>0$ 为每次订货费，$C_0>0$ 为单位年度保管费。基本 EOQ 假设需求恒定、瞬时补货、无缺货且无安全库存；模型不同不能直接套用。

本模型总相关成本 $TC(N)=D{P}_0/N+N{C}_0/2$，其连续最优订货量为 $N^{\ast }=\sqrt{2D{P}_0/C_0}$。例如 $D=1000$ 件/年、$P_0=20$ 元/次、$C_0=1$ 元/(件·年)，得到 $N^{\ast }=200$ 件，年订货费与保管费各100元，总计200元；采购单价成本若不随批量变，是本次优化中不变的项。

• 库存费用分析

  • 库存费用模型结构

    • 原材料费用模型库存费用

      $$\mathrm{库}\mathrm{存}\mathrm{费}\mathrm{用}=\mathrm{订}\mathrm{货}\mathrm{费}+\mathrm{保}\mathrm{管}\mathrm{费}$$$$TC=P+C$$

    • 半成品和成品库存费用

      $$\mathrm{库}\mathrm{存}\mathrm{费}\mathrm{用}(TC)=\mathrm{工}\mathrm{装}\mathrm{调}\mathrm{整}\mathrm{费}+\mathrm{保}\mathrm{管}\mathrm{费}$$$$TC=S+C$$

  • 库存费用

    • 订货费用

      $$\mathrm{订}\mathrm{货}\mathrm{费}=\frac{\mathrm{年}\mathrm{需}\mathrm{要}\mathrm{量}}{\mathrm{订}\mathrm{货}\mathrm{量}}\ast \mathrm{一}\mathrm{次}\mathrm{订}\mathrm{货}\mathrm{费}$$$$P=\frac{D}{N}\ast P_0$$

    • 工装调整费

      $$\mathrm{工}\mathrm{装}\mathrm{调}\mathrm{整}\mathrm{费}=\frac{\mathrm{年}\mathrm{计}\mathrm{划}\mathrm{产}\mathrm{量}}{\mathrm{生}\mathrm{成}\mathrm{批}\mathrm{量}}\ast \mathrm{一}\mathrm{次}\mathrm{工}\mathrm{装}\mathrm{调}\mathrm{整}\mathrm{费}$$$$S=\frac{R}{N}\ast P_s$$

    • 保管费

      $$\mathrm{保}\mathrm{管}\mathrm{费}=\mathrm{平}\mathrm{均}\mathrm{库}\mathrm{存}\mathrm{量}\ast \mathrm{单}\mathrm{位}\mathrm{物}\mathrm{质}\mathrm{保}\mathrm{管}\mathrm{费}$$$$C=\frac{N}{2}{C}_0$$

  • 保管费（存货套、单元 年度保管费用）

    $$\mathrm{保}\mathrm{管}\mathrm{费}=\mathrm{平}\mathrm{均}\mathrm{库}\mathrm{存}\mathrm{量}\ast \mathrm{库}\mathrm{存}\mathrm{物}\mathrm{资}\mathrm{单}\mathrm{价}\ast \mathrm{保}\mathrm{管}\mathrm{费}\mathrm{率}$$$$C=\frac{1}{2}Np{C}_i$$

    这里 $p$ 是库存物资单价，$C_i$ 是年度保管费率，与前式表示年计划产量的 $R$ 区分；$C_0=p{C}_i$ 是单位物资年度保管费。

• 平均库存的概念

  $N$表示订货量大小

  • 平均库存额$$\mathrm{平}\mathrm{均}\mathrm{库}\mathrm{存}\mathrm{额}=\mathrm{每}\mathrm{个}\mathrm{单}\mathrm{元}\mathrm{货}\mathrm{每}\mathrm{个}\mathrm{套}\mathrm{台}\mathrm{的}\mathrm{单}\mathrm{位}\mathrm{价}\mathrm{格}（\mathrm{库}\mathrm{存}\mathrm{物}\mathrm{资}\mathrm{单}\mathrm{位}）\ast \mathrm{平}\mathrm{均}\mathrm{库}\mathrm{存}\mathrm{量}$$$$M=\frac{1}{2}Np$$

第五章：线性规划

线性规划概念

• 线性规划：线性规划的基本特点是线性函数
• 约束条件：线性规划的模型结构中，决策对于实现目标的限制因素
• 最优解：在所有可行解中，使目标函数取得最小值（最小化问题）或最大值（最大化问题）的解；仅满足约束条件还只是可行解。
• 先寻找基本可行解再建立单纯形表；原点不一定可行，必要时使用两阶段法。
  • 标准形式 $Ax=b,x\ge 0$ 中，设 $A$ 有 $m$ 个线性独立行。选取 $m$ 个线性独立列构成基矩阵 $B$，将非基变量置零，得到唯一基解 $x_B=B^{-1}b$；非负时才是基本可行解。
  • 线性规划模型中，基解要求所有的非基变量都等于 0
  • 标准形式线性规划若可行且有有限最优值，至少存在一个基本可行最优解；并非所有最优解都是基本解（最优边上可以有无穷多个点）。
• 约束方程的个数
  • 先删去冗余约束并检查相容性。若 $A$ 满行秩且有 $m$ 行、$n$ 个变量，则基变量数为 $m$，非基变量数为 $n-m$；未去冗余时不能用表面上的方程条数代替矩阵秩。
  • 初始单纯形表对应已确认的基本可行解，不能不检查约束就以原点起步。

线性规划标准形式

标准形式可写为 $min{c}^{\mathsf{T}}x$，约束 $Ax=b,x\ge 0$。目标函数和约束均须为线性；可行域为空表示无可行解，目标沿可行方向无限改善表示无界。

第六章：运输问题

运输问题概念

• 运输问题的解决步骤
  • 求初始调运方案
  • 对初始调运方案进行改进
  • 求得最优方案
• 闭合回路法
  • 在求解运输问题时，对运输表中各个空格寻求改进路线和计算改进指数的方法
  • 闭合回路法先对各个空格寻求一条闭合的改进路线，然后再按每条改进路线计算每个空格的改进指数
• 需要量小于供应量的运输问题
  • 总需求量小于总供应量时，增设一个虚拟需求点，其需求量等于两者之差；与真实需求点个数多少无关。
  • 仅当剩余供应闲置没有额外成本时，虚拟路线单位费用取0；若有保管、处置或闲置成本，必须按实际模型计入。

第七章：网络计划与关键线路

网络计划与关键线路概念

• 网络图的分类
  • 箭线式网络图：箭线代表活动（作业），以结点代表活动的开始和完成，由活动、结点和线路三个部分组成
  • 结点式网络图：结点代表活动，以箭线表示各活动之间的先后承接关系
• 关键线路的特点
  • 线路时差为 0
  • 主要矛盾线
  • 所需工时最长
• 线路：从网络的始点开始，顺着箭线的方向，中间经过互相连接的结点和箭线，到网络终点为止的连线
• 作业时间：网络图中，一定生产技术条件下，完成一项活动或一道工序所需时间
• 最乐观时间：网络图中，完成一项活动可能最短的时间
• 最可能时间：网络图中，正常条件下完成一项活动可能性最大的时间
• 最保守时间：最保守时间：完成一项活动可能最长的时间
• 活动的四个时间
  • 对箭线式网络的活动 $(i,j)$，工时为 $t_{ij}$，节点最早、最迟发生时间分别记为 $T_E,T_L$。
  • 最早开始时间：$E{S}_{ij}=T_E(i)$。
  • 最早完成时间：$E{F}_{ij}=T_E(i)+t_{ij}$。
  • 最迟开始时间：$L{S}_{ij}=T_L(j)-t_{ij}$，从箭头节点倒推，不是直接取箭尾节点的最迟时间。
  • 最迟完成时间：$L{F}_{ij}=T_L(j)$。

第八章：图论与网络优化

图论与网络优化概念

• 图的最基本的要素
  • 点：表示要研究的对象
  • 点之间的连线：表示对象之间的某种特定的关系
  • 连通图：在网络图中，如果所有的点都可以通过相互之间的连线而连通，则这种图形称为连通图
  • 树：在一个网络中，如果图形是连通且不含圈的，则这种图形称之为树
  • 几种问题的解决方法
    • 最小枝杈树问题：普赖姆法或克鲁斯喀尔法
    • 最短线路问题：最短路线法
    • 最大流量问题：有向图解法，找出能在起点进入，并通过这个网络，在终点输出的最大流量
    • 最佳订货批量问题：表格法、图解法、数学方法
    • 最小枝杈树问题：在一个网络中，如果从一个起点出发到所有的点，找出一条或几条路线，以使在这样一些路线中所采用的全部支线的总长度最小，这种方法称之为最小枝杈树问题
    • 网络图的几种常见问题模型
      • 网络路线问题：从入口到出口、最少时间，最短距离或最少费用
      • 最大流量问题：满足边容量和中间节点流量守恒，使源到汇的总流量最大。若还要求最大流中费用最小，需另建最小费用最大流模型；时间最短也是另一类目标。
      • 最小枝杈树问题：起点到所有点、长度最小、费用最小