人貓雞米渡河問(wèn)題的數(shù)學(xué)模型

.../人貓雞米渡河問(wèn)題的數(shù)學(xué)模型摘要：人帶著貓、雞、米過(guò)河,從左岸到右岸,船除了需要人劃之外〔船除了要載人外,只能載貓、雞、米三者之一,而當(dāng)人不在場(chǎng)時(shí)貓要吃雞、雞要吃米。本文將設(shè)計(jì)一個(gè)安全過(guò)河方案,使渡河次數(shù)盡量地少。模仿"商人過(guò)河"的模型設(shè)計(jì)出新的數(shù)學(xué)模型。關(guān)鍵字：窮舉法,Matlab運(yùn)算求解。一、問(wèn)題的提出課本P19.T5:模仿"商人過(guò)河"模型,做下面游戲：人帶著貓、雞、米過(guò)河,船除需要人劃之外,至多能載貓、雞、米三者之一,而當(dāng)人不在場(chǎng)時(shí)貓要吃雞、雞要吃米。設(shè)計(jì)一個(gè)過(guò)河方案,建立數(shù)學(xué)模型,并使渡河次數(shù)盡量地少。二、問(wèn)題的分析因?yàn)檫@是個(gè)簡(jiǎn)單問(wèn)題,研究對(duì)象少,所以可以用窮舉法,簡(jiǎn)單運(yùn)算即可解題。此問(wèn)題是從狀態(tài)向量A〔1,1,1,1經(jīng)過(guò)奇數(shù)次運(yùn)算向量B變?yōu)闋顟B(tài)向量A〔0,0,0,0的狀態(tài)。轉(zhuǎn)移過(guò)程為什么是奇數(shù)次？我們注意到過(guò)河有兩種,奇數(shù)次的為從左岸到右岸,而偶數(shù)的為右岸回到左岸,因此得到下述轉(zhuǎn)移過(guò)程,所以最后應(yīng)該是過(guò)河完成時(shí)狀態(tài)轉(zhuǎn)移數(shù)為奇數(shù)次。三、問(wèn)題的假設(shè)1.1：假設(shè)船除了載人之外,至多只能載貓、雞、米三者之一。1.2：當(dāng)人不在場(chǎng)時(shí),貓一定會(huì)吃雞、雞一定會(huì)吃米。四、定義符號(hào)說(shuō)明：我們將人,貓,雞,米依次用四維向量中的分量表示,當(dāng)一物在左岸時(shí),相應(yīng)的分量記為1,在右岸時(shí)記為0.如向量〔1,0,1,0表示人和雞在左岸,貓和米在右岸,并將這些向量稱為狀態(tài)向量。例如〔1,1,1,1表示它們都在左岸,〔0,1,1,0表示貓,雞在左岸,人,米在右岸；由于問(wèn)題中的限制條件,有些狀態(tài)是允許的,有些狀態(tài)是不允許的。凡問(wèn)題可以允許存在的狀態(tài)稱為可取狀態(tài)。A向量定義為狀態(tài)變量。比如是一個(gè)可取狀態(tài)向量,但是一個(gè)不可取狀態(tài)向量。此外,B向量定義為運(yùn)載變量。把每運(yùn)載一次也用一個(gè)四維向量來(lái)表示。如表示人和貓?jiān)诖?而雞和米不在船上,這自然是可取的運(yùn)載,因?yàn)榇奢d兩物,而則是不可取運(yùn)載,依此規(guī)律類推。五、模型的建立對(duì)于這個(gè)問(wèn)題我們用窮舉的方法來(lái)解決,首先將此問(wèn)題化為狀態(tài)轉(zhuǎn)移問(wèn)題來(lái)解決。對(duì)本問(wèn)題來(lái)說(shuō)：可取狀態(tài)向量共有10個(gè),可以用窮舉法列出來(lái)：右邊5個(gè)正好是左邊5個(gè)的相反狀態(tài)。可取運(yùn)載共有4個(gè)：5.3、可取運(yùn)算：規(guī)定與相加時(shí)對(duì)每一分量按二進(jìn)制法則〔異或運(yùn)算進(jìn)行。這樣,一次渡河就是一個(gè)可取狀態(tài)向量與一個(gè)可取運(yùn)載向量相加,可取狀態(tài)經(jīng)過(guò)加法運(yùn)算仍是一個(gè)可取狀態(tài),這種運(yùn)算稱為可取運(yùn)算。在上述規(guī)定下,問(wèn)題轉(zhuǎn)化為：從初始狀態(tài)至少經(jīng)過(guò)多少次〔奇數(shù)次可取運(yùn)算才能轉(zhuǎn)化為狀態(tài)。六、模型的求解如果一個(gè)狀態(tài)是可取的就打,否則就打,雖然可取但已重復(fù)就打,于是問(wèn)題可用窮舉法解答如下：1〔2〔3〔4〔4〔5〔5〔6〔7第7步已經(jīng)出現(xiàn)了狀態(tài),說(shuō)明經(jīng)7次運(yùn)載即可,其過(guò)程為：因此,該問(wèn)題的最優(yōu)方案有2種：1、人先帶雞過(guò)河,然后人再回來(lái),把米帶過(guò)河,然后把雞運(yùn)回河岸,人再把貓帶過(guò)河,最后人回來(lái)把雞帶過(guò)去。2、人先帶雞過(guò)河,然后人再回來(lái),把貓帶過(guò)河,然后把雞運(yùn)回河岸,人再把米帶過(guò)河,最后人回來(lái)把雞帶過(guò)去。七、模型的評(píng)價(jià)7.1、優(yōu)點(diǎn)：本算法將研究對(duì)象用四維向量中的分量用0,1表示,運(yùn)用窮舉法找出所有可取狀態(tài)向量再用一些基礎(chǔ)可取運(yùn)算方法將結(jié)果列出來(lái)再以圖形表示出來(lái)。模型簡(jiǎn)單,切合實(shí)際,易于理解,整個(gè)過(guò)程易懂合理。7.2、缺點(diǎn)：由于問(wèn)題的求解沒有使用LINGO,LINDO或MATLAB軟件,當(dāng)狀態(tài)和決策過(guò)多時(shí),采用上述方法求解顯得繁瑣,容易出錯(cuò),所以下面給出此問(wèn)題的matlab求解過(guò)程。7．3、推廣：正如課本上的商人們安全過(guò)河問(wèn)題,當(dāng)商人和隨從人數(shù)增加或小船的容量加大時(shí),靠邏輯思考就有些困難了,而適當(dāng)?shù)卦O(shè)置狀態(tài)和決策,確定狀態(tài)轉(zhuǎn)移率,建立多步?jīng)Q策模型,仍可方便有效地求解此類型問(wèn)題。八、mathlab求解過(guò)程模型假設(shè)與建立：8.1.1、由上可知,可取狀態(tài)向量共有10個(gè),即：可取運(yùn)載B有4個(gè)：〔1,1,0,0、〔1,0,1,0、〔1,0,0,1、〔1,0,0,0。8.2、算法設(shè)計(jì)：8.2.1、規(guī)定A和B的每一分量相加時(shí)按二進(jìn)制法則進(jìn)行,這樣一次渡河就是一個(gè)可取狀態(tài)和一個(gè)可取運(yùn)載相加,在判斷和向量是否屬于可取狀態(tài)即可。8.2.2、可以將可取狀態(tài)及可取運(yùn)載分別編成矩陣。共分為五個(gè)m文件,一個(gè)主文件xduhe.m數(shù),四個(gè)子文件分別為：8.2.2.1、duhe〔L,B,M,s函數(shù)：用來(lái)實(shí)現(xiàn)渡河總思路。思路為：將起始矩陣A分別與可取運(yùn)載相加〔使用二進(jìn)制法則,判斷相加后的矩陣C是否是〔0,0,0,0,如果是,則渡河成功。否則,用fuhe<C,M>函數(shù)判斷C是否是可取狀態(tài),如果是,則打印并將C與初始矩陣合并成新矩陣,繼續(xù)調(diào)用duhe.m函數(shù)。8.2.2.2、fuhe<C,M>函數(shù)：判斷和矩陣C是否屬于矩陣M,如果是,則返回1,否則返回0.8.2.2.3、Panduan〔S函數(shù)：判斷S矩陣中是否有兩個(gè)相同的狀態(tài),即行向量。如果有,則返回0,否則返回1.8.2.2.4、print<K,C,s>函數(shù)：打印相應(yīng)的狀態(tài)。8.3、程序代碼：8.3.1、xduhe.m文件：clear;clc;A=[1,1,1,1];B=[1,0,1,0;1,1,0,0;1,0,0,1;1,0,0,0];M=[1,1,1,0;0,0,0,1;1,1,0,1;0,0,1,0;1,0,1,1;0,1,0,0;1,0,1,0;0,1,0,1];duhe<A,B,M,1>;8.3.2、duhe.m文件：functionduhe<L,B,M,s>;[h,l]=size<L>;fork=s:hfori=1:4C=mod<L<k,:>+B<i,:>,2>;ifC==[0,0,0,0]print<B<i,:>,C,s>;fprintf<'渡河成功\n\n'>;break;elseiffuhe<C,M>==1print<B<i,:>,C,s>;S=[L;C];ifPanduan<S>==1duhe<S,B,M,s+1>;elsefprintf<'此渡河方案不可行\(zhòng)n\n'>;endendendendend8.3.3、fuhe.m文件：functiony=fuhe<C,M>y=0;fori=1:8if<C==M<i,:>>y=1;break;endend8.3.4、Panduan.m文件：functionz=Panduan<S>z=1;[m,n]=size<S>;forp=1:mforq=<p+1>:mifS<p,:>-S<q,:>==[0,0,0,0]z=0;break;endendend8.3.5、print.m文件：functionprint<K,C,s>fprintf<'第%d次渡河:',s>;ifK<1>==1fprintf<'人,'>;endifK<2>==1fprintf<'貓,'>;endifK<3>==1fprintf<'雞,'>;endifK<4>==1fprintf<'米,'>;endifC<1>==0fprintf<'從左岸到達(dá)右岸\n'>;elsefprintf<'從右岸回到左岸\n'>;end8.4、模型結(jié)論在matlab中運(yùn)行,結(jié)果如下：從運(yùn)行結(jié)果可以看出,共有兩種運(yùn)送方案：人先帶雞過(guò)河,然后人再回來(lái),把米帶過(guò)河,然后把雞運(yùn)回河岸,人再把貓帶過(guò)河,最后人回來(lái)把雞帶過(guò)去。人先帶雞過(guò)河,然后人再回來(lái),把貓帶過(guò)河,然后把雞運(yùn)回河岸,人再把米帶過(guò)河,最后人回來(lái)把雞帶過(guò)去。8.5、收獲與不足：復(fù)習(xí)和加深了對(duì)matlab的學(xué)習(xí),見識(shí)了MATLAB7.10.0<R2010a>的厲害,引發(fā)了我對(duì)數(shù)學(xué)建模的強(qiáng)大興趣。而且,利用MATLAB可以非常容易而且很直觀地得出問(wèn)題的解決方案,從而在不斷深化對(duì)問(wèn)題認(rèn)識(shí)的同時(shí),把問(wèn)題普遍化。但是這個(gè)問(wèn)題的求解過(guò)程是請(qǐng)教了師姐才得以完成的。九、"商人過(guò)河"的算法步驟和matlab求解過(guò)程另外,由于本次數(shù)學(xué)建模的啟發(fā),我們組根據(jù)老師上課講的"商人過(guò)河"的算法步驟,用matlab編程出程序,求解過(guò)程如下：9.1、模型建立：

此問(wèn)題可視為一個(gè)

多步?jīng)Q策多步?jīng)Q策:決策過(guò)程難以一次完成,而要分步優(yōu)化,最后獲取一個(gè)全局最優(yōu)方案的決策方法稱為多步?jīng)Q策。問(wèn)題：每一步就是一次渡河,每次渡河就是一次狀態(tài)轉(zhuǎn)移。

用三維變量表示狀態(tài)：商人數(shù)的取值范圍：{0,1,2,3}；隨從數(shù)

的取值范圍：{0,1,2,3}；船

的取值范圍：{0,1}。

那么安全狀態(tài)〔可取向量可表示為：安全狀態(tài)：商人們安全是指在兩岸都安全,故當(dāng)x=0,3時(shí),y=0,1,2,3,而當(dāng)x=1,2時(shí),此岸要求x≥y,對(duì)岸要求3-x≥3-y,綜合即x=y；安全狀態(tài)：商人們安全是指在兩岸都安全,故當(dāng)x=0,3時(shí),y=0,1,2,3,而當(dāng)x=1,2時(shí),此岸要求x≥y,對(duì)岸要求3-x≥3-y,綜合即x=y；<3,3,1><3,2,1><3,1,1><2,2,1><3,0,1><0,3,1><0,2,1><1,1,1><0,1,1><3,2,0><3,1,0><2,2,0><3,0,0><0,3,0><0,2,0><1,1,0><0,1,0><0,0,0>

這就是此問(wèn)題的數(shù)學(xué)模型。9.2、模型求解：這樣問(wèn)題要求由<3,3,1>變到<0,0,0>的一條道路。

根據(jù)題意,狀態(tài)轉(zhuǎn)移時(shí)要滿足一定的規(guī)則：Z從1變?yōu)?與從0變?yōu)?交替進(jìn)行；當(dāng)Z從1變?yōu)?時(shí),即船從此岸到對(duì)岸,此岸人數(shù)減少1或2個(gè)；即<x,y,1>→<u,v,0>時(shí),u≤x,v≤y,u+v=x+y-1oru+v=x+y-2；當(dāng)Z從0變?yōu)?時(shí),即船從對(duì)岸到此岸,此岸人數(shù)增加1或2個(gè)；

即<x,y,0