浙江大学管理学院 杜 红 duhong@cma.zju.edu.cn 管理科学方法（复习版） 浙江大学管理学院 杜 红 duhong@cma.zju.edu.cn.

Presentation on theme: "浙江大学管理学院 杜 红 duhong@cma.zju.edu.cn 管理科学方法（复习版） 浙江大学管理学院 杜 红 duhong@cma.zju.edu.cn."— Presentation transcript:

1 浙江大学管理学院 杜 红 duhong@cma.zju.edu.cn
管理科学方法（复习版） 浙江大学管理学院 杜 红

2 第一章 管理科学简介 狭义的管理科学：数理方法制定管理决策 运筹方法（问题、建模、解决）
第一章 管理科学简介 狭义的管理科学：数理方法制定管理决策 Management Science = Operations research (MS=OR) 决策制定（主体、环境、过程） 定量分析（数学、概率、统计） 运筹方法（问题、建模、解决）

3 第一章 管理科学简介 管理科学的方法论 定性分析的方法 德尔菲方法 小组讨论 …… 定量模型的运用 运筹模型

4 第一章 管理科学简介 运筹方法－解决典型管理问题 解决方法 典型的办法 财务模型 线性规划 目标规划 预 测 网络分析 决策分析 库存模型
第一章 管理科学简介 运筹方法－解决典型管理问题 解决方法 典型的办法 财务模型 线性规划 目标规划 预 测 网络分析 决策分析 库存模型 概率统计 排队模拟 盈亏平衡与经营安全分析 在线性目标和约束条件下取得最优结果 在多个相对立的目标下寻得合理结果 设计时间序列，或找到因果关系 用各种活动和事件的网络排列来说明项目计划 风险决策与不确定决策的基本方法 寻求使库存成本降至最低的存储策略 数学期望与概率分布 分析等待的队列,模拟合理作业时间和资源利用

5 第三章 线性规划模型 建立线性规划问题模型 模型构建的一般思路： 确定该LP问题的目标是什么？ 实现目标取决于什么因素和条件？
第三章 线性规划模型 建立线性规划问题模型 模型构建的一般思路： 确定该LP问题的目标是什么？ 实现目标取决于什么因素和条件？ 确定哪几个因素为决策变量？ 目标如何用决策变量来加以描述？ 约束条件如何表达？ 决策变量本身是否有限制条件？

6 第三章 线性规划模型 线性规划问题模型的一般形式： 目标函数： 约束条件：

7 第三章 线性规划模型 线性规划问题的基本要求 目标函数和约束条件必须是线性函数； 线性表达：相加性、比例性 决策变量的连续分布；
第三章 线性规划模型 线性规划问题的基本要求 目标函数和约束条件必须是线性函数； 线性表达：相加性、比例性 决策变量的连续分布； 不限于整数，可以是小数，但不能四舍五入 目标函数的单一性； 多目标是要设法简化成单目标 模型必须是确定型的； 所有参数a、b、c都应是确定值 决策变量的非负性

8 第三章 线性规划模型 两个变量的线性规划问题的几何解释 例：求解以下线性规划问题 Max z = X1+3X2 s.t. X1+ X2≤6
第三章 线性规划模型 两个变量的线性规划问题的几何解释 例：求解以下线性规划问题 x2 Max z = X1+3X2 s.t. X1+ X2≤6 -X1+2X2≤8 X1 , X2≥0 6 5 4 3 2 1 (4/3,14/3) z=15.3 可行域 z=12 z=9 z=6 z=3 z=0 x1 目标函数等值线 Z = X1+3X2

9 第三章 线性规划模型 对偶问题与影子价格 MAX Z = CTX s.t. AX≤b X≥0 为原始问题，则称以下问题
第三章 线性规划模型 对偶问题与影子价格 定义： 设以下线性规划问题 MAX Z = CTX s.t AX≤b X≥0 为原始问题，则称以下问题 MIN W = bTY s.t ATY≥C Y≥0 为原始问题的对偶问题，最优值Y为影子价格

10 第三章 线性规划模型 对偶问题与原始问题的关系 目标 变 量 n xj≥0 aTijyi≥cj 约 束 xj无约束 aTijyi=cj
第三章 线性规划模型 对偶问题与原始问题的关系 目标 极大化问题 Cj（max Z） 极小化问题bi（min W） 变 量 n xj≥0  aTijyi≥cj 约 束 xj无约束 aTijyi=cj xj≤0 aTijyi≤cj m aijxj≥bi yi≤0 aijxj=bi yi无约束 aijxj≤bi yi≥0

11 第三章 线性规划模型 对偶问题的性质 对偶问题的对偶是原问题。
第三章 线性规划模型 对偶问题的性质 对偶问题的对偶是原问题。 若两个互为对偶问题之一有最优解，则另一个必有最优解，且目标函数值相等(Z*=W*)，最优解满足CX*=Y*b。 若X*,Y*分别是原问题和对偶问题的可行解，则 X*,Y*为最优解的充分必要条件是Y*XL=0和YSX*=0。 原问题标准型： Max Z= CX AX + XL= b X,XL≥0 对偶问题标准型： Min W= Yb YA - YS= C Y,YS≥0

12 第三章 线性规划模型 原问题和对偶问题的互补松松弛关系：

13 第三章 线性规划模型 对偶问题求解举例： 对以下线性规划问题： MIN Z＝2X1－X2＋2X3 s.t. －X1＋X2＋X3＝4
第三章 线性规划模型 对偶问题求解举例： 对以下线性规划问题： MIN Z＝2X1－X2＋2X3 s.t. －X1＋X2＋X3＝4 －X1＋X2－KX3≤6 X1≤0，X2≥ 0，X3 无约束 已知其最优解为 X1* =－5 , X2* = 0 , X3* =－1。 写出其对偶问题并求其最优解和 K 的值。 写出对偶问题： MAX W = 4Y1+6Y2 s.t. -Y1-Y2 ≥2 Y1+Y2≤-1 Y1-KY2=2 Y2≤0 根据对偶性质： 4Y1+6Y2 = -12 -Y1-Y2 =2 Y1-KY2=2 Y1*=0,Y2*=-2,K=1

14 第三章 线性规划模型 对偶问题解－－影子价格 根据对偶问题的性质有： Z* = W* = ∑bi yi* 两边对bi求偏导数得到： ∂ Z*
第三章 线性规划模型 对偶问题解－－影子价格 根据对偶问题的性质有： Z* = W* = ∑bi yi* 两边对bi求偏导数得到： ∂ Z* = yi* (i= 1,2, …,m) ∂ bi 即 yi* 表示每增加一个单位 bi 后 Z* 的增量

15 第三章 线性规划模型 线性规划模型的应用 生产计划问题（教材P42,实例3.1,例3-6) 项目投资问题（教材P43,实例3.2,例3-7)
第三章 线性规划模型 线性规划模型的应用 生产计划问题（教材P42,实例3.1,例3-6) 项目投资问题（教材P43,实例3.2,例3-7) 配料配套问题（教材P44,实例3.3,作业) 合理下料问题（例3-8) 运输调运问题（线性规划问题扩展） 任务指派问题（线性规划问题扩展）

16 第四章 线性规划的扩展 整数线性规划(Integer Linear Programming, ILP) 所有变量都取整数的规划称为纯整数规划
第四章 线性规划的扩展 整数线性规划(Integer Linear Programming, ILP) 问题定义： 决策变量是整数的线性规划 所有变量都取整数的规划称为纯整数规划 部分变量取整数的规划称为混合整数规划 整数规划与线性规划的关系 线性规划问题 整数规划问题

17 第四章 线性规划的扩展 整数规划与线性规划解的差异 A B X2 线性规划解：A （2.6，3.8）, Z=17.8 整数规划解： B
第四章 线性规划的扩展 整数规划与线性规划解的差异 X2 线性规划解：A （2.6，3.8）, Z=17.8 A 整数规划解： B （5，3 ）, Z=17.0 B X1

18 第四章 线性规划的扩展 0-1规划 一些变量的取值被限定为0或1。是整数规划的特例。 0-1规划的一般模型： s.t.
第四章 线性规划的扩展 0-1规划 一些变量的取值被限定为0或1。是整数规划的特例。 0-1规划的一般模型： s.t. Xj = 0,1 j=1,2,…,n （X=0,1 等价于 X≤1, X≥0 且取整数。） 0-1规划问题求解：思路与LP、IP问题一致。 教材P81－83 实例4.7、实例4.8

19 第四章 线性规划的扩展 考虑固定成本的最小生产费用问题
第四章 线性规划的扩展 考虑固定成本的最小生产费用问题 某工厂有三种设备均可生产同一产品，第j种设备运行的固定成本为dj，运行的单位变动成本为cj，则生产成本与产量xj的关系为： j=1,2,3 如何使设备运行的总成本最小？

20 第四章 线性规划的扩展 引入0－1变量 yj ， 令 建立以下模型： 这里M是一个很大的正数。
第四章 线性规划的扩展 引入0－1变量 yj ， 令 建立以下模型： 这里M是一个很大的正数。 当yj=0时，xj=0，即第j种设备不运行，相应的运行成本 djyj+cjxj=0 当yj＝1时，0≤xj≤M，实际上对xj没有限制，运行成本为 dj+cjxj 这是一个混合0-1规划问题

21 第四章 线性规划的扩展 互斥约束的处理：如：︱f(x)︱≥ a (a≥0)
第四章 线性规划的扩展 互斥约束的处理：如：︱f(x)︱≥ a (a≥0) 当问题需要同时考虑一对分段约束时，如何将其同时出现在模型中（非线性变成线性）： 如： f(x)-3≥0 (1) ; f(x)≤0 (2) 通过引入一个0－1整数变量 y 和一个充分大的正实数M, 可化为： －f(x)+3≤My (3) f(x) ≤M(1-y) (4) 当y=0时，(3)=(1), (4)自然成立，不起作用 当y=1时，(4)=(2),(3)为：3≤M+f(x),当M很大时也自然成立，因此也不起作用。 （3）和（4）可同时进入模型约束。

22 第四章 线性规划的扩展 多中选一的处理： 模型希望在下列n个约束中，只能有一个约束有效：
第四章 线性规划的扩展 多中选一的处理： 模型希望在下列n个约束中，只能有一个约束有效： fi (x) ≤ 0 (i=1,2,…,n) （1） 引入n个0－1整数变量yi ,(i=1,2,…,n),可将上式改写为： fi (x) ≤ M(1- yi) (i=1,2,…,n), (2) (3) M为任意大的正数。 (2) : 当yi＝1 时 ，(2)=(1) ; yi ＝0 时，自然满足 (3) : 保证了yi 有且只有一个取值为1，其余为0。

23 第四章 线性规划的扩展 多中选一的处理： 模型希望在下列n个约束中，只能有一个约束有效：
第四章 线性规划的扩展 多中选一的处理： 模型希望在下列n个约束中，只能有一个约束有效： fi (x) ≤ 0 (i=1,2,…,n) （1） 引入n个0－1整数变量yi ,(i=1,2,…,n),可将上式改写为： fi (x) ≤ M(1- yi) (i=1,2,…,n), (2) (3) M为任意大的正数。 (2) : 当yi＝1 时 ，(2)=(1) ; yi ＝0 时，自然满足 (3) : 保证了yi 有且只有一个取值为1，其余为0。

24 第四章 线性规划的扩展 多中选一的处理： 模型希望在下列2个约束中，只能有一个约束有效： 3X1+4X2 ≤ 5，4X3-2X2≤ 3
第四章 线性规划的扩展 多中选一的处理： 模型希望在下列2个约束中，只能有一个约束有效： 3X1+4X2 ≤ 5，4X3-2X2≤ 3 引入2个0－1整数变量yi ,(i=1,2),可将上式改写为： （Y=1时不采用，Y＝0时采用） 3X1+4X2 ≤ 5 + M×Y1 4X3-2X2≤ 3 +M×Y2 Y1+Y2=1 M为任意大的正数。

25 第四章 线性规划的扩展 指派问题 n项任务（B1,B2,…,Bn)由n个人 (A1,A2,…,An) 去完成，每项任务交给一人，每人只有一项任务。第i个人Ai去做第j项任务Bj的工作效率（如工时、成本或价值等）为Cij。问如何安排人员使总工作效率最好？ 设Xij表示Ai完成Bj工作，并令 1 当指派Ai去完成Bj工作 Xij = 0 当不指派Ai去完成Bj工作

26 第四章 线性规划的扩展 指派问题数学模型的标准型 MIN Z = （Cij≥0) （i= 1,2,…,n) (j= 1,2,…,n)
第四章 线性规划的扩展 指派问题数学模型的标准型 MIN Z = （Cij≥0) （i= 1,2,…,n) (j= 1,2,…,n) Xij 皆为 0 或 1 由 Cij 组成的方阵 C = ( Cij )n×n 称为效率矩阵

27 第四章 线性规划的扩展 指派问题标准型的求解－匈牙利法
第四章 线性规划的扩展 指派问题标准型的求解－匈牙利法 指派问题有以下性质： 若从效率矩阵C的任何一行（列）各元素中分别减去一个常数K（K可正可负）得到新矩阵D,则以D为效率矩阵的指派问题与原问题有相同的解，但最优值比原问题最优值小K。 用匈牙利法求解的条件： MIN、i=j 、Cij≥0

28 第四章 线性规划的扩展 匈牙利法的主要步骤： 第一步：变换效率矩阵，使在各行各列都出现零元素。 1、从矩阵C的每行元素减去该行的最小元素；
第四章 线性规划的扩展 匈牙利法的主要步骤： 第一步：变换效率矩阵，使在各行各列都出现零元素。 1、从矩阵C的每行元素减去该行的最小元素； 2、再从所得矩阵的每列中减去该列最小元素。 第二步：以最少数目的水平线和垂直线划去所有的零元素。如果所用的直线等于行或列数，则结束指派。否则继续。 第三步：找到没有被划去的最小的元素，所有没有被划中的元素减去这一最小值。而被划中两次的元素（该元素行列都被划中）则要加上这一最小值。再返回到第一步。 第四步：最后根据零元素的位置，确定最优分配方案。

29 练习题：建立线性规划模型

30 练习题1：建立线性规划模型 确定决策变量： X1，X2，X3为每月买进的商品量 Y1，Y2，Y3为每月卖出的商品量 确定目标函数：
MAX Z=3.31Y1+3.25Y2+2.95Y3 -2.85X1-3.05X2-2.90X3 确定约束条件： 买进的商品当月到货下月卖出，每月卖出的量应小于月初时的库存量 在买卖时间没有严格要求的情况下，先卖再买总是有利的，因此每月最大库存量为月初库存减去卖出再加上买进的量

31 练习题1：建立线性规划模型 月初库存量 买进 卖出 一月 1000 X1 Y1 二月 1000－Y1+X1 X2 Y2
月初库存量 买进 卖出 一月 X1 Y1 二月 －Y1+X X2 Y2 三月 －Y1+X1-Y2+X X3 Y3 因此： Y1 ≤ 1000 Y2 ≤ 1000－Y1+X1 Y3 ≤ 1000－Y1+X1-Y2+X2 每月库存容量最多为5000，三月末为2000 ： 一月： －Y1+X1 ≤ 5000 二月： －Y1+X1-Y2+X2 ≤ 5000 三月： 1000－Y1+X1-Y2+X2-Y3+X2 = 2000

32 练习题1：建立线性规划模型 每月进货的资金应小于拥有的资金和卖出商品的收入之和：（先卖再买）
一月：2.85 X1 ≤ Y1 二月：3.05 X2 ≤ Y1 -2.85X1+3.25Y2 三月：2.90 X3 ≤ Y1 -3.05X2+2.95Y3 X1,X2,X3,Y1,Y2,Y3非负整数

33 练习题2：建立线性规划模型

34 练习题2：建立线性规划模型 决策变量确定：（是否投资需要决策） 约束条件确定： X11，X12，X21，X31 均为0－1变量
第一种产品的方案一和方案二最多只能选一： X11+X12 ≤ 1 第二种产品、第三种产品可选也可不选： X21 ≤ 1 ， X31 ≤ 1 全部投资额应不超过550万 300X11+280X12+260X21+240X31 ≤ 550 第一种产品 方案1 方案2 X X12 第二种产品 X21 第三种产品 X31

35 练习题2：建立线性规划模型 目标函数确定：每年的收益和最大 每年的总收益包含两部分： 第一部分：项目投资收益，利用投资回收系数
第二部分：剩余资金的普通投资收益

36 练习题3： 结果：张－化学（76） 王－物理（77） 李－数学（90） 赵－语文（93）
有张、王、李、赵4位教师被分配教语文、数学、物理、化学4门课程，每位教师教一门课程，每门课程由一位老师教。根据这四位教师以往教课的情况，他们分别教这四门课程的平均成绩如下表： 四位教师每人只能教一门课，每一门课只能由一个教师来教。要确定哪一位教师上哪一门课，使四门课的平均成绩之和为最高。 结果：张－化学（76） 王－物理（77） 李－数学（90） 赵－语文（93）

37 指派问题线性规划模型举例 设xij（i=1, 2, 3, 4；j=1, 2, 3, 4）为第i个教师是否教第j门课，xij只能取值0或1，这个指派问题的线性规划模型为： max z= 92x11+68x12+85x13+76x14+82x21 +91x22+77x23+63x24+83x31+90x32+74x33 +65x34+93x41+61x42+83x43+75x44 s.t. x11+x12+x13+x14=1 （1） x21+x22+x23+x24=1 （2） x31+x32+x33+x34=1 （3） x41+x42+x43+x44=1 （4） x11+x21+x31+x41=1 （5） x12+x22+x32+x42=1 （6） x13+x23+x33+x43=1 （7） x14+x24+x34+x44=1 （8） xij=0, （x14=1，x23=1，x32=1，x41=1，max z=336 ）

38 第四章 线性规划的扩展 运输问题 从产地到销地之间运送货物的最佳路径。 多个产地和多个销地；
第四章 线性规划的扩展 运输问题 从产地到销地之间运送货物的最佳路径。 多个产地和多个销地； 每个产地的产量不同，每个销地的销量也不同； 各产销两地之间的运价不同。 如何组织调运，才能既满足各销地的要求，又使总的运输费用（或里程、时间等）最小。

39 第四章 线性规划的扩展 设有同一种货物从m个出发地1，2，…，m运往n个到达地1，2，…，n。第i个出发地的供应量（Supply）为si（si≥0）， 第j个到达地的需求量（Demand）为 dj（dj≥0）。 每单位货物从产地 i 运到销地 j 的运价为Cij。求一个使总运费最小的运输方案。 … n 供应 c c1n s1 c 成本 c2n s2 … cij … … m cm cmn sm 需求 d dn ∑ 出 发 地 到达地

40 第四章 线性规划的扩展 产销平衡的运输问题模型 令Xij为 从i地运到j地的数量 MIN Z = （Cij≥0)
第四章 线性规划的扩展 产销平衡的运输问题模型 令Xij为 从i地运到j地的数量 MIN Z = （Cij≥0) （i= 1,2,…,m) 供应约束 (j= 1,2,…,n) 需求约束 Xij≥0 由 Cij、Si、dj 组成的 (m+1)×(n+1) 矩阵称为运输矩阵

41 第四章 线性规划的扩展 目标规划及有概念关数学模型 偏差： 实际决策值与目标值之间的差异 正偏差：决策值超过目标值的部分
第四章 线性规划的扩展 目标规划及有概念关数学模型 偏差： 实际决策值与目标值之间的差异 正偏差：决策值超过目标值的部分 负偏差：决策值低于目标值的部分 记正偏差量 d+，负偏差量d- ， 则有： d+× d- ＝0 绝对约束：严格满足的等式或不等式约束 目标约束：把约束右端项看成是要追求的目标值， 在达到此目标时允许有正负偏差，线性规划问题的目标函数，在给定目标值和加入正、负偏差后可变换为目标约束，也可将绝对约束变换为目标约束。

42 第四章 线性规划的扩展 优先等级与权系数：要达到的多个目标之间有主次、轻重缓急之分，因此各目标之间有优先等级。凡第一位要达到的目标赋予等级系数P1,次位的赋予等级系数P2，以此类推；并规定Pk>>Pk+1, Pk比Pk+1更大的优先权。相同等级的以不同的权系数ω加以区别。 目标规划的目标函数： 目标规划的目标函数是按各目标约束的正、负偏差变量和赋予相应的优先因子而构造的。当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值，因此目标规划的目标函数只能是 MIN Z = f（d+,d- )。 要求恰好达到目标值（正负偏差都要尽可能地小），这时 MIN Z = f（d+ ＋ d- ) 要求不超过目标值（允许达不到，正偏差要尽可能地小） MIN Z = f（d+ ) 要求不低于目标值： MIN Z = f（d- )

43 第四章 线性规划的扩展 练习：建立目标规划模型 某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定：
第四章 线性规划的扩展 练习：建立目标规划模型 某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定： 不超过年工资总额60000元； 每级的人数不超过定编规定的人数； II，III级的升级面尽可能达到现有人数的20％； III级不足编制的人数可录用新职工，又I级的职工中有10％ 要退休。 有关资料汇总于下表中，问该领导应如何拟定一个满意的方案。 等级 工资额（元/年） 现有人数 编制人数 I II III 2000 1500 1000 10 12 15 合计 37 42

44 目标规划求解： 设X1,X2,X3分别表示提升到I,II级和录用到III级的人数。 优先因子P1:不超年工资总额60000元
优先因子P3:II,III级升级面尽可能达到… 建立目标约束： 2000(10－10×0.1＋X1)+1500(12-X1+X2)+1000(15-X2+X3)+d1－－d1+=60000

45 目标规划求解： 每级人数不超过定编人数： I级有：10(1-0.1)+X1+d2--d2+=12
II级有：12-X1+X2+d3- -d3+=15 III级有：15-X2+X3+d4- -d4+=15 II,III级升级面不大于现有人数的20％，但尽可能多提； 对II级有：X1+d5- -d5+=12×0.2 对III级有：X2+d6- -d6+=15×0.2 目标函数： MIN Z=P1 d1++P2(d2++ d3+ + d4+ )+P3(d5- +d6- )

46 第四章 线性规划的扩展 动态规划 动态规划解决多阶段决策问题 将过程按时间、空间等标志分为若干个阶段； 每一个阶段都需要作出决策；
第四章 线性规划的扩展 动态规划 动态规划解决多阶段决策问题 将过程按时间、空间等标志分为若干个阶段； 每一个阶段都需要作出决策； 阶段决策依赖于当前状态，又影响以后发展。 动态规划没有标准模型，没有唯一确定的解法 决策1 决策2 决策3 决策n 状态n 状态1 状态2 状态3 状态4 1 2 3 n 阶段1 阶段2 阶段3 阶段n

47 第四章 线性规划的扩展 动态规划的基本概念： 阶段k：表示决策顺序的离散量，阶段可按时间或空间划分。
第四章 线性规划的扩展 动态规划的基本概念： 阶段k：表示决策顺序的离散量，阶段可按时间或空间划分。 状态Sk：能确定地表示决策过程当前特征的量。状态可以是数量也可以是字符，数量状态可以是连续的也可以是离散的。 状态变量Xk：表示每一状态可以取不同值的变量。 决策dk：从某一状态向下一状态过渡时所做的选择。决策是所在状态变量的函数，记为dk(Xk)。 决策允许集合Dk(xk)：在状态Xk下，允许采取决策的全体。 状态转移方程Xk+1=T(Xk,dk)：某一状态以及该状态下的决策，与下一状态之间的函数关系。

48 第四章 线性规划的扩展 最优化原理 最佳路径中任一状态（中间点）到最终状态（最终点）的路径也是该状态到最终状态一切可能中的最短路径。 A
第四章 线性规划的扩展 最优化原理 最佳路径中任一状态（中间点）到最终状态（最终点）的路径也是该状态到最终状态一切可能中的最短路径。 A Bi Cj Dt E 阶段1 阶段2 阶段3 阶段4

49 第四章 线性规划的扩展 动态规划的方法（教材P92） 将完整的问题划分成若干个阶段； 明确最终要达到的目的；
第四章 线性规划的扩展 动态规划的方法（教材P92） 将完整的问题划分成若干个阶段； 明确最终要达到的目的； 从最终结果倒推，逐个阶段地作出决策； 回到出发点，作出最后一个决策，再向前推可得到每一阶段的最优决策。

50 动态规划练习

51 第四章 线性规划的扩展 0.48 0.80 剩余人数 0.60 S2=0 S3=0 0.80 0.15 0.40 0.30 0.50 0.06 S2=1 S3=1 0.50 S4=0 S1=2 0.60 0.20 0.20 0.40 0.30 0.40 0.16 0.30 S2=2 S3=2 0.60 第一组 第二组 第三组

52 第五章 时序和路径规划 工作的时序规划 时序＝顺序＋时间 时序规划 多项任务等待同一人或物处理，每项任务的单独完成的时间确定，且没有先后关系（紧前、紧后）。怎样安排各项任务的顺序，使总效率最高？ 系统时间＝加工时间＋排队时间

53 第五章 时序和路径规划 工作的时序规划 平均排队（等待）时间最短问题 加工时间最短者优先 （相同时间的可任意安排） 平均延误时间最短问题
第五章 时序和路径规划 工作的时序规划 平均排队（等待）时间最短问题 加工时间最短者优先 （相同时间的可任意安排） 平均延误时间最短问题 最先到期的工作优先

54 第五章 时序和路径规划 延误的工作项数最少 先按先到期者优先的原则排初次次序 如果没有延误的工作，则是最优解。
第五章 时序和路径规划 延误的工作项数最少 先按先到期者优先的原则排初次次序 如果没有延误的工作，则是最优解。 如果有延误的工作，则找出其中的一项，找出到此项工作之前（包括该项）加工时间最长的一项，并将之抽去，重新安排时间，如果已没有延误的工作，则将被抽取的这一项放置最后；如仍有被延误的工作，则再重复这一步。

55 第五章 时序和路径规划 时序规划扩展（约翰逊原则）： 两台顺序机器完成一批工作
第五章 时序和路径规划 时序规划扩展（约翰逊原则）： 两台顺序机器完成一批工作 每项工作在机器1和机器2上的加工时间不一样，如何使系统效率最高？ 4 3 2 1 机器1 机器2 工作

56 第五章 时序和路径规划 约翰逊原则 例5－3：教材P110 实例5.6 找出各台机器上加工时间最短的一项工作，
第五章 时序和路径规划 约翰逊原则 找出各台机器上加工时间最短的一项工作， 如果在机器1上，这项工作最先做； 如果在机器2上，这项工作最后做； 不断重复，从两端往内排。相同时间可任选一 个，一般先安排机器1上工作。 例5－3：教材P110 实例5.6

57 第五章 时序和路径规划 最小树 一个网络中有很多树，其中边的长度（权数）之和为最小的树为最小树。 最小树的获取－－破圈法
第五章 时序和路径规划 最小树 一个网络中有很多树，其中边的长度（权数）之和为最小的树为最小树。 最小树的获取－－破圈法 从图中任取一个圈，去掉该圈的一条最大边，将此圈破去，然后重复破圈，直至无圈为止。

58 第五章 时序和路径规划 通过一个网络的最短路径 问题 求解
第五章 时序和路径规划 通过一个网络的最短路径 问题 在一个网络中，给定一个始点Vs，和一个终点Vt，求Vs 到Vt的一条路，使路长最短。 求解 能划分阶段的，可采用动态规划方法。 不能分阶段的，采用狄克斯屈方法。

59 第五章 时序和路径规划 狄克斯屈方法 开始节点标永久标记[0,S],其余临时[T,-]
第五章 时序和路径规划 狄克斯屈方法 开始节点标永久标记[0,S],其余临时[T,-] 找出与开始节点相邻的所有节点，为每一个设标记[L,1]，其中L值最小的节点标记右上角标上*，使之成为永久标志。 从新的永久标志开始，找出从此节点出发可到达的所有节点，计算这些节点的最短距离（现有距离和经新的永久标志到达的距离的小的一个值），保持、新设或更改这些节点的标志为 [最短距离，最短路径上前一节点标号]，比较图中所有没有*的标记（临时性标记），找出距离最短的一个节点，使之成为永久性标记。重复这一步，直到所有的节点都成为永久性标志为止。

60 第五章 时序和路径规划 狄克斯屈方法 k [Dj,k] j [Di,m] i Lij 从i-j时：
第五章 时序和路径规划 狄克斯屈方法 k [Dj,k] j [Di,m] i Lij 从i-j时： 如果Di+Lij>Dj,则不改变j的标记； 如果Di+Lij<Dj，则改为[Di+Lij,i]

61 练习题 某地7个村镇之间现有交通距离如图 求：1)从村1到其余各村的最短距离？
2)如要沿路架设电话线，如何使总长度最小同时又使每个村都能安装上电话？ 4 26 7 12 10 24 10 5 7 1 2 11 16 15 25 12 15 6 3 17

62 最小树：破圈法 4 26 7 12 10 24 10 5 7 1 2 11 16 15 25 12 15 6 3 17

63 第五章 时序和路径规划 通过一个网络的最大流量 最大流量问题 最大流量求解（“分步流动”的思路）
第五章 时序和路径规划 通过一个网络的最大流量 最大流量问题 在一定条件下，使网络系统中从开始点到结束点之间的某种物资流的流量达到最大的问题。限制条件是每一条边的最大通过能力（流量）不等。但有多条路 最大流量求解（“分步流动”的思路） 福特－富尔克逊标号法

64 第五章 时序和路径规划 福特－富尔克逊标号法： 标记：[流入节点的流量，该流量的来源节点]，第一个节点标记[∞，S]。
第五章 时序和路径规划 福特－富尔克逊标号法： 标记：[流入节点的流量，该流量的来源节点]，第一个节点标记[∞，S]。 选取已有标记的一个节点，找出从此节点能直接到达的一个节点，确定到达节点的最大流量，相应地标上标记。重复这一步，尽快到达终点，得到一条从起点到终点的路径，此路径的最大流量为流入终点的流量。将此路径上的每一边的流动能力减去此流量。再从起始节点开始，按新的流动能力，重新进行标号，找出新的一条途径和流量，重复进行下去，直到把所有可能的路径全部找到为止，全部路径的流量和即为通过该网络的最大流量。

65 第五章 时序和路径规划 福特－富尔克逊标号法： [Fi,K] [Fj,i] i j mij Fj=min(Fi,mij)

66 第七章 决策分析 风险决策 存在几种自然状态，哪一种状态发生不确定，但每种自然状态发生的可能性可以预计（主观概率值）。
第七章 决策分析 风险决策 存在几种自然状态，哪一种状态发生不确定，但每种自然状态发生的可能性可以预计（主观概率值）。 决策依据：最大期望收益、最小期望损失标准 期望值：不同自然状态下可能得到的值 期望值＝∑（概率×结果值） 决策方法：最大期望计算、条件概率、决策树、效用曲线分析

67 第七章 决策分析 最大期望收益值计算 i为备择方案，i=1,2,…,n j为自然状态，j=1,2,…,m 为为第i个备择方案的期望收益值
第七章 决策分析 最大期望收益值计算 i为备择方案，i=1,2,…,n j为自然状态，j=1,2,…,m 为为第i个备择方案的期望收益值 pj为第j个自然状态出现的概率 Oij为第i个备择方案在第j个自然状态下的收益 Vi0 为第i个备择方案的初始投资值

68 第七章 决策分析 风险的衡量 当备择方案的期望收益值相等时，需计算风险值。风险应尽可能地小。 为第i个备择方案的风险

69 第七章 决策分析 决策树结构 收益 概率值 状态 节点 收益 概率值 决策 节点 概率值 收益 状态 节点 概率值 收益 方案枝 概率枝

70 第七章 决策分析 利用决策树决策 决策树求解多阶段决策问题 绘出决策树 预计各状态概率 从右向左计算各个方案的收益期望
第七章 决策分析 利用决策树决策 绘出决策树 预计各状态概率 从右向左计算各个方案的收益期望 根据期望值大小选择方案 决策树求解多阶段决策问题

71 练习题 某厂工艺改进有两条途径： I：自行研究，成功可能性0.6； II:国外引进，谈判成功可能性是0.8。
不论何种途径成功，生产规模都考虑两种方案：产量不变和增加产量。 如果都失败，则仍采用原工艺进行生产，产量也保持不变。 据市场预测，今后5年内这种产品跌价的可能性是0.1，保持中等价的可能性是0.5，涨价的可能性是0.4。

72 各状态下的收益值如下： 试用决策树进行决策。 按原工艺生产 引进技术成功 自行研究成功 产不 变量 增加 产量 价格低0.1 价格中0.5 价格高0.4 －100 100 －200 50 150 －300 250 200 －250 600

73 决策树练习答案： II I III 30 82 95 95 65 60 85 85 63 30 低价（0.1) －100 中价（0.1) 3
失败 (0.2) 高价（0.4) 100 82 95 －300 低价（0.1) 引 进 技 术 1 增加 产量 中价（0.4) 4 50 95 高价（0.4) 250 成功 (0.8) II 65 －200 低价（0.1) 中价（0.5) 5 产量 不变 50 高价（0.4) I 150 60 －300 低价（0.1) 增加 产量 中价（0.5) 6 －250 85 高价（0.4) 600 自 行 研 究 III －200 低价（0.1) 成功 (0.6) 85 中价（0.5) 63 7 产量 不变 2 高价（0.4) 200 低价（0.1) 30 －100 失败 (0.4) 中价（0.5) 8 高价（0.4) 100

74 第七章 决策分析 贝叶斯决策 自然状态出现的概率估计的正确程度直接影响到决策中收益期望值。在条件许可的情况下，往往需要补充新信息。获得补充信息需支付一定的费用。根据获得的新信息修正原先对自然状态出现的概率的估计值，并利用修正的概率重新进行决策。修正概率主要利用贝叶斯定理。

75 第七章 决策分析 贝叶斯决策过程 先验分析 预验分析 后验分析 根据资料及经验对各自然状态出现的概率作出估 计，称为先验概率；
第七章 决策分析 贝叶斯决策过程 先验分析 根据资料及经验对各自然状态出现的概率作出估 计，称为先验概率； 根据先验概率可作出决策，得到最优期望值，记为 EMV*。 预验分析 补充信息的成本－收益分析 后验分析 获取条件概率，运用贝叶斯定理对先验概率进行修正，得到后验概率； 根据后验概率作出决策，计算补充信息的价值。

76 第七章 决策分析 预验分析 信息的价值在于它能提高决策的最大期望值。但获取信息的费用超过它所能提高的期望收益就不合算了。
第七章 决策分析 预验分析 信息的价值在于它能提高决策的最大期望值。但获取信息的费用超过它所能提高的期望收益就不合算了。 所有信息中最好、最理想的信息自然是完全可靠、准确的信息，这种信息预报某自然状态出现，则在实际中必定出现这自然状态，这种信息称为完备信息。 补充信息费用应远小于完备信息的价值（上限）。 当完全信息预报出现第K个自然状态出现时，最优方案由 MAX{Ukj}j 确定。 在完备信息下，决策所能获得的最大期望收益值： ERPI与EMV*之间的差额就是得到完全信息而使期望值增加的部分，即为完备信息价值EVPI。

77 第七章 决策分析 后验分析 补充新信息，通过对X1,X2,…,XS共S个状态的调查，获得实际出现自然状态θi而预报Xj的概率，即：P(Xj|θi)。 在已知先验概率P(θj)(j=1,2,…,m)及条件概率P(Xj|θi)(j=1,2,…,s;i=1,2,…,m)的基础上，利用贝叶斯定理计算修正概率，即后验概率： 根据后验概率，计算各方案的期望收益值，并依据期望收益值，重新作出决策(最大期望收益)。 计算获得补充信息后，最大期望收益的实际增量。

78 第七章 决策分析 后验分析计算的表格形式 I 先验状态概率 P(θj) II 条件概率 P(Xi|θj)
第七章 决策分析 后验分析计算的表格形式 I 先验状态概率 P(θj) II 条件概率 P(Xi|θj) III P(θj) P(Xi|θj) X1, … , Xi, … , XS X1, … , Xi, … , XS θ1 : P(θ1) …, P(Xi|θ1),... …, P(θ1) P(Xi|θ1), ... θ2 : P(θ2) …, P(Xi|θ2), … …, P(θ2) P(Xi|θ2), ... …… … … θm : P(θm) …, P(Xi|θm), … …, P(θm) P(Xi|θm), ... 对第III部分的每一列求和 P(X1), …, P(Xi) , …, P(Xm) 后验概率: θ1 P(θ1|X1), …, P(θ1|Xi),… P(θj|Xi)= θ2 P(θj) P(Xi|θj)/ P(Xi) θm P(θ2|X1), …, P(θ2|Xi),… P(θm|X1), …, P(θm|Xi),…

79 风险型决策 贝叶斯决策练习： 假定天气是影响某工程项目能否按期完工的决定因素，如果天气好，工程能按期完工，施工单位能获利5万元；如果天气不好，不能按期完工，则要罚款1万元；但如不施工则要损失人工费0.2万元。根据过去的经验，在计划期内天气好的可能性为30％。为更好地掌握天气情况，可请气象部门作进一步的预报，需支付信息费0.08万元。从所提供的预报信息可知，气象部门对好天气的预测准确性为80％，对坏天气的预报准确性为90％。问该如何进行决策？

80 贝叶斯决策作业 好天气θ1（0.3) 坏天气θ2（0.7) EMV 先验分析： 施工 5 －1 0.8 不施工 －0.2 －0.2 －0.2
施工 － 不施工 － － －0.2 EMV* = 0.8 施工有利，期望收益0.8万元 预验分析： 完备信息最大期望收益 ERPI=0.3*5＋0.7*(-0.2) =1.36 (万元） 完备信息价值 EVPI= = 0.56 (万元) EVPI远大于收集信息成本(0.08),初步认为合算。

81 贝叶斯决策作业 后验分析： 气象中心提供预报两种天气状态：好(X1),坏(X2) (补充信息的自然状态与原自然状态一致) 补充信息概率
好天气预报准确性为80％，坏天气预报准确性为90％ P(X1| θ1)= 实际是好天气预报也是好天气 P(X2| θ1)= 实际是好天气预报且是坏天气 P(X1| θ2)= 实际是坏天气预报且是好天气 P(X2| θ2)= 实际是坏天气预报也是坏天气

82 贝叶斯决策作业 后验分析概率计算的表格形式： 后验决策： 施工 5 －1 3.62* 不施工 －0.2 －0.2 －0.2
预报天气好（X1），每个方案的最大期望收益EMV 好天气θ1|X1（0.77) 坏天气θ2|X1（0.23) EMV 施工 － * 不施工 － － －0.2 I 先验状态概率 P(θj) II 条件概率 P(Xi|θj) III P(θj) P(Xi|θj) 好天气 X1, 坏天气 X2 X1, X2 好天气θ1 : 0.3 坏天气θ2 : 0.7 全概率P(Xi): 对第III部分每一列求和 后验概率P(θj|Xi) : θ1 P(θj) P(Xi|θj)/ P(Xi) θ2

83 贝叶斯决策作业 后验决策： 施工 5 －1 －0.46 补充信息价值： 后验决策结果： 预报好天气时施工，预报坏天气时不施工。
预报天气坏（X2），每个方案的最大期望收益EMV 好天气θ1|X2（0.09) 坏天气θ2|X2（0.91) EMV 施工 － －0.46 不施工 － － －0.2* 补充信息价值： 后验决策最大期望收益EMV*=0.31× ×(－0.2)=0.9842 补充信息价值：补充信息带来期望收益增量＝ =0.1842 补充信息价值大于预报信息成本（0.08)，因此的确是合算的。 后验决策结果： 预报好天气时施工，预报坏天气时不施工。

84 贝叶斯决策的决策树 天气好 0.3 5 0.8 施工 4 0.8 -1 天气差 0.7 2 -0.2 不预报 不施工 -0.2 5 0.98
天气好 0.77 5 3.62 1 施工 8 3.62 -1 天气差 0.23 6 -0.2 预报好0.31 -0.2 预报 不施工 9 0.98 天气好 0.09 5 3 -0.46 10 施工 -0.2 -1 天气差 0.91 预报差0.69 7 -0.2 11 -0.2 不施工

85 第七章 决策分析 不确定型决策 两类不确定型决策（按不确定程度区分） 两类问题的决策方法 自然条件未知（I类）
第七章 决策分析 不确定型决策 两类不确定型决策（按不确定程度区分） 自然条件未知（I类） 已知自然条件，但不知发生的概率（II类） 两类问题的决策方法 I类：定性方法 II类：选用一定的决策准则进行决策

86 第七章 决策分析 决策准则 乐观准则（准则）：大中取大、 max max 悲观准则（WALD）小中取大max min
第七章 决策分析 决策准则 乐观准则（准则）：大中取大、 max max 不放弃任何获取最大收益的机会 悲观准则（WALD）小中取大max min 假定最差的结果出现，再求得最大收益的机会 折衷主义准则（乐观系数α，悲观系数 1－α） 既不乐观也不悲观，介于两者之间，0≤α≤ 1 等可能性准则（LAPLACE准则） 假定每一种自然状态出现的可能性相同 最小机会损失准则（后悔值准则、SAVAGE准则） 后悔值：最好的可能结果与实际结果之间的差。min max 源于悲观的假设（最大后悔情况出现），再要求最小后悔方案

87 第八章 项目管理 绘制网络图的准备工作 确定目标：以时间要求还是资源费用要求为主 工程分解：列出全部分解后的工序及代号清单
第八章 项目管理 绘制网络图的准备工作 确定目标：以时间要求还是资源费用要求为主 工程分解：列出全部分解后的工序及代号清单 工序关系：确定每一道工序的紧前工序是哪些 工序时间：确定每一道工序的完成所需的时间 一时估计法：仅估计一个完成工序的最大时间D 三时估计法：乐观时间 a、悲观时间b、最可能时间m

88 第八章 项目管理 网络图绘制规则 方向、时序与结点编号
第八章 项目管理 网络图绘制规则 方向、时序与结点编号 网络图是有向图，按流程的顺序，规定工序从左向右排列。网络图中的各个结点都有一个时间（某一个或若干个工序开始或结束时间），一般按结点的时间顺序编号（从左到右，从上到下），箭尾结点编号应小于箭头结点编号。始结点编号为1。 网络图中不能出现缺口和回路 二个结点之间只能有一个工序 两条箭线不能有同样的始末结点，若二个事项之间有几个平行进行的工序，不许直接连接，而需要引入虚工序。

89 第八章 项目管理 网络图绘制规则 平行作业 有几个工序平行作业结束后转入下一个工序的情况下，考虑到计算网络时间的方便，选择在平行作业的几个工序中所需时间最长的一个工序，直接与其紧后工序衔接，而其它工序则通过虚工序与其紧后工序衔接。 交叉作业 对需要较长时间才能完成的一些工序，在工艺流程与生产组织条件允许的情况下，可以不必等待工序全部结束后再转入其紧后工序，而是分期分批的转入。分批转入时需增加虚工序。

90 第八章 项目管理 网络图绘制规则 始点和终点 为表示工程的开始和结束，在网络图中只能有一个始点和一个终点。当工程开始时有几个平行工序或结束时有几个平行工序，而又不能用一个始结点或一个终结点表示时，需用虚工序把它们与始结点或终结点连接。 网络图布局 尽可能将关键线路布置在中心位置，尽量将联系紧密的工作布置在相近的位置；尽量用水平线或具有一段水平线的折线。

91 第八章 项目管理 时间参数计算的符号约定 i j K E(i) L(i) E(j) L(j) D(i,j) S(i) S(j) ESij
第八章 项目管理 时间参数计算的符号约定 i j K E(i) L(i) E(j) L(j) D(i,j) S(i) S(j) ESij LSij E(j) E(1)=0 L(j) EFij LFij

92 第八章 项目管理 结点（事项）时间 结点本身不占用时间，它只表示某项工作应在某一时刻开始或结束，因此，结点参数主要只有两个：最早实现时间（最早时间）和最迟实现时间（最迟时间）。 最早时间：以该结点结束的工作最早可能结束的时间，或以该结点开始的工作最早可能开始的时间。E(1)=0,计算时从左往右算。 最迟时间：允许所有后续工序都能及时开始的最晚时间。L(n)=E(n),计算时需从右往左算。

93 第八章 项目管理 结点（事项）时间计算 结点最早时间E(j)的计算 E(1)=0
第八章 项目管理 结点（事项）时间计算 结点最早时间E(j)的计算 E(1)=0 E(j)=max[E(i)+D(i,j)], j=2,3,4,…… E(7)=5 7 E(9)=MAX[E(7)+6,E(8)+7)] =13 6 9 E(8)=6 7 8

94 第八章 项目管理 结点（事项）时间计算 结点最迟时间L(i)的计算 L(n)=E(n)
第八章 项目管理 结点（事项）时间计算 结点最迟时间L(i)的计算 L(n)=E(n) L(i)=MIN[L(j)-D(i,j)], i=n-1,n-2,…… L(10)=70 L(9)=MIM[L(10)-20, L(11)-12)] =50 10 20 9 L(11)=89 12 11

95 第八章 项目管理 工序时间参数计算 一个工序可以从箭尾结点的最早时间开始作业，也可以适当推迟开始，但须在箭头结点的最迟时间内完工才不至于延误后续工序，因此工序时间就包括最早开始时间和最迟开始时间，加上或减去该工序的作业时间，相应地还有最早结束时间和最迟结束时间。 最早开始时间: ESij=E(i) 最早结束时间：EFij=ESij+D(i,j) 最迟结束时间：LFij=L(j) 最迟开始时间：LSij=LFij-D(i,j)

96 第八章 项目管理 时差及计算 结点时差：最迟与最早时间差 S(i)=L(i)－E(i)
第八章 项目管理 时差及计算 结点时差：最迟与最早时间差 S(i)=L(i)－E(i) 工序总时差：不影响工期(最早结束时间）的该工序可松动的时间（可以推迟开始的时间）. Sij = LSij － ESij = LFij － EFij = L(j) － E(i) － D(i,j) 工序单时差：不影响紧后工序最早可能开始条件下，工序最早可能完工时间可以推迟的时间. Rij = E(j) － EFij

97 第八章 项目管理 关键线路 关键线路的长度决定了工程周期，关键线路可以有多条，计划安排得越紧凑，关键线路越多。 关键线路的确定
第八章 项目管理 关键线路 关键线路的长度决定了工程周期，关键线路可以有多条，计划安排得越紧凑，关键线路越多。 关键线路的确定 破圈法：在圈中去掉最短的一个工序。 图上作业法：标注结点时间，结点时差为0的结点组成关键线路。 表上作业法：计算工序时间，总时差为0的工序组成关键线路。

98 第八章 项目管理 图上标注法 1 5 3 8 7 6 4 2 A H E L K G D F C B 60 45 18 10 20 40
第八章 项目管理 图上标注法 1 5 3 8 7 6 4 2 A H E L K G D F C B 60 45 18 10 20 40 15 30 25 35 117 70 60 135 170 60 135 170 80 110 80 110 120 100

99 第八章 项目管理 缩短工程工期问题 保证质量和不增加人力物力的前提下尽量缩短工期。注意关键线路的变化。 压缩关键工序的工序时间
第八章 项目管理 缩短工程工期问题 保证质量和不增加人力物力的前提下尽量缩短工期。注意关键线路的变化。 压缩关键工序的工序时间 在关键工序上采取改进技术、工艺和设备等措施，尽先保证关键工序所需，矛盾时非关键线路应尽可能让路。 在非关键工序上尽量挖掘潜力 利用非关键线路上的时差进行合理调度，抽调资源支援关键线路。 采用平行或交叉作业

100 第八章 项目管理 费用与完工时间的关系 工 程 费 用 总费用 直接费用 间接费用 极限时间 T’ 正常时间

101 第八章 项目管理 时间-费用优化分析方法： 最低成本日程：费用最低的工程完工时间T’ 直接费用变动率：缩短单位时间增加的直接费用
第八章 项目管理 时间-费用优化分析方法： 最低成本日程：费用最低的工程完工时间T’ 直接费用变动率：缩短单位时间增加的直接费用 T’计算程序（请参考教材P315) 按正常时间画出网络图，找到关键线路计算成本时间 在关键线路上找出g最小的工序，压缩活动时间 重复上一步，直到总费用上升为止

102 第八章 项目管理 时间－资源优化 尽量合理地利用现有资源，并缩短周期 时间－资源优化方法 优先安排关键工序所需要的资源；
第八章 项目管理 时间－资源优化 尽量合理地利用现有资源，并缩短周期 时间－资源优化方法 优先安排关键工序所需要的资源； 利用非关键工序的总时差，错开工序开工时间，拉平资源需要量的高峰； 在确实受到资源限制，或者在综合考虑经济效益的条件下，也可适当地推迟完工时间

103 练习：画网络图并调整时间

104 关键线路：1－5－4－6－7 或 B－X－G－H ， 长度：15天
练习：画网络图并调整时间 11 12 3 Y 4 5 F 12 12 7 E 2 6 D 5 G H A 4 3 4 15 15 3 4 8 8 1 7 X B C 8 6 5 8 8 关键线路：1－5－4－6－7 或 B－X－G－H ， 长度：15天

105 练习：画网络图并调整时间 正常进度完工费用=直接费用＋间接费用 153＋15(天)×5(百元/天)=228 百元
153＋15(天)×5(百元/天)=228 百元 关键线路 B,G,H中g最小的是G(g=3)，缩短G一天（为什么只缩短一天？）的工程费用变为（间接费用减少）： 228＋1×3－1×5＝226 调整后有三条关键线路，并且所有节点的时差均为0，因此已无法再压缩工程时间。 1－5－4－6－7；1－2－3－6－7；1－5－7

106 第九章 库存控制 库存问题基本概念 需求：生产消费需求，从存储系统中减少 供应量Q：从供应商或生产中补充到存储系统
第九章 库存控制 库存问题基本概念 需求：生产消费需求，从存储系统中减少 需求量D: 单位时间的需求（需求率） 连续输出与间断输出 均匀输出与非均匀输出 确定输出与随机输出 供应量Q：从供应商或生产中补充到存储系统 提前时间：提前备货（订货）的时间 拖后时间：订货推迟时间 经济批量：成本最低时每次订货量Q0

107 第九章 库存控制 成本C： 目标函数：单位时间平均成本或费用总和最小 持有成本HC：每存储单位物质单位时间存储费用
第九章 库存控制 成本C： 持有成本HC：每存储单位物质单位时间存储费用 订货成本RC：每订一次货的订货费用，与量无关 购置成本BC：购买商品的单价 缺货成本AC : 不允许缺货时，缺货损失费无限大 目标函数：单位时间平均成本或费用总和最小 变量是单位时间内订货次数和每一次的订货量 各类成本和需求的单位时间必须保持一致 价格不变时购置成本对最优解没有影响 不允许缺货时，缺货损失费也可不考虑

108 第九章 库存模型 模型一：不允许缺货、瞬时到货模型 基本假设： 用户的需求是连续均匀的，需求率D为常数； 当存储降至0时，可以立即得到补充
第九章 库存模型 模型一：不允许缺货、瞬时到货模型 基本假设： 用户的需求是连续均匀的，需求率D为常数； 当存储降至0时，可以立即得到补充 缺货损失费为无穷大，不允许缺货 每次订货量不变，记为Q，订货成本RC不变 单位存储费不变，即HC为常数。 存储量 Q Q/2 t T 2T 3T 4T

109 EOQ: Economic ordering quantity
确定性存储模型（一） 不允许缺货模型 D :年需求量（消耗速度） RC:每次订货成本 HC:单位年存储费用 平均存货水平＝ Q/2 使总平均费用最小的 一年内次数N0=D/Q0 订货周期T0=Q0/D Q 斜率-D Q/2 T EOQ: Economic ordering quantity

110 第九章 库存模型 模型一：不允许缺货，生产时间很短 S:最大库存 Q 斜率-D Q/2 T

111 第九章 库存模型 模型二：不允许缺货，生产需要一定时间 T S 斜率-D 斜率P-D t S/2 Q

112 第九章 库存模型 模型三：允许缺货，生产时间很短 S 存储量 T t Q-S Q t2 t1 －D S/2 t2×D/2

113 第九章 库存模型 模型四求解结果： 存储量 S t3 T t Q t2 t1 －D P-D

114 第九章 库存模型 模型五：需求为随机的单一周期存储模型 模型假设： 需求服从一定的分布；
第九章 库存模型 模型五：需求为随机的单一周期存储模型 模型假设： 需求服从一定的分布； 单一周期存储只考虑一个周期，到周期结束时存储应为0，通常采用降价处理方式。 报童问题： 报童每天售报数量是一个随机变量。每售出一份赚k元。如果报纸未能售出，每份赔h元。每日售出报纸r份的概率P(r) 可根据以往经验得到，问报童每天应准备多少份报纸?

115 第九章 库存模型 设报童每天订报q份，从损失角度考虑： 供大于求时（r ≤q）, 实际损失期望值为：
第九章 库存模型 设报童每天订报q份，从损失角度考虑： 供大于求时（r ≤q）, 实际损失期望值为： 供不应求时（r >q）, 机会损失期望值为： 总的损失期望值为：

116 第九章 库存模型 对EC (q)求最小值： 设Q为最佳值并且通常为整数，则必有: 1） EC(Q)≤EC(Q+1)
第九章 库存模型 对EC (q)求最小值： 设Q为最佳值并且通常为整数，则必有: 1） EC(Q)≤EC(Q+1) 2） EC(Q)≤EC(Q－1) 可得到最优数量Q应满足:

117 第九章 库存模型 离散型概率分布时有： 上式等价于： 连续型概率分布时有：

118 感谢大家的参与和支持！ 祝大家取得好成绩！
感谢大家的参与和支持！ 祝大家取得好成绩！