1、摘要本文就沿著”大長河”露營問題進行探究,旨在解決如何使更多的游客加入漂流,即使目標函數最大化的問題。由于游客數量的增加，管理者應合理安排游客出行，最大限度的利用露營地，并且使船只盡少接觸河面上其他船只，在考慮河面容納量的條件下，解決游客出行問題。針對問題一，建立了動態規劃模型。我們首先根據管理者的目的和旅客的要求對摩托船和橡皮筏的比例進行研究，得出比例8：2。其次，利用泊松分布和正態分布，建立整體規劃模型，得到乘坐不同類型船只漂流天數和每天行程的概率，并對其進行歸一化處理。接著，利用截面法，得出旅客個數與露營點個數成正比。最后，建立動態規劃模型，利用matlab求解：露營點數，船數量，平均每

2、天旅客數為。 針對問題二，建立了排程方案模型，得到每天的排程方案。首先對某一天的情況進行分析，得出這天出發的機動帆船和橡膠筏的數量分別為5艘和1艘，以及得出發船時刻表。這樣就可以根據這天的情況來安排，依次循環，得到以后每天的方案。 問題三要求我們對河流容納量提出自己的建議，我們建立了河流容納量模型。很容易得到河流最大容納量是露營點的個數48.為了使模型更具說服力，我們對模型進行了驗證。得出的結果認為是合理的。 關鍵詞：露營 漂流 整數規劃模型 排程方案模型 容納量模型 動態規劃模型目錄一、問題重述3二、問題分析3三、符號說明5四、模型假設6五、模型的建立與求解6六、模型驗證14七、模型評價15

3、八、模型改進15一、 問題重述隨著生活水平的提高，人們更傾向于投入野外生活，親近大自然。聞名遐邇的大長河以漂流而享譽世界各地，河流順流而下，共225公里。可供旅客選擇的船只有兩種：一種為平均4英里/小時的以槳為動力的橡膠筏；另一種為平均8英里/小時的機動帆船。目前每年有六個月的旅行開放時間（一年內的其余部分的天氣對于河流旅行來講溫度太低），共可以安排X次旅行，整個旅行河道上共均勻分布有Y處露營，從開始到結束經歷6到18個夜晚。在此，我們提出以下兩個問題：問題一：在露營地一定的條件下，選取不同的時間（單位為夜）以及推動方式（馬達或槳），使得行駛的船只最少的接觸到河面上的其他的船只，最大限度的利用

4、露營地，也就是說，在長河的的漂流季節，最多能有多少乘船旅行加入？如何安排一個最優的混合旅行方案，提出最佳排程方案。問題二：對于河流的承載能力提出相關的意見，以及準備一頁備忘錄，向河流的管理者描述我們的主要發現。二、 問題分析問題一在數學上屬于動態規劃問題，即在不同時間、不同的驅動方式下，安排一個最優的混合旅游方案，使得在一定時間段內最大限度的利用露營地是的每天增開盡量多的船只而接納更多的旅行隊，并且要使船只盡可能少接觸到河上的其他船只。假設管理者只考慮船只的主動性，根據實際調查的情況來合理安排摩托船和橡膠筏的數量比，暫且忽略旅客對不同中船只喜歡與否的主觀性。這樣旅行隊選擇摩托船和橡膠筏的概率問

5、題就化簡成為求解所安排兩種類型船只的比例。然而，為讓旅行隊享盡水面飄流的樂趣，必須將船只的主動權給予旅行隊，即：在規定的時間范圍內（8：00-18：00）搭乘一種船只，并完成漂流。乘坐不同類型船只的旅行隊的旅行天數的平均值不同，但他們的旅行的天數都成泊松分布；不同旅行天數計劃旅行路程的平均值也不同，但是每天的旅行路程服從正態分布。于是可以得到不同類型的旅行船只的天數和路程，可以由此計算出旅行船只在河面上相遇的概率。在我根據靠近優先的原則概率。根據題目，我們可以得到6個月內的總漂流船只和露營地的個數，先確定第一天的船只類型，進而計算出6個月中的每天的排成安排。問題二中，要對河流的承載能力提出建議

6、，在問題一的基礎上得出每天最多可以進行幾次水上旅行，才能最大限度的利用露營地，從而進一步求出這六個月可以進行幾次水上旅行，得出該河流的承載能力。實現河的承載能力最大化，對求出的河流承載能力進行分析，給出意見。思路流程圖如下：預處理1、摩托船和橡皮筏的比例2、旅行天數的概率分布3、每天行進路程的概率分布4、截面法得到旅客數與露營點個數建立規劃模型目標函數：旅客最大約束1、旅客找到露營地概率足夠大2、旅客間相遇次數足夠小3、露營地個數約束動態規劃模型每一天根據前一天安排 第一天摩托船：4橡皮筏：2建立排程方案模型三、 符號說明游客選擇摩托船的概率游客選擇橡皮艇的概率選擇摩托船漂流所用的時間選擇橡皮

7、艇漂流所用的時間選擇摩托船游玩k天的概率選擇橡皮艇游玩k天的概率歸一化處理后選擇摩托船游玩k天的概率歸一化處理后選擇橡皮艇游玩k天的概率選擇旅行時長為k天的平均概率選擇旅行時長為k天的游客平均每天漂流的路程船的平均速度每天最多旅行長度k天旅行計劃的游客每日旅行路程游客平均每天行程四、 模型假設1.旅行隊一旦選定一種交通工具在途中不能更改。2.認為船一旦行駛到終點即可被公園投入再使用。3.旅行隊的數量足夠。4.每一組旅行隊的行駛時間為8：00-18：00，其他時間在露營地休息。5.不考慮外界因素給船帶來的影響。6.假設在這六個月中的游客數量符合正態分布。五、 模型的建立與求解我們假設游客選擇游覽

8、的天數為天，已知河總長為225英里，橡膠筏的速度為4英里/每小時，機動帆船速度為8英里/每小時。 則：機動帆船平均每天漂流的時間： （1） 橡膠筏平均每天漂流的時間： （2）其中為船只完成整段旅行所停留的夜晚。夜晚個數為6至18個。因為河流的總長是225英里，乘客可以選擇平均4英里/小時的橡膠筏或者平均為8英里/小時的機動帆船旅行。因此每位乘客的漂流時間為56.25小時或者28.125小時。考慮到整個旅行從開始到結束會經歷6至18個夜晚，因此每天的漂流時間為1.5625-4.6875小時或者為3.125-9.375小時，每天的漂流行程為12.5-37.5公里。據此可得不同類型漂流的船次如下表：

9、表一 不同漂流類型不同旅行天數下每天平均旅行時間天數6789101112131415161718膠筏9.487.06.35.65.14.74.343.73.53.33.1機動帆船4.743.53.12.82.52.32.221.81.81.71.5從表中可知，總共有26種不同的旅行方式，最多漂流時間為9.4小時，我們可以認為每日最長漂流時間為10小時。也就是說，每天的漂流時長不會超過10小時。5.1.1模型一的建立（1）機動帆船和橡膠筏比例的研究我們從兩方面來考慮現實橡皮筏和機動帆船的比例。一是從河流的管理者角度，我們知道機動帆船的速度是橡膠筏的2倍，可以認為選擇機動帆船的旅行隊會更快的到達終

10、點，管理者要允許更多的旅行隊參加漂流，機動帆船應該更多一些。二是從旅行隊的角度，河流全長225英里，是比較長的，旅行隊的目的是為了游賞風景而不是為了劃船，可以認為旅行隊選擇機動帆船的概率會更多一些。綜合以上兩點考慮，我們認為，旅行隊選擇機動帆船和橡膠筏的比例為8:2，也就是說，旅行隊選擇機動帆船的概率為80%，選擇橡膠筏的概率為20%。即：（2） 旅行隊露營天數的研究 我們假設選擇機動帆船和橡皮筏的旅行隊每天行進6小時，這是符合實際情況的.那么，機動帆船所用的總時間： （小時） (3)選擇機動帆船的旅行隊平均需要的旅行時長： （天） （4）同理，橡皮筏的旅行隊平均需要的旅行時長：（小時） (5

11、)選擇橡皮筏的旅行隊平均需要的旅行時長：（天） (6)假設游客對旅游天數的選擇服從泊松分布，即得到，選擇不同類型漂流的旅行隊的旅行天數的概率分布： 選擇機動帆船的旅行隊旅行天數k的概率分布： (7) 表二 游客選擇摩托船旅行k天的概率分布 時長6789101112概率0.14620.10440.06530.03630.01810.00820.0034時長131415161718概率0.00130.00050.00010.00000.00000.0000選擇橡膠筏的旅行隊旅行天數k的概率分布： (8)表三 游客選擇橡膠筏旅行k天的概率分布（3）槳、馬達和露營天數的關系首先對上一步求出的旅行隊旅行

12、天數k的概率分布進行歸一化處理： (9) (10)就可以得到旅行隊旅行選擇時長的概率公式: (11)表四 游客選擇不同方式旅游k天的平均概率分布時長6789101112概率0.318360.237060.16040.10270.064780.041680.0276時長131415161718概率0.018460.013980.008540.004920.002760.0016（4）每日旅行路程的研究：假設旅行隊可以自由選擇每日旅行路程，并且這個路程符合正態分布規律。1、均值：旅行k天的游客每天的平均路程： （12）這里把總的路程看作1，以簡化計算。2、方差：前面已經說明，每天一條船最長漂流時間

13、小時旅行隊每天旅行速度的平均值： (英里/小時) (13)那么旅行隊每日旅行的最大路程： (14)根據概率論中的準則確定旅行路程的 (15)得到 (16)3、天旅行計劃的游客每日旅行路程： 上面得到了天旅行計劃的游客每日平均旅行路程和路程的方差，我們認為，旅行隊每日旅行的路程服從正態分布，這是符合實際情況的，因為剛開始的時候，旅行隊由于好奇新鮮等原因，每日走的會相對較慢，路程較短；在旅行的中間時刻會相對較快，形成較長；在快結束的時候，也會相對較慢，行程較短。 (17)其中代表在k天旅行計劃中的第天，就表示天旅行計劃之內第天的行程。4、游客平均每天行程： (18) （5）截面法模擬游客流 在以上

14、的平均化計算的鋪墊下，把問題模擬成流體在管子中的流動，在流量最大的情況下計算單位時間里通過某一截面的流體體積即可得到最大流量。流體截面簡化圖計算公式為： (19)代入數據，得到： (20)從簡化的式子可以得到旅行的旅行隊數X是與露營點數Y成正比的，說明，露營點越多，允許旅行的旅行隊就越多，這是符合實際情況的。2. 動態規劃模型的建立 這條河長225英里，認為露營地的個數是符合實際情況的。下面以為例說明確定旅行隊數和露營點數規劃模型的建立過程。在第四步中，我們得到了旅行隊每日的最長路程，于是得到游客每日平均通過的最多露營點數量: (21)假設游客會選擇距離希望露營點最近的露營地露營，那么旅行對可

15、以選擇的通過的露營點的個數有15個，我們可以根據旅行隊一天走過的路程來計算經過的每個露營點露營的概率，計算公式如下： (22)下表就是旅行隊每日經過的每個露營點露營的概率：表五 旅行隊每日經過的每個露營點露營的概率123456780.03760.06580.07720.08640.0980.12570.14740.16891011121314150.13940.11760.09630.05840.02860.00730.0089每個露營點被占據的概率： (23)代入公式計算得到每個露營點被占據的概率的數據表如下：表六 每個露營點被占據的概率30313233343536370.64560.645

16、40.64480.64450.64430.64390.64360.643538394041424344450.64320.64290.64210.64140.64080.64010.63950.639246474849505152530.63860.63820.63760.63730.63680.63640.63570.6355545556575859600.63510.63470.63460.63420.63360.63330.6328（6） 特殊情況下，一隊游客可以在時間t內找到一處空露營點的概率k近似于二項分布，其公式為： (24)變換導出： (25)由于是不確定的，得到的是與的關系式。

17、在計算過程中，令，得到一組解，可以認為，的解是和這組解很相近的。表七 旅行天數k=1時的近似解30313233343536377.347.146.986.766.546.366.185.9638394041424344455.745.685.465.365.145.024.864.746474849505152534.564.454.344.24.093.983.793.66545556575859603.63.523.463.373.293.223.163.行進中的碰撞次數1仍然以流體模型來計算碰撞次數。此時假定流體分為兩層，上層為機動帆船層，下層為橡膠筏。兩層密度分別為： (26) (27

18、)每日平均行進路程 (28)又 (29)從第二步中我們可以得到 (30)由以上三式可以得到 (31)碰撞次數的計算 (32)這得到的是碰撞次數與露營地個數的關系式，代入數據，得到與的關系如下表：表八 碰撞次數C與露營地個數的對應關系30313233343536371.561.741.982.172.242.382.522.6438394041424344452.822.963.093.323。463.613.823.9646474849505152534.164.344.584.764.985.185.365.62545556575859605.946.266.486.767.027.267.

19、624. 確定與的值 確定和值的限定條件碰撞次數小于3 (33)能夠在5小時內找到一處空露營地 (34)露營地個數在30到60之間 (35)旅行隊數為正整數 (36)綜上所述，規劃模型為：5.1.2 模型一的求解根據建立的模型，由遺傳算法進行求解：（1） 首先設定若干組具體的船只調度時刻表；（2） 作河流承載能力的適值函數；（3） 將時刻表代入模型中，選擇河流承載能力較大的可行解進行交叉，變換；（4） 重復進行數次后，所得的解應趨于穩定，此時變為所求的最優解；求解結果：河流的最大承載能力，對應露營點數。進一步得到露營點的間距英里，也是比較符合現實情況的。即河流的最大承載能力為1206只船，總共

20、有48個露營點。5.2 模型二的建立與求解排程方案模型：對于每一隊游客，我們就可以依照他們可到達的露營點被占據概率的大小給出建議休息點的位置。在第一個模型中我們已經得到了在允許漂流的6個月內可以旅行的總的旅行隊數和露營地的各個數，得到平均每天的旅行隊數：由于第一天之前是沒有旅行隊在露營點的，所以第一天安排6個旅行隊進行旅行，下面我們根據模型一給出出發的各個旅行隊的類型：首先選擇機動帆船的旅行隊的個數：這里取;選擇橡膠筏的旅行隊個數：這里取；從上面可以看到，管理者平均每天需要安排5艘機動帆船和一艘橡膠筏。根據模型一得求解可知某一天發船的時刻表如下：發船時刻表時間機動帆船橡皮筏8：00：00-9：

21、00AM2010：00：00-11：00AM1114：00：00-15：00PM1017：00：00-18：00PM10綜上可知，我們已經得出了每天發船的時刻表，并求得河流在這6個月中最大的承載能力為1206艘船，每天總發船六艘，其中機動帆船5艘，橡膠筏1艘。5.3模型三的建立與求解河流的容納量模型河流的容納量是指一天中河流最多進行旅行的旅行隊的個數。由于河流上的個數已經確定為48個，容易理解，當一天中的所有露營點都被占據時，河流的容納量就已經達到了極限，即A=Y。六、 模型驗證模型二和模型三都是在模型一的基礎上進行的，為了驗證模型的正確性，我們對模型一進行檢驗。由于被占用的露營地個數是不會變

22、得，這里只對進行檢驗。考慮到第一種特殊的極端情況，所有的旅行隊都選擇摩托船，并且都在和上度過6個晚上后到達終點，并且每天發船次數一樣，成為典型的的相逐問題，這樣，可以求得一個最大的旅行隊的數量： (43)考慮到第二種特殊的極端情況，所有的旅行隊都選擇槳船，并且都在和上度過18個晚上后到達終點，同樣每天發船次數一樣，這樣，可以求得一個最小的旅行隊的數量： (44)我們發現，本模型得出的結果比最少情況的旅行隊數量有很大的增加，同時比較接近最大的旅行隊數量，主觀認為是本模型得出的結果是合理的。下面的說明可以進一步驗證本模型的正確性：在模型中我們給出摩托船和槳船的所占所有船的比例分別是：0.8和0.2.這里我們對上面的和進行簡單的線性加權： （45） 可以更直觀發現，模型