美国大学生数学建模竞赛培训材料共299页.pdf

2009cI?)?m?2008 c 12?8 F i c?2009cI?)?m3=?mc?o?n?d?F?mk?d?o?:1?I?0?S?;1?9?(?d?dI?n?http:/www.carroll.edu/kcline/mcm.pdf;1n?D?k?0308Cc?A?k?5g?L?n#?1o?A0?matlab!lingo?Nk?SKud?|?ka?P?AO?a?fi.?U?,?a?I?9?IS?p?J?6?m?D?1XJ?k?fl?X?mcm-dlu-?08c1?14F ii 888I?III?10.1I?)?m?m?o?.30.2mc?S?.4II?999?(?71?mmm?91.1S?.91.2?.91.31n.101.4?.112?(?)?132.1K8.132.2?.132.3flK?.142.4?.142.5)?Y.152.6(J.152.7(?.?dU?Y.162.8o?.16iii iv IIIDDD?193Cardboard Comfortable When it Comes to Crashing214The Booth Tolls for Thee475The Coming Oil Crisis986A Schedule for Lazy but Smart Ranchers1327When Topologists Are Politicians.1598A Convenient Truth?A model for sea level rise forecast 1789The Most Expensive is not the Best21510?mmmKKK26210.1 2003 A-The Stunt Person.26210.2 2005 B-Tollbooths.26210.3 2005 C-Nonrenewable Resources.26310.4 2006 A-Positioning and Moving Sprinkler Systems forIrrigation.26410.5 2007 A-Gerrymandering.26510.6 2008 A-Take a Bath.26510.7 2008 C-Finding the Good in Health Care Systems.266IV?AAA26911 Matlab?AAA27111.1 Cellular Automata in Matlab.27111.1.1 Matlab code considerations.27111.1.2 Examples.27211.2 Queuing Model in Matlab.27411.3 matlab?SK.279 v 12 lingo?AAA28312.1?55y.28312.2 015y.28412.3?.28512.4 lingo?SK.288Part I?III?10.1 I?)?m?m?o?3 0.1III?)?mmm?mmm?ooo?2009cIS?m?uI?m2?5F?8?I?m2?9F?8?fi?m2?6F?8?2?10F?8?m?1?UY|?)d?m?Jpm?Y?|?)?1?o?gIS?m?o?z?O:?g?:?=ISm?+?Im?+?n?m?+?Y?N?Xe?ISm?10?6m?4?Im?6?w?5?w?4?w?n?3?n?m?5?3n?2?g?=?Ly?+?w?+u?+?m?N?Xe?0.5?-0.5?L0.5?-1?g?-3?nd?b?1O?g?-1 zg?m?1n?20?14n?10?dP?3?m?V?(?)?U?)?(-5-10?T?o?mmm(?“?(?IS?)?m?m?08c1?14F 4 0.2mmmccc?SSS?L 1:ccU?F?SN1?12F P?1?Oym?mS?2?5K1?13F1?g0?9Y?1?14F?81ISD?06MCM-A?S2?Latex?1?15F1?.9?matlabSy1?16F?15y?.?.5y!8I5y!?.!?.1?17F1ISD?05MCM2?2lingo)zflK3?uK1?18Fo?1?mS9?2?O8?.9A1?19F?1?z?9lingo)2ISD?071?20F?N?1?6?o(1?21F?y91ISD?2V?.1?22F?N?1?1?23F?N?1?2?uK1?24F?+1ISD?081?25F?N?S!?b0.2 mc?S?5 L 2:c?U?F?M?S?7LkA?.?)?,?5?n?“y?L1n?N?9?Nk(?o?5?fi?(?”?o?1?!?9?u5?”?”3mmXJ?YflK?l?flK?5?9?I?3?I?w?k?S?3?S?I?1.2?,S?59TN?“3S?X?,?S?3N?vk?m?3?L?m(J?)?7L?!O(?I?rfl?E,z?8IAT?U?3?AT?7L?k?8IAT3(F?c?.?v?CXk?7L4?z?5?z?(J?3?,?vk?I?i,?2?U?E?E?D?O?cm?A?A?*:?G?“?6?I?,?7L?N?“!IK/BIK!w?L?LaTexk?“?6?1.3111nnn?3m?1?A?kN?4?k?3?7L?Ad1n?9(?z?fl?z?fl?6?!g,?=?AT?P4z?AT?O?U?”XJ?UflS?XJ?k?k?U?|?mUS?XJU?/N?AT?XJ?)?7L?8?38?F?.7L?(I?(J?N?9?.u?9?.?1n?:1.4?11 1.4?3m?7L?z?3z?Uu?:c?J2?$c?XJ?)?k?pc?o?z?N33?Ly?;?*:7L?gC?k?XJvk?=m?h?U?XJuygC?u?eAT?l?/?”AT?o”qX?U?z”XJ?pc?flfl?g?l?%r?O?r?n?6?L?!?,?(U?c?flkU?flK?o?”?og”?l?5”?“?AT?”?ATr?,?#?5www?U?n)?-?1?4?l?XJ?U?)”?U3?L?12 11?m?1112?(?)?2.1KKK888K8?1?k?.?K8X5D?)XXXXflK62.2?AT?2?H?3?vk?c,?AT?n?mS?r?c4?mM?S?i?z?Ug?u?YflK?X?)?k?n)O#?mu?L?AT?u?)?flK?9?a?S?,?5?g)?5ul?flKI?GX?)?k?5?8?u?uu?8k?AT3e?J?.?vAT(8?2.5)?Y 15 2.5)?YYY?1?3?n?u?nd1?)?S?X?)flK7Lk?)?Y2J2?H?)?Y?yk?I?k?.?)?Y?kl?,?J?)?Y?eul?flK?)?Y?U?J3?I?yfiflK?1?.?&?fi?N?)?Y=?m?Z)?Y,?Y3?E,ATLl?)?Y,?z?“?Z)?YXJ?k?n?”?r?3?5Lfil?1?=?)?Y?E,!?k?3y)?.?yk?flK?/8I?Bu?y?uflK5k?5?5?d?d?ATd?gd?Y?(U2.6(JJJ3pI?L?(J?AT?AO5?fi?L?XJ?U?J?5|?(?.?a.?8?1?”?X?5?(?y3?.!?AT?U?m3?yfi?5?nflK?fi?U/?flK?k?N?(J?J?L?“XJ?.&?.?y?z?k?I?ATL?/“5?w?L?I?3L?e?)”5?o?u“?16 12?(?)?N(J?JJJ?Nm=?.J?)?Y$1?u?(J?(?7L?1g/?7L?(?)?Y?A?Cz?CzN?,U?(?(J4?w?)?Y(?“/?3?A?e?U?w?2.7(?.?dddUUU?YYYkJ?(?=fi3?J?LX?”l?N?w?A?1?u?B 34?u?C67?”I?i5V)k?fl?z?A?J?i5?1?XJ3(J?pfiJ?”?A?N?wu?B?B?kgC?:”3(?c?”a?”?I?3?Lfi?N!?(?.?d?)”?/?I?U?/?w“?L?V)5?i?L?)”:(J?*:?3pJ9?J?:9?5?b?y?nflK?J?U?Y?7I?k?du?vk5?93O?y”mk?m?/?wflK?N?r”2.8ooo?fi!L?qN?”?N?5?)IK!w“?L!L?!/?i?y?!?m?C?H?U?U?AT?i?!?AT?5K5/?mLIK?LiL9?U?C?k?2.8 o?17 IKIK?XJ?K?k?IK?5?j?wIK?L?)?6AT?J?Ng?ATS?IKIKfIK?IKNr?z?k(?8I?y?vkIK?=?k|u?K8?rKXeSN?”?.?I?)4?*:”1?*:1?*:1n?*:1o?*:?a.?L?+?kn?1.?y?a2.rN?g?3.?N?5?XJ?U?$1?O?S?L?$1Azgzg?,?LXJU?L?/“|?u?=?U3e?+=yxplazaWWyxii where 1()denotes an indicator function and plaza denotes the matrix of cells.The Booth Tolls for Thee.75.Simulation and Results To determine the optimal number of tollbooths for a given number of highway lanes,the cellular automata simulation is run for relevant combinations of the two.Recall one of our general assumptions is that the number of tollbooths in any plaza is at least equal to the number of highway lanes that are feeding it.An optimal tollbooth number is selected for a given number of highway lanes when the system cost optimization method discussed earlier is applied.Recall the cost optimization method defines total cost as follows:()QBLBWNCtotal+=,Using the cellular automata model,we compute waiting time as a function of both the number of lanes and the number of tollbooths.For a fixed L,we compare all values of Ctotal and choose the lowest one.The results of this method are presented in Table 6.Table 6:Optimization for Cellular Automata Model Highway LanesTypical DayRush Hour122244356477589610117121381415162729Optimal#Booths As indicated in Table 6,there is fairly good agreement between the recommended number of booths for a typical day and for peak hours.However,we note that the optimal booth number for a typical day never exceeds that for rush hour.Rush hour seems to require slightly more booths than a typical day in order for the plaza to operate most efficiently.Each value in Table 6 is representative of approximately 20 trials.Through these trials,we noted a remarkable stability in our model.Despite the stochastic nature of our algorithm,each number of lanes was almost always optimized to the same number of tollbooths.There were a handful of exceptions;they occurred exclusively for small numbers of highway lanes(3 lanes).Integer values are presented in Table 6 only because fractional tollbooths have no physical meaning.The Booth Tolls for Thee.76.Example As an example of one optimization using the cellular automata model,let us consider the instance of six highway lanes.For comparison,the analogous optimization is carried out previously in models 1 and 2.Figure 11:Minimization of mean waiting time for six lane roadway.Use of 10 tollbooths minimizes the mean wait for customers.Figure 11 is created by running the simulation repeatedly for six lanes and varying the number of tollbooths.A choice of ten tollbooths provides the lowest mean wait time for vehicles.However,ten is not necessarily the optimal number of tollbooths for the system.To determine the optimal solution,we must refer to the cost optimization function developed previously.The Booth Tolls for Thee.77.Figure 12:Minimization of total daily system cost for six lane roadway.Use of 10 tollbooths minimizes both the mean wait for customers and the system cost.As seen in Figure 12,ten tollbooths minimizes system cost as well as mean waiting time(Figure 11).Thus,ten tollbooths is the optimal number for a toll plaza with six incoming lanes(given our selection of parameters).Although the curves in Figures 11 and 12 look very similar,they are indeed more than scalar multiples.One notes that the differences between the two curves is most pronounced at the two ends.Discussion of Cellular Automata Traffic Model Evaluation of Assumptions Let us now consider the assumptions made in the development of the cellular automata traffic model.In what way have these assumptions been either confirmed or discredited?Has there been an assumption which has proven to be particularly limiting?We first assumed that the plaza contains only three types of cells occupied,vacant,and forbidden.In fact,there are two other kinds of cells(flagged cells and incrementing booth cells).These arose as artifacts of the nature of the computer program and did not affect the dynamics of the system.Although treating the plaza in this simplified manner may have neglected some details,it was necessary to develop the framework for a cellular automata based simulation.The model could possibly be improved by The Booth Tolls for Thee.78.adding detail(via additional cell types),but new features unless dramatic would probably not change the fundamental behavior of the system.Our next assumption was that cells represent a physical space that may accommodate a standard vehicle and a comfortable buffer region on either side.Again,this was a simplifying assumption designed to accommodate the use of only three cell types.However,it is not a bad assumption if when we recall that vehicles are typically required to move slowly within toll plazas(1 tollbooth per incoming lane)over the basic 1:1 case.Quantitative Estimation For the cellular automata model,an immediate reduction in cost often is realized upon adding only a single extra tollbooth to a 1:1 plaza configuration(by 1:1,we mean one tollbooth for each incoming lane).This cost reduction is typically continued until a local minimum is reached the number of tollbooths corresponding to this minimum is frequently the optimal number of tollbooths(which we will designate B*).As additional tollbooths are added to the plaza configuration,the cost function typically increases at approximately the same rate as it fell before reaching B*.For cases such as this,we may write a simple expression for the number of tollbooths at which the cost function reaches a value comparable to that for the 1:1 configuration,which we designate:LB=*2 The Booth Tolls for Thee.83.where L is the number of lanes feeding the toll plaza.In this expression,represents the number of tollbooths at which the benefit of added tollbooths in terms of line length is balanced by the corresponding increase in bottlenecking.In other words,if the number of tollbooths exceeds,the cost of the system increases beyond what it would have been if no tollbooths had been added.Certain data from the macroscopic model indicate that the effect of bottlenecking is never sufficient to counterbalance the initial cost reduction from adding tollbooths.Such an example is provided in Figure 13.78910111213120140160180200 Figure 13:Total wait time vs number tollbooths.Data from macroscopic model illustrate that bottlenecking is not sufficient to incur same cost as 1:1 configuration(Note L=6).Briefly,both of our bottlenecking models agree that the first few tollbooths added to a plaza with a 1:1 configuration will reduce waiting time and system costs.However,much of our data suggest that these initial gains achieved by reducing line length are not ever counterbalanced by the effect of bottlenecking.There exist some counterexamples in which may be estimated using the above method.Conclusion We used three models the Basic Car-Tracking Model Without Bottlenecks,the Macroscopic Model for Total Cost Minimization,and the Cellular Automata Model in order to determine the optimal(per our definition)number B of tollbooths required in a toll plaza of L lanes.In short,the Basic Car-Tracking Model uses a simple orderly lineup of cars approaching tollbooths and ignores bottlenecking after the tollbooths.While a quick model,it does omit bottlenecks,and provides us with a strong upper bound on B for any given L.Cost analysis on this model was not as effective as threshold analysis,The Booth Tolls for Thee.84.and we determined an optimal B by recognizing when additional tollbooths did not decrease waiting time significantly.The Macroscopic Model looks at the motion of traffic as a whole,rather than individual models.It tabulates waiting time in line before the tollbooths by considering times when traffic influx into the toll plaza is greater than tollbooth service time.It also finds bottlenecking time by assuming there exists a threshold of outflux,above which bottlenecks will occur,and notices when outflux is greater than said threshold.This is a much more accurate model than the Car-Tracking Model,and it provides us with reasonable solutions for B in terms of L.The Cellular Automata Model looks at individual vehicles,and their“per lane length”motion on a toll plaza made up of cells.With a probabilistic model of how drivers advance and change lanes,this model far better details the waiting time in line and the bottlenecking after the tollbooths than the previous models.It was through this detail that we decide that this model is likely to be most accurate.Thus we decide to recommend values closer to those provided by the automata model than the macroscopic one.In order to write B explicitly in terms of L,we invoke the linearity of the chart shown in the Comparison of Results.Also,in order to preserve integral values for B,we use the floor function and determine that 9.065.1+=LB,where x is the greatest integer less than x.Table 10:Final Results and Recommendations Lanes Car-Tracking Macroscopic Automata Recommendation143222554437655487775109896121110107131212128161414141629272727 Potential Extension and Further Consideration Our models assume that each booth is identical to any other.In recent years,however,systems such as E-ZPass,which allow a driver to electronically pay a toll from an in-car device without ever slowing down to stop at a booth window,have been increasingly prevalent.If all E-ZPass booths also double as regular teller-operated booths,much of our models remain the same,except the average service rate might be increased.The same effects would be similar upon introduction of The Booth Tolls for Thee.85.electronic coin collectors for those drivers with exact change.The trouble comes when all the booths are not the same and drivers may need to change lanes upon entering the plaza.This directed lane changing was not implemented in any of the models presented here,but could easily become a part of the automata model.Exclusive E-ZPass booths also would drastically reduce the operating cost for the booth,since an operators salary would not need to be paid(from$180,000 to$16,000 annually)Sullivan 1994.References Boronico,Jess S.,and Philip H.Siegel.“Capacity planning for toll roadways incorporating consumer wait time costs.”Transportation Research A(May 1998)32(4):297-310.Daganzo,C.F.,et al.1997.“Causes and effects of phase transitions in highway traffic.”ITS Research Report UCB-ITS-RR-97-8(December 1997).Gartner,Nathan,Carroll J.Messer,and Ajay K.Rathi.1992.Traffic Flow Theory:A State of the Art Report.Revised monograph.Special Report 165.Oak Ridge,TN:Oak Ridge National Laboratory.http:/www.tfhrc.gov/its/tft/tft.htm.Gelenbe,E.,and G.Pujolle.1987.Introduction to Queueing Networks.New York:John Wiley&Sons.Jost,Dominic,and Kai Nagel.2003.“Traffic jam dynamics in traffic flow models.”Swiss Transport Research Conference.http:/www.strc.ch/Paper/jost.pdf.Accessed 4 February 2005.Kuhne,Reinhart,and Panos Michalopoulos.1992.“Continuum flow models.”Chapter 5 in Gartner et al.1992.Schadschneider,A.,and M.Schreckenberg.“Cellular automaton models and traffic flow.”Journal of Physics A:Mathematical and General(1993)26:L679-L683.Sullivan,R.Lee.“Fast lane.”Forbes(4 July 1994)154:112-115.Tampere,Chris,Serge P.Hoogendoorn,and Bart van Arem.“Capacity funnel explained using the human-kinetic traffic flow model.”http:/www.kuleuven.ac.be/traffic/dwn/res2.pdf.Accessed 4 February 2005.The Booth Tolls for Thee.86.Appendix I:Fourier Series Hour Influx(cars/min)Fourier Approx of Influx%Error0.515.4415.162724781.7961.51