建模需要思想，也需要数学训练和手上功夫—B题综合评述

第19卷建模专辑工程数学学报．19spp加。月JOURNALOFENGINEERINGMATHEMATICSFeb2002文章编号：1005—3085(2002)05—0107—06建模需要思想，也需要数学训练和手上功夫——B题综合评述刘宝光(北京理工大学．北京100081)摘要：本文对于2OO1年全国太学生教学建横竞赛B题的解答，从模型框架、模型建立和模型求解等三千方面鲭出评述。美键词：公交车调度；敦学规划模型；目标规划分粪号：AMS(2000)90C08中舶分类号：Tbl141文献标识码：A1模型框架正如题目的标题所示，这是一个“公交车调度问题”。题目给定了限制条件和目标，要求在一定统计数据资料的基础上，构建理论模型并据以实现调度。应当指出，构建“明确、完整的数学模型”，是本题懈案要求的一个本质性的方面。事实上，每一天，在全国各地，都有无数的车队调度在作这类问题。他们遵守各自的约束，追求各自的目标，用他们习惯了的方法调度车辆，指挥着全国各地公交车的运行。他们不见得都有多高深的数学修养，所给出的调度 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 也不见得都是合理的优良的。本题的意义，并非要参赛者习作普通的车队调度，而是要求对这一问题用数学方法作更深一层次的探讨。这次有占相当比例的答卷没有完成明确、完整的模型的建立，只从数据出发，凭某种直观方法给出一个可行的调度方案。应当说这是不符合题目要求的，因而都不在得奖者之列。考察题意最直接的想法会是建立数学规划模型。在培出了数学模型的答卷中，恐怕有七成以上是用的各种不同的数学规划模型。模型的变量，既然题目要求设计调度方案，最自然的就是发车时刻系列T1，T2，⋯，但这一变量，其维数m很高，而且是不定的。这会为使用某些成熟的优化数值方法求解带来麻烦。一种适当的简化方法是将全天分作若干时段，在每一类时段中等间距发车。这时，模型的变量可取作各类时段的发车时问间距，从而可建立有确定的低维数的数学规划模型。例如，将全天分为平峰时段和高峰时段，分别间距f1和t2分钟发一班车，则可得到以(，f2)为变量的2维模型。题目称调度方案应满足四项要求。若记i为乘客候车时间，；为早高峰时乘客候车时间，为车辆载客人数，则要求为(a)≤1O分钟；(b)；≤5分钟；(c)≥50；(d)P≤120。维普资讯http://www.cqvip.com108工程教学学报第19卷按照题目所列的乘车人数统计数据，严格满足这四项要求的调度方案是不存在的。而题目只是限定()为硬性约束，不应违反。其他三条使用“一般不要”措词，即是说可以违反，但应使违反程度尽可能低。这很自然导向使用目标规划(goalprogramming)~，而且粗看起来，如下模型是合理的，rain(，，)(1)￡．f～5≤10(2)r～≤5(3)p+≥50(4)≤120(5)1≥z(6)n，t2，s，，s≥0(7)然而，由于约束(2)和(3)要对每个乘客成立，约束(4)和(5)要对每辆车每个路段(指相邻二车站间的道路区段)成立，这一模型只有观赏意义，是难以处理的。将和r换作所有乘客的最大候车时间。换作各车各路段的最小载客数，便真的是作成了三个约束。但此时、f和作为(1，2)的函数难以给出表达。不仅如此，因为和r是以分钟为单位的等候时间数，是车上的人数，二者是不可比较的，所以会给权因子的设置带来困难。这样的模型在答卷中有，为数极少。如上述，这一模型实际上是不能操作的。必须另外想变通的方法。一种作法是计算两种时段中超时候车(>10，r>5)的乘客数在各段乘客总数中所占的百分比(作为(￡l，t2)的函数)，计算载客人数p<5O的车路段数在全部车路段数中所占的百分比，即gl(f2)=豢，：(tl,t2=题镰，并要求其取最小。这样直接导致多目标规划问题rain(gl，g2，g)s．t．≤120l≥2≥0(8)(9)(10)三个百分率函数gI，g2，毋的引A，既将涉及各个乘客和单个车路段的要求目标整合为一种集总的表述，又将三个函数的数量统一为无单位的百分率，使之有良好的可比性，易于用加权和形式化为单目标问题，从而使问题(8)一(10)成为一实际可操作的模型。这次评定得奖的答卷，很大一部分都采用了各种不同的集总表示。如不少答卷定义了各种不同的乘客满意度指标和公交公司满意程度指标，也有的用总等待时间和总发车数，平均等待时间和平均载客量等。这些集总表示各有长短，所导致的调度方案也各不相同，但只要想法台理．表述和计算正确，都是合理的解答。但是有的答卷，设想了公交公司利益和乘客利益的一些不同的方面，作为要优化的目标函数，而将(a)一(d)四项要求作为约束条件，因无可行性，便放开某一条或某几条，仍将其余的作为硬性约束。更有个别答卷将(a)一(c)三条作为硬性约条处理，而完全放开表现载客数上限的条目(d)。这样做实际上已经改变了原来的题目。就维普资讯http://www.cqvip.com堡堡童量建模需要思想，也需要数学训练和手上功夫lO9题目文字所表现的意义，公交公司利益和乘客利益的体现就是(a)一(d)这四项要求。除了数学规划模型之外，部分答卷建立了排队论模型，有的用了计算机模拟。这样的答卷也有成绩很好的。2模型建立上段谈及的模型，只是给出了一个框架，如(8)一(10)。要完成模型建立，还需利用统计数据，将gl，g2，g3和p等各个函数的表达方法建立起来。记早高峰时段为[t1，t2]，晚高峰时段为[t3，t4]。我们假设由发车间隔￡1，2所确定的全天共m班车的发车时刻序列为T】jT2，⋯，这些L值在各高峰和平峰时段内是均匀等间距的，在跨越，=1，2，3。4时的确定L值的 规则 编码规则下载淘宝规则下载天猫规则下载麻将竞赛规则pdf麻将竞赛规则pdf ，要作一些补充规定。比如，设t左侧相邻的L值为．，则可规定frr1．+￡2当t1一T1≤f2“lt】，当t1一T>￡2t2左侧相邻T值为Tf．，则规定T¨1=L，+1，等等。或按其他规则，此处不赘述。设以=1，2，⋯，”标记车站。从J一1站到J站的站问行车时间(包括J站的停车时间)记为，J=2，3，⋯，n。第班车驶离站的时刻记作T，则有i：1+∑J=2，3，⋯，”～1(12)=2这便给出了每一班车的行车时刻表。为了求g(，2)和p(‘，2)，需要计算每～班车驶离各站时车上的乘客数(，)，=1，2，⋯，m，J：1，2，⋯，一1。而为了计算g1(1，2)和g2(￡l，2)，需要计算每个乘客的候车时间。这些都要从乘客流的统计数据出发。首先对每一车站J引人乘客来站的时间密度，即单位时间来站乘客数，记以函数“，()，J=1，2，⋯，”一1。统计数据恰好给出每隔60分钟一个点上的平均密度值。据此或用插值或用拟台，总可以得出“。(f)的一个近似表示。这里最简单的是用阶梯函数；作分段线性插值得一折线函数也很简单好用。答卷上对此一细节的处理花样繁多，有的甚至作了长篇幅的讨论。其实，这在整个解案中不过是一个细节，下功夫过大则势必舍本逐末。类似可建立乘客离站的时间密度函数．(c)，f=2，3，⋯，”。虽说乘客来站是分散的，离站是成批的，但统计数据中并未反映这一区别，因而在计算中也就作完全一样的处理。乘客等候时间的计算较为曲折。这里使用将乘客按等候时间长短分类统计的方法。为此，设第^班车到达站时，站上已等候过h辆车而仍未能上车的乘客数为，(^)。以下将(，)和(，=1，2，⋯，一1，k=1，2，⋯，m，用对k和二重递推的方式表述出来。注意对任意的^，，当^=0，因为j=(0)为时间段[(0)=J“)出‘‘·1其中的TD1理解作题目所讨论的全天的开始时间，即To，=To：5×60，j=1，2，。一，l，]的来客数，所以有(13)(14)维普资讯http://www.cqvip.com110工程数学学报第19卷对于k=1，根据(13)式，对任意的J，l，(0)为已知。以下证明：对于任意k，若对任意^≤k一1．任意J，(h)为已知，则可以导出()，，=1，2，⋯，n一1和+1，(h)，=1，2，⋯，n一1，h≤k。我们假设乘客按先到先上车的队列原则乘车。记h．为站上等待最久的乘客的候车趟数，即h=maxIhl(^)>0}我们规定0=0，(L0)=Oo依次对于，=1，2，⋯，一1，记n目=maxI(—1)一l吐(t)dt，0；(15)』^一l即第k班车到达j站，乘客下车后，车上仍留下的乘客数。这里的仍如(14)式。此时，可容纳的乘客上车数上界=120一。(16)这时有^()=min{120，n+∑w~j(h)}(17)^=0．h^+lJ=max{hlh=0或使∑wkj(r)>l(18)(18)式的意思是按候车趟数从多到少依次累加，(hkj)+(一1)+⋯直到苜次出现大于6“则停止累加，以累加到的最后的(最小的)一个h作为+l；如果直加至目(0)仍不大于，则h^+l=Oo然后，若h^+lJ=0，则“l(1)=0；否则∞--h+1)(^)=∞(^一1)，h=1，2，⋯，^+lj一1(19)．十1)()=H(^一1)一％一∑(^)(20)‘～+1，，(0)则如(13)式。现在可以建立模型(8)一(10)中的各个函数了。利用P()，有∑{1l()>50}g3(tl，t2)=且—厂(2)注意P(L，)的构造过程已保证了约束条件(9)式的成立，因而无须再求函数(￡1，2)，该约束在建成的模型中也不再出现。为求gl和g2，注意到至，时刻，，站上已候^辆车而仍未能上车的乘客的等候时间满足一L一≤f或≤一L一^一Ij以保守的原则取其下限，则有∑{，(^)l，一L一>5，^=1，2．⋯．(22)(23)维普资讯http://www.cqvip.com建模专辑建模需要思想，也需要数学训练和手上功夫三个函数都是百分率，数值上有良好的可比性，可以简单地取其加权和作为单一目标函数。题目中没有关于优先权及权重的规定，可以认为公交公司利益与乘客利益等权，并且表现乘客利益的二函数g。和g2等权。这样便有2)1g3(1，2)(24)(25)可以以此作为求解￡。，￡2的规划模型。三个函数的表述，是该题目的最具难度之点。构想一个如上一段所述的模型框架并不很难，要表述出这些函数从而完成模型的建立，却是对参赛者的数学训练和手上功夫的考验。这次的答卷中有表现极好的，但是不多。从这一现象是否可以提出一个问题。近一些年来，在教学中很注意思想性的方面，学生在这一方面也确实有很大提高。但对于实际的手上功夫的训练却渐趋弱化。固然技术的进步代替了许多手上的操作，但同时却派生出许多新的需要人工操作的事情。即如本题，不是计算技术如今天的进步，也就不会提出这样的题目。在教学上应当如何适应情况的这种变化呢?3模型求解此次的答卷中，模型建立与其后的求解计算两相脱节者所在多有。这是不好的。建立了模型，而又不用它去寻解案，那么建模又是为了什么呢?所建的模型难解，不会解，那就应当再进一步抽象，再引入新的假设以简化模型，直到你能够处理它为止(包括引出理论结果或数值求解)。前面两段中，我们先是作等间隔发车的假设，以便将一个有不确定的高维数的问题变为一个2维问题；然后又将本应是面向各单个乘客和单个车路段的目标要求，集总化为三个百分率函数。这些都是为了使得做成的模型能够作求解处理。模型(24)一(25)是容易求解的。作为一个非线性规划问题，只有2维，且约束极为简单，除非目标函数的求值不能实现，总可以用某种直接方法(不涉及求导数)求得近似解。上段中函数(，)和，(h)的二重递推式的表述，实际上就给出了对给定的(I，2)值求这些函数值的算法。(21)、(22)和(23)式则表示如何用这些函数值完成目标函数求值运算。而实际上，(21)式的分子是台条件的()的个数的计数器，(22)和(23)式的分子是台条件f(h)值的累加。因此，g1，g2和g3的计算可以放人到为产生P()和(^)的对k和J的2重循环中。随产生随累加，以免去对这些不再有用的()和(h)的存储。使用参赛者熟知的Mattab语言，容易作成给定(￡】，f2)值后产生‘目标函数值的程序段，再使用Mattab的优化工具箱的程序即可完成求解。这当中或许要为t。，2设一个合理的上界，或许要通过随机搜索选一个好一点的初始点，都是容易做到的事情。有的答卷中选用遗传算法求解此模型，单从其目标函数构成复杂，可以求值而难于求导或作其他处理等特点，这一选择就是正确的。另外要指出一点。如果将函数g3和g进一步分拆成两项，即分别单独计算平峰时段和高峰时段的载客数不到50的车路段百分率和候车超时乘客的百分率，并且对两种时段的交接点处的情况作适当处理，目标函数就可以化为可分离的形式，即f(】，2)=fl(1)+，2(2)这时就可以分别求解两个一维问题f1(t1)1≥0(2)2≥0140知维普资讯http://www.cqvip.com112工程数学学报第19卷比如分别为f1和2设定合理的上界，就可以用0．618方法求解(其关键的运算还是目标函数^和^的求值。)设得解为和f。如果≤f，则(f，)就是所求之解。4结束语作者认为，这个题目的难点在于目标函数的具体表述(如本文第2段)。如果判定建立此表述的难度是适当的，那么这个题目是选得很好的。事实上，尽管漂亮的答卷不多，怛众多答卷上对于这样一个活生生的相当复杂的实际问题，表现出分析的思路是舍理的，也很有深度。为解决问题，表现的思路也很广。不足之处，从总体上说，相对于完成表述，显得数学训练和手上功夫欠缺些。或难度太了些(相对于三天集中时间)?或的确是训练差了些?或二者兼有?以供讨论。建模是重要的。在各类信息系统平台日趋完善的今天．如何从中发现知识，如何优化决策，人们祈求建模。而建模不光要有思想，也要靠人工完成表述，这要求数学训练和手上功夫致谢：本文参考了大量的参赛者的答卷，和全国及北京眷区两级阅卷组的评论 意见 文理分科指导河道管理范围浙江建筑工程概算定额教材专家评审意见党员教师互相批评意见 ，并特别引用了供题者所提供的参考 答案 八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案 。谨在此一井致谢。Ideas，Well—trainingandSkillsareNeededinMathematicalModeling——ASummaryofAnswersoftheProblemB(BeijingInstituteofTechnology，Beijing．100081)AbstractThispaperpresentsasummaryofanswei~oftheproblemBofChinaUndergraduateMathematicalCon—t∞tinModeJingin2001，fromthreeaspects：frameworkofmodels．modelbuildingandmodelsolvingKeywords：mathematic[n~adeling；modelbuilding；busschedtding维普资讯http://www.cqvip.com