商人過(guò)河資料

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