《飞机排队问题》由会员分享，可在线阅读，更多相关《飞机排队问题（11页珍藏版）》请在金锄头文库上搜索。
1、问题一飞机排队问题问题机场通常都有用“先来后到”的原则分配飞机跑道.即当飞机准备离开登机口 时，驾驶员电告地面控制中心，加入等候跑道的行列.假设控制塔可以从快速反应 数据库中得到每架飞机的如下信息：1）预定离开登机口的时间；2）实际离开登机口的时间；3）机上乘客人数；4）预定在下一站转机的人数和转机时间；5）到达下一站的预定时间.又设共有7种飞机，载客量从100人起以50人递增，最大的飞机载客量为400人. 这7种飞机可能分属不同的航空公司.试开发和建立一种能使乘客和航空公司双方都满意的数学模型，以安排飞机 起飞的先后次序.（2）假设1）机场控制塔上有一个快速反应的数据库，该库中存贮着每一架飞
2、机的正点起飞 时间，正点抵达目的地的时间，乘客数量，飞行距离等信息,其他一些有用的参数，可 以根据数据库中已有数据估计出来.2）所有飞机都在同一专用跑道上起飞，任何一种飞机在跑道上起飞所需要的时间 相同，这样可以把时间划分成间隔为的起飞时段.3）标号为i的飞机在第j个时段起飞所需费用与先前起飞的飞机无关，仅与其安排 的次序有关.这一假设使我们可以把总费用作为飞机调度排序的线性函数.4）所有飞机从登机口到跑道起点的时间相同.5）记t为使飞机尚能正点到达目的地所推迟起飞的最长时间.同时假定，当飞机的 误点时间超过t时,则飞机将以最大的安全速度飞行.6）如果飞机推迟起飞的时间超过t ,则机上所有下站
3、转机的乘客都将耽误转机.7）因误点而要求改航的赔偿费对每一个乘客都是相同的.（3）记号及意义： 飞机起飞的时间间隔；0最早起飞的飞机离港时间；d :正点起飞的时间；ta:正点到达目的地的时间；t:晚点时间；T：最大允许晚点起飞的时间；k:各种类型的飞机因晚点起飞而引起耗油的费用常数；仲:平均飞行速度；y max :最大的安全飞行速度；r:要求改航的乘客的赔偿费；n :下站转机的乘客数；P:乘客总数；:由于晚点起飞所引起的乘客不满意程度的增长率；a:全体乘客由于飞机晚点起飞所引起的不满意度折合成美元的折合率； b:耽误转机的乘客不满意度折合成美元的折合率.分析与建模若有n架飞机都要求在时刻正点起
4、飞，并且认为所有飞机都有直通跑道.我 们以总费用最小作为目标来安排飞机起飞的次序.总费用由两部分组成，即航空公 司的费用和乘客不满意程度所折合的费用.设为标号i的飞机在第j个起飞时段起飞的费用，引入状态变量X，其定义 为=J1,当标号为i的飞机第j个起飞七=|0,其它则总费用为一 n nZ = ZZ exi=1 j=1为了保证每一架飞机只安排在一个时段内起飞及每一个时段内只有一架飞机 起飞，因此对状态变量xij增加约束条件：z x = 1, i = 1,2,., nx = 1, j = 1,2,.,nij=1由假设条件可知，七与*.无关，因而总费用C是一个线性函数.这是一个指派问题.假定每隔时
5、间只有一架飞机离开登机口加入到请求起 飞的行列中，这样就保证总有飞机请求起飞.每隔时间，执行一次程序，以安排在 当前状态下最优的起飞次序.这里需要说明一点，该程序运行时间极短，不到一分 钟便可完成，因此，如果数据发生变化时,如飞机晚点进港等，几乎可以立即决策.下面来分析费用系数的确定问题.总费用应包括航空公司的费用和乘客的不满意度所折合的费用.首先把基本 费用视为0,即设飞机在正点起飞时的费用为0,仅考虑由于飞机晚点起飞所导致 的额外费用.航空公司的费用主要由两部分组成.一部分为额外的汽油费，这个费用主要是 由于飞机晚点起飞时，要在空中快速飞行所额外消耗的汽油费;另一部分为耽误了 转机的乘客需
6、要改航时的赔偿费.若飞机晚点起飞，为了正点抵达目的地,它必须 在空中以更快的速度飞行,这样由于风阻力的增大和其它因素，就要增加汽油的消 耗.我们不太清楚速度的增加如何引起耗油费和增加，但当飞机加速过程结束,在空中 以最大安全速度飞行时,额外的耗油费将是一个常数.为简单起见，选用线性函数 来表示额外的油耗费，其公式为:kt,t T其中J为飞机晚点起飞的时间，显然当飞机正点起飞时J=0,若to为首架起飞的时 刻，？为正点起飞的时刻,为起飞的时间间隔，则第j个起飞的飞机晚点起飞的 时间为:t = t + (j - 1)A-10d由于T为最长的晚点起飞时间，即当晚点起飞的时间超过T以后，即使在空中以最
7、 大速度飞行，也不能正点抵达目的地，因此edVmaxT = T tA d其中t A为正点抵达目的地的时刻,d为飞行距离，y max为最大的安全飞行速 度.d可用公式来表示d =匕其中七为正点起飞时刻，Vav为正点起飞时平均飞行速度.常数k与油价、单位晚点时间油耗的增加率及最大安全飞行速度有关，同时 还应与飞行距离有关，当然飞行距离越长，额外的油耗就越大.由于飞行距离为Ta - td -T ,乘以最大安全飞行速度,则有:F(t)=,(厂尸*,tA d下面再计算改航旅客的赔偿费.为简单起见，由假设条件，记每一个改航旅客 的赔偿费用为一个常数r(若赔偿不同，则令r为赔偿的期望值).由于当飞机晚点起
8、飞时，所有下站转机的乘客都将改航,则改航的赔偿费为：R(t) = rnu(t-t )n为转机旅客总数,u(t)为单位阶梯函数，即0, S 0 u (s)= 0费用系数中还应考虑乘客的不满意程度.一般地,飞机晚点起飞的时间越长， 旅客就越抱怨，其不满意程度就越大.如果晚点时间只有12分钟,旅客就不会太 不满意.但是，随着晚点时间的增加，旅客会非常生气，而不满意度会急骤增加，因此 我们选用指数函数描述旅客的不满意程度.这个不满意程度对机上每一旅客都是 如此，但对下站要转机的乘客,还需要追加另外的不满意度，用D(t)表示总的不满 意程度所折合的费用，则D(t) = ap(eB -1) + bnu(t
9、 -t )p为机上乘客总数,n为下站转机的乘客总数,为了保证在正点起飞时乘客的不满 意度为0,因而采用了(欲-1)的形式，显然t=0时,D(0)=0. a为乘客不满意度的增长率,a,b为折合率，ap（伽 T）代表全体乘客不满意度折合的费用，b兀（）为下站转机乘客追加的不满意度所折合的费用,这一项只有当t t才起作用.综上所述，费用系数 .应为额外油耗费、赔偿费、及不满意度所折合的费用之和c = F（t）+R（t）+D（t）jgt tcij ,d “ ，=k(T t t )t + ap(et 1),t tA dt和T由下式给出0 dtmaxt = t -1 + (j -1)A2）计算实例为了执行
10、简单，再作一些假设。1）至多有三架飞机等候飞行（即nW3），如果不足三架，在模型中增加一架或两架虚拟的飞机，虚拟的飞机的费用系数视为0。2）任何飞机起飞时间至多1分钟，即=1，其间，其它飞机不能占用跑道。3）跑道上没有飞机降落；4）每一个改航旅客的赔偿费用为350美元；5）一个要改航乘客的不满意度是误点15分钟的乘客的2倍乘客多的飞机先起飞例有A,B,C三架飞机都已离开了登机口，要求在上午6点钟正点起飞，这三架 飞机将飞往三个不同城市，但空中飞行距离都相同，正点抵达目的地的时间均为上 午7点20分.另外，其乘客数量分别为350,100,400,且每架飞机上都有100名乘 客将在下一站转机.执行
11、结果为:标号乘客数/转机乘客数费用系数解A350/10000.480.97010B100/10000.410.83001C400/10000.51100其最小费用为1.31,起飞的次序为C,A,B.这一结果与我们的直觉完全一致，即在 其它条件相同的情况下，乘客数量多的飞机优先起飞.误点时间最长的飞机优先起飞接着上面问题，飞机C正在起飞的同时，飞机D已经离开了登机口请求起飞.已知 飞机D载有200名乘客，其中150名将在下站转机，这架飞机已经晚点18分钟， 要使飞机D正点抵达目的地,必须在2分钟内起飞（即必须在6点02分或6点03 分两个起飞时段内起飞）.执行结果如下表.标号乘客数/转机乘客 数
12、已晚点时间（min）费用系数解D200/150180.280.911100B100/10010.070.150.22001A350/10010.090.170.26010这个例子中的总费用为1.22，最优的起飞次序为D,A,B.这一结果与直觉相符，即 晚点时间最长的飞机优先起飞.优先权相差不明显的情形当系统时钟指向6点03分，此时C,D,A三架飞机已先后起飞，飞机B已晚点 3分钟，而又有一架飞机E离开登机口，请求起飞.对飞机E,我们知道如下信息:总 乘客数不122名，其中89名乘客在下站转机，晚点1分钟的费用为450美元;最长 的晚点时间为45分钟.在求解时,须增加一架虚拟飞机X,对应于飞机X
13、的所有参数为0.结果如下:标号乘客数/转机乘客 数已晚点时间（min）费用系数解B100/10030.60.81010E122/89000.280.56100X0/00000000从上表可以看到，总费用之差0.88-0.8=0.08,这个数目不太大，因而究竟哪架飞机应该先起飞不甚明显.事实上，由于飞机E有较多的富裕时间，因而应先安排飞机B 起飞.但是，由于飞机E在飞行时费用较大，以及有更多的乘客，因而飞机E应先起 飞，这与模型的结果一致.问题二生产计划铸铁厂要生产一种规格的铸件共10 t.其成分要求为：锰含量至少达到 0.45%,硅含量允许在3.25%5.5%，市场有充分的锰和三种不同型号的生
14、铁可 供作铸件的炉料使用，它们价格是锰每千克75元，A种生铁每吨1700元，B 种生铁每吨1900元，C种生铁每吨1400元.三种生铁含锰和硅的成分百分比() 如表所示ABC锰0.40.50.35硅410.5若不计冶炼铸造过程中的损耗，问工厂怎样选择炉料能使成本最低？解：建立模型设用A种生铁x 1吨，用B种生铁% 2吨，用C种生铁x 3吨，用锰% 4 吨，且由题知每千克锰75元，则每吨锰要75000元，z为最低成本，于是有关 系式：z = 1700气 +1900x 2 +1400% + 75000七我们称其为目标函数，生产条件可以表示为：0.0004尤 + 0.0005x + 0.00035x + 0.1x 0.00450.004x + 0.001x + 0.0005x 0.03250.004x1 + 0.001 x2 + 0.0005x3 0I123, 4此问题是一个优化问题，解决此问题的过程就是优化的建模过程。然后求出X 1 , X 2 , X 3， 4，使得生产成本最小。下面是
