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

2、貨，但是乘船渡河的方案由商人決定.商人們怎樣才能安全過河?問題的關鍵解決的關鍵集中在商人和隨從的數量上，以及小船的容量上，該問題就是考慮過河步驟的安排和數量上。各個步驟對應的狀態及決策的表示法也是關鍵。三、 問題的分析在安全的前提下(兩岸的隨從數不比商人多),經有限步使全體人員過河。由于船上人數限制，這需要多步決策過程，必須考慮每一步船上的人員。動態規劃法正是求解多步決策的有效方法。它要求把解的問題一層一層地分解成一級一級、規模逐步縮小的子問題。直到可以直接求出其解的子問題為止。分解成所有子問題按層次關系構成一棵子問題樹樹根是原問題。原問題的解依賴于子問題樹中所有子問題的解。四、 模型假設記第

3、k次過河前A岸的商人數為XK，隨從數為YK k=1，2，XK ,YK=0，1，2，3，將二維向量SK=(XK，YK)定義為狀態把滿足安全渡河條件下的狀態集合稱為允許狀態集合。記作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次過河船上的商人數為UK隨從數為VK將二維向量DK=(UK ,VK)定義為決策由小船的容量可知允許決策集合（記作D)為D=(UK ,VK)|UK +VK=l,2=(O,1);(O,2);(1,O);(1,1);(2,O) 模型建立：動態規劃法正是求解多步決策的有效

4、方法。它要求把解的問題一層一層地分解成一級一級、規模逐步縮小的子問題。直到可以直接求出其解的子問題為止。分解成所有子問題按層次關系構成一棵子問題樹樹根是原問題。原問題的解依賴于子問題樹中所有子問題的解。用動態規劃法分析三名商人的過河問題。可得如下的遞歸樹：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(1,1)K=7=

5、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（注解：當K為奇數時，船在B岸；當K為偶數時，船在A岸。）通過分析該遞歸樹，知道求解關鍵在于正確地寫出基本的狀態轉移關系式和恰當的邊界條件。因為k為奇數時，船是從A岸駛向B岸，k為偶數時。船是由B岸駛回A岸。所以狀態SK隨決策DK變化的規律是SK+1=SK+(-1)K DK，k=l，2，稱之為狀態轉移律，這樣，制定過河方案就歸結為如下的多步決策問題：每一步，船由A岸駛向B岸或B岸駛回A

6、岸，都要對船上的人員(商人UK，隨從VK各幾人)作出決策，在保證安全的前提下即兩岸的商人數XK都不比隨從數YK少，用有限步使人員全部過河用狀態(變量)SK表示某一岸的人員狀況，決策(變量)DK表示船上的人員狀況，可以找出狀態SK隨決策DK變化的規律這樣安全過河問題就轉化為：求決策DKD(k=1,2，n)，使得狀態SKS，按照狀態轉移律，由初始狀態S1=(3，3)，經有限步n到達狀態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，YK=0,1,2

7、,3);(XK =YK =1,2),Sn+1 =(0,0)這就是三個商人的過河問題模型。 模型求解：窮舉法：先建立編程的基本過程，然后考慮模型，再編寫程序然后就可以得出結果了 開始變量賦值初始化判斷是否完全過河選擇一種可行方案，進行過河或返回，得到新的狀態否判斷是不是允許狀態集合中的狀態，并且還沒在已經考慮的狀態 中是否還有其他狀態否結束是是是主程序流程圖圖解法：狀態s=(x,y) 16個格點 允許狀態 10個點 允許決策 移動1或2格; k奇,左下移;右下移xy3322110S1sn+1d1d11總共需要11步七、模型的檢驗 用2名商人和2名隨從的過河問題的解決思路，檢驗3名商人和3名隨從的過河問題。八、 模型的拓展和延伸通過三名商人和三名隨從的過河問題的解決方案，可以進一步計算四名商人和四名隨從的過河問題，通過計算機編程可以設計m名商人和n名隨從的過河問題。這需要用多步決策九、總結 這是通過數學分析的方法解決實用問題，經過問題提出、問題假設、問題分析、模型建立、模型求解、模型檢驗的過程，解決商人過河問題。然后擴展延伸到n個商人的問題。 學習數學建模以來，重新認識了學習數學的樂趣，也重新認識了數學，本以為數學是單調的，枯燥的，學習了之后，發現數學是普遍存在我們生活之中的。解決現實中的問題，很多都需要數學。沉浸在數學的世界里，發現學習是有趣的；相比于機械的認識各