倒煤台问题1993B美赛 数学建模 西南财大培训 飞机装卸问题解答.doc

飞机装卸问题分析摘要本文研究了在飞机装卸与等待过程中有关费用最小化的问题。首先，在每天五点装卸台的初始状态为装满，当天工作不延迟到下一天的假设下建立了模型一。根据飞机到达时间服从均匀分布，得到各飞机等待时间的概率密度函数。分12种情况分别求出等待时间和工作时间的分段函数，并由此解得飞机的等待费用和工作组工作费用，其和即为总费用。机场工作方案为当还在对前一架飞机进行装货时，后一架已经到达，启用第二个工作组；前一飞机装满离开后，装卸台所剩货物已经不足装满一架飞机，而在继续向装卸台中装货时，后一架已经到达，启用第二个工作组；除此外用一个工作组。总费用为: 元。 而后，在模型一的基础上，考虑实际情况受前一天迟滞的影响，早上五点时装卸台不一定满，放宽当天工作不延迟到下一天的假设。且原方案中启用第二个工作组的时刻不能使总费用最低，因此建立计算机随机数模拟优化模型，寻找启用第二个工作组的最佳时刻，使总费用最低。利用计算机随机模拟，找出当装卸台需要单位货物才能装满，当天还有架飞机还未到达时，能使总费用最小，启用第二个工作组的时刻，即为机场工作方案。工作方案为同时有两架或三架飞机时，先到先装，装满才装下一架。在时刻，机场无飞机等待，装卸台需要单位货物才能装满，当天还有架飞机还未到达，有时刻，当 时用一组工人工作，当时用两组工人工作。具体数值见表3，总费用为9112.3万元。关键词 计算机模拟 优化问题 一、问题重述航空货运已是物流的一个重要组成部分。成都机场某公司经营机场某一货物装卸台，当货机到达时，货物通过装卸台吊装到飞机上。一架货机要用3小时装满，而装卸台的容量是一架半货机。每天，运输部门向这个装货设施发送三架货机，货机到达时间不确定。这些货机在上午5点到下午8点的任何时间内到达。如果一货机到达后因等待装货而停滞在那里（即处于等待服务状态）的话，机场要征收停机费15000元/小时架。一个装货工作组要用6个小时用装卸车把空的装卸台装满。这个工作组的费用是每小时9000元。可以调用第二个工作组及其装卸车来提高装货速度，而费用为每小时12000元，出于安全的原因，当往装卸台装货时，不能往货机上装货。每当由于往装卸台装货而中断往货机上装货时，就要征收停机费。如果你是公司的管理者，你将如何进行安排。注意：你们的分析至少应包括考虑以下的问题：1、建立合理的装货安排模型来选择最佳方案使费用少？ 2、必要的结果，比如：最佳方案，年预期开支（预期开支是指工作组的费用与停机费的总和）3、用计算机模拟的方法检验你对问题的分析和结果。二、模型假设1飞机需装满才能起飞。2. 增加一个工作组参与装卸能使装卸速度提高一倍。3. 飞机到达机场后直接进行装卸，不考虑维修，加油等时间。 三、符号说明 第一和第二架飞机到达的时间差； 第二架飞机的等待时间的密度函数； 第二和第三架飞机到达的时间差； 第三架飞机的等待时间的密度函数； 第二架飞机等待时间； 第三架飞机等待时间； 总费用； 工人的装卸费用； 飞机的等待费用； 机场无飞机等待的时刻，； 当天未到飞机数，； 装卸台的剩余容量，以每小时向飞机搬运的货物量为单位，； 使用一个工作组事件； 使用两个工作组事件； 使用一个工作组的概率； 使用两个工作组的概率； 从一个工作组转为用两个工作组的时刻，此时还有架飞机未到，装卸台还有单位货物未装满； 工人给装卸台装货的速度， 当天未到的架飞机均在后到达的概率； 当天未到的飞机中至少有一架在时刻之前到达的概率； 当天第一架飞机到达时刻； 当天第一架飞机到达时刻； 当天第一架飞机到达时刻； 前一天第三架飞机到达时刻；四、问题求解4.1 模型一建立与求解 4.1.1模型一建立（1）飞机装卸规则（方案）每天五点装卸台满货，每天独立；时间是连续的；当还在对前一架飞机进行装货时，后一架飞机已经到达，启用第二个工作组；证明如下：设在a机装机过程中b机到达，等待a机飞走的时间为，此时装卸台上的货物量为（用一个工作组一小时装飞机工作量为单位，）。则a机飞走后，用一个工作组装装卸台产生的装卸费和等待费用为： ， 1-（1）用两个工作组装装卸台产生的装卸费和等待费用为：1-（2）两式相减可得： ， 1-（3）在条件下，必有，即用两个工作组总费用更小。前一架飞机装满货离开后，装卸台所剩的货物已经不足装满一架飞机，后一架飞机已经到达，启用第二个工作组。（2）模型建立 设三架飞机到达的时间分别为， 则第一和第二架飞机到达的时间差为： ， 1-（4） 第二三架飞机达到的时间差为： ， 1-（5） 设为第二架飞机等待时间，为第三架飞机等待时间，且满足在间的独立的均匀分布。则第二架飞机的等待时间的密度函数为： ， 1-（6）其中为第一和第二架飞机到达的时间差，为第二架飞机的等待时间的密度函数。 第三架飞机的等待时间的密度函数为： ， 1-（7） 其中为第二和第三架飞机到达的时间差，为第三架飞机的等待时间的密度函数。 则可计算第二架飞机等待时间，现取其期望得： ， 1-（8）其中为第二架飞机等待时间，为第二架飞机的等待时间的密度函数。同理第三架飞机等待时间的期望为： ， 1-（9）其中为第三架飞机等待时间，为第三架飞机的等待时间的密度函数。由于假设每天五点装卸台初始量为满，因此第一架飞机的等待时间必定为0。总等待时间： ， 1-（10）4.1.2模型求解 （1）求解等待时间和费用现需求出第二架飞机等待时间以及第三架飞机等待时间的分布函数和期望，用MATLAB编程求解，算法如下，程序见附录1：Step 1：运用matlab中int函数求积分，求出第二架飞机等待时间的期望值；Step 2：将各值赋给a，输出矩阵a；Step 3：运用matlab中int函数求积分，求出第三架飞机等待时间的期望值；Step 4：将各值赋给b，输出矩阵b。其分段函数和每段概率表示如下表（表1）：表1 飞机等待时间表条件1第二驾飞机等待的时间第一架飞机等待时间的期望条件2第三架飞机的滞期时间第二架飞机等待时间的期望000000且000000而总的滞期时间为： 1-（11）（2）求解工作费用各组的工作时间表达式见下表（表2）：表2 工作时间表条件1第二架飞机开始装货前只用第一工作组工作的时间第二架飞机开始装货前两组工作组工作的时间条件2第二架飞机离开后第三架飞机开始装货前只用第一工作组工作的时间第二架飞机离开后第三架飞机开始装货前两组工作组工作的时间010240024000且0400120而工作费用为： 1-（12）利用MATLAB编程，算法如下，程序见附录2Step1: 分别用matlab中int函数求积分求出一个装卸工作组工作时间，两个装卸工作组工作时间；Step2: 分别求和再乘以各自工作组的工作费用求得一天费用总和。得： 1-（13）综上求得机场工作方案为：当还在对前一架飞机进行装货时，后一架飞机已经到达，启用第二个工作组；前一架飞机装满货物离开后，装卸台所剩的货物已经不足装满架飞机，而在继续向装卸台中装货时，后一架飞机已经到达，启用第二个工作组。4.2模型二建立4.1.1 模型一局限 上述模型一有以下局限：（1） 每天早上5点装卸台已满的假设不合理；（2） 没有考虑第一天的飞机装卸工作延迟到第二天，对第二天工作的影响；（3） 飞机到达后开始转为用第二个工作组并不能保证这样能使装卸费用和飞机等待费用最小；故在模型一的基础上优化建立模型二，找出由一个工作组转为两个工作组时刻。4.1.2 模型二建立思路 模型目标是设计机场工作方案使得飞机装卸费用和等待费用最小。为保证费用最小，需找出由一个工作组转为两个工作组的时刻。因飞机的到达时间机场工作人员不可预测，不能将其作为安排工作的条件，故选用装卸台剩余容量和每天飞机未到架数作为自变量。对此建立转换时刻和这两个变量的函数关系，列出费用表达式。用计算机模拟找出费用最小的方案，即为最佳方案。4.1.3 模型二（1）目标函数 目标是使得总花费最小。总花费分为飞机等待费用和装卸费用，故有： ， 2-（1）其中表示总费用，表示工人的钱装卸费用，表示飞机的等待费用。 （2）飞机装卸规则对任意一架飞机，在其装机过程中有其余飞机到达，在该机飞走后，用两个工作组装装卸台。同时有两架或三架飞机时，先到先装，装满才装下一架。在时刻，机场无飞机等待，装卸台需要单位（以每小时向飞机搬运的货物量为单位，）货物才能装满，当天还有架飞机还未到达，他们到达的时刻相互独立地服从的均匀分布。则存在时刻，方案要求在时用一组工人，时用两组工人。 证明如下：设用一个工作组为事件，用两个工作组为事件，表示用一个工作组的概率，表示用两个工作组的概率。无飞机在机场等待且装卸台不满时，有： ， 2-（2）其中表示机场无飞机等待的时刻，表示装卸台的剩余容量（以每小时向飞机搬运的货物量为单位，），表示用一个工作组的概率，表示用两个工作组的概率。定义存在时刻，使得：， 2-（3）在，给定时，是关于的增函数，是关于的减函数，即随时时间的推移，为了使当天的任务尽量完成，使用两个工作组的概率增大，使用一个组的概率减小。则方案要求在时用一组工人，时用两组工人最优。每天未到飞机数随着时间增加是减少的，故易得： ， 2-（4）（3）缩小搜索范围现缩小的范围。在时刻机场无飞机等待，且装卸台有单位货物待装。定义工人给装卸台装货的速度为单位/小时，以一个工作组每小时向飞机搬运的货物量为单位，即飞机的容量为3单位，装卸台的容量为4.5单位，则： ， 2-（5）定义事件为当天未到的架飞机均在，即时刻之后到达，事件为未到的飞机中至少有一架在，即时刻之前到达。对于事件，一个工作组就可在时刻装满工作台，不增加飞机的等待时间，为使费用最少，所以。这时用一个工作组工作，有： ， 2-（6）对于事件，飞机最晚到达的时刻恰好能够满足两个工作组将装卸台填满，故时刻开始两个工作组一起工作，使最早到达的那架飞机等待时间最短，则费用最少，所以。这时用两个工作组工作, 有：， 2-（7）故有：， 2-（8）其中表示机场中无飞机等待的时刻，表示当天未到的架飞机均在后到达的概率，表示用一个工作组的概率，表示未到的飞机中至少有一架在时刻之前到达的概率。对于，当时，因每天的飞机必会在晚上8点前到达机场，故为0；时，因飞机到达时刻满足的均匀分布，故可由时间长之比求得。所以有：， 2-（9） 其中表示机场中无飞机等待的时刻，表示当天未到的架飞机均在后到达的概率，表示装卸台的剩余容量（以每小时向飞机搬运的货物量为单位），表示当天未到飞机数，。对于，当时，即，此时飞机是在时刻之前到达，不满足假设，故为0；当时，即，因飞机到达时刻满足的均匀分布，故可由时间长之比求得。所以有： ， 2-（10） 其中表示机场中无飞机等待的时刻，表示当天未到的架飞机均在后到达的概率，表示装卸台的剩余容量（以每小时向飞机搬运的货物量为单位），表示当天未到飞机数，。 设：满足， 2-（11）满足， 2-（12） 则有，分别为的上下限，即：， 2-（13） 其中 表示将一个工作组换成两个工作组的时刻。综上，对于任意给定的，都可通过上述（9），（10），（11），（12），（13）公式解得 的范围，即缩小范围模型为： 2-（14）（4）费用公式 总费用分为飞机等待费用和工人装卸费用。即： ， 2-（15） 其中表示总费用，表示工人的装卸费用，表示飞机的等待费用。 对于工人的装卸费用，因飞机的装卸工作有延迟到第二天完成的可能，故工人需时刻尽量使装卸台装满以减少未到飞机的等待时间。由以上可知机场安排工作组的决策按照，进行，在之前使用一个工作组工作，在之后使用两个工作组工作。设分别为当天第一架飞机，第二架飞机，第三架飞机到达机场的时间，为前一天第三架飞机到达时刻。故有： ， 2-（16） 其中为一个工作组换位两个工作组的时刻。 对于飞机等待费用，当装卸台上货物量能满足一架飞机所需的货物时，飞机无等待费用，当无法满足时，飞机产生等待费用，等待时间为工作组将装卸台装至能满足飞机需要的时间。故有：， 2-（17）其中分别为当天第一架飞机，第二架飞机，第三架飞机到达机场的时间，为装卸台剩余容量，为一个工作组换位两个工作组的时刻。（5）总模型综上所述，建立计算机模拟优化模型。模型如下：给定一离散的，；由缩小范围模型找出的范围；用计算机模拟不同的时间点，最小化总费用，分别找出三种未到飞机数费用最少的三个时刻，；重复上述13步骤，找出对于每个和对应的费用最小的点；则所有的即为机场的决策函数。4.1.4 模型二求解利用MATLAB软件编程求解，算法如下，程序见附录3：Step1：定义装卸台剩余容量，因为装卸台最大容量为4.5，属于0到4.5之间；Step2：初始值定为0.1，每次循环加上0.1；Step3：分别定义、为还有三架飞机、两架飞机、一架飞机未到达时，启用第二个工作组的时间点，、与相关；Step4：将、分别以1为步长在时间5到20之间循环；Step5: 用计算机随机生成三架飞机到达时间x、y、z；Step6：根据启动第二组时间、以及飞机到达时间x、y、z可以求出一天内飞机的等待费与货物装卸费之和Step7：找到每天最小费用，记录下此；时的以及与之对应的、Step8：加上0.1，再重复Step3Step7；Step9：求出最小费用的平均值，乘以一年的天数得到一年的费用模拟值。结果为见下表（表3）：表3 模型二方案表Q0.10.20.30.40.50.60.70.80.911.11.21.31.41.5t(Q,3)121591310118910101311989t(Q,2)161512141114121214141314131215t(Q,1)201820191718181918181816181818Q1.61.71.81.922.12.22.32.42.52.62.72.82.93t(Q,3)58138106689897887t(Q,2)13121314101013111412101391010t(Q,1)161617171716171816151716171414Q3.13.23.33.43.53.63.73.83.944.14.24.34.44.5t(Q,3)677855867866766t(Q,2)111011129696811896710t(Q,1)161614151413161114131513141414机场根据装卸台剩余容量，和未到飞机数，选择符合此时条件的时刻将一个工作组变为两个工作组工作。 用计算机模拟得到总费用为9112.3万元 。五、模型评价5.1 模型优点（1）本文先从简单的角度着手建立模型，然后放宽限制条件建立更严密的模型。过程严谨，理论性强，逻辑严密，而且易于理解。（2）本文大量运用了计算机程序，所有数据均由计算机处理，故误差由计算机精度产生，模型据有良好的稳定性。5.2 模型不足 没有从理论上证明模型的最优性，同时要得到更好的结果，计算量较大。六、参考文献1 韩中庚，数学建模方法及其应用M，北京：高等教育出版社，20052 韩中庚，数学建模竞赛获奖论文精选与点评，北京：科学出版社，20073 姜启源，数学模型（第二版），北京：高等教育出版社，19924 韩中庚，数学建模方法及其应用，北京：高等教育出版社，2005.65 谢金星，优化建模与LINDO/LINGO软件，北京：清华大学出版社，2005.76 李尚任，数学建模竞赛教程，南京：江苏教育出版社，1996.06七、附录7.1模型一等待时间MATLAB程序syms t;a(1)=int(1/15*(4-t),0,3);a(2)=int(1/15*(5-t)/2,3,5);a(3)=int(1/15*0*t,5,7);a(4)=int(1/15*0*t,7,15);asyms x y;b(1)=int(int(9-x-y)/112.5,y,0,7-x),x,0,3);b(2)=int(int(11-x-y)/2/112.5,y,7-x,11-x),x,0,3);b(3)=int(int(15-x-2*y)/2/112.5,y,0,5.5-x/2),x,3,5);b(4)=int(int(19-x-2*y)/4/112.5,y,(11-x)/2,(19-x)/2),x,3,5);b(5)=int(int(15-x-2*y)/2/112.5,y,0,3),x,5,7);b(6)=int(int(12+x+y)/2/112.5,y,3,12-x),x,5,7);b(7)=int(int(4-y)/112.5,y,0,3),x,7,15);b(8)=int(int(5-y)/2/112.5,y,3,5),x,7,15);b 7.2模型一工作费用MATLAB程序clearclcsyms t;a1(1)=int(1/15*0*t,0,3);a1(2)=int(1/15*(t-3),3,5);a1(3)=int(1/15*(t-3),5,7);a1(4)=int(4/15+0*t,7,15);a1; a2(1)=int(1/15*t,0,3);a2(2)=int(1/15*(5-t)/2,3,5);a2(3)=int(1/15*0*t,5,7);a2(4)=int(1/15*0*t,7,15);a2; syms x y;b1(1)=int(int(0*x*y,y,0,7-x),x,0,3);b1(2)=int(int(x+y-7)/112.5,y,7-x,11-x),x,0,3);b1(3)=int(int(4/112.5+0*x*y,y,11-x,15),x,0,3);b1(4)=int(int(0*x*y,y,0,5.5-x/2),x,3,5);b1(5)=int(int(2*y+x-11)/2/112.5,y,(11-x)/2,(19-x)/2),x,3,5);b1(6)=int(int(4/112.5+0*x*y,y,(19-x)/2,15),x,3,5);b1(7)=int(int(0*x*y,y,0,3),x,5,7);b1(8)=int(int(y-3)/112.5+0*x,y,3,12-x),x,5,7);b1(9)=int(int(5-x)/112.5+0*y,y,0,12-x),x,5,7);b1(10)=int(int(0*x*y,y,0,3),x,7,15);b1(11)=int(int(y-3)/112.5+0*x,y,3,5),x,7,15);b1(12)=int(int(2/112.5+0*x*y,y,5,15),x,7,15);b1; b2(1)=int(int(2/112.5+0*x*y,y,0,7-x),x,0,3);b2(2)=int(int(11-x-y)/2/112.5,y,7-x,11-x),x,0,3);b2(3)=int(int(0*x*y,y,11-x,15),x,0,3);b2(4)=int(int(2/112.5+0*x*y,y,0,5.5-x/2),x,3,5);b2(5)=int(int(19-x-2*y)/4/112.5,y,(11-x)/2,(19-x)/2),x,3,5);b2(6)=int(int(0*x*y,y,(19-x)/2,15),x,3,5);b2(7)=int(int(9-x)/2/112.5+0*y,y,0,3),x,5,7);b2(8)=int(int(12-x-y)/2/112.5,y,3,12-x),x,5,7);b2(9)=int(int(0*x*y,y,0,12-x),x,5,7);b2(10)=int(int(1/112.5+0*x*y,y,0,3),x,7,15);b2(11)=int(int(5-y)/2/112.5+0*x,y,3,5),x,7,15);b2(12)=int(int(0*x*y,y,5,15),x,7,1