5對(duì)夫妻要過(guò)河問(wèn)題

數(shù)學(xué)建模論文題目：夫妻過(guò)河問(wèn)題題目：夫妻過(guò)河有5對(duì)夫妻要過(guò)河，船至多可載3人，條件是任一女子不能在其丈夫不在場(chǎng)的情況下與另外的男子在一起，問(wèn)如何安排這5對(duì)夫妻過(guò)河？摘要：主要運(yùn)用狀態(tài)轉(zhuǎn)移矩陣的方法分析類似于夫妻過(guò)河等問(wèn)題。一個(gè)系統(tǒng)的某些因素在轉(zhuǎn)移中，第k+1次結(jié)果只受第k的結(jié)果影響，即只與當(dāng)前所處狀態(tài)有關(guān)，而與過(guò)去狀態(tài)無(wú)關(guān)。引入狀態(tài)轉(zhuǎn)移這個(gè)概念。所謂狀態(tài)是指客觀事物可能出現(xiàn)或存在的狀態(tài)；狀態(tài)轉(zhuǎn)移是指客觀事物由一種狀態(tài)轉(zhuǎn)移到另一種狀態(tài)的概率。關(guān)鍵詞：狀態(tài)轉(zhuǎn)移，狀態(tài)集合，圖解法。正文：?問(wèn)題的復(fù)述：有5對(duì)夫妻要過(guò)河，船至多可載3人，條件是任一女子不能在其丈夫不在場(chǎng)的情況下與另外的男子在一起，問(wèn)如何安排這5對(duì)夫妻過(guò)河？?問(wèn)題分析：多步?jīng)Q策過(guò)程：決策：每一步（此岸到彼岸或彼岸到此岸）船上的人員。過(guò)約束條件：1五對(duì)夫妻（十人）；2只有一條僅可容三人的小船；3妻子必須有丈夫在身旁。?模型假設(shè)：1不考慮五對(duì)夫妻及所帶物品的重量；2五對(duì)夫妻只能依靠小船過(guò)河；?符號(hào)說(shuō)明：1此岸有H個(gè)男人(丈夫),F個(gè)女人(妻子)，k為小船的行駛次數(shù)。2滿足妻子必須有丈夫在身旁稱允許狀態(tài)，允許狀態(tài)集合S。3u,v分別表示小船離岸時(shí)船上男人與女人的數(shù)量。4規(guī)定第k次運(yùn)算(-1)*(u,v)由第k+1個(gè)狀態(tài)57+1減去第n個(gè)狀態(tài)S#來(lái)確定。建模目的：確定一系列的允許運(yùn)算(k=l,2,…，m)?模型分析：假設(shè)由北岸往南岸渡河，用向量(H,F)表示有H個(gè)男子、F個(gè)女子在北岸，其中OWH,FW5,稱向量(H,F)為狀態(tài)向量；由條件知，有些狀態(tài)是可取的，有些是不可取的，如(2,3)是不可取的，而狀態(tài)(5,1)是可取的?？扇顟B(tài)：由己知條件知可取狀態(tài)為(0,1),(1,2),(5,2),0WIW5。(1,1)為可取狀態(tài)，這是因?yàn)榭偪梢赃m當(dāng)安排而使他們是i對(duì)夫妻?？偣灿?6種(5,4)(5,3)(5,2)(5,1)(5,0)(0,4)(0,3)(0,2)(0,1)(0,0)(1,1)(2,2)(3,3) (4,4)(5,5)(0,5)用S表示可取狀態(tài)的集合，成為允許狀態(tài)集合?？扇∵\(yùn)載：(0,1),(0,2),(0,3)(1,0) (2,0),(3,0)(1,1),(2,1)其中(1,1)表示1對(duì)夫妻。用d表示可取運(yùn)載集合，稱為允許決策集合。?模型建立:記載k次渡河前北岸男子數(shù)為Ha，女子數(shù)為Fk，S=(H,F)稱為狀態(tài)；記第k次渡河船上的男子數(shù)位u,女子數(shù)為v.可取運(yùn)載：取可取運(yùn)載向量為也二(-1)1(u,V)其中u,v=0,1,2,3且1Wu+vW3,k=l,2,3……當(dāng)k為奇數(shù)時(shí)，負(fù)向量表示過(guò)河；當(dāng)k為偶數(shù)時(shí)，正向量表示由對(duì)岸返回來(lái)。貝V,我們把方程 Sh=S^dk稱為狀態(tài)轉(zhuǎn)移律。?模型解決與結(jié)果：求解.實(shí)際上是要一步一步地考慮由一個(gè)允許狀態(tài)加上一個(gè)允許運(yùn)算，得出另一個(gè)允許狀態(tài)的過(guò)程，試圖尋求一條由初始狀態(tài)(5,5)轉(zhuǎn)為期望狀態(tài)(0,0)的路徑(當(dāng)然對(duì)有些問(wèn)題這種路徑不一定存在)，也就是要確定一系列的允許運(yùn)算d.(k=l，2,???,in),使得(5'5)+次+北+……+dm=(°，°)由于本問(wèn)題涉及的變量不多，約束條件也不多，我們可以憑簡(jiǎn)單的用圖解法進(jìn)行求解。圖解過(guò)程如下圖圖所示:(5,5)去三女K5,2)—回一女■(5,3)去兩女.(5,1)回一女?去三男〈2,2)回一女一男?去三男夕0,3)—回一女.(0,4)去三女KQ1)—回?女.所以經(jīng)過(guò)11次決策即可完成。(0,2)去兩女.(0,0) 五對(duì)夫妻可過(guò)河！結(jié)語(yǔ)狀態(tài)轉(zhuǎn)移問(wèn)題一般并不一定有解存在，有解時(shí)解法乂不一定唯一.當(dāng)解法不唯一時(shí),