当前位置:刘毅传书 > 眼光作文

MMs 等待制排队模型

时间:2021-06-07 03:47:17|来源:未知|编辑:admin|点击:
简介:专题十 排队论
Queueing Theory
10.1 排队论概述
10.2 顾客达到流与服务时间的分布
10.3 生灭过程及其状态平衡方程
10.4 M/M/s 等待制排队模型
10.5 排队服务系统的优化
10.4 等待制排队模型
? 模型
?系统状态图:
:系统内没有顾客,服务员闲着;
:有一个顾客,服务员正在为其服务,无顾客排队;
:有两个顾客,服务员正在为先到者服务,另一个在排队等待;
:有 个顾客,服务员正在忙着,有 个顾客在排队等待.
λ
μS0 S1
λ
μ S2
λ
μ Sk
λ
μ
λ
μ
( )//MMs
( )/ /1MM
0S
1S
2S
kS k 1?k
?当 时极限概率存在.1?=?

12
0 1
?
?
?
?
?
?
?
?
?
+
?
?

?
?++
?
?

?
?++=
k
P ?
?
?
?
?
?
? ? 121 ?+++++= k?
?当ρ<1时,该几何级数收敛.求和后得
?=
?

?
?=
?
11
1 1
0P
?按下列公式可求出 , ,…, ,…
),1(001
? ?===PPP
( )?
? ?=
?
?

?
?=12
0
2
2 PP
( ) , 13
3 ? ?=P
( ) , 1 ? ?=k
kP
1P 2P kP
?系统的运行指标:
⑴ 系统中顾客的平均数 (数学期望)
?=
?
=0k
kkP ? =
?
=0
)1(
k
kk ? =
?
=
?
0
1)1(
k
kk ?
=
?
=0
)1(
k
k
d
d ?=
?
=0
)1(
k
k
d
d

?
?

?
?
?= 1
1)1( d
d
2)1(
1)1(
?

?
=
?
?
?=1
?
?=
s 0 1 2 kL=0 P +1 P +2 P + +k P +? ? ? ?
sL
⑵ 系统中排队顾客的平均数 (数学期望)
? ?=
?
=1
)1(
k
kPk ? =
?
=
?
=1 1k k
kk PkP ? ? =
?
=
?
=0 0
0 )(
k k
kk PPkP
s0(1 )LP=? ?

? =1 ?
?
?=1
2
s [1 (1 )]L ?=? ? ? sL ?=?
?此外,Ls=Ls-L服,所以有L服=ρ.
?根据 Little 公式 Ls=λWs、 Lq=λWq,可求出
s
s
LW
?=q
q
LW
?=
q 1+ 2 3 kL=0 P 1 P +2 P + +(k-1) P +? ? ? ?
qL
例. 某火车票售票处在一天的繁忙期内,平均每小时到达15人,服从泊松分
布.该售票处设有一个售票处窗口,每个顾客的平均售票时间为3分钟,服从
负指数分布.试计算这个排队服务系统的运行指标.
解 已知平均到达强度 λ=15人/小时
平均服务强度 μ=60/3=20人/小时
? 系统的负荷: 75.04
3
20
15====?

s
0.75 3 (人)1 1 0.75L ?
?===
qs 3 0.75 2.25 (人)LL?=?=?=
( ) ( )s
s
3 0.2 小时 12 分钟15
LW
?====
( ) ( )q
q 0.15 小时=9分钟LW
?==
? 顾客不排队的概率:
0 1 1 0.75 0.25?=?=?=P
? 顾客到达后必须等待 k 个顾客以上的概率:
=?=?
=
?
+=
k
n
n
kn
n PPknP
01
1)(
? ?)1()1()1()1(1 2 ? ?++?+?+=k?
? ?132211 +?++?+?+=kk ? ?
1+=k?
3164.075.0)3( 44===? ?nP3,若 则=k
小 结
(1) 模型的基本特征;
(2) 模型的系统运行指标;
(3) 模型的应用。
( )//MMs
( )/ /1MM 更多>> 简介:决策论/OR
专题八 决策论---单目标决策
Decision Theory----- single objective decision
8.1 决策论的基本知识
8.2 风险型决策问题
8.3 不确定型决策问题
决策论/OR
期望值
5
17/3
11/3
8.3 不确定型决策问题
(1)等可能准则
? 基本思想:认为各种自然状态出现的概率均等,
将不确定型化为风险型考虑.
例 效益值 状态
方案
高(S1) 中(S2) 低(S3)
I
II
III
20
9
4
1
8
4
-6
0
3
1/3 1/3

1/3
最优决策为:方案II
( ) ( ) ( ) ( )12=====jnP S P S P S P S
决策论/OR
(2)乐观准则(也称max-max准则)
? 基本思想:对结果估计得很乐观,每种方案都取最有利的情况,再从
中选效益值最大者做为决策方案.
例 试用乐观准则进行决策.
效益值 状态
方案
高 中 低
I
II
III
20
9
4
1
8
4
-6
0
3
乐观
max max
20
9
4
20√
最优决策为:方案 I
决策论/OR
(3)悲观准则(也称min-max准则)
? 基本思想:对结果估计得很不利,再从各种不利方案中选最好者.
例 用悲观准则进行决策.
效益值 状态
方案
高 中 低
I
II
III
20
9
4
1
8
4
-6
0
3
悲观
min max
-6
0
3 3√
最优决策为:方案 III
决策论/OR
(4)最小后悔值准则(也称max-min准则)
?基本思想:找出使后悔最小的方案.
?基本方法:①确定各状态的理想目标,并求后悔值;
②求各方案的最大后悔值;
③从各最大后悔值中找出最小者.
例 用最小后悔值准则进行决策.
效益值 状态
方案
高 中 低
I
II
III
20
9
4
1
8
4
-6
0
3
后悔值
max min
9
11
16
9√
后悔值
矩阵
0
11
16
7
0
4
9
3
0
最优决策为:方案 I
决策论/OR
11
max{ } (1 ) min{ } ( 1,2,..., )i ij ijj n j n
H c c i m
? ? ? ?
=? + ? ?=
(5)折衷准则
?基本思想:采取折衷的办法克服完全乐观或悲观.
?方法:决策者依经验确定乐观系数a(0≤a≤1)的取值, 按下式求
出各方案的折衷效益值并选最大者:
决策论/OR
效益值 状态
方案
高 中 低
I
II
III
20
9
4
1
8
4
-6
0
3
折衷效益

0.5
2.25
3.25 √
例 用折衷准则进行决策.
解 取 ?=1/4,则
5.0)6(4
11204
1
1=
?

?
? ?+?=H
最优决策为:方案 III
决策论/OR
效益值 状态
方案
高 中 低
I
II
III
20
9
4
1
8
4
-6
0
3
等可能
期望值
5
17/3
11/3

乐观 max
max
20
9
4
20√
悲观
min max
-6
0
3 3√
后悔值
max min
9
11
16
9√
折衷效益值
0.5
2.25
3.25√
决策论/OR
小结:
(1)不确定型决策问题,最明显的特征就是对自然状态发
生的概率一无所知。决策完全取决于所采用的决策准则。
(2)等可能准则、乐观准则、悲观准则、后悔值准则和折
衷准则。
(3)同一个决策问题,不同准则所作的决策不一定相同。 更多>> 简介:专题九 存贮论
Inventory Theory
9.1 存贮问题的基本概念
9.2 确定型存贮模型
9.3 单周期随机存贮模型
?存贮系统
9.1 存贮问题的基本概念
满足需求补充供应 存贮
(购进) (销售)
“供”
系统的输入 “销”
系统的输出“存”
量和周期
“供过于求”,造成积压,带来损失;
“供不应求”,引起缺货,也带来损失.
由于消费与存贮、需求与供应之间的不协
调,往往出现“供不应求”和“供过于求”
的现象而造成损失,如何权衡这种得失的
一类问题,称为存贮问题。
存贮问题
?需求:为满足需要,从存贮中取出一定数量存贮物的过程.需求相当
于存贮系统的输出.
?需求量:单位时间内的需求,一般用 或 表示.
?需求方式
(a)间断成批; (b)均匀连续.
?需求量规律
(a)确定性;
(b)随机性,但服从某种概率分布;
(c)一无所知.
?需求与需求量
R r
?补充:存贮系统的输入.
订货或生产
?补充量 :指定周期内的
订货量或生产量.
?补充与补充量
存贮策略:决定补充量与补充时机的策略。
?存贮策略
常见的存贮策略有:
(1) 循环策略
每隔时间 补充存贮量为
(2) 策略
称为最低库存量,
是最大库存量。
(3) 混合策略
衡量策略优劣:计算并比较其平均费用.
Q
t
( ),sS
s
S
( ),,t s S
⑴存贮费
? 包括仓库使用费、货物保管费、占用流动资金的利息、货物损坏
变质等费用.一般和存贮物的数量及时间成比例。
? :每件存贮物在单位时间内所分摊到的费用.
⑵缺货费
? 存贮物供不应求时所引起的有关损失.
? :每件短缺物品在单位时间内的损失费用.
? 费用
1c
2c
⑶进货费
? 订购费 ( ) :即固定费用,与订货次数有关而与订货数量无关.
? 货物的成本费用 ( ) :即可变费用,与订货的数量有关. 为
货物单价。
则有:进货费为
3c
KQ K
3 +c KQ
确定型存贮模型
随机型存贮模型
?目标函数
?模型分类
? ?平均费用Min
? ?平均利润Max

小结:
(1)基本问题:对于特定的需求类型,以怎样的方式进
行补充,才能最好地实现存贮管理的目标。
(2)基本方法:费用分析。
(3)存贮问题的类型:确定型和随机型。 更多>> 简介:1、极小(MinS)目标函数的处理:
?方法一:Cj – Zj ? 0 达到最优
?方法二: Zj – Cj ? 0 达到最优
? 1.6 单纯形法的进一步讨论
2、构造基:当约束条件为“?”或“=”时,
需要设置“人工变量”构造基
求解方法有:
?方法一:大M法
?方法二:两阶段法
?大M法
?方法要点:目标函数按下式处理(M是一个充分大的正数),
约束条件不变,填入单纯形表进行求解。
Mx
Mx
MinS
MaxZ
人工
人工
+=
?=


?例


?
?
?++
?+
++=
0,,
4
62
7810
321
321
21
321
xxx
xxx
xx
xxxMinS


?
?
=?++
=+?+
=
0,,,,,
4
62
007810
654321
5321
6421
654321
xxxxxx
xxxx
xxxx
MxxxxxxMaxZ


?
?
=?++
=+?+
+++++=
0,,,,,
4
62
007810
654321
5321
6421
654321
xxxxxx
xxxx
xxxx
MxxxxxxMinS

?两阶段法
?方法要点
(1)第一阶段目标函数的设置:
(2)转入第二阶段的条件及处理方法:
1 ,
1 ,
==
?=?=
人工人工
人工人工
即或

cxMinS
cxMaxZ

?条件:第一阶段满足最优性检验,且该阶段的目标值等于0,转
入第二阶段;否则该问题无解,计算终止;
?处理:替换目标函数,在第一阶段最优表上继续 更多>> 简介:专题九 存贮论
Inventory Theory
9.1 存贮问题的基本概念
9.2 确定型存贮模型
9.3 单周期随机存贮模型
9.3 单周期随机型存贮模型
(1)单周期:订购量的决定是“一次性”的,并规定两次订购之间
不发生联系,每次都视为独立订购。 .
(2)需求为随机变量:包括离散随机变量和连续随机变量。
? 问题的基本特征
? 报童问题
报童每天出售的报纸数是一个随机变量(即需求是随机离散的),
根据以往的经验,已知每天出售r 份报纸的概率为P(r).卖出一份
报纸可得报酬 k 元,卖不出去每份赔 h 元.问报童每天应订购多
少份报纸才能使损失最小或者收入最大?
设报童每天的订报数为 ,则
? 供过(等)于求 的损失期望值
?
=
?
Q
r
rPrQh
0
)()(
?
?
+=
?
1
)()(
Qr
rPQrk
? 供不应求 的损失期望值
? 总损失的期望值为:
解: Q
( )?Qr
( )?Qr
( )
01
( ) ( ) ( ) ( )
Q
r r Q
C Q h Q r P r k r Q P r
?
==+
=? + ?
**
**
( ) ( 1)
( ) ( 1)
? ?+
C Q C Q
C Q C Q
**-1
00
( ) ( )
==
+
QQ
rr
kP r P rkh
解之得:
若报童每天订购的报纸的最佳批量为 ,则必有:?Q
例 某商场拟在新年期间出售一批日历画片,每出售1000张可以赢利
70元,如果在新年期间不能售出,必须削价处理(削价一定可以售
出),此时每千张损失40元。根据以往的经验,市场需求的概率如
下表:
数量 1000 2000 3000 4000 5000
概率 0.15 0.20 0.35 0.20 0.10
问年前一次订货应订购画片多少张?

70 0.6470+40
k
hk==+
1000
0
( ) 0.15
r
Pr
=
=?
2000
0
( ) (1000) (2000) 0.35
r
P r P P
=
=+=?
3000
0
( ) 0.70
r
Pr
=
=?
2000 3000
00
( ) 0.35 0.64 ( ) 0.70
rr
P r P r
==
=? ?=
临界值0.64接近0.70, 故年前一次订货应订购画片3000张.
70, 40==kh
小结:
(1)单周期随机存贮问题的基本特征;
(2)单周期随机存贮问题模型;
(3)需求为离散型的单周期随机存贮模型求解及应用。 更多>> 简介:专题五 动态规划
(Dynamic Programming,DP)
基本思想:把问题变换为一系列互相联系的单阶段问题,然
后加以解决;
理论基础:Bellman等人提出的“最优性原理”.
是一种特殊“方法”,不是特殊“算法”.
应以丰富的想象力去建立模型,用创造性的技巧去求解.
分类:
按变量取值:离散型、连续型.
按决策过程的演变方式:确定性、随机性.
按每阶段需处理的状态变量和决策变量个数:一维、多维.
离散确定型
一维 连续确定型
多维 离散随机型
连续随机型
?
主要内容
? 5.1 动态规划的基本原理和基本概念
? 5.2 离散确定型动态规划问题
? 5.3 连续确定型动态规划问题
? 5.4 多维动态规划问题
5.1 动态规划的基本原理和概念
7 4
3 4 5
6 5 2 3
6 3 4
4 5 6
5
3

B1
3
B2
B3
C1
C2
C3
D2
D1
E
4
7
5
9
12
10
10
14
引例:最短路线问题
7
◆动态规划的基本原理
动态规划的最优性原理:一个最优策略具有这样的性质:无论初始状态和
初始策略如何,相对于初始策略产生的状态来说,其后策略必须构成最优。
实际决策方向
1 2 3 … n-1 n
始点 终点
动态规划寻优方向
◆动态规划的基本概念
阶段(Stage):一般按时间和空间的自然特征来划分,且要便于把问题
的过程转化为多阶段决策过程,使每一阶段都可以做出不同的决策。描
述阶段的变量称为阶段变量,通常用 表示。
状态(State):表示阶段开始所处的自然状况或客观条件,通常是一
个数或一组数,用状态变量变量 表示。状态变量必须具有如下两个
性质:
?无后效性。
?可知性。
决策(Decision):从该状态到下一阶段的演变方式的选择。决策也可
用一个数或一组数表示,称为决策变量,用 表示。其取值常限制在
某范围内,此范围称为允许决策集合,记为 。
k
kS
kx
( )kkDx
4) 策略(Policy):从起点到终点一系列决策所构成的行动方案。
5) 状态转移方程: 的值随 和 的值变化而变化的对应关系。
6) 指标函数:衡量所实现过程优劣的一种数量指标。
对于第 阶段,记为 ;
对于从第 阶段开始的后部过程,一般为各阶段指标值之和(有时
为各阶段指标值的乘积):
),( jj
n
kj
j xSd?
=
,k+1 k k kS=T (S x )
k+1S kS kx
k ( )k kkd s ,x
后部过程的最优指标函数:
7)指标递推方程(动态规划的基本方程):
?
? ?=
=
n
kj
jjjkk xSdSf ),(minmax/)(
?
?
?
=
=+=
++
++
0)(
,...,2,1 )},(),(min{max/)(
11
11
nn
kkkkkkk
Sf
nkSfxSdSf
例 投资金额分配问题.某公司有4百万元资金需要投资,有三个投资
项目可以选择。经市场调查预测,如果向项目 投资 百万元,则每年
所得到的利润(万元/年)因投资额的不同而有差异,如下表所示。问
应如何投资才能使总的利润最大?
投资额
利润
项目
0 1 2 3 4
项目1
项目2
项目3
0
0
0
16
12
10
25
17
14
30
21
16
32
22
17
解:令每给一个项目考虑投资多少资金为一个决策阶段,则该投资
决策问题可分为三个阶段.决策顺序为:
项目1→项目2 →项目3
i j
项目3(阶段3):
状态(未分的资金额) 0 1 2 3 4
最优决策(分配资金额) 0 1 2 3 4
最优决策的效益值 0 10 14 16 17
项目2(阶段2):
状 态
决 策 最优
决策
目标
值0 1 2 3 4
0
1
2
3
4
0+0 0 0
0+10 12+0 * 1 12
0+14 12+10 17+0* 1 22
0+16 12+14 17+10 21+0* 2 27
0+17 12+16 17+14 21+10 22+0* 2,3* 31
项目1(阶段1):
状 态
决 策 最优
决策
目标
值0 1 2 3 4
4 0+31 16+27 25+22 30+12 32+0* 2 47
S1 x1 S2 x2 S3 x3
4
0-0
4
1-16 3
2-25 2
3-30
14-32
0
0 412
3
17
2
21
1
22
0
012
17
21
0
12
170
12
0
17
0
16
14
10
0
17
16
14
10
0
31
27
22
12
0
47 更多>> 简介:最优
?原问题 :
保持原问题可行
当所有的检验数
满足最优性检验
即:保持原问题
可行,将对偶问
题由不可行转化
为可行
?对偶问题 :
保持对偶问题可行
当所有的 ,则
即:保持对偶问
题可行,将原问
题由不可行化为
可行
?算法思想:
2.4 对偶单纯形法
( )Max Z
( )0?ib
( )0jjcz
( )Min S
( )0?ib
找出初始基本解,满足cj-zj≤0 (MaxZ)
bi>0? Y
最优解N
i=L
?0?Lja
Y
无解N
找出新的基本解,满足cj-zj≤0
?
?
?算法流程:
1 2 3 4 5 6
1 2 3 5
1 2 4 6
0, 1,2,3, 4,5, 6
1200 800 1600 1200 0 0
24 2
2 2 4 3
=+ + + + +
? ? ? +=? ? ? +=
? ?=
?
?
j j
MinS x x x x x x
x x x x
x x x x
x

解:标准型为
1 2 3 4
1 2 3
1 2 4
1200 +800x 1600 1200
2 + 4 2
2 +2 4 3
0, 1,2,3
=+ +
? +?
? +
? ?=? j
Min S x x x
x x x
x x x
xj
例题:
列入单纯形表:
Cj 1200 800 1600 1200 0 0
CB XB b x1 x2 x3 x4 x5 x6
0
0
X5
X6
-2
-3
-2 -1 -4 0 1 0
-2 -2 0 -4 0 1
Zj
cj-zj
0 0 0 0 0 0
1200 800 1600 1200 0 0

? ?0
0负检验数
?=?


i i L L
Lj K
Lj
Min b b b x
Min a xa
? 换入变量的确定:
? 换出变量的确定:
Cj 1200 800 1600 1200 0 0
CB XB b x1 x2 x3 x4 x5 x6
0
0
X5
X6
-2
-3
-2 -1 -4 0 1 0
-2 -2 0 -4 0 1
Zj
cj-zj
0 0 0 0 0 0
1200 800 1600 1200 0 0

Min{-1200/-2; -800/-2; -1200/-4}=300
-4 L
K
Cj 1200 800 1600 1200 0 0
CB XB b x1 x2 x3 x4 x5 x6
0
1200
X5
X4
-2
3/4
-2 -1 -4 0 1 0
1/2 1/2 0 1 0 -1/4
Zj
cj-zj
600 600 0 1200 0 -300
600 200 1600 0 0 300

-1
L
K
Cj 1200 800 1600 1200 0 0
CB XB b x1 x2 x3 x4 x5 x6
800
1200
X2
X4
2
-1/4
2 1 4 0 -1 0
-1/2 0 -2 1 1/2 -1/4
Zj
cj-zj
1000 800 800 1200 -200 -300
200 0 800 0 200 300

-2 L
K
Cj 1200 800 1600 1200 0 0
CB XB b x1 x2 x3 x4 x5 x6
800
1600
X2
X3
3/2
1/8
1 1 0 2 0 -1/2
1/4 0 1 -1/2 -1/4 1/8
Zj
cj-zj
1200 800 1600 800 400 200
0 0 0 400 400 200

?有非基变量的检验数为0,多重解
最优解为: 310, , ,0,0,0 , 140028
==
T
X Min S
◆ 小结
? 对偶单纯形法的算法思想
? 对偶单纯形法的算法流程及实现
? 与单纯形法的区别与联系
◆ 课后讨论
(1)对偶单纯形法是一种用来求解对偶问题的算法。
(2)对偶单纯形法可以替代大M法和两阶段法。 更多>> 简介:(1)对称性:对偶问题的对偶是原问题
0
MaxZ CX
AX b
X
=
? ?
?

0
MinS Yb
YA C
Y
=
? ?
?

--,--, 0MinS Yb YA C Y=? ?
证明:变换对偶问题模型
ax
0
M S Yb
YA C
Y
=?
? ?
?

0
MinZ CX
AX b
X
=?
? ?
?

2.3 对偶问题的性质
bYXC ?
(2)弱对偶性:若 是原问题的可行解, 是对偶问题的可行解,则存在有

X


Y
证明:
0
MaxZ CX
AX b
X
=
? ?
?

0
MinS Yb
YA C
Y
=
? ?
?

因 是原问题的可行解, 是对偶问题的可行解,所以有:
;Y AX Yb Y AX C X
bYMinS=
最优目标
XCMaxZ=
? 弱对偶性的图形解释
(3)可行解是最优解的性质:
若 是原、对的可行解,当YX ?,? bYXC =则: 是最优解YX ?,?
bYMinS=
最优
XCMaxZ=
(4)对偶定理
若原问题有最优解,那么对偶问题也有最优解,且原问题与对
偶问题最优目标函数值相等。
1? ?=BCY B
01 ? ABCC B
( )
( )
XABCCbBC
XBCCXNBCCXBBCCbBC
XBCCXNBCCbBC
XCXCXBCNXBCbBC
XCXCXC
X
X
X
CCCCXZ
XBNXBbBX
b
X
X
X
INBAX
BB
SBSNBNBBBB
SBSNBNB
SSNNSBNBB
SSNNBB
S
N
B
SNB
SNB
S
N
B
)(
)()()(
)()(
11
1111
111
111
111


?
?
?
?+=
?+?+?+=
?+?+=
++=
++=
?
?
?
?
?
?
?
?
?
?
==
=
=
?
?
?
?
?
?
?
?
?
?
=

01 ? ABCC B
? 检验数的推导:
(5)互补松弛性:若 分别是原问题和对偶问题的可行解,那
么 当且仅当 为最优解
YX ?,?
0?0?==XYXY SS 和
1
1
? ? ?0 , 0
? ? ?, 0 , 0
若 则有 即
若 即 则有
=
=
?==
? ?=
?
?
n
i ij j i si
j
n
ij j i si i
j
y a x b x
a x b x y
? 对偶变量的经济含义----影子价格
资源 的单位改变量引起目标函数值(Z )的改变量,
通常称为影子价格(shadow price)或边际价格(marginal
price)。
( )ib
◆小结
(1)对偶问题的基本性质
(2)影子价格 更多>> 简介:?企业经营活动
目标:提高效
益,利润最大
更新设备、改进工艺(硬件)
合理规划、改善管理(软件)
线性规划所研究的问题
投入不变,使工作成果达到最大
工作成果不变,使耗费达到最小
#同一个问题的两种提法,隐含着对偶原理
2.1 对偶问题及其数学模型
?常识:方形中:周长一定,正方形面积最大;面积一定,正方形周长最短。
?引例:有一机械厂在年度内计划生产甲乙两种产品,两种产品分别需要
在A,B,C,D四种不同机床上加工。各产品在各机床上所需的加工工时及每
种机床在年内可以提供的机器台时、单位产品获利如下表。问如何确定甲、
乙产品的产量,才能使工厂总利润最大?

A



B

C

D

单位利润
(元)


2
2
1
2
4
0
0
4
2
3
可供台时 1200 800 1600 1200





产 品
?
?
?
?

?
?
?
?
?
?
?+
?+
+=
0,
12004
16004
8002
120022
32
21
2
1
21
21
21
xx
x
x
xx
xx
xxMaxZ
模型分析:站在厂商的角度,如何安排生产,使利润达最大?
------原问题
解:设 和 分别表示甲乙两种产品的年产量,则有:1x 2x
解:设 分别表示A, B, C, D四种机床每台时出租
价格,则:
?建模分析:
?若厂商不生产、将机械设备出租赚取租金,厂商首先面临的问
题就是给出租设备定出合理价格
1 2 3 4, , ,y y y y
站在出租方:出租生产1单位甲所耗机床台时所得的租金收入不
能低于生产1单位甲所得到的销售利润:
2042 4321 ?+++ yyyy
同理,对于乙产品,有:
34022 4321 ?+++ yyyy
出租设备的总收入:
4321 120016008001200 yyyyS +++=
出租设备台时的总收入也就是承租人支付的承租总成本
? 站在承租人的角度,如何安排,使成本达最小?
-----对偶问题
2042 4321 ?+++ yyyy
34022 4321 ?+++ yyyy
4321 120016008001200 yyyyMinS +++=
0,,, 4321 ?yyyy
-----对偶问题数学模型
对偶问题
2042 4321 ?+++ yyyy
34022 4321 ?+++ yyyy
4321 120016008001200 yyyyMinS +++=
0,,, 4321 ?yyyy
原问题
?
?
?
?

?
?
?
?
?
?
?+
?+
+=
0,
12004
16004
8002
120022
32
21
2
1
21
21
21
xx
x
x
xx
xx
xxMaxZ
对偶理论表明:每一个线性规划问题都伴随着一个被称之为对偶
问题的线性规划问题,先提出来的称为原问题,与之对应的就称
为对偶问题;
更有趣的是,求出原问题解的同时也求出了对偶问题的解。 更多>> 简介:对偶问题
2042 4321 ?+++ yyyy
34022 4321 ?+++ yyyy
4321 120016008001200 yyyyMinS +++=
0,,, 4321 ?yyyy
原问题
?
?
?
?

?
?
?
?
?
?
?+
?+
+=
0,
12004
16004
8002
120022
32
21
2
1
21
21
21
xx
x
x
xx
xx
xxMaxZ
0
MaxZ CX
AX b
X
=
? ?
?
0
MinS Yb
YA C
Y
=
? ?
?

2.2 对偶问题模型的构建
0
MaxZ CX
AX b
X
=
? ?
?

0
MinS Yb
YA C
Y
=
? ?
?

?例
解:调整后,原问题变为 1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
6 3 5
2 3 16
2 5 10
6
6
0, 1,2,3j
MinS x x x
x x x
x x x
x x x
x x x
xj
=+ +
? + + ?
? + ?
? + +
? ? ?
? ?=?

y1
y3′
y3″
y2′
1 2 3 3
1 2 3 3
1 2 3 3
1 2 3 3
1 2 3 3
16 10 6 6
26
2 5 3
35
0, 0, 0, 0
? ? =? + ?
? ? ? + ?
? ? ? ? + ? ? ? ? + + ?
? ? ? ? ? ?
Max Z y y y y
y y y y
y y y y
y y y y
y y y y
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
16 +10 6
+2 6
2 +5 3
35
0, 0, 为自由变量
=+
+
? +? ? +
? ?
Max Z y y y
y y y
y y y
y y y
y y y
原问题
(MinS)
对偶问题
(MaxZ)
cj bi
A AT








正变量
≤ 负变量
= 自由变量
m 个 m 个



正变量 约




负变量 ≥
自由变量=
n 个 n 个

?对比分析原问题、对偶问题模型,有:
y2
y1
y3
?根据上表模型参数之间的对应关系,对偶问题模型可以直接写出:
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
16 +10 6
+2 6
2 +5 3
35
0, 0, 为自由变量
=+
+
? +? ? +
? ?
Max Z y y y
y y y
y y y
y y y
y y y
1 2 3
1 2 3
1 2 3
1 2 3
6 +3x 5
+2 3 16
2 +5 10
6
0, 1,2,3
=+
+
? + +=?
? ?=? j
Min S x x
x x x
x x x
x x x
xj
◆ 小结:
对偶问题模型构建方法:
(1)根据模型结构之间的对应关系
(2)根据模型参数之间的对应关系 更多>> 简介:5.4 多维动态规划问题
例 二维资源分配问题. 设有两种原料,数量各为 a 和 b 单位,需要分配用于生产
n 种产品。若分别用 xi、yi 单位的第一、二种原料用于生产第 i 种产品,其收入为
gi(xi,yi) 。问应如何分配这两种原料于 n 种产品的生产使总收入最大?
该问题的静态规划模型为
1 1 1ax ( , ) ( , )n n nM Z g x y g x y=+ +


?
=?
=+++
=+++
niyx
byyy
axxx
ii
n
n
,,2,1 ,0,
21
21
?
?
?
动态规划模型:
(1)按生产 n 种产品划分为 n 个阶段。
(2)状态变量 :第 阶段初拥有的第一种原料的数量,
:第 阶段初拥有的第二种原料的数量,
决策变量 :用于生产第 种产品的第一种原料数,
:用于生产第 种产品的第二种原料数。
允许决策集合
?
?
?


kk
kk
kkk Ry
SxyxD 0
0 :),(
(3)状态转移方程:
(4)指标函数:
(5)指标递推方程
?
?
?
=
=+=
+++
+++
0),(
,,2,1 )},,(),(max{),(
111
111
nnn
kkkkkkkkk
RSf
nkRSfyxgRSf ?
k+1 k k
k+1 k k
S=S -x
R=R -y
k k kg (x ,y )
kS
kx
kR
k
kY
例 二维背包问题.有n种不同类型的货物要由一运输工具装运。设第i种货
物共有mi件,每件价值为ci,重量为wi,体积为vi,运输工具的载重量
为a,容积为b。问各种货物应装载多少件,才能在既不超载又不超容
的条件下,使所装载的货物的总价值为最大?
设xi表示第i种类型货物的装载件数,则问题的静态规划模型为
?=
=
n
i
ii xcZ
1
max
?
?
?
?
?
?
?
?
?
=?
?
? ?
? ?
=
=
nix
mx
bxv
axw
i
ii
n
i
ii
n
i
ii
,,2,1 ,0
1
1
?
动态规划模型:
(1)每装一种货物作为一阶段,共分为 阶段。
(2)状态变量 :第 阶段初运输工具拥有的装载量,
:第 阶段初运输工具拥有的容积,
决策变量 :第 种货物的装载件数。
允许决策集合 .},,min{0 :)( 且为整数
k
k
k
k
kkkk v
R
w
SmxxD
(3)状态转移方程:
(4)指标函数:
(5)指标递推方程


?
=
=+=
+++
++
0)(
,,2,1 )},({max),(
1,11
11
nnn
kkkkxkkk
RSf
nkSfxcRSf
k
?
k+1 k k k
k+1 k k k
S=S -w x
R=R -v x
k k k k k kd (S ,R ,x )=c x
kS
kx
kR
k
n
◆多维动态规划问题的求解
例 购销量计划问题. 某公司经售某种货物,仓库容量 w=600件。公司
每月初为下个月订购货物,月末收到。订购数量只受仓库容量的限制,
即本月末剩余货物数量与订购量之和不得超过600件。还假定每个月
销售量由公司根据具体情况决定,最多不超过月初仓库具有的货物数
量。1至4月的单位购货成本及销售价格如表下所示。若1月初有200件
存货,问如何安排每个月的购进与销售数量,使四个月的利润最大?
1月 2月 3月 4月
购货成本(元/件)Ck
销售价格(元/件)Pk
40
45
38
42
40
39
42
44
解 问题的动态规划模型为
(1)按月份分为4个阶段。
(2)状态变量 :第 阶段初的库存量,
决策变量 :第 阶段的订购量,
决策变量 :第 阶段的销售量。
(3)状态转移方程
(4)指标函数
(5)指标递推方程


?
=
=+?=++
0)(
4,3,2,1 )},({max)(
55
11,
Sf
kSfyCzPSf kkkkkkzykk
kk
k k k k S=S +y -z
k k k k k k k kd (S ,y ,z )=P z -C y
kS
kz
ky
k
k=4 时
)}(max{)( 11 +++?=kkkkkkkk SfyCzPSf
f4(S4)={44z4-42y4}
(0, 0) (0,w-S4) (S4, w) (S4, 0)
S4 0 42S4-42w 44S4-42w 44S4
(z4
*, y4
*)
(S4, 0)
f4(S4)
44S4
kk
k k k
kk
zS
S +y -z
z , y 0
?
?
?
w
4 4 4 4 4 4f (S )=Max{44z -42y +f (S )}
zk
zk=Sk
Sk
Sk+yk-zk=w
(0,0)
(Sk,0)
(0,w-Sk)
k=3 时
f3(S3)={-5z3+4y3+44S3}
(0, 0) (0,w-S3) (S3, w) (S3, 0)
S3 44S3 4w+40S3 4w+39S3 39S3
(z3
*, y3
*)
(0,w-S3)
f3(S3)
4w+40S3
(因w≥S3,所以4w+40S3≥44S3)
k=2 时
f2(S2)={2z2+2y2+40S2 + 4w}
(z2
*,y2
*) f2(S2)(0, 0) (0,w-S2) (S2, w) (S2, 0)
S2 40S2 + 4w 38S2 + 6w 42S2 +6w 42S2 + 4w (S2, w) 42S2 +6w
3 3 3 3 4 4
3 3 3 3 3
3 3 3
f (S )=ax{39z -40y +f (S )}
=ax{39z -40y +44(S +y -z )}
=Max{-5z +4y +44S }
M
M

f1(S1)={3z1+2y1+4S1 + 6w}
(z1
*,y1
*) f1(S1)(0, 0) (0,w-S1) (S1, w) (S1, 0)
S1 42S1 + 6w 40S1 + 8w 45S1 +8w 45S1 + 6w (S1, w) 45S1 +8w
已知 ,w=600,
∴ (元)
最优策略为
月份
1 200 600
2 600 600
3 0 0
4 600 0
1 1 1 f (S )=45S +8w=13800
kS ?
kz ?
ky
=1k
1 200=S
1=200S
2 1 1 1S=600+ ?=S y z
3 600 600 600 600=+ ?=S
4 600 0 0 600=+ ?=S 更多>> 简介:决策论/OR
专题八 决策论---单目标决策
Decision Theory----- single objective decision
8.1 决策论的基本知识
8.2 风险型决策问题
8.3 不确定型决策问题
决策论/OR
8.2 风险型决策问题
?决策准则:
(1)最大概率准则
?基本思想:选择一个概率最大的状态进行决策,将风险型转化为确定型。
?注意:仅适用于各状态概率值差别较大
(2)最大期望值准则
?基本思想:把每个方案的效益值看做离散随机变量,然后求出各方案的
效益期望值,加以比较后选择效益期望值最大的方案作为最优方案.
决策论/OR
? 决策方法
(1)矩阵法
利用矩阵乘法的计算原理来求方案的效益期望值,再通过比较进行决策.
状态
方案
S1 S2 … Sn
期望效益值
E(Ai)
P1 P2 … Pn
A1
A2

Am
c11 c12 … c1n
c21 c22 … c2n
… … … …
cm1 cm2 … cmn
E(A1)
E(A2)

E(Am)
概率
效益值
决策论/OR
( ) 1 1 2 2=+ + + + +i i i ij j in nE A c P c P c P c P
( )
( )
( )
( )
11 1111 12
221 22 2 22
12
12




=




j n
jn
ji i ij ini
m m mj mn nm
cEA Pccc
Pc c c cEA
Pc c c cEA
c c c c PEA
决策论/OR
产品销路
效益值(万)
生产方案
好(S1) 一般(S2) 差(S3)
大批量(A1)
中批量(A2)
小批量(A3)
20
15
13
11
13
12
5
6
10
0.20.50.3
?
?
?
?
?
?
?
?
?
?
=
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
=
?
?
?
?
?
?
?
?
?
?
9.11
2.12
5.12
2.0
5.0
3.0
10 12 13
6 13 15
5 11 20
)(
)(
)(
3
2
1
AE
AE
AE
E(Ai)
12.5
12.2
11.9

最优决策:大批量生产
例 用矩阵法进行决策
决策论/OR
?矩阵法是根据矩阵乘法的特点来求各方案的效益期望值.
?适用于单级决策问题.
?对于多级决策问题一般采用决策树法.
矩阵法小结:
决策论/OR
(2)决策树法
按逻辑关系画出的树形图,利用最大期望值准则对风险型决策问题
进行决策的一种方法。
它既可以解决单级决策问题也可以解决多级决策问题。
决策树:把方案、状态、结果和状态概率等用一棵树来表示,将效
益期望值也标在树上,直接通过比较进行决策.
决策论/OR
?决策树构图(组成):
①决策点与方案枝
用方块节点表示.从它引出的分枝称为方案分枝.
A1
A2
A3
方案分枝
决策论/OR
②机会点(概率点)与概率枝
用圆圈节点表示.其上方数字表示该方案的效益期望值,从它引
出的分枝称为概率分枝.每条分枝代表一种状态.
S1, P(S1)
S2 , P(S2)
S3 , P(S3)
概率分枝
效益期望值
决策论/OR
S1, P(S1)
S2 , P(S2)
S3 , P(S3)
c11
c12
c13
③结果节点
用三角节点表示.表示某一方案在某一状态下的结果(效益值).
决策论/OR
?单级决策问题:只包含一项决策问题,在决策树中只有一个决策点.
产品销路
效益值(万)
生产方案
好(S1) 一般(S2) 差(S3)
大批量(A1)
中批量(A2)
小批量(A3)
20
15
13
11
13
12
5
6
10
例:用决策树法进行决策
决策论/OR
解:①依题意画出决策树,标上原始数据;
②计算各机会点的期望值;
③按期望值准则进行决策.
1
2
A1
3
A2
4
A3
销路好, P(S1)=0.3 20
销路一般, P(S2)=0.5 11
销路差, P(S3)=0.2 5
销路好, P(S1)=0.3 15
销路一般, P(S2)=0.5 13
销路差, P(S3)=0.2 6
销路好, P(S1)=0.3 13
销路一般, P(S2)=0.5 12
销路差, P(S3)=0.2 10
12.5
12.2
11.9
12.5
最优方案为A1:大批量生产。
决策论/OR
?多级决策问题
包含两级及其以上的决策问题.
例 某科研单位考虑向某工厂提出开发一种新产品的建议.为提出此建
议需花2万元做一些前期工作. 根据经验及对该工厂和竞争者的估计,
建... 更多>> 简介:专题十 排队论
Queueing Theory
10.1 排队论概述
10.2 顾客达到流与服务时间的分布
10.3 生灭过程及其状态平衡方程
10.4 M/M/s 等待制排队模型
10.5 排队服务系统的优化
10.2 顾客到达流与服务时间的分布
(1)事件流
? 事件流:同类事件在随机时刻,一个接一个地发生的序列.
? 事件流可以看作“点”在时间轴上的分布:
0 t
0 t
? 流的强度( λ ):单位时间内,事件发生的平均数.
? 正则流:事件发生的间隔时间相等、固定.
? 平稳流:事件发生的概率与时间无关.即发生的概率只与 的
长度有关,而与 在时间轴上的位置无关,概率近为 .
? 无后效性的流:每个事件发生的时刻互不相关.
? 普通性的流:在充分小的时间间隔中,最多有一个事件发生.
Δt Δt
? 事件流有以下几个特征:
?t
?t t
(2)泊松流 (Poisson流,也称最简单流)
?同时具有平稳性、无后效性和普通性的事件流.
① 概率分布,即在时间t 内到达n 个顾客的概率:
n
()() !
n
ttP t en
?=
② 数学期望: .
? 若取单位时间,即 .
※描述了在给定时间内,系统到达顾客数这一特征.
( ) ?=E N t t
( )1, 则 ?==t E N
(3)负指数分布
? 描述泊松流的另一重要特征:相邻两顾客到达的间隔时间 .
? 间隔时间 小于等于时间 的概率:

=?=? ?
=?=? ?0
( ) ( ) 1 ( )
1 ( ) 1 ( 0)
T
t
F t P T t P T t
P t e t
f ( ) ( 0)t
T t e t ?=?
? 的分布密度函数:
? 数学期望:
1()ET
?=
T
T t
T
※若到达顾客流是泊松流,则到达间隔时间 服从指数分布.
※泊松流具有可加性.即 .
T
1 2 1 2,? ? ? ?→+
? 约定:对于一个输入流和输出流都是泊松流(或者说到达间隔时间
和服务间隔时间都服从指数分布)的服务系统,习惯地描述为到达
流服从泊松分布,服务间隔时间服从指数分布.
排队服
务系统
到达流
泊松流 ( λ )
到达间隔时间
负指数分布
(1/λ)
服务流
泊松流 ( μ )
服务间隔时间
负指数分布
(1/μ)
小结:
(1)泊松流的三个基本性质:平稳性、无后效性和普通性;
(2)泊松流和负指数分布的概率分布式、期望值表达式;
(3)将它们引入排队系统中所表征的基本含义;
(4)两个分布之间的内在联系。 更多>>
上一篇:Italy 下一篇:没有了

刘毅传书