管理运筹学(ppt)
管理运筹学(ppt)详细内容
管理运筹学(ppt)
管 理 运 筹 学
绪论
线性规划(运输问题)
整数规划
动态规划
存储论
排队论
对策论
决策分析
第一章 绪论
运筹学(Operational Research) 直译为“运作研究”
运筹学是应用分析、试验、量化的方法,对经济管理系统中的人力、物力、财力等资源进行统筹安排,为决策者提供有依据的最优方案,以实现最有效的管理。
运筹学有广泛应用
运筹学的产生和发展
§1 决策、定量分析与管理运筹学
决策过程(问题解决的过程):
1)提出问题:认清问题
2)寻求可行方案:建模、求解
3)确定评估目标及方案的标准或方法、途径
4)评估各个方案:解的检验、灵敏性分析等
5)选择最优方案:决策
6)方案实施:回到实践中
7)后评估:考察问题是否得到完满解决
1)2)3):形成问题;4)5)分析问题:定性分析与定量分析。构成决策。
§2 运筹学的分支
线性规划
非线性规划
整数规划
图与网络模型
存储模型
排队论
排序与统筹方法
决策分析
动态规划
预测
§3运筹学在工商管理中的应用
生产计划:生产作业的计划、日程表的编排、合理下
料、配料问题、物料管理等
库存管理:多种物资库存量的管理,库存方式、库存
量等
运输问题:确定最小成本的运输线路、物资的调拨、
运输工具的调度以及建厂地址的选择等
人事管理:对人员的需求和使用的预测,确定人员编
制、人员合理分配,建立人才评价体系等
市场营销:广告预算、媒介选择、定价、产品开发与
销售计划制定等
财务和会计:预测、贷款、成本分析、定价、证券管
理、现金管理等
*** 设备维修、更新,项目选择、评价,工程优化设计与管理等
运筹学方法使用情况(美1983)
运筹学的推广应用前景
据美劳工局1992年统计预测: 运筹学应用分析人员需求从1990年到2005年的增长百分比预测为73%,增长速度排到各项职业的前三位.
结论:
运筹学在国内或国外的推广前景是非常广阔的
工商企业对运筹学应用和需求是很大的
在工商企业推广运筹学方面有大量的工作要做
第二章 线性规划的图解法
在管理中一些典型的线性规划应用
合理利用线材问题:如何下料使用材最少
配料问题:在原料供应量的限制下如何获取最大利润
投资问题:从投资项目中选取方案,使投资回报最大
产品生产计划:合理利用人力、物力、财力等,使获利最大
劳动力安排:用最少的劳动力来满足工作的需要
运输问题:如何制定调运方案,使总运费最小
线性规划的组成:
目标函数 Max f 或 Min f
约束条件 s.t. (subject to) 满足于
决策变量 用符号来表示可控制的因素
§1问题的提出
例1. 某工厂在计划期内要安排甲、乙两种产品的生产,已知生产单位产品所需的设备台时及A、B两种原材料的消耗以及资源的限制,如下表:
问题:工厂应分别生产多少单位甲、乙产品才能使工厂获利最多?
线 性 规 划 模 型
一般形式
目标函数: Max (Min) z = c1 x1 + c2 x2 + … + cn xn
约束条件: s.t. a11 x1 + a12 x2 + … + a1n xn ≤ ( =, ≥ )b1
a21 x1 + a22 x2 + … + a2n xn ≤ ( =, ≥ )b2
…… ……
am1 x1 + am2 x2 + … + amn xn ≤ ( =, ≥ )bm
x1 ,x2 ,… ,xn ≥ 0
标准形式
目标函数: Max z = c1 x1 + c2 x2 + … + cn xn
约束条件: s.t. a11 x1 + a12 x2 + … + a1n xn = b1
a21 x1 + a22 x2 + … + a2n xn = b2
…… ……
am1 x1 + am2 x2 + … + amn xn = bm
x1 ,x2 ,… ,xn ≥ 0
线性规划标准型
线性规划标准型
线性规划标准型
线性规划标准型
线性规划标准型
线性规划标准型
线性规划标准型
线性规划标准型
线性规划标准型
线性规划标准型
线性规划标准型
线性规划标准型
§2 线 性 规 划 的 图 解 法
例1.
目标函数:
Max z = 50 x1 + 100 x2
约束条件:
s.t.
x1 + x2 ≤ 300 (A)
2 x1 + x2 ≤ 400 (B)
x2 ≤ 250 (C)
x1 ≥ 0 (D)
x2 ≥ 0 (E)
得到最优解:
x1 = 50, x2 = 250
最优目标值 z = 27500
线性规划图解法的步骤
(2)对每个不等式(约束条件),先取其等式在坐标系中作直线,然后确定不等式所决定的半平面。若各半平面交出来的公共区域存在,显然,其中的点满足所有的约束条件,称这样的点为此线性规划的可行解,全体可行解的集合称为可行集或可行域。若这样的公共区域不存在,则该线性规划问题无可行解。
(3)任意给定目标函数一个确定的值,作出对应的目标函数等值线,并确定该族等值线平行移动时目标函数值增加的方向。然后平移目标函数的等值线,使其达到既与可行域有交点又不可能使值再增加的位置(有时交于无穷远处,此时称无有限最优解)。此时,目标函数等值线与可行域的交点即此线性规划的最优解(一个或多个),此目标函数的值即最优值。
进 一 步 讨 论
线性规划的标准化内容之一: —— 引入松驰变量(含义是资源的剩余量)
例1 中引入 s1, s2, s3 模型化为
目标函数:Max z = 50 x1 + 100 x2 + 0 s1 + 0 s2 + 0 s3
约束条件:s.t. x1 + x2 + s1 = 300
2 x1 + x2 + s2 = 400
x2 + s3 = 250
x1 , x2 , s1 , s2 , s3 ≥ 0
对于最优解 x1 =50 x2 = 250 , s1 = 0 s2 =50 s3 = 0
说明:生产50单位甲产品和250单位乙产品将消耗完所有可能的设备台时数及原料B,但对原料A则还剩余50千克。
进 一 步 讨 论(续)
解的性质:
1) 线性规划的最优解如果存在,则必定有一个顶点(极点)是最优解;
2) 有的线性规划问题存在无穷多个最优解的情况;
3) 有的线性规划问题存在无有限最优解的情况,也称无解;
4) 有的线性规划问题存在无可行解的情况。
§3图解法的灵敏度分析
灵敏度分析:建立数学模型和求得最优解后,研究线性规划的一个或多个参数(系数)ci , aij , bj 变化时,对最优解产生的影响。
3.1 目标函数中的系数 ci 的灵敏度分析
考虑例1的情况, ci 的变化只影响目标函数等值线的斜率,
目标函数 z = 50 x1 + 100 x2
在 z = x2 (x2 = z 斜率为0 ) 到 z = x1 + x2 (x2 = -x1 + z 斜率为 -1 )之间时,
原最优解 x1 = 50,x2 = 100 仍是最优解。
一般情况:
z = c1 x1 + c2 x2 写成斜截式 x2 = - (c1 / c2 ) x1 + z / c2
§3图解法的灵敏度分析(续)
目标函数等值线的斜率为 - (c1 / c2 )
当 -1 - (c1 / c2 ) 0 (*) 时,原最优解仍是最优解
假设产品乙的利润100元不变,即 c2 = 100,代到式(*)并整理得
0 c1 100
假设产品甲的利润 50 元不变,即 c1 = 50 ,代到式(*)并整理得
50 c2 +
假若产品甲、乙的利润均改变,则可直接用式(*)来判断。
假设产品甲、乙的利润分别为60元、55元,则
- 2 - (60 / 55) - 1
那麽,最优解为 z = x1 + x2 和 z = 2 x1 + x2 的交点 x1 = 100,x2 = 200 。
3.2 约束条件中右边系数 bj 的灵敏度分析(续)
解释:原最优解没有把原料 A 用尽,有50千克的剩余,因此增加10千克值增加了库存,而不会增加利润。
在一定范围内,当约束条件右边常数增加1个单位时
1)若约束条件的对偶价格大于0,则其最优目标函数值得到改善(变好);
2)若约束条件的对偶价格小于0,则其最优目标函数值受到影响(变坏);
3)若约束条件的对偶价格等于0,则其最优目标函数值不变。
线性规划问题的计算机求解(1)
管理运筹学软件1.0版使用说明:(演示例1)
一、系统的进入与退出:
1、在WINDOWS环境下直接运行main.exe文件,或者在DOS下UCDOS中文平台环境下运行,也可直接运行各可执行程序。
2、退出系统的方法可以在主菜单中选退出项,也可按Ctrl+Break键直接退出。
3、在WINDOWS环境下直接运行软件,如果出现乱码,那是因为启用了全屏幕方式,解决办法是按ALT+ENTER键, 即可转换成非全屏的界面(一般就会消除乱码,如果还是乱码,可以点击菜单的“汉”选项);若要每次启动程序都没有乱码,则需要修改屏幕设置的相应属性。具体方法是:在非全屏界面下点击菜单的“属性”选项,再选择“窗口”选项,然后选中其中的“窗口”项,并取消“启动时恢复设置”项,这样就可保证每次运行软件时以非全屏方式显示。
线性规划问题的计算机求解(1)续
二、输入部分:
1、线性规划、整数规划的目标函数和约束的输入必须按由小到大的序号顺序输入,同时约束变量必须放在运算符的左侧。如(x1+x2-x3=0,不能输为x2-x3+x1=0;x1-x2+x3=0,不能输为x1+x3=x2)
2、输入的约束中不包括“≥”或“≤”,而是用“>”或“<”代替,这不会影响求解。如 对于约束 X1≥2, 则输入 X1>2, 而不是X1≥2。
线性规划问题的计算机求解(2)续
* 允许增加量 = 上限 - 现在值 c1 的允许增加量为 100 - 50 = 50
b1 的允许增加量为 325 - 300 = 25
* 允许减少量 = 现在值 - 下限 c2 的允许减少量为 100 - 50 = 50
b3 的允许减少量为 250 - 200 = 50
* 允许增加的百分比 = 增加量 / 允许增加量
* 允许减少的百分比 = 减少量 / 允许减少量
考虑前面例题的对偶问题: 若设备和原料都用于外协加工,工厂收取加工费。试问:设备工时和原料A、B 各如何收费才最有竞争力? 设 y1 ,y2 ,y3 分别为每设备工时、 原料 A、B每单位的收取费用。
线性规划对偶问题
Max z = 50x1 + 100x2
s.t. x1 + x2 ≤300
2x1 + x2 ≤ 400
x2 ≤ 250
x1 , x2 ≥ 0
Min f = 300y1+ 400y2 + 250y3
s.t. y1+2y2 ≥50 (不少于甲产品的利润)
y1+y2+y3 ≥100 (不少于乙产品的利润)
y1,y2 ,y3 ≥0
线性规划对偶问题
对偶定义
对称形式: 互为对偶
(LP) Max z = cT x (DP) Min f = bT y
s.t. Ax ≤ b s.t. AT y ≥ c
x ≥ 0 y ≥ 0
“Max -- ≤ ” “Min-- ≥”
线性规划对偶问题
一对对称形式的对偶规划之间具有下面的对应关系。
(1)若一个模型为目标求“极大”,约束为“小于等于”的不等式,则它的对偶模型为目标求“极小”,约束是“大于等于”的不等式。即“max,≤”和“min,≥”相对应。
线性规划对偶问题
(2)从约束系数矩阵看:一个模型中为A,则另一个模型中为AT。一个模型是m个约束,n个变量,则它的对偶模型为n个约束,m个变量。
(3)从数据b、C 的位置看:在两个规划模型中,b和C 的位置对换。
(4)两个规划模型中的变量皆非负。
线性规划对偶问题
非对称形式的对偶规划
一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。
对于非对称形式的规划,可以按照下面的对应关系直接给出其对偶规划:
(1)将模型统一为“max,≤”或“min,≥” 的形式,对于其中的等式约束按下面(2)、(3)中的方法处理;
(2)若原规划的某个约束条件为等式约束,则在对偶规划中与此约束对应的那个变量取值没有非负限制;
线性规划对偶问题
(3)若原规划的某个变量的值没有非负限 制,则在对偶问题中与此变量对应的那个约束为等式。
下面对关系(2)作一说明。对于关系(3)
可以给出类似的解释。
设原规划中第一个约束为等式:
a11x1 + … + a1nxn = b1
那么,这个等式与下面两个不等式等价
线性规划对偶问题
a11x1+…+a1nxn≥b1
a11x1+…+a1nxn≤b1
这样,原规划模型可以写成
maxZ=c1x1+∧+cnxn
a11x1+∧+a1nxn≤b1
-a11x1-∧-a1nxn≤-b1
M
am1x1+∧+amnxn≤bm
xj≥0,j=1,2, ∧,m
线性规划对偶问题
此时已转化为对称形式,直接写出对偶规划
minf=b1y1’-b1y1’’+b2y2+∧+bmym
a11y1’-a11y1’’∧+am1ym≥c1
a12y1’-a12y1’’∧+am2ym≥c2
M
a1ny1’-a1ny1’’∧+amnym≥cn
y1’,,y1’’,y2,∧,ym≥0,y1
这里,把y1看作是y1=y1’-y1’’,
于是y1没有非负限制,关系(2)的说明完毕。
线性规划对偶问题
例3.1写出下面线性规划的对偶规划模型:
maxZ=x1-x2+5x3-7x4
x1+3x2-2x3+x4=25
2x1+7x3+2x4≥-60
2x1+2x2-4x3≤30
-5≤x4≤10,x1,x2, ≥0,x3没有非负限制
解先将约束条件变形为“≤”形式
线性规划对偶问题
x1+3x2-2x3+x4=25
-2x1-7x3-2x4 ≤60
2x1+2x2-4x3 ≤30
x4 ≤10
-x4 ≤5
x1≥0,x2≥0,x3,x4没有非负限制
再根据非对称形式的对应关系,直
接写出对偶规划
线性规划对偶问题
minf =25y1+60y2+30y3+10y4+5y5
y1-2y2+2y3≥1
3y1+2y3 ≥-1
-2y1-7y2-4y3=5
y1-2y2+y4-y5= -7
y1没有非负限制,y2,y3,y4,y5≥0
线性规划对偶问题
影子价格 —— 是一个向量,它的分量表示最优目标值随相应资源数量变化的变化率。
若x*,y* 分别为(LP)和(DP)的最优解,
那么, cT x* = bT y* 。
根据 f = bTy*=b1y1*+b2y2*++bmym*
可知 f / bi = yi*
yi* 表示 bi 变化1个单位对目标 f 产生的影响,称 yi* 为 bi的影子价格。
线性规划对偶问题
影子价格的经济含义
(1)影子价格是对现有资源实现最大效益时的一种估价
企业可以根据现有资源的影子价格,对资源的使用有两种考虑:第一,是否将设备用于外加工或出租,若租费高于某设备的影子价格,可考虑出租该设备,否则不宜出租。第二,是否将投资用于购买设备,以扩大生产能力,若市价低于某设备的影子价格,可考虑买进该设备,否则不宜买进。
线性规划对偶问题
(2)影子价格表明资源增加对总效益产生的影响,根据理论“设x0和y0分别为原规划(P )和对偶规划(D)的可行解,当cx0=bty0时,x0,y0分别是两个问题的最优解”可知,在最优解的情况下,有关系:
Z*=f *=b1y1*+b2y2*∧+bmym*根
因此,可以将z*看作是bi,i=1,2,…,m的函数,对bi求偏导数可得到:
﹠z*
=yi*i=1,2, ∧,m
﹠bi
这说明,如果右端常数增加一个单位,则目标函数值的增量将是:
yi*,i=1,2, ∧,m
线性规划对偶问题
影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力,考虑增加设备,就应该从影子价格高的设备入手。这样可以用较少的局部努力,获得较大的整体效益。
线性规划对偶问题
需要指出,影子价格不是固定不变的,当约束条件、产品利润等发生变化时,有可能使影子价格发生变化。另外,影子价格的经济含义是指资源在一定范围内增加时的情况,当某种资源的增加超过了这个“一定的范围”时,总利润的增加量则不是按照影子价格给出的数值线性地增加。
线性规划在工商管理中的应用(1)续
解:设 xi 表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的
数学模型。
目标函数: Min x1 + x2 + x3 + x4 + x5 + x6
约束条件:s.t. x1 + x6 ≥ 60
x1 + x2 ≥ 70
x2 + x3 ≥ 60
x3 + x4 ≥ 50
x4 + x5 ≥ 20
x5 + x6 ≥ 30
x1,x2,x3,x4,x5,x6 ≥ 0
线性规划在工商管理中的应用(2)续
解:设 xi ( i = 1~7)表示星期一至日开始休息的人数,这样我们建立如下的
数学模型。
目标函数: Min x1 + x2 + x3 + x4 + x5 + x6 + x7
约束条件:s.t. x1 + x2 + x3 + x4 + x5 ≥ 28
x2 + x3 + x4 + x5 + x6 ≥ 15
x3 + x4 + x5 + x6 + x7 ≥ 24
x4 + x5 + x6 + x7 + x1 ≥ 25
x5 + x6 + x7 + x1 + x2 ≥ 19
x6 + x7 + x1 + x2 + x3 ≥ 31
x7 + x1 + x2 + x3 + x4 ≥ 28
x1,x2,x3,x4,x5,x6,x7 ≥ 0
线性规划在工商管理中的应用(3)续
解:设 x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数, x4,x5 分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。
求 xi 的利润:利润 = 售价 - 各成本之和
可得到 xi (i = 1,2,3,4,5) 的利润分别为 15、10、7、13、9 元。
这样我们建立如下的数学模型。
目标函数: Max 15x1 + 10x2 + 7x3 + 13x4 + 9x5
约束条件: s.t. 5x1 + 10x2 + 7x3 ≤ 8000
6x1 + 4x2 + 8x3 + 6x4 + 4x5 ≤ 12000
3x1 + 2x2 + 2x3 + 3x4 + 2x5 ≤ 10000
x1,x2,x3,x4,x5 ≥ 0
线性规划在工商管理中的应用(4)续
解:设 xijk 表示第 i 种产品,在第 j 种工序上的第 k 种设备上加工的数量。
利润 = [(销售单价 - 原料单价)* 产品件数]之和 - (每台时的设备费用*设备实际使用的总台时数)之和。 这样我们建立如下的数学模型:
Max 0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123
s.t. 5x111 + 10x211 ≤ 6000 ( 设备 A1 )
7x112 + 9x212 + 12x312 ≤ 10000 ( 设备 A2 )
6x121 + 8x221 ≤ 4000 ( 设备 B1 )
4x122 + 11x322 ≤ 7000 ( 设备 B2 )
7x123 ≤ 4000 ( 设备 B3 )
x111+ x112- x121- x122- x123 = 0 (Ⅰ产品在A、B工序加工的数量相等)
x211+ x212- x221 = 0 (Ⅱ产品在A、B工序加工的数量相等)
x312 - x322 = 0 (Ⅲ产品在A、B工序加工的数量相等)
xijk ≥ 0 , i = 1,2,3; j = 1,2; k = 1,2,3
线性规划在工商管理中的应用(5)续
设 x1,x2,x3,x4,x5 分别为上面前 5 种方案下料的原材料根数。
这样我们建立如下的数学模型。
目标函数: Min x1 + x2 + x3 + x4 + x5
约束条件: s.t. x1 + 2x2 + x4 ≥ 100
2x3 + 2x4 + x5 ≥ 100
3x1 + x2 + 2x3 + 3x5 ≥ 100
x1,x2,x3,x4,x5 ≥ 0
线性规划在工商管理中的应用(6)续
解:设 xij 表示第 i 种(甲、乙、丙)产品中原料 j 的含量。这样我们建立数学模型时,要考虑:
对于甲: x11,x12,x13;
对于乙: x21,x22,x23;
对于丙: x31,x32,x33;
对于原料1: x11,x21,x31;
对于原料2: x12,x22,x32;
对于原料3: x13,x23,x33;
目标函数: 利润最大,利润 = 收入 - 原料支出
约束条件: 规格要求 4 个;
供应量限制 3 个。
线性规划在工商管理中的应用(7)续
问:
a)应如何确定这些项目的每年投资额,使得第五年年末拥有资金的本利金额为最大?
b)应如何确定这些项目的每年投资额,使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小?
解: 1)确定决策变量:连续投资问题
设 xij ( i = 1~5,j = 1~4)表示第 i 年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的决策变量:
A x11 x21 x31 x41 x51
B x12 x22 x32 x42
C x33
D x24
线性规划在工商管理中的应用(7续)
2)约束条件:
第一年:A当年末可收回投资,故第一年年初应把全部资金投出去,于是 x11+ x12 = 200;
第二年:B次年末才可收回投资,故第二年年初有资金1.1 x11,于是 x21 + x22+ x24 = 1.1x11;
第三年:年初有资金 1.1x21+ 1.25x12,于是 x31 + x32+ x33 = 1.1x21+ 1.25x12;
第四年:年初有资金 1.1x31+ 1.25x22,于是 x41 + x42 = 1.1x31+ 1.25x22;
第五年:年初有资金 1.1x41+ 1.25x32,于是 x51 = 1.1x41+ 1.25x32;
B、C、D的投资限制: xi2 ≤ 30 ( i =1、2、3、4 ),x33 ≤ 80,x24 ≤ 100
线性规划在工商管理中的应用(7续)
3)目标函数及模型:
a) Max z = 1.1x51+ 1.25x42+ 1.4x33 + 1.55x24
s.t. x11+ x12 = 200
x21 + x22+ x24 = 1.1x11;
x31 + x32+ x33 = 1.1x21+ 1.25x12;
x41 + x42 = 1.1x31+ 1.25x22;
x51 = 1.1x41+ 1.25x32;
xi2 ≤ 30 ( i =1、2、3、4 ),x33 ≤ 80,x24 ≤ 100
xij ≥ 0 ( i = 1、2、3、4、5;j = 1、2、3、4)
b) Min f = (x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24
s.t. x11+ x12 = 200
x21 + x22+ x24 = 1.1x11;
x31 + x32+ x33 = 1.1x21+ 1.25x12;
x41 + x42 = 1.1x31+ 1.25x22;
x51 = 1.1x41+ 1.25x32;
xi2 ≤ 30 ( i =1、2、3、4 ),x33 ≤ 80,x24 ≤ 100
1.1x51 + 1.25x42+ 1.4x33+ 1.55x24 ≥ 330
xij ≥ 0 ( i = 1、2、3、4、5;j = 1、2、3、4)
运 输 问 题(1)
§1 运 输 模 型
例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示,问:应如何调运可使总运输费用最小?
运 输 问 题(1)续
解: 产销平衡问题: 总产量 = 总销量
设 xij 为从产地Ai运往销地Bj的运输量,得到下列运输量表:
运 输 问 题(2)
设 xij 为从产地Ai运往销地Bj的运输量,得到下列一般运输量问题的模型:
m n
Min f = cij xij
i = 1 j = 1
n
s.t. xij = si i = 1,2,…,m
j = 1
m
xij = dj j = 1,2,…,n
i = 1
xij ≥ 0 (i = 1,2,…,m ; j = 1,2,…,n)
运 输 问 题(2)续
变化:
1)有时目标函数求最大 如求利润最大或营业额最大等;
2)当某些运输线路上的能力有限制时,模型中可直接加入(等式或不等式)约束;
3)产销不平衡时,可加入虚设的产地(销大于产时)或销地(产大于销时)。
运 输 问 题(3)续
例3、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示,问:应如何调运可使总运输费用最小?
解:增加一个
虚设的产地
运输费用为0
运输问题(4)续§3 运输问题的应用
解: 根据题意,作出产销平衡与运价表:
这里 M 代表一个很大的正数,其作用是强迫相应的 x31、 x33、 x34取值为0。
运输问题(5)续§3 运输问题的应用
解: 根据题意,作出产销平衡与运价表:
最低要求必须满足,因此把相应的虚设产地运费取为 M ,而最高要求与最低要求的差允许按需要安排,因此把相应的虚设产地运费取为 0 。对应 4”的销量 50 是考虑问题本身适当取的数据,根据产销平衡要求确定 D的产量为 50。
运输问题(6)续§3 运输问题的应用
解: 设 xij为第 i 季度生产的第 j 季度交货的柴油机数目,那末应满足:
交货:x11 = 10 生产:x11 + x12 + x13 + x14 ≤ 25
x12 + x22 = 15 x22 + x23 + x24 ≤ 35
x13 + x23 + x33 = 25 x33 + x34 ≤ 30
x14 + x24 + x34 + x44 = 20 x44 ≤ 10
把第 i 季度生产的柴油机数目看作第 i 个生产厂的产量;把第 j 季度交货的柴油机数目看作第 j 个销售点的销量;成本加储存、维护等费用看作运费。可构造下列产销平衡问题:
目标函数:Min f = 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.25 x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44
运输问题(7)续§3 运输问题的应用
解: 这个生产存储问题可化为运输问题来做。考虑:各月生产与交货分别视为产地和销地
1)1--6月份合计生产能力(包括上年末储存量)为743台,销量为707台。设一假想销地销量为36;
2)上年末库存103台,只有仓储费和运输费,把它列为的0行;
3)6月份的需求除70台销量外,还要80台库存,其需求应为70+80=150台;
4)1--6表示1--6月份正常生产情况, 1’--6’表示1--6月份加班生产情况。
运输问题(8)§3 运输问题的应用
产销平衡与运价表:
运 输 问 题(9)续
解:设 xij 为从 i 到 j 的运输量,可得到有下列特点的线性规划模型:
目标函数:Min f = 所有可能的运输费用(运输单价与运输量乘积之和)
约束条件:
对产地(发点) i :输出量 - 输入量 = 产量
对转运站(中转点):输入量 - 输出量 = 0
对销地(收点) j :输入量 - 输出量 = 销量
运 输 问 题(10)续
用“管理运筹学”软件求得结果:
x13 = 550 x14 = 0 ;
x23 = 0 x24 = 150 x28 = 300 ;
x35 = 200 x36 = 0 x37 = 350 x38 = 0 ;
x45 = 0 x46 = 150 x47 = 0 x48 = 0 。
运输问题(11)续
运输问题(12)续
第三章 整数规划
§1 整数规划的图解法
§2整数规划的计算机求解
§3整数规划的应用
§4整数规划的分枝定界法
§1 整数规划的图解法
例1. 某工厂在计划期内要安排甲、乙两种仪器设备的生产,已知生产仪器设备
需要A、B两种材
料的消耗以及资
源的限制,如右
表。
问题:工厂应分
别生产多少件种仪器设备才
能使工厂获利最多?
§2整数规划的计算机求解
例2:
Max z = 15x1 + 10x2 + 7x3
s.t.
5x1 - 10x2 + 7x3 ≤ 8
6x1 + 4x2 + 8x3 ≤ 12
-3x1 + 2x2 + 2x3 ≤ 10
x1,x2,x3 ≥ 0 为整数
例2:
Max z = 15x1 + 10x2 + 7x3
s.t.
5x1 - 10x2 + 7x3 ≤ 8
6x1 + 4x2 + 8x3 ≤ 12
-3x1 + 2x2 + 2x3 ≤ 10
x1,x2,x3 ≥ 0
x3 为整数 x1 为0-1变量
§3整数规划的应用(1)
一、投资场所的选择
例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部,拟议中有10个位置 Aj (j=1,2,3,…,10)可供选择,考虑到各地区居民的消费水平及居民居住密集度,规定:
在东区由A1 , A2 ,A3 三个点至多选择两个;
在西区由A4 , A5 两个点中至少选一个;
在南区由A6 , A7 两个点中至少选一个;
在北区由A8 , A9 , A10 三个点中至少选两个。
Aj 各点的设备投资及每
年可获利润由于地点不同都
是不一样的,预测情况见右表所
示 (单位:万元)。但投资总额不能超过720万元,问应选择哪几个销售点,可使年利润为最大?
§3整数规划的应用(1)续
解:设:0--1变量 xi = 1 (Ai 点被选用)或 0 (Ai 点没被选用)。
这样我们可建立如下的数学模型:
Max z =36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10
s.t. 100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10 ≤ 720
x1 + x2 + x3 ≤ 2
x4 + x5 ≥ 1
x6 + x7 ≥ 1
x8 + x9 + x10 ≥ 2
xj ≥ 0 且xj 为0--1变量,i = 1,2,3,……,10
二、固定成本问题
例5.高压容器公司制造小、中、大三种尺寸的金属容器,所用资源为金属板、劳动力和机器设备,制造一个容器所需的各种资源的数量如下表所示。不考虑固定费用,每种容器售出一只所得的利润分别为 4万元、5万元、6万元,可使用的金
属板有500吨,劳动力有300人月,机器有100台月,此外不管每种容器制造的数量是多少,都要支付一笔固定的费用:小号是l00万元,中号为 150 万元,大号为200万元。现在要制定一个生产计划,使获得的利润为最大。
§3整数规划的应用(3)续
解:引入0—1变量 xij,并令
xij = 1(当指派第 i人去完成第j项工作时)或0(当不指派第 i人去完成第j项工作时).
这可以表示为一个0--1整数规划问题:
Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41 +21x42+23x43+17x44
s.t. x11+ x12+ x13+ x14= 1 (甲只能干一项工作)
x21+ x22+ x23+ x24= 1 (乙只能干一项工作)
x31+ x32+ x33+ x34= 1 (丙只能干一项工作)
x41+ x42+ x43+ x44= 1 (丁只能干一项工作)
x11+ x21+ x31+ x41= 1 ( A工作只能一人干)
x12+ x22+ x32+ x42= 1 ( B工作只能一人干)
x13+ x23+ x33+ x43= 1 ( C工作只能一人干)
x14+ x24+ x34+ x44= 1 ( D工作只能一人干)
xij 为0--1变量,i,j = 1,2,3,4
* * * 求解可用《管理运筹学》软件中整数规划方法。
§3整数规划的应用(4)续
解: a) 设 xij为从Ai 运往Bj 的运输量(单位千箱), yk = 1(当Ak 被选中时)或0(当Ak 没被选中时),k =2,3,4,5.
这可以表示为一个整数规划问题:
Min z = 175y2+300y3+375y4+500y5+ 8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41 +7x42+5x43+10x51 +4x52+2x53
其中前4项为固定投资额,后面的项为运输费用。
s.t. x11+ x12+ x13 ≤ 30 ( A1 厂的产量限制)
x21+ x22+ x23 ≤ 10y2 ( A2 厂的产量限制)
x31+ x32+ x33 ≤ 20y3 ( A3 厂的产量限制)
x41+ x42+ x43 ≤ 30y4 ( A4 厂的产量限制)
x51+ x52+ x53 ≤ 40y5 ( A5 厂的产量限制)
x11+ x21+ x31+ x41 + x51 = 30 ( B1 销地的限制)
x12+ x22+ x32+ x42 + x52 = 20 ( B2 销地的限制)
x13+ x23+ x33+ x43 + x53 = 20 ( B3 销地的限制)
xij ≥0,i = 1,2,3,4,5; j = 1,2,3, yk 为0--1变量,k = 2,3,4,5。
* * * 求解可用《管理运筹学》软件中整数规划方法。
§3整数规划的应用(5)续
解:1) 设xiA、xiB、xiC、xiD ( i =1,2,3,4,5)分别表示第 i 年年初给项目A,B,C,D的投资额;
设yiA, yiB,是0—1变量,并规定取 1 时分别表示第 i 年给A、B投资,否则取 0( i = 1, 2, 3, 4, 5)。
设yiC 是非负整数变量,并规定:2年投资C项目8万元时,取值为4;
2年投资C项目6万元时,取值为3;
2年投资C项目4万元时,取值为2;
2年投资C项目2万元时,取值为1;
2年不投资C项目时, 取值为0;
这样我们建立如下的决策变量:
第1年 第2年 第3年 第4年 第5年
A x1A x2A x3A x4A
B x3B
C x2C (=20000y2C)
D x1D x2D x3D x4D x5D
§3整数规划的应用(6)续
3)目标函数及模型:
Max z = 1.15x4A+ 1.40x2C+ 1.28x3B + 1.06x5D
s.t. x1A+ x1D = 100000;
x2A+x2C+x2D = 1.06x1D;
x3A+x3B+x3D = 1.15x1A+ 1.06x2D;
x4A+x4D = 1.15x2A+ 1.06x3D;
x5D = 1.15x3A+ 1.06x4D;
x1A ≥ 40000y1A ,
x1A ≤ 200000y1A ,
x3B ≥ 30000y3B ,
x3B ≤ 50000y3B ;
x2C = 20000y2C ,
yiA, yiB = 0 或 1,i = 1,2,3,4,5
y2C = 0,1,2,3,4
xiA ,xiB ,xiC ,xiD ≥ 0 ( i = 1、2、3、4、5)
§4整数规划的分枝定界法(1)
问题(A) Min z = c1 x1 + c2 x2 + … + cn xn 记 问题(B)为去掉整数约束的问题(A)
s.t. a11 x1 + a12 x2 + … + a1n xn = b1
a21 x1 + a22 x2 + … + a2n xn = b2
…… ……
am1 x1 + am2 x2 + … + amn xn = bm
x1 ,x2 ,… ,xn ≥ 0 为整数
在分枝定界法过程中求解问题(B),应有以下情况之一:
①(B)无可行解,则(A)亦无可行解,停止对此问题的计算;
②(B)有最优解,并满足整数约束,即同时为(A)的最优解,那么z*同时是当前问题(A)最优目标值的上界和下界。停止对这个问题的计算;
③(B)有最优解 x 及最优值 z 但不符合整数条件。这时得到当前问题(A)最优目标值的一个下界 z =z ,于是通过以下判断可对此问题进一步计算。
§4整数规划的分枝定界法(1)续
分枝定界法的计算过程:
1、对原问题(A),求解松弛问题(B)。根据上面分析,若出现情况①,②则停机。若情况③发生,得到(A)问题最优值的一个下界。我们任找(A)问题的一个可行解,那么对应的目标函数值是(A)最优值的一个上界 z¯ 。即得到 z < z* <z¯。(注:找(A)问题的可行解往往需要较大的计算量,这时可简单记 z¯=+,而先不必费很大力量去求较好的上界。从以下分析可以看到,找到一个好的最优目标值上界,将对算法的快速求得目标非常有效。),转2,进行以下一般步的迭代;
§4整数规划的分枝定界法(2)
2、对当前问题进行分枝和定界:
分技:无妨设当前问题为(A),其松弛问题(B)的最优解不符合整数约束,任取非整数的分量 xr 。构造两个附加约束: xr ≤ [xr] 和 xr ≥ [xr]+1 ,对(A)分别加入这两个约束,可得到两个子问题(A1)和(A2),显然这两个子问题的可行解集的并是(A)的可行解集;
定界:根据前面分析,对每个当前问题(A)可以通过求解松弛问题(B),以及找(A)的可行解得到当前问题的上、下界 z¯和 z 。
对一般迭代步,设根据分枝定界方法得到了原问题(A)的一个同层子问题(AI ),i=1,2,...,n 之和的分解。这里的同层子问题是指每个子问题(AI)都是(A)经过相同分枝次数得到的。
§4整数规划的分枝定界法(2)续
3、比较与剪枝:
对当前子问题进行考察,若不需再进行计算,则称之为剪枝。一般遇到下列情况就需剪枝:
①(B)无可行解;
②(B)的最优解符合整数约束;
③(B)的最优值 z ≥ z¯ 。
通过比较,若子问题不剪枝则返回 2 。
分枝定界法当所有子问题都剪枝了,即没有需要处理的子问题时,达到当前上界 z¯ 的可行解即原问题的最优解, 算法结束。
§4整数规划的分枝定界法(3)
分枝定界法是求整数规划的一种常用的有效的方法,既能解决纯整数规划的问题,也能解决混合整数规划的问题。
例:
Min f = -5x1-4x2
s.t. 3x1+4x2 ≤ 24
9x1+5x2 ≤ 45
x1,x2 ≥ 0 整数
§4整数规划的分枝定界法(4)
隐枚举法是求解0—1规划最常用的方法之一
对于 n 个决策变量的完全 0—1 规划,其可行点最多有 2n 个,当 n 较大时其计算量大得惊人。隐枚举法的基本思想是根据0—1规划的特点,进行分技逐步求解。
1、用于隐枚举法的0—1规划标准形式:
为了计算的方便,需要把一般的 0—1规划问题等价地化成下列标准形式
Min f = c1 x1 + c2 x2 + … + cn xn cj ≥ 0 j = 1,2,…,n
s.t. ai1 x1 + ai2 x2 + … + ain xn ≤ bi i = 1,2,…,m
x1 ,x2 ,… ,xn = 0 或 1
§4整数规划的分枝定界法(4)续
下面说明一个完全的0—1规划问题可以化为等价的标准形式:
(1)若目标函数求最大:Max z,可令 f = - z,变为求最小 Min f ;
(2)若目标函数的系数有负值时,如 cj <0。那么,可以令相应的 yj = 1- xj ;
(3)当某个约束不等式是“≥”时,只需两端同乘以 -1,即变为“≤” ;
(4)当某个约束是等式约束时,可得到两个方向相反的不等式。
§4整数规划的分枝定界法(5)
隐枚举法的基本过程:
1、将0—1规划问题化为标准形式,设其最优解为 x*,最优目标值为 f* 。显然 x = 0 时,目标值 f =0 是不考虑线性不等式约束的最小解,于是 f* ≥ 0。若 x = 0 是可行解,那末 f =0是该问题的最优解,结束计算。否则,置所有分量为自由变量。转2;
2、任选一自由变量 xk ,令 xk 为固定变量,分别固定为 xk = 0 与 xk =1,令所有自由变量取零值,则得到两个分枝。对每个分枝的试探解进行检验(把自由变量逐次定为固定变量的顺序可以是任意的,在不进行先验考察时,常按指标变量从小到大的顺序进行)。转3;
§4整数规划的分枝定界法(5)续
3、检验当前试探解时,遇到下列4种情况就剪枝,即不必再向下分枝,在剪枝的子问题下方标记“×”:
情况一:若子问题的试探解可行,即满足所有线性不等式约束,则此问题的目标值是原问题最优目标值的一个上界记为 f¯ 即 f* ≤ f¯ 。把 f¯ 的值记在子问题框的旁边,并在下方标记上“×”;
§4整数规划的分枝定界法(6)
情况二:若试探解不可行,且存在一个线性不等式约束,将所有固定变量值代入后,所得到的不等式中所有负系数之和大于右端项或若无负系数时,最小的系数大于右端项,那么此问题的任何分枝都是不可行的问题。于是在此问题框的下方标记“×”;
情况三:若试探解不可行,且它的目标值与目标函数中对应当前自由变量的任一个系数之和大于所有已得到的上界中最小者时,说明在当前问题的基础上,固定任何自由变量都不可能对目标函数有改善,于是在该问题框的下方标记“×”;
情况四:若试探解不可行,但所有变量已被置为固定变量,也应剪枝,于是在该问题框的下方标记“×”。
把已标记“×”的子问题,称为已探明的枝。转4。
§4整数规划的分枝定界法(6)续
4、进一步考察。如果所有的枝均为已探明的枝,则停机结束计算。找出所有子问题框边标记 f¯ 值的问题,比较得到其中最小者,其对应的试探解即原问题的最优解,相应值即原问题的最优目标值 f*;若没有标记 f¯ 值的框,则说明原问题无最优解,实际上原问题无可行解。
如果仍存在尚未探明的分枝,则可任选一个未探明的分枝。转2。
§4整数规划的分枝定界法(7)
0-1规划的隐枚举法
例:
Max z=100x1+30x2+40x3+45x4
s.t. 50x1+30x2+25x3+10x4≤95
7x1+ 2x2+ 3x3+ 4x4≤11
2x1+ x2+ x3+10x4≤12
x4 ≤ x2+ x3
xj= 0 或 1 ,i = 1,2,3,4
标准化:
取f’=-z=-100x1-30x2-40x3 -45x4
令 y1=1-x1, y2=1-x2, y3=1-x3, y4=1-x4
f’=100y1+30y2+40y3 +45y4-215,
记 f = f’ + 215, 得到
Min f=100y1+30y2+40y3 +45y4
s.t.
-50y1-30y2-25y3 -10y4≤-20
- 7y1- 2y2- 2y3 - 4y4≤- 4
- 2y1- y2- y3 -10y4≤- 2
y2+ y3 - y4≤ 1
yj= 0 或 1 ,i = 1,2,3,4
第四章 动态规划
第五章 存贮论(Inventory Theory)
§1 经济订购批量存贮模型
§2 经济生产批量模型
§3允许缺货的 经济订购批量模型
§4允许缺货的 经济生产批量模型
§5 经济订购批量折扣模型
§6需求为随机的单一周期的存贮模型
§7需求为随机变量的订货批量、再订货点模型
§8需求为随机变量的定期检查存贮量模型
§9物料需求计划(MRP)与准时化生产方式(JIT)简介
第五章 存贮论
存贮是缓解供应与需求之间出现的供不应求或供过于求等不协调情况的必要和有效的方法和措施。
但是,要存贮就需要资金和维护,存贮的费用在企业经营的成本中占据非常大的部分。
存贮论主要解决存贮策略问题,即如下两个问题:
1.补充存贮物资时,每次补充数量(Q)是多少?
2.应该间隔多长时间( T )来补充这些存贮物资?
建立不同的存贮模型来解决上面两个问题,如果模型中的需求率、生产率等一些数据皆为确定的数值时,存贮模型被称为确定性存贮摸型;如果模型中含有随机变量则被称为随机性存贮模型。
§1 经济订购批量存贮模型
经济订购批量存贮模型,又称不允许缺货,生产时间很短存贮模型,是一种最基本的确定性存贮模型。在这种模型里,需求率即单位时间从存贮中取走物资的数量是常量或近似乎常量;当存贮降为零时,可以立即得到补充并且所要补充的数量全部同时到位(包括生产时间很短的情况,我们可以把生产时间近似地看成零)。这种模型不允许缺货,并要求单位存贮费,每次订购费,每次订货量都是常数,分别为一些确定的、不变的数值。
主要参数:
需求率 : d
单位货物单位时间的存贮费: c1
每次订购费: c3
每次订货量: Q
是一些确定的、不变的数值。
§1 经济订购批量存贮模型
各参量之间的关系:
订货量 Q 单位存贮费 c1 每次订购费 c3
越小 存贮费用越小 订购费用越大
越大 存贮费用越大 订购费用越小
存贮量Q与时间 t 的关系
§1 经济订购批量存贮模型
这种存贮模型的特点:
1. 需求率 (单位时间的需求量)为 d;
2. 无限供货率(单位时间内入库的货物数量) ;
3. 不允许缺货;
4. 单位货物单位时间的存贮费 c1 ;
5. 每次的订货费 c3 ;
6. 每期初进行补充,即期初存贮量为Q 。
单位时间内的总费用=单位时间内的存贮费用+单位时间内的订货费用
单位时间内的存贮费用=单位时间内购买货物所占用资金的利息
+贮存仓库的费用+保险费用+损耗费用+管理费用等
设每次的订货量为Q,由于补充的货物全部同时到位,故0时刻的存贮量为Q。到T时刻存贮量为0,则0到T时间内的平均存贮量为Q/2。又设单位时间内的总需求量为D,(单位货物的进价成本即货物单价为c),则
§1 经济订购批量存贮模型
单位时间内的总费用
求极值得使总费用最小的订购批量为
这是存贮论中著名的经济订购批量公式,也称哈里斯-威尔逊公式。
单位时间内的存贮费用=
单位时间内的订货费用=
单位时间内的总费用=
§1 经济订购批量存贮模型
经济生产批量模型也称不允许缺货、生产需要一定时间模型,这也是一种确定型的存贮模型。它的存贮状态图为
§2 经济生产批量模型
2. 生产率(单位时间的产量)为 p — 有限供货率;
3. 不允许缺货;
4. 单位产品单位时间的存贮费 c1 ;
5. 每次的生产准备费 c3 ;
6. 每期初进行补充。
设每次生产量为 Q ,由于生产率是 p,则每次的生产时间 t 为Q/ p ,于是最高库存量为 (p-d) Q/ p。到T 时刻存贮量为0,则0到T时间内的平均存贮量为 (p-d) Q/2p 。故单位时间的存贮费为:
另一方面,设D为产品的单位时间需求量,则单位时间的生产准备费为 c3 D /Q ,进而,单位时间的总费用TC为:
§3 允许缺货的经济订购批量模型
使TC达最小值的最佳订购量
订购量为Q*时的最大缺货量
单位时间的最低总费用
订购量为Q*时的最大存贮量为
每个周期T所需时间
显然, 时,允许缺货订购模型趋于经济订购批量模型。
§4 允许缺货的经济生产批量模型(1)
此模型与经济生产批量模型相比,放宽了假设条件:允许缺货。与允许缺货的经济订货批量模型相比,相差的只是:补充不是靠订货,而是靠生产逐步补充,因此,补充数量不能同时到位。开始生产时,一部分产品满足需要,剩余产品作为存贮。生产停止时,靠存贮量来满足需要。
这种模型的存贮状态图为 :
§4 允许缺货的经济生产批量模型(2)
存贮量
§4 允许缺货的经济生产批量模型(3)
这种存贮模型的特点:
1. 需求率 (单位时间的需求量)为 d;
2. 生产率(单位时间的产量)为 p — 有限供货率;
3. 允许缺货,且最大缺货量为S;
4. 单位货物单位时间的存贮费 c1 ;
5. 每次的订货费 c3 ;
6.单位时间缺少一个单位货物所支付的单位缺货费c2 ;
7. 当缺货量达到S时进行补充,且逐步补充到最大存贮量。
§4 允许缺货的经济生产批量模型(4)
单位时间的总费用
TC =(单位时间的存贮费)+(单位时间的生产准备费)
+ (单位时间的缺货费)
=(平均存贮量)×c1 +(单位时间的生产次数)×c3
+ (平均缺货量)×c2
§4 允许缺货的经济生产批量模型(5)
使单位时间总费用TC最小的最优生产量
最优缺货量
单位时间最少的总费用
§5 经济订货批量折扣模型(1)
§5 经济订货批量折扣模型(2)
这种存贮模型的特点:
1. 需求率 (单位时间的需求量)为 d;
2. 无限供货率(单位时间内入库的货物数量) ;
3. 不允许缺货;
4. 单位货物单位时间的存贮费为 c1 ;
5. 每次的订货费为 c3 ;
6. 单位货物的进价成本即货物单价为 c ;
7. 每期初进行补充,即期初存贮量为 Q。
全量折扣模型
设货物单价 c 为订货量 Q 的分段函数,即
c(Q) = ki, Q∈[Qi -1 , Qi ) ,i = 1,2,…,n,
其中 k1 > k2 > … > kn , Q0< Q1< Q2< … < Qn , Q0 是最小订购数量,通常为0; Qn 为最大批量,通常无限制。
§5 经济订货批量折扣模型(3)
下图是 n = 3时 c(Q) 和 TC 的图形表示:
当订货量为Q∈[Qi -1 , Qi ) 时,由于 c(Q)= ki ,则有
由此可见,总费用 TC 也是 Q 的分段函数,具体表示如下:
§5 经济订货批量折扣模型(4)
TC(Q) = TCi, Q∈[Qi -1 , Qi ) , i = 1,2,…,n。
由微积分的有关知识可知,分段函数TC(Q)的最小值只可能在函数导数不存在的点、区间的端点和驻点达到。为此,我们需要先找出这些点。由于 TCi 中的 Dki 是常数,求导数为0,所以,类似于模型一,得 TCi 的驻点
由TC 的图形知,如果 TCi 的驻点 满足 Qi-1< < Qi ,则计算并比较 TCi( ) ,TCi+1(Qi) ,TCi+2(Qi+1), … ,TCn(Qn-1)的值,其中最小者所对应的 Q 即为最佳订货批量Q*,即Q*满足
§5 经济订货批量折扣模型(5)
例4. 图书馆设备公司准备从生产厂家购进阅览桌用于销售,每个阅览桌的价格为500元,每个阅览桌存贮一年的费用为阅览桌价格的20%,每次的订货费为200元,该公司预测这种阅览桌每年的需求为300个。生产厂商为了促进销售规定:如果一次订购量达到或超过50个,每个阅览桌将打九六折,即每个售价为480元;如果一次订购量达到或超过100个,每个阅览桌将打九五折,即每个售价为475元。请决定为使其一年总费用最少的最优订货批量Q*,并求出这时一年的总费用为多少?
解:已知 D = 300个/年,c3 = 200/次 。
Q < 50时, k1 = 500元, =500*20% =100(元/个年)
50 ≤ Q < 100时, k2 = 480元, = 480*20% = 96(元/个年)
100 ≤ Q时, k3 = 475元, = 475*20% = 95(元/个年)
§5 经济订货批量折扣模型(6)
Q < 50时,
50 ≤ Q < 100时,
100 ≤ Q时,
其中只有 在其范围内。
§5 经济订货批量折扣模型(7)
计算得
比较上面的数值,得一年的总费用最少为147600元,因此,最佳订货批量为 Q*= 50。
§6 需求为随机的单一周期存贮模型(1)
在前面讨论的模型中,我们把需求看成是固定不变的已知常量。但是,在现实世界中,更多的情况却是需求为一个随机变量。为此,在本节中我们将介绍需求是随机变量,特别是需求服从均匀分布和正态分布这两种简单情况的存贮模型。
所谓单一周期存贮是指在产品订货、生产、存贮、销售这一周期的最后阶段或者把产品按正常价格全部销售完毕,或者把按正常价格未能销售出去的产品削价销售出去,甚至扔掉。总之,在这一周期内把产品全部处理完毕,而不能把产品放在下一周期里存贮和销售。季节性和易腐保鲜产品,例如季节性的服装、挂历、麦当劳店里的汉堡包等都是按单一周期的方法处理的。报摊销售报纸是需要每天订货的,但今天的报纸今天必须处理完,与明天的报纸无关。因此,我们也可以把它看成是一个单一周期的存贮问题,只不过每天都要作出每天的存贮决策。
§6 需求为随机的单一周期存贮模型(2)
报童问题:报童每天销售报纸的数量是一个随机变量,每日售出 d 份报纸的概率 P(d )(根据以往的经验)是已知的。报童每售出一份报纸赚 k 元,如果报纸未能售出,每份赔 h 元,问报童每日最好准备多少报纸?
这就是一个需求量为随机变量的单一周期的存贮问题。在这个问题中要解决最优订货量 Q 的问题。如果订货量 Q 选得过大,那么报童就会因不能售出报纸造成损失;如果订货量 Q 选得过小,那么报童就要因缺货失去销售机会而造成机会损失。如何适当地选择订货量 Q,才能使这两种损失的期望值之和最小呢?
§6 需求为随机的单一周期存贮模型(3)
设售出d 份报纸的概率为P(d ),从概率论可知
已知因报纸未能售出而造成每份损失 h 元,因缺货而造成机会损失每份k 元,则满足下面不等式的 Q*是这两种损失的期望值之和最小的订报量
例5. 某报亭出售某种报纸,每售出一百张可获利15元,如果当天不能售出,每一百张赔20元。每日售出该报纸份数的概率P(d )根据以往经验如下表所示。试问报亭每日订购多少张该种报纸能使其赚钱的期望值最大。
§6 需求为随机的单一周期存贮模型(4)
解:要使其赚钱的期望值最大,也就是使其因售不出报纸的损失和因缺货失去销售机会的损失的期望值之和为最小。已知 k = 15,h = 20,则有
另有
故当Q = 8时,不等式
成立.因此,最优的订报量为每天800张,此时其赚钱的期望值最大。
§6 需求为随机的单一周期存贮模型(5)
我们可以把公式(12. 42)改写成
公式(12. 43)既适用于离散型随机变量也适用于连续型随机变量。如果只考虑连续型随机变量,公式(12. 43)又可以改写为
§6 需求为随机的单一周期存贮模型(6)
例6. 某书店拟在年前出售一批新年挂历。每售出一本可盈利20元,如果年前不能售出,必须削价处理。由于削价,一定可以售完,此时每本挂历要赔16元。根据以往的经验,市场的需求量近似服从均匀分布,其最低需求为550本,最高需求为1100本,该书店应订购多少新年挂历,使其损失期望值为最小?
解:由题意知挂历的需求量是服从区间[550,1100]上的均匀分布的随机变量, k = 20,h = 16,则其需求量小于Q*的概率为
则由公式(12. 44)得
由此求得 Q*= 856(本),并从 5/9可知,这时有5/9的概率挂历有剩余,有1-5/9=4/9的概率挂历脱销。
§6 需求为随机的单一周期存贮模型(7)
例7. 某化工公司与一客户签订了一项供应一种独特的液体化工产品的合同。客户每隔六个月来购买一次,每次购买的数量是一个随机变量,通过对客户以往需求的统计分析,知道这个随机变量服从以均值 =1000(公斤),方差 =100 (公斤)的正态分布。化工公司生产一公斤此种产品的成本为15元,根据合同固定售价为20元。合同要求化工公司必须按时提供客户的需求。一旦化工公司由于低估了需求产量不能满足需要,那么化工公司就到别的公司以每公斤19元的价格购买更高质量的替代品来满足客户的需要。一旦化工公司由于高估了需求,供大于求,由于这种产品在两个月内要老化,不能存贮至六个月后再供应给客户,只能以每公斤5元的价格处理掉。化工公司应该每次生产多少公斤的产品才使该公司获利的期望值最大呢?
§6 需求为随机的单一周期存贮模型(8)
解:根据题意得 k =5-1= 4,h = 15-5= 10,利用公式(12. 44)得
由于需求服从均值 =1000,方差 =100 的正态分布,上式即为
通过查阅标准正态表,得
把 =1000, =100 代入,得
从 可知,当产量为945公斤时,有0.29的概率产品有剩余,有1-0.29 = 0.71的概率产品将不满足需求。
§7需求为随机变量的订货批量、再订货点模型(1)
本节介绍需求为随机变量的多周期存贮模型。在这种模型里,
由于需求为随机变量,我们无法求得周期(即两次订货时间间隔)的确切时间,也无法求得再次订货点确切来到的时间。
下面我们给出求订货量和再订货点的最优解的近似方法,而精确的数学公式太复杂,这里不作介绍。具体求解步骤如下:
1. 设全年的需求量近似为D,利用经济订货批量存贮模型求出(每次的)最优订货量Q*。
2. 根据具体情况制定出服务水平,即制定在m天里出现缺货的概率,也即不出现缺货的概率为1。利用下式求出 r
P( m 天里需求量 r ) = 1,
其中 r 为再订货点,即当库存量下降到r 时订货, m 天后货到。
存贮的 ( r, Q ) 策略 r 为最低存贮量,即订货点,对库存量随时进行检查,当 H >r 时不补充;当 H ≤ r 时进行补充,每次补充的数量为Q 。
§7需求为随机变量的订货批量、再订货点模型(2)
例8.某装修材料公司经营某品牌的地砖,公司直接从厂家进这种产品。由于公司与厂家距离较远,双方合同规定,在公司填写订货单后一个星期厂家把地砖运到公司。公司根据以往的数据统计分析知道,在一个星期里此种地砖的需求量服从以均值 =850箱,方差 =120箱的正态分布,又知道每次订货费为250元,每箱地砖的成本为48元,存贮一年的存贮费用为成本的20%,即每箱地砖一年的存贮费用为48×20% = 9.6元。公司规定的服务水平为允许由于存贮量不够造成的缺货情况为5%。公司应如何制定存贮策略,使得一年的订货费和存贮费的总和为最少?
解:首先按经济订货批量存贮模型求出最优订货批量Q* 。已知每年的平均需求量 D =8 50 ×52 = 44200 箱/年,c1 = 9.6 元/箱年, c3 = 250元,得
§7需求为随机变量的订货批量、再订货点模型(3)
于是,每年平均约订货 44200/1517≈29次。由服务水平,得
P (一个星期的需求量 r ) = 1 =1 0.05=0.95
进一步,有
查标准正态分布表,得
进一步,有 r = 1047,安全存贮量为 r d m =1047 850 =197箱。
在这样的存贮策略下,在订货期有95%的概率不会出现缺货,有5%的概率会出现缺货。
§8 需求为随机变量的定期检查存贮量模型(1)
需求为随机变量的定期检查存贮量模型是另一种处理多周期的存贮问题的模型。在这个模型里,管理者要订期例如每隔一周、一个月等检查产品的库存量,根据现有的库存量来确定订货量,在这个模型中管理者所要做的决策是:依照规定的服务水平制定出产品的存贮补充水平M。一旦确定了M,也就确定了订货量Q 如下所示:
Q = M H,
式中H 为检查时的库存量。
存贮的 (t,r,M ) 策略
每隔 t 时间检查库存量 H,当 H > r 时不补充;当 H ≤ r 时补充存贮量使之达到 M,补充量为 M H。
§8 需求为随机变量的定期检查存贮量模型(2)
解:设商品A的存贮补充水平为 MA从统计知识可知
P (商品A的需求量d MA ) = 1A =1 0.25=0.975
进一步,有
查标准正态分布表,得
从而 MA = A +1.96 A ≈717(条)。也就是说,商店在每隔两周的清货盘店时,发现A商品还剩 HA 时,马上向厂家订货A商品为 717 HA 条,使得当时A商品的库存量加上订货量正好达到存贮补充水平 717。
第六章 排队论 (Queuing Theory)
排队过程的组成部分
单服务台泊松到达、负指数服务时间的排队模型
多服务台泊松到达、负指数服务时间的排队模型
排队系统的经济分析
单服务台泊松到达、任意服务时间的排队模型
单服务台泊松到达、定长服务时间的排队模型
多服务台泊松到达、任意的服务时间、损失制排队模型
顾客来源有限制排队模型
§1 排队过程的组成部分(1)
一、基本概念
一些排队系统的例子
排队系统 顾 客 服务台 服 务
电话系统 电话呼叫 电话总机 接通呼叫或取消呼叫
售票系统 购票旅客 售票窗口 收款、售票
设备维修 出故障的设备 修理工 排除设备故障
防空系统 进入阵地的敌机 高射炮 瞄准、射击直至敌机被击落或 离开
排队的过程可表示为:
§1 排队过程的组成部分(2)
考虑要点:
1、服务台(或通道)数目:单服务台(单通道)、多服务台(多通道)。
2、顾客到达过程:本教材主要考虑顾客的泊松到达情况。
满足以下四个条件的输入流称为泊松流(泊松过程)
*平稳性:在时间区间 [t, t+t) 内到达k个顾客的概率与t无关,只与 t 有关,记为 pk(t);
*无后效性:不相交的时间区间内到达的顾客数互相独立;
*普通性:在足够短的时间内到达多于一个顾客的概率可以忽略;
*有限性:任意有限个区间内到达有限个顾客的概率等于1。
泊松分布 为单位时间平均到达的顾客数
P (x) = x e- / x! (x = 0, 1, 2,……)
§1 排队过程的组成部分(2)续
3、服务时间分布: 服从负指数分布 为平均服务率,即单位时间服务的顾客数,
P(服务时间≤ t ) = 1- e- t 。
4、排队规则分类
(1) 等待制: 顾客到达后,一直等到服务完毕以后才离去,
先到先服务,后到先服务,随机服务,有优先权的服务;
(2) 损失制: 到达的顾客有一部分未接受服务就离去。
5、平稳状态: 业务活动与时间无关
§1 排队过程的组成部分(3)
§2 单服务台泊松到达、负指数服务时间的排队模型
M / M / 1 / ∞ / ∞
单位时间顾客平均到达数 ,单位平均服务顾客数 (< )
数量指标公式:
1、系统中无顾客的概率 P0 =1 /
2、平均排队的顾客数 Lq =2/( )
3、系统中的平均顾客数 Ls = Lq + /
4、顾客花在排队上的平均等待时间 Wq = Lq /
5、顾客在系统中的平均逗留时间 Ws = Wq+ 1/
6、顾客得不到及时服务必须排队等待的概率 Pw = /
7、系统中恰好有 n 个顾客的概率 Pn =( /)n P0
第七章 对策论
由“齐王赛马”引入
1.对策论的基本概念
对策模型的三个基本要素:
1.局中人:参与对抗的各方;
2.策略集:局中人选择对付其它局中人的行动方案称为策略;某局中人的所有可能策略全体称为策略集;
3.一局势对策的益损值:局中人各自使用一个对策就形成了一个局势,一个局势决定了各局中人的对策结果(量化)称为该局势对策的益损值。
“齐王赛马”齐王在各局势中的益损值表(单位:千金)
其中:齐王的策略集: S1={ 1, 2, 3, 4, 5, 6 },
田忌的策略集:S2={ 1, 2, 3, 4, 5, 6 }。
下面矩阵称齐王的赢得矩阵:
3 1 1 1 -1 1
1 3 1 1 1 -1
A= 1 -1 3 1 1 1
-1 1 1 3 1 1
1 1 1 -1 3 1
1 1 -1 1 1 3
1.对策论的基本概念(续)
二人有限零和对策(又称矩阵对策):
局中人为2;每个局中人的策略集的策略数目都是有限的;每一局势的对策均有确定的损益值,并且对同一局势的两个局中人的益损值之和为零。
通常将矩阵对策记为: G = {S1, S2, A}
S1:甲的策略集; S2:乙的策略集;
A:甲的赢得矩阵。
“齐王赛马”是一个矩阵策略。
2.矩阵对策的最优纯策略
在甲方的赢得矩阵中:
A=[aij]m×n
i 行代表甲方策略 i=1, 2, …, m;j 行代表乙方策略 j=1, 2, …, n;aij 代表甲方取策略 i,乙方取策略 j,这一局势下甲方的益损值。此时乙方的益损值为 -aij(零和性质)。
在考虑各方采用的策略时,必须注意一个前提,就是双方都是理智的,即双方都是从各自可能出现的最不利的情形选择一种最为有利的情况作为决策的依据。
2.矩阵对策的最优纯策略(续)
例2 某单位采购员在秋天决定冬季取暖用煤的贮两问题。已知在正常的冬季气温条件下要消耗15吨煤,在较暖和较冷的气温条件下要消耗10吨和20吨。假定冬季的煤价随天气寒冷程度而有所变化,在较暖、正常、较冷的气候条件下每吨煤价分别为10元,15元和20元,又设秋季时煤价为每吨10元。在没有关于当年冬季准确的气象预报的条件下,秋季贮煤多少吨能使单位的支出最少?
解:
局中人I为采购员;局中人II为大自然,采购员有三个策略,在秋季买10吨、15吨和20吨,分别记为1、2 、3,大自然也有三个策略,分别为较暖、正常和较冷,记为1、2、 3。
以冬季取暖用煤实际费用,作为局中I采购员的赢得,得到赢得矩阵如下:
1(较暖) 2 (正常) 3 (较冷) min
1 -100 -175 -300 -300
2 -150 -150 -250 -250
3 -200 -200 -200 -200
Max -100 -150 -200
得 max min aij=min max aij=a32=-200
3.矩阵对策的混合策略
设矩阵对策 G = { S1, S2, A }。当
max min aij min max aij
i j j i
时,不存在最优纯策略。
例:设一个赢得矩阵如下:
min
5 9 5
A = max 6 策略2
8 6 6 i
max 8 9
min 8 策略1
j
当甲取策略2 ,乙取策略1时,甲实际赢得8比预期的多2,乙当然不满意。考虑到甲可能取策略2这一点,乙采取策略2。若甲也分析到乙可能采取策略2这一点,取策略1,则赢得更多为9 … 。此时,对两个局中人甲、乙来说,没有一个双方均可接受的平衡局势,其主要原因是甲和乙没有执行上述原则的共同基础,即 max min aij min max aij 。
i j j i
一个自然的想法:对甲(乙)给出一个选取不同策略的概率分布,以使甲(乙)在各种情况下的平均赢得(损失)最多(最少)-----即混合策略。
求解混合策略的问题有图解法、迭代法、线性方程法和线性规划法等我们这里只介绍线性规划法,其他方法略。
例:设甲使用策略1的概率为X1′,使用策略2的概率为X2′ ,并设在最坏的情况下,甲赢得的平均值为V(未知)。
5 9
A= STEP 1
8 6 1) X1′+X2′=1
X1′, X2′0
2)无论乙取何策略,甲的平均赢得应不少于V:
对乙取1: 5X1’+ 8X2’ V
对乙取2: 9X1’+ 6X2’ V
注意 V>0,因为A各元素为正。
STEP 2
作变换: X1= X1’/V ; X2= X2’/V
得到上述关系式变为:
X1+ X2=1/V (V愈大愈好)待定
5X1+ 8X21
9X1+ 6X21
X1, X20
建立线性模型:
min X1+X2
s.t. 5X1+8X21 X1= 1/21
9X1+6X21 X2= 2/21
X1, X20 1/V= X1+X2=1/7
所以,V=7
返回原问题: X1’= X1V= 1/3
X2’= X2V= 2/3
于是甲的最优混合策略为:
以1/3的概率选1, 以2/3的概率选2,最优值V=7.
3.矩阵对策的混合策略(续)
例:求解“齐王赛马”问题。
优超原则:
假设矩阵对策 G ={ S1, S2, A }
甲方赢得矩阵 A=[aij]mn
若存在两行(列),s 行(列)的各元素均优于 t 行(列)的元素,即
asjatj j=1,2 … n ( ais ait i=1,2 … m )
称甲方策略s优超于t ( s优超于t)
3.矩阵对策的混合策略(续)
优超原则:当局中人甲方的策略t被其它策略所优超时,可在其赢得矩阵A中划去第t行(同理,当局中人乙方的策略t被其它策略所优超时,可在矩阵A中划去第t列)。
如此得到阶数较小的赢得矩阵A’,其对应的矩阵对策
G’= { S1, S2, A’} 与 G = { S1, S2, A }
等价,即解相同。
3.矩阵对策的混合策略(续)
例 5. 设甲方的益损值,赢得矩阵为
3 2 0 3 0 被第3、4行所优超
5 0 2 5 9 被第3行所优超
A= 7 3 9 5 9
4 6 8 7 5.5
6 0 8 8 3
得到
7 3 9 5 9 被第1列所优超
A1= 4 6 8 7 5.5 被第2列所优超
6 0 8 8 3
3.矩阵对策的混合策略(续)
3.矩阵对策的混合策略(续)
对A4计算,用线性规划方法得到:
(注意:余下的策略为3,4,1,2)
甲: X* = (0,0,1/15,2/15,0)T V=5
X*’= (0,0,1/3 ,2/3 ,0)T
乙: Y* = (1/10,1/10,0,0,0)T V=5
Y*’= (1/2 ,1/2 ,0,0,0)T 。
注:
利用有超原则化简赢得矩阵时,有可能将原对策问题的解也划去一些(多解情况);
线性规划求解时有可能是多解问题。
习题:P343-1,3,4
第八章 决策分析
“决策” 一词来源于英语 Decision making,直译为“做出决定”。所谓决策,就是为了实现预定的目标在若干可供选择的方案中,选出一个最佳行动方案的过程,它是一门帮助人们科学地决策的理论。
第十五章 决策分析
决策的分类:
按决策问题的重要性分类
按决策问题出现的重复程度分类
按决策问题的定量分析和定性分析分类
按决策问题的自然状态发生分类:
第十五章 决策分析
确 定 型 决 策 问 题
在决策环境完全确定的条件下进行,
不 确 定 型 决 策 问 题
在决策环境不确定的条件下进行,决策者对各自然状态发生的概率一无所知
风 险 型 决 策 问 题
在决策环境不确定的条件下进行,决策者对各自然状态发生的概率可以预先估计或计算出来
第十五章 决策分析
构成决策问题的四个要素:
决策目标、行动方案、自然状态、效益值
行动方案集: A = { s1, s2, …, sm }
自然状态集: N = { n1, n2, …, nk }
效益(函数)值:v = ( si, nj )
自然状态发生的概率P=P(sj) j =1, 2, …, m
决策模型的基本结构:(A, N, P, V)
基本结构(A, N, P, V)常用决策表、决策树等表示
§1 不确定情况下的决策
特征:1、自然状态已知;2、各方案在不同自然状态下的收益值已知;3、自然状态发生不确定。
例:某公司需要对某新产品生产批量作出决策,各种批量在不同的自然状态下的收益情况如下表(收益矩阵):
§1 不确定情况下的决策(续)
一、最大最小准则(悲观准则)
决策者从最不利的角度去考虑问题:
先选出每个方案在不同自然状态下的最小收益值(最保险),然后从这些最小收益值中取最大的,从而确定行动方案。 用(Si, Nj)表示收益值
§1 不确定情况下的决策(续)
二、最大最大准则(乐观准则)
决策者从最有利的角度去考虑问题:
先选出每个方案在不同自然状态下的最大收益值(最乐观),然后从这些最大收益值中取最大的,从而确定行动方案。 用(Si, Nj)表示收益值
§1 不确定情况下的决策(续)
三、等可能性准则 ( Laplace准则 )
决策者把各自然状态发生的机会看成是等可能的:
设每个自然状态发生的概率为 1/事件数 ,然后计算各行动方案的收益期望值。
用 E(Si )表示第I方案的收益期望值
§1 不确定情况下的决策(续)
四、乐观系数(折衷)准则(Hurwicz胡魏兹准则)
决策者取乐观准则和悲观准则的折衷:
先确定一个乐观系数 (01),然后计算:CVi = max [(Si, Nj)] +(1- )min [(Si, Nj)]
从这些折衷标准收益值CVi中选取最大的,从而确定行动方案。 取 = 0.7
§1 不确定情况下的决策(续)
五、后悔值准则(Savage 沙万奇准则)
决策者从后悔的角度去考虑问题:
把在不同自然状态下的最大收益值作为理想目标把各方案的收益值与这个最大收益值的差称为未达到理想目标的后悔值,然后从各方案最大后悔值中取最小者,从而确定行动方案。 用aij’表示后悔值,构造后悔值矩阵:
§2 风险型情况下的决策
特征:1、自然状态已知;2、各方案在不同自然状态下的收益值已知;3、自然状态发生的概率分布已知。
一、最大可能准则
在一次或极少数几次的决策中,取概率最大的自然状态,按照确定型问题进行讨论。
§2 风险型情况下的决策(续)
二、期望值准则
根据各自然状态发生的概率,求不同方案的期望收益值,取其中最大者为选择的方案。
E(Si) = P(Nj) (Si,Nj)
§2 风险型情况下的决策(续)
三、决策树法
具体步骤:
(1) 从左向右绘制决策树;
(2) 从右向左计算各方案的期望值,并将结果标在相应方案节点的上方;
(3) 选收益期望值最大(损失期望值最小)的方案为最优方案,并在其它方案分支上打∥记号。
主要符号
决策点 方案节点 结果节点
§2 风险型情况下的决策(续)
前例 根据下图说明S3是最优方案,收益期望值为6.5
§2 风险型情况下的决策(续)
四、灵敏度分析
研究分析决策所用的数据在什么范围内变化时,原最优决策方案仍然有效.
前例 取 P(N1) = p , P(N2) = 1- p . 那么
E(S1) = p30 + (1-p)(-6) = 36p - 6 p=0.35为转折概率
E(S2) = p20 + (1-p)(-2) = 22p - 2 实际的概率值距转
E(S3) = p10 + (1-p)(+5) = 5p + 5 折概率越远越稳定
§2 风险型情况下的决策(续)
五、全情报的价值(EVPI)
全情报:关于自然状况的确切消息。
在前例,当我们不掌握全情报时得到 S3 是最优方案,数学期望最大值为 0.3*10 + 0.7*5 = 6.5万 记为 EVW0PI。
若得到全情报:当知道自然状态为N1时,决策者必采取方案S1,可获得收益30万,概率0.3;当知道自然状态为N2时,决策者必采取方案S3,可获得收益5万, 概率0.7。于是,全情报的期望收益为
EVWPI = 0.3*30 + 0.7*5 = 12.5万
那么, EVPI = EVWPI - EVW0PI = 12.5 - 6.5 = 6万
即这个全情报价值为6万。当获得这个全情报需要的成本小于6万时,决策者应该对取得全情报投资,否则不应投资。
注:一般“全”情报仍然存在可靠性问题。
§2 风险型情况下的决策(续)
六、具有样本情报的决策分析(贝叶斯决策)
先验概率:由过去经验或专家估计的将发生事件的概率;
后验概率:利用样本情报对先验概率修正后得到的概率;
前例,如果请咨询公司进行市场调查,可以根据样本情报来修正先验概率,得到后验概率。如此用决策树方法,可得到更高期望值的决策方案。
在自然状态为Nj的条件下咨询结果为Ik的条件概率,可用全概率公式计算
再用贝叶斯公式计算
条件概率的定义: 乘法公式
§3 效用理论在决策中的应用
效用:衡量决策方案的总体指标,反映决策者对决策问题各种因素的总体看法
使用效用值进行决策:首先把要考虑的因素折合成效用值,然后用决策准则下选出效用值最大的方案,作为最优方案。
例:求下表显示问题的最优方案(万元)
§3 效用理论在决策中的应用(续)
用收益期望值法:
E(S1) = 0.360 + 0.540 + 0.2(-100) = 18万
E(S2) = 0.3100 + 0.5(-40)+ 0.2(-60) = -2万
E(S3) = 0.30 + 0.50 + 0.20 = 0万
得到 S1 是最优方案,最高期望收益18万。
一种考虑:
由于财务情况不佳,公司无法承受S1中亏损100万的风险,也无法承受S2中亏损50万以上的风险,结果公司选择S3,即不作任何项目。
§3 效用理论在决策中的应用(续)
用效用函数解释:
把上表中的最大收益值100万元的效用定为10,即U(100) = 10;最小收益值-100万元的效用定为0,即U(-100) = 0;
对收益60万元确定其效用值:设经理认为使下两项等价的 p=0.95
(1)得到确定的收益60万;
(2)以 p 的概率得到100万,以 1- p 的概率损失100万。
计算得:U(60)= p*U(100)+(1-p)*U(-100) = 0.95*10+0.05*0=9.5
§3 效用理论在决策中的应用(续)
类似地,设收益值为40、0、- 40、- 60相应等价的概率分别为0.90、0.75、0.55、0.40,可得到各效用值:
U(40) = 9.0; U(0) = 7.5; U(-40) = 5.5; U(-60) = 4.0
我们用效用值计算最大期望,如下表:
§3 效用理论在决策中的应用(续)
一般,若收益期望值能合理地反映决策者的看法和偏好,可以用收益期望值进行决策。否则,需要进行效用分析。
收益期望值决策是效用期望值决策的一种特殊情况。
管理运筹学(ppt)
管 理 运 筹 学
绪论
线性规划(运输问题)
整数规划
动态规划
存储论
排队论
对策论
决策分析
第一章 绪论
运筹学(Operational Research) 直译为“运作研究”
运筹学是应用分析、试验、量化的方法,对经济管理系统中的人力、物力、财力等资源进行统筹安排,为决策者提供有依据的最优方案,以实现最有效的管理。
运筹学有广泛应用
运筹学的产生和发展
§1 决策、定量分析与管理运筹学
决策过程(问题解决的过程):
1)提出问题:认清问题
2)寻求可行方案:建模、求解
3)确定评估目标及方案的标准或方法、途径
4)评估各个方案:解的检验、灵敏性分析等
5)选择最优方案:决策
6)方案实施:回到实践中
7)后评估:考察问题是否得到完满解决
1)2)3):形成问题;4)5)分析问题:定性分析与定量分析。构成决策。
§2 运筹学的分支
线性规划
非线性规划
整数规划
图与网络模型
存储模型
排队论
排序与统筹方法
决策分析
动态规划
预测
§3运筹学在工商管理中的应用
生产计划:生产作业的计划、日程表的编排、合理下
料、配料问题、物料管理等
库存管理:多种物资库存量的管理,库存方式、库存
量等
运输问题:确定最小成本的运输线路、物资的调拨、
运输工具的调度以及建厂地址的选择等
人事管理:对人员的需求和使用的预测,确定人员编
制、人员合理分配,建立人才评价体系等
市场营销:广告预算、媒介选择、定价、产品开发与
销售计划制定等
财务和会计:预测、贷款、成本分析、定价、证券管
理、现金管理等
*** 设备维修、更新,项目选择、评价,工程优化设计与管理等
运筹学方法使用情况(美1983)
运筹学的推广应用前景
据美劳工局1992年统计预测: 运筹学应用分析人员需求从1990年到2005年的增长百分比预测为73%,增长速度排到各项职业的前三位.
结论:
运筹学在国内或国外的推广前景是非常广阔的
工商企业对运筹学应用和需求是很大的
在工商企业推广运筹学方面有大量的工作要做
第二章 线性规划的图解法
在管理中一些典型的线性规划应用
合理利用线材问题:如何下料使用材最少
配料问题:在原料供应量的限制下如何获取最大利润
投资问题:从投资项目中选取方案,使投资回报最大
产品生产计划:合理利用人力、物力、财力等,使获利最大
劳动力安排:用最少的劳动力来满足工作的需要
运输问题:如何制定调运方案,使总运费最小
线性规划的组成:
目标函数 Max f 或 Min f
约束条件 s.t. (subject to) 满足于
决策变量 用符号来表示可控制的因素
§1问题的提出
例1. 某工厂在计划期内要安排甲、乙两种产品的生产,已知生产单位产品所需的设备台时及A、B两种原材料的消耗以及资源的限制,如下表:
问题:工厂应分别生产多少单位甲、乙产品才能使工厂获利最多?
线 性 规 划 模 型
一般形式
目标函数: Max (Min) z = c1 x1 + c2 x2 + … + cn xn
约束条件: s.t. a11 x1 + a12 x2 + … + a1n xn ≤ ( =, ≥ )b1
a21 x1 + a22 x2 + … + a2n xn ≤ ( =, ≥ )b2
…… ……
am1 x1 + am2 x2 + … + amn xn ≤ ( =, ≥ )bm
x1 ,x2 ,… ,xn ≥ 0
标准形式
目标函数: Max z = c1 x1 + c2 x2 + … + cn xn
约束条件: s.t. a11 x1 + a12 x2 + … + a1n xn = b1
a21 x1 + a22 x2 + … + a2n xn = b2
…… ……
am1 x1 + am2 x2 + … + amn xn = bm
x1 ,x2 ,… ,xn ≥ 0
线性规划标准型
线性规划标准型
线性规划标准型
线性规划标准型
线性规划标准型
线性规划标准型
线性规划标准型
线性规划标准型
线性规划标准型
线性规划标准型
线性规划标准型
线性规划标准型
§2 线 性 规 划 的 图 解 法
例1.
目标函数:
Max z = 50 x1 + 100 x2
约束条件:
s.t.
x1 + x2 ≤ 300 (A)
2 x1 + x2 ≤ 400 (B)
x2 ≤ 250 (C)
x1 ≥ 0 (D)
x2 ≥ 0 (E)
得到最优解:
x1 = 50, x2 = 250
最优目标值 z = 27500
线性规划图解法的步骤
(2)对每个不等式(约束条件),先取其等式在坐标系中作直线,然后确定不等式所决定的半平面。若各半平面交出来的公共区域存在,显然,其中的点满足所有的约束条件,称这样的点为此线性规划的可行解,全体可行解的集合称为可行集或可行域。若这样的公共区域不存在,则该线性规划问题无可行解。
(3)任意给定目标函数一个确定的值,作出对应的目标函数等值线,并确定该族等值线平行移动时目标函数值增加的方向。然后平移目标函数的等值线,使其达到既与可行域有交点又不可能使值再增加的位置(有时交于无穷远处,此时称无有限最优解)。此时,目标函数等值线与可行域的交点即此线性规划的最优解(一个或多个),此目标函数的值即最优值。
进 一 步 讨 论
线性规划的标准化内容之一: —— 引入松驰变量(含义是资源的剩余量)
例1 中引入 s1, s2, s3 模型化为
目标函数:Max z = 50 x1 + 100 x2 + 0 s1 + 0 s2 + 0 s3
约束条件:s.t. x1 + x2 + s1 = 300
2 x1 + x2 + s2 = 400
x2 + s3 = 250
x1 , x2 , s1 , s2 , s3 ≥ 0
对于最优解 x1 =50 x2 = 250 , s1 = 0 s2 =50 s3 = 0
说明:生产50单位甲产品和250单位乙产品将消耗完所有可能的设备台时数及原料B,但对原料A则还剩余50千克。
进 一 步 讨 论(续)
解的性质:
1) 线性规划的最优解如果存在,则必定有一个顶点(极点)是最优解;
2) 有的线性规划问题存在无穷多个最优解的情况;
3) 有的线性规划问题存在无有限最优解的情况,也称无解;
4) 有的线性规划问题存在无可行解的情况。
§3图解法的灵敏度分析
灵敏度分析:建立数学模型和求得最优解后,研究线性规划的一个或多个参数(系数)ci , aij , bj 变化时,对最优解产生的影响。
3.1 目标函数中的系数 ci 的灵敏度分析
考虑例1的情况, ci 的变化只影响目标函数等值线的斜率,
目标函数 z = 50 x1 + 100 x2
在 z = x2 (x2 = z 斜率为0 ) 到 z = x1 + x2 (x2 = -x1 + z 斜率为 -1 )之间时,
原最优解 x1 = 50,x2 = 100 仍是最优解。
一般情况:
z = c1 x1 + c2 x2 写成斜截式 x2 = - (c1 / c2 ) x1 + z / c2
§3图解法的灵敏度分析(续)
目标函数等值线的斜率为 - (c1 / c2 )
当 -1 - (c1 / c2 ) 0 (*) 时,原最优解仍是最优解
假设产品乙的利润100元不变,即 c2 = 100,代到式(*)并整理得
0 c1 100
假设产品甲的利润 50 元不变,即 c1 = 50 ,代到式(*)并整理得
50 c2 +
假若产品甲、乙的利润均改变,则可直接用式(*)来判断。
假设产品甲、乙的利润分别为60元、55元,则
- 2 - (60 / 55) - 1
那麽,最优解为 z = x1 + x2 和 z = 2 x1 + x2 的交点 x1 = 100,x2 = 200 。
3.2 约束条件中右边系数 bj 的灵敏度分析(续)
解释:原最优解没有把原料 A 用尽,有50千克的剩余,因此增加10千克值增加了库存,而不会增加利润。
在一定范围内,当约束条件右边常数增加1个单位时
1)若约束条件的对偶价格大于0,则其最优目标函数值得到改善(变好);
2)若约束条件的对偶价格小于0,则其最优目标函数值受到影响(变坏);
3)若约束条件的对偶价格等于0,则其最优目标函数值不变。
线性规划问题的计算机求解(1)
管理运筹学软件1.0版使用说明:(演示例1)
一、系统的进入与退出:
1、在WINDOWS环境下直接运行main.exe文件,或者在DOS下UCDOS中文平台环境下运行,也可直接运行各可执行程序。
2、退出系统的方法可以在主菜单中选退出项,也可按Ctrl+Break键直接退出。
3、在WINDOWS环境下直接运行软件,如果出现乱码,那是因为启用了全屏幕方式,解决办法是按ALT+ENTER键, 即可转换成非全屏的界面(一般就会消除乱码,如果还是乱码,可以点击菜单的“汉”选项);若要每次启动程序都没有乱码,则需要修改屏幕设置的相应属性。具体方法是:在非全屏界面下点击菜单的“属性”选项,再选择“窗口”选项,然后选中其中的“窗口”项,并取消“启动时恢复设置”项,这样就可保证每次运行软件时以非全屏方式显示。
线性规划问题的计算机求解(1)续
二、输入部分:
1、线性规划、整数规划的目标函数和约束的输入必须按由小到大的序号顺序输入,同时约束变量必须放在运算符的左侧。如(x1+x2-x3=0,不能输为x2-x3+x1=0;x1-x2+x3=0,不能输为x1+x3=x2)
2、输入的约束中不包括“≥”或“≤”,而是用“>”或“<”代替,这不会影响求解。如 对于约束 X1≥2, 则输入 X1>2, 而不是X1≥2。
线性规划问题的计算机求解(2)续
* 允许增加量 = 上限 - 现在值 c1 的允许增加量为 100 - 50 = 50
b1 的允许增加量为 325 - 300 = 25
* 允许减少量 = 现在值 - 下限 c2 的允许减少量为 100 - 50 = 50
b3 的允许减少量为 250 - 200 = 50
* 允许增加的百分比 = 增加量 / 允许增加量
* 允许减少的百分比 = 减少量 / 允许减少量
考虑前面例题的对偶问题: 若设备和原料都用于外协加工,工厂收取加工费。试问:设备工时和原料A、B 各如何收费才最有竞争力? 设 y1 ,y2 ,y3 分别为每设备工时、 原料 A、B每单位的收取费用。
线性规划对偶问题
Max z = 50x1 + 100x2
s.t. x1 + x2 ≤300
2x1 + x2 ≤ 400
x2 ≤ 250
x1 , x2 ≥ 0
Min f = 300y1+ 400y2 + 250y3
s.t. y1+2y2 ≥50 (不少于甲产品的利润)
y1+y2+y3 ≥100 (不少于乙产品的利润)
y1,y2 ,y3 ≥0
线性规划对偶问题
对偶定义
对称形式: 互为对偶
(LP) Max z = cT x (DP) Min f = bT y
s.t. Ax ≤ b s.t. AT y ≥ c
x ≥ 0 y ≥ 0
“Max -- ≤ ” “Min-- ≥”
线性规划对偶问题
一对对称形式的对偶规划之间具有下面的对应关系。
(1)若一个模型为目标求“极大”,约束为“小于等于”的不等式,则它的对偶模型为目标求“极小”,约束是“大于等于”的不等式。即“max,≤”和“min,≥”相对应。
线性规划对偶问题
(2)从约束系数矩阵看:一个模型中为A,则另一个模型中为AT。一个模型是m个约束,n个变量,则它的对偶模型为n个约束,m个变量。
(3)从数据b、C 的位置看:在两个规划模型中,b和C 的位置对换。
(4)两个规划模型中的变量皆非负。
线性规划对偶问题
非对称形式的对偶规划
一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。
对于非对称形式的规划,可以按照下面的对应关系直接给出其对偶规划:
(1)将模型统一为“max,≤”或“min,≥” 的形式,对于其中的等式约束按下面(2)、(3)中的方法处理;
(2)若原规划的某个约束条件为等式约束,则在对偶规划中与此约束对应的那个变量取值没有非负限制;
线性规划对偶问题
(3)若原规划的某个变量的值没有非负限 制,则在对偶问题中与此变量对应的那个约束为等式。
下面对关系(2)作一说明。对于关系(3)
可以给出类似的解释。
设原规划中第一个约束为等式:
a11x1 + … + a1nxn = b1
那么,这个等式与下面两个不等式等价
线性规划对偶问题
a11x1+…+a1nxn≥b1
a11x1+…+a1nxn≤b1
这样,原规划模型可以写成
maxZ=c1x1+∧+cnxn
a11x1+∧+a1nxn≤b1
-a11x1-∧-a1nxn≤-b1
M
am1x1+∧+amnxn≤bm
xj≥0,j=1,2, ∧,m
线性规划对偶问题
此时已转化为对称形式,直接写出对偶规划
minf=b1y1’-b1y1’’+b2y2+∧+bmym
a11y1’-a11y1’’∧+am1ym≥c1
a12y1’-a12y1’’∧+am2ym≥c2
M
a1ny1’-a1ny1’’∧+amnym≥cn
y1’,,y1’’,y2,∧,ym≥0,y1
这里,把y1看作是y1=y1’-y1’’,
于是y1没有非负限制,关系(2)的说明完毕。
线性规划对偶问题
例3.1写出下面线性规划的对偶规划模型:
maxZ=x1-x2+5x3-7x4
x1+3x2-2x3+x4=25
2x1+7x3+2x4≥-60
2x1+2x2-4x3≤30
-5≤x4≤10,x1,x2, ≥0,x3没有非负限制
解先将约束条件变形为“≤”形式
线性规划对偶问题
x1+3x2-2x3+x4=25
-2x1-7x3-2x4 ≤60
2x1+2x2-4x3 ≤30
x4 ≤10
-x4 ≤5
x1≥0,x2≥0,x3,x4没有非负限制
再根据非对称形式的对应关系,直
接写出对偶规划
线性规划对偶问题
minf =25y1+60y2+30y3+10y4+5y5
y1-2y2+2y3≥1
3y1+2y3 ≥-1
-2y1-7y2-4y3=5
y1-2y2+y4-y5= -7
y1没有非负限制,y2,y3,y4,y5≥0
线性规划对偶问题
影子价格 —— 是一个向量,它的分量表示最优目标值随相应资源数量变化的变化率。
若x*,y* 分别为(LP)和(DP)的最优解,
那么, cT x* = bT y* 。
根据 f = bTy*=b1y1*+b2y2*++bmym*
可知 f / bi = yi*
yi* 表示 bi 变化1个单位对目标 f 产生的影响,称 yi* 为 bi的影子价格。
线性规划对偶问题
影子价格的经济含义
(1)影子价格是对现有资源实现最大效益时的一种估价
企业可以根据现有资源的影子价格,对资源的使用有两种考虑:第一,是否将设备用于外加工或出租,若租费高于某设备的影子价格,可考虑出租该设备,否则不宜出租。第二,是否将投资用于购买设备,以扩大生产能力,若市价低于某设备的影子价格,可考虑买进该设备,否则不宜买进。
线性规划对偶问题
(2)影子价格表明资源增加对总效益产生的影响,根据理论“设x0和y0分别为原规划(P )和对偶规划(D)的可行解,当cx0=bty0时,x0,y0分别是两个问题的最优解”可知,在最优解的情况下,有关系:
Z*=f *=b1y1*+b2y2*∧+bmym*根
因此,可以将z*看作是bi,i=1,2,…,m的函数,对bi求偏导数可得到:
﹠z*
=yi*i=1,2, ∧,m
﹠bi
这说明,如果右端常数增加一个单位,则目标函数值的增量将是:
yi*,i=1,2, ∧,m
线性规划对偶问题
影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力,考虑增加设备,就应该从影子价格高的设备入手。这样可以用较少的局部努力,获得较大的整体效益。
线性规划对偶问题
需要指出,影子价格不是固定不变的,当约束条件、产品利润等发生变化时,有可能使影子价格发生变化。另外,影子价格的经济含义是指资源在一定范围内增加时的情况,当某种资源的增加超过了这个“一定的范围”时,总利润的增加量则不是按照影子价格给出的数值线性地增加。
线性规划在工商管理中的应用(1)续
解:设 xi 表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的
数学模型。
目标函数: Min x1 + x2 + x3 + x4 + x5 + x6
约束条件:s.t. x1 + x6 ≥ 60
x1 + x2 ≥ 70
x2 + x3 ≥ 60
x3 + x4 ≥ 50
x4 + x5 ≥ 20
x5 + x6 ≥ 30
x1,x2,x3,x4,x5,x6 ≥ 0
线性规划在工商管理中的应用(2)续
解:设 xi ( i = 1~7)表示星期一至日开始休息的人数,这样我们建立如下的
数学模型。
目标函数: Min x1 + x2 + x3 + x4 + x5 + x6 + x7
约束条件:s.t. x1 + x2 + x3 + x4 + x5 ≥ 28
x2 + x3 + x4 + x5 + x6 ≥ 15
x3 + x4 + x5 + x6 + x7 ≥ 24
x4 + x5 + x6 + x7 + x1 ≥ 25
x5 + x6 + x7 + x1 + x2 ≥ 19
x6 + x7 + x1 + x2 + x3 ≥ 31
x7 + x1 + x2 + x3 + x4 ≥ 28
x1,x2,x3,x4,x5,x6,x7 ≥ 0
线性规划在工商管理中的应用(3)续
解:设 x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数, x4,x5 分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。
求 xi 的利润:利润 = 售价 - 各成本之和
可得到 xi (i = 1,2,3,4,5) 的利润分别为 15、10、7、13、9 元。
这样我们建立如下的数学模型。
目标函数: Max 15x1 + 10x2 + 7x3 + 13x4 + 9x5
约束条件: s.t. 5x1 + 10x2 + 7x3 ≤ 8000
6x1 + 4x2 + 8x3 + 6x4 + 4x5 ≤ 12000
3x1 + 2x2 + 2x3 + 3x4 + 2x5 ≤ 10000
x1,x2,x3,x4,x5 ≥ 0
线性规划在工商管理中的应用(4)续
解:设 xijk 表示第 i 种产品,在第 j 种工序上的第 k 种设备上加工的数量。
利润 = [(销售单价 - 原料单价)* 产品件数]之和 - (每台时的设备费用*设备实际使用的总台时数)之和。 这样我们建立如下的数学模型:
Max 0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123
s.t. 5x111 + 10x211 ≤ 6000 ( 设备 A1 )
7x112 + 9x212 + 12x312 ≤ 10000 ( 设备 A2 )
6x121 + 8x221 ≤ 4000 ( 设备 B1 )
4x122 + 11x322 ≤ 7000 ( 设备 B2 )
7x123 ≤ 4000 ( 设备 B3 )
x111+ x112- x121- x122- x123 = 0 (Ⅰ产品在A、B工序加工的数量相等)
x211+ x212- x221 = 0 (Ⅱ产品在A、B工序加工的数量相等)
x312 - x322 = 0 (Ⅲ产品在A、B工序加工的数量相等)
xijk ≥ 0 , i = 1,2,3; j = 1,2; k = 1,2,3
线性规划在工商管理中的应用(5)续
设 x1,x2,x3,x4,x5 分别为上面前 5 种方案下料的原材料根数。
这样我们建立如下的数学模型。
目标函数: Min x1 + x2 + x3 + x4 + x5
约束条件: s.t. x1 + 2x2 + x4 ≥ 100
2x3 + 2x4 + x5 ≥ 100
3x1 + x2 + 2x3 + 3x5 ≥ 100
x1,x2,x3,x4,x5 ≥ 0
线性规划在工商管理中的应用(6)续
解:设 xij 表示第 i 种(甲、乙、丙)产品中原料 j 的含量。这样我们建立数学模型时,要考虑:
对于甲: x11,x12,x13;
对于乙: x21,x22,x23;
对于丙: x31,x32,x33;
对于原料1: x11,x21,x31;
对于原料2: x12,x22,x32;
对于原料3: x13,x23,x33;
目标函数: 利润最大,利润 = 收入 - 原料支出
约束条件: 规格要求 4 个;
供应量限制 3 个。
线性规划在工商管理中的应用(7)续
问:
a)应如何确定这些项目的每年投资额,使得第五年年末拥有资金的本利金额为最大?
b)应如何确定这些项目的每年投资额,使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小?
解: 1)确定决策变量:连续投资问题
设 xij ( i = 1~5,j = 1~4)表示第 i 年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的决策变量:
A x11 x21 x31 x41 x51
B x12 x22 x32 x42
C x33
D x24
线性规划在工商管理中的应用(7续)
2)约束条件:
第一年:A当年末可收回投资,故第一年年初应把全部资金投出去,于是 x11+ x12 = 200;
第二年:B次年末才可收回投资,故第二年年初有资金1.1 x11,于是 x21 + x22+ x24 = 1.1x11;
第三年:年初有资金 1.1x21+ 1.25x12,于是 x31 + x32+ x33 = 1.1x21+ 1.25x12;
第四年:年初有资金 1.1x31+ 1.25x22,于是 x41 + x42 = 1.1x31+ 1.25x22;
第五年:年初有资金 1.1x41+ 1.25x32,于是 x51 = 1.1x41+ 1.25x32;
B、C、D的投资限制: xi2 ≤ 30 ( i =1、2、3、4 ),x33 ≤ 80,x24 ≤ 100
线性规划在工商管理中的应用(7续)
3)目标函数及模型:
a) Max z = 1.1x51+ 1.25x42+ 1.4x33 + 1.55x24
s.t. x11+ x12 = 200
x21 + x22+ x24 = 1.1x11;
x31 + x32+ x33 = 1.1x21+ 1.25x12;
x41 + x42 = 1.1x31+ 1.25x22;
x51 = 1.1x41+ 1.25x32;
xi2 ≤ 30 ( i =1、2、3、4 ),x33 ≤ 80,x24 ≤ 100
xij ≥ 0 ( i = 1、2、3、4、5;j = 1、2、3、4)
b) Min f = (x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24
s.t. x11+ x12 = 200
x21 + x22+ x24 = 1.1x11;
x31 + x32+ x33 = 1.1x21+ 1.25x12;
x41 + x42 = 1.1x31+ 1.25x22;
x51 = 1.1x41+ 1.25x32;
xi2 ≤ 30 ( i =1、2、3、4 ),x33 ≤ 80,x24 ≤ 100
1.1x51 + 1.25x42+ 1.4x33+ 1.55x24 ≥ 330
xij ≥ 0 ( i = 1、2、3、4、5;j = 1、2、3、4)
运 输 问 题(1)
§1 运 输 模 型
例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示,问:应如何调运可使总运输费用最小?
运 输 问 题(1)续
解: 产销平衡问题: 总产量 = 总销量
设 xij 为从产地Ai运往销地Bj的运输量,得到下列运输量表:
运 输 问 题(2)
设 xij 为从产地Ai运往销地Bj的运输量,得到下列一般运输量问题的模型:
m n
Min f = cij xij
i = 1 j = 1
n
s.t. xij = si i = 1,2,…,m
j = 1
m
xij = dj j = 1,2,…,n
i = 1
xij ≥ 0 (i = 1,2,…,m ; j = 1,2,…,n)
运 输 问 题(2)续
变化:
1)有时目标函数求最大 如求利润最大或营业额最大等;
2)当某些运输线路上的能力有限制时,模型中可直接加入(等式或不等式)约束;
3)产销不平衡时,可加入虚设的产地(销大于产时)或销地(产大于销时)。
运 输 问 题(3)续
例3、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示,问:应如何调运可使总运输费用最小?
解:增加一个
虚设的产地
运输费用为0
运输问题(4)续§3 运输问题的应用
解: 根据题意,作出产销平衡与运价表:
这里 M 代表一个很大的正数,其作用是强迫相应的 x31、 x33、 x34取值为0。
运输问题(5)续§3 运输问题的应用
解: 根据题意,作出产销平衡与运价表:
最低要求必须满足,因此把相应的虚设产地运费取为 M ,而最高要求与最低要求的差允许按需要安排,因此把相应的虚设产地运费取为 0 。对应 4”的销量 50 是考虑问题本身适当取的数据,根据产销平衡要求确定 D的产量为 50。
运输问题(6)续§3 运输问题的应用
解: 设 xij为第 i 季度生产的第 j 季度交货的柴油机数目,那末应满足:
交货:x11 = 10 生产:x11 + x12 + x13 + x14 ≤ 25
x12 + x22 = 15 x22 + x23 + x24 ≤ 35
x13 + x23 + x33 = 25 x33 + x34 ≤ 30
x14 + x24 + x34 + x44 = 20 x44 ≤ 10
把第 i 季度生产的柴油机数目看作第 i 个生产厂的产量;把第 j 季度交货的柴油机数目看作第 j 个销售点的销量;成本加储存、维护等费用看作运费。可构造下列产销平衡问题:
目标函数:Min f = 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.25 x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44
运输问题(7)续§3 运输问题的应用
解: 这个生产存储问题可化为运输问题来做。考虑:各月生产与交货分别视为产地和销地
1)1--6月份合计生产能力(包括上年末储存量)为743台,销量为707台。设一假想销地销量为36;
2)上年末库存103台,只有仓储费和运输费,把它列为的0行;
3)6月份的需求除70台销量外,还要80台库存,其需求应为70+80=150台;
4)1--6表示1--6月份正常生产情况, 1’--6’表示1--6月份加班生产情况。
运输问题(8)§3 运输问题的应用
产销平衡与运价表:
运 输 问 题(9)续
解:设 xij 为从 i 到 j 的运输量,可得到有下列特点的线性规划模型:
目标函数:Min f = 所有可能的运输费用(运输单价与运输量乘积之和)
约束条件:
对产地(发点) i :输出量 - 输入量 = 产量
对转运站(中转点):输入量 - 输出量 = 0
对销地(收点) j :输入量 - 输出量 = 销量
运 输 问 题(10)续
用“管理运筹学”软件求得结果:
x13 = 550 x14 = 0 ;
x23 = 0 x24 = 150 x28 = 300 ;
x35 = 200 x36 = 0 x37 = 350 x38 = 0 ;
x45 = 0 x46 = 150 x47 = 0 x48 = 0 。
运输问题(11)续
运输问题(12)续
第三章 整数规划
§1 整数规划的图解法
§2整数规划的计算机求解
§3整数规划的应用
§4整数规划的分枝定界法
§1 整数规划的图解法
例1. 某工厂在计划期内要安排甲、乙两种仪器设备的生产,已知生产仪器设备
需要A、B两种材
料的消耗以及资
源的限制,如右
表。
问题:工厂应分
别生产多少件种仪器设备才
能使工厂获利最多?
§2整数规划的计算机求解
例2:
Max z = 15x1 + 10x2 + 7x3
s.t.
5x1 - 10x2 + 7x3 ≤ 8
6x1 + 4x2 + 8x3 ≤ 12
-3x1 + 2x2 + 2x3 ≤ 10
x1,x2,x3 ≥ 0 为整数
例2:
Max z = 15x1 + 10x2 + 7x3
s.t.
5x1 - 10x2 + 7x3 ≤ 8
6x1 + 4x2 + 8x3 ≤ 12
-3x1 + 2x2 + 2x3 ≤ 10
x1,x2,x3 ≥ 0
x3 为整数 x1 为0-1变量
§3整数规划的应用(1)
一、投资场所的选择
例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部,拟议中有10个位置 Aj (j=1,2,3,…,10)可供选择,考虑到各地区居民的消费水平及居民居住密集度,规定:
在东区由A1 , A2 ,A3 三个点至多选择两个;
在西区由A4 , A5 两个点中至少选一个;
在南区由A6 , A7 两个点中至少选一个;
在北区由A8 , A9 , A10 三个点中至少选两个。
Aj 各点的设备投资及每
年可获利润由于地点不同都
是不一样的,预测情况见右表所
示 (单位:万元)。但投资总额不能超过720万元,问应选择哪几个销售点,可使年利润为最大?
§3整数规划的应用(1)续
解:设:0--1变量 xi = 1 (Ai 点被选用)或 0 (Ai 点没被选用)。
这样我们可建立如下的数学模型:
Max z =36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10
s.t. 100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10 ≤ 720
x1 + x2 + x3 ≤ 2
x4 + x5 ≥ 1
x6 + x7 ≥ 1
x8 + x9 + x10 ≥ 2
xj ≥ 0 且xj 为0--1变量,i = 1,2,3,……,10
二、固定成本问题
例5.高压容器公司制造小、中、大三种尺寸的金属容器,所用资源为金属板、劳动力和机器设备,制造一个容器所需的各种资源的数量如下表所示。不考虑固定费用,每种容器售出一只所得的利润分别为 4万元、5万元、6万元,可使用的金
属板有500吨,劳动力有300人月,机器有100台月,此外不管每种容器制造的数量是多少,都要支付一笔固定的费用:小号是l00万元,中号为 150 万元,大号为200万元。现在要制定一个生产计划,使获得的利润为最大。
§3整数规划的应用(3)续
解:引入0—1变量 xij,并令
xij = 1(当指派第 i人去完成第j项工作时)或0(当不指派第 i人去完成第j项工作时).
这可以表示为一个0--1整数规划问题:
Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41 +21x42+23x43+17x44
s.t. x11+ x12+ x13+ x14= 1 (甲只能干一项工作)
x21+ x22+ x23+ x24= 1 (乙只能干一项工作)
x31+ x32+ x33+ x34= 1 (丙只能干一项工作)
x41+ x42+ x43+ x44= 1 (丁只能干一项工作)
x11+ x21+ x31+ x41= 1 ( A工作只能一人干)
x12+ x22+ x32+ x42= 1 ( B工作只能一人干)
x13+ x23+ x33+ x43= 1 ( C工作只能一人干)
x14+ x24+ x34+ x44= 1 ( D工作只能一人干)
xij 为0--1变量,i,j = 1,2,3,4
* * * 求解可用《管理运筹学》软件中整数规划方法。
§3整数规划的应用(4)续
解: a) 设 xij为从Ai 运往Bj 的运输量(单位千箱), yk = 1(当Ak 被选中时)或0(当Ak 没被选中时),k =2,3,4,5.
这可以表示为一个整数规划问题:
Min z = 175y2+300y3+375y4+500y5+ 8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41 +7x42+5x43+10x51 +4x52+2x53
其中前4项为固定投资额,后面的项为运输费用。
s.t. x11+ x12+ x13 ≤ 30 ( A1 厂的产量限制)
x21+ x22+ x23 ≤ 10y2 ( A2 厂的产量限制)
x31+ x32+ x33 ≤ 20y3 ( A3 厂的产量限制)
x41+ x42+ x43 ≤ 30y4 ( A4 厂的产量限制)
x51+ x52+ x53 ≤ 40y5 ( A5 厂的产量限制)
x11+ x21+ x31+ x41 + x51 = 30 ( B1 销地的限制)
x12+ x22+ x32+ x42 + x52 = 20 ( B2 销地的限制)
x13+ x23+ x33+ x43 + x53 = 20 ( B3 销地的限制)
xij ≥0,i = 1,2,3,4,5; j = 1,2,3, yk 为0--1变量,k = 2,3,4,5。
* * * 求解可用《管理运筹学》软件中整数规划方法。
§3整数规划的应用(5)续
解:1) 设xiA、xiB、xiC、xiD ( i =1,2,3,4,5)分别表示第 i 年年初给项目A,B,C,D的投资额;
设yiA, yiB,是0—1变量,并规定取 1 时分别表示第 i 年给A、B投资,否则取 0( i = 1, 2, 3, 4, 5)。
设yiC 是非负整数变量,并规定:2年投资C项目8万元时,取值为4;
2年投资C项目6万元时,取值为3;
2年投资C项目4万元时,取值为2;
2年投资C项目2万元时,取值为1;
2年不投资C项目时, 取值为0;
这样我们建立如下的决策变量:
第1年 第2年 第3年 第4年 第5年
A x1A x2A x3A x4A
B x3B
C x2C (=20000y2C)
D x1D x2D x3D x4D x5D
§3整数规划的应用(6)续
3)目标函数及模型:
Max z = 1.15x4A+ 1.40x2C+ 1.28x3B + 1.06x5D
s.t. x1A+ x1D = 100000;
x2A+x2C+x2D = 1.06x1D;
x3A+x3B+x3D = 1.15x1A+ 1.06x2D;
x4A+x4D = 1.15x2A+ 1.06x3D;
x5D = 1.15x3A+ 1.06x4D;
x1A ≥ 40000y1A ,
x1A ≤ 200000y1A ,
x3B ≥ 30000y3B ,
x3B ≤ 50000y3B ;
x2C = 20000y2C ,
yiA, yiB = 0 或 1,i = 1,2,3,4,5
y2C = 0,1,2,3,4
xiA ,xiB ,xiC ,xiD ≥ 0 ( i = 1、2、3、4、5)
§4整数规划的分枝定界法(1)
问题(A) Min z = c1 x1 + c2 x2 + … + cn xn 记 问题(B)为去掉整数约束的问题(A)
s.t. a11 x1 + a12 x2 + … + a1n xn = b1
a21 x1 + a22 x2 + … + a2n xn = b2
…… ……
am1 x1 + am2 x2 + … + amn xn = bm
x1 ,x2 ,… ,xn ≥ 0 为整数
在分枝定界法过程中求解问题(B),应有以下情况之一:
①(B)无可行解,则(A)亦无可行解,停止对此问题的计算;
②(B)有最优解,并满足整数约束,即同时为(A)的最优解,那么z*同时是当前问题(A)最优目标值的上界和下界。停止对这个问题的计算;
③(B)有最优解 x 及最优值 z 但不符合整数条件。这时得到当前问题(A)最优目标值的一个下界 z =z ,于是通过以下判断可对此问题进一步计算。
§4整数规划的分枝定界法(1)续
分枝定界法的计算过程:
1、对原问题(A),求解松弛问题(B)。根据上面分析,若出现情况①,②则停机。若情况③发生,得到(A)问题最优值的一个下界。我们任找(A)问题的一个可行解,那么对应的目标函数值是(A)最优值的一个上界 z¯ 。即得到 z < z* <z¯。(注:找(A)问题的可行解往往需要较大的计算量,这时可简单记 z¯=+,而先不必费很大力量去求较好的上界。从以下分析可以看到,找到一个好的最优目标值上界,将对算法的快速求得目标非常有效。),转2,进行以下一般步的迭代;
§4整数规划的分枝定界法(2)
2、对当前问题进行分枝和定界:
分技:无妨设当前问题为(A),其松弛问题(B)的最优解不符合整数约束,任取非整数的分量 xr 。构造两个附加约束: xr ≤ [xr] 和 xr ≥ [xr]+1 ,对(A)分别加入这两个约束,可得到两个子问题(A1)和(A2),显然这两个子问题的可行解集的并是(A)的可行解集;
定界:根据前面分析,对每个当前问题(A)可以通过求解松弛问题(B),以及找(A)的可行解得到当前问题的上、下界 z¯和 z 。
对一般迭代步,设根据分枝定界方法得到了原问题(A)的一个同层子问题(AI ),i=1,2,...,n 之和的分解。这里的同层子问题是指每个子问题(AI)都是(A)经过相同分枝次数得到的。
§4整数规划的分枝定界法(2)续
3、比较与剪枝:
对当前子问题进行考察,若不需再进行计算,则称之为剪枝。一般遇到下列情况就需剪枝:
①(B)无可行解;
②(B)的最优解符合整数约束;
③(B)的最优值 z ≥ z¯ 。
通过比较,若子问题不剪枝则返回 2 。
分枝定界法当所有子问题都剪枝了,即没有需要处理的子问题时,达到当前上界 z¯ 的可行解即原问题的最优解, 算法结束。
§4整数规划的分枝定界法(3)
分枝定界法是求整数规划的一种常用的有效的方法,既能解决纯整数规划的问题,也能解决混合整数规划的问题。
例:
Min f = -5x1-4x2
s.t. 3x1+4x2 ≤ 24
9x1+5x2 ≤ 45
x1,x2 ≥ 0 整数
§4整数规划的分枝定界法(4)
隐枚举法是求解0—1规划最常用的方法之一
对于 n 个决策变量的完全 0—1 规划,其可行点最多有 2n 个,当 n 较大时其计算量大得惊人。隐枚举法的基本思想是根据0—1规划的特点,进行分技逐步求解。
1、用于隐枚举法的0—1规划标准形式:
为了计算的方便,需要把一般的 0—1规划问题等价地化成下列标准形式
Min f = c1 x1 + c2 x2 + … + cn xn cj ≥ 0 j = 1,2,…,n
s.t. ai1 x1 + ai2 x2 + … + ain xn ≤ bi i = 1,2,…,m
x1 ,x2 ,… ,xn = 0 或 1
§4整数规划的分枝定界法(4)续
下面说明一个完全的0—1规划问题可以化为等价的标准形式:
(1)若目标函数求最大:Max z,可令 f = - z,变为求最小 Min f ;
(2)若目标函数的系数有负值时,如 cj <0。那么,可以令相应的 yj = 1- xj ;
(3)当某个约束不等式是“≥”时,只需两端同乘以 -1,即变为“≤” ;
(4)当某个约束是等式约束时,可得到两个方向相反的不等式。
§4整数规划的分枝定界法(5)
隐枚举法的基本过程:
1、将0—1规划问题化为标准形式,设其最优解为 x*,最优目标值为 f* 。显然 x = 0 时,目标值 f =0 是不考虑线性不等式约束的最小解,于是 f* ≥ 0。若 x = 0 是可行解,那末 f =0是该问题的最优解,结束计算。否则,置所有分量为自由变量。转2;
2、任选一自由变量 xk ,令 xk 为固定变量,分别固定为 xk = 0 与 xk =1,令所有自由变量取零值,则得到两个分枝。对每个分枝的试探解进行检验(把自由变量逐次定为固定变量的顺序可以是任意的,在不进行先验考察时,常按指标变量从小到大的顺序进行)。转3;
§4整数规划的分枝定界法(5)续
3、检验当前试探解时,遇到下列4种情况就剪枝,即不必再向下分枝,在剪枝的子问题下方标记“×”:
情况一:若子问题的试探解可行,即满足所有线性不等式约束,则此问题的目标值是原问题最优目标值的一个上界记为 f¯ 即 f* ≤ f¯ 。把 f¯ 的值记在子问题框的旁边,并在下方标记上“×”;
§4整数规划的分枝定界法(6)
情况二:若试探解不可行,且存在一个线性不等式约束,将所有固定变量值代入后,所得到的不等式中所有负系数之和大于右端项或若无负系数时,最小的系数大于右端项,那么此问题的任何分枝都是不可行的问题。于是在此问题框的下方标记“×”;
情况三:若试探解不可行,且它的目标值与目标函数中对应当前自由变量的任一个系数之和大于所有已得到的上界中最小者时,说明在当前问题的基础上,固定任何自由变量都不可能对目标函数有改善,于是在该问题框的下方标记“×”;
情况四:若试探解不可行,但所有变量已被置为固定变量,也应剪枝,于是在该问题框的下方标记“×”。
把已标记“×”的子问题,称为已探明的枝。转4。
§4整数规划的分枝定界法(6)续
4、进一步考察。如果所有的枝均为已探明的枝,则停机结束计算。找出所有子问题框边标记 f¯ 值的问题,比较得到其中最小者,其对应的试探解即原问题的最优解,相应值即原问题的最优目标值 f*;若没有标记 f¯ 值的框,则说明原问题无最优解,实际上原问题无可行解。
如果仍存在尚未探明的分枝,则可任选一个未探明的分枝。转2。
§4整数规划的分枝定界法(7)
0-1规划的隐枚举法
例:
Max z=100x1+30x2+40x3+45x4
s.t. 50x1+30x2+25x3+10x4≤95
7x1+ 2x2+ 3x3+ 4x4≤11
2x1+ x2+ x3+10x4≤12
x4 ≤ x2+ x3
xj= 0 或 1 ,i = 1,2,3,4
标准化:
取f’=-z=-100x1-30x2-40x3 -45x4
令 y1=1-x1, y2=1-x2, y3=1-x3, y4=1-x4
f’=100y1+30y2+40y3 +45y4-215,
记 f = f’ + 215, 得到
Min f=100y1+30y2+40y3 +45y4
s.t.
-50y1-30y2-25y3 -10y4≤-20
- 7y1- 2y2- 2y3 - 4y4≤- 4
- 2y1- y2- y3 -10y4≤- 2
y2+ y3 - y4≤ 1
yj= 0 或 1 ,i = 1,2,3,4
第四章 动态规划
第五章 存贮论(Inventory Theory)
§1 经济订购批量存贮模型
§2 经济生产批量模型
§3允许缺货的 经济订购批量模型
§4允许缺货的 经济生产批量模型
§5 经济订购批量折扣模型
§6需求为随机的单一周期的存贮模型
§7需求为随机变量的订货批量、再订货点模型
§8需求为随机变量的定期检查存贮量模型
§9物料需求计划(MRP)与准时化生产方式(JIT)简介
第五章 存贮论
存贮是缓解供应与需求之间出现的供不应求或供过于求等不协调情况的必要和有效的方法和措施。
但是,要存贮就需要资金和维护,存贮的费用在企业经营的成本中占据非常大的部分。
存贮论主要解决存贮策略问题,即如下两个问题:
1.补充存贮物资时,每次补充数量(Q)是多少?
2.应该间隔多长时间( T )来补充这些存贮物资?
建立不同的存贮模型来解决上面两个问题,如果模型中的需求率、生产率等一些数据皆为确定的数值时,存贮模型被称为确定性存贮摸型;如果模型中含有随机变量则被称为随机性存贮模型。
§1 经济订购批量存贮模型
经济订购批量存贮模型,又称不允许缺货,生产时间很短存贮模型,是一种最基本的确定性存贮模型。在这种模型里,需求率即单位时间从存贮中取走物资的数量是常量或近似乎常量;当存贮降为零时,可以立即得到补充并且所要补充的数量全部同时到位(包括生产时间很短的情况,我们可以把生产时间近似地看成零)。这种模型不允许缺货,并要求单位存贮费,每次订购费,每次订货量都是常数,分别为一些确定的、不变的数值。
主要参数:
需求率 : d
单位货物单位时间的存贮费: c1
每次订购费: c3
每次订货量: Q
是一些确定的、不变的数值。
§1 经济订购批量存贮模型
各参量之间的关系:
订货量 Q 单位存贮费 c1 每次订购费 c3
越小 存贮费用越小 订购费用越大
越大 存贮费用越大 订购费用越小
存贮量Q与时间 t 的关系
§1 经济订购批量存贮模型
这种存贮模型的特点:
1. 需求率 (单位时间的需求量)为 d;
2. 无限供货率(单位时间内入库的货物数量) ;
3. 不允许缺货;
4. 单位货物单位时间的存贮费 c1 ;
5. 每次的订货费 c3 ;
6. 每期初进行补充,即期初存贮量为Q 。
单位时间内的总费用=单位时间内的存贮费用+单位时间内的订货费用
单位时间内的存贮费用=单位时间内购买货物所占用资金的利息
+贮存仓库的费用+保险费用+损耗费用+管理费用等
设每次的订货量为Q,由于补充的货物全部同时到位,故0时刻的存贮量为Q。到T时刻存贮量为0,则0到T时间内的平均存贮量为Q/2。又设单位时间内的总需求量为D,(单位货物的进价成本即货物单价为c),则
§1 经济订购批量存贮模型
单位时间内的总费用
求极值得使总费用最小的订购批量为
这是存贮论中著名的经济订购批量公式,也称哈里斯-威尔逊公式。
单位时间内的存贮费用=
单位时间内的订货费用=
单位时间内的总费用=
§1 经济订购批量存贮模型
经济生产批量模型也称不允许缺货、生产需要一定时间模型,这也是一种确定型的存贮模型。它的存贮状态图为
§2 经济生产批量模型
2. 生产率(单位时间的产量)为 p — 有限供货率;
3. 不允许缺货;
4. 单位产品单位时间的存贮费 c1 ;
5. 每次的生产准备费 c3 ;
6. 每期初进行补充。
设每次生产量为 Q ,由于生产率是 p,则每次的生产时间 t 为Q/ p ,于是最高库存量为 (p-d) Q/ p。到T 时刻存贮量为0,则0到T时间内的平均存贮量为 (p-d) Q/2p 。故单位时间的存贮费为:
另一方面,设D为产品的单位时间需求量,则单位时间的生产准备费为 c3 D /Q ,进而,单位时间的总费用TC为:
§3 允许缺货的经济订购批量模型
使TC达最小值的最佳订购量
订购量为Q*时的最大缺货量
单位时间的最低总费用
订购量为Q*时的最大存贮量为
每个周期T所需时间
显然, 时,允许缺货订购模型趋于经济订购批量模型。
§4 允许缺货的经济生产批量模型(1)
此模型与经济生产批量模型相比,放宽了假设条件:允许缺货。与允许缺货的经济订货批量模型相比,相差的只是:补充不是靠订货,而是靠生产逐步补充,因此,补充数量不能同时到位。开始生产时,一部分产品满足需要,剩余产品作为存贮。生产停止时,靠存贮量来满足需要。
这种模型的存贮状态图为 :
§4 允许缺货的经济生产批量模型(2)
存贮量
§4 允许缺货的经济生产批量模型(3)
这种存贮模型的特点:
1. 需求率 (单位时间的需求量)为 d;
2. 生产率(单位时间的产量)为 p — 有限供货率;
3. 允许缺货,且最大缺货量为S;
4. 单位货物单位时间的存贮费 c1 ;
5. 每次的订货费 c3 ;
6.单位时间缺少一个单位货物所支付的单位缺货费c2 ;
7. 当缺货量达到S时进行补充,且逐步补充到最大存贮量。
§4 允许缺货的经济生产批量模型(4)
单位时间的总费用
TC =(单位时间的存贮费)+(单位时间的生产准备费)
+ (单位时间的缺货费)
=(平均存贮量)×c1 +(单位时间的生产次数)×c3
+ (平均缺货量)×c2
§4 允许缺货的经济生产批量模型(5)
使单位时间总费用TC最小的最优生产量
最优缺货量
单位时间最少的总费用
§5 经济订货批量折扣模型(1)
§5 经济订货批量折扣模型(2)
这种存贮模型的特点:
1. 需求率 (单位时间的需求量)为 d;
2. 无限供货率(单位时间内入库的货物数量) ;
3. 不允许缺货;
4. 单位货物单位时间的存贮费为 c1 ;
5. 每次的订货费为 c3 ;
6. 单位货物的进价成本即货物单价为 c ;
7. 每期初进行补充,即期初存贮量为 Q。
全量折扣模型
设货物单价 c 为订货量 Q 的分段函数,即
c(Q) = ki, Q∈[Qi -1 , Qi ) ,i = 1,2,…,n,
其中 k1 > k2 > … > kn , Q0< Q1< Q2< … < Qn , Q0 是最小订购数量,通常为0; Qn 为最大批量,通常无限制。
§5 经济订货批量折扣模型(3)
下图是 n = 3时 c(Q) 和 TC 的图形表示:
当订货量为Q∈[Qi -1 , Qi ) 时,由于 c(Q)= ki ,则有
由此可见,总费用 TC 也是 Q 的分段函数,具体表示如下:
§5 经济订货批量折扣模型(4)
TC(Q) = TCi, Q∈[Qi -1 , Qi ) , i = 1,2,…,n。
由微积分的有关知识可知,分段函数TC(Q)的最小值只可能在函数导数不存在的点、区间的端点和驻点达到。为此,我们需要先找出这些点。由于 TCi 中的 Dki 是常数,求导数为0,所以,类似于模型一,得 TCi 的驻点
由TC 的图形知,如果 TCi 的驻点 满足 Qi-1< < Qi ,则计算并比较 TCi( ) ,TCi+1(Qi) ,TCi+2(Qi+1), … ,TCn(Qn-1)的值,其中最小者所对应的 Q 即为最佳订货批量Q*,即Q*满足
§5 经济订货批量折扣模型(5)
例4. 图书馆设备公司准备从生产厂家购进阅览桌用于销售,每个阅览桌的价格为500元,每个阅览桌存贮一年的费用为阅览桌价格的20%,每次的订货费为200元,该公司预测这种阅览桌每年的需求为300个。生产厂商为了促进销售规定:如果一次订购量达到或超过50个,每个阅览桌将打九六折,即每个售价为480元;如果一次订购量达到或超过100个,每个阅览桌将打九五折,即每个售价为475元。请决定为使其一年总费用最少的最优订货批量Q*,并求出这时一年的总费用为多少?
解:已知 D = 300个/年,c3 = 200/次 。
Q < 50时, k1 = 500元, =500*20% =100(元/个年)
50 ≤ Q < 100时, k2 = 480元, = 480*20% = 96(元/个年)
100 ≤ Q时, k3 = 475元, = 475*20% = 95(元/个年)
§5 经济订货批量折扣模型(6)
Q < 50时,
50 ≤ Q < 100时,
100 ≤ Q时,
其中只有 在其范围内。
§5 经济订货批量折扣模型(7)
计算得
比较上面的数值,得一年的总费用最少为147600元,因此,最佳订货批量为 Q*= 50。
§6 需求为随机的单一周期存贮模型(1)
在前面讨论的模型中,我们把需求看成是固定不变的已知常量。但是,在现实世界中,更多的情况却是需求为一个随机变量。为此,在本节中我们将介绍需求是随机变量,特别是需求服从均匀分布和正态分布这两种简单情况的存贮模型。
所谓单一周期存贮是指在产品订货、生产、存贮、销售这一周期的最后阶段或者把产品按正常价格全部销售完毕,或者把按正常价格未能销售出去的产品削价销售出去,甚至扔掉。总之,在这一周期内把产品全部处理完毕,而不能把产品放在下一周期里存贮和销售。季节性和易腐保鲜产品,例如季节性的服装、挂历、麦当劳店里的汉堡包等都是按单一周期的方法处理的。报摊销售报纸是需要每天订货的,但今天的报纸今天必须处理完,与明天的报纸无关。因此,我们也可以把它看成是一个单一周期的存贮问题,只不过每天都要作出每天的存贮决策。
§6 需求为随机的单一周期存贮模型(2)
报童问题:报童每天销售报纸的数量是一个随机变量,每日售出 d 份报纸的概率 P(d )(根据以往的经验)是已知的。报童每售出一份报纸赚 k 元,如果报纸未能售出,每份赔 h 元,问报童每日最好准备多少报纸?
这就是一个需求量为随机变量的单一周期的存贮问题。在这个问题中要解决最优订货量 Q 的问题。如果订货量 Q 选得过大,那么报童就会因不能售出报纸造成损失;如果订货量 Q 选得过小,那么报童就要因缺货失去销售机会而造成机会损失。如何适当地选择订货量 Q,才能使这两种损失的期望值之和最小呢?
§6 需求为随机的单一周期存贮模型(3)
设售出d 份报纸的概率为P(d ),从概率论可知
已知因报纸未能售出而造成每份损失 h 元,因缺货而造成机会损失每份k 元,则满足下面不等式的 Q*是这两种损失的期望值之和最小的订报量
例5. 某报亭出售某种报纸,每售出一百张可获利15元,如果当天不能售出,每一百张赔20元。每日售出该报纸份数的概率P(d )根据以往经验如下表所示。试问报亭每日订购多少张该种报纸能使其赚钱的期望值最大。
§6 需求为随机的单一周期存贮模型(4)
解:要使其赚钱的期望值最大,也就是使其因售不出报纸的损失和因缺货失去销售机会的损失的期望值之和为最小。已知 k = 15,h = 20,则有
另有
故当Q = 8时,不等式
成立.因此,最优的订报量为每天800张,此时其赚钱的期望值最大。
§6 需求为随机的单一周期存贮模型(5)
我们可以把公式(12. 42)改写成
公式(12. 43)既适用于离散型随机变量也适用于连续型随机变量。如果只考虑连续型随机变量,公式(12. 43)又可以改写为
§6 需求为随机的单一周期存贮模型(6)
例6. 某书店拟在年前出售一批新年挂历。每售出一本可盈利20元,如果年前不能售出,必须削价处理。由于削价,一定可以售完,此时每本挂历要赔16元。根据以往的经验,市场的需求量近似服从均匀分布,其最低需求为550本,最高需求为1100本,该书店应订购多少新年挂历,使其损失期望值为最小?
解:由题意知挂历的需求量是服从区间[550,1100]上的均匀分布的随机变量, k = 20,h = 16,则其需求量小于Q*的概率为
则由公式(12. 44)得
由此求得 Q*= 856(本),并从 5/9可知,这时有5/9的概率挂历有剩余,有1-5/9=4/9的概率挂历脱销。
§6 需求为随机的单一周期存贮模型(7)
例7. 某化工公司与一客户签订了一项供应一种独特的液体化工产品的合同。客户每隔六个月来购买一次,每次购买的数量是一个随机变量,通过对客户以往需求的统计分析,知道这个随机变量服从以均值 =1000(公斤),方差 =100 (公斤)的正态分布。化工公司生产一公斤此种产品的成本为15元,根据合同固定售价为20元。合同要求化工公司必须按时提供客户的需求。一旦化工公司由于低估了需求产量不能满足需要,那么化工公司就到别的公司以每公斤19元的价格购买更高质量的替代品来满足客户的需要。一旦化工公司由于高估了需求,供大于求,由于这种产品在两个月内要老化,不能存贮至六个月后再供应给客户,只能以每公斤5元的价格处理掉。化工公司应该每次生产多少公斤的产品才使该公司获利的期望值最大呢?
§6 需求为随机的单一周期存贮模型(8)
解:根据题意得 k =5-1= 4,h = 15-5= 10,利用公式(12. 44)得
由于需求服从均值 =1000,方差 =100 的正态分布,上式即为
通过查阅标准正态表,得
把 =1000, =100 代入,得
从 可知,当产量为945公斤时,有0.29的概率产品有剩余,有1-0.29 = 0.71的概率产品将不满足需求。
§7需求为随机变量的订货批量、再订货点模型(1)
本节介绍需求为随机变量的多周期存贮模型。在这种模型里,
由于需求为随机变量,我们无法求得周期(即两次订货时间间隔)的确切时间,也无法求得再次订货点确切来到的时间。
下面我们给出求订货量和再订货点的最优解的近似方法,而精确的数学公式太复杂,这里不作介绍。具体求解步骤如下:
1. 设全年的需求量近似为D,利用经济订货批量存贮模型求出(每次的)最优订货量Q*。
2. 根据具体情况制定出服务水平,即制定在m天里出现缺货的概率,也即不出现缺货的概率为1。利用下式求出 r
P( m 天里需求量 r ) = 1,
其中 r 为再订货点,即当库存量下降到r 时订货, m 天后货到。
存贮的 ( r, Q ) 策略 r 为最低存贮量,即订货点,对库存量随时进行检查,当 H >r 时不补充;当 H ≤ r 时进行补充,每次补充的数量为Q 。
§7需求为随机变量的订货批量、再订货点模型(2)
例8.某装修材料公司经营某品牌的地砖,公司直接从厂家进这种产品。由于公司与厂家距离较远,双方合同规定,在公司填写订货单后一个星期厂家把地砖运到公司。公司根据以往的数据统计分析知道,在一个星期里此种地砖的需求量服从以均值 =850箱,方差 =120箱的正态分布,又知道每次订货费为250元,每箱地砖的成本为48元,存贮一年的存贮费用为成本的20%,即每箱地砖一年的存贮费用为48×20% = 9.6元。公司规定的服务水平为允许由于存贮量不够造成的缺货情况为5%。公司应如何制定存贮策略,使得一年的订货费和存贮费的总和为最少?
解:首先按经济订货批量存贮模型求出最优订货批量Q* 。已知每年的平均需求量 D =8 50 ×52 = 44200 箱/年,c1 = 9.6 元/箱年, c3 = 250元,得
§7需求为随机变量的订货批量、再订货点模型(3)
于是,每年平均约订货 44200/1517≈29次。由服务水平,得
P (一个星期的需求量 r ) = 1 =1 0.05=0.95
进一步,有
查标准正态分布表,得
进一步,有 r = 1047,安全存贮量为 r d m =1047 850 =197箱。
在这样的存贮策略下,在订货期有95%的概率不会出现缺货,有5%的概率会出现缺货。
§8 需求为随机变量的定期检查存贮量模型(1)
需求为随机变量的定期检查存贮量模型是另一种处理多周期的存贮问题的模型。在这个模型里,管理者要订期例如每隔一周、一个月等检查产品的库存量,根据现有的库存量来确定订货量,在这个模型中管理者所要做的决策是:依照规定的服务水平制定出产品的存贮补充水平M。一旦确定了M,也就确定了订货量Q 如下所示:
Q = M H,
式中H 为检查时的库存量。
存贮的 (t,r,M ) 策略
每隔 t 时间检查库存量 H,当 H > r 时不补充;当 H ≤ r 时补充存贮量使之达到 M,补充量为 M H。
§8 需求为随机变量的定期检查存贮量模型(2)
解:设商品A的存贮补充水平为 MA从统计知识可知
P (商品A的需求量d MA ) = 1A =1 0.25=0.975
进一步,有
查标准正态分布表,得
从而 MA = A +1.96 A ≈717(条)。也就是说,商店在每隔两周的清货盘店时,发现A商品还剩 HA 时,马上向厂家订货A商品为 717 HA 条,使得当时A商品的库存量加上订货量正好达到存贮补充水平 717。
第六章 排队论 (Queuing Theory)
排队过程的组成部分
单服务台泊松到达、负指数服务时间的排队模型
多服务台泊松到达、负指数服务时间的排队模型
排队系统的经济分析
单服务台泊松到达、任意服务时间的排队模型
单服务台泊松到达、定长服务时间的排队模型
多服务台泊松到达、任意的服务时间、损失制排队模型
顾客来源有限制排队模型
§1 排队过程的组成部分(1)
一、基本概念
一些排队系统的例子
排队系统 顾 客 服务台 服 务
电话系统 电话呼叫 电话总机 接通呼叫或取消呼叫
售票系统 购票旅客 售票窗口 收款、售票
设备维修 出故障的设备 修理工 排除设备故障
防空系统 进入阵地的敌机 高射炮 瞄准、射击直至敌机被击落或 离开
排队的过程可表示为:
§1 排队过程的组成部分(2)
考虑要点:
1、服务台(或通道)数目:单服务台(单通道)、多服务台(多通道)。
2、顾客到达过程:本教材主要考虑顾客的泊松到达情况。
满足以下四个条件的输入流称为泊松流(泊松过程)
*平稳性:在时间区间 [t, t+t) 内到达k个顾客的概率与t无关,只与 t 有关,记为 pk(t);
*无后效性:不相交的时间区间内到达的顾客数互相独立;
*普通性:在足够短的时间内到达多于一个顾客的概率可以忽略;
*有限性:任意有限个区间内到达有限个顾客的概率等于1。
泊松分布 为单位时间平均到达的顾客数
P (x) = x e- / x! (x = 0, 1, 2,……)
§1 排队过程的组成部分(2)续
3、服务时间分布: 服从负指数分布 为平均服务率,即单位时间服务的顾客数,
P(服务时间≤ t ) = 1- e- t 。
4、排队规则分类
(1) 等待制: 顾客到达后,一直等到服务完毕以后才离去,
先到先服务,后到先服务,随机服务,有优先权的服务;
(2) 损失制: 到达的顾客有一部分未接受服务就离去。
5、平稳状态: 业务活动与时间无关
§1 排队过程的组成部分(3)
§2 单服务台泊松到达、负指数服务时间的排队模型
M / M / 1 / ∞ / ∞
单位时间顾客平均到达数 ,单位平均服务顾客数 (< )
数量指标公式:
1、系统中无顾客的概率 P0 =1 /
2、平均排队的顾客数 Lq =2/( )
3、系统中的平均顾客数 Ls = Lq + /
4、顾客花在排队上的平均等待时间 Wq = Lq /
5、顾客在系统中的平均逗留时间 Ws = Wq+ 1/
6、顾客得不到及时服务必须排队等待的概率 Pw = /
7、系统中恰好有 n 个顾客的概率 Pn =( /)n P0
第七章 对策论
由“齐王赛马”引入
1.对策论的基本概念
对策模型的三个基本要素:
1.局中人:参与对抗的各方;
2.策略集:局中人选择对付其它局中人的行动方案称为策略;某局中人的所有可能策略全体称为策略集;
3.一局势对策的益损值:局中人各自使用一个对策就形成了一个局势,一个局势决定了各局中人的对策结果(量化)称为该局势对策的益损值。
“齐王赛马”齐王在各局势中的益损值表(单位:千金)
其中:齐王的策略集: S1={ 1, 2, 3, 4, 5, 6 },
田忌的策略集:S2={ 1, 2, 3, 4, 5, 6 }。
下面矩阵称齐王的赢得矩阵:
3 1 1 1 -1 1
1 3 1 1 1 -1
A= 1 -1 3 1 1 1
-1 1 1 3 1 1
1 1 1 -1 3 1
1 1 -1 1 1 3
1.对策论的基本概念(续)
二人有限零和对策(又称矩阵对策):
局中人为2;每个局中人的策略集的策略数目都是有限的;每一局势的对策均有确定的损益值,并且对同一局势的两个局中人的益损值之和为零。
通常将矩阵对策记为: G = {S1, S2, A}
S1:甲的策略集; S2:乙的策略集;
A:甲的赢得矩阵。
“齐王赛马”是一个矩阵策略。
2.矩阵对策的最优纯策略
在甲方的赢得矩阵中:
A=[aij]m×n
i 行代表甲方策略 i=1, 2, …, m;j 行代表乙方策略 j=1, 2, …, n;aij 代表甲方取策略 i,乙方取策略 j,这一局势下甲方的益损值。此时乙方的益损值为 -aij(零和性质)。
在考虑各方采用的策略时,必须注意一个前提,就是双方都是理智的,即双方都是从各自可能出现的最不利的情形选择一种最为有利的情况作为决策的依据。
2.矩阵对策的最优纯策略(续)
例2 某单位采购员在秋天决定冬季取暖用煤的贮两问题。已知在正常的冬季气温条件下要消耗15吨煤,在较暖和较冷的气温条件下要消耗10吨和20吨。假定冬季的煤价随天气寒冷程度而有所变化,在较暖、正常、较冷的气候条件下每吨煤价分别为10元,15元和20元,又设秋季时煤价为每吨10元。在没有关于当年冬季准确的气象预报的条件下,秋季贮煤多少吨能使单位的支出最少?
解:
局中人I为采购员;局中人II为大自然,采购员有三个策略,在秋季买10吨、15吨和20吨,分别记为1、2 、3,大自然也有三个策略,分别为较暖、正常和较冷,记为1、2、 3。
以冬季取暖用煤实际费用,作为局中I采购员的赢得,得到赢得矩阵如下:
1(较暖) 2 (正常) 3 (较冷) min
1 -100 -175 -300 -300
2 -150 -150 -250 -250
3 -200 -200 -200 -200
Max -100 -150 -200
得 max min aij=min max aij=a32=-200
3.矩阵对策的混合策略
设矩阵对策 G = { S1, S2, A }。当
max min aij min max aij
i j j i
时,不存在最优纯策略。
例:设一个赢得矩阵如下:
min
5 9 5
A = max 6 策略2
8 6 6 i
max 8 9
min 8 策略1
j
当甲取策略2 ,乙取策略1时,甲实际赢得8比预期的多2,乙当然不满意。考虑到甲可能取策略2这一点,乙采取策略2。若甲也分析到乙可能采取策略2这一点,取策略1,则赢得更多为9 … 。此时,对两个局中人甲、乙来说,没有一个双方均可接受的平衡局势,其主要原因是甲和乙没有执行上述原则的共同基础,即 max min aij min max aij 。
i j j i
一个自然的想法:对甲(乙)给出一个选取不同策略的概率分布,以使甲(乙)在各种情况下的平均赢得(损失)最多(最少)-----即混合策略。
求解混合策略的问题有图解法、迭代法、线性方程法和线性规划法等我们这里只介绍线性规划法,其他方法略。
例:设甲使用策略1的概率为X1′,使用策略2的概率为X2′ ,并设在最坏的情况下,甲赢得的平均值为V(未知)。
5 9
A= STEP 1
8 6 1) X1′+X2′=1
X1′, X2′0
2)无论乙取何策略,甲的平均赢得应不少于V:
对乙取1: 5X1’+ 8X2’ V
对乙取2: 9X1’+ 6X2’ V
注意 V>0,因为A各元素为正。
STEP 2
作变换: X1= X1’/V ; X2= X2’/V
得到上述关系式变为:
X1+ X2=1/V (V愈大愈好)待定
5X1+ 8X21
9X1+ 6X21
X1, X20
建立线性模型:
min X1+X2
s.t. 5X1+8X21 X1= 1/21
9X1+6X21 X2= 2/21
X1, X20 1/V= X1+X2=1/7
所以,V=7
返回原问题: X1’= X1V= 1/3
X2’= X2V= 2/3
于是甲的最优混合策略为:
以1/3的概率选1, 以2/3的概率选2,最优值V=7.
3.矩阵对策的混合策略(续)
例:求解“齐王赛马”问题。
优超原则:
假设矩阵对策 G ={ S1, S2, A }
甲方赢得矩阵 A=[aij]mn
若存在两行(列),s 行(列)的各元素均优于 t 行(列)的元素,即
asjatj j=1,2 … n ( ais ait i=1,2 … m )
称甲方策略s优超于t ( s优超于t)
3.矩阵对策的混合策略(续)
优超原则:当局中人甲方的策略t被其它策略所优超时,可在其赢得矩阵A中划去第t行(同理,当局中人乙方的策略t被其它策略所优超时,可在矩阵A中划去第t列)。
如此得到阶数较小的赢得矩阵A’,其对应的矩阵对策
G’= { S1, S2, A’} 与 G = { S1, S2, A }
等价,即解相同。
3.矩阵对策的混合策略(续)
例 5. 设甲方的益损值,赢得矩阵为
3 2 0 3 0 被第3、4行所优超
5 0 2 5 9 被第3行所优超
A= 7 3 9 5 9
4 6 8 7 5.5
6 0 8 8 3
得到
7 3 9 5 9 被第1列所优超
A1= 4 6 8 7 5.5 被第2列所优超
6 0 8 8 3
3.矩阵对策的混合策略(续)
3.矩阵对策的混合策略(续)
对A4计算,用线性规划方法得到:
(注意:余下的策略为3,4,1,2)
甲: X* = (0,0,1/15,2/15,0)T V=5
X*’= (0,0,1/3 ,2/3 ,0)T
乙: Y* = (1/10,1/10,0,0,0)T V=5
Y*’= (1/2 ,1/2 ,0,0,0)T 。
注:
利用有超原则化简赢得矩阵时,有可能将原对策问题的解也划去一些(多解情况);
线性规划求解时有可能是多解问题。
习题:P343-1,3,4
第八章 决策分析
“决策” 一词来源于英语 Decision making,直译为“做出决定”。所谓决策,就是为了实现预定的目标在若干可供选择的方案中,选出一个最佳行动方案的过程,它是一门帮助人们科学地决策的理论。
第十五章 决策分析
决策的分类:
按决策问题的重要性分类
按决策问题出现的重复程度分类
按决策问题的定量分析和定性分析分类
按决策问题的自然状态发生分类:
第十五章 决策分析
确 定 型 决 策 问 题
在决策环境完全确定的条件下进行,
不 确 定 型 决 策 问 题
在决策环境不确定的条件下进行,决策者对各自然状态发生的概率一无所知
风 险 型 决 策 问 题
在决策环境不确定的条件下进行,决策者对各自然状态发生的概率可以预先估计或计算出来
第十五章 决策分析
构成决策问题的四个要素:
决策目标、行动方案、自然状态、效益值
行动方案集: A = { s1, s2, …, sm }
自然状态集: N = { n1, n2, …, nk }
效益(函数)值:v = ( si, nj )
自然状态发生的概率P=P(sj) j =1, 2, …, m
决策模型的基本结构:(A, N, P, V)
基本结构(A, N, P, V)常用决策表、决策树等表示
§1 不确定情况下的决策
特征:1、自然状态已知;2、各方案在不同自然状态下的收益值已知;3、自然状态发生不确定。
例:某公司需要对某新产品生产批量作出决策,各种批量在不同的自然状态下的收益情况如下表(收益矩阵):
§1 不确定情况下的决策(续)
一、最大最小准则(悲观准则)
决策者从最不利的角度去考虑问题:
先选出每个方案在不同自然状态下的最小收益值(最保险),然后从这些最小收益值中取最大的,从而确定行动方案。 用(Si, Nj)表示收益值
§1 不确定情况下的决策(续)
二、最大最大准则(乐观准则)
决策者从最有利的角度去考虑问题:
先选出每个方案在不同自然状态下的最大收益值(最乐观),然后从这些最大收益值中取最大的,从而确定行动方案。 用(Si, Nj)表示收益值
§1 不确定情况下的决策(续)
三、等可能性准则 ( Laplace准则 )
决策者把各自然状态发生的机会看成是等可能的:
设每个自然状态发生的概率为 1/事件数 ,然后计算各行动方案的收益期望值。
用 E(Si )表示第I方案的收益期望值
§1 不确定情况下的决策(续)
四、乐观系数(折衷)准则(Hurwicz胡魏兹准则)
决策者取乐观准则和悲观准则的折衷:
先确定一个乐观系数 (01),然后计算:CVi = max [(Si, Nj)] +(1- )min [(Si, Nj)]
从这些折衷标准收益值CVi中选取最大的,从而确定行动方案。 取 = 0.7
§1 不确定情况下的决策(续)
五、后悔值准则(Savage 沙万奇准则)
决策者从后悔的角度去考虑问题:
把在不同自然状态下的最大收益值作为理想目标把各方案的收益值与这个最大收益值的差称为未达到理想目标的后悔值,然后从各方案最大后悔值中取最小者,从而确定行动方案。 用aij’表示后悔值,构造后悔值矩阵:
§2 风险型情况下的决策
特征:1、自然状态已知;2、各方案在不同自然状态下的收益值已知;3、自然状态发生的概率分布已知。
一、最大可能准则
在一次或极少数几次的决策中,取概率最大的自然状态,按照确定型问题进行讨论。
§2 风险型情况下的决策(续)
二、期望值准则
根据各自然状态发生的概率,求不同方案的期望收益值,取其中最大者为选择的方案。
E(Si) = P(Nj) (Si,Nj)
§2 风险型情况下的决策(续)
三、决策树法
具体步骤:
(1) 从左向右绘制决策树;
(2) 从右向左计算各方案的期望值,并将结果标在相应方案节点的上方;
(3) 选收益期望值最大(损失期望值最小)的方案为最优方案,并在其它方案分支上打∥记号。
主要符号
决策点 方案节点 结果节点
§2 风险型情况下的决策(续)
前例 根据下图说明S3是最优方案,收益期望值为6.5
§2 风险型情况下的决策(续)
四、灵敏度分析
研究分析决策所用的数据在什么范围内变化时,原最优决策方案仍然有效.
前例 取 P(N1) = p , P(N2) = 1- p . 那么
E(S1) = p30 + (1-p)(-6) = 36p - 6 p=0.35为转折概率
E(S2) = p20 + (1-p)(-2) = 22p - 2 实际的概率值距转
E(S3) = p10 + (1-p)(+5) = 5p + 5 折概率越远越稳定
§2 风险型情况下的决策(续)
五、全情报的价值(EVPI)
全情报:关于自然状况的确切消息。
在前例,当我们不掌握全情报时得到 S3 是最优方案,数学期望最大值为 0.3*10 + 0.7*5 = 6.5万 记为 EVW0PI。
若得到全情报:当知道自然状态为N1时,决策者必采取方案S1,可获得收益30万,概率0.3;当知道自然状态为N2时,决策者必采取方案S3,可获得收益5万, 概率0.7。于是,全情报的期望收益为
EVWPI = 0.3*30 + 0.7*5 = 12.5万
那么, EVPI = EVWPI - EVW0PI = 12.5 - 6.5 = 6万
即这个全情报价值为6万。当获得这个全情报需要的成本小于6万时,决策者应该对取得全情报投资,否则不应投资。
注:一般“全”情报仍然存在可靠性问题。
§2 风险型情况下的决策(续)
六、具有样本情报的决策分析(贝叶斯决策)
先验概率:由过去经验或专家估计的将发生事件的概率;
后验概率:利用样本情报对先验概率修正后得到的概率;
前例,如果请咨询公司进行市场调查,可以根据样本情报来修正先验概率,得到后验概率。如此用决策树方法,可得到更高期望值的决策方案。
在自然状态为Nj的条件下咨询结果为Ik的条件概率,可用全概率公式计算
再用贝叶斯公式计算
条件概率的定义: 乘法公式
§3 效用理论在决策中的应用
效用:衡量决策方案的总体指标,反映决策者对决策问题各种因素的总体看法
使用效用值进行决策:首先把要考虑的因素折合成效用值,然后用决策准则下选出效用值最大的方案,作为最优方案。
例:求下表显示问题的最优方案(万元)
§3 效用理论在决策中的应用(续)
用收益期望值法:
E(S1) = 0.360 + 0.540 + 0.2(-100) = 18万
E(S2) = 0.3100 + 0.5(-40)+ 0.2(-60) = -2万
E(S3) = 0.30 + 0.50 + 0.20 = 0万
得到 S1 是最优方案,最高期望收益18万。
一种考虑:
由于财务情况不佳,公司无法承受S1中亏损100万的风险,也无法承受S2中亏损50万以上的风险,结果公司选择S3,即不作任何项目。
§3 效用理论在决策中的应用(续)
用效用函数解释:
把上表中的最大收益值100万元的效用定为10,即U(100) = 10;最小收益值-100万元的效用定为0,即U(-100) = 0;
对收益60万元确定其效用值:设经理认为使下两项等价的 p=0.95
(1)得到确定的收益60万;
(2)以 p 的概率得到100万,以 1- p 的概率损失100万。
计算得:U(60)= p*U(100)+(1-p)*U(-100) = 0.95*10+0.05*0=9.5
§3 效用理论在决策中的应用(续)
类似地,设收益值为40、0、- 40、- 60相应等价的概率分别为0.90、0.75、0.55、0.40,可得到各效用值:
U(40) = 9.0; U(0) = 7.5; U(-40) = 5.5; U(-60) = 4.0
我们用效用值计算最大期望,如下表:
§3 效用理论在决策中的应用(续)
一般,若收益期望值能合理地反映决策者的看法和偏好,可以用收益期望值进行决策。否则,需要进行效用分析。
收益期望值决策是效用期望值决策的一种特殊情况。
管理运筹学(ppt)
[下载声明]
1.本站的所有资料均为资料作者提供和网友推荐收集整理而来,仅供学习和研究交流使用。如有侵犯到您版权的,请来电指出,本站将立即改正。电话:010-82593357。
2、访问管理资源网的用户必须明白,本站对提供下载的学习资料等不拥有任何权利,版权归该下载资源的合法拥有者所有。
3、本站保证站内提供的所有可下载资源都是按“原样”提供,本站未做过任何改动;但本网站不保证本站提供的下载资源的准确性、安全性和完整性;同时本网站也不承担用户因使用这些下载资源对自己和他人造成任何形式的损失或伤害。
4、未经本网站的明确许可,任何人不得大量链接本站下载资源;不得复制或仿造本网站。本网站对其自行开发的或和他人共同开发的所有内容、技术手段和服务拥有全部知识产权,任何人不得侵害或破坏,也不得擅自使用。
我要上传资料,请点我!
管理工具分类
ISO认证 课程讲义 管理表格 合同大全 法规条例 营销资料 方案报告 说明标准 管理战略 商业计划书 市场分析 战略经营 策划方案 培训讲义 企业上市 采购物流 电子商务 质量管理 企业名录 生产管理 金融知识 电子书 客户管理 企业文化 报告论文 项目管理 财务资料 固定资产 人力资源 管理制度 工作分析 绩效考核资料 面试招聘 人才测评 岗位管理 职业规划 KPI绩效指标 劳资关系 薪酬激励 人力资源案例 人事表格 考勤管理 人事制度 薪资表格 薪资制度 招聘面试表格 岗位分析 员工管理 薪酬管理 绩效管理 入职指引 薪酬设计 绩效管理 绩效管理培训 绩效管理方案 平衡计分卡 绩效评估 绩效考核表格 人力资源规划 安全管理制度 经营管理制度 组织机构管理 办公总务管理 财务管理制度 质量管理制度 会计管理制度 代理连锁制度 销售管理制度 仓库管理制度 CI管理制度 广告策划制度 工程管理制度 采购管理制度 生产管理制度 进出口制度 考勤管理制度 人事管理制度 员工福利制度 咨询诊断制度 信息管理制度 员工培训制度 办公室制度 人力资源管理 企业培训 绩效考核 其它
精品推荐
- 1XX公司战略发展目标(xls 497
- 2“回佣”管理规定 818
- 3通信公司战略的制定方法(pp 551
- 4500强企业管理方法(ppt 933
- 5管理沟通172页(doc) 754
- 6农村基层人才现状的调查与思考 544
- 7企业内部控制应用指引—资产管 885
- 8新创企业的风险管理.ppt 575
- 9逐条点评《劳动合同法实施条例 712
下载排行
- 1社会保障基础知识(ppt) 16695
- 2安全生产事故案例分析(ppt 16695
- 3行政专员岗位职责 16695
- 4品管部岗位职责与任职要求 16695
- 5员工守则 16695
- 6软件验收报告 16695
- 7问卷调查表(范例) 16695
- 8工资发放明细表 16695
- 9文件签收单 16695


