美国2007建模大赛优秀论文.docx

2007 MCM ProblemsPROBLEM A: GerrymanderingThe United States Constitution provides that the House of Representatives shall be composed of some number (currently 435) of individuals who are elected from each state in proportion to the states population relative to that of the country as a whole. While this provides a way of determining how many representatives each state will have, it says nothing about how the district represented by a particular representative shall be determined geographically. This oversight has led to egregious (at least some people think so, usually not the incumbent) district shapes that look unnatural by some standards. Hence the following question: Suppose you were given the opportunity to draw congressional districts for a state. How would you do so as a purely baseline exercise to create the simplest shapes for all the districts in a state? The rules include only that each district in the state must contain the same population. The definition of simple is up to you; but you need to make a convincing argument to voters in the state that your solution is fair. As an application of your method, draw geographically simple congressional districts for the state of New York. PROBLEM B: The Airplane Seating ProblemAirlines are free to seat passengers waiting to board an aircraft in any order whatsoever. It has become customary to seat passengers with special needs first, followed by first-class passengers (who sit at the front of the plane). Then coach and business-class passengers are seated by groups of rows, beginning with the row at the back of the plane and proceeding forward. Apart from consideration of the passengers wait time, from the airlines point of view, time is money, and boarding time is best minimized. The plane makes money for the airline only when it is in motion, and long boarding times limit the number of trips that a plane can make in a day. The development of larger planes, such as the Airbus A380 (800 passengers), accentuate the problem of minimizing boarding (and deboarding) time.Devise and compare procedures for boarding and deboarding planes with varying numbers of passengers: small (85-210), midsize (210-330), and large (450-800).Prepare an executive summary, not to exceed two single-spaced pages, in which you set out your conclusions to an audience of airline executives, gate agents, and flight crews.Note: The 2 page executive summary is to be included IN ADDITION to the reports required by the contest guidelines.An article appeared in the NY Times Nov 14, 2006 addressing procedures currently being followed and the importance to the airline of finding better solutions. The article can be seen at: /2006/11/14/business/14boarding.html2007 ICM ProblemPROBLEM C: Organ Transplant: The Kidney Exchange ProblemTo view and print problem C, you will need to have the Adobe Acrobat Reader installed in your Web browser. Downloading and installing Acrobat is simple, safe, and only takes a few minutes.Download Acrobat HereClick the Title Below To View a PDF of Problem COrgan Transplant: The Kidney Exchange ProblemThe drawing of political districts in the United States is a great source of contention among elected officials and the electorate. Often, a political party will use its power to influence the redistricting process so that the districts are drawn in such a way as to increase that partys chances of winning seats in the political body in question. This leads to oddly shaped districts that are determined more by politics than the geographical or population characteristics of the area or the concerns of the citizens living within the district in question. The goal of this model was to provide a simple,impartial method for creating political districts in the states that also centered the districts in a single geographic area. In other words, the goal was to make the districts as square as possible, since this would help to ensure that the people covered by the district were close together geographically. It was hoped that this geographic proximity would mean that more residents of the district would have the same concerns for their representative to convey to Congress, increasing the likelihood of their concerns being address by Congress. A further goal for this model was that it would be generic enough that it could be applied to any state and any level of government, from New Yorks congressional districts, to the districts for the Mississippi state legislature. For this model, The State of New Yorks congressional districts were used. For this model, the population density was viewed as function of the latitude and longitude of a position with in the state. This function is labeled (1)Where x is the latitude and y is the longitude. To determine the bounds of the district, the number of people in a district (district) was set equal to a double integral that integrated of an area of the state (2)In this integral, xi is the starting x-coordinate, xf in the final x-coordinate, yi is the starting y-coordinate, and yf is the final y-coordinate. While, this provided a method for determining theboundaries of a district, it could not be easily used to determine a series of districts. To adhere totime constraints, the integral was broken into two integrals. This was done in such a way as to dividethe state into a series of horizontal or vertical bands with the first integral by setting the integralequal so several times the number of people in a district. In the case of New York, the number 4 waschosen, meaning that each band contained 4 times the number of people in one district and that thestate would be divided into 7 vertical or horizontal bands. This gives the integrals (3) (4)Staring at x=0 or y=0, the integral could be evaluated with the upper integration limit unknown.The resultant equation could then be solved for the unknown upper limit of integration. Once the state had been divided into 7 horizontal or vertical bands, each band was then divided into 4 parts.These parts would become the districts. This was done using the integrals (5) (6)Again, staring at x=0 or y=0, the integral could be evaluated with the upper integration limit unknown. The resultant equation could then be solved for the unknown upper limit of integration.This would give a series of horizontal or vertical lines from band to band. These line, combined with the bands would create the districts. The series of images below depicts the process for vertical bands and horizontal district lines.For states that have a prime number of districts, the division of the districts is determined based off of one minus the number of districts that the state actually has, this ”lost” district must be accounted for. To do this, the point on the state with the greatest population density is chosen. A square is then expanded around this point until the size of one district is reached. This becomes the ”lost” district. A new population density function is now created where values for the population density of the coordinate that are within the box that was just created are set to zero. This new function will be called p(x, y). From here, the model is implemented the same as above.To implement this model for the population of the state of New York, a grid indexed from 0 to 35 latitudinally and 0 to 47 longitudinally was laid over a map of the state of New York. A spreadsheet was then created which had the same indexing as the grid. This spreadsheet was then filled in with the population density for the county each grid square resided in. If a grid square resided over water or in another state, its population density value was set to zero. If a grid square resided at the intersection of several counties or the intersection of a county and a large body of water, the population density value was set to the population density of the county that had the largest area in the grid square in question. Once this data had been entered into the spreadsheet, it was converted to a text file so that it could be read into a Java program. The program then performed a numerical version of the integrations described above on this discrete distribution.This implementation was chosen because it would have been too time consuming to regress a truly accurate distribution function for the population density of the entire state and then integrate thefunction and solve the results of those integrations several times. Furthermore, the data the was readilyavailable from the Census Bureau was a discrete distribution, so this implementation would be almostas accurate as integration on a regressed function, with the advantage of being considerably simpler and less time consuming to implement. However, this implementation did have several limitations,many arising from the assumptions that were necessary for this implementation to work effectively within the time constraints.The assumptions made in this implementation of our model are: The population density of each county is assumed to be uniformly distributed. Errors arising from errors in determining the population density of grid squares where countiesjoin or counties meet bodies of water or other states are assumed to be inconsequential. Small fluctuations between the sizes of districts are allowed. The low resolution of the grid will not significantly affect the outcome of the implementation. A solution exists for the equations that this model generatesThe limitations of this implementation of the model are: States that have a number of representatives that is prime present additional problems. Extremely densely populated areas present additional problems Different starting points (origins) could create different maps Resolution has to match the states population density distribution Creating a file representing the population distribution of the state is very time consuming在美国的政治区的绘制是一个伟大的民选官员和选民之间客源的争夺。通常情况下，一个政党将使用其权力影响选区重划过程中，使该地区绘制在这样一种方式，以提高打赢问题政治机构席位，党的机会。这将导致形状奇特的地区，更多地取决于政治，而不是该地区的地理或人口特征或生活小区内有问题的市民的关注。这个模型的目标是提供一个简单的，公正的方法创造政治区的状态，也集中在一个单一的地理区域的地区。换句话说，目标是使该地区尽可能为正方形，因为这将有助于确保人民区所涵盖的地域并拢。希望地理上的接近，这将意味着更多的小区居民将有同样的担忧，增加他们的代表传达给国会的可能性其地址由国会的关注。这个模型的另外一个目标是，这将是足够通用的，它可以适用于任何国家和任何级别的政府，来自纽约州的国会选区，密西西比州州议会的选区。在这个模型中，纽约州国会选区。对于这个模型，人口密度被视为功能的状态的位置的纬度和经度。此功能是标记（1）其中x是纬度和y是经度。要确定的边界区，一些人在一区（ district ）等于一个区域的状态，集成了双积分（2）在这个积分，喜的是在最后的x坐标x坐标， XF开始，易建联是起始Y坐标， YF是最后的y坐标。 ，虽然这提供了一种方法确定一个地区的边界，它不能很容易地用来确定一系列的地区。要坚持TOTIME约束，积分被分解成两个积分。这样做是在这样一种方式，以d