商人過(guò)河優(yōu)化模型

1、2011高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽承諾書(shū)我們仔細(xì)閱讀了中國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽的競(jìng)賽規(guī)則.我們完全明白，在競(jìng)賽開(kāi)始后參賽隊(duì)員不能以任何方式（包括電話、電子郵 件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問(wèn) 題。我們知道，抄襲別人的成果是違反競(jìng)賽規(guī)則的，如果引用別人的成果或其他 公開(kāi)的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正 文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競(jìng)賽規(guī)則，以保證競(jìng)賽的公正、公平性。如有違反 競(jìng)賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們參賽選擇的題號(hào)是（從A/B/C/D中選擇一項(xiàng)填寫(xiě)）：B我們的參賽報(bào)名號(hào)為（如果賽區(qū)設(shè)置

2、報(bào)名號(hào)的話）：所屬學(xué)校（請(qǐng)?zhí)顚?xiě)完整的全名）：西京學(xué)院參賽隊(duì)員（打印并簽名）：1.鄒高永張大偉錢(qián)曉東指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人（打印并簽名）：日期：年 月 日2011高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽編號(hào)專用頁(yè)賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）:賽區(qū)評(píng)閱記錄（可供賽區(qū)評(píng)閱時(shí)使用）：評(píng)閱人評(píng)分備注全國(guó)統(tǒng)一編號(hào)（由賽區(qū)組委會(huì)送交全國(guó)前編號(hào)）：全國(guó)評(píng)閱編號(hào)（由全國(guó)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：商人過(guò)河摘要本文針對(duì)商人安全渡河的問(wèn)題，采用多步?jīng)Q策的過(guò)程建立數(shù)學(xué)模型，求解得 到了在隨從沒(méi)有殺人越貨的情況下的渡河方案。對(duì)于本題而言，在3名商人、3名隨從、船的最大容量為2的情況下，首先 定義了渡河前此岸的狀態(tài)，

3、并設(shè)安全渡河條件下的狀態(tài)集定義為允許狀態(tài)集合， 接著得到渡河方案的允許決策集合，然后得到狀態(tài)隨渡河方案變化的規(guī)律，最后 利用平面坐標(biāo)分析法，并利用計(jì)算機(jī)進(jìn)行了仿真，得到了一種商人安全渡河的方 案。但是，本文不僅僅是為了拼湊出一個(gè)可行方案，而是希望能找到求解這類 問(wèn)題的規(guī)律性，并建立數(shù)學(xué)模型，用以解決更為廣泛的問(wèn)題?；诖四康?，利用 了 dijkstra算法，得到最短路徑的最優(yōu)解。但同時(shí)由于該算法遍歷計(jì)算的節(jié)點(diǎn) 很多，所以效率低，而且當(dāng)有多個(gè)最短距離時(shí)，不能夠?qū)⑺蟹蠗l件的情況逐 一列出。最后，從這類問(wèn)題解得趣味性、合理性進(jìn)行了深入討論，得到了 “傳教士 與野蠻人渡河”，“印度夫妻渡河”等問(wèn)題

4、通用的模型，并將其進(jìn)行了推廣。這也 是本文的一大特色。關(guān)鍵詞渡河問(wèn)題狀態(tài)集合決策集合平面坐標(biāo)dijkstra算法1問(wèn)題重述三名商人各帶一個(gè)隨從乘船渡河，一只小船只能容納二人，由他們自己劃 行。隨從們密約，在河的任意一岸，一旦隨從的人數(shù)比商人多，就殺人越貨.但 是如何乘船渡河的大權(quán)掌握在商人們手中。商人們?cè)鯓硬拍馨踩珊幽?？同時(shí)， 推廣到四名商人帶四名隨從又如何？2問(wèn)題分析安全渡河問(wèn)題可以看成一個(gè)多步?jīng)Q策過(guò)程。每一步，即船由此岸駛向彼岸或 從彼岸駛回此岸，都要對(duì)船上的人員（商人隨從各幾人）作出決策，在保證安全的 前提下（兩岸的商人數(shù)都不比隨從數(shù)少），在有限步內(nèi)使人員全部過(guò)河。用狀態(tài)（變 量）表示

5、某一岸的人員狀況，決策（變量）表示船上的人員狀況，可以找出狀態(tài)隨決 策變化的規(guī)律。問(wèn)題轉(zhuǎn)化為在狀態(tài)的允許變化范圍內(nèi)（即安全渡河條件），確定每 一步的決策，達(dá)到渡河的目的。此類智力問(wèn)題經(jīng)過(guò)思考，可以拼湊出一個(gè)可行方案。但是，我們現(xiàn)在希望能 找到求解這類問(wèn)題的規(guī)律性，并建立數(shù)學(xué)模型，用以解決更為廣泛的問(wèn)題。3模型假設(shè)及符號(hào)說(shuō)明3.1模型假設(shè)（1）每個(gè)商人和隨從都會(huì)劃船；（2）只有一條船，且每條船上最多只能乘坐兩個(gè)人；（3）所有商人與隨從之間沒(méi)有矛盾，不會(huì)出現(xiàn)兩人不愿意坐一條船的現(xiàn)象；（4）船在渡河的過(guò)程中不受外界環(huán)境的影響。3.2符號(hào)說(shuō)明A 初始狀態(tài)下，商人和隨從所在的一岸；B初始狀態(tài)下，商人和隨

6、從欲到達(dá)的一岸；七第k次渡河前，A岸的商人數(shù)；七 第k次渡河前，A岸的隨從數(shù)；Sk渡河前A岸商人與隨從數(shù)的狀態(tài)；S渡河前A岸商人與隨從數(shù)的允許狀態(tài)的集合；七 第k次渡河時(shí)，船上的乘坐商人數(shù)；匕第k次渡河時(shí)，船上的乘坐隨從數(shù)；dk第k次渡河方案的決策；D渡河方案的允許決策集合Dk第k次狀態(tài)的轉(zhuǎn)移4模型的建立與求解4.1模型的建立根據(jù)題意，可以作出商人渡河初始狀態(tài)的示意圖:渡河（選擇A岸為參考點(diǎn)）記第k次渡河前A岸的商人數(shù)為七，隨從數(shù)為yk, k = 1,2, ,m，且 七,yk= 0,1,2,3將二維向量，廣（氣,*）定義為狀態(tài)，安全渡河條件下的狀態(tài)集定義為允許 狀態(tài)集合，記為S，因此有：S =

7、 （x,y）I x = 0,3; y = 0, 1, 2, 3 或x = 1;y = 0, 1 或x = 2;y = 0, 1,2（ 1）記第k次渡河時(shí)，船上的乘坐商人數(shù)為七，隨從數(shù)為匕，將二維向量dk =（七,匕）定義為第k次渡河方案的決策，渡河方案的允許決策集合記為D 根據(jù)題意可知，船的容量是一定的，因此，得D = （u, v） I u+v = 1,2 （2）因?yàn)楫?dāng)k = 2n-1時(shí)，船由A岸駛向B岸；當(dāng)k = 2n時(shí)，船由B岸駛向A岸。所以狀態(tài)S隨著d的變化的規(guī)律為： kkSki= Sk +(-1)kdk(3)這樣，制定安全渡河方案歸結(jié)為如下的多步?jīng)Q策問(wèn)題：即：求決策dk e D(k =

8、 1,2, ,m)，使?fàn)顟B(tài)Sk e S。按照轉(zhuǎn)移規(guī)律，由初始狀態(tài) S =(3,3)經(jīng)有限m步后到達(dá)狀態(tài)S +1 = (0,0)。4.2模型的求解根據(jù)(1)(2)(3)式，通過(guò)利用matlab編寫(xiě)一段程序來(lái)求解多步?jīng)Q策問(wèn) 題是可行的，但是當(dāng)商人和隨從數(shù)都不多的情況下還可以用平面坐標(biāo)法解此模型 更為方便。接下來(lái)，我們先用平面坐標(biāo)法求解此模型，最后再使用計(jì)算機(jī)仿真， 對(duì)求解的結(jié)果進(jìn)行驗(yàn)證，并給予推廣。4.2.1平面坐標(biāo)法設(shè)x為商人數(shù)，y為隨從數(shù)。在功y平面坐標(biāo)系上作分析。先標(biāo)出此案的安 全狀態(tài)點(diǎn)。起始點(diǎn)-(3,3)；最終點(diǎn)-(0,0)即模型求解就是探求從狀態(tài)(3,3)經(jīng)過(guò)有限次轉(zhuǎn)移之后到達(dá)狀態(tài)(0,

9、0)的方案。設(shè)Dk為第k次狀態(tài)的轉(zhuǎn)移，當(dāng)k = 2n -1時(shí)，船由A岸駛向B岸，此時(shí)x, y只能減少， 不能增加。故坐標(biāo)點(diǎn)只能向左下方移動(dòng)。由于受船的容量的限制，x + y至多減 少2，即至多只能向左下方移動(dòng)兩格。如下圖所示：從圖中可以看出，在這種渡河方案中，時(shí)刻都能夠確?！皟砂栋踩?，不會(huì) 出現(xiàn)隨從們“殺人越貨”。4.2.2計(jì)算機(jī)仿真通過(guò)利用matlab編寫(xiě)一段程序來(lái)求解這種多步?jīng)Q策問(wèn)題見(jiàn)附件:程序一， 當(dāng)我們將商人數(shù)與隨從數(shù)以及船的容量按照題意輸入時(shí)，便會(huì)得到商人們的渡河 方案如下：表1 4種可供商人選擇的不同渡河方案瓦案 狀態(tài)方案一方案一方案三方案四（M，N）表示A 岸現(xiàn)在有M個(gè) 商人，

10、N個(gè)隨從(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)檢驗(yàn)，結(jié)果與使用平面坐標(biāo)法得到的結(jié)果完全一致。通過(guò)計(jì)算機(jī)仿真，當(dāng)題目中給定出任意數(shù)量的商人，隨從，以及規(guī)定出任

11、 意船的容量，都可以判斷出“商人們能否安全渡河？ ”以及解決“如果能，那么 安全渡河的方案是什么？”的問(wèn)題。從而使這個(gè)模型更具有一定的推廣價(jià)值。5模型的評(píng)價(jià)與改進(jìn)5.1模型的評(píng)價(jià)5.1.1模型的優(yōu)點(diǎn)（1）采用了較為成熟的數(shù)學(xué)理論建立模型，可行度比較高；（2）在討論商人安全渡河的方案時(shí)，運(yùn)用了圖表，比較直觀；（3）模型的求解運(yùn)用了強(qiáng)大的matlab軟件，結(jié)果可信度高，便于推廣；（4）通過(guò)matlab程序，能判斷出“當(dāng)任意個(gè)商人、任意個(gè)隨從、船的容量任意 時(shí)，商人能否安全渡河？”及解決了“如果能，那么渡河方案又是什么？”的問(wèn) 題，使得所建模型更加全面。5.1.2模型的缺點(diǎn)利用平面坐標(biāo)法求解該模型時(shí)

12、，出現(xiàn)了明顯的遺漏，考慮的不夠全面；沒(méi)有找到商人數(shù)、隨從數(shù)及船的容量之間的數(shù)量關(guān)系；沒(méi)有考慮到實(shí)際生活中，在安全渡河的前提下，商人過(guò)河的優(yōu)先級(jí)應(yīng)高于 隨從。5.2模型的改進(jìn)基于以上求解模型用到的方法，我們明顯意識(shí)到了結(jié)果考慮到的不夠全面。 為此，我們利用dijkstra算法，通過(guò)相應(yīng)程序求解前面模型見(jiàn)附件：程序二， 得到最短路徑的最優(yōu)解。但同時(shí)由于該算法遍歷計(jì)算的節(jié)點(diǎn)很多，所以效率低。 而且當(dāng)有多個(gè)最短距離時(shí)，不能夠?qū)⑺蟹蠗l件的情況逐一列出。綜合以上的努力，我們與致力于研究出一套方案：即給出任意個(gè)商人與任 意個(gè)隨從以及船的容量任意的時(shí)候，都可以給出安全渡河的方案；并且在給出商 人數(shù)、隨從數(shù)

13、、船的容量中任意兩者，并要使其能夠安全渡河情況下的第三者的 取值范圍，以及得到最優(yōu)的渡河方案。由于水平有限，我們只能提出這個(gè)美好的想法，用某種方法能把在所有安 全狀態(tài)集合和決策集合中，搜索出所有可能的解，從而從其中找出最優(yōu)的解。6模型的推廣“商人渡河”模型適合于解決很多問(wèn)題，如“傳教士與野蠻人渡河”， “印度夫妻渡河”等。這些問(wèn)題本質(zhì)上都是相同或相似的，由此可見(jiàn)這個(gè)趣 味問(wèn)題流傳的廣泛性。另外還有所謂“人狗雞米過(guò)河”問(wèn)題，也是頗有趣味 的，人、狗、雞、米均要過(guò)河，船需人劃，而船上至多還可載一物，但若人 不在時(shí)，狗會(huì)吃雞，雞會(huì)吃米，問(wèn)如何設(shè)計(jì)安全過(guò)河方案。我們完全可以仿 照商人渡河問(wèn)題建立一個(gè)多步?jīng)Q策模型，將上述算法稍作修改，就可以得到 它的解。這里就不再贅述了。另外，用一定容積的若干油瓶倒出一定量的油 的問(wèn)題也屬此類問(wèn)題。7參考文獻(xiàn)1數(shù)學(xué)建模