商人過河問題數(shù)學建模.doc

作業(yè)1、2：商人過河一、 問題重述問題一：4個商人帶著4個隨從過河，過河的工具只有一艘小船，只能同時載兩個人過河，包括劃船的人。隨從們密約, 在河的任一岸, 一旦隨從的人數(shù)比商人多, 就殺人越貨。乘船渡河的方案由商人決定。商人們怎樣才能安全過河?問題二：假如小船可以容3人，請問最多可以有幾名商人各帶一名隨從安全過河。二、問題分析問題可以看做一個多步?jīng)Q策過程。每一步由此岸到彼岸或彼岸到此岸船上的人員在安全的前提下(兩岸的隨從數(shù)不比商人多),經(jīng)有限步使全體人員過河。用狀態(tài)變量表示某一岸的人員狀況，決策變量表示船上的人員情況，可以找出狀態(tài)隨決策變化的規(guī)律。問題就轉(zhuǎn)換為在狀態(tài)的允許變化范圍內(nèi)（即安全渡河條件），確定每一步的決策，達到安全渡河的目標。三問題假設1. 過河途中不會出現(xiàn)不可抗力的自然因素。2. 當隨從人數(shù)大于商人數(shù)時，隨從們不會改變殺人的計劃。3船的質(zhì)量很好，在多次滿載的情況下也能正常運作。4. 隨從會聽從商人的調(diào)度。四、模型構(gòu)成x(k)第k次渡河前此岸的商人數(shù) x(k),y(k)=0,1,2,3,4;y(k)第k次渡河前此岸的隨從數(shù) k=1,2,.s(k)= x(k), y(k)過程的狀態(tài) S允許狀態(tài)集合S=(x,y) |x=0,y=0,1,2,3,4; x=4,y=0,1,2,3,4;x=y=1,2,3u(k)第k次渡船上的商人數(shù) u(k), v(k)=0,1,2;v(k) 第k次渡船上的隨從數(shù) k=1,2.d(k)=( u(k), v(k)過程的決策 D允許決策集合D=u,v|u+v=1,2,u,v=0,1,2狀態(tài)因決策而改變s(k+1)=s(k)+(-1)k*d(k)狀態(tài)轉(zhuǎn)移律求d(k) D(k=1,2,.n),使s(k) S并按轉(zhuǎn)移律s(k+1)=s(k)+(-1)k*d(k)由（4,4）到達（0,0）商人x隨從y數(shù)學模型： （1） （2） （3） （4） （5）模型分析：由（2）（3）（5）可得 化簡得 綜合（4）可得 和 （6）還要考慮 （7）把（2）（3）帶入（7）可得化簡得 （8）綜合（6）（7）（8）式可得 滿足條件的情況滿足下式 （9） 所以我們知道滿足條件的點如上圖所示：點移動由 （8）到達 （6）時，可以認為完成渡河。因為移動的格數(shù)小于等于2，只有中心點（2，2）到（6）點和（8）點的距離為2，所以中心點（2,2）成為渡河的關(guān)鍵點。當我們移動到（2,2）點時，就無法進行下去。故4個商人，4個隨從，船容量為2人時，無法安全渡河。對于問題二，我們可以建立模型為： （10） （11） （12） （13） （14） u(k), v(k)=0,1,2,3; （15）通過類似于問題一的步驟可以知道：坐標上的關(guān)鍵點是（3,3），最多可以五名商人帶五名隨從過去。 需要確定五名商人帶五名隨從的方案可行再確定六名商人帶六名隨從的方案不可行 1、五名商人帶五名隨從的情況： （1）首先不可能有三名商人先過河，兩名商人一名隨從過河，一名商人兩名隨從過河 （2）三個隨從先過河（5,2），回來一個隨從（5,3），過去兩個隨從（5,1）回來一個隨從（5,2），再過去三個商人（2,2），回來一個商人一個隨從（3,3），再過去三個商人（0,3），回來一個隨從（0,4），過去三個隨從（0,1），回來一個隨從（0,2）再過去兩個隨從（0,0）綜上可知：五名商人帶五名隨從，小船可以載三個人可以過河 2、六名商人帶六名隨從的情況： （1）首先不可能有三名商人先過河，兩名商人一名隨從過河，一名商人兩名隨從過河 （2）三個隨從先過河（6,3），回來一個隨從（6,4），過去兩個隨從（6,2）回來一個隨從（6,3），過去三個商人（3,3），此時兩岸都是（3,3），由坐標法分析知，這是最接近終點的臨界點，但是如果回來的時候一定是回來一個商人和一個隨從，如果這一步可行，后面就進行不去 綜上所述，六個商人帶六個隨從，小船載三個人的情況下不能渡河 結(jié)合1、2知，當小船最多載三個人的時候，最多五名商人各帶一個隨從可以過河。5、 模型的檢