最优装卸安排
五队:廖秋辰沈悦斌杨博
摘要
本文通过对煤矿装卸安排的讨论,首先建立了关于第二工作班调用次数和月滞期费期望的两个概率模型,然后建立了的模型,最后讨论了是否加入第三个工作班和能否加入第四辆标准列车的问题。对于问题一,考虑到每天之间相互影响的概率较小,我们对这一部分做分析后近似求解;对每天相互独立的情况,通过概率模型的建立,运用几何概率的方法求出调用次数的分布律,并根据分布律得出调用期望;最后,对于星期四的情况,我们也采用近似处理的方法;最后得到的一年调用第二个工作班的次数为:757次。对于问题二,也存在每天独立与否的情况,同理在每天相互独立的情况下,通过概率模型的建立,通过联合概率密度函数对二维连续随机变量期望进行求解;在每天相互影响的情况和况和星期四的情况分别进行近似处理。最后得到的月滞期费用为:3.3百万元。对于问题三,对于问题四,通过简单计算得出结论:调用第三个工作班能降低装煤费用,此时每天能再装第四辆标准列车的煤。
其次,我们用计算机模拟的方法求得:一问:一年应调用第二个工作班的次数为:740-780。二问:预期的月滞期费用是:3.55百万元。三问:在模拟出的日调度安排下,各部分总费用都有减少,减少后的费用为劳务费:44.34百万元,滞期费:6.79百万元。第四问:要调用第三个工作班,其中劳务费减少减少31.11,滞期费减少10.87.在调用第三个工作班的情况下,能增加一列标准列车。通过计算机模拟结果的检验,我们发现对各个问题的分析和求解都很符合模拟结果。
关键词:几何概率联合概率密度函数均匀分布分布律
一 问题重述(略)
二 问题分析(见各模型的建立部分)
三 模型假设
1、标准列车到达倒煤台的时点在5点至20点之间均匀随机分布,大容量列车在周四11点至下午1点均匀随机分布。
2、增加装煤工作班不能提高装车速度,每增加一个班倒煤的效率增加一倍。
3、先倒煤后装车,且倒煤台的库存要至少足够装满下一列车才停止装煤。
4、假设一年52周,364天。
5、每个星期四所有能调用的工作班都调用。
6、滞后到第二天的情况相对均匀的分布在一年中。
7、不考虑节假日对工作的影响。
8、平时日指的是周五、周六、周日、周一、周二、周三。 9、装煤工作班可在任意时间调用,可调用任意时间。
10、装煤工作班的在一个时段里的时间所作的事情是均匀的。
四 符号说明
x : 第一列火车到达倒煤台的时刻 y :第二列火车到达倒煤台的时刻 z: 第三列火车到达倒煤台的时刻
:1t 第二列火车和第一列火车到达倒煤台的时间间隔 :1t 第三列火车和第二列火车到达倒煤台的时间间隔
),,(z y x F :调用第二个工作班的次数关于x y z 的函数 n :一天的调用次数
),(21t t F : 调用次数关于21t t 的函数
)(1t g : 第二列火车的滞期时间关于1t 的函数 T :一天的总滞期时间 ),(21t t g : 第三列火车的滞期时间关于21t t 的函数
五 模型的建立与求解
5.1 问题一
5.1.1模型一的建立
将此问题的所有情况分两部分考虑:
第一种情况:当天第一列车到达倒煤台的时候,倒煤台容量满,即当天第一列车的装煤任务不受前一天的影响,那么当天第一列车不需要调用第二个工作班。不包含星期四。
第二种情况:受到前一天的影响,当天第一列车要调用第二个工作班。包含星期四的情况。
于是问题总的求解思路是:
情况一,即是说明了天与天的装煤任务是相互独立的,于是我们建立如下模型: 设x,y,z 分别表示第一、二、三列车到达倒煤台的时刻 1. 用x ,y ,z 表示出调用次数关于列车到达时刻的函数:
),,(z y x F (1) 2. 降维:设,列火车到达的时间间隔表示第一列火车和第二x y t -=1y z t -=2表示第三 列火车和第二列火车到达的时间间隔,于是将上式的),,(z y x F 转化为21t t 和的函数: ),(21t t F (2)
所围成的区域
轴以及直线轴为上的均匀分布,其中)服从区域,随机变量(15y x G G .32121=+t t t t 其中G 区域的面积为:15*15/2=112.5 于是由几何概率的方法得出: 总
S S
P =
(3) 4.得出调用次数n 的分布律:
P(n) (4)
5.根据分布律求出调用次数n 的期望: ∑=?=
2
)()(n n n p n E (5)
情况二的不可能得到精确求解,由于问题的复杂性,需认为进行假设、近似求解: 情况二分析、假设及合理性说明:
1、由于我们不知道列车到达的具体时间,所以我们假设只要没有装车工作就开始倒煤,且在下一列车到达前只调用一个工作班,直到将倒煤台满库。
2、每调用一个工作班增加12000-9000=3000每小时,每列车滞期费至少增加15000每小时,为使得总费用最小所以我们更愿意通过增调工作班来减少滞期时间。所以在列车来后若倒煤台有一列车的煤就先装车再倒煤,若没有一列车的煤则马上调用第二个工作班迅速补上。若有等待的列车则在前一列车走后调用两个工作班倒一列车的煤。
3、作为煤矿公司,当天的事情会尽量当天去做完,尽量不让其拖到第二天5点以后。所以,如果发生第一天的工作可能滞后到第二天时,我们假设最后装完第三列车后就调用第二个工作班,将倒煤台尽量在5点时填满。若无论如何调用仍要滞后则调用3个小时的第二个班。
4、当无论如何也要滞后时,我们就先将滞后对第二天的影响忽略,将滞后的时间挪到第一天空闲的时间上去。因为我们前面有假设滞后到影响第二天的情况在一年中相对均匀分布,所以这个影响在后面的某一年必将用空闲时间来吸收掉。所以我们将其进行一个时空转换直接放到当天去吸收掉。装一列车要3小时,装三列车9小时,一个班倒煤一列4小时,倒煤共用12小时,总共21小时<24小时。即使是一个班也能吸收掉,所以即使是滞后情况在年末分布多一些一年时间有多于一天的滞留的概率也是十分小的,我们可以将365天空出来专门处理,这样,我们就假设一年可以处理完所有滞后影响。
5、由于以上分析,我们将平时的一天考虑为独立的,刚开始时为满库1.5列,第3列车走后花6个小时将倒煤台填满,由此算出调用第二个班次数的期望。最后再补算一年中第三辆车走后要调用第二个班来尽快结束当天工作的次数和由于滞后造成第二天本来不用调用第二个班却不得不调用的次数(我们考虑一种极端情况,三列车都在8点来,平时第一天的影响肯定能被第二天吸收掉,不会拖到第三天,第三天吸收的影响只会是第二天的)。
6、对于周四,即使是全天调用两个班也做不完,必会做25小时以上,既然我们知道当天是完不成工作的,而4列车到达的具体时点是不知道的,那么我们只能让其尽量快的完成,于是我们假设一到星期四,全天的倒煤作业都用两个班,于是周四的调用次数就固定为5次,而周四的滞后对于后面的影响的极限是这种情况:大车14点来,3辆标准车都是当天8点来,于是滞后时间为3*3+6=15加上10-(20-14)=4小时减去晚上的9个小时总共10小时,影响到周五的15点而周五即使是3列车都在8点到所造成的影响也能被周六吸收掉,我们将周四与周五绑定在一起看做一个特殊的平时日则通过挪移则一定能分别在平时日各自的空闲时间中处理掉,而这个平时日的影响看做是周五对周六的影响,但是挪是挪到这整个特殊平时日的空闲时间中。因为25+21=46<48,所以这整个特殊平时日的工作都能在这个特殊平时日处理掉。
5.1.2模型一的求解
情况一的模型精确求解:
1.求函数)
x
y
F:
,
(z
,
2. 求解F(21,t t ) 用y z t x y t -=-=21进行代换降维求解得:
??????
?
?????
?
≥≥≤≥≤+≤≤≤+≤≤≥+≤≤≤+≤≤≥+≤≤+≤=5
70
571127501275119253119253211t 且t 31 11t 且t 32),(212121121112112121121121t t t t t t t t t t t t t t t t t t t t F 且且且且且且
3.求分布律
用几何概率求解方法画图求得概率:
条件表达式中只含21,t t 并且21,t t 在G 上是等可能的 于是可画图求解概率:
即 P (n=0)=1/15 P(n=1)=41/75 P(n=2)=29/75
期望 )(1n E = 56/75+28/75 = 99/75
所以一年内的总调用次数 410)52364()(1=-?N E
情况二的近似求解: 1、周四(N ’1)
因为我们假设周四全用2个班来进行作业,所以一个周四定死为调用5次,N ’1=5*52=260
2、平时日最末为不把工作拖到第二天而调用的次数(N ’2)
若第1列车在11点以后来则要调用,概率:P21=12527
535353=??
若第2列车在15点以后来则要调用,概率:P22=9
1
3131=?
以上两种情况其中有重复的部分,概率:P23=45
1
313151=??
所以N ’2=312*(P21+P22-P23)=95.125
3、平时日对后一天的影响所造成的增加次数(N ’3)
平时日对后一天的影响范围为5点到11点,若将11点视为0,5点视为1,中间的6个小时看做长度1,则服从F (x )=x 2的分布,期望为1/3,即在第一天对第二天产生影响程度的期望是2个小时,而出现影响2个小时的概率为
第1列车在14点以后来,概率:P31=1258
525252=??
第2列车在18点以后来,概率:P32=225
4
152152=?
以上两种情况其中有重复的部分,概率:P33=675
4
15215251=??
P3=0.0782,可以看出使得第二天本来不调用结果由于前一天的影响使其调用相当之小的,这里我们不再细算。期望值为:
34521)(2=+=N N N E
总述: 综上所述:一年来看,调用第二个工作班的总次数为:
757410345)()(21=+=+N E N E 次
故一年总的调用次数为757
5.2 问题二
5.2.1 模型二的建立
采用问题一的解题思路,我们将问题分为三个小部分求解: 第一是每天相互独立且不包含周四的精确求解; 第二是对星期四的近似求解;
第三是每天相互影响的情况的近似求解。 1对每天相互独立的情况的模型建立:
设x ,y ,z 分别表示第一、二、三列火车到达倒煤台的时刻 1).第二列火车的滞期时间与第一列车和第二列车的到达时间有关,根据题意可表示为:
),(y x g (1)
第三列火车的滞期时间与第一、二、三列火车的到达时间都有关,根据题意表示为:
),,(z y x g ' (2)
2).降维:设,列火车到达的时间间隔表示第一列火车和第二x y t -=1y z t -=2表示第三 列火车和第二列火车到达的时间间隔,于是将上式的),(y x g 和),,(z y x g '转化为关于
21t t 和的函数:
),(y x g =)(1t g ),(),,(21t t g z y x g '=' (3)
所围成的区域
轴以及直线轴为上的均匀分布,其中)服从区域,随机变量(15y x G G ).32121=+t t t t 其中G 区域的面积为:15*15/2=112.5 于是:
联合概率密度函数 ???
??∈='其他
),(5
.1121),(2121G t t t t f
),(21t t g 的数学期望 ?
?
+∞∞-+∞∞
-''='21212121),(),()],([dt dt t t f t t g t t g E (4)
同理上的均匀分布。于是:
,服从区间随机变量]150[1t 概率密度函数 ???
??∈=其他
0]15,0[15
1)(11t t f .
)(1t g '的数学期望 1111)()()]([dt t f t g t g E ?
+∞
∞
-'=
(5)
4).一天的总停滞时间 为: 1T =)],([21t t g E '+)]([1t g E (6) 2.星期四的情况:
我们这样考虑星期四的情况:由于大容量列车的存在,使得煤矿公司需用一段时间处理大容量列车,设煤矿公司处理大容量列车的时间为 2T
由于煤矿公司处理大车的时间的耗费,使得标准列车的滞期时间增加T ',分析知道,处理大车用2T 的时间,则综合下来标准列车滞期的时间期望也就应该增加2T 的时间。 2T T =' 此种情况下标准列车的滞期时间期望为:T T '+1 大车本身的滞期时间: 2T ' 3.每天相互影响的情况:
5.2.2模型二的求解
按照模型建立的步骤,没一步的求解如下所示: 1.每天相互独立时 精确求解:
1). 求),(y x g 和),,(z y x g ' 滞后时间关于各列车到达时间x y z 的条件表达式:
2).通过y Z t x y t -=-=21 求出)(1t g 和),(21t t g ':
???
?
???
???
?
??
?
??
?
???
??
?≤≤?≥-≤?≥--≤≤?≤≤--≤?≤≤--≤+≤?≤≤--≤+?≤≤--≤+≤?≤--≤+?≤--='其他
053725374123752123752215192115342191125322151173211739),(21221212121212
1121211212
1211212112121t t t t t t t t t t t t t t t t t t t t t t t t
t t t t t
t t t t t t t t g
?????
????≥≤≤≤≤-≤-=7
750532
534)(g 1111111t t t t
t t t
3).通过期望的求解模型得滞后时间的期望为:
由于)(),(121t g t t g '和属于分段函数,因此在每个分段区间求出各自的期望,计算结果如下 :
)],([21t t g E '
)]([1t g E
所以 )],([21t t g E '=1.82 )]([1t g E =1.02
故1T =2.84
年滞期费为:2.84*(364-52)*5000*3=13.3百万元 月滞期费为:p1=13.3/12=1.11 百万元
2.星期四的单独情况 近似求解
1)周四的滞期费比平日的增加
由于平时的15小时几乎全是在做事情的,将周四单独的作业(从库满到库满)需要10小时,将其硬加进平时的作业很重,则加上大车的影响期望大致也就是10个小时的等待。而小车因为大车的加入,大概也有10小时的滞自费增加,受影响为1列车。
近似计算:
周四的滞期费为10*25000+10*15000=400000
一年:400000*52=20800000
2)周四造成的对于周五的影响的期望的约数
首先,我们有以下事实:
1、大车来的时点的期望在12点
2、滞留的影响是从第二天的5点到14点共9个小时
近似计算:
我们仍采取一问中的用9小时乘以1/3, 估计出对第二天的滞后影响大概是3小时,费用为3*15000=45000
一年:45000*52=2340000
3.每天相互影响的情况近似求解:
由于一问的讨论,有一天有0.0782的概率滞后2小时
近似计算:
我们直接用0.0782*2*15000=2346
一年:2346*364=853944
总的滞期费:
一年:20800000+2340000+853944+2.84*364*15000= 39500000
月滞期费:3950000012=3.3百万元
5.3 问题三
因为我们能够调度标准列车在任意时间准时到来,而劳务费换取滞留费是肯定会降低总的费用,所以平时就尽量让其不产生滞留费,而劳务费让其最小。我们先给出我们所认为一周中最优的调度方案,后面再说明是如何求出的:
平时日:
劳务费:9000*12=108000
滞留费:0
周四:
劳务费期望:9000*12+12000*8+500=209000
滞留费:1*25000+7*15000=130000
一年:
劳务费期望:44330000
滞留费:6760000 总费用:51090000
算法:
由于平时日可以通过调度使得滞留费为0,所以我们只要使得平时日满足此条件即可。剩下的是对周四的调度安排使得滞留费最少,由于周四肯定会由于滞留导致工作拖到周五,那么周五就得尽量再不产生多余劳务费的情况下向后安排,由于平时日产生最小劳务费用所花时间为13个小时(包括最后6小时将倒煤台填满)于是我们定为8点来第一列车,其余的小车跟着就确定了。
对于周四,大车来的时间不知道,但是期望为12点,我们先将大车定死在12点来考虑。
由于第一列车肯定能在12点前装满且不产生滞期费,那么我们肯定将其定在5点到12点之间,而由于第一列车走后来不及装满倒煤台,我们为减少劳务费则令其5点来。 对于第三列车由于大车无论怎样都会滞留到21点以后,而在第一列车和大车之间即使加入第二列车也会产生滞期费,中间是加不了第三列车的,而第三列车在20点来降低的滞期费最少,所以我们说应当考虑的就是第二列车在哪段的问题,若是放在大车之前则10点到达滞期费最少,若是放在大车之后,则放在20点时候滞期费最少。我们将两种情况都进行了计算,发现放到20点结果会优很多,于是时间定死在20点。
对于大车,它在11点至13点之间的出现均匀任意的分布,12点向11点移动时,最后装煤时候劳务费减少,12点向13点移动时,劳务费在后面增多。两者是对称的,期望在12点(由于均匀分布)。然而在12点向11点移动时大车来之前的装煤费用会增多,大小正好与最后的减少相抵消,期望是500元。
5.4 问题四
1)我们通过简单的比较来说明调用第三个工作班能否减少费用: 设列车等待工作班装煤的时间为t
只用一个工作班,总费用: t*5000*3+9000*t=24000t
调用第二个工作班,总费用: t t
t t 180002*120002*90003*5000*2=++
调用第三个工作班,总费用: =++3
*12000*23*90003*5000*3t
t t 16000t
结果:由于16000t t t 2400018000≤≤ 故知道:调用第三个费用为12000每小时的倒煤台操作系统能降低年操作费用。
2)调用第三个工作班后:
关于是否能再装一辆标准车的问题,我们在网上查到了关于煤矿的价格 及一辆标准火车的相关数据,且通过计算机验证,该倒煤台可在一年内
如果增加一列标准车则可增加煤矿公司年收入:1751.75百万元
增加劳务费:387.79百万元减237.95百万元
为149.84百万元
增加滞期费:71.16百万元减30.92百万元
为40.24百万元
总费用增加:190.08百万元
与增加的收入相比非常微小,故可以加一列标准车。
六计算机模拟检验
计算机模拟检验
我们应用visual basic语言对上述问题进行模拟,考虑到计算机模拟只需根据实际情况进行操作判断,所以一些题目假设并未出现在程序中,但是一些基本规则还是不变的。我们应用这种做法在验证结果的同时也可以验证假设的合理性。
程序流程图如下:
程序窗口如下:
第一问:调用第二队平均761次;
第二问:预期月滞期费为3.55百万元;
第三问:调度方案为:
周五,周六,周日,周一,周二,周三为第一辆车8点到,第二辆车,12 点到,第三辆车20点到。
周四第一辆车5点到,大车在11点到13点间随机到达,第二辆车与第三辆车在20点一起到达。
劳务费:44.34百万元滞期费:6.79百万元
总费用:51.13百万元
第四问:增加第三个工作队可减少年操作费:
劳务费由269.06百万元降至237.95百万元。减少31.11百万元
滞期费由41.79百万元降至30.92百万元。减少10.87百万元
新增一辆标准车
增加劳务费:387.79百万元减237.95百万元
为149.84百万元
增加滞期费:71.16百万元减30.92百万元
为40.24百万元
总费用增加:190.08百万元
与增加的收入相比非常微小,故可以加一列标准车。
程序见附录
七模型的评价和改进
6.1评价:
根据这道题,我们先通过合理的假设,建立了概率模型,运用几何概率、联合概率密度函数求概率的方法,求出了比较合理的期望值,估算出题目的答案,然后通过计算机编程,去除为了方便计算的假设,在一定规则下进行仿真模拟,最后得出与计算比较
一致的答案,在模拟的同时,验证了假设的合理性。
利用vb的可视化操作建立工程,运行效率大幅提高,且具有一定的实用价值。
在程序内部安插多个计数器,稍加修改即可用于验证所求得的概率。
最终计算结果与程序模拟结果基本吻合,验证了我们计算的正确性。
在计算的时候,由于有些数据处理过于复杂我们用了近似算法,得到相对准确的值,但误差仍然不容忽视,使模型变得粗糙,这也是模型的不足之处。
6.2改进:
1、我们在这里假设一年364天,且每个月是不仅天数一样,而且所有费用情况和滞留情况也是一致的,但是每个月不仅天数不同而且周四的数目也有变化,所以具体的月滞期费应当根据当月情况进行调整,制定季度计划。
2、在求增补的天数和滞期费时我们用了很多近似假设,许多是很粗糙的,对结果的影响是比较大的。由于时间问题,我们没有进行深入的讨论。具体进行操作时可以求出相对准确的概率。
3、每天的列车不一定准时到达,而工人也不是随时可以调用的,实际操作时要充分考虑人事安排。
参考文献
1.马戈概率论与数理统计国防工业出版社
2.姜启源谢金星数学模型高等教育出版社
3.复旦大学数学系数学分析高等教育出版社
附录
程序代码:
Private Sub Command1_Click()
Dim i, x(5), t, g2, p, q, n, y(5, 2), y1, y2, z(7), mmm, op, oq As Integer
Dim money1, money2, m, money, nnn, bm As Double
Dim b As String
Dim c, d As String
Dim j, gzd, che As Integer
Dim k As Integer
money2 = 0#
money1 = 0#
m = 0#
t = 0
g2 = 0
gzd = Text7.Text
money = 0#
che = 0
mmm = 0
op = 0
nnn = 0
oq = 0
If Option4.Value = True Then
che = 4
Else
che = 3
End If
For i = 1 To 52
For k = 1 To 7
mmm = 0
op = 0
Randomize
'生成连续15小时到达时间
If k <> 4 Then '非周四
If Option1.Value = True Or Option3.Value = True Or Option4.Value = True Then x(1) = Rnd() * 900
x(2) = Rnd() * 900
x(3) = Rnd() * 900
x(4) = Rnd() * 900
End If
For p = 1 To (che - 1)
For q = p + 1 To che
If x(p) > x(q) Then
n = x(p)
x(p) = x(q)
x(q) = n
End If
Next q
Next p
If 1440 - t >= 360 Then '时间初始化
t = 0
money2 = money2 + 6# * 9000#
m = 1.5
Else
If t <= 1440 Then
money2 = money2 + (1440# - t) * 9000
m = m + (1440# - t) * 1.5 / 360
'm = 1.5
t = 0
Else
t = t - 1440
End If
End If
For n = 1 To che
If x(n) < t Then
If n = 1 Then
mmm = 1
End If
If mmm = 1 And n = 2 Then
op = 1
End If
If mmm = 1 And op = 1 And n = 3 Then
oq = oq + 1
nnn = nnn + t - x(n) + (1 - m) * 6 / (1.5 * (gzd + 1)) * 60
End If
g2 = g2 + gzd
money1 = money1 + (t - x(n)) * 15000 / 60 + (1 - m) * 6 / (1.5 * (gzd + 1)) * 15000
t = t + (1 - m) * 6 / (1.5 * (gzd + 1)) * 60
money2 = money2 + (1 - m) * 6 / (1.5 * (gzd + 1)) * (9000# + 12000# * gzd)
m = 0
t = t + 180
'剩余时间
Else
bm = m
m = m + (x(n) - t) * 1.5 / (60 * 6)
If m > 1.5 Then
money2 = money2 + (6 - 4 * bm) * 9000
m = 1.5
Else
money2 = money2 + (x(n) - t) * 9000 / 60
End If
If m >= 1 Then
t = x(n) + 180
m = m - 1
Else
If n = 1 Then
mmm = 1
End If
If mmm = 1 And n = 2 Then
op = 1
End If
If mmm = 1 And op = 1 And n = 3 Then
oq = oq + 1
nnn = nnn + (1 - m) * 6 / (1.5 * (gzd + 1)) * 60
End If
g2 = g2 + gzd
money1 = money1 + (1 - m) * 6 / (1.5 * (gzd + 1)) * 15000
t = t + (1 - m) * 6 / (1.5 * (gzd + 1)) * 60
money2 = money2 + (1 - m) * 6 / (1.5 * (gzd + 1)) * (9000# + 12000# * gzd)
m = 0
t = t + 180
'剩余时间
End If
End If
Next n
End If
If k = 4 Then '周四
If Option1.Value = True Or Option3.Value = True Or Option4.Value = True Then For j = 1 To che
y(j, 1) = Rnd() * 900
y(j, 2) = 0
Next j
End If
y(che + 1, 1) = Rnd() * 120 + 360
y(che + 1, 2) = 1
p = 0
q = 0
For p = 1 To che
For q = p + 1 To (che + 1)
If y(p, 1) > y(q, 1) Then
y1 = y(p, 1)
y(p, 1) = y(q, 1)
y(q, 1) = y1
y2 = y(p, 2)
y(p, 2) = y(q, 2)
y(q, 2) = y2
End If
Next q
Next p
If 1440 - t >= 360 Then '时间初始化
t = 0
money2 = money2 + 6# * 9000#
m = 1.5
Else
If t <= 1440 Then
money2 = money2 + (1440# - t) * 9000
m = m + (1440# - t) * 1.5 / 360
t = 0
Else
t = t - 1440
End If
End If
For p = 1 To che + 1
If y(p, 2) = 1 Then
q = p
End If
Next p
x(1) = y(1, 1)
x(2) = y(2, 1)