1、數學建模論文商仆過河問題作者：*學院 *班 * * *號2014年12月4日摘要：為了求解3個商人和3個隨從的過河問題，用數學分析方法，建立數學模型，并且加以求解，展示動態規劃思想的應用步驟。最后利用計算機編程進行求解，獲得過河問題的完整求解過程；有效地求解類似多步決策問題的作用。關鍵詞：多步決策 計算機求解 狀態轉移律 圖解法 MATLAB程序一、問題的提出S個商人各帶一個隨從乘船過河，一只小船只能容納K人，由他們自己劃船。商人們竊聽到隨從們密謀，在河的任意一岸上，只要隨從的人數比商人多，就殺掉商人。但是如何乘船渡河的決策權在商人手中，商人們如何安排渡河計劃確保自身安全？二、問題的關鍵解決的

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

3、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=A(0,2)B(3,1)K=8(0,1)（轉下頁）A(0,3)B(3

5、,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岸，都要對船上的人員(商人UK，隨從VK各幾人)作出決策，

6、在保證安全的前提下即兩岸的商人數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,3);(XK =YK =1,2),Sn+1 =

7、(0,0)這就是三個商人的過河問題模型。六、模型求解：窮舉法：計算機編程（見附）先建立編程的基本過程，然后考慮模型，再編寫程序。然后就可以得出結果了。 開始變量賦值初始化判斷是否完全過河選擇一種可行方案，進行過河或返回，得到新的狀態否判斷是不是允許狀態集合中的狀態，并且還沒在已經考慮的狀態中是否還有其他狀態否結束是是是主程序流程圖圖解法：狀態s=(x,y) 16個格點允許狀態 10個點允許決策 移動1或2格; k奇,左下移;k偶,右上移.xy3322110S1sn+1d1d11總共需要11步可以得出經過11步的渡河就能達到安全渡河的目標及滿足渡河的次數盡量少的條件。這11步的渡河方案就是上面程

8、序運行結果中船上下面的一列。八、 模型的檢驗用2名商人和2名隨從的過河問題的解決思路，檢驗3名商人和3名隨從的過河問題。九、 模型的拓展和延伸通過三名商人和三名隨從的過河問題的解決方案，可以進一步計算四名商人和四名隨從的過河問題，通過計算機編程可以設計m名商人和n名隨從的過河問題。十、總結這是通過數學分析的方法解決實用問題，經過問題提出、問題假設、問題分析、模型建立、模型求解、模型檢驗的過程，解決商人過河問題。然后擴展延伸到n個商人的問題。學習數學建模以來，重新認識了學習數學的樂趣，也重新認識了數學，本以為數學是單調的，枯燥的，學習了之后，發現數學是普遍存在我們生活之中的。解決現實中的問題，很

9、多都需要數學。沉浸在數學的世界里，發現學習是有趣的；相比于機械的認識各個組織器官，建立一個數學模型解決問題是十分有趣的。參考文獻：（1）傅清祥數據結構與算法王曉東北京：電子工業出版社 1998（2）姜啟瑟數學建模(第二版)北京：高等教育出版社，2000（3）運籌學教材編寫組運籌學(修訂版)北京：清華大學出版社。2001附：商仆過河的C程序及運行截屏:#include <iostream>using namespace std;struct Nodeint nMer;int nSer;int length;class Apublic:A();A();void Tspt();/過河的動

10、作void doLeft(int nhead,int ntail,int nlength);private:bool islegal(int nm,int ns); /判斷是否滿足約束條件，滿足為trueNode *funTspt(int nm,int ns,bool flag);/添加STEPhead可以向后延伸的節點bool noRepeat(int nm,int ns);/沒有重復返回TRUEvoid funshow(int a2,int ntail);bool funLeft(Node nd,int b1,int b2,int n);void show(int s,int p2,int

11、 &top,int &count,int a);int head;int tail;int n;/商仆的對數int nB;/船最多的載人數目Node *STEP;A:A()free(STEP);A:A()cout<<"請輸入商仆的對數S="F:cin>>n;if(n=1)nB=2; cout<<"船最多載人的數目K="<<nB;else if(n=2) cout<<"船最多載人的數目可以取:"for(int x=n;x<=2*n;x+)cout<&

12、lt;x<<"、"cout<<endl;cout<<"請輸入船最多載人的數目K=" cin>>nB;else if(n=3) cout<<"船最多載人的數目可以取:"for(int x=n-1;x<=2*n;x+)cout<<x<<"、" cout<<endl;cout<<"請輸入船最多載人的數目K=" cin>>nB;else if(n=4) cout<<&

13、quot;船最多載人的數目可以取:"for(int x=n-1;x<=2*n;x+)cout<<x<<"、" cout<<endl;cout<<"請輸入船最多載人的數目K=" cin>>nB;else if(n>=5&&n<=100) cout<<"船最多載人的數目可以取:"for(int x=4;x<=2*n;x+)cout<<x<<"、" cout<<en

14、dl;cout<<"請輸入船最多載人的數目K=" cin>>nB;else if(n<1|n>100) cout<<"本程序僅在S=(0100)以內保證其正確性"<<endl; cout<<"請重新輸入商仆的對數S="goto F;STEP = (Node *)malloc(sizeof(Node)*10000);memset(STEP,0,sizeof(Node)*10000);head = tail = 0;STEP0.nMer = STEP0.nSer =

15、n;int main() cout<<"問題描述： S個商人各帶一個隨從乘船過河，一只小船只能容納K人，由他們自己劃船。商人們竊聽到隨從們密謀，在河的任意一岸上，只要隨從的人數比商人多，就殺掉商人。但是如何乘船渡河的決策權在商人手中，商人們如何安排渡河計劃確保自身安全？"<<endl;A a;a.Tspt();return 0;void A:show(int s,int p2,int &top,int &count,int a)if(top = -1)return ;/已找到目標狀態需，輸出數據if(top = STEPhead.le

16、ngth)cout<<"* "<<+count<<" *"<<endl;funshow(p,top + 1);B:top-;if(top = -1)return ;C:stop-;if(STEP(stop).length != top)/退過了stop = atop;goto B;if(funLeft(STEP(stop),ptop - 10,ptop - 11,top - 1) = false)goto C;ptop0 = STEP(stop).nMer;ptop1 = STEP(stop).nSer;s

17、how(s,p,top,count,a);return ;/在中間加入節點STEP(stop + 1) if(funLeft(STEP(stop + 1),ptop0,ptop1,top) = true)/符合條件top+;ptop0 = STEP(stop).nMer;ptop1 = STEP(stop).nSer;show(s,p,top,count,a);return ;else/不符合條件E:stop + 1-;if(STEP(stop + 1).length = top)/退過了，到了下一層stop + 1 = atop + 1;D:stop-;if(STEP(stop).lengt

18、h != top)/退過了，到了下一層for(int i = top; i <= STEPhead.length; i+)si = ai;top-;if(top = -1)return ;goto D;if(top = 0)return ;if(funLeft(STEP(stop),ptop - 10,ptop - 11,top - 1) = false)goto D;ptop0 = STEP(stop).nMer;ptop1 = STEP(stop).nSer;show(s,p,top,count,a);return ;if(funLeft(STEP(stop + 1),ptop0,p

19、top1,top) = false)goto E;top+;ptop0 = STEP(stop).nMer;ptop1 = STEP(stop).nSer;show(s,p,top,count,a);void A:doLeft(int nhead,int ntail,int nlength)int a1000;int a11000;int sp10002;bool flag = false;memset(a,0xff,4000);memset(a1,0xff,4000);memset(sp,0xff,8000);if(STEPhead.length%2 = 0)flag = true;whil

20、e(STEPhead.length = nlength - 1)funTspt(STEPhead.nMer,STEPhead.nSer,flag);head+;for(int i = 0; i < head + 1; i+)a(STEPi.length) = i;a1(STEPi.length) = i;sp00 = sp01 = n;STEPhead.nMer = STEPhead.nSer = 0;int top = 0;int count = 0;show(a1,sp,top,count,a);bool A:funLeft(Node nd,int b1,int b2,int n)b

21、ool flag = abs(nd.nMer - b1) + abs(nd.nSer - b2) < nB + 1 && abs(nd.nMer - b1) + abs(nd.nSer - b2) > 0;if(flag = false)return false;if(n%2 = 0 && b1 >= nd.nMer && b2 >= nd.nSer)return true;if(n%2 = 1 && b1 <= nd.nMer && b2 <= nd.nSer)return t

22、rue;return false;void A:Tspt()Node *temp = new Node;temp = NULL;bool flag = false;while(head <= tail)if(STEPhead.length%2 = 0)flag = true;elseflag = false;temp = funTspt(STEPhead.nMer,STEPhead.nSer,flag);if(NULL != temp)break;head+;if(head > tail) cout<<"此問題無解!"<<endl; ex

23、it(1);doLeft(temp->nMer,temp->nSer,temp->length);/temp->nMer表示headdelete temp;Node* A:funTspt(int nm,int ns,bool flag)/flag = true 向對岸運輸Node *nd = NULL;int temp = 1;int tM = STEPhead.nMer;/可供運輸的商人數int tS = STEPhead.nSer;/可供運輸的仆人數if(flag = false)/向此岸運輸tM = n - STEPhead.nMer;tS = n - STEPh

24、ead.nSer;temp = -1;for(int i = 0; i < tM + 1 && i < nB + 1; i+)/i表示運輸的商人數for(int j = 0; j < tS + 1 && j < nB - i + 1; j+)/j表示運輸的仆人數if(i + j = 0)continue;int p = STEPhead.nMer - temp*i;int q = STEPhead.nSer - temp*j;if(islegal(p,q) = true && noRepeat(p,q) = true)if

25、(p = 0 && q = 0)tail+;STEPtail.length = STEPhead.length + 1;STEPtail.nMer = p;STEPtail.nSer = q;nd = (Node*)malloc(sizeof(Node);nd->length = STEPhead.length + 1;nd->nMer = head;nd->nSer = tail;return nd;tail+;STEPtail.length = STEPhead.length + 1;STEPtail.nMer = p;STEPtail.nSer = q;return nd;bool A:noRepeat(int nm,int ns)int j1 = 0;if(STEPhead.length%2 = 0)j1 = 1;for(int i = j1;