數(shù)學(xué)建模商人過河__論文

1、組長：王鵬道 110714組員：任利偉110713、孫祎110706小組成員負(fù)責(zé)情況：王鵬道：選擇論文題目、設(shè)計(jì)論文版面字體、分配成員任務(wù)、總結(jié)任利偉：一、問題提出、關(guān)鍵、分析。二、模型假設(shè)、三、模型建立孫祎：四、模型求解、五、模型的檢驗(yàn)、拓展及延伸2014年11月24日摘 要為了求解3個(gè)商人和3個(gè)隨從的過河問題，用數(shù)學(xué)分析方法，建立數(shù)學(xué)模型，并且加以求解，展示動(dòng)態(tài)規(guī)劃思想的應(yīng)用步驟。最后利用計(jì)算機(jī)蝙程進(jìn)行求解，獲得過河問題的完整求解過程；有效地求解類似多步?jīng)Q策問題的作用。關(guān)鍵詞：多步?jīng)Q策 計(jì)算機(jī)求解 狀態(tài)轉(zhuǎn)移律 圖解法一、 問題的提出隨從們密約, 在河的任一岸, 一旦隨從的人數(shù)比商人多, 就

2、殺人越貨，但是乘船渡河的方案由商人決定.商人們?cè)鯓硬拍馨踩^河?二、 問題的關(guān)鍵解決的關(guān)鍵集中在商人和隨從的數(shù)量上，以及小船的容量上，該問題就是考慮過河步驟的安排和數(shù)量上。各個(gè)步驟對(duì)應(yīng)的狀態(tài)及決策的表示法也是關(guān)鍵。三、 問題的分析在安全的前提下(兩岸的隨從數(shù)不比商人多),經(jīng)有限步使全體人員過河。由于船上人數(shù)限制，這需要多步?jīng)Q策過程，必須考慮每一步船上的人員。動(dòng)態(tài)規(guī)劃法正是求解多步?jīng)Q策的有效方法。它要求把解的問題一層一層地分解成一級(jí)一級(jí)、規(guī)模逐步縮小的子問題。直到可以直接求出其解的子問題為止。分解成所有子問題按層次關(guān)系構(gòu)成一棵子問題樹樹根是原問題。原問題的解依賴于子問題樹中所有子問題的解。四、

3、模型假設(shè)記第k次過河前A岸的商人數(shù)為XK，隨從數(shù)為YK k=1，2，XK ,YK=0，1，2，3，將二維向量SK=(XK，YK)定義為狀態(tài)把滿足安全渡河條件下的狀態(tài)集合稱為允許狀態(tài)集合。記作S。則S=(XK ,YK)|(XK =0,YK =0,1,2,3),(XK =3,YK =0,1,2,3),(XK =YK =1)(XK =YK =2)記第k次過河船上的商人數(shù)為UK隨從數(shù)為VK將二維向量DK=(UK ,VK)定義為決策由小船的容量可知允許決策集合（記作D)為D=(UK ,VK)|UK +VK=l,2=(O,1);(O,2);(1,O);(1,1);(2,O)五、 模型建立：動(dòng)態(tài)規(guī)劃法正是求

4、解多步?jīng)Q策的有效方法。它要求把解的問題一層一層地分解成一級(jí)一級(jí)、規(guī)模逐步縮小的子問題。直到可以直接求出其解的子問題為止。分解成所有子問題按層次關(guān)系構(gòu)成一棵子問題樹樹根是原問題。原問題的解依賴于子問題樹中所有子問題的解。用動(dòng)態(tài)規(guī)劃法分析三名商人的過河問題?？傻萌缦碌倪f歸樹：K=1A(3,2)B(0,1)A(3,2)B(0.1)K=2A（3,1）B(0,2)(0,1)A（2,2）B(1,1)（0，2）A(3,0)B(0,3)(1,1)(2,0)（3,3）（1,1）(1,0)相同情況K=3(0,2)A(3,1)B(0,2)K=4K=5(0,1)(2,0)A(1,1)B(2,2)K=6A(2,2)B(

5、1,1)K=7=A(0,2)B(3,1)K=8(0,1)A(0,3)B(3,0)K=9(0,2)A(0,1)B(3,2)A(1,1)B(2,2)A(0,2)B(3,1)(1,0)(0,1)A(0,0)B(3,3)K=10K=11（注解：當(dāng)K為奇數(shù)時(shí)，船在B岸；當(dāng)K為偶數(shù)時(shí)，船在A岸。）通過分析該遞歸樹，知道求解關(guān)鍵在于正確地寫出基本的狀態(tài)轉(zhuǎn)移關(guān)系式和恰當(dāng)?shù)倪吔鐥l件。因?yàn)閗為奇數(shù)時(shí)，船是從A岸駛向B岸，k為偶數(shù)時(shí)。船是由B岸駛回A岸。所以狀態(tài)SK隨決策DK變化的規(guī)律是SK+1=SK+(-1)K DK，k=l，2，稱之為狀態(tài)轉(zhuǎn)移律，這樣，制定過河方案就歸結(jié)為如下的多步?jīng)Q策問題：每一步，船由A岸駛向

6、B岸或B岸駛回A岸，都要對(duì)船上的人員(商人UK，隨從VK各幾人)作出決策，在保證安全的前提下即兩岸的商人數(shù)XK都不比隨從數(shù)YK少，用有限步使人員全部過河用狀態(tài)(變量)SK表示某一岸的人員狀況，決策(變量)DK表示船上的人員狀況，可以找出狀態(tài)SK隨決策DK變化的規(guī)律這樣安全過河問題就轉(zhuǎn)化為：求決策DKD(k=1,2，n)，使得狀態(tài)SKS，按照狀態(tài)轉(zhuǎn)移律，由初始狀態(tài)S1=(3，3)，經(jīng)有限步n到達(dá)狀態(tài)SK+1=(O,O)。SK+1=SK+(-1)KDK，k=l,2，3，其中DK D=(UK ,VK)|UK +VK=l，2，其中SK (XK ,YK)|(XK=0，YK =1，2，3)；(XK =3，

7、YK=0,1,2,3);(XK =YK =1,2),Sn+1 =(0,0)這就是三個(gè)商人的過河問題模型。六、 模型求解：a) 窮舉法：先建立編程的基本過程，然后考慮模型，再編寫程序b) 然后就可以得出結(jié)果了 開始變量賦值初始化判斷是否完全過河選擇一種可行方案，進(jìn)行過河或返回，得到新的狀態(tài)否判斷是不是允許狀態(tài)集合中的狀態(tài)，并且還沒在已經(jīng)考慮的狀態(tài) 中是否還有其他狀態(tài)否結(jié)束是是是主程序流程圖c) 圖解法：狀態(tài)s=(x,y) 16個(gè)格點(diǎn) 允許狀態(tài) 10個(gè)點(diǎn) 允許決策 移動(dòng)1或2格; k奇,左下移;右下移xy3322110S1sn+1d1d11總共需要11步七、模型的檢驗(yàn) 用2名商人和2名隨從的過河問

8、題的解決思路，檢驗(yàn)3名商人和3名隨從的過河問題。八、 模型的拓展和延伸通過三名商人和三名隨從的過河問題的解決方案，可以進(jìn)一步計(jì)算四名商人和四名隨從的過河問題，通過計(jì)算機(jī)編程可以設(shè)計(jì)m名商人和n名隨從的過河問題。這需要用多步?jīng)Q策九、總結(jié) 這是通過數(shù)學(xué)分析的方法解決實(shí)用問題，經(jīng)過問題提出、問題假設(shè)、問題分析、模型建立、模型求解、模型檢驗(yàn)的過程，解決商人過河問題。然后擴(kuò)展延伸到n個(gè)商人的問題。 學(xué)習(xí)數(shù)學(xué)建模以來，重新認(rèn)識(shí)了學(xué)習(xí)數(shù)學(xué)的樂趣，也重新認(rèn)識(shí)了數(shù)學(xué)，本以為數(shù)學(xué)是單調(diào)的，枯燥的，學(xué)習(xí)了之后，發(fā)現(xiàn)數(shù)學(xué)是普遍存在我們生活之中的。解決現(xiàn)實(shí)中的問題，很多都需要數(shù)學(xué)。沉浸在數(shù)學(xué)的世界里，發(fā)現(xiàn)學(xué)習(xí)是有趣的；相比于機(jī)械的認(rèn)識(shí)各個(gè)組織器