商人過河優(yōu)化模型.doc

2012高教社杯全國大學(xué)生數(shù)學(xué)建模競賽承 諾 書我們仔細(xì)閱讀了中國大學(xué)生數(shù)學(xué)建模競賽的競賽規(guī)則.我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們參賽選擇的題號是（從A/B/C/D中選擇一項填寫）： A 我們的參賽報名號為（如果賽區(qū)設(shè)置報名號的話）： J2202 所屬學(xué)校（請?zhí)顚懲暾娜?江西環(huán)境工程職業(yè)學(xué)院 參賽隊員 (打印并簽名) ：1. 羅妮娜 2. 肖思彥 3. 熊明遠(yuǎn) 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人 (打印并簽名)： 教練組 日期： 2012 年 8月 9日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進(jìn)行編號）：2012高教社杯全國大學(xué)生數(shù)學(xué)建模競賽編 號 專 用 頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進(jìn)行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）：評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：全國評閱編號（由全國組委會評閱前進(jìn)行編號）：商人過河摘要本文針對商人安全渡河的問題，采用多步?jīng)Q策的過程建立數(shù)學(xué)模型，求解得到了在隨從沒有殺人越貨的情況下的渡河方案。對于本題而言，在3名商人、3名隨從、船的最大容量為2的情況下，首先定義了渡河前此岸的狀態(tài)，并設(shè)安全渡河條件下的狀態(tài)集定義為允許狀態(tài)集合，接著得到渡河方案的允許決策集合，然后得到狀態(tài)隨渡河方案變化的規(guī)律，最后利用平面坐標(biāo)分析法，并利用計算機(jī)進(jìn)行了仿真，得到了一種商人安全渡河的方案。但是，本文不僅僅是為了拼湊出一個可行方案，而是希望能找到求解這類問題的規(guī)律性，并建立數(shù)學(xué)模型，用以解決更為廣泛的問題?；诖四康模昧怂惴?，得到最短路徑的最優(yōu)解。但同時由于該算法遍歷計算的節(jié)點很多，所以效率低，而且當(dāng)有多個最短距離時，不能夠?qū)⑺蟹蠗l件的情況逐一列出。 最后，從這類問題解得趣味性、合理性進(jìn)行了深入討論，得到了“傳教士與野蠻人渡河”，“印度夫妻渡河”等問題通用的模型，并將其進(jìn)行了推廣。這也是本文的一大特色。關(guān)鍵詞 渡河問題 狀態(tài)集合 決策集合 平面坐標(biāo) 算法 一 、問題的提出三名商人各帶一個隨從乘船渡河，一只小船只能容納二人，由他們自己劃行。隨從們密約，在河的任意一岸，一旦隨從的人數(shù)比商人多，就殺人越貨但是如何乘船渡河的大權(quán)掌握在商人們手中。商人們怎樣才能安全渡河呢？同時，推廣到四名商人帶四名隨從又如何？二、問題分析安全渡河問題可以看成一個多步?jīng)Q策過程。每一步，即船由此岸駛向彼岸或從彼岸駛回此岸，都要對船上的人員(商人隨從各幾人)作出決策，在保證安全的前提下(兩岸的商人數(shù)都不比隨從數(shù)少)，在有限步內(nèi)使人員全部過河。用狀態(tài)(變量)表示某一岸的人員狀況，決策(變量)表示船上的人員狀況，可以找出狀態(tài)隨決策變化的規(guī)律。問題轉(zhuǎn)化為在狀態(tài)的允許變化范圍內(nèi)(即安全渡河條件)，確定每一步的決策，達(dá)到渡河的目的。此類智力問題經(jīng)過思考，可以拼湊出一個可行方案。但是，我們現(xiàn)在希望能找到求解這類問題的規(guī)律性，并建立數(shù)學(xué)模型，用以解決更為廣泛的問題。三、 模型假設(shè)及符號說明3.1 模型假設(shè)（1）每個商人和隨從都會劃船；（2）只有一條船，且每條船上最多只能乘坐兩個人；（3）所有商人與隨從之間沒有矛盾，不會出現(xiàn)兩人不愿意坐一條船的現(xiàn)象；（4）船在渡河的過程中不受外界環(huán)境的影響。3.2 符號說明 初始狀態(tài)下，商人和隨從所在的一岸； 初始狀態(tài)下，商人和隨從欲到達(dá)的一岸； 第次渡河前，岸的商人數(shù)； 第次渡河前，岸的隨從數(shù)； 渡河前岸商人與隨從數(shù)的狀態(tài)； 渡河前岸商人與隨從數(shù)的允許狀態(tài)的集合； 第次渡河時，船上的乘坐商人數(shù)； 第次渡河時，船上的乘坐隨從數(shù)； 第次渡河方案的決策； 渡河方案的允許決策集合 第次狀態(tài)的轉(zhuǎn)移四、 模型的建立與求解4.1 模型的建立根據(jù)題意，可以作出商人渡河初始狀態(tài)的示意圖：AB渡河目的：（選擇岸為參考點）記第次渡河前岸的商人數(shù)為，隨從數(shù)為，且將二維向量定義為狀態(tài)，安全渡河條件下的狀態(tài)集定義為允許狀態(tài)集合，記為，因此有： （1）記第次渡河時，船上的乘坐商人數(shù)為，隨從數(shù)為，將二維向量定義為第次渡河方案的決策，渡河方案的允許決策集合記為根據(jù)題意可知，船的容量是一定的，因此，得 （2）因為當(dāng)時，船由岸駛向岸；當(dāng)時，船由岸駛向岸。所以狀態(tài)隨著的變化的規(guī)律為： （3）這樣，制定安全渡河方案歸結(jié)為如下的多步?jīng)Q策問題：即：求決策，使?fàn)顟B(tài)。按照轉(zhuǎn)移規(guī)律，由初始狀態(tài)經(jīng)有限步后到達(dá)狀態(tài)。4.2 模型的求解根據(jù)（1）（2）（3）式，通過利用matlab編寫一段程序來求解多步?jīng)Q策問題是可行的，但是當(dāng)商人和隨從數(shù)都不多的情況下還可以用平面坐標(biāo)法解此模型更為方便。接下來，我們先用平面坐標(biāo)法求解此模型，最后再使用計算機(jī)仿真，對求解的結(jié)果進(jìn)行驗證，并給予推廣。4.2.1 平面坐標(biāo)法設(shè)為商人數(shù)，為隨從數(shù)。在平面坐標(biāo)系上作分析。先標(biāo)出此案的安全狀態(tài)點。起始點-；最終點-即模型求解就是探求從狀態(tài)經(jīng)過有限次轉(zhuǎn)移之后到達(dá)狀態(tài)的方案。設(shè)為第次狀態(tài)的轉(zhuǎn)移，當(dāng)時，船由岸駛向岸，此時只能減少，不能增加。故坐標(biāo)點只能向左下方移動。由于受船的容量的限制，至多減少2，即至多只能向左下方移動兩格。如下圖所示：2X 商人Y仆人13123 如圖1.3商仆過河的示意圖 從圖中可以看出，在這種渡河方案中，時刻都能夠確?！皟砂栋踩保粫霈F(xiàn)隨從們“殺人越貨”。4.2.2 計算機(jī)仿真通過利用matlab編寫一段程序來求解這種多步?jīng)Q策問題見附件：程序一，當(dāng)我們將商人數(shù)與隨從數(shù)以及船的容量按照題意輸入時，便會得到商人們的渡河方案如下：表 1 4種可供商人選擇的不同渡河方案方案狀態(tài)方案一方案二方案三方案四（，）表示岸現(xiàn)在有個商人，個隨從（3,3）（3,3）（3,3）（3,3）（2,2）（3,1）（2,2）（3,1）（3,2）（3,2）（3,2）（3,2）（3,0）（3,0）（3,0）（3,0）（3,1）（3,1）（3,1）（3,1）（1,1）（1,1）（1,1）（1,1）（2,2）（2,2）（2,2）（2,2）（0,2）（0,2）（0,2）（0,2）（0,3）（0,3）（0,3）（0,3）（0,1）（0,1）（0,1）（0,1）（0,2）（0,2）（1,1）（1,1）（0,0）（0,0）（0,0）（0,0）經(jīng)檢驗，結(jié)果與使用平面坐標(biāo)法得到的結(jié)果完全一致。通過計算機(jī)仿真，當(dāng)題目中給定出任意數(shù)量的商人，隨從，以及規(guī)定出任意船的容量，都可以判斷出“商人們能否安全渡河？”以及解決“如果能，那么安全渡河的方案是什么？”的問題。從而使這個模型更具有一定的推廣價值。五、 模型的評價與改進(jìn)1.模型的評價（1） 模型的優(yōu)點:（1）采用了較為成熟的數(shù)學(xué)理論建立模型，可行度比較高；（2）在討論商人安全渡河的方案時，運(yùn)用了圖表，比較直觀；（3）模型的求解運(yùn)用了強(qiáng)大的matlab軟件，結(jié)果可信度高，便于推廣；（4）通過matlab程序，能判斷出“當(dāng)任意個商人任意個隨從船的容量 任意時，商人能否安全渡河？”及解決了“如果能，那么渡河方案又是什么？”的問題，使得所建模型更加全面。5.1.2 模型的缺點:（1）利用平面坐標(biāo)法求解該模型時，出現(xiàn)了明顯的遺漏，考慮的不夠全面；（2）沒有找到商人數(shù)隨從數(shù)及船的容量之間的數(shù)量關(guān)系；（3）沒有考慮到實際生活中，在安全渡河的前提下，商人過河的優(yōu)先級應(yīng)高于隨從。5.2 模型的改進(jìn)基于以上求解模型用到的方法，我們明顯意識到了結(jié)果考慮到的不夠全面。為此，我們利用dijkstra算法，通過相應(yīng)程序求解前面模型見附件：程序二，得到最短路徑的最優(yōu)解。但同時由于該算法遍歷計算的節(jié)點很多，所以效率低。而且當(dāng)有多個最短距離時，不能夠?qū)⑺蟹蠗l件的情況逐一列出。綜合以上的努力，我們與致力于研究出一套方案：即給出任意個商人與任意個隨從以及船的容量任意的時候，都可以給出安全渡河的方案；并且在給出商人數(shù)、隨從數(shù)、船的容量中任意兩者，并要使其能夠安全渡河情況下的第三者的取值范圍，以及得到最優(yōu)的渡河方案。由于水平有限，我們只能提出這個美好的想法，用某種方法能把在所有安全狀態(tài)集合和決策集合中，搜索出所有可能的解，從而從其中找出最優(yōu)的解。六、模型的推廣“商人渡河”模型適合于解決很多問題，如“傳教士與野蠻人渡河”，“印度夫妻渡河”等。這些問題本質(zhì)上都是相同或相似的，由此可見這個趣味問題流傳的廣泛性。另外還有所謂“人狗雞米過河”問題，也是頗有趣味的，人、狗、雞、米均要過河，船需人劃，而船上至多還可載一物，但若人不在時，狗會吃雞，雞會吃米，問如何設(shè)計