1-MCM outstanding thesis-美赛国赛论文

数学建模竞赛论文分析0．引言数学建模是指将研究对象的内在规律用数学的语言和方法表述出来，并将求得的数量结果返回到实际对象的问题中去的全过程。在决策科学化、定量化日益重要的今天，人们生活的方方面面，都已经离不开数学建模，例如，保险险种的设计、容器材料的优化、公共汽车的调度等等。可以说，在科技更加发达的明天，数学建模将在更多的领域内发挥更加重要的作用。由于数学建模的重要作用以及远大的前景，作为大学生，自然应该掌握一定的数学建模的方法，懂得一定的数学建模的技巧，数学建模竞赛正是在这种背景下应运而生的。数学建模竞赛以通讯赛的方式进行，参赛者组对参赛，在规定时间内，完成一篇包括模型的假设、建立和求解，计算方法的设计和计算机实现、结果分析和检验、模型的改进等方面的论文。这一竞赛是对参赛者能力和素质的全面考验，尤其是对参赛者开放性思维和创新意识的考验。另一方面，这一竞赛对参赛者的数学水平要求并不是很高，只要做到学以致用就可以了，也就是说，只要具备解出所建立的模型的数学水平和能力就可以了。这一点大大吸引了非数学专业的大学生参与竞赛。在这些有利因素的推动下，数学建模竞赛在大学生中间的影响越来越大，参与竞赛的人越来越多。目前，对我校学生最有影响的竞赛有两个：一年一度的全国大学生数学建模竞赛以及一年一度的美国数学建模竞赛。我校同学尤其是我系同学历年来在这两个竞赛中可以说是硕果累累，屡屡获奖。我写这篇论文的目的，就是通过对优秀论文的仔细分析、解剖，回答下面这两个问题：什么样的模型在竞赛中被认为是好的模型？如何在竞赛中建立好的数学模型？总述数学建模竞赛要求参赛者在规定时间内提交一篇论文，这篇论文应该至少包含摘要、正文、参考文献这三个部分，有必要的，还可以增加其他部分，如附录，备忘录等等。首先是摘要，摘要论文的首页，是在正文前对全文的高度概括，也是给读者的一个导读，一篇好的摘要对于一篇优秀的论文来说是必不可少的。摘要的内容要简洁明了，让读者一阅便知论文的主旨、大意。对于论文中涉及的关键的具有创意的知识和方法要作一些提点，以便引起读者的重视。摘要末尾应当附有论文的关键字，方便读者阅读全文。由于读者首先读到的是摘要而不是正文，因此，是摘要给了读者第一印象，摘要的重要性可见一斑。好的摘要，能够引发读者的兴趣，给读者留下非常好的印象，这一点在竞赛中是十分重要的；反之，平淡无奇、冗长无味或者不知所言的摘要则会使整个论文的质量大打折扣，给读者留下不好的第一印象。其次是正文，正文是整个论文的主干部分，应该包括建立模型，模型求解，结果分析的全过程。论文的质量集中体现在正文质量上，下面，我先阐述正文应该包括的部分，然后在介绍每部分优劣的评判标准。正文的第一部分应为问题的重述。给出的问题是一个具体的现实生活中的问题，通常不能直接对它进行数学加工，为此，用略微抽象的语言对问题进行“数学格式化”是很有必要的，这是建立模型的第一步。问题重述的要求是在不改变问题原意的情况下，用尽量规范的数学语言对问题进行描述，以便后面有针对性的建立模型。从中可以看出，问题重述的好，要做到两点，一是合理，即问题的重述不能改变问题的原意；二是尽量要用规范的数学语言，这样有利于后面的建模过程。第二部分为提出建模所必须的假设，这是非常关键的一个步骤。数学模型是对原问题的一个数学抽象，不可避免的要比原问题来的简单、特殊，因此，必须在原问题的基础上提出一定的假设，原问题才能被抽象出来，成为一个数学模型。假设也是为后面的建模所做的准备工作，因此，提出的假设也要围绕着方便地建立一个好的模型这一指导思想。提出的假设也要满足两个条件：合理性，这是指原问题的本质在假设下没有发生变化，假设仍然符合时常生活的客观规律。抽象性，这是指假设必须有助于对原问题进行抽象、简化，否则，这个假设的提出就没有意义了。很明显，一个好的假设在不改变问题本质以及不违背日常生活规律的前提下，对问题尽可能简化的假设。第三部分就是模型的建立，这是整个论文的核心部分。这就是将实际问题抽象成一个数学问题的过程，是集中体现参赛者创造力和发散性思维的部分。一个好的模型的要求是很高的，首先，它要很好的反映原问题的本质、特点，也就是说，要“抽象得象”；其次，它要舍弃原问题中一些无关紧要的细枝末节，也就是要“抽象的准”。如果模型不能很好的反映原问题的本质、特点，那么它就偏离了原问题，这样的模型显然是没有意义的；但是，另一方面，如果模型完全照般原问题，不经过必要的加工，就会导致后面解模的过程难度异常的大，因为原问题是一个实际问题，影响结果的次要因素是非常多的，如果过多的纠缠于这些细枝末节，必然导致所建立的模型十分复杂，这对解模带来的不便是可想而知的。所以说，一个成功的数学模型，应该牢牢的抓住原问题的本质和特点而大胆的舍弃那些无关紧要的次要因素——一个反映原问题本质和特点的简单的模型才是好的数学模型。第四部分是解模，这部分是利用数学知识和数学方法对上面所建立的模型进行求解，得到结果的过程。这部分主要考察参赛者的数学功底，但是，并不是说，数学功底深，所用的数学知识和方法深奥就是好，能够用尽量简单但是确实有效的方法解模才是最可贵的。这就象吃东西一样，并不一定山珍海味、大鱼大肉才好吃，所谓“食无定味，适口者珍”，也就是说，所用的数学方法能够很好的配合所建立的模型，才是解模成功的关键。另外，在同样达到解模目的的情况下，用的方法越简单，解模的水平越高。正文的最后一个部分是结果分析。由于数学建模竞赛的原问题往往取自日常生活，因此，解模得到的结果应该符合两个条件：符合实际情况以及对实际情况的改进有积极的意义。这部分内容就是要从这两点对结果进行分析。实际上，这部分内容也就是对整个模型的建立以及解模好坏的一个检验，成功的模型必然带来成功的、有价值结果。正文后面是参考资料，这部分内容主要是说明摘要以及正文所引用的数据、资料、知识、方法的来源、出处。这部分内容是方便读者查询相关信息以及其他必要的资料而设置的，只要如实编写，做到文中的数据、资料都言出有典，有据可查就可以了。以上是对引言中提出的两个问题的一般的回答，大致的说明了数学建模的要求以及优劣的评判标准，下面，我将具体分析一篇优秀的数学建模竞赛论文，进一步的阐述引言问题的答案。举例说明：我所分析的论文是2002年美国数学建模竞赛B题的优秀论文，论文中有一些图表无法重现，因此省略，此外，对论文的参考文献以及备忘录部分的翻译工作意义不大，故译文省略。原题ProblemB

Authors:BillFoxandRichWest

Title:AirlineOverbookingYou'reallpackedandreadytogoonatriptovisityourbestfriendinNewYorkCity.Afteryoucheckinattheticketcounter,theairlineclerkannouncesthatyourflighthasbeenoverbooked.Passengersneedtocheckinimmediatelytodetermineiftheystillhaveaseat.

Historically,airlinesknowthatonlyacertainpercentageofpassengerswhohavemadereservationsonaparticularflightwillactuallytakethatflight.Consequently,mostairlinesoverbook-thatis,theytakemorereservationsthanthecapacityoftheaircraft.Occasionally,morepassengerswillwanttotakeaflightthanthecapacityoftheplaneleadingtooneormorepassengersbeingbumpedandthusunabletotaketheflightforwhichtheyhadreservations.Airlinesdealwithbumpedpassengersinvariousways.Somearegivennothing,somearebookedonlaterflightsonotherairlines,andsomearegivensomekindofcashorairlineticketincentive.Considertheoverbookingissueinlightofthecurrentsituation:

LessflightsbyairlinesfrompointAtopointB

Heightenedsecurityatandaroundairports

Passengers'fear

LossofbillionsofdollarsinrevenuebyairlinestodateBuildamathematicalmodelthatexaminestheeffectsthatdifferentoverbookingschemeshaveontherevenuereceivedbyanairlinecompanyinordertofindanoptimaloverbookingstrategy,i.e.,thenumberofpeoplebywhichanairlineshouldoverbookaparticularflightsothatthecompany'srevenueismaximized.Insurethatyourmodelreflectstheissuesabove,andconsideralternativesforhandling"bumped"passengers.Additionally,writeashortmemorandumtotheairline'sCEOsummarizingyourfindingsandanalysis.译文问题B

作者：BillFox和RichWest

标题：航空公司超员订票你备好行装准备去旅行，访问NewYork城的一位挚友。在检票处登记之后，航空公司职员告诉说，你的航班已经超员订票。乘客们应当马上登记以便确定他们是否还有一个座位。航空公司一向清楚，预订一个特定航班的乘客们只有一定的百分比将实际乘坐那个航班。因而，大多数航空公司超员订票?也就是，他们办理超过飞机定员的订票手续。而有时，需要乘坐一个航班的乘客是飞机容纳不下的，导致一位或多位乘客被挤出而不能乘坐他们预订的航班。航空公司安排延误乘客的方式各有不同。有些得不到任何补偿，有些改订到其他航线的稍后航班，而有些给予某种现金或者机票折扣。根据当前情况，考虑超员订票问题：航空公司安排较少的从A地到B地航班机场及其外围加强安全性乘客的恐惧航空公司的收入迄今损失达数千万美元

建立数学模型，用来检验各种超员订票方案对于航空公司收入的影响，以求找到一个最优订票策略，就是说，航空公司对一个特定的航班订票应当超员的人数，使得公司的收入达到最高。确保你的模型反映上述问题，而且考虑处理“延误”乘客的其他办法。此外，书写一份简短的备忘录给航空公司的CEO（首席执行官），概述你的发现和分析。原论文OptimalOverbookingDavidArtherSamMaloneOazNirDukeDurthamAdvisorDavidKrainesIntroductionWeconstructaseveralmodelstoexaminetheeffectofoverbookingpoiciesonairlinerevenueandcostsinlightofthecurrentstateoftheindustry,includingfewerflights,increasedsecurity,passengers'fear,andbillionsinlosses.Usingaplausibleaverageticketprice,wemodelthewaiting-timedistributionforflightsandestimatetheaveragecostperinvoluntarilybumpedpassenger.Forticketholdersbumpedvoluntarily,theinteractionbetweentheairlineandticketholderstakestheformofaleast-bidauctioninwhichwinnersrecievecompansationforforegoingtheirflights.Wediscusstheprecedentforthistypeofauctionandintroduceahighlysimilarcontinuousauctionmodelthatallowsustocalculateanovelformulafortheexpectedcompensationrequired.OurOne-planeModelmodelsexpectedrevenueasafunctionofoverbookingpolicyforasingleplane.Usingthisframework,weexaminedtherelationshipbetweentheoptimal(revenue-maximizing)overbookingstrategyandthearrivalprobabilityforticketholders.Weextendthemodeltoconsidermultioplefareclasses;doingsodoesnotsignificantlyalteroptimaloverbookingpolicy.OurInteractiveSimulationModeltakesintoaccountestimatesforaveragecompensationcosts.Itsimulatestheinteractionbetween10majorU.S.airlineswithamarketbaseof10,000peaple,factoringinpassengerarrivalprobability,flightfrequency,compensationforbumping,andthebehaviorofrivalairlines.Thus,weestimateoptimalbookingpolicyinacompetitiveenviroment.SimulationsofthismodelwithlikelyparameterbaluesbeforeandafterSeptember11givesrobustresultsthatcorroboratetheconclusionsoftheOne-PlaneModelandthecompensation-costformula.Overall,weconcludethatairlinesshouldmaintainordecreastheircurrentlevelsofoverbook.TermsTicketholders:Peoplewhopurchasedaticket.Contenders:Ticketholderswhoarriveintimetoboardtheirflight.Boardedpassengers:Contenderswhoboardsuccessfully.Bumpedpassengers:Contenderswhoarenotgivensaetingontheirflight.Voluntarilybumpedpassengers:Bumpedpassengerswhooptoutoftheirsaetinginexchangeforcompensation.Involuntarilybumpedpassengers:Bumpedpassengerswhoaredeniedboardingagainsttheirwill.Conpensationcost:Thetotalvalueofmoneyandotherincentivesgiventobumpedpassengers.FlightCapacity:thenumberofsaetsonaflight.Overbooking:Thepracticeofsellingmoreticketsthanflightcapacity.Waiting-time:Thetimethatabumpedpassengerwouldhavetowaitforthenextflighttothedistination.Loadfactor:Theratioofthenumberofsaetsfilledtothecapacity.AaaumptionsandHypothesesFlightsaredomestic,direct,andone-way.Thewaiting-timebetweenflightsistheamountoftimeuntilthescheduleddeparturetimeofthenextavailableflighttogivendestination.Theticketpriceis$140[AirlineTransportAssociation2002],independentofwhentheticketisbought,exceptwhenweconsidermultiplefares.Per-September11,theaverageprobabilityofaticketholdercheckinginfortheflight(andthusbecomingacontender)was85%[Smithetal.1992,9].Theper-September11averageloadfactorwas72%[BureauofTrasportationStatics2000].ComplicatingFactorsEachofourmodelsattemptstotakeintoaccountthecurrentsituationfacingairlines.TheTrafficFactorOnaverage,therearefewerflightsbyairlinesbetweenanygivenlocations.TheSecurityFactorSecurityinandaroundairportshasbeenheightened.TheFearFactorPassengersaremorewaryofthedangersofairtravel,suchaspossibleterroristattacks,planecrashes,andsecuritybreachesatairports.TheFinancialLossFactorAirlineshavelostbillionsofdollarsinrevenueduetodecreaseddemandforairtravel,increasdsecuritycosts,andincreasdindustryrisks.TheTrafficFactorBecausetherearefewerflights,itislikelythatthedemandforanygivenflightwillincreas.Flightarelikelytobefuller;theaveragewaiting-timebetweenflightstoadestinationislikelytoincrease,sobumpedpassengerswilldemandhighercompensation.TheSecurityFactorTheincreasinsecuritywilllikelyleadtoanincreasinthenumberofticketholderswhoarriveattheairportbut--dueto--securitydelays--donotarriveattheirdeparturegateintime.Successfulimplementationofsecuritymeasuresmayleadtoanimprovementinthepublicperceptionoftheairlineindstryandanincreasindemandforairtravel.TheFearFactorIncreasedfearofflyingdecreasesdemandforiretravel,sosecuritydelaysmaynotbeasserious.Ontheotherhand,ifahigherpercentageofticketholdersareflyingoutofnecessity,thentheprobabilitythataticketholderbecomesacontendermayincreasebecauseofdecreasedcancellationsandno-shows.However,fewerticketholdersarelikelytoagreetobebumpedvoluntarilyatanyprice,sothepercentageofinvoluntarilybumpedpassengersmayincrease.TheFinancialLossFactorBecausecompaniesmayseektoincreasshort-termprofitsinthefaceofrecentlosses,someairlinesmayimplementmoreaggressiveoverbooking,whichcouldinduceanoverbookingwarbetweenairlines[Suzuki2002,148].Thelikelyincreaseinthenumberofbumpedpassengerswouldleadtoariseincompensationcoststhatwouldpartiallyoffsetincreasedrevenue.Decreasingthenumberofbumpedpassengerswouldimprovetheairlines'imageandmightspurdemand,whichwouldbolsterfuturerevenue.One-PlaneModelIntroductionandMotivationWefirstconsidertheoptimaloverbookingstrategyforasingleflight,independentofallotherflights.Wewillseelaterthatitsresultsareagoodapproximationtotheresultsofthefull-fledgeInteractionSimulationModel.DevelopmentLettheplanehaveacapacityofCidenticalseatsandletaticketcostT=$140independentofwhenitisbought.Lettheairline'soverbookingstrategybetoselluptoBtickets,ifpossible(B>C).WeanalyzethisstrategyinthecasewhenallBticketsaresold.Wemodelthenumberofcontendersfortheflightwithabinomialsidtribution,whereaticketholderbecomesacontenderwithprobabilityp.TheaveragepforflightsfromthetenleadingU.S.carriersisp=0.85[Smithetal.1992].Thevalueofpforaparticularflightdependsonahostoffactors--flighttime,lengthdestination,whetheritisaholidayseason--sowecarryoutouranalysisforarangeofpossiblepvalue.Withourbinomialmodel,theprobabilityofexactlyicontendersamoungtheBticketholdersis.Weassumethateachbumpedpassengerispaidcompensation(1+k)T=140(1+k),forsomeconstantk.Translatedintoeverydayterms,thismeansthatabumpedpassengerrecievescompensationequaltotheticketpriceTplussomeadditionalcompensationkT>0.Later,werelaxtheassumptionthatthecompensationcostisthesameforeachpassenger,whenweconsiderinvoluntaryvs.voluntarybumping.WedefinethecompensationcostfunctionF(i,C)tobethetotalcompensationtheairlinemustpayifthereareexactlyicontendersforaflightwithseatingcapacityC:F(I,C)={WecalculateexpectedrevenueRasafunctionofB:R(B)==140B-140(k+1)Weuseacomputerprogamtodetermine,forgivenC,p,andk,theoverbookingstrategythatmaximizeR(B).However,itisalsopossibletoproduceacloseanalyticapproximation,whichwenowderive.Therevenueforabumpedpassenger,,hasmagnitudektimesthatforaboardedpassenger,T.Thus,theoptimaloverbookingstrategyissuchthatthedistributionofcontendersisinsomesense“balanced,”with1/(k+1)ofitsareacorrespondingtobumpedpassengersandtheremainingk/(k+1)correspondingtoboardedpassengers.Weapproximatethebinomialdistributionofcontenderswithanormaldistribution:,whereisthecumulativedistributionfunctionofthestandardnormaldistribution.Clearingdenominatorsandsolvingtheresultingquadraticingives(1)asananalyticapproximationto.Fork=1,weget=C/p.Thisanalyticapproximationisalwayswithin1oftheoptimaloverbookingstrategyforand.ResultsandInterpretationTheairlineshouldbeabletoobtaingoodapproximationstopandkempirically.Thus,itcantakeourcomputerprogram,insertitsdataforC,T,p,andk,andobtaintheoptimaloverbookingstrategy.Figure1plotsexpectedrevenueR(B)vs.BC=150,k=1,p=0.85,andT=140.AtB=177,theairlinecanexpectrevenueR(177)=$24,200,whichismorethan15%inexcessoftheexpectedrevenueR(150)=$21,000fromapolicyofnooverbooking.Operatingataless-than-optimaloverbookingstrategycanhaveseriousconsequences.Forexample,AmericanAirlineshasanannualrevenueof$20billion[AMRCorporation2000].AnoverbookingpolicyBoutsidetherangeof[173,183]impliesanexpectedlossofmorethan$1billionover5-yearperiodcomparedwiththeexpectedrevenueat=177.LimitationsThesingle-planemodelFialstoaccountforbumpedpassengers’generaldissatisfactionandprorensitytoswitchairlines;Assumesasimpleconstant-costcompensationfunctionforbumpedpassengers;Ignoresthedistinctionbetweenvoluntaryandinvoluntarybumping;Assumethatallticketsareindentical–thatis,everyonefliescoach;AssumesthatallBticketsthattheairlineiswillingtosellareactuallysold.Evenso,thyemodelsuccessfullyanalyzesrevenueasafunctionofoverbookingstrategy,planecapacity,theprobabilitythatticketholdersbecomecontenders,andcompensationcost.Later,wedevelopamorecompletemodel.ThecomplicatingfactorsFirst,though,weusethebasicmodeltomakepreliminarypredictionsfortheoptimaloverbookingstrategyinlightofmarketchangesduetothecomplicatingfactorspost-September11.Ofthefourcomplicatingfactors,onlytwoaredirectlyrelevanttothismodel:thesecurityfactorandthefearfactor.Theprimaryeffectofthesecurityfactoristodecreasetheprobabilitypofaticketholderreachingthegateontimeandbecomingacontender.Ontheotherhand,theprimaryeffectoffearfactoristhatagreaterproportionofthosewhoflydosooutofnecessity;sincesuchpassengersaremorelikelytoarrivefortheirflightsthancasualflyers,thefearfactortendstoincreasep.Figure2plottheoptimaloverbookingstrategyvs.pforfixedk=1andC=150.Itisdifficulttoassesstheprecisechangeinpresultingfromthesecurityandfearfactors.However,airlinescandeterminethisempiricallybygatheringstatisticsontheirflights,thenuseourgraphorcomputerprogramtodetermineanewoptimaloverbookingstrategy.One-PlaneModel:MultifareExtensionIntroductionandMotivationMostairlinessellticketsindifferentfareclasses(mostcommonlyfirstcalssandcoach).WeextendthebasicOne-PlaneModeltoaccountformultiplefareclasses.DevelopmentForsimplicity,weconsideratwo-faresystem,withfirst-classseatsandcoachseats.Weassumethatafirst-classticketcostsandthatacoachticketcosts.Weconsideranoverbookingstrategyofsellinguptofirstcalssticketsanduptocoachtickets,wherethetwotypesofsalesaremadeindependentlyofoneanother.Weassumethatafirst-classticketholderbecomesafirst-classcontenderwithprobabilityandthatacoachticketholderbecomesacoachcontenderwithprobability.Weusetwoindependentbinomialdistributionsasourmodel.First-classticketholdersaremorelikelytobecomecontendersthancoachpassengers,sincethayhavemadealargemonetaryinverstmentintheirtickets;thatis,>.Thus,theprobabilitiesofexactlyifirst-classcontendersandexactlyjcoachcontendersare,.Wemodelcompensationcostsasconstantperbumpedpassengerbutdependentonfareclass,with()ascompensationforabumpedfirs-classpassengerand()forabumpedcoachpassenger.Wedefinethecompensationcostfunction:F(i,j,,)={Thejustificationforthethirdcaseisthatanexcessofcoachconrtendersisallowedtospilloverintoanyavailablefirst-classseats.Ontheotherhand,excessfirst-classcontenderscannotbeseatedinanyavailablecoachseats;thisfactisreflectedinthesecondcase.WemodelexpectednevenueRasafunctionoftheoverbookingstrategy():ResultsandInterpretationForfixed,and(i=1,2),wecanfind(forwhichismaximalbyadaptingthecomputerprogramusedtosolvetheone-farecase.Forexample,foraplanewith=20firstclassseats,=130coachseats,ticketcostofand,andcompensationconstants,weobtaintheoptimaloverbookingstrategieslistedinTable2.Theoptimalstrategyinvolvesrelativelylittleoverbookingoffirst-classpassengers,sincethereisamuchhighercompensationcost.However,thetotalnumberofpassengers(coachplusfirst-class)overbookedinanoptimaltwo-faresituationisvirtuallythesameasthetotalnumberoverbookedintheone-faresituation.Theupshotisthattheeffectofmultiplefareclassesontheoptimaloverbookingstrategyisnotverysignificant;so,whenweconstructourmoregeneralmodel,wedonottakeintoaccountmultiplefares.CompensationCostThekeyelementthatseparatesdifferentschemesforcompensationbumpedticketholdersisthedegreeofchoiceforthepassenger.Airlineoftenholdauctionforcontendersinwhichthelowestbidsarefirsttobeboughtoffofaflight.WeconstructamodelforinvoluntarybumpingcoststhatisbasedonDOTregulationsandtakesintoaccountthewaitingtimedistributionforflights.Thenwediscussauctionmethodsforvoluntarybumpingandderivenovelresultsforexpectedcompensationcostforacontinuousauctionthatmatchesactualticketauctionsfairlywell.InvoluntaryBumping:DOTRegulationsTheDepartmentofTransportation(DOT)requireseachairlinetogiveallpassengerswhoarebumpedinvoluntarilyawrittenstatementdescribingtheirrightsandexplaininghowtheairlinedecideswhogetsonoverbookedflightandwhodoesnot[DepartmentofTransportation2002].Travelerswhodonotgettoflyareusuallyentitledtoan“an-the-spot”paymentofdeniedboardingcompensation.Theamountdependsonthepriceoftheirticketandthelengthofthedelay:Passengersbumpedinvoluntarilyforwhomtheairlinearrangessubstitutetransportationscheduledtogettotheirfinaldestinationwithinonehouroftheiroriginalscheduledarrivaltimereceivenocompensation.Iftheairlinearrangedsubstitutetransportationscheduledtoarriveatthedestinationbetweenoneandtwohoursaftertheoriginalarrivaltime,theairlinemustpaybumpedpassengersanamountequaltotheirone-wayfare,witha$200maximum.Ifthesubstitutetransportationisscheduledtogettothedistinationmorethentwohourslater,orifairlinedoesnotmakeanysubstitutetravelarrangementsforthebumpedpassenger,theairlinemustpayanamountequaltothelesserof200%ofthefarepriceand$400.Bumpedpassengersalwaysgettokeeptheirticketsandusethemonanotherflights.Iftheychoosetomaketheirownarrangements,theyareentitledtoan“involuntaryrefund”fortheiroriginalticket.Theseconditionsapplyonlytodomesticflightsandnottoplanesthathold60orfewerpassengers.ThefunctionforthecompensationcostforaninvoluntarilybumpedpassengeriswhereTiswaitingtimeandFisthefareprice.Weassumethatallflightstoagivenlocationaredirectandhavethesameflightduration.Thus,thewaitingtimebetweenflightsequalsthedifferenceindeparturetimes,andwaitingtimeTisthetimeuntilthenextflighttothedestinationdeparts.Weassumethatinvoluntarilybumpedpassengersalwaysaskforarefundoftheirfare.InvoluntaryBumping:TheWaitingTimeModelTousethecompensationcostoffunctiontodeterminetheaveragecompensation(perinvoluntarilybumpedpassenger),wewouldneedtoknowthejointdistributionoffarepriceandwaitingtimes.Becausethisinformationwouldbeextremelydifficulttoobtain,weoptinsteadforapracticalcompromises:Werestrictourattentiontodeterminingtheexpectedcompensationcostfortheaverageticketprice,$140[AirlineTransportAssociation2000].Wespecifyaworkablemodelforthedistributionofwaitingtimethatallowsustocalculatethiscostdirectly.Ourmodelforthedistributionofwaitingtimesistheexponentialdistribution,acommondistributionforwaitingtimes.LetTbearandomvariablerepresentingwaitingtimebetweenflights;thenandE(T)==1/,whereisthemeanwaitingtimeforthenextavailableflight.TheexpectedcostofcompensatinganinvoluntarilybumpedpassengerwhopurchasedaticketofpricePcanbeevaluateddirectlyandisFromexaminingairlinebookingsites,weestimatetheaveragedaytimewaitingtimetobe2.6h,notincludingthetimebetweenthelastflightofthedayandthefirstflightofthenextday.Ifweincludethesenight-next-daywaitingtimeinourcalculations,weobtain4.8h;thisvaluecorrespondstofiveflightsper24-hoursperiod,whichisfairlytypical.Usingthesmaller,strictlydaytimevalue=2.6h,weobtainanexpectedcompensationcostof$255.ThisestimateisatoddswithAlstrupetal.[1986],whoquoteanaveragecompensationof$50in1997dollars;accordingtohourmodel,thisamountcorrespondstoanaveragewaitingtimeof=0.55h.Onepossibleconclusionisthatourmodeldoesnotprovidethebestfitforthewaitingtimedistribution.Anotherpossibleconclusionisthatinvoluntarybumpingregulationswerechangedornotenforcedproperly15yearsago.VoluntaryBumping:AuctionModelsIn1968,J.L.Simonproposedanauctionamountticketedpassengers.Eachticketedpassengercontendingforaseatonaflightwouldsubmitasealedenvelopebidofthesmallestamountofmoneyforwhichthecontenderwouldgiveuptheseatandwaituntilthenextavailableone.Theairlinewouldcompensatethepassengerswhorequiredtheleastmoneyandrequirethattheygiveuptheirseats.Passengerswouldnevergetbumpedwithoutsuitablecompensation,andairlinescouldraisetheiroverbookinglevelmuchhigherthantheycouldotherwise.AfterRalphNadersuccessfullysuedAlleghenyAirlinesforbumpinghim,variantsonthisschemehavegraduallybecomestandardthroughouttheindustry.Therearetworeasonablewaystoattemptanauction.PerSimon,forceeverycontendertochooseaprioriapriceforwhichtheywouldgiveuptheirticket.Theairlinecouldarrangeallbumpingsimmediately.Theactualpracticebymostairlinesistoannouncepossiblecompensationpricesindiscretetimeintervals.Customerscanthenacceptanyoffertheywishto.Thefirstisattractivetotheairlinesbecauseitisinstantandminimizescompensation.Thesecond,however,canbestartedwellbeforeaflightdeparts;andifintervalsareincreasedgraduallyenough,thedifferenceincostisnegligible.Themethodsshouldgeneratesimilarresults,soforsimplicityweconcentrateonthesecond,thoughwithcontinuouscompensationofferings.VoluntaryBumping:Continuous-TimeAuctionIntheliterature,itiscommontoassumethatifmpassengersarecompensatedthroughanauction,thetotalcostfortheairlineshouldbelinearinm,althoughsomeauthors(suchasSmithetal.[1992])recognizethatthefunctionshouldbenonlinearandconvexbutdonotanalyzeitfurther.Infact,wecansayagreatdealmorewithonlyafewbasicassumptions.Indeed,supposethatNticketholderscheckinforaflightwithcapacityC,withn>C.Eachcontenderhasalimitprice,thesmallestcompensationtobewillingtogiveuptheseat.Anairlinecanalwaysrebookaticketholderononeofitsownlaterflightsatnocost(i.e.itdoesnothavetopayforaticketonarivalairline).Inanidealauction,theairlineofferssuccessivelyhighercompensationprices;whenevertheofferexceedsacontender’slimitprice,thecontendergivesuptheticketvoluntarily.Supposethatticketholders()areorderedsothat’slimitpriceislessthan’slimitpricefori<j.Define:D(x)=theprobabilitythatarandomlyselectedticketholdergivesuptheseatforapricex.=thecompensationthatairlinemustpaytogiveuptheticket.=thetotalcompensationthattheairlinemustpayformcontendersgiveuptheirseats.Wehave=.TodetermineE[],wedetermineE[]fori.Todothis,weneedthefollowingresults:.[EDITOR’SNOTES:Weomittheauthors’proof.]VerylittlecanbedonebeyondthispointwithoutfurtherknowledgeaboutthenatureofD(x).Thereisnotmuchrecentdataonthis;butwhenairlineswerefirstconsideringmovingtoanauction-basedsystem,K.V.Nagarajan[1978]polledairlinepassengersontheirlimitprice.Althoughheperformedlittleanalysis,wefindthatthecumulativedistributionfunctionofthislimitpricefitsverycloselyexponentialcurvesoftheformforafixedA(Figure3)WithforsomeconstantA,then.[EDITOR’SNOTES:Weomittheauthors’proof.]UsingtheapproximationthisbecomesThereisnoreasontobelievethatthevalueofAisconstantacrossscenarios.Forexample,contenderswillcertainlyacceptasmallercompensationifthenextflightisdepartingsoon.Forourpurposes,however,weassumethatAisconstantoverallsituations;andweestimatethatonaflightwithcapacityC=150andonlyasmallnumberofoverbookedpassengers,hasalimitpriceof$100.ThenwehavesoHence,theexpectedcompensationrequiredto