商人過河四商四仆

1、2012高教社杯全國大學(xué)生數(shù)學(xué)建模競賽承諾書我們仔細(xì)閱讀了中國大學(xué)生數(shù)學(xué)建模競賽的競賽規(guī)則.我們完全明白，在競賽開始后參賽隊(duì)員不能以任何方式（包括電話、 電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與 賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的，如果引用別人的成果 或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的 表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競賽規(guī)則，以保證競賽的公正、公平性。如 有違反競賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們參賽選擇的題號是（從A/B/C/D中選擇一項(xiàng)填寫）：A我們的參賽報(bào)名號為（如果賽區(qū)設(shè)置

2、報(bào)名號的話）：J2202所屬學(xué)校（請?zhí)顚懲暾娜航鳝h(huán)境工程職業(yè)學(xué)院參賽隊(duì)員（打印并簽名）：1.2. 3. 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人（打印并簽名）：教導(dǎo)組日期：2012年8月9 EI賽區(qū)評閱編號（由賽區(qū)組委會評閱前進(jìn)行編號）:2012高教社杯全國大學(xué)生數(shù)學(xué)建模競賽編號專用頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進(jìn)行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）:評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）:全國評閱編號（由全國組委會評閱前進(jìn)行編號）:摘要本文研究的是四個商人和四個仆人從河岸的一邊過到河的另一邊的 問題，過河的工具只有一搜小船，只能同時載兩個人過河，包括劃船的人, 由他

3、們自己劃行。針對商人安全渡河的問題，采用多步?jīng)Q策的過程，根據(jù) 各量的空間兒何關(guān)系，經(jīng)過嚴(yán)格的數(shù)學(xué)公式推導(dǎo)。分別建立兩個模型：模型一采用窮舉法，對各種過河的方案一一列舉, 然后根據(jù)商人們要安全過河為前提對各種進(jìn)行了列舉，經(jīng)過層層篩選，最 終求出商人安全的方案。模型二采用圖解法，利用圖示表示說明該題的解 法。最后本文就此問題進(jìn)行推廣，當(dāng)有M名商人N名隨從且小船容量為K 時，將會得到兒種解決方案給出了說明。關(guān)鍵詞：渡河問題數(shù)學(xué)公式一、問題的提出當(dāng)今社會每個人都想當(dāng)王者，誰都想成為富翁，所以就在這個問題中 仆人們也想成為商人。仆人們密約，在河的任何一邊，只要仆人的數(shù)量超 過商人的數(shù)量，仆人就會聯(lián)合起來

4、將商人殺死并搶奪其財(cái)物，問應(yīng)如何設(shè) 計(jì)過河順序才能讓所有人安全地過到河的另一邊。二、模型的分析四個商人各帶一名仆人乘船渡河，一只小船最多能容納兩個人，要他 們都安全到達(dá)河的對岸。這個問題可以看成一個多步?jīng)Q策的過程，每一步, 即船由此岸駛向彼岸或從彼岸駛回此岸，都要對船上的人員作出計(jì)算，在 保證安全的前提下（兩岸的商人數(shù)都比仆人多）。在有限步內(nèi)使人員全部 渡河，用狀態(tài)（變量）表示某一岸的人員數(shù)量，決策（變量）表示船上的 人員數(shù)量，可以找出狀態(tài)隨決策的變化規(guī)律。問題轉(zhuǎn)化為在狀態(tài)的允許范 圍內(nèi)（安全條件渡河），確定每一步?jīng)Q策，達(dá)到渡河的目的。三、模型的假設(shè)1. 小船的質(zhì)量是好的。2. 過河的途中沒有

5、突發(fā)情況。3. 水流的速度正常。4. 每個商人和隨從都會劃船5. 隨便兩個人都會做同一條船四、符號說明符號詮釋符號詮釋M商人N仆人m商人數(shù)量n仆人數(shù)量K小船的容量A正常狀況下，商人和隨從所在河的一邊B正常情況下，商人和隨從所在河的一邊的對岸X第n次，A岸的商人數(shù)y第n次,A岸的隨從數(shù)g渡河前A岸的商人和隨從的人數(shù)狀況圖1符號表示示意圖 五、模型的建立與求解9 商人、浦諦T宗咅園模型一：窮舉法 假設(shè)商人數(shù)量有4個（分別為M, Mj, MJ,仆人數(shù)量也有4個（分別為N”汕），小船可容納人數(shù)為2 首先M、弘先過河對岸 M回來 M、M過河對岸 他回來 過河對岸這時，河的本岸及對岸人數(shù)都是2商人2仆人，

6、無論哪一方過河對岸，結(jié) 果都是商人無法安全過河，此模型陷入無限循環(huán)之中。因此此模型無解。 模型二：坐標(biāo)法y仆人禹Kra q 南 a壬口41、人斤匚力;市出糸菩反1允許步驟數(shù)厶是沿方格線移動1格或2格，厶為奇數(shù)時向左.下方移動, 厶為偶數(shù)時向右上方移動，要確定一系列的厶，使初始狀態(tài)（4, 4）最終 變?yōu)椋?, 0）,無論怎樣走都必須經(jīng)過中間點(diǎn)（2, 2）,然后奇數(shù)次到達(dá)Y 軸，而無論怎么變化人數(shù)都也只能到達(dá)此點(diǎn)后不能繼續(xù)走下去，只能循 環(huán)走，達(dá)不到最終的目標(biāo)（0, 0）oSO二(4, 4)Sl=(3, 3)S2=(4, 3)S3二(4, 1)S4= (4,2)S5=(4, 0)S6=(4, 1)

7、Sl=(4, 2)S5=(2,2)S6=(3,3)由流程圖看出，最后陷入循環(huán)，達(dá)不到(0, 0).六、模型的評價及推廣“商人渡河”模型適合于解決很多問題，如“傳教士與野蠻人渡河”, “印度夫妻渡河”等。這些問題本質(zhì)上都是相同或相似的，由此可見這個 趣味問題流傳的廣泛性。另外還有所謂“人狗雞米過河”問題，也是頗有 趣味的，人、狗、雞、米均要過河，船需人劃，而船上至多還可載一物， 但若人不在時，狗會吃雞，雞會吃米，問如何設(shè)計(jì)安全過河方案。我們完 全可以仿照商人渡河問題建立一個多步?jīng)Q策模型，將上述算法稍作修改， 就可以得到它的解。這里就不再贅述了。另外，用一定容積的若干油瓶倒 出一定量的油的問題也屬此類問題。七、模型的改進(jìn)優(yōu)點(diǎn)：多步?jīng)Q策不會出現(xiàn)遺漏可能的過河方式，可以將其全部得出來 且看起來直觀易懂。缺點(diǎn)：模型的缺點(diǎn)也很明顯，就是解決是復(fù)雜繁瑣，且只能解決過河 的人少時的過河方案，如果人多的話，這種方法顯然不適合。推廣：商人過河模型適合于解決很多問題，如“和尚和尼姑過河”、“人 狗雞米過河”等。這些問題本質(zhì)上市相同