狼羊過河模型

1、大學(xué)生數(shù)學(xué)建模承 諾 書我們仔細(xì)閱讀了數(shù)學(xué)建模的規(guī)則.我們完全明白，在競(jìng)賽開始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競(jìng)賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競(jìng)賽規(guī)則，以保證競(jìng)賽的公正、公平性。如有違反競(jìng)賽規(guī)則的行為，我們將受到嚴(yán)肅處理。所屬班級(jí)（請(qǐng)?zhí)顚懲暾娜?隊(duì)員 (打印并簽名) ：1. 2. 3. 4. 5. 小組負(fù)責(zé)人 (打印并簽名)： 日期： 2012 年

2、 3月 30日教師評(píng)閱：人、狼、羊、白菜過河模型 一人擺渡希望用一條船將一只狼，一只羊，一籃白菜從河岸一邊帶到河岸對(duì)面，由于船的限制，一次只能帶一樣?xùn)|西過河，絕不能在無人看守的情況下將狼和羊放在一起；羊和白菜放在一起，怎樣才能將它們安全的帶到河對(duì)岸去？一、 問題分析：在正常情況下，一般要求在渡河過程中不能損失任何物品，但在某些情況下，有時(shí)候會(huì)從時(shí)間和經(jīng)濟(jì)考慮，可能會(huì)舍棄一些對(duì)自己不重要的，現(xiàn)在我們只考慮正常情況下的。人狼羊白菜安全渡河問題可以看做是一個(gè)多步?jīng)Q策過程。每一步要讓船從此岸駛向彼岸或從彼岸返回此岸，都不能使得它們有損失，要對(duì)狼羊白菜作出決策，在保證安全的前提下，在有限步內(nèi)全部安全通過

3、，用圖可以找出決策變化的規(guī)律，確定每一步的決策來達(dá)到安全渡河的目標(biāo)。二、 模型構(gòu)建：用二維向量Sk=(x,y) 定義為狀態(tài). ，k=1,2,3,4,5,6,7設(shè)A,B,C,D分別為人帶狼，人帶羊，人帶白菜,人不帶任何。安全渡河條件下的集合記為可行狀態(tài)集合S，記Sk= (x,y)|x =D，y=A,B,C，D 其中當(dāng)k為奇數(shù)的時(shí)候表示船從此岸駛向彼岸，偶數(shù)的時(shí)候表示船從彼岸駛向此岸，（x,y）表示x帶著y.例如： S1=（D,B）表示人帶著羊從此岸駛向彼岸； S2= (D,D) 表示人不帶物從彼岸駛向此岸。三、 模型實(shí)現(xiàn)：此題由于比較簡(jiǎn)單，用圖解法做較之容易，可以做一個(gè)過河分析圖如下：圖一：在從

4、圖一可以確定狼、羊、白菜過河的過程，可以得到以下的兩種渡河的具體方法，用圖解法畫出來用以下圖一，圖二表示：dcba0abc 圖二：圖三：圖二解法A：S1=(D,B),S2=(D,D),S3=(D,A),S4=(D,B),dcba0abcS5=(D,C),S6=(D,D),S7=(D,B)。圖三解法B：S1=(D,B),S2=(D,D),S3=(D,C),S4=(D,B), S5=(D,A),S6=(D,D),S7=(D,B)。 從以上模型得出了兩種移動(dòng)方案，經(jīng)過決策S1，S2,，S7.,最終通過這七步使得人、狼、羊、白菜安全通過，這結(jié)果為渡河的方案。四、 結(jié)論分析：從以上圖形可以看出有兩種辦法

5、使得人能帶著東西安全渡過河，所建立的多步?jīng)Q策模型可以用計(jì)算機(jī)求解，但對(duì)于該問題，用圖解法更容易求的方法。通過圖解法可以得到的兩種方法，翻譯成分別為方法A和方法B：方法A：是人先帶羊，然后回來，帶狼過河，然后把羊帶回來，放下羊，帶白菜過去，然后再回來把羊帶過去。 方法B：是人先帶羊過河，然后自己回來，帶白菜過去，放下白菜，帶著羊回來，然后放下羊，把狼帶過去，最后再回轉(zhuǎn)來，帶羊過去。五、 模型延拓：對(duì)于這個(gè)模型來說首先需要假定許多的外在條件不變下，才有了上述的決策，但對(duì)于現(xiàn)實(shí)生活中的決策者來說，不一定要將所有的物品帶到彼岸就是最好的決策方案，有時(shí)候考慮到其他的外在因素存在的時(shí)候，決策者可以適當(dāng)?shù)倪x擇舍棄某些對(duì)于大局無傷大雅的物品來做到最優(yōu)化的決策！例如：1、 在往返與河岸之間浪費(fèi)了許多的時(shí)間和精力，這對(duì)于某些決策者來說是很不合理的，他們沒有那么多的時(shí)間和精力用來浪費(fèi)！在此時(shí)對(duì)于決策者來說就可以考慮舍棄對(duì)于整個(gè)事件無傷大雅的事物，可以綜合考慮整個(gè)事件的經(jīng)濟(jì)效益！通