商人過河資料

-PAGE5-數學建模題目：商人安全過河問題學院：數理與信息工程學院專業(yè)：數學與應用數學組員：指導老師：評分：摘要本文通過MATLAB編程來解決商人安全過河問題。運用編程來計算分析，動態(tài)規(guī)劃思想的應用步驟。最后利用計算機編程進行求解，獲得過河問題的完整求解過程；有效地求解類似多步決策問題。針對此問題，為了求解3個商人和3個隨從的過河問題，用數學分析方法，建立多步決策數學模型，并且加以求解。首先通過圖解法求解3個商人和3個隨從的過河問題，引進狀態(tài)、允許狀態(tài)集合、狀態(tài)轉移等，通過多步決策將初始狀態(tài)到最終狀態(tài)來解決問題?？傊?，問題轉化為多步決策模型通過計算機、圖解法解決了問題過河需要經過11此來回。關鍵詞：多步決策；計算機求解；狀態(tài)轉移律；圖解法；MATLAB程序1問題重述三名商人各帶一個隨從過河，一只小船只能容納兩個人，隨從們約定，只要在河的任何一岸，一旦隨從人數多于商人人數就殺人越貨，但是商人們知道了他們的約定，并且如何過河的大權掌握在商人們手中，商人們該采取怎樣的策略才能安全過河呢？S個商人各帶一個隨從乘船過河，一只小船只能容納K人，由他們自己劃船。商人們竊聽到隨從們密謀，在河的任意一岸上，只要隨從的人數比商人多，就殺掉商人。但是如何乘船渡河的決策權在商人手中，商人們如何安排渡河計劃確保自身安全？2模型假設1.假設記第k次過河前A岸的商人數為XK，隨從數為YK，k=1，2，?S=2.假設記第k次過河船上的商人數為UK，隨從數為將二維向量DK=(UK3模型的建立與求解3.1問題一3.1.1問題分解在安全的前提下(兩岸的隨從數不比商人多),經有限步使全體人員過河。由于船上人數限制，這需要多步決策過程，必須考慮每一步船上的人員。動態(tài)規(guī)劃法正是求解多步決策的有效方法。它要求把解的問題一層一層地分解成一級一級、規(guī)模逐步縮小的子問題。直到可以直接求出其解的子問題為止。分解成所有子問題按層次關系構成一棵子問題樹．樹根是原問題。原問題的解依賴于子問題樹中所有子問題的解。3.1.3模型求解：窮舉法：計算機編程（見附錄）先建立編程的基本過程，然后考慮模型，再編寫程序。然后就可以得出結果了。開始開始變量賦值初始化判斷是否完全過河選擇一種可行方案，進行過河或返回，得到新的狀態(tài)否判斷是不是允許狀態(tài)集合中的狀態(tài)，并且還沒在已經考慮的狀態(tài)中是否還有其他狀態(tài)否結束是是是主程序流程圖圖解法：狀態(tài)s=(x,y)16個格點允許狀態(tài)10個●點允許決策移動1或2格;k奇,左下移;k偶,右上移.xxy3322110S1sn+1d1d11總共需要11步可以得出經過11步的渡河就能達到安全渡河的目標及滿足渡河的次數盡量少的條件。這11步的渡河方案就是上面程序運行結果中船上下面的一列。4模型的檢驗用2名商人和2名隨從的過河問題的解決思路，檢驗3名商人和3名隨從的過河問題。5模型的拓展和延伸通過三名商人和三名隨從的過河問題的解決方案，可以進一步計算四名商人和四名隨從的過河問題，通過計算機編程可以設計m名商人和n名隨從的過河問題。6總結這是通過數學分析的方法解決實用問題，經過問題提出、問題假設、問題分析、模型建立、模型求解、模型檢驗的過程，解決商人過河問題。然后擴展延伸到n個商人的問題。學習數學建模以來，重新認識了學習數學的樂趣，也重新認識了數學，本以為數學是單調的，枯燥的，學習了之后，發(fā)現(xiàn)數學是普遍存在我們生活之中的。解決現(xiàn)實中的問題，很多都需要數學。沉浸在數學的世界里，發(fā)現(xiàn)學習是有趣的；相比于機械的認識各個組織器官，建立一個數學模型解決問題是十分有趣的。7參考文獻[1]傅清祥．《數據結構與算法》．王曉東．北京：電子工業(yè)出版社1998．[2]姜啟瑟．《數學建?！?第二版)．北京：高等教育出版社，2000．[3]運籌學教材編寫組．《運籌學》(修訂版)．北京：清華大學出版社。2001．附錄：商仆過河的MATLAB程序及運行截屏:clear;clcn=3;%輸入商人數目;nn=3;%輸入仆人數目;nnn=2;%輸入船的最大容量;%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%決策生成jc=1;%決策向量存放在矩陣“d”中，jc為插入新元素的行標初始為1fori=0:nnnforj=0:nnnif(i+j<=nnn)&(i+j>0)%滿足條件D={(u,v)|1<=u+v<=nnn,u,v=0,1,2}d(jc,1:3)=[i,j1];%生成一個決策向量后立刻將他擴充為三維（再末尾加“1”）d(jc+1,1:3)=[-i,-j,-1];%同時生成他的負向量jc=jc+2;%由于一氣生成兩個決策向量,jc指標需要往下移動兩個單位endendj=0;end%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%狀態(tài)數組生成kx=1;%狀態(tài)數組存放在矩陣“A”中，生成方法同決策生成fori=n:-1:0forj=nn:-1:0if((i>=j)&((n-i)>=(nn-j)))|((i==0)|(i==n))%(i>=j)&((n-i)>=(nn-j)))|((i==0)|(i==n))為可以存在的狀態(tài)的約束條件A(kx,1:3)=[i,j,1];%生成狀態(tài)數組集合D`A(kx+1,1:3)=[i,j,0];kx=kx+2;endendj=nn;end;%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%將狀態(tài)數組生成抽象矩陣k=(1/2)*size(A,1);CX=zeros(2*k,2*k);a=size(d,1);fori=1:2*kforj=1:ac=A(i,:)+d(j,:);x=find((A