当前位置：文档之家 › 运筹学 第十章1

运筹学 第十章1

  • 格式：ppt
  • 大小：891.50 KB
  • 文档页数：37

下载文档原格式

  / 37

合集下载

运筹学 第十章

运筹学 第十章
若H=0.15，B=1，A=100，L=1/10（年）,在L这段时间内的需求量服从μ=1000，σ2=625的正态分布，年平均需要量D=10000件，求缺货补充的（s，Q）存储策略。
【解】迭代过程见下表。
数据
订货量Q(i)
不缺货的概率F(s)
(s-μ)/σ(查表）
H=
0.15
Q(1)=
3651.4837
I3*$C$9+$C$8
G=
1-H3
b(1)=
$C$9*L3+($C$8-K3)*M3
其余单元格用上一步迭代公式复制即可。
(s-μ)/σ、f((s-μ)/σ)查表得到
最优存储策略为：再订货点s＝1040，订货量Q＝3640。
11181003
某化工厂每年需要甘油100吨，订货的固定成本为100元，甘油单价为7800元/吨，每吨年保管费为32元，求：（1）最优订货批量；（2）年订货次数；（3）总成本。
s(6)=
1040.0000
0.0632
0.0546
-0.6052
SS(6)=
40.00
公式：
Q(1)=
SQRT(2*C5*C4/C3)
Q(2)=
SQRT((2*$C$4*($C$5+$C$6*N3)/$C$3))
F(1)=
1-$C$3*F3/($C$7*$C$3*F3+$C$6*$C$4)
s(1)=
0.98
0.96
0.94
答案：最佳批量为每批50000个
商店出售某商品，预计年销售量为5000件，商品的价格为k(t)=50t（单位：元）。每次订货费为100元，每件商品年保管费为50元，求最优存储策略。
【解】D=5000，C(t)=50t，A=100，H＝50，C0=50，由式（10.33）及（10.34）

运筹学课件第十章排队论

运筹学课件第十章排队论
第十章 排队论
第一节 引言
一、排队系统的特征及排队论 排队论研究排队系统的数学理论和方法， 是运筹学的一个重要分支。 排队问题表现：
到达的顾客 1、不能运转机器 2、病人 3、打电话 4、等待降落飞机 5、河水进入水库
要求的服务 修理 就诊 通话 降落 放水，调整水 位
服务机构 修理工人 医生 交换台 跑道指挥机构 水闸管理员
四、排队系统的主要数量指标和记号 描述一个排队系统运行状况的主要指标： 1、队长、排队长 队长：系统中的顾客数量（排队顾客+接受服务顾客）。
排队长：系统中的正在排队等待服务的顾客数量。
2、等待时间和逗留时间 等待时间：从顾客到达时刻起到他开始接受服务止这段时间 为等待时间。 逗留时间：从顾客到达时刻起到他接受服务完成这段时间为 逗留时间。
(i)队长有限：系统等待空间有限。 有限系统的空间为K, 顾客到达时的队长为L。若 L<K，则顾客进入队列等待服务，若L=K，则 顾客离去。 (ii) 等待时间有限： 顾客对等待时间具有不耐烦 性的系统。设最长等待时间是T0，某个顾客从 进入队列后的等待时间为 T。若T<T0，顾客继 续等待；若T=T0，则顾客脱离队列而离去。 (iii)逗留时间有限：等待时间与服务时间之和。
排队可以是人，也可以是物。 为了一致：将要求得到服务的对象统称为“顾客”，将提 供服务的服务者称为“服务员”或“服务机构”。
排队系统的一般描述; 顾客为了得到服务而到达系统，如果不能 立刻得到服务而又允许排队等待，则加入 等待队伍，待获得服务后离开系统。
顾客到达 队列 服务台 单服务台服务系统 服务完后离开

n 0
n ,n C 1 , 2 , 3 ,...... n u n p p , n 1 , 2 , 3 ,...... n 0

运筹学--第10章

运筹学--第10章
11
2.决策的分类与过程
现状调查是通过认真细致的调查 研究，充分认识问题产生的原因、 规律和解决的方法。通过发现问题 和现状调查，为决策目标的制定提 供充分的客观依据。 2.建立可行方案：这是决策过程 的第二步骤，是科学决策的基础。 这个阶段主要有轮廓设想、方案预 测和详细设计。
12
2.决策的分类与过程
表10-6
aij
决 策 表
2
¼
j
1
¼
3
¼
4
¼
Ki
E(ki)
D(ki)
决 策 方 案
K1 K2 K3 K4 K5
4 2 5 3 3
5 4 7 5 5
6 6 3 6 5
7 9 5 8 5
5.5 5.25 5 5.5 4.5
1.5
2.5
30
4.不确定型的决策问题
其中 E(k1)=(1/4)*4+(1/4)*5+(1/4)*6+(1/4)*7=5.5 E(k2)=(1/4)*2+(1/4)*4+(1/4)*6+(1/4)*9=5.25 E(k3)=(1/4)*5+(1/4)*7+(1/4)*3+(1/4)*5=5 E(k4)=(1/4)*3+(1/4)*5+(1/4)*6+(1/4)*8=5.5 E(k5)=(1/4)*3+(1/4)*5+(1/4)*5+(1/4)*5=4.5 因为E(k1)=E(k4)，所以比较D(k1)和D(k4)的大小 D(k1)=E(k1)-minaij=5.5-4=1.5
作业：
习题—1,3
36
5.风险型的决策问题
1.引 言

第10章 (运筹学) 决策论

第10章 (运筹学) 决策论

第10章 决策论
着各种事件的发生概率不清时，决策者考虑可能由于决策错 误而造成重大经济损失。由于自己的经济实力比较弱，他 在处理问题时就比较谨慎。他分析各种最坏的可能结果， 从中选择最好者，以它对应的策略为决策策略。用符号表 示为max-min决策准则。在收益矩阵中先从各策略所对应的 可能发生的“策略—事件”对的结果中选出最小值，将它 们列于表的最右列。再从此列的数值中选出最大值，以它 对应的策略为决策者应选的决策策略。 悲观决策准则又称小中取大的准则。该准则为： （1）根据收益矩阵A=[aij]，确定每一个策略可能得到最 坏结果Mi Mi=min{ai1,ai2,…,ain},i=1,2,…,m （2）选取Sk使得Mk=max{M1,M2,…,Mm}。
第10章 决策论
相应的收益和损失值。如当选择月生产量为20件时，而销出 量为10件，这时收益额为： 10×(35-30)-1×(20-10)=40（元） 可以一一计算出各“策略—事件”对应的收益值和损失值， 记为aij，将这些数据汇总在决策矩阵中，见下表：
Ej Si 策 0 10 事 20 件 30 40
第10章 决策论
或行业负责人）要进行战略性决策，中下层管理人员(如部 门经理、计划管理人员、作业调度指挥人员等)要进行战术 性决策或技术性决策。地位越高，决策在工作中的作用就 显得越重要。决策的正确与否，对经济和让会效益影响极 大，小则影响一个企业、一个部门，大则影响整个国家和 社会的发展。 正确的决策必须建立在认识和了解问题内部关系以及环境 状况的基础上。首先，必须掌握决策对象的运动规律，占 有必要的资料和信息。其次，还要掌握辅助决策的技术和 方法，遵守必要的决策程序和步骤。 1. 决策问题的构成 为了说明决策问题的构成，我们先举一个例子。某工厂生 产的产品要销往销售地，决定自己组织运输，方案有两种： 一是增购车辆，二是租车。如果租车运输，所支付的运费 就高些，如果使用自己的车辆运输，运费就便宜些，

管理运筹学10

管理运筹学10
7. 进入20世纪70年代以后，计算机技术在生产活动中的深入应用已经使生产运作管
理发生了根本性的变革。CAD、CAM、MIS、OA及生产系统中出现的FMS、GT、 CAPP等技术的应用极大的提高了生产和管理的自动化程度，提高了生产率，CIMS 技术更使得企业的经营计划、产品开发、产品设计、生产制造、生产运作、市场营 销、财务管理、采购供应等一系列活动构成一个完整的有机系统，从而更加灵活地 适应环境的变化和要求。
1
管理运筹学
生产运作的分类：
生产运作
制造性生产
工艺过 程特点
组织生 产特点
服务性生产
是否提供 顾客是否 劳动密集程度+与 有形产品 参与 顾客接触程度
离散
连续 性 生产 （流
性 生产 （加 工
备货 型 生产
订货 型 生产
纯 劳 务 生
程 装 MTS MTO 产
型） 配
型）
大专大专
一 般 劳 务 生 产
计划、独立需求库存控制，制造资源计划（MRPII），作业计划与控制，项目计划 管理等。
3. 生产运作系统的维护：主要涉及质量管理、准时生产方式与精细生产方式，其它
先进生产方式等。
说明：
1。传统的生产管理只考虑有效地控制生产系统的运行，但现代生产与运作管理已突破了传统 管理的框架，充分考虑到生产运作系统的建立对运行阶段的先天性制约与影响，已将管理的范 围延伸到生产运作系统 的设计、选择上，以便使生产运行的前提——产品的工艺可行性，生 产系统的合理性能够得到保障；同时也要考虑到市场需求，生产环境等的不断变化，以及新的 生产运作管理方式、方法、理论的不断出现，使生产运作系统不断得到改进与完善。
8. 可以预计：今后企业的生产经营综合体制进一步朝着经营与生产一体化、制造1与管

运筹学第10章

运筹学第10章

例10.7在10.2例10.1中，假定根据已往的统计资料估计每周销 售量10件,20件,30件,40件的概率分别为0.1，0.3，0.5，0.1， 试采用最大可能准则给出决策。
状态 Θ1 Θ2 0.1 0.3 50 方 K1 (10) 50 案 K (20) 0 100
2
Θ3 0.5 50
θ4 0.1 50
画决策树的方法是在左端首先画出 一个方框作为出发点，它叫做决策 点．从决策点画出若干条直线，每一直 线代表一个策略（方案），这些直线叫 做策略枝．在各个策略枝的末端画出一 个圆圈，它们叫做事件点（机会点）， 从事件点出发引出若干直线，每条直线 代表一种状态，这些直线叫做概率 枝．最后把各个策略在各种状态下的结 果值记在概率枝末端，这样就构成了一 个决策树．
i n ij j 1
2
K3 (30) -50
50
150
100
150
200
75*
50
K4 (40) -100 0
通过比较可知最优策略是每周进货20件或30件．
10.3 不确定型决策 （续）
10.3.5 后悔值准则 后悔值准则也叫做Savage准则， 是对悲观决策法的一种修正， 目的是使得保守程度少一些。
通过比较可知最优策略是每周进货40件．
10.3 不确定型决策 （续）
10.3.4 等可能准则
• 等可能准则也称Laplace准则。运 用该准则决策时，决策者认为各种 未来事件的发生是等可能的，可采 用等概率计算各个方案的期望结果 值，然后选择期望结果值最优的方 案作为最优方案。
例10.4 用平均值决策法对例10.4进行决策． 解 列决策表如表 10-5所示 ． 状态 E (a ) θ4 Θ1 Θ2 Θ3 1 （10）（20）（30）（40）n V 50 50 50 50 方 K1 (10) 50 案 K (20) 0 100 100 100 75*

运筹学排队论2

运筹学排队论2
现将上式参数 引入时间因素 t ,即将
换为 t ,得到
pn
(t)
(t)n
n!
et
,
t
0,
n
0,1,2,.
表示长为t的时间区间内到达n个顾客的概率为 pn (t) ,且服从泊松分布.这称为泊松流或泊松过 程或简单流. 设t时间内到达的顾客数为随机变量N(t),则有
E[N(t)] t, D[N(t)] t.
服务台
2.C个服务台,一个公共队伍
服务台1 服务台2 服务台C
3.C个服务台,C个队伍
服务台1 服务台2 服务台C
二.排队系统的三个组成部分
1.输入过程:指顾客按怎样的规律到达. ⑴顾客的总体数或顾客源:指可能到达服务机
构的顾客总数.顾客总体数可以是有限的,也可 以是无限的; ⑵顾客到达的类型:顾客是单个到达还是成批 到达; ⑶顾客相继到达时间间隔的分布,如按泊松 分布,定长分布还是负指数分布.
排队论的创始人是丹麦哥本哈根市电话局的 工程师爱尔朗(A.K.Erlang),他早期研究电话 理论,特别是电话的占线问题,就是早期排队 论的内容.
§2 排队论的基本概念
一.排队现象的共同特征:为了获得某种服务而 到达的顾客,如不能立即得到服务而又允许排 队等候,则加入等待的队伍,获得服务后离开.我 们把包含这些特征的系统称为排队系统. 排队系统的几种情况: 1.单服务台排队系统
例9.1 某仓库全天都可以进行发料业务，假设 顾客到达的时间间隔服从均值为1的负指数分 布现在有一位顾客正好中午12：00到达领料， 试求：
（1）下一个顾客将在下午1：00前到达的概率； （2）在下午1：00与2：00之间到达的概率： （3）在下午2：00以后到达的概率。

第10章 动态规划

第10章 动态规划
②某些情况下，用动态规划处理不仅能定性描 述分析，且可利用计算机给出求其数值解的 方法。
管理运筹学
7
缺点
①没有统一的处理方法，求解时要根据问题的 性质，结合多种数学技巧。因此实践经验及 创造性思维将起重要的引导作用；
②“维数障碍”，当变量个数太多时，由于计 算机内存和速度的限制导致问题无法解决。 有些问题由于涉及的函数没有理想的性质使 问题只能用动态规划描述，而不能用动态规 划方法求解。
盈利 工厂 设备台数
0 1 2
3 4 5
甲厂
0 3 7 9 12 13
乙厂
0 5 10 11 11 11
管理运筹学
29
第一阶段：只有1个始点A，终点有B1,B2,B3,B4 。对始点和终 点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题：
表10-4
本阶段始 点(状态)
A
阶段1 本阶段各终点（决策）
B1
B2
B3
B4
4+12=16 3+13=16 3+14=17 2+12=14
到E的最 本阶段最优终 短距离 点(最优决策)
第四阶段：两个始点D1和D2，终点只有一个；
表10-1
阶段4
本阶段始点 本阶段各终点（决策） 到E的最短距离
（状态）
E
D1
10
10
D2
6
6
分析得知：从D1和D2到E的最短路径唯一。
本阶段最优终点 （最优决策)
E E
管理运筹学
27
第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点
和终点进行分析和讨论分别求C1，C2，C3到D1，D2 的最短路

运筹学讲义完整版

运筹学讲义完整版
第35页
等可能准则
n
max{
i
1 n
Vij
j=1
}
S1 A1 20 A2 9 A3 6
S2
S3
Vi =
1 3
Vij
1 -6
5
80
5
2 3
max=5
2 3
54
5
选 A2
第36页
5.后悔值准则（Savage原则 ） （最小机会损失决策）
定义：称每个方案aj在结局Si下的最大可能 收益与现收益的差叫机会损失，又称后悔值 或遗憾值。记Rij(si,aj)=MaxQij(si,aj)-Qij(si,aj)
第27页
收益矩阵
事件 高
方案
S1
A1
20
A2
9
A3
6
中
低
S2 S3(万元)
1
-6
8
0
5
4
第28页
1.乐观准则（Hurwicz原则、MaxMax ） （冒险型决策）
对于任何行动方案 ，都认为将是最好的状态发 生，即益损值最大的状态发生。然后，比较各 行动方案实施后的结果，取具有最大益损值的 行动为最优行动的决策原则，也称为最大最大 准则。
第39页
（3）在机会损失表中，从每一行选一 个最大的值，即每一方案的最大机会损 失值 Max Rij(si,aj) （4）再在选出的 Max Rij(si,aj)选择最 小者：
第37页
对于任何行动方案aj ,都认为将是 最大的后悔值所对应的状态发生。然后， 比较各行动方案实施后的结果，取具有 最小后悔值的行动为最优行动的决策原 则，称为后悔值准则。记
R (s,aopt) = Min Max Rij(si,aj) ji

项目管理-运筹学-第10章 (1)

项目管理-运筹学-第10章 (1)
第 十 章
图与网络分析
图与网络分析
引言

起源：东普鲁士的哥尼斯堡，布雷格尔河上的七桥问题。 图论是应用非常广泛的运筹学分支，它已经广泛地应用于： 系统科学，工程技术，交通运输，经济管理，电子计算机 等各项领域。许多问题都可以同图论的理论和方法来加以 解决。例如： 通信线路的架设，
输油管道的铺设，
树





不含圈的连通图，称为树。 定理1：设G＝（V，E）是一个树，p（G）≥2，则G中至 少有两个悬挂点。 定理2：图G＝（V，E）是一个树，iff，G不含圈，且仅 有p－1条边。 定理3：图G＝（V，E）是一个树，iff，G是连通的，且q （G）＝p（G）－1。 定理4：图G是一个树，iff，G的任意两个结点之间有且仅 有一条链。 注意三个条件：G连通，G不含圈， q（G）＝p（G）－1， 任两个成立即可构成树。
25
图与网络分析
最大流问题
2.调整过程
首先按照vt和其他的点的第一个标号，反向追踪，找出增广链。再看 vk 的第一个标号，若是 vi ，则弧 (vi,vk) 都在 μ 上。依次类推，直到 vs为止。 这时，所找出的弧就成为网络 D的一条增广链 μ。取调整量 θ= l(vt),即vt 的第二个标号，令
铁路或者公路交通网络的合理布局等 都可以应用图论的方法，快捷地加以解决。
2
图与网络分析
引 言(七桥问题)
3
4
图与网络分析
图的基本概念


图：由非空的结点集V以及由结点对表示的边所构成的边 集E所构成。记作：G＝（V，E）。 图的分类
有向图：所有的边都是有向边，有向边（v1，v2）又称弧； 无向图：所有的边都是无向边，无向边 [v1，v2] 又称边。 |V|＝p（G）＝p，称为图的阶数 |E|=q(G)=q， 有限图：V（G）、E（G）均为有限集合； 无限图： V（G）、E（G）至少一个为无限集合。 空图：q＝0的图。平凡图：p＝1的图。多重边、环。 简单图、多重图。结点的次数（度数），入度与出度。

运筹学第十章

运筹学第十章

共八十四页
在纯策略下有解的矩阵对策(duìcè)的解 法
解法的思想(sīxiǎng)：双方都立足在不利的情况下争取最好 的结果─最大最小原则。
例 求解矩阵对策 G ={S1,S2;A}，其中:
7 1 8
A
3
2
4
16 1 3
3 0 5
共八十四页
解：
max aij
i
1 2 3
1 7 1 8
共八十四页
第1节 引言(yǐnyán) 1.1 对策行为和对策论
对策行为是指具有(jùyǒu)竞争或对抗性质的 行为,在这类行为中，竞争对手可能采取的 各种策略是清楚的；各方一旦选定了自己 的策略，竞争结果就清楚了，竞争结果可 以定量描述；双方都希望取得最好的结果 而且十分清楚对方也想达到同样的目的。
S1 ={α1，α2…，αm} S2 ={β1，β2，…βn}
共八十四页
为了与后面的概念区分开来，称αi为I的 纯策略，βj为II的纯策略，对于(duìyú)纯策略
构 成的局势（αi，βj）称为纯局势。
共八十四页
局中人I的赢得(yíngdé)矩阵记 为
a11 a12
a1 j
a21
a22
a2 j
金，田忌要输3千金。田忌的谋士建议田忌在赛前先探
听齐王赛马的出场次序，然后用自己的下马对齐王的上 马，用中马对齐王的下马，用上马对齐王的中马。结果
(jiē guǒ)负一局胜两局赢得1千金。由此看来，两个人各 采取什么样的出马次序对胜负是至关重要的。
共八十四页
1.2 对策(duìcè)模型的三要素
我们称具有对策(duìcè)行为的模型为对策(duìcè) 模型或
min j
aij

运筹学第十章

运筹学第十章

2.最小生成树 对于无向图G= G=( ),保留 中所有点, 保留G 对于无向图G=(V,E),保留G中所有点,而删掉 的边或保留一部分G的边,所获得图,称为G G的边或保留一部分G的边,所获得图,称为G的生 成子图. 成子图.
v3 v2 v1 v9 v10 v5 v6 v8 (a) v2 v1 v9 v10 v5 v6 v8 (c) v7 v7 v4 v1 v9 v10 v3 v4 v3 v2 v5 v6 v8 (b) v7 v4
关联边:与同一顶点相连的边, 关联边:与同一顶点相连的边, 称为该点的关联边 相邻点:一条边的两个顶点, 相邻点:一条边的两个顶点,称 为相邻点. 为相邻点. 环:两个顶点相同的边称为环 v1 多重边:两顶点间边的个数≥ 多重边:两顶点间边的个数≥2, 叫多重边. 叫多重边. 一个顶点v 次:一个顶点v具有关联边的总数 e3 称为该顶点的次,记作d 称为该顶点的次,记作d(v). 悬挂点:次为1的顶点称为悬挂点. 悬挂点:次为1的顶点称为悬挂点. 孤立点:次为0的顶点称为孤立点. 孤立点:次为0的顶点称为孤立点. v3 简单图:无环, 简单图:无环,无多重边的图称 e6 为简单图. 为简单图.
一,求解最短路的Dijkstra算法 注意:Dijkstra算法只适用每条弧的赋权数都大 注意:Dijkstra算法只适用每条弧的赋权数都大 于等于零的情况. 于等于零的情况. Dijkstra算法又称为双标号法 所谓"双标号" 算法又称为双标号法, Dijkstra算法又称为双标号法,所谓"双标号", 也就是对图中点vj赋予两个标号(lj,kj), vj赋予两个标号 ),第 也就是对图中点vj赋予两个标号(lj,kj),第 一个标号lj表示vs vj的最短路长度 lj表示vs到 的最短路长度, 一个标号lj表示vs到vj的最短路长度,第二个标 kj表示在vs至vj的最短路上vj前面一个邻点的 表示在vs 的最短路上vj 号kj表示在vs至vj的最短路上vj前面一个邻点的 下标,这样从始点到终点逐次标号, 下标,这样从始点到终点逐次标号,最后可得最 短路长,再由终点顺着第二标号, 短路长,再由终点顺着第二标号,即可得最短路 径.

运筹学-第十章-排队论

运筹学-第十章-排队论
一般来说，排队论所研究的排队系统中，顾客到来的时 刻和服务台提供服务的时间长短都是随机的，因此这样 的服务系统被称为随机服务系统
小结
排队系统又称随机服务系统 ① 有请求服务的人或物； ② 有为顾客服务的人或物； ③ 顾客到达时间与接受服务时间是随机的。
结构： 顾客到达 ----- 排队 ------ 服务机构服务 ------ 顾客离去
类似地还可画出许多其他形式的排队系统，如串并混联的 系统，网络排队系统等
尽管各种排队系统的具体形式不同，但都可以由图10-5 加以描述
图10-5 随机服务系统
通常称上图表示的系统为一随机聚散服务系统，任一排队系 统都是一个随机聚散服务系统。 这里，“聚”表示顾客的到达，“散”表示顾客的离去。
所谓随机性则是排队系统的一个普遍特点，是指顾客的 到达情况(如相继到达时间间隔)与每个顾客接受服务的时 间往往是事先无法确切知道的，或者说是随机的。
II
在排队系统中，忙期和闲期总是交替出现的。
3、其他相关指标
(1)忙期服务量：指一个忙期内系统平均完成 服务的顾客数；
(2)损失率: 指顾客到达排队系统，未接受服务 而离去的概率;
（对损失制或系统容量有限而言） (3)服务强度： = /s ；
根据前面的约定，我们将主要分析系统的平稳分布。于是记： Pn ：当系统达到统计平衡时处于状态n的概率（pn(t)）
② 等待时间有限。即顾客在系统中的等待时间不超过 某一给定的长度T，当等待时间超过T 时，顾客将自动 离去，并不再回来。 如顾客到饭馆就餐，等了一定时间后不愿再等而自动 离去另找饭店用餐。
③ 逗留时间(等待时间与服务时间之和)有限。例如 用高射炮射击敌机，当敌机飞越高射炮射击有效区 域的时间为t 时，若在这个时间内未被击落，也就不 可能再被击落了。

运筹学第十章 图论与网络优化

运筹学第十章 图论与网络优化

平面图
一个图称为平面图，如它有一个平面图形，使得 边与边仅在顶点相交。下图就是一个平面图：
v1
e2
v3
非平面图
e3
e1
v2
e4 e5
e6
v4
环、多重边
端点重合为一点的边称为环。 连接同一对顶点的多条边称为多重边。
v1
e1
e3
e2
v2
e4
v3
e5
简单图
一个图称为简单图,如果它既没有环也没有多重边.
含有多重边的图称为多重图.
我们只讨论有限简单图，
v1
e2
v2
即顶点集与边集都是有限的图。
只有一个顶点的图称为平凡图； e5
e7
e3
边集是空集的图称为空图。
v4
e4
v3
完全图K n
完全图是每一对不同顶点都恰有一边的简单图； 具有 n 个顶点的完全图记为K n.
|
E(Kn )
|
Cn2
n
2
n(n 1) 2
连通性
图G称为连通的，如果G的任意两个顶点u 和 v 中存在一条(u,v)路。
一个连通图称为一个连通分支。 不连通图（分离图）至少有两个连通分支。
用w 表示G的连通分支数。 割边：删除掉这条边后图G不连通。 割点：删除掉这个点后图G不连通。 割集：删除掉连通图中的若干条必要的边后，使 得图不连通，则这些边的集合称为图的一个割集.
图论(Graph Theory)是运筹学中的一个重要分支， 主要研究具有某种二元关系的离散系统的组合结构 和性质。
随着电子计算机的蓬勃发展，图论不仅得到了迅速 发展，而且应用非常广泛。它直观清晰，使用方便， 易于掌握。

第十章 物流运筹学——排队论

第十章 物流运筹学——排队论

2．排队问题解决 （1）排队问题分析。将每次到达的药品看作一 个客户，每次到达的药品可能有一个品规也可能 有多个品规，每个品规验收员都要进行验收。由 于国药集团医药控股沈阳有限公司物流中心的供 应商分布在全国各地，没有关联性药品到达相互 独立。验收的服务时间由于到达货物的品规数， 到货包装破损情况，药品剂型等的不同每个客户 的验收时间也不同，客户的服务时间可能服从负 指数分布。 （2）客户到达服务观察。从4月12日到7月12 日62个工作日中利用随机抽样原则随机抽取了10 天进行观察，记录每天9个时段内客户到达的数量。
c
ρ
P0
Pc
D
4 0.75 0.0377 0.1272 0.5090
5 0.6 0.0466 0.0945 0.2363
6 0.5 0.0489 0.0495 0.0990
7 0.43 0.0495 0.0215 0.0377
可见，应设置7个站台。
M / M / c / ∞ 排队系统模型（
λ
0 1
案例分析
以国药集团医药控股沈阳有限公司在验收服务 设施配置中的应用，给出排队模型，说明排队理论 在实际当中的应用情况。 • 国药集团医药控股沈阳有限公司物流中心每天 要验收大量的货物，货物到达后需要签收、验收、 入库。现验收组有两人，验收员和理货员各一人， 从2004年4月开始由于到货量增加，验收出现不及 时，经常被内部客户投诉。物流中心为提高客户服 务水平，需要增加验收服务能力，为此需要对验收 排队服务进行以下数量分析作为决策依据。 1．决策目标 （1）降低客户等待时间； （2）降低作业成本。 •
实训设计
• 【实训目标】 实训目标 掌握 M / M / c （包括 c =1）排队模型的各项系 统指标的求解方法。 • 【实训内容与要求 实训内容与要求】 在企业内或流通环节中调查数据，并以此建 立数学模型，利用排队模型计算得出的各项系统 指标来具体分析系统的结构，以获得更好的效益。 • 【成果与检验 成果与检验】 能够建立相应的排队模型，利用以给出的系 统指标公式，给出系统的量化结果。

第10章 排队论 《运筹学》PPT课件全

第10章 排队论 《运筹学》PPT课件全

WL
Wq
Lq
W
1
M/M/s 混 合 制 排 队 模 型
一、 单服务台混合制模型
M/M/1/K： 顾客的相继到达时间服从参数 为λ的负指数分布(即顾客的到达过程为 Poisson流)，服务台个数为1，服务时间V 服从参数为μ的负指数分布，系统的空间 为K。
单
平稳状态下队长N的分布pn=P{N=n},n=0,1,2,…。
服
由于所考虑的排队系统中最多只能容纳K个顾 客(等待位置只有K-1个)，因而有
务 台
n
0
n
n=0,1,2,...,K-1 n≥K n=1,2,...K
混 合
有
Cn
(
)n
n
n=0,1,2,...,K
0
n>K
制
故 pn n p0 n=1,2,…,K
模 型
1
其中，p0
1
1
K
n
1
K
1
1
n1
统
其分布函数为B(t)，密度函数为b(t)，则
的
常见的分布有： (1) 定长分布(D)
描
(2) 负指数分布(M)
述
(3) k阶爱尔朗分布(Ek)：
排
排队系统的符号表示
队
“Kendall记号”，其一般形式为：X/Y/Z/A/B/C，其中 XX：顾客到达时间间隔的分布
系
YY：服务时间的分布
统
Z Z：服务台个数
的
A ：系统容量 B B：顾客源数量
符
C C：服务规则
号
例 （M / M / 1 /
FCFS）表示：
表
到达间隔为负指数分布，服务时间也为负指数分 布，1个服务台，顾客源无限，系统容量也无限，
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

15
第三阶段：
f 3 s 3 max r3 s 3 , x 3 f 4 s4 max r3 s 3 , x 3 .
x 3 s3 x 3 s3
s 3 0,1,2,3,4,5;
表9-6
x3 s3
0 1 2 3 0 0 — — — 1 — 4 — —
函数值之和中的最小值.
f k s k min rk s k , x k f k 1 s k 1 , k n, n 1,,2,1 边界条件 : f n1 s n1 0. r2 B1 , C 1 f 3 C 1 f 2 B1 min r2 B1 , x 2 f 3 s 3 min r2 B1 , C 2 f 3 C 2 如: r B , C f C 3 3 2 1 3 2 12 14 min 1 11 min 12 12. 6 11 17
12
§3.动态规划应用
建立动态规划模型必须做到一下几点: 1. 根据时间或空间的自然特性将实际问题恰当地划分为若干个 阶段，即把问题的过程转化为多阶段决策过程. 2.正确的选择状态变量sk,使它既能描述过程的演变特征,又要 满足无后效性(到达这个状态前的决策将不影响到该状态以后的 决策). P7 3.确定决策变量xk. 4.正确写出状态转移方程
1
§1.多阶段决策过程最优化问题举例
最优化原理 作为整个过程的最优策略应具有这样的性质,即无论 过去的状态和决策如何,对于前面的决策所形成的状态而言, 余下 的诸决策必须构成最优策略. 最短路径问题:
最优化原理在最短路上的应用可阐述如下: 从最短路上的每一点到终点的部分道路,也一定是从该点到 终点的最短路.
s 3 T2 s 2 , x 2 s 2 x 2 .
而且，有 s 3 x 3 .
f k s k max rk s k , x k f k 1 s k 1 , k 3,2,1. xk 边界条件 : f 4 s 4 0.
甲 厂
乙 厂
丙 厂
14
P18 P17 P16
解: 将问题按工厂分为三个阶段,甲、乙、丙三厂分别编号为 1、2、3厂。并设
sk 分配给第k个工厂至第3个工厂的设备的台数k 1,2,3). ( xk 分配给第k个工厂的设备台的数k 1,2,3). (
显然：s1 5.
s 2 T1 s1 , x1 s1 x1 ,
2
例1.如图9-1,给定一个运输网络,两点之间连线上的数字表示 两点间的距离,试求一条从A到E的运输线路,使总距离为最短. B1 2 1 6 4 B2 7 2 4 8 B3 3 75 B4 1
4 A 3 3 2
C1
8 6
7 C2 5 1 C3 6
D1 10
6 D2 E
图9-1
3
P5 P6
4 A 3 3 2
阶段1 本阶段始 点(状态) A 本阶段各终点(决策) B2 B3 3+13=16 3+14=17 到E的 本阶段最优 终点 最短 距离 (最优决策) 14 B4
6
B1 4+12=16
B4 2+12=14
此问题的最短路:
A
B4
C3
D1
E
P10
这段路的长度为: 14 . 利用动态规划的方法,不仅求出了全过程的最短路,还求出了图 上任意一点到E的最短路.
9
P7
5.指标函数
指标函数是衡量全过程策略或k子过程策略优劣的数量指标, 最优指标函数: 指标函数的最优值.记作 f 1 s1 或f k s k . 全过程最优指标函数.
k子过程最优指标函数. 例 1中的指标指的是从某点到终点的距离, 最优指标是从某 点到终点的最短距离.
f k s k
f 2 s 2
0 5 10 14 16
x2
0 1 2 2 1，2
5
0+12
5+12
10+11
11+6
11+4
11+0
21
2
17
P14
第一阶段： s1 5; s2 s1 x1 5 x1 ,
0 x1 s1
f 1 s1 max r1 s1 , x1 f 2 s 2 max r1 5, x1 f 2 5 x1
f 1 s1
如:
f 1 s1 f 1 A 14; f 2 B2 13;3 11.
阶段指标函数(阶段效益) rk s k , x k : 表示在第k阶段的sk状态下 做出xk决策的指标值.
如: r1 A, B1 4; r2 B3 , C 2 8; r4 D1 , E 10.
r3 s 3 , x 3
2 — — 6 — 3 — — — 11 4 — — — — 5 — — — —
f 3 s 3
0 4 6 11
x3
0 1 2 3
4 5
— —
— —
— —
— —
12 —
— 12
12 12
4 5
16
P14
第二阶段：
f 2 s 2 max r2 s 2 , x 2 f 3 s 3 max r2 s 2 , x 2 f 3 s 2 x 2
0 x 2 s 2 0 x 2 s 2
s 2 0,1,2,3,4,5;
s3 s2 x2 ,
表9-7
x2 s2
0 1 2 3 4 0 0+0 0+4 0+6 0+11 0+12
r2 s 2 , x 2 f 3 s 2 x 2
1 — 5+0 5+4 5+6 5+11 2 — — 10+0 10+4 10+6 3 — — — 11+0 11+4 4 — — — — 11+0 5 — — — — —
B1 2 1 6 4 B2 7 2 4 8 B3 3 75 B4 1
四阶段决策过程最优化问题 C1 7 C2 5 1 C3 6 8 6 D1 10
D2
6
E
四个弧远的点(E)为终点.
4
逆序解法:(P187中) 第四阶段: 阶段4
P7 P3
本阶段始点 本阶段各终点(决策) 到E的最短 本阶段最优终点 (最优决策) 距离 E (状态) D1 10 10 E D2 6 6 E 第三阶段: 阶段3
s k 1 Tk s k , x k .
13
5.正确写出指标函数.
一.资源分配问题 例2.某公司拟将某种设备5台,分配给所属的甲、乙、丙三个 工厂，各工厂获得此设备后,预测可以创造的利润如表9-5所示,问 这5台设备应如何分配给这3个工厂,使得所创造的总利润为最大? 表9-5 盈利 设备台数 0 1 2 3 4 5 0 3 7 9 12 13 0 5 10 11 11 11 0 4 6 11 12 12 工厂
本阶段始点 (状态) C1 C2 C3
本阶段各终点(决策) D1 D2 8+10=18 6+6=12 7+10=17 5+6=11 1+10=11 6+6=12
到E的 本阶段最优终点 (最优决策) 最短距离 12 D2 11 D2 11 D1 5
第二阶段:
阶段2 本阶段始 点(状态) 本阶段各终点(决策) C2 C3 到E的最 短距离
p1,4 s1 x1 A B4 ; x2 B4 C3 ; x3 C3 D1; x4 D1 E
k子过程策略:从第k阶段开始到最后阶段的决策组成的决策 序列称为k子过程策略,简称k子策略.记为 pk ,n sk . 如:
p2,4 s1 x2 B2 C1; x3 C1 D1; x4 D1 E
阶段: 第一阶段: 以A点为始点,而以距离A点正好一个弧远的点(B1,B2, B3,B4)为终点; 第二阶段: 以距离A点正好一个弧远的点(B1,B2,B3,B4)为始点,以 距离A点正好两个弧远的点(C1,C2,C3)为终点; 第三阶段: 以距离A点两个弧远的点(C1,C2,C3)为始点,以距离A点 三个弧远的点(D1,D2)为终点; 第四阶段: 以距离A点三个弧远的点(D1,D2)为始点,以距离A点
第十章 动态规划
动态规划(Dynamic progroming)是运筹学的一个重要分支, 是解决多阶段决策过程最优化的一种量化方法.这种方法把困难 的多阶段决策问题变换成一系列互相联系较容易的单阶段问题, 是由美国学者贝尔曼(R.Bellman)所建立的. 动态规划的成功之处在于, 它可以把一个n维决策问题转化 为n个一维最优化问题,一个一个的解.另外动态规划还能求出全 局极大和极小. 用动态规划可以解决管理中的最短路问题、装载问题、库 存问题、资源分配问题、生产过程最优化问题。
0 x1 5
表9-8
x1 s1
5 0 0+21 1 3+16
r1 5, x1 f 2 s1 x1
2 7+14 3 9+10 4 12+5 5 13+0
10
P6
6.状态转移方程 已知第k+1阶段的状态是由第k阶段的状态和第k阶段的决策 所决定的,将这种关系用方程的形式表示为 在sk的状态下,在所有做出的各种 决策xk中,取一个第k阶段的指标值 s k 1 Tk s k , x k rk(sk,xk)与k+1子过程的最优指标 如: s 3 C 1 T2 B2 , C 1 . 二.基本方程 k子过程与k+1子过程最优指标函数有如下递推关系: