商仆过河问题——数学建模
商仆过河问题
作者：*学院**班*** ********** **号
2014年12月4日
摘要：为了求解3个商人和3个随从的过河问题，用数学分析方法，建立
数学模型，并且加以求解，展示动态规划思想的应用步骤。最后利用计算机编程进行求解，获得过河问题的完整求解过程；有效地求解类似多步决策问题的作用。
关键词：多步决策 计算机求解 状态转移律 图解法 MATLAB 程序
一、问题的提出
S 个商人各带一个随从乘船过河，一只小船只能容纳K 人，由他们自己划船。商人们窃听到随从们密谋，在河的任意一岸上，只要随从的人数比商人多，就杀掉商人。但是如何乘船渡河的决策权在商人手中，商人们如何安排渡河计划确保自身安全？
二、问题的关键
解决的关键集中在商人和随从的数量上，以及小船的容量上，该问题就是考虑过河步骤的安排和数量上。各个步骤对应的状态及决策的表示法也是关键。
三、问题的分析
在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河。由于船上人数限制，这需要多步决策过程，必须考虑每一步船上的人员。动态规划法正是求解多步决策的有效方法。它要求把解的问题一层一层地分解成一级一级、规模逐步缩小的子问题。直到可以直接求出其解的子问题为止。分解成所有子问题按层次关系构成一棵子问题树．树根是原问题。原问题的解依赖于子问题树中所有子问题的解。
四、 模型假设
记第k 次过河前A 岸的商人数为X K ，随从数为Y K k=1，2，? X K ,Y K =0，1，2，3，将二维向量S K =(X K ，Y K )定义为状态．把满足安全渡河条件下的状态集合称为允许状态集合。记作S 。则
S={(X K ,Y K )|(X K =0,Y K =0,1,2,3),(X K =3,Y K =0,1,2,3),(X K =Y K =1)(X K =Y K =2)} 记第k 次过河船上的商人数为U K ，随从数为V K
将二维向量D K =(U K ,V K )定义为决策．由小船的容量可知允许决策集合（记作D)为 D={(U K ,V K )|U K +V K =l,2}={(O,1);(O,2);(1,O);(1,1);(2,O)}
五、模型建立：
动态规划法正是求解多步决策的有效方法。它要求把解的问题一层一层地分解成一级一级、规模逐步缩小的子问题。直到可以直接求出其解的子问题为止。分解成所有子问题按层次关系构成一棵子问题树．树根是原问题。原问题的解依赖于子问题树中所有子问题的解。
用动态规划法分析三名商人的过河问题。可得如下的递归树：
K=1
A(3,2)B(0,1) A(3,2)B(0.1)
K=2
A（3,1）B(0,2)
(0,1) A（2,2）B(1,1)
（0，2）
A(3,0)B(0,3)
(1,1)
(2,0)
（3,3）
（1,1
(1,0)
相同情况
K=3
(0,2)
A(3,1)B(0,2)
K=4
K=5
(0,1)
(2,0)
A(1,1)B(2,2)
K=6
A(2,2)B(1,1)
K=7
A(0,2)B(3,1)
K=8 (0,1)
（转下页）
（注解：当K 为奇数时，船在B 岸；当K 为偶数时，船在A 岸。）
通过分析该递归树，知道求解关键在于正确地写出基本的状态转移关系式和恰当的边界条件。
因为k 为奇数时，船是从A 岸驶向B 岸，k 为偶数时。船是由B 岸驶回A 岸。所以状态S K 随决策D K 变化的规律是
S K+1=S K +(-1)K D K ，k=l ，2，?，
称之为状态转移律，这样，制定过河方案就归结为如下的多步决策问题： 每一步，船由A 岸驶向B 岸或B 岸驶回A 岸，都要对船上的人员(商人U K ，随从V K 各几人)作出决策，在保证安全的前提下即两岸的商人数X K 都不比随从数Y K 少，用有限步使人员全部过河．用状态(变量)S K 表示某一岸的人员状况，决策(变量)D K 表示船上的人员状况，可以找出状态S K 随决策D K 变化的规律．这样安全过河问题就转化为：
求决策D K ∈D(k=1,2，……，n)，使得状态S K ∈S ，按照状态转移律，由初始状态S 1=(3，3)，经有限步n 到达状态S K+1=(O,O)。
模型建立：
SK+1=SK+(-1)KDK ，k=l,2，3，其中DK ∈D={(UK ,VK)|UK +VK=l ，2}，{其中SK ∈(XK ,YK)|(XK=0，YK =1，2，3)；(XK =3，YK=0,1,2,3);(XK =YK =1,2)},Sn+1 =(0,0)
这就是三个商人的过河问题模型。
A(0,3)B(3,0)
K=9
(0,2)
A(0,1)B(3,2)
A(1,1)B(2,2) A(0,2)B(3,1)
(1,0)
(0,1)
A(0,0)B(3,3)
K=10
K=11
六、模型求解：
穷举法：计算机编程（见附）
先建立编程的基本过程，然后考虑模型，再编写程序。
然后就可以得出结果了。
开始
变量赋值初始化
是
判断是否完全过河
否
选择一种可行方案，进行过河或返
回，得到新的状态
判断是不是允许状态集合中的状
态，并且还没在已经考虑的状态中
是
是
是否还有其他状态
否
结束
主程序流程图
图解法：状态s=(x,y) 16个格点
允许状态 10个●点
允许决策 移动1或2格; k 奇,左下移;
k 偶,右上移.
总共需要11步
可以得出经过11步的渡河就能达到安全渡河的目标及满足渡河的次数尽量少的条件。这11步的渡河方案就是上面程序运行结果中船上下面的一列。
八、 模型的检验
用2名商人和2名随从的过河问题的解决思路，检验3名商人和3名随从的过河问题。
九、 模型的拓展和延伸
通过三名商人和三名随从的过河问题的解决方案，可以进一步计算四名商人和四名随从的过河问题，通过计算机编程可以设计m 名商人和n 名随从的过河问题。
x
y 3 3 2 2 1 1
S 1
s n +1 d 1
d 11
十、总结
这是通过数学分析的方法解决实用问题，经过问题提出、问题假设、问题分析、模型建立、模型求解、模型检验的过程，解决商人过河问题。然后扩展延伸到n个商人的问题。
学习数学建模以来，重新认识了学习数学的乐趣，也重新认识了数学，本以为数学是单调的，枯燥的，学习了之后，发现数学是普遍存在我们生活之中的。解决现实中的问题，很多都需要数学。沉浸在数学的世界里，发现学习是有趣的；相比于机械的认识各个组织器官，建立一个数学模型解决问题是十分有趣的。
参考文献：
（1）傅清祥．《数据结构与算法》．王晓东．北京：电子工业出版社 1998．
（2）姜启瑟．《数学建模》(第二版)．北京：高等教育出版社，2000．
（3）运筹学教材编写组．《运筹学》(修订版)．北京：清华大学出版社。2001．
附：商仆过河的C程序及运行截屏:
#include
using namespace std;
struct Node
{ int nMer;
int nSer;
int length;
};
class A
{
public:
A();
~A();
void Tspt(); //过河的动作
void doLeft(int nhead,int ntail,int nlength);
private:
bool islegal(int nm,int ns); //判断是否满足约束条件，满足为true
Node *funTspt(int nm,int ns,bool flag);//添加STEP[head]可以向后延伸的节点
bool noRepeat(int nm,int ns);//没有重复返回TRUE
void funshow(int a[][2],int ntail);
bool funLeft(Node nd,int b1,int b2,int n);
void show(int s[],int p[][2],int &top,int &count,int a[]);
int head;
int n; //商仆的对数
int nB; //船最多的载人数目
Node *STEP;
};
A::~A()
{
free(STEP);
}
A::A()
{
cout<<"请输入商仆的对数S=";
F: cin>>n;
if(n==1)
{
nB=2;
cout<<"船最多载人的数目K="< } else if(n==2) { cout<<"船最多载人的数目可以取:"; for(int x=n;x<=2*n;x++) { cout< } cout< cout<<"请输入船最多载人的数目K="; cin>>nB; } else if(n==3) { cout<<"船最多载人的数目可以取:"; for(int x=n-1;x<=2*n;x++) { cout< } cout< cout<<"请输入船最多载人的数目K="; cin>>nB; } else if(n==4) { cout<<"船最多载人的数目可以取:"; for(int x=n-1;x<=2*n;x++) cout< } cout< cout<<"请输入船最多载人的数目K="; cin>>nB; } else if(n>=5&&n<=100) { cout<<"船最多载人的数目可以取:"; for(int x=4;x<=2*n;x++) { cout< } cout< cout<<"请输入船最多载人的数目K="; cin>>nB; } else if(n<1||n>100) { cout<<"本程序仅在S=(0…100)以内保证其正确性"< cout<<"请重新输入商仆的对数S="; goto F; } STEP = (Node *)malloc(sizeof(Node)*10000); memset(STEP,0,sizeof(Node)*10000); head = tail = 0; STEP[0].nMer = STEP[0].nSer = n; } int main() { cout<<"问题描述：S个商人各带一个随从乘船过河，一只小船只能容纳K人，由他们自己划船。商人们窃听到随从们密谋，在河的任意一岸上，只要随从的人数比商人多，就杀掉商人。但是如何乘船渡河的决策权在商人手中，商人们如何安排渡河计划确保自身安全？"< A a; a.Tspt(); return 0; } void A::show(int s[],int p[][2],int &top,int &count,int a[]) { if(top == -1) return ; //已找到目标状态需，输出数据 if(top == STEP[head].length) { cout<<"*********** "<<++count<<" ***********"< funshow(p,top + 1); B: top--; if(top == -1) return ; C: s[top]--; if(STEP[(s[top])].length != top)//退过了 { s[top] = a[top]; goto B; } if(funLeft(STEP[(s[top])],p[top - 1][0],p[top - 1][1],top - 1) == false) goto C; p[top][0] = STEP[(s[top])].nMer; p[top][1] = STEP[(s[top])].nSer; show(s,p,top,count,a); return ; } //在中间加入节点STEP[(s[top + 1])] if(funLeft(STEP[(s[top + 1])],p[top][0],p[top][1],top) == true)//符合条件 { top++; p[top][0] = STEP[(s[top])].nMer; p[top][1] = STEP[(s[top])].nSer; show(s,p,top,count,a); return ; } else //不符合条件 { E: s[top + 1]--; if(STEP[(s[top + 1])].length == top)//退过了，到了下一层 { s[top + 1] = a[top + 1]; D: s[top]--; if(STEP[(s[top])].length != top)//退过了，到了下一层 { for(int i = top; i <= STEP[head].length; i++) s[i] = a[i]; top--; if(top == -1) return ; goto D; } if(top == 0) return ; if(funLeft(STEP[(s[top])],p[top - 1][0],p[top - 1][1],top - 1) == false) goto D; p[top][0] = STEP[(s[top])].nMer; p[top][1] = STEP[(s[top])].nSer; show(s,p,top,count,a); return ; } if(funLeft(STEP[(s[top + 1])],p[top][0],p[top][1],top) == false) goto E; top++; p[top][0] = STEP[(s[top])].nMer; p[top][1] = STEP[(s[top])].nSer; show(s,p,top,count,a); } } void A::doLeft(int nhead,int ntail,int nlength) { int a[1000]; int a1[1000]; int sp[1000][2]; bool flag = false; memset(a,0xff,4000); memset(a1,0xff,4000); memset(sp,0xff,8000); if(STEP[head].length%2 == 0) flag = true; while(STEP[head].length == nlength - 1) { funTspt(STEP[head].nMer,STEP[head].nSer,flag); head++; } for(int i = 0; i < head + 1; i++) { a[(STEP[i].length)] = i; a1[(STEP[i].length)] = i; } sp[0][0] = sp[0][1] = n; STEP[head].nMer = STEP[head].nSer = 0; int top = 0; int count = 0; show(a1,sp,top,count,a); } bool A::funLeft(Node nd,int b1,int b2,int n) { bool flag = abs(nd.nMer - b1) + abs(nd.nSer - b2) < nB + 1 && abs(nd.nMer - b1) + abs(nd.nSer - b2) > 0; if(flag == false) return false; if(n%2 == 0 && b1 >= nd.nMer && b2 >= nd.nSer) return true; if(n%2 == 1 && b1 <= nd.nMer && b2 <= nd.nSer) return true; return false; } void A::Tspt() { Node *temp = new Node; temp = NULL; bool flag = false; while(head <= tail) { if(STEP[head].length%2 == 0) flag = true; else flag = false; temp = funTspt(STEP[head].nMer,STEP[head].nSer,flag); if(NULL != temp) break; head++; } if(head > tail) { cout<<"此问题无解!"< exit(1); } doLeft(temp->nMer,temp->nSer,temp->length);//temp->nMer表示head delete temp; } Node* A::funTspt(int nm,int ns,bool flag) {//flag == true 向对岸运输 Node *nd = NULL; int temp = 1; int tM = STEP[head].nMer; //可供运输的商人数 int tS = STEP[head].nSer; //可供运输的仆人数 if(flag == false) //向此岸运输 { tM = n - STEP[head].nMer; tS = n - STEP[head].nSer; temp = -1; } for(int i = 0; i < tM + 1 && i < nB + 1; i++)//i表示运输的商人数 { for(int j = 0; j < tS + 1 && j < nB - i + 1; j++)//j表示运输的仆人数 { if(i + j == 0) continue; int p = STEP[head].nMer - temp*i; int q = STEP[head].nSer - temp*j; if(islegal(p,q) == true && noRepeat(p,q) == true) { if(p == 0 && q == 0) { tail++; STEP[tail].length = STEP[head].length + 1; STEP[tail].nMer = p; STEP[tail].nSer = q; nd = (Node*)malloc(sizeof(Node)); nd->length = STEP[head].length + 1; nd->nMer = head; nd->nSer = tail; return nd; } tail++; STEP[tail].length = STEP[head].length + 1; STEP[tail].nMer = p; STEP[tail].nSer = q; } } } return nd; } bool A::noRepeat(int nm,int ns) { int j1 = 0; if(STEP[head].length%2 == 0) j1 = 1; for(int i = j1; i < tail + 1; i++) { if(STEP[i].length%2 == j1 && nm == STEP[i].nMer && ns == STEP[i].nSer) return false; } return true; } bool A::islegal(int nm,int ns) { //商人数少于仆人数或者商人数为0 if((nm == 0) || (nm == n) || (nm == ns)) return true; return false; } void A::funshow(int a[][2],int ntail) { cout< cout<<" 商人数仆人数"< for(int i = 0; i < ntail; i++) { cout<<"第"< if(i != ntail - 1 && i%2 == 0) cout<<" --> ("< < else if(i != ntail - 1 && i%2 == 1) cout<<" <-- ("< < } cout< } 商人过河问题数学建模 WEIHUA system office room 【WEIHUA 16H-WEIHUA WEIHUA8Q8- 作业1、2： 商人过河 一、问题重述 问题一：4个商人带着4个随从过河，过河的工具只有一艘小船，只能同时载两个人过河，包括划船的人。随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货。乘船渡河的方案由商人决定。商人们怎样才能安全过河? 问题二：假如小船可以容3人，请问最多可以有几名商人各带一名随从安全过河。 二、问题分析 问题可以看做一个多步决策过程。每一步由此岸到彼岸或彼岸到此岸船上的人员在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河。用状态变量表示某一岸的人员状况，决策变量表示船上的人员情况，可以找出状态随决策变化的规律。问题就转换为在状态的允许变化范围内（即安全渡河条件），确定每一步的决策，达到安全渡河的目标。 三．问题假设 1. 过河途中不会出现不可抗力的自然因素。 2. 当随从人数大于商人数时，随从们不会改变杀人的计划。 3．船的质量很好，在多次满载的情况下也能正常运作。 4. 随从会听从商人的调度。 四、模型构成 x(k)~第k次渡河前此岸的商人数 x(k),y(k)=0,1,2,3,4; y(k)~第k次渡河前此岸的随从数 k=1,2,….. s(k)=[ x(k), y(k)]~过程的状态 S~允许状态集合 S={(x,y) x=0,y=0,1,2,3,4; x=4,y=0,1,2,3,4;x=y=1,2,3} u(k)~第k 次渡船上的商人数 u(k), v(k)=0,1,2; v(k)~ 第k 次渡船上的随从数 k=1,2….. d(k)=( u(k), v(k))~过程的决策 D~允许决策集合 D={u,vu+v=1,2,u,v=0,1,2} 状态因决策而改变s(k+1)=s(k)+(-1)^k*d(k)~状态转移律 求d(k) D(k=1,2,….n),使s(k) S 并按转移律s(k+1)=s(k)+(-1)^k*d(k)由（4,4）到达（0,0） 数学模型： k+1k S =S +k k D （-1） （1） '4k k x x += （2） '4k k y y += （3） k.k x y ≥ （4） ''k k x y ≥ （5） 商人过河问题 /*************************************************** *M个商人与每人各带的一个仆人过河问题 *船每次至多运N个人，至少要有一人划船 *在任一岸，当商人数<仆人数时,仆人就杀人越货 *过河由商人安排运送人员及数目 *找出安全渡河的全部方法并打印(原问题中M=3，N=2) *2010-10-10 20时许（纪念伟大的双十） * LYP ***************************************************/ /****************************************************************** *本题为多步决策 *若考虑只针对人数为 M = 3 对，每次过河人数最多 N = 2 *可以证明路径中必须经坐标中(3,1)过至(1,1)点(过诃时)， *后返回至(2,2)点，再过诃至(0,2)点(只剩2个仆人) *可以先考虑(3,3)到(3,1)点 *再经(0,2)至(0,0),完成过诃(由图形的对称性关系,可以直接将(3,1)至(3,1)路径翻转,更改对应标号即可) *当然也可以用动态规划求解 *本代码不限定M,N值,可通过修改宏M,N的值,求其他商人(仆人)数与最大过河人数的全部路径 *******************************************************************/ /********************************************************************* * *商人数x < 仆人数y时遭杀人越货，过河失败 *对应可行域为: *x = 0, y = 0…M; elements[]中编号0…M *0 < x < M, y = x; elements[]中编号M+1…2M-1 *x = M, y = 0…M； elements[]中编号2M…3M *图像上表示如下:(共 3*M+1 个点),过河即从3M点到0点 *过河为左下方1/4圆区域 *返回为右上方1/4圆区域 老和尚背了一个美女过河，最后终于忍不住了, 说....... 2017-02-11 启示：学会体谅他人并不困难，只要你愿意认真地站在对方的角度和立场看问题。 4、有个老木匠即将退休，老板舍不得他，要他再建一座房子再走。老木匠虽答应，但心已不在工作上，用的是差料，出的是粗活。当房子建好，老板说这就是他退休的礼物。没想到建的竟是自己的房子，他既羞愧又后悔。 启示：其实，人生每一件事都是为自己而做，要做就做到最好。 5、老鼠掉进了半满米缸，意外让它喜不自禁。确定没有危险后，它一顿猛吃，吃完便睡。就这样，它在米缸里吃了睡、睡了吃。美好的日子总是很快地溜过去，米缸快要见底时，它终究摆脱不了大米的诱惑。最后，米吃完了，它才发现，跳出去只是梦想，一切都无能为力。 启示：我们的生活看似平坦，其实到处都是危机。 6、第一天，小白兔去钓鱼，一无所获。第二天，它又去钓鱼，还是如此。第三天它刚到，一条大鱼从河里跳出来，大叫：你要是再敢用胡萝卜当鱼饵，我就扁死你。 启示：你给的都是你自己“想”给的，而不是对方想要的，活在自己世界里的付出，不值钱! 7、一个朋友是医生，一次癌症手术，打开后发现切不了，只好再缝上。去和病人解释情况，那病人农村来的，听不懂术语，坚持认为手术过了，病就好了。只好让其出院，一年后回访，真好了，癌细胞真消失了。朋友原是医学博士，后来接着读心理学博士去了。 启示：乐观的心态是最好的手术。 8、那年，他坐在咖啡店等朋友，一位女孩走过来问：你是通过王阿姨来相亲的吗?他抬头打量一下她，正是自己喜欢的类型，心想何不将错就错，于是忙答应道：对，请坐。……结婚当天，他坦白当时自己不是去相亲的。老婆笑，说：我也不是去相亲，只是找个借口和你搭讪…… 启示：机遇来了，毫不犹豫，抓住它! 9、两只老虎，一只在笼子里，一只在荒野中。两只老虎认为自己所处环境不好，互相羡慕对方。它们决定交换身份，开始时十分快乐。但不久，两只老虎都死了：一只饥饿而死，一只忧郁而死。 启示：有时，人们对自己的幸福熟视无睹，总是把眼睛看向别人的幸福。其实，你所拥有的正是别人所欣羡的。 10、女生公开投票选班花，相貌平平的小梅发表演说：如我当选，再过几年，在座姐妹可以向自己先生骄傲的说，我上大学时候，比班花还漂亮!结果，她全票当选! 启示：说服别人支持你，不一定要证明比别人都优秀，而是让别人觉得,因为有你，他们变得更优秀更有成就感。 1、问题描述（问题与假设） 随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货.乘船渡河的方案由商人决定.商人们怎样才能安全过河? 假设：1. 过河途中不会出现不可抗力的自然因素。 2. 当随从人数大于商人数时，随从们不会改变杀人的计划。 3.船的质量很好，在多次满载的情况下也能正常运作。 4. 随从会听从商人的调度。 2、问题模型与求解（公式、图、表、算法或代码等） 模型的建立： x(k)~第k 次渡河前此岸的商人数 x(k),y(k)=0,1,2,3,4; y(k)~第k 次渡河前此岸的随从数 k=1,2,….. s(k)=[ x(k), y(k)]~过程的状态 S~允许状态集合 u(k)~第k 次渡船上的商人数 u(k), v(k)=0,1,2; v(k)~ 第k 次渡船上的随从数 k=1,2….. d(k)=( u(k), v(k))~过程的决策 D~允许决策集合 D={u,v u+v=1,2,u,v=0,1,2} 状态因决策而改变s(k+1)=s(k)+(-1)^k*d(k)~状态转移律 求d(k)∈D(k=1,2,….n),使s(k) ∈S 并按转移律s(k+1)=s(k)+(-1)^k*d(k) 由（4,4）到达（0,0） 数学模型： 模型分析： 由（2）（3）（5）可得 Yk Xk -≥-44 化简得 Yk k ≤X 关键代码： clear clc n=3;m=3;h=2; m0=0;n0=0; tic LS=0; LD=0; for i=0:n for j=0:m if i>=j&n-i>=m-j|i==n|i==0 LS=LS+1; S(LS,:)=[i j]; end if i+j>0&i+j<=h&(i>=j|i==0) LD=LD+1; D(LD,:)=[i j]; end end end N=15; Q1=inf*ones(2*N,2*N); Q2=inf*ones(2*N,2*N); t=1; le=1; q=[m n]; f0=0; while f0~=1&t 商人过河数学模型 专业信息与计算科学 班级 113010102 姓名罗彪 学号 11301010229 一、问题重述 3名商人各带一名随从乘船渡河，一只小船只能容纳二人，由他们自己划行。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。但是如何乘船渡河的大权掌握在商人们手中。商人们怎样才能安全过河呢？ 二、问题分析 商随过河问题可以视为一个多步决策过程，通过多次优化，最后获取一个全局最优的决策方案。对于每一步，即船由此岸驶向彼岸或由彼岸驶向此岸，都要对船上的人员作出决策，在保证两岸的商人数不少于随从数的前提下，在有限步内使全部人员过河。用状态变量表示某一岸的人员状况，决策变量表示船上的人员状况，可以找出状态随决策变化的规律，问题转化为在状态的允许变化范围内(即安全渡河条件)，确定每一步的决策，达到安全渡河的目标。 三、模型假设 1.每个商人和随从都会划船； 2.只有一条船，且每条船上最多只能乘坐两个人； 3.所有商人与随从之间没有矛盾，不会出现两人不愿意坐一条船的现象； 4.船在渡河的过程中不受外界环境的影响。 四、模型的建立与求解 1.模型建立 k x ~第k 次渡河前此岸的商人数，k y ~第k 次渡河前此岸的随从数 k x , k y =0,1,2,3; k =1,2,… … k S =(k x , k y , c k )~过程的状态， 其中k x , k y , c k 分别表示对应时刻此岸的商人，仆人数以及船的行进方向，其中c 取值1表示即将向彼岸运行，为0表示即将向此岸运行 S ~ 允许状态集合，S={(x , y )| x =0, y =0,1,2,3; x =3 ,y =0,1,2,3; x =y =1,2} k u ~第k 次渡船上的商人数 k v ~第k 次渡船上的随从数 k d =(k u , k v )~决策，D={(u , v )| 21≤+≤v u ,k u , k v =0,1,2} ~允许决策集合 k =1,2,… … 因为k 为奇数时船从此岸驶向彼岸，k 为偶数时船从彼岸驶向此岸，所以状态 k S 随决策k d 的变化规律是 1+k S =k S +k )1(-k d ~状态转移律 求k d ∈D(k =1,2, …n), 使k S ∈S, 并按转移律由1S =(3,3,1)到达状态 1+n S =(0,0,0(1))。 2.模型求解 本模型使用MATLAB 软件编程求解，运行结果如下 >> chouxiang 输入商人数目:3 1、三个人三只狼，要用一艘船从一边运到另一边。一次最多能运两个，返回时船不能为空船，当无论哪一边狼比人多时，狼把人吃掉，平等时不会吃。 2、三个猎人带着一只黑熊，和两只棕熊过河，船很小，每次只能载两人或两熊或一人一熊过河，三个猎人都会划船，黑熊是猎人训练过的，也回划船，但熊的数量一旦超过人的数量，熊就会吃人，怎样可以安全过河？ 3、三个大人分别带一个小孩过河。一艘船，只能载两个单位的人，如果小孩和别的大人在一起而离开自己的大人，就有危险。问如何安全过河？ 4、有一个猎人和一只狼，还有一个男人和一个女人，还有男人养的两只狗和女人养的两只猫，要过一条河，河上只有一条船，船上只能载两人(或者是一个人和一只动物)，如果猎人不在，狼就会咬死所有的人和动物，如果女人不在，男人就会打死两只猫，如果男人不在，女人就会打死两只狗，而且，只有猎人、男人、女人会开船，请问怎么过？【答案】 1、猎人和狼过，猎人回 2、猎人和一只狗过，猎人和狼回 3、男人和一只狗过，男人回 4、男人和女人过，女人回 5、猎人和狼过，男人回 6、男人和女人过，女人回 7、女人和一只猫过，猎人和狼回 8、猎人和一只猫过，猎人回 9、猎人和狼过，OK~~~~ 5、一个猎人，带了一条狗；一个男人，带了两个儿子：一个女人，带了两个女儿；他们要过河，现有一条船，每次过河只能带两个单位（两个人或一人一狗），且只有男人，女人，猎人会划船。 1．猎人不在，狗会咬任何人；2．男人不在，女人会打儿子；3．女人不在，男人会打女 儿；问；如何过河 【答案】男人女人（过河）→男人（返回）→男人儿子（过河）→男人女人（返回）→男人儿子（过河）→男人（返回）→男人女人（过河）→女人（返回）→猎人狗（过河）→男人（返回）→男人女人（过河）→女人（返回）→女人女儿（过河）→男人女人（返回）→女人女儿（过河）→女人（返回）→男人女人（过河） 6、在渡河中，有一个父亲，一个母亲，两个儿子，两个女儿，一个爷爷，一只狗，条件是：一只船只能载两个人；挣船的一定是大人；母亲不在，父亲会打死女儿；父亲不在，母亲会打死儿子；爷爷不在，狗就咬死所有人。而且只有爷爷，父亲和母亲能划船。【答案】1)爷爷带狗先过河的对面，然后爷爷把狗放下自己回来； 2)爷爷再带儿子A过河，将儿子A放下，把狗带回来； 3)爸爸带儿子B过河，将儿子B放下，自己回来； 4)爸爸带妈妈过河，上岸后，妈妈自己回来； 5)爷爷再带狗过河，爷爷和狗都上岸，爸爸回来； 6)爸爸和妈妈再过河，妈妈自己回来； 7)妈妈带女儿A过河，妈妈和女儿A都上岸，爷爷带狗回来； 8)爷爷带女儿B过河，女儿B上岸后，爷爷自己回来； 9)爷爷再带狗过河就可以了。 7、一家六口去旅行（爸爸、妈妈，两个儿子，两个女儿），在路上遇上了歹徒。幸好被一个警察所救，警察逮捕了歹徒。警察和他们正好同路，就带着歹徒一起回去。在回去的路上有一条河，河上有一个竹排，只能坐两个人。 但是：一，警察如果不和歹徒在一起，歹徒就会伤害其他人（但歹徒不会逃跑）二，母亲和儿子在一起时，如果没有父亲在场，母亲会教训儿子 三，父亲和女儿在一起时，如果没有母亲在场，父亲会欺负女儿 四，只有警察，父亲和母亲三个人会开船 八个人要如何顺利渡过这条河呢？ 基于商人过河游戏的数学建模 1提出问题 文献[1]给出一个智力游戏：“三名商人各带一个随从渡河，一只小船只能容纳二人，由他们自己划行。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。但是如何乘船的大权掌握在商人们手中。商人怎样才能安全渡河呢？”此类智力问题当然可以通过一番思考，拼凑出一个可行的方案来。文献[1]中通过图解法给出了解答，但是当商人数与随从数发生变化，船能容纳的人数不是二人时，图解法就会变得繁复而难以解决问题。 因此，将上述游戏改为n名商人各带一个随从过河，船每次至多运p个人，至少要有一个人划船，由他们自己划行。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。 但是如何乘船的大权掌握在商人们手中。商人怎样才能安全渡河的问题。 除此之外，考虑了随着船载人数的增多，以及商人与仆人的对数增多到多少时，会影响商人的安全渡河的问题。 2问题分析 由于这个虚拟的游戏已经理想化了，所以不必再作假设。我们希望能找出这类问题的规律性，建立数学模型，并通过计算机编程进行求解。安全渡河游戏可以看做是一个多步决策过程，分步优化，船由此岸驶向彼岸或由彼岸驶回此岸的每一步，都要对船上的商人和随从做出决策，在保证商人安全的前提下，在无限步内使全部人员过河。用状态表示某一岸的人员状况，决策表示船上的人员情况，可以找出状态随决策变化的规律。问题转化为在状态的允许范围内，确定每一步的决策，最后获取一个全局最优方案的决策方案，达到渡河的目标。 除此以外，我们还要找出，随着船载人数的增加，商人与仆人对数达到多少时，会影响到商人不能安全过河。这里要对船载人数进行限制，因为船载人数过多时，此智力游戏会变得相当繁复，就会失去作为游戏的本来意义。 3模型构成 商人过河functionjueche=guohe %程序开始需要知道商人和仆人数； n=input（' 输入商人数目:'）; nn=input（' 输入仆人数目:'）; nnn=input（' 输入船的最大容量:'）; ifnn>n n=input（'' 输入商人数目:'）; nn=input（' 输入仆人数目:'）; nnn=input（' 输入船的最大容量:'）; end %决策生成 jc=1;% 决策向量放在矩阵 d 中，jc 为插入新元素的行标初始为 1 ； for i=0:nnn for j=0:nnn if（i+j<=nnn）&（i+j>0）% 满足条D={（u,v） |1<=u+v<=nnn,u,v=0,1,2} d（ jc,1:3）=[i,j ，1] ；%生成一个决策向量立刻扩充为三维； d（ jc+1,1:3）=[-i,-j,-1];% 同时生成他的负向量； jc=jc+2;% 由于生成两个决策向量，则jc 要向下移动两个；end end j=0; end% 状态数组生成 kx=1;% 状态向量放在 A 矩阵中，生成方法同矩阵生成； for i=n:-1:0 for j=nn:-1:0 if((i>=j)&((n-i)>=(nn-j)))|((i==0)|(i==n))%(i>=j)&((n-i)>=(nn-j)))|((i==0)|(i==n ))为可以存在状态的约束条件 A(kx,1:3)=[i,j,1];% 生成状态数组集合D' A(kx+1,1:3)=[i,j,0]; kx=kx+2; end end j=nn; end; % 将状态向量生成抽象矩阵 k=(1/2)*size(A,1); CX=zeros(2*k,2*k); a=size(d,1); for i=1:2*k for j=1:a c=A(i,:)+d( j,:); x=find((A(:,1)==c(1))&(A(:,2)==c(2))&(A(:,3)==c(3))); 作业1、2： 商人过河 一、问题重述 问题一：4个商人带着4个随从过河，过河的工具只有一艘小船，只能同时载两个人过河，包括划船的人。随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货。乘船渡河的方案由商人决定。商人们怎样才能安全过河? 问题二：假如小船可以容3人，请问最多可以有几名商人各带一名随从安全过河。 二、问题分析 问题可以看做一个多步决策过程。每一步由此岸到彼岸或彼岸到此岸船上的人员在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河。用状态变量表示某一岸的人员状况，决策变量表示船上的人员情况，可以找出状态随决策变化的规律。问题就转换为在状态的允许变化范围内（即安全渡河条件），确定每一步的决策，达到安全渡河的目标。 三．问题假设 1. 过河途中不会出现不可抗力的自然因素。 2. 当随从人数大于商人数时，随从们不会改变杀人的计划。 3．船的质量很好，在多次满载的情况下也能正常运作。 4. 随从会听从商人的调度。 四、模型构成 x(k)~第k次渡河前此岸的商人数x(k),y(k)=0,1,2,3,4; y(k)~第k次渡河前此岸的随从数k=1,2,….. s(k)=[ x(k), y(k)]~过程的状态S~允许状态集合 S={(x,y) x=0,y=0,1,2,3,4; x=4,y=0,1,2,3,4;x=y=1,2,3} u(k)~第k次渡船上的商人数u(k), v(k)=0,1,2; v(k)~ 第k次渡船上的随从数k=1,2….. d(k)=( u(k), v(k))~过程的决策 D~允许决策集合 D={u,v |u+v=1,2,u,v=0,1,2} 状态因决策而改变s(k+1)=s(k)+(-1)^k*d(k)~状态转移律 求d(k) ∈D(k=1,2,….n),使s(k) ∈S 并按转移律s(k+1)=s(k)+(-1)^k*d(k)由（4,4）到达（0,0） 数学模型： k+1k S =S +k k D （-1） （1） '4k k x x += （2） '4k k y y += （3） k.k x y ≥ （4） ''k k x y ≥ （5） 模型分析： 由（2）（3）（5）可得 44k k x y -≥- 化简得 k k x y ≤ 数学建模作业——实验1 学院：软件学院 姓名： 学号： 班级：软件工程2015级 GCT班 邮箱： 电话： 日期：2016年5月10日 基本实验 1.椅子放平问题 依照1.2.1节中的“椅子问题”的方法，将假设中的“四腿长相同并且四脚连线呈正方形”，改为“四腿长相同并且四脚连线呈长方形”，其余假设不变，问椅子还能放平吗？如果能，请证明；如果不能，请举出相应的例子。 答：能放平，证明如下： 如上图，以椅子的中心点建立坐标，O为原点，A、B、C、D为椅子四脚的初始位置，通过旋转椅子到A’、B’、C’、D’，旋转的角度为α，记A、B两脚，C、D两脚距离地面的距离为f(α)和g(α)，由于椅子的四脚在任何位置至少有3脚着地，且f(α)、g(α)是α的连续函数，则f(α)和g(α)至少有一个的值为0，即f(α)g(α)=0，f(α)≥ 0，g(α)≥0，若f(0)＞0，g(0)=0， 则一定存在α’∈（0，π），使得 f(α’)=g(α’)=0 令α=π（即椅子旋转180°,AB 边与CD 边互换），则 f(π)=0，g(π)＞0 定义h(α)=f(α)-g(α)，得到 h(0)=f(0)-g(0)＞0 h(π)=f(π)-g(π)＜0 根据连续函数的零点定理，则存在α’∈（0，π），使得 h(α’)=f(α’)-g(α’)=0 结合条件f(α’)g(α’)=0,从而得到 f(α’)=g(α’)=0，即四脚着地，椅子放平。 2. 过河问题 依照1.2.2节中的“商人安全过河”的方法，完成下面的智力游戏：人带着猫、鸡、米过河，船除需要人划之外，至多能载猫、鸡、米之一，而当人不在场时，猫要吃鸡、鸡要吃米，试设计一个安全过河的方案，并使渡河的次数尽量的少。 答：用i =1,2,3,4分别代表人，猫，鸡，米。1=i x 在此岸，0=i x 在对岸，()4321,,,x x x x s =此岸状态，()43211,1,1,1x x x x D ----=对岸状态。安全状态集合为 : 数学模型实验—实验报告6 学院：工商学院专业：电气二类（计算机）姓名：辛文辉尚磊张亨 学号：___ 2012484019 2012484091 2012484055 ____ 实验时间：__ 3.18 ____ 实验地点：b3 一、实验项目： Matlab程序设计 安全渡河问题可以看成一个多步决策过程。每一步，即船由此岸驶向彼岸或从彼岸驶回此岸，都要对船上的人员(商人随从各几人)作出决策，在保证安全的前提下(两岸的商人数都不比随从数少)，在有限步内使人员全部过河。用状态(变量)表示某一岸的人员状况，决策(变量)表示船上的人员状况，可以找出状态随决策变化的规律。问题转化为在状态的允许变化范围内(即安全渡河条件)，确定每一步的决策，达到渡河的目的。 此类智力问题经过思考，可以拼凑出一个可行方案。但是，我们现在希望能找到求解这类问题的规律性，并建立数学模型，用以解决更为广泛的问题。 二、实验目的和要求 a.了解Matlab程序设计有关基本操作 b.掌握有关程序结构 三、实验内容 允许的状态向量 0 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 0 11 1 11 2 11 3 11 4 11 5 11 6 11 7 11 8 11 9 11 10 允许的决策向量: 0 1 0 2 0 3 0 4 0 5 0 6 1 0 1 1 2 0 2 1 2 2 3 0 3 1 3 2 3 3 4 0 4 1 4 2 5 0 5 1 6 0 过河步骤： 第1步：0商5仆过河，0商1仆返回 第2步：5商1仆过河，1商1仆返回 第3步：3商3仆过河，1商1仆返回 第4步：3商3仆过河，1商1仆返回 第5步：3商3仆过河，完成 过河过程中状态变化： 步骤此岸商此岸仆方向彼岸商彼岸仆 1 11 6 ==> -8 -3 中国游客亲历惊呼：越南美女真多可惜养不起(第1页) 中国游客亲历惊呼：越南美女真多可惜养不起来源:东方财富网|2015-07-23 01:45:00 导读： 越南女人追求金钱是第一位，她们想嫁国外改变她们自身的生活环境。越南女人如果感觉男人不好，她们就想逃跑出去，不管是她们国内还是国外都是一个样，不会给对方说什么活，就是让对方找不到人;对于花钱来说，挣钱之后基本上都想花完，之后再上班再挣钱，存钱的想法基本为0，这是对于中国人来说最难容忍的事。 本人在越南胡志明市附近乡下之处呆了一个月左右，所见如下：1、越南女人追求金钱是第一位，她们想嫁国外改 变她们自身的生活环境。 2、越南女人如果感觉男人不好，她们就想逃跑出去， 不管是她们国内还是国外都是一个样，不会给对方说什么活，就是让对方找不到人; 3、对于花钱来说，挣钱之后基本上都想花完，之后再 上班再挣钱，存钱的想法基本为0，这是对于中国人来说最难容忍的事; 4、越南女人对于婚姻来说，很厌终老，特别是对于贫困的人来讲，更是不可能一起生活。嫁于国外的60%以上的基本上会逃离原来的伴，又回到她们原来的国内，再继续找人。 5、南越胡志明附近的人家，不是太贫困，因这里的气候原因，有大量的水果和河流，可以打鱼为生，所以吃鱼天天有，很正常的事，自己买点青菜之类就可以了，这都非常便宜。吃的可能比国内有些地方还好，一餐饭有四到五个菜左右。 6、以目前的越南水平来说，吃饭是没有问题，但存钱基本上不可能，大城市消费很高工资相对低，1500元人民币来说，基本上是高工资，个别是例外; 7、越南女人非常听父母的话，把所有的钱都给家里，这是她们的共性，所以找越南老婆的人如果没有给她们钱，基本上都会跑路，莫明奇妙的消失; 8、越南女人生活在南方的，所生的女孩基本上都非常漂亮可爱。 数学建模课程作业 论文题目： 对商人过河问题的研究 指导教师：黄光辉 小组成员：黄志宇（20156260）车辆工程04班 牛凯春（20151927）电气工程05班 文逸楚（20150382）工商管理02 班 一、问题重述 3名商人带3名随从乘一条小船过河，小船每次只能承载至多两人。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。乘船渡河的方案由商人决定，商人们如何才能安全渡河呢？ 二、问题分析 本题针对商人们能否安全过河问题，需要选择一种合理的过河方案。对该问题可视为一个多步决策模型，通过对每一次过河的方案的筛选优化，最终得到商人们全部安全过到河对岸的最优决策方案。对于每一次的过河过程都看成一个随机决策状态量，商人们能够安全到达彼岸或此岸我们可以看成目标决策允许的状态量，通过对允许的状态量的层层筛选，从而得到过河的目标。 三、模型假设 1.过河途中不会出现不可抗力的自然因素。 2.当随从人数大于商人数时，随从们不会改变杀人的计划。 3．船的质量很好，在多次满载的情况下也能正常运作。 4.随从会听从商人的调度，所有人都到达河对岸。 四、符号说明 第k次渡河前此岸的商人数 第k次渡河前此岸的随从数 过程的状态向量 允许状态集合 第k次渡船上的商人数 第k次渡船上的随从数 决策向量 允许决策集合 x y 3322110s 1s n +1d 1d 11五、模型建立 本题为多步决策模型，每一次过河都是状态量的转移过程。 用二维向量表示过程的状态，其中分别表示对应时刻此岸的商人，仆人数以及船的行进方向，其中则允许状态集合: = 又将二维向量定义为决策，则允许的决策合集为: 因为k 为奇数时船从此岸驶向彼岸，k 为偶数时船从彼岸驶向此岸，所以状态随决策的变化规律是 该式称为状态转移律。 求决策，使,并按照转移律，由经过有限步n 到达状态 六、模型求解 本模型使用MATLAB 软件编程，通过穷举法获得决策方案如下(完整matlab 程序详见附录): 初始状态： 可用图片表示为：X0= 3 3状态为: S = 3 13 23 03 11 12 20 20 30 10 20 0决策为: D = 02 承诺书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）：A 我们的参赛报名号为（如果赛区设置报名号的话）：J2202 __________ 所属学校（请填写完整的全名）：江西环境工程职业学院 参赛队员（打印并签名）：1. ___________________________________ 2. ___________________________________________ 3. ___________________________________ 指导教师或指导教师组负责人（打印并签名）：教练组_____________________________ 日期：2012年8月9日赛区评阅编号（由赛区组委会评阅前进行编号）： 编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）: 赛区评阅记录（可供赛区评阅时使用）： 评 阅 人 评 分 备 注 全国统一编号（由赛区组委会送交全国前编号）： 全国评阅编号（由全国组委会评阅前进行编号）： 商人过河 摘要 本文针对商人安全渡河的问题，采用多步决策的过程建立数学模型，求解得到了在随从没有杀人越货的情况下的渡河方案。 对于本题而言，在3名商人、3名随从、船的最大容量为2的情况下，首先定义了渡河前此岸的状态，并设安全渡河条件下的状态集定义为允许状态集合，接着得到渡河方案的允许决策集合，然后得到状态随渡河方案变化的规律, 最后利用平而坐标分析法，并利用计算机进行了仿真，得到了一种商人安全渡河的方案。 但是，本文不仅仅是为了拼凑出一个可行方案，而是希望能找到求解这类问题的规律性，并建立数学模型，用以解决更为广泛的问题。基于此目的，利用了 dijkstm算法,得到最短路径的最优解。但同时由于该算法遍历计算的节点很多，所以效率低，而且当有多个最短距离时，不能够将所有符合条件的情况逐一列出。 最后，从这类问题解得趣味性、合理性进行了深入讨论，得到了“传教士与野蛮人渡河”，“印度夫妻渡河”等问题通用的模型，并将其进行了推广。这也是本文的一大特色。 关键词渡河问题状态集合决策集合平面坐标dijg算法 过河智力题 过河智力题在一条河边有猎人、狼、男人领着两个小孩，一个女人也带着两个小孩。条件为：如果猎人离开的话，狼就会把所有的人都吃掉，如果男人离开的话，女人就会把男人的两个小孩掐死，而如果女人离开，男人则会把女人的两个小孩掐死。 这时，河边只有一条船，而这个船上也只能乘坐两个人(狼也算一个人)，而所有人中，只有猎人、男人、女人会划船。则问，怎样做才能使他们全部度过这条河? 答案 第一步：猎人与狼先乘船过去，放下狼，回来后再接女人的一个孩子过去。 第二步：放下孩子将狼带回来，然后一同下船。 第三步：女人与她的另外一个孩子乘船过去，放下孩子，女人再回来接男人; 第四步：男人和女人同时过去，然后男人再放下女人，男人回来下船，猎人与狼再上去。 第五步：猎人与狼同时下船，然后，女人再上船。 第六步：女人过去接男人，男人划过去放下女人，回去接自己的一个孩子。 第七步：男人放下自己的一个孩子，猎人和狼上船，回去接男人的另外一个孩子。 第八步：猎人放下狼，接上男人的第二个小孩过去。 第九步：猎人放下小孩，再回去接回狼; 过桥智力题小明一家过一座桥，过桥时是黑夜，所以必须有灯。现在小明过桥要1秒，小明的弟弟要3秒，小明的爸爸要6秒，小明的妈妈要8秒，小明的爷爷要12秒。每次此桥最多可过两人，而过桥的速度依过桥最慢者而定，而且灯在点燃后30秒就会熄灭。问：小明一家如何过桥? 答案： 1、小明和小明弟弟过桥，需要花费3秒(小明弟弟慢，花3秒)，计t1 = 3秒，总用时tc=3秒; 2、小明回来，需要花费1秒，记t2=1秒，总用时tc=4秒; 3、小明爷爷和小明妈妈一起过桥，需要花费12秒，记t3=12，总用时tc=16秒; 4、小明弟弟回来，需要花费3秒，记t4=3秒，总用时tc=19秒; 5、小明和小明爸爸一起过桥，需要花费6秒，记t5=6秒，总用时tc=25秒; 6、小明回来，需要花费1秒，记t6=1秒，总用时tc=26秒; 7、小明和小明弟弟一起过桥，需要花费3秒，记t7=3秒，总用时tc=29秒; 这样，在第3步，小明爷爷和妈妈过桥后留下，第5步，小明爸爸过桥后留下，第7步，小明和小明弟弟过桥后，一家人成功在30秒内过桥。 关于过河的智慧故事一位信徒遇到了前所未有的困难， 组长：王鹏道110714 组员：任利伟110713、孙祎110706 小组成员负责情况： 王鹏道：选择论文题目、设计论文版面字体、分配成员任务、总结任利伟：一、问题提出、关键、分析。二、模型假设、三、模型建立孙祎：四、模型求解、五、模型的检验、拓展及延伸 2014年11月24日 摘要 为了求解3个商人和3个随从的过河问题，用数学分析方法，建立数学模型，并且加以求解，展示动态规划思想的应用步骤。最后利用计算机蝙程进行求解，获得过河问题的完整求解过程；有效地求解类似多步决策问题的作用。 关键词：多步决策计算机求解状态转移律图解法 一、 问题的提出 随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货，但是乘船渡河的方案由商人决定.商人们怎样才能安全过河? 二、 问题的关键 解决的关键集中在商人和随从的数量上，以及小船的容量上，该问题就是考虑过河步骤的安排和数量上。各个步骤对应的状态及决策的表示法也是关键。 三、 问题的分析 在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河。由于船上人数限制，这需要多步决策过程，必须考虑每一步船上的人员。动态规划法正是求解多步决策的有效方法。它要求把解的问题一层一层地分解成一级一级、规模逐步缩小的子问题。直到可以直接求出其解的子问题为止。分解成所有子问题按层次关系构成一棵子问题树．树根是原问题。原问题的解依赖于子问题树中所有子问题的解。 四、 模型假设 记第k 次过河前A 岸的商人数为X K ， 随从数为Y K k=1，2，? X K ,Y K =0，1，2，3，将二维向量S K =(X K ，Y K )定义为状态．把满足安全渡河条件下的状态集合称为允许状态集合。记作S 。则 S={(X K ,Y K )|(X K =0,Y K =0,1,2,3),(X K =3,Y K =0,1,2,3),(X K =Y K =1)(X K =Y K =2)} 记第k 次过河船上的商人数为U K 随从数为V K 将二维向量D K =(U K ,V K )定义为决策．由小船的容量可知允许决策集合（记作D)为 D={(U K ,V K )|U K +V K =l,2}={(O,1);(O,2);(1,O);(1,1);(2,O)} 五、 模型建立： 动态规划法正是求解多步决策的有效方法。它要求把解的问题一层一层地分解成一级一级、规模逐步缩小的子问题。直到可以直接求出其解的子问题为止。分解成所有子问题按层次关系构成一棵子问题树．树根是原问题。原问题的解依赖于子问题树中所有子问题的解。 P59 4.学校共1002名学生，237人住在A 宿舍，333人住在B 宿舍，432人住在C 宿舍。学生要组织一个10人的委员会，使用Q 值法分配各宿舍的委员数。 解:设P 表示人数，N 表示要分配的总席位数。i 表示各个宿舍（分别取A,B,C ），i p 表示i 宿舍现有住宿人数，i n 表示i 宿舍分配到的委员席位。 首先，我们先按比例分配委员席位。 A 宿舍为:A n = 365.21002 10237=? B 宿舍为:B n =323.31002 10333=? C 宿舍为:C n =311.4100210432=? 现已分完9人，剩1人用Q 值法分配。 5.93613 22372 =?=A Q 7.92404 33332 =?=B Q 2.93315 44322 =?=C Q 经比较可得，最后一席位应分给A 宿舍。 所以，总的席位分配应为：A 宿舍3个席位，B 宿舍3个席位，C 宿舍4个席位。 商人们怎样安全过河 由上题可求：4个商人，4个随从安全过河的方案。 解：用最多乘两人的船，无法安全过河。所以需要改乘最多三人乘坐的船。 如图所示，图中实线表示为从开始的岸边到河对岸，虚线表示从河对岸回来。商人只需要按照图中的步骤走，即可安全渡河。总共需要9步。 P60 液体在水平等直径的管内流动，设两点的压强差ΔP 与下列变量有关：管径d,ρ,v,l,μ,管壁粗糙度Δ，试求ΔP 的表达式 解：物理量之间的关系写为为()?=?,,,,,μρ?l v d p 。 各个物理量的量纲分别为 []32-=?MT L p ，[]L d =，[]M L 3-=ρ，[]1-=LT v ，[]L l =，[]11--=MT L μ，Δ是一个无量纲量。 ???? ??????-----=?0310100011110010021113173A 其中0=Ay 解得 ()T y 00012111---=， ()T y 00101102--=， ()T y 01003103--=， ()T y 10000004= 所以 l v d 2111---=ρπ，μρπ112--=v ，p v ?=--313ρπ，?=4π 因为()0,,,,,,=??p l v d f μρ与()0,,,4321=ππππF 是等价的，所以ΔP 的表达式为： ()213,ππψρv p =? 商人过河的数学模型及编程解决 摘要：M对商仆过河，一只船最多载N人，船上和岸上的仆人数都不能多于商人数，否则商人有危险。安排合理的渡河方案，保证商人能安全渡河。（可利用向量，矩阵，图解等方法） 一．问题提出： 有M对商仆乘船过河，一只船最多载N人，由商人和仆人自己划船渡河，在河的任意一岸，一旦仆人数多于商人数，仆人就可将商人杀死，谋取利益，但是乘船渡河的主动权掌握在商人们手中，商人们如何安排渡河方案，才能安全渡河？ 二．假设： 商人和仆人都会划船，天气很好，无大风大浪，船的质量很好，船桨足够很多次的运载商人和仆人。 三．参数： 1．设（x，y）是状态向量，表示任一岸的商人和仆人数，并且x，y分别要大于等于0，小于等于M。 2．设（m，n）是运载向量，表示运载的商人数和仆人数，0<=m<=N，0<=n<=N，0<=m+n<=N。 3．设用s表示所有的可取状态向量的集合。 4．设用d表示所有运载向量的集合。 5．设用表示从此岸到彼岸，作减；用表示从彼岸到此岸，作加。Sk：表示第k步可取状态向量（sk 属于s）；dk：表示第k步可取转移向量（dk属于 d）； 四．问题分析： 商仆安全渡河问题可以视为一个多步决策过程，多步决策是指决策过程难以一次完成，而是多步优化，最后获取一个全局最优方案的决策方法。对于每一步，即船由此岸驶向彼岸，或者船由彼岸驶向此岸的决策，不仅会影响到该过程的效果，而且还会影响到下一步的初始状态，从而对整个过程都会有影响。所以，在每一次过河时，就不能只从这一次过河本身考虑，还要把它看成是整个过河过程中的一个部分。在对船上的人员做决策时，要保证两岸的商人数不能少于仆人数，用最少的步伐是人员全部过河。应用状态向量和运载向量，找出状态随运载变化的规律，此问题就转化为状态在允许范围内（即安全渡河条件），确定每一次该如何过河，从而达到渡河的目标。现在我们都把它们数量化：即用数学语言来表示。 我们以3名商人为例 设第k次渡河前此岸的商人数为x k，随从数为y k，k=1，2，…，x k，y k =0，1，2，3，将二维向量S k = （x k，y k）定义为状态。安全渡河条件下的状态集合称为允许状态集合，记为S，则允许状态集合为： 日本女生的名字.txt骗子太多，傻子明显不够用了。我就是在路上斩棘杀龙游江过河攀上塔顶负责吻醒你的公主。日本女生的名字2009-03-21 12:34あ AI あい爱 AIKO あいこ爱子 AINA あいな爱奈 AIMI あいみ爱美 AIRI あいり爱理 AOI あおい葵 AKANE あかね茜 AKI あき亜纪/秋 AKIKO あきこ亜希子/亜希子/亜纪子/安喜子/安纪子/秋子 AKINA あきな秋奈 AKIRA あきら晶 AKIHA あきは秋叶 AGURI あぐり亜栗 AKO あこ亜子 ASAKA あさか浅香/朝香 ASAGI あさぎ（本意为“浅黄色”） ASAKO あさこ安佐子/浅子 ASAMI あさみ朝美/麻美/亜佐美 ASUKA あすか明日香/（男子名时译为“飞鸟”） ASUMI あすみ阿澄 AZUMI あずみ安昙 ATSUKO あつこ温子/厚子/敦子 ATSUMI あつみ敦美 ADO あど AMARI あまり AMI あみ亜美 AMIKA あみか AMIRU あみる AYA あや亜矢 AYAKA あやか绫香/彩香 AYAKO あやこ亜矢子/绚子/绫子/彩子/苑子 AYANA あやな AYANO あやの绫乃/绫野 AYAME あやめ（本意为“菖蒲”） AYUKO あゆこ鮎子/歩子 AYUMI あゆみ歩美/亜由美 AYUMU あゆむ歩 ARI あり有/亚理 ARISA ありさ亜理纱/阿丽莎(直译) AN あん安 ANJI あんじ ANJYU あんじゅ安寿 ANZU あんず杏子 ANNA あんな安奈/（外国人名时为“安娜”） い IORI いおり伊织 IKUE いくえ育恵/郁恵/郁江 IKUKO いくこ育子/郁子/ IKUMI いくみ伊久美/育美/郁美 IZUMI いずみ泉/泉美 ITSUMIいつみ逸美 IRUMI いるみ う UNO うの宇野/鹈野 URARA うららえ EIKO えいこ映子/栄子/永子/瑛子/英子 EMI えみ栄美/絵美/恵美/江美 EMIKO えみこ栄美子/栄美子/絵美子/恵美子/江美子/笑子/笑美子EMIRI えみり恵美理 ERI えり恵理/恵里 ERIKA えりか恵里香 ERIKO えりこ英里子/絵里/絵里子/恵利子/恵理子/恵里/江利子/江里子ERISA えりさ恵理沙/絵梨沙 ERINA えりな絵理奈 ERIN えりん絵凛 ERU える（还好不是ERO... = =） ERUMI えるみ ERENA えれな（外国人名“爱莲娜”） EREN えれん（外国人名“艾琳”）お OTOHA おとは音叶/音羽 OTOME おとめ乙女 か行 KAORI かおり薫理/香织/香里 KAORU かおる薫 KAZAMI かざみ风见 KAZUE かずえ一恵/和恵，和江 KAZUKO かずこ佳寿子/和子 KAZIKI かずさ和纱 KAZUNA かずな和奈/和菜 KASUMI かすみ霞/香澄 KAZUMI かずみ一美/和美 KATSUMIかつみ胜美 KANA かな加奈/香奈 KANAE かなえ香奈恵/香苗商人过河问题数学建模修订稿
商人过河问题
老和尚背了一个美女过河
数学建模题型
商人过河数学模型
过河问题
基于商人过河游戏的数学建模-最新教育文档
商人过河问题matlab程序
商人过河问题数学建模
数学建模作业——实验1
商人过河实验报告
中国游客亲历惊呼：越南美女真多可惜养不起(第1页)
数学建模 商人过河
商人过河优化模型.docx
过河智力题
数学建模商人过河__论文
数学建模与数学实验课后习题答案
最新商人过河的数学模型及编程解决
日本女生的名字