數(shù)學建模商人過河問題-論

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

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

3、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) 模型建立：動態(tài)規(guī)劃法正是求解多步?jīng)Q策的有效

4、方法。它要求把解的問題一層一層地分解成一級一級、規(guī)模逐步縮小的子問題。直到可以直接求出其解的子問題為止。分解成所有子問題按層次關(guān)系構(gòu)成一棵子問題樹樹根是原問題。原問題的解依賴于子問題樹中所有子問題的解。用動態(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(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為奇數(shù)時，船在B岸；當K為偶數(shù)時，船在A岸。）通過分析該遞歸樹，知道求解關(guān)鍵在于正確地寫出基本的狀態(tài)轉(zhuǎn)移關(guān)系式和恰當?shù)倪吔鐥l件。因為k為奇數(shù)時，船是從A岸駛向B岸，k為偶數(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岸駛向B岸或B岸駛回A

6、岸，都要對船上的人員(商人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到達狀態(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，YK=0,1,2

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