重庆大学本科生数学模型作业报告
人猫鸡米渡河问题的数学模型
组员： 唐新 20123062 赵广志 20122590
指导教师： 黄光辉
1
人猫鸡米渡河问题的数学模型
一、摘要：
本文主要对数学建模基础模型跟“商人过河”类似简单问题：人带着猫、鸡、米过河，船除需要人划之外，至多能载猫、鸡、米三者之一，而当人不在场时猫要吃鸡、鸡要吃米。试设计一个安全过河方案，建立数学模型，并使渡河次数尽量地少。模仿“商人过河”的模型设计出新的数学模型。
二、问题的重述
人带着猫、鸡、米过河，船除需要人划之外，至多能载猫、鸡、米三者之一，而当人不在场时猫要吃鸡、鸡要吃米。试设计一个安全过河方案，并使渡河次数尽量地少。
关键词：人不在场时猫要吃鸡、鸡要吃米，船需人划，穷举法
三、模型假设
不考虑外界其他影响，只考虑问题所述的条件: 1、船除需要人划之外，至多能载猫、鸡、米三者之一 2、当人不在场时猫要吃鸡、鸡要吃米
2
四、符号说明
符号 i?1, i?2, 诠释 人 猫 鸡 米 在此岸 在对岸 此岸状态 对岸状态 i?3, i?4, xi?1 xi?0 s??x1,x2,x3,x4? s'??1?x1,1?x2,1?x3,1?x4? d??u1,u2,u3,u4? ui?1 乘船方案 i在船上时 i不在船上 第k次渡河前此岸的状态 第k次渡河的决策 ui?0 sk dk
3
五、问题分析
安全过河问题可以看着是一个多部决策的过程。每作出一步决策，都必须保证船、人、猫、鸡、米能满足题设条件。否则，不仅难以实现过河的最优化，而且还容易出现事物的不安全性。因此，在保证安全的前提下，即猫、鸡在一起时，人要在场，鸡、米在一起时，人也要在场，用状态变量s表示某一岸的状况，决策变量d表示是乘车方案，我们容易得到s和d的关系，其中问题的转化要在允许变化范围内，确定每一步的决策关系，从而达到渡河的最优目标。
六、模型建立与求解
Ⅰ. 模型的建立：
人、猫、鸡、米分别记为i?1,2,3,4，当i在此岸时记xi?1，否则记
xi?0，则此岸的状态可用s??x1,x2,x3,x4?表示。记s的反状态为
s'??1?x1,1?x2,1?x3,1?x4?，允许状态集合为
S???1,1,1,1?,?1,1,1,0?,?1,1,0,1?,?1,0,1,1?,?1,0,1,0?? （1） 以及他们的5个反状态。
决策为乘船方案，记作d??u1,u2,u3,u4?，当i在船上时记ui?1，否则记
ui?0，允许决策集合为
D???1,1,0,0?,?1,0,1,0?,?1,0,0,1?,?1,0,0,0?? （2）
记第k次渡河前此岸的状态为sk，第k次渡河的决策为dk，则状态转移律为
s?s???1?kd， （3） k?1kk
4
设计安全过河方案归结为求决策序列d1,d2,?,dn?D,，使状态sk?S按状态转移律由初始状态s1??1,1,1,1?经n步达到sn?1??0,0,0,0?。
Ⅱ. 模型的求解：
从而我们得到一个可行的方案如下：
k 1 2 3 4 5 6 7 8 sk ?1,1,1,1? ?0,1,0,1? ?1,1,0,1? ?0,1,0,0??1,1,1,0? ?0,0,1,0??1,0,1,0??0,0,0,0? dk?1,0,1,0??1,0,0,0??1,0,0,1??1,0,1,0? ?1,1,0,0??1,0,0,0??1,0,1,0?
因此，该问题的最优方案是：
1、人先带鸡过河，然后人再回来，把米带过河，然后把鸡运回河岸，人再把猫带过河，最后人回来把鸡带过去。
2、人先带鸡过河，然后人再回来，把猫带过河，然后把鸡运回河岸，人再把米带过河，最后人回来把鸡带过去。
5
七、模型评价与推广
（Ⅰ）优点：
1、模型简单，切合实际，易于理解； 2、建立了合理、科学的状态转移的模型。
3、结合实际情况对问题进行求解，使得模型具有很好的通用性和推广性； （Ⅱ）缺点：
由于问题的求解没有使用LINGO或MATLAB软件，当状态和决策过多时，采用上述方法求解显得繁琐，容易出错。 （Ⅲ）推广：
正如课本上的商人们安全过河问题，当商人和随从人数增加或小船的容量加大时，靠逻辑思考就有些困难了，而适当地设置状态和决策，确定状态转移率，建立多步决策模型，仍可方便有效地求解此类型问题。
七、参考文献：
【1】姜启源，谢金星，叶俊《数学模型》，第四版。高等教育出版社 【2】赵静，但琦《数学建模与数学实验》，高等教育出版社 【3】姜启源，谢金星，邢文训，张立平《大学数学实验》，第二版，清华大学出版社
【4】 杨启帆，边馥萍. 数学建模. 浙江大学出版社
6