5對夫妻要過河問題

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