飞机排队模型 数学建模.ppt

MCM-89机场安排最佳队列调度。机场通常按照“先到先得”的原则分配跑道，即当飞机准备离开登机口时，飞行员呼叫地面控制中心加入等待跑道的队列。假设控制塔可以快速获得在线数据库中每架飞机的以下信息：1。离登机口的预定出发时间；2.从登机口出发的实际时间；3.船上乘客人数；4、计划在下一站换乘的人数和换乘时间；5.到达下一站的预定时间。还有七种飞机，乘客从100人增加到50人，载客量最多的是400人。试着开发和分析一个能同时满足乘客和航空公司的数学模型。(注：七种飞机可能属于不同的航空公司)。目前，各国机场普遍采用“先到先得”的排队系统。虽然该系统已经使用了很长时间，但其效率不高，不能适应事故的发生。在这里，我们将给出一个利用数据库系统的快速排队模型，使机场能够高效服务，使航空公司以尽可能少的成本达到顾客满意的目标。该模型的基本假设是，所有在机场起飞的飞机必须有相同的跑道，任何飞机起飞时都需要完全占据整个跑道，并且每架飞机占用的时间相同。这种假设可以将整个时间分成离散的等长小时间段(也称为起飞窗口宽度)，每个时间段可以容纳一架飞机来完成起飞操作。当第一架飞机从第J个时隙起飞时，它的费用只与飞机和时间位置有关，而与它前面的飞机无关。也就是说，成本不是前一架飞机的函数，因此这个假设可以将对应于不同订单的总成本统一描述为线性函数。假设任何飞机从自己的入口到达跑道入口所需的时间是相同的。与此同时，为了避免大量飞机拥挤在跑道入口等待飞机(一般机场不太可能出现这种情况)，如果另一架飞机在紧急情况下需要起飞，必须将前面的所有飞机推到一边腾出空间。因此，假设每架飞机都可以立即进入跑道入口。这样，当需要调整顺序时，只需要调整数据库中的顺序，而不需要重新排列字段中的平面。并且飞机必须被允许在指定的一小段时间内离开它自己的入口。模型设计和可行性分析，如果在时间t0只有一架飞机或没有飞机需要起飞，机场将直接安排其起飞或闲置。因此，在t0时刻，有N架飞机要求同时起飞。假设1，n架飞机起飞所需的总时间可以分成n个等长的小时间段(例如，长时间)。如何安排哪架飞机何时起飞取决于实际飞行成本和客户满意度。将Cij设置为第一个平面从第J个小时隙起飞所需的所有成本的总和，因此所有可能的排序的成本计算由以下成本矩阵表示：(1)，并设置Xij=0或1，当第I个平面在第J个时隙起飞时，Xij=1，否则Xij=0，因此计划矩阵相应地安排如下：第一个平面从第一行的第二个窗口起飞，第二行从第一个窗口起飞.最后一排最后起飞。根据上表的安排，已知(2)中的矩阵满足每行只有一个元素是1，即每个窗口只有一架飞机。阵列的每一列中的一个元素是1，即每架飞机占据n个窗口中的一个。也就是说，变量Xij必须满足约束条件：对于赋值问题，有一种专门为这种特殊结构设计的有效算法，称为GraverThrallprimal算法。对于一个随机产生的16个变量的指派问题，解最多可以在2.9秒内完成，而对于任何适当的变量指派问题，使用现代计算机，解可以在不到一秒的时间内得到。同时，因为模型中的成本系数矩阵(1)需要被量化，它们可以从下一段4中的公式中获得。从数据库中的数据计算出来，这个定量模型的过程还需要不到一秒的时间。因此，建立和求解整个模型所需的时间约为几秒钟，因此当机场控制塔面临一系列快速起飞请求时，它几乎可以立即响应排序。飞机的起飞间隔远不是几秒钟的数量级。一般至少几分钟，所以这个模型是可行的。更重要的是。如果发生事故，也可以使用机场的原始时刻表，数据库可以预先安排起飞顺序，让飞机安排起飞顺序。唯一需要重新安排的情况是飞机出现延误或紧急情况，此时的计算将在一秒钟内解决问题。此外，假设(3)不会由于变化而导致暂时拥塞。4.模型中成本系数矩阵的量化。因为(1)中的Cij是从第J个时隙起飞的第I个飞机的成本，它与航班的模型和运营成本、飞机上的乘客数量和他们的满意度相关。为了简化计算，基本运行成本被设置为成本零，并且仅考虑由飞机延迟起飞引起的成本。这一成本包括因延误而以更快或最快的速度飞行而不是以最经济的速度飞行所造成的燃油损失。以及由于下一站转机延误而重新安排行程的乘客的损失；以及由于各种延误造成的客户损失。这三项被归入成本计算，并简要记录为：成本：1。燃油附加费2。乘客误机的费用是3英镑。乘客未清偿损失。接下来，分别建立了几种成本计算公式。1.燃料附加费。由于延迟，飞机必须尽可能快地飞行，所以燃料随延迟时间的长短而变化。然而，即使它被延迟，只要它达到最大时间限制，它可以以低于最大安全速度的速度飞行。起飞后它能保持恒定的速度，所以油耗在时间上应该是恒定的。由于不知道燃油消耗如何随飞行速度变化，所以选择了一个近似的线性函数，即增加单位时间燃油消耗的成本函数为：根据这个公式，飞机延误的时间越长，它消耗的燃油就越多，直到飞机以最大速度起飞(假设4)。为了便于建模和讨论，下面将给出上述公式和将来使用的一些参数的汇总表。乘客错过航班的费用被设定为乘客必须补偿延迟转机的费用，在这里该费用被视为常数(假设为5)。如果每个人的补偿费用确实不同，它将被作为每个人费用的数学期望平均值，并且只有当飞机的延迟时间超过时间限制时，才进行重新安排的旅行，因此费用计算如下。3.失去不满意的乘客，飞机延误越多，乘客越不满意。如果飞机只晚点一两分钟，顾客不会太不愿意。然而，如果你到达晚了，错过了转接航班，乘客将立即变得焦虑和非常生气。这种情况可以适当地概括为在指数增长函数中增加一个阶跃函数，总成本函数为：但如果到达的飞机可以在准备着陆时就允许着陆，那么这个模型仍然适用，只要为了防止那些还没有准备好的飞机在准备好之前向它们发出起飞命令。飞机在预定起飞时间之前在某一窗口起飞的损失是无限的，如果考虑1、2和3中的费用，则得出计算费用的一般公式：4。排队模型概述：2)求解线性规划模型(分配模型)的最优解，可以确定哪个飞机在什么时候起飞；在正常操作条件下，上述总结中的步骤1)和2)只需执行一次即可逐步操作，并且只有在发生事故时才能启用零件3)。5.模型检查。最重要的模型检查是检查模型是否有意义。编制了用单纯形法求解线性规划的程序和几个简单的例子来检验模型的良好运行。在后面第6部分的具体结果中，可以看出所有的结果都与预期的直观判断一致。后来，进行了更彻底的检查。改变参数，测试更复杂的示例，甚至在实践中操作系统，如果实际操作结果显示航空公司在将客户满意度保持在可接受的水平的同时节省了费用，则该模型将是完全成功的。下面是改变参数的测试，即在参数受到干扰的情况下，模型是否稳定的测试。如果模型中的一个或几个参数稍微偏离真实值，并且模型结果没有偏离最优解太多，则可以认为模型是稳定的。此外，如果参数的微小变化导致模型的剧烈变化，则需要确定哪个参数更敏感。这样，更多的信息将被用于确定它，以达到准确性。在下文中，我们将指定模型(4)来表示运输模型：从运输模型的相关理论中，我们知道运输问题有一个可行的解决方案，并且对于这样的运输模型(9)，必须有一个最优值，并且该最优值的所有分量都是舍入的。还要注意约束条件(9)的限制，那么可能的整数解不能是0或1，所以运输问题等价于原始问题(4)。(9)由目标函数的向量形式表示(如(4)中所定义):6。计算机模拟模型。为了理解模型的良好操作和模型的特性，使用以下计算机模拟示例进行演示。显然。理论模型比计算机模型限制更少。为了简化编程和解释问题，在最初的基本假设中增加了以下具体假设：1.1。每个窗口最多有三架飞机准备起飞。当只有两个平面准备好时，可以添加一个虚拟变量，这样相应的成本系数为0。实际上，这些值应该通过实验室或调查获得：每个起飞窗口长一分钟，即任何飞机最多需要一分钟起飞，其他飞机不允许在一分钟内占据跑道；配备飞机着陆的情况；虚假转让赔偿费为每人350元；错过转接航班的乘客比那些延误15分钟的乘客愤怒两倍。例如1(具有使乘客最多的飞机先起飞的功能)，考虑到在早上6: 00，三架飞机同时要求起飞并建立它们的相同型号和距离该机场相同的终端机场(但是它们可以飞往不同城市的机场)。设置三架飞机为a、b、c。它们都被安排在7: 20到达目的地，但是飞机a有350名乘客。机上有100人；c飞机上有400人。此外，每架飞机上有100名乘客要求转机。计算结果如表1所示。当c飞机准备离开时，d飞机请求紧急起飞。D飞机已经晚了18分钟。如果它想在7: 06准时到达目的地，它必须在2分钟内起飞。机上有200名乘客，150人要求换机。表2显示了结果。例3(具有根据情况决定顺序的功能)假设再过两分钟后，D和A已经离开，而剩余的B已经延迟了三分钟，而另一个E请求此时起飞。设定E有以下条件：1)按时准备好；2)在准时到达终点线(7: 42)之前，还有42分钟空闲。(3)机上有122名乘客，其中89人要求转机；(4)滞纳金每分钟增加450元。例如，如果我们引入一个虚拟变量，平面x，这个平面的所有成本系数都是0。结果如下：从视觉上看谁应该先走并不明显。事实上，似乎乙应该先走。然而，由于高速飞行期间E的高