商人過河資料

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