数学建模：研究商人过河问题
数学建模实验一报告
实验题目：
研究商人过河问题
一、实验目的：
编写一个程序（可以是C,C++或Mathlab）实现商人安全过河问题。
二、实验环境：
Turbo c 2.
0、Microsoft Visual C++ 6.
0、Matlab 6.0以上
三、实验要求：
要求该程序不仅能找出一组安全过河的可行方案，还可以得到所有的安全过河可行方案。并且该程序具有一定的可扩展性，即不仅可以实现3个商人，3个随从的过河问题。还应能实现
n个商人，n个随从的过河问题以及n个不同对象且每个对象有m个元素问题(说明：
对于3个商人，3个随从问题分别对应于n=2,m=3)的过河问题。从而给出课后习题5（n=4,m=1）的全部安全过河方案。
四、实验步骤：
第一步：
问题分析。这是一个多步决策过程，涉及到每一次船上的人员以及要考虑此岸和彼岸上剩余的商人数和随从数，在安全的条件下（两岸的随从数不比商人多），经有限步使全体人员过河。
第二步：
分析模型的构成。记第k次渡河前此岸的商人数为x
k，随从数为y
k，k1,2，x
k,y
k1,2n，（具有可扩展性），将定义为状态，状态集合（x
k,y
k）
（x,y）|x0,y0,1,2,3;x3,y0,1,2,3;x y1,2}成为允许状态集合（S）。S={
记第k次渡船的商人数为u
k，随从数为v
k，决策为(u
k,v
k)，安全渡河条件下，决策的集合为允许决策集合。允许决策集合记作D，所以（u,v）|1u v2,u,v0,1,2|1 驶向彼岸，k为偶数时船由彼岸驶向此岸，所以状态s k随决策d k变化的规律是s k1s k(1)dkk，此式为状态转移律。制定安全渡河方案归结为如下的多步决策模型： 求决策d k D(k1,2n)，使状态s k S按照转移xx，由初始状态s 1(3,3)经有限n步到达s n1(0,0) 第三步： 模型求解。 #include "stdio.h" #include "string.h" #include #include #include using namespace std; #include "conio.h" FILE *fp;/*设立文件指针，以便将它用于其他函数中*/ struct a{ long m,s; struct a *next; };/*数组类型a： 记录各种情况下船上的商人和仆人数，m： 代表商人数s： 代表仆人数*/struct a *jj,head;/*head为头指针的链表单元（船上的人数的各种情况的链表）*/ int n,total=0,js=0;/*total表示船上各种情况总数*/ struct aim { long m1,s1,m2,s2; int n; struct aim *back,*next;};/*用于建立双向的指针链表，记入符合的情况，m1，s1表示要过岸的商人数和仆人数；m2，s2表示过岸了的商人数和仆人数，n表示来回的次数*/int k1,k2; void freeit(struct aim *p){ struct aim *p1=p; p1=p->back; free(p); if(p1!=NULL) p1->next=NULL; return; }/*释放该单元格，并将其上的单元格的next指针还原*/ int determ(struct aim *p) { struct aim *p1=p; if(p->s1>k2)return -1;/*仆人数不能超过总仆人数*/ if(p->m1>k1)return -1;/*商人数不能超过总商人数*/ if(p->s2>k2)return -1;/*对岸，同上*/ if(p->m2>k1)return -1;/*对岸，同上*/ if(p->s1<0)return -1;/*仆人数不能为负*/ if(p->s2<0)return -1;/*商人数不能为负*/ if(p->m1<0)return -1;/*对岸，同上*/ if(p->m2<0)return -1;/*对岸，同上*/ if(p->m1!=0) if(p->s1>p->m1)return -1; if(p->m2!=0) if(p->s2>p->m2)return -1;/*两岸商人数均不能小于仆人数*/ while(p1!=NULL){ p1=p1->back; if(p1!=NULL) if(p1->n%2==p->n%2) if(p1->s1==p->s1) if(p1->s2==p->s2) if(p1->m1==p->m1) if(p1->m2==p->m2) return -1;}/*用于解决重复，算法思想： 即将每次算出的链表单元与以前的相比较，若重复，则表示出现循环*/ if(p->s1==0&&p->m1==0) if(p->n%2==0)return 1; else return -1;/*显然如果达到条件就说明ok了*/ return 0;}/*判断函数*/ int sign(int n){ if(n%2==0)return -1; return 1;}/*符号函数*/ void copyit(struct aim *p3,struct aim *p){ p3->s1=p->s1; p3->s2=p->s2; p3->m1=p->m1; p3->m2=p->m2; p3->n=p->n+1; p3->back=p; p3->next=NULL; p->next=p3; }/*复制内容函数，将p中的内容写入p3所指向的链表单元中*/ void print(struct aim *p3){ struct aim *p=p3; js++; while(p->back){p=p->back;} printf("\n第%d种方法: \n",js); fprintf(fp,"\n第%d种方法: \n",js); int count=0; while(p){ printf("%ld,%ld: :%ld,%ld\t",p->m1,p->s1,p->m2,p->s2); fprintf(fp,"%ld,%ld: :%ld,%ld\t",p->m1,p->s1,p->m2,p->s2); p=p->next; count++;}cout<<"一共有"< void trans(struct aim *p){ struct aim *p3;/*p3为申请的结构体指针*/ struct a *fla; int i,j,f; fla= p3=(struct aim *)malloc(sizeof(struct aim)); f=sign(p->n); for(i=0;i fla=fla->next; copyit(p3,p); p3->s1-=fla->m*f; p3->m1-=fla->s*f; p3->s2+=fla->m*f; p3->m2+=fla->s*f;/*运算过程，即过河过程*/ j=determ(p3);/*判断，j记录判断结果*/ if(j==-1){ if(i else{ freeit(p3); break;}} int count1=0; if(j==1){if(i count1++; continue;} else{print(p3); freeit(p3); break;} //cout< printf("%d",count1); printf("\n");}if(j==0)trans(p3);}return; }/*转移函数，即将人转移过河*/ /*n=0*/ void main() { struct aim *p,*p1;int j,a,e,f; struct a *flag;/*flag是用与记录头指针*/ FILE*fpt; if((fpt=fopen("c: result.dat","w+"))==0){ printf("can't creat it\n"); exit (0);} fp=fpt; system("cls"); printf("问题描述： 三个商人各带一个随从乘船过河，一只小船只能容纳X人，由他们自己划船。三个商人窃听到随从们密谋，在河的任意一岸上，只要随从的人数比上人多，就杀掉商人。但是如何乘船渡河的决策权在商人手里，商人们如何安排渡河计划确保自身安全？\n"); printf("\n"); p=(struct aim *)malloc(sizeof(struct aim)); p->back=NULL; p->next=NULL; p->s2=0; p->m2=0; p->n=1;/*设立初始头指针*/ printf("please input the total of people on the board\n"); fprintf(fp,"\n请输入船上的人数\n"); scanf("%d",&n); fprintf(fp,"\n%d\n",n); flag= for(e=0;e<=n;e++) for(f=0;f<=n;f++) if(e+f>0&&e+f<=n) { total++; jj=(struct a*)malloc(sizeof(struct a)); jj->m=e; jj->s=f; flag->next=jj; jj->next=NULL; flag=jj;}/*********************************/ printf("please input the total of merchant and salvent as follow: mechant,salvent;\n"); fprintf(fp,"\nplease input the total of merchant and salvent as follow: mechant,salvent;\n");scanf("%ld,%ld",&p->m1,&p->s1); fprintf(fp,"\n%ld,%ld\n",p->m1,p->s1); /**********************************/ k1=p->m1; k2=p->s1; trans(p); fclose(fpt); getch();}第一步： 三个商人，三个随从的模型求解答案为： 运行后的结果为： 第1种方案： (3,3)到(0,0)、(3,1)到(0,2)、(3,2)到(0,1)、(3,0)到(0,3)、(3,1)到(0,2)、 (1,1)到(2,2)、(2,2)到(1,1)、(0,2)到(3,1)、(0,3)到(3,0)、(0,1)到(3,2)、(0,2)到(3,1)、(0,0)到(3,3) 第2种方案： (3,3)到(0,0)、(3,1)到(0,2)、(3,2)到(0,1)、(3,0)到(0,3)、(3,1)到(0,2)、(1,1)到(2,2)、(2,2)到(1,1)、(0,2)到(3,1)、(0,3)到(3,0)、(0,1)到(3,2)、(1,1)到(2,2)、(0,0)到(3,3) 第3种方案： (3,3)到(0,0)、(2,2)到(1,1)、(3,2)到(0,1)、(3,0)到(0,3)、(3,1)到(0,2)、(1,1)到(2,2)、(2,2)到(1,1)、(0,2)到(3,1)、(0,3)到(3,0)、(0,1)到(3,2)(、0,2)到(3,1)、(0,0)到(3,3) 第4种方案： (3,3)到(0,0)、(2,2)到(1,1)、(3,2)到(0,1)、(3,0)到(0,3)、(3,1)到(0,2)、(1,1)到(2,2)、(2,2)到(1,1)、(0,2)到(3,1)、(0,3)到(3,0)、(0,1)到(3,2)、(1,1)到(2,2)(0,0)到(3,3) 第二步： 四个商人三个随从，其结果为： 第1种方法: 4,3::0,03,2::1,14,2::0,12,2::2,13,2::1,1 2,1::2,22,2::2,10,2::4,10,3::4,00,1::4,2 1,1::3,20,0::4,3一共有12步完成 第2种方法: 4,3::0,03,2::1,14,2::0,12,2::2,13,2::1,1 2,1::2,22,2::2,10,2::4,10,3::4,00,1::4,2 2,1::2,21,0::3,31,1::3,20,0::4,3一共有14步完成 第3种方法: 4,3::0,03,2::1,14,2::0,12,2::2,13,2::1,1 2,1::2,22,2::2,10,2::4,10,3::4,00,1::4,2 0,2::4,10,0::4,3一共有12步完成 第4种方法: 4,3::0,03,2::1,14,2::0,12,2::2,13,2::1,1 2,1::2,22,2::2,11,1::3,22,1::2,20,1::4,2 1,1::3,20,0::4,3一共有12步完成 第5种方法: 4,3::0,03,2::1,14,2::0,12,2::2,13,2::1,1 2,1::2,22,2::2,11,1::3,22,1::2,20,1::4,2 0,2::4,10,0::4,3一共有12步完成 第6种方法: 4,3::0,03,2::1,14,2::0,12,2::2,13,2::1,1 2,1::2,22,2::2,11,1::3,22,1::2,21,0::3,3 1,1::3,20,1::4,20,2::4,10,0::4,3一共有14步完成第7种方法: 4,3::0,03,2::1,14,2::0,12,2::2,13,2::1,1 2,1::2,22,2::2,11,1::3,22,1::2,21,0::3,3 1,1::3,20,0::4,3一共有12步完成 第8种方法: 4,3::0,03,2::1,14,2::0,14,0::0,34,1::0,2 2,1::2,22,2::2,10,2::4,10,3::4,00,1::4,2 1,1::3,20,0::4,3一共有12步完成 第9种方法: 4,3::0,03,2::1,14,2::0,14,0::0,34,1::0,2 2,1::2,22,2::2,10,2::4,10,3::4,00,1::4,2 2,1::2,21,0::3,31,1::3,20,0::4,3一共有14步完成 第10种方法: 4,3::0,03,2::1,14,2::0,14,0::0,34,1::0,2 2,1::2,22,2::2,10,2::4,10,3::4,00,1::4,2 0,2::4,10,0::4,3一共有12步完成第11种方法: 4,3::0,0 2,1::2,2 1,1::3,2 第12种方法: 4,3::0,0 2,1::2,2 0,2::4,1 第13种方法: 4,3::0,0 2,1::2,2 1,1::3,2 第14种方法: 4,3::0,0 2,1::2,2 1,1::3,2 第15种方法: 4,3::0,0 2,1::2,2 1,1::3,2 第16种方法: 4,3::0,0 2,1::2,2 2,1::2,2 第17种方法: 4,3::0,0 2,1::2,2 0,2::4,1 第18种方法: 4,3::0,0 2,1::2,2 1,1::3,2 第19种方法: 4,3::0,0 2,1::2,2 0,2::4,13,2::1,14,2::0,14,0::0,3 2,2::2,11,1::3,22,1::2,2 0,0::4,3一共有12步完成3,2::1,14,2::0,14,0::0,3 2,2::2,11,1::3,22,1::2,2 0,0::4,3一共有12步完成 3,2::1,14,2::0,14,0::0,3 2,2::2,11,1::3,22,1::2,2 0,1::4,20,2::4,10,0::4,3 3,2::1,14,2::0,14,0::0,3 2,2::2,11,1::3,22,1::2,2 0,0::4,3一共有12步完成 3,2::1,13,3::1,02,2::2,1 2,2::2,10,2::4,10,3::4,0 0,0::4,3一共有12步完成 3,2::1,13,3::1,02,2::2,1 2,2::2,10,2::4,10,3::4,0 1,0::3,31,1::3,20,0::4,3 3,2::1,13,3::1,02,2::2,1 2,2::2,10,2::4,10,3::4,0 0,0::4,3一共有12步完成 3,2::1,13,3::1,02,2::2,1 2,2::2,11,1::3,22,1::2,2 0,0::4,3一共有12步完成 3,2::1,13,3::1,02,2::2,1 2,2::2,11,1::3,22,1::2,2 0,0::4,3一共有12步完成4,1::0,2 0,1::4,2 4,1::0,2 0,1::4,2 4,1::0,2 1,0::3,3 一共有14步完成 4,1::0,2 1,0::3,3 3,2::1,1 0,1::4,2 3,2::1,1 0,1::4,2 一共有14步完成 3,2::1,1 0,1::4,2 3,2::1,1 0,1::4,2 3,2::1,1 0,1::4,2 第20种方法: 4,3::0,03,2::1,13,3::1,02,2::2,13,2::1,1 2,1::2,22,2::2,11,1::3,22,1::2,21,0::3,3 1,1::3,20,1::4,20,2::4,10,0::4,3一共有14步完成第21种方法: 4,3::0,03,2::1,13,3::1,02,2::2,13,2::1,1 2,1::2,22,2::2,11,1::3,22,1::2,21,0::3,3 1,1::3,20,0::4,3一共有12步完成 第22种方法: 4,3::0,0 4,0::0,3 0,3::4,0 第23种方法: 4,3::0,0 4,0::0,3 0,3::4,0 0,0::4,3 第24种方法: 4,3::0,0 4,0::0,3 0,3::4,0 第25种方法: 4,3::0,0 4,0::0,3 2,1::2,2 第26种方法: 4,3::0,0 4,0::0,3 2,1::2,2 第27种方法: 4,3::0,0 4,0::0,3 2,1::2,2 0,0::4,3 第28种方法: 4,3::0,0 4,0::0,3 2,1::2,2 第29种方法: 4,3::0,0 2,2::2,1 0,3::4,0 第30种方法: 4,3::0,03,2::1,13,3::1,0 0,1::4,21,1::3,2 3,2::1,13,3::1,0 4,1::0,22,1::2,2 0,1::4,22,1::2,2 一共有16步完成3,2::1,13,3::1,0 4,1::0,22,1::2,2 0,1::4,20,2::4,1 3,2::1,13,3::1,0 4,1::0,22,1::2,2 0,1::4,21,1::3,2 3,2::1,13,3::1,0 4,1::0,22,1::2,2 0,1::4,20,2::4,1 3,2::1,13,3::1,0 4,1::0,22,1::2,2 1,0::3,31,1::3,2 一共有16步完成3,2::1,13,3::1,0 4,1::0,22,1::2,2 商人过河问题数学建模 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） 1问题描述(问题与假设) 随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货决定.商人们怎样才能安全过河？ 假设：1.过河途中不会出现不可抗力的自然因素。 2. 当随从人数大于商人数时，随从们不会改变杀人的计划。 3. 船的质量很好，在多次满载的情况下也能正常运作。 4. 随从会听从商人的调度。 2、问题模型与求解(公式、图、表、算法或代码等) 模型的建立： 由(4,4)到达(0,0) 数学模型: 纭产70 ⑴ 叫—J - 4 (2) 2 H y\ —■) (4) 模型分析： 由(2)( 3)( 5)可得 4 Xk 4 Yk 化简得Xk Yk 关键代码： clear clc n=3;m=3;h=2; .乘船渡河的方案由商人 x(k)~第k次渡河前此岸的商人数y(k)~第k次渡河前此岸的随从数s(k)=[ x(k), y(k)]~ 过程的状态 u(k)~第k次渡船上的商人数v(k)~第k次渡船上的随从数 d(k)=( u(k), v(k))~ 过程的决策 D={u,v u+v=1,2,u,v=0,1,2} 状态因决策而改变s(k+1)=s(k)+ 求d(k) D(k=1,2,….n),使s(k) x(k),y(k)=0,1,2,3,4; k=1,2，… S~允许状态集合 u(k), v(k)=0,1,2; k=1,2 ….. D~允许决策集合 -1)A k*d(k)~状态转移律 S 并按转移律s(k+1)=s(k)+(-1)Ak*d(k) 叮叮小文库 m0=0 ;n 0=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; Q仁inf*on es(2*N,2*N); Q2=i nf*on es(2*N,2*N); t=1; le=1; q=[m n]; f0=0; while f0~=1 &t 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 重庆大学本科生数学模型作业报告人猫鸡米渡河问题的数学模型 组员：唐新 赵广志 < 指导教师：黄光辉 人猫鸡米渡河问题的数学模型 一、摘要： 本文主要对数学建模基础模型跟“商人过河”类似简单问题：人带着猫、鸡、米过河，船除需要人划之外，至多能载猫、鸡、米三者之一，而当人不在场时猫要吃鸡、鸡要吃米。试设计一个安全过河方案，建立数学模型，并使渡河次数尽量地少。模仿“商人过河”的模型设计出新的数学模型。 二、问题的重述 人带着猫、鸡、米过河，船除需要人划之外，至多能载猫、鸡、米三者之一，而当人不在场时猫要吃鸡、鸡要吃米。试设计一个安全过河方案，并使渡河次数尽量地少。 关键词：人不在场时猫要吃鸡、鸡要吃米，船需人划，穷举法 三、模型假设 不考虑外界其他影响，只考虑问题所述的条件: 1、船除需要人划之外，至多能载猫、鸡、米三者之一 2、当人不在场时猫要吃鸡、鸡要吃米 四、符号说明 五、问题分析 安全过河问题可以看着是一个多部决策的过程。每作出一步决策，都必须保证船、人、猫、鸡、米能满足题设条件。否则，不仅难以实现过河的最优化，而且还容易出现事物的不安全性。因此，在保证安全的前提下，即猫、鸡在一起时，人要在场，鸡、米在一起时，人也要在场，用状态变量s 表示某一岸的状况，决策变量d 表示是乘车方案，我们容易得到s 和d 的关系，其中问题的转化要在允许变化范围内，确定每一步的决策关系，从而达到渡河的最优目标。 六、模型建立与求解 Ⅰ. 模型的建立： 人、猫、鸡、米分别记为4,3,2,1=i ，当i 在此岸时记1=i x ，否则记 0=i x ，则此岸的状态可用()4321,,,x x x x s =表示。记s 的反状态为()4321'1,1,1,1x x x x s ----=，允许状态集合为 ()()()()(){}0,1,0,1,1,1,0,1,1,0,1,1,0,1,1,1,1,1,1,1=S （1） 以及他们的5个反状态。 决策为乘船方案，记作()4321,,,u u u u d =，当i 在船上时记1=i u ，否则记 0=i u ，允许决策集合为 ()()()(){}0,0,0,1,1,0,0,1,0,1,0,1,0,0,1,1=D （2） 记第k 次渡河前此岸的状态为k s ，第k 次渡河的决策为k d ，则状态转移律为 ()k d k k s k s 11-+=+， （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提出问题 文献[1]给出一个智力游戏：“三名商人各带一个随从渡河，一只小船只能容纳二人，由他们自己划行。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。但是如何乘船的大权掌握在商人们手中。商人怎样才能安全渡河呢？”此类智力问题当然可以通过一番思考，拼凑出一个可行的方案来。文献[1]中通过图解法给出了解答，但是当商人数与随从数发生变化，船能容纳的人数不是二人时，图解法就会变得繁复而难以解决问题。 因此，将上述游戏改为n名商人各带一个随从过河，船每次至多运p个人，至少要有一个人划船，由他们自己划行。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。 但是如何乘船的大权掌握在商人们手中。商人怎样才能安全渡河的问题。 除此之外，考虑了随着船载人数的增多，以及商人与仆人的对数增多到多少时，会影响商人的安全渡河的问题。 2问题分析 由于这个虚拟的游戏已经理想化了，所以不必再作假设。我们希望能找出这类问题的规律性，建立数学模型，并通过计算机编程进行求解。安全渡河游戏可以看做是一个多步决策过程，分步优化，船由此岸驶向彼岸或由彼岸驶回此岸的每一步，都要对船上的商人和随从做出决策，在保证商人安全的前提下，在无限步内使全部人员过河。用状态表示某一岸的人员状况，决策表示船上的人员情况，可以找出状态随决策变化的规律。问题转化为在状态的允许范围内，确定每一步的决策，最后获取一个全局最优方案的决策方案，达到渡河的目标。 除此以外，我们还要找出，随着船载人数的增加，商人与仆人对数达到多少时，会影响到商人不能安全过河。这里要对船载人数进行限制，因为船载人数过多时，此智力游戏会变得相当繁复，就会失去作为游戏的本来意义。 3模型构成 数学建模课程作业 论文题目： 对商人过河问题的研究 指导教师：黄光辉 小组成员：黄志宇（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 数学建模作业——实验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 ----=对岸状态。安全状态集合为 : 组长：王鹏道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)} 五、 模型建立： 动态规划法正是求解多步决策的有效方法。它要求把解的问题一层一层地分解成一级一级、规模逐步缩小的子问题。直到可以直接求出其解的子问题为止。分解成所有子问题按层次关系构成一棵子问题树．树根是原问题。原问题的解依赖于子问题树中所有子问题的解。 数学建模作业（四）——商人过河问题 一．问题描述 有四名商人各带一名仆人过河，但船最多能载二人，商人已获得仆人的阴谋：在河的任一岸，只要仆人数超过商人数，仆人会将商人杀死并窃取财物且安排如何乘船的权力掌握在商人手中。试为商人制定一个安全过河的方案。 二．解决方案 用递归的源程序如下： 开始时商人，强盗所在的河的这边设为0状态，另一边设为1状态（也就是船开始时的一边设为0，当船驶到对岸是设为1状态，在这两个状态时，都必须符合条件） #include PPointer1=newnode; PPointer2=newnode; } else { PPointer2-> next=newnode; PPointer2=newnode; } } void Pop() /*弹栈*/ { link pointer; if(PPointer1==PPointer2) { free(PPointer1); PPointer1=NULL; PPointer2=NULL; } pointer=PPointer1; while(pointer-> next!=PPointer2) pointer=pointer-> next; free(PPointer2); PPointer2=pointer; PPointer2-> next=NULL; } int history(int a,int b,int n) /*比较输入的数据和栈中是否有重复的*/ { link pointer; if(PPointer1==NULL) return 1; else { pointer=PPointer1; while(pointer!=NULL) { if(pointer-> x==a&&pointer-> y==b&&pointer-> state==n) return 0; 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 =? 数学建模作业 班级：数学131 姓名：丁延辉 学号：13190122 （二）商人过河Matlab代码 三个商人三个随从 z=zeros(30,3); %z为由(a,b,c)的列向量组成的3行30列数组，初始化为0矩阵，a,b,c代表此刻此岸的商人，仆人数量以及船的运行状态，c=1表示即将向彼岸运行 m=zeros(1,20); %m为一维行向量，初始化为1矩阵，用于在后面的程序中判断第k次选择的乘船方案 d=[0,1,1;0,2,1;1,0,1;1,1,1;2,0,1]; %共有5种可以选择的乘船方案，最后面一列全为1，即用于在后面表示使得z(k,3)的取值保持随着k的奇偶性保持着0-1变换. z(1,:)=[3,3,1]; %初始状态为[3,3,1] k=1; m(k)=1; %第一次默认的乘船方案为决策1——d(1) flag=1; %用于在后面判断是否成功找到方案 answer=0; %用于在后面判断是否找到 答案 while k>0 %保持k>0 if m(k)>5 flag=0; break; end p=0; z(k+1,:)=z(k,:)+(-1)^k*d(m(k),:); %每一次的运算规则都是z(k+1)=z(k)-(-1)^k*d(m(k),:),d(m(k),:)表示决策方案 a=z(k+1,1); %将当前情况的矩阵数值复制给a商人,b仆人 b=z(k+1,2); c=z(k+1,3); if (a==3&&(b==0||b==1||b==2||b==3))||(a==1&&b==1)||(a==2&&b==2 )||(a==0&&(b==0||b==1||b==2||b==3)) %判断(a,b)是否符合限定情况 for j=1:k %判断是否此岸a,b,c与之前有重复，如果是，结束此次循环，重新选择乘船方案 if a==z(j,1)&&b==z(j,2)&&c==z(j,3) if m(k)~=5 %决策方案只有5种，所以m(k)<=5， 讨论资金积累、国民收入与人口增长的关系 班级：2009级数学与应用数学 黄全（组长）: P092314746 邱亚彪: P091712712 谢志成:P091712679 央金:P091715381 罗国庭:P091712739 讨论资金积累、国民收入与人口增长的关系 摘要 如何保证人口增长对国民收入影响的正效应和国民平均收入持续性增长，一直是全国人民所共同关注的问题。本文对资金积累、国民收入和人口增长三者之间的关系进行讨论，通过导数结合三者之间存在的基本规律，建立相应的微分方程，利用微分方程法给出方程，由matlab解得资金积累、国民收入与人口增长的关系。通过掌握该关系，确定资金积累的增长率大于人口增长率时国民收入才会增长，从而更好地调整人口出身率、控制人口的数量和人口质量，保证我国人口增长与国民收入增长之间的适当的比例关系，使得国民平均持续性增长，促进社会经济的迅速发展，提高人民的生活质量，为整个社会的长远战略需求做贡献。 关键字：资金积累状态转移律图解法微分方程决策 一、 问题重述 讨论资金积累、国民收入与人口增长的关系 （1）若国民平均收入x 与按人口平均资金积累y 成正比，说明仅当总资金积累 的相对增长率k 大于人口的相对增长率r 时，国民平均收入才是增长的. （2）作出k(x)和r(x)的示意图，说明二曲线交点是平衡点，讨论它的稳定性。 （3）分析人口激增会引起什么后果 二、符号说明 1x : t 时刻总资金累积量，2x ：t 时刻人口数量， 3x ：国民平均收入量 ，k ：总资金的相对增长率 r ：人口的相对增长率 三 、模型的假设 在一定时期后,增长的人口数量为:：22x rx '=； 总资金的增长量为：11x kx '= ； 四、问题的分析 在社会主义发展的初级阶段，国民收入是指一定时期（通常为1年）内，物质生产部门劳动者新创造的价值,它是物质资料生产进一步发展和人口再生产条件改善的物质基础。在其他条件已定的情况下,国民收入总量愈多,人均消费基金和积累基金也越多，从而有利于人们生活的改善和技术装备水平的提高，也有利于人口数量的控制和人口质量的提高。人口增长从 3个方面影响国民收入的增减： ① 人口或劳动者数量的多少； ② 每个劳动者技术装备水平的高低； ③ 劳动者节省消耗和管理才能的大小。 国民收入又分为资金的累积和消费，累积资金=国民收入错误！未找到引用源。消费资金，而消费资金=基本消费资金错误！未找到引用源。人口发展速度。因此， 为增加人均国民收入，增强一国的经济实力和提高人民生活水平，要在大力发展经济、增加生产的基础上合理地调节人口增长。 作业1、２: 商人过河 一、问题重述 问题一:４个商人带着4个随从过河，过河得工具只有一艘小船，只能同时载两个人过河，包括划船得人。随从们密约，在河得任一岸, 一旦随从得人数比商人多, 就杀人越货.乘船渡河得方案由商人决定.商人们怎样才能安全过河？ 问题二:假如小船可以容３人，请问最多可以有几名商人各带一名随从安全过河。 二、问题分析 问题可以瞧做一个多步决策过程。每一步由此岸到彼岸或彼岸到此岸船上得人员在安全得前提下（两岸得随从数不比商人多),经有限步使全体人员过河。用状态变量表示某一岸得人员状况，决策变量表示船上得人员情况,可以找出状态随决策变化得规律。问题就转换为在状态得允许变化范围内(即安全渡河条件)，确定每一步得决策,达到安全渡河得目标。 三.问题假设 1、过河途中不会出现不可抗力得自然因素。 2、当随从人数大于商人数时,随从们不会改变杀人得计划。 3。船得质量很好，在多次满载得情况下也能正常运作。 4、随从会听从商人得调度。 四、模型构成 x（k)～第k次渡河前此岸得商人数x(k），ｙ（k)=0，1，2,3,4； y(k）~第ｋ次渡河前此岸得随从数k＝1，２，…、、 s（k）=［x（k), y（k）］～过程得状态Ｓ~允许状态集合Ｓ＝{(x，ｙ） x=０,y=０,１,２,3，４;ｘ=4，y=０,1,2，３，４；x=y＝１，２，3｝ u（k）~第ｋ次渡船上得商人数u（k）, ｖ（ｋ)=0,1，２; ｖ(k）~ 第k次渡船上得随从数k＝1，2…、、 d（k）＝(u(ｋ), v（k)）～过程得决策D～允许决策集合D={u，ｖ｜u+v=1,2,u,v=0,1，2｝ 状态因决策而改变s（k+1）＝s（k）+(-１）^ｋ*d（k)~状态转移律求d（k)∈Ｄ(k＝1，２,…、n),使s(ｋ)∈S并按转移律s（k+1）=s （k）+(-１)＾k＊ｄ（k）由(４,4）到达（０，０) 数学模型: （1) (2） （３) （４） （５） 模型分析： 由（2）（３）（５）可得 化简得 综合（4）可得 2011高教社杯全国大学生数学建模竞赛 承诺书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）：西京学院 参赛队员(打印并签名) ：1. 邹高永 2. 张大伟 3. 钱晓东 指导教师或指导教师组负责人(打印并签名)： 日期：年月日赛区评阅编号（由赛区组委会评阅前进行编号）： 2011高教社杯全国大学生数学建模竞赛 编号专用页 赛区评阅编号（由赛区组委会评阅前进行编号）： 赛区评阅记录（可供赛区评阅时使用）： 评 阅 人 评 分 备 注 全国统一编号（由赛区组委会送交全国前编号）： 全国评阅编号（由全国组委会评阅前进行编号）： 商人过河 摘要 本文针对商人安全渡河的问题，采用多步决策的过程建立数学模型，求解得到了在随从没有杀人越货的情况下的渡河方案。 对于本题而言，在3名商人、3名随从、船的最大容量为2的情况下，首先定义了渡河前此岸的状态，并设安全渡河条件下的状态集定义为允许状态集合，接着得到渡河方案的允许决策集合，然后得到状态随渡河方案变化的规律，最后利用平面坐标分析法，并利用计算机进行了仿真，得到了一种商人安全渡河的方案。 但是，本文不仅仅是为了拼凑出一个可行方案，而是希望能找到求解这类问题的规律性，并建立数学模型，用以解决更为广泛的问题。基于此目的，利用了dijkstra算法，得到最短路径的最优解。但同时由于该算法遍历计算的节点很多，所以效率低，而且当有多个最短距离时，不能够将所有符合条件的情况逐一列出。 最后，从这类问题解得趣味性、合理性进行了深入讨论，得到了“传教士与野蛮人渡河”，“印度夫妻渡河”等问题通用的模型，并将其进行了推广。这也是本文的一大特色。 关键词渡河问题状态集合决策集合平面坐标dijkstra算法 《数学模型实验》实验报告 姓名：王佳蕾学院：数学与信息科 学学院 地点：主楼402 学号：055专业：数学类时间：2017年4 月16日 实验名称： 商人和仆人安全渡河问题的matlab实现 实验目的： 1.熟悉matlab基础知识，初步了解matlab程序设计； 2.研究多步决策过程的程序设计方法； 3.（允许）状态集合、（允许）决策集合以及状态转移公式的matlab表示；实验任务： 只有一艘船，三个商人三个仆人过河，每一次船仅且能坐1-2个人，而且任何一边河岸上仆人比商人多的时候，仆人会杀人越货。怎么在保证商人安全的情况下，六个人都到河对岸去，建模并matlab实现。 要求：代码运行流畅，结果正确，为关键语句加详细注释。 实验步骤： 1.模型构成 2.求决策 3.设计程序 4.得出结论（最佳解决方案） 实验内容： （一）构造模型并求决策 设第k次渡河前此岸的商人数为xk，随从数为yk，k=1,2,...，xk，yk=0,1,2,3.将二维向量sk=（xk，yk）定义为状态，安全渡河条件下的状态集合称为允许状态集合，记作S，S 对此岸和彼岸都是安全的。 S={(x,y)|x=0,y=0,1,2,3;x=3,y=0,1,2,3;x=y=1,2} 设第k次渡船上的商人数为uk，随从数vk，将二维变量dk=（uk，vk）定义为决策，允许决策集合记为D,由小船的容量可知， D={(u,v)|1<=u+v<=2,u,v=0,1,2} k为奇数时，船从此岸驶向彼岸，k为偶数时，船从彼岸驶向此岸，状态sk随决策变量dk的变化规律为sk+1=sk+(-1)^k*dk（状态转移律） 这样制定安全渡河方案归结为如下的多步决策模型： 求决策dk∈D(k=1,2,...,n)，使状态sk∈S，按照转移律，由初始状态s1=（3,3）经有限步n到达状态sn+1=（0,0）。 （二）程序设计 14对商仆过河问题 题目 有14名商人各带一名仆人要过河，但船最多能载4人。商人已获得仆人的阴谋：在河的任意一岸，只要仆人数超过商人数，仆人会将商人杀死并窃取货物。安排如何乘船的权利权利在商人手上，试为商人制定一个安全的过河方案。 一．摘要 n对商仆过河，一只船最多载m人，船上和岸上的仆人数都不能多于商人数，否则商人有危险。安排合理的渡河方案，保证商人能安全渡河。（可利用向量，矩阵，图解等方法）。 二．问题提出： 有14对商仆乘船过河，一只船最多载4人，由商人和仆人自己划船渡河，在河的任意一岸，一旦仆人数多于商人数，仆人就可将商人杀死，谋取利益，但是乘船渡河的主动权掌握在商人们手中，商人们如何安排渡河方案，才能安全渡河 三．问题分析 商仆安全渡河问题可以视为一个多步决策过程，多步决策是指决策过程难以一次完成，而是多步优化，最后获取一个全局最优方案的决策方法。对于每一步，即船由此岸驶向彼岸，或者船由彼岸驶向此岸的决策，不仅会影响到该过程的效果，而且还会影响到下一步的初始状态，从而对整个过程都会有影响。所以，在每一次过河时，就不能只从这一次过河本身考虑，还要把它看成是整个过河过程中的一个部分。在对船上的人员做决策时，要保证两岸的商人数不能少于仆人数，用最少的步伐是人员全部过河。应用状态向量和运载向量，找出状态随运载变化的规律，此问题就转化为状态在允许范围内（即安全渡河条件），确定每一次该如何过河，从而达到渡河的目标。现在我们都把它们数量化：即用数学语言来表示。 四．模型假设与符号假设 （一）模型假设 商人和仆人都会划船，天气很好，无大风大浪，船的质量很好，船桨足够很多次的运载商人和仆人。 （二）符号假设 设（x，y）是状态向量，表示任一岸的商人和仆人数，且x，y 分别要大于等于0，小于等于M。 1.设（m，n）是运载向量，表示运载的商人数和仆人数，0<=m<=N，0<=n<=N，0<=m+n<=N。 2.设用s表示所有的可取状态向量的集合。 3.设用d表示所有运载向量的集合。 4.设用表示从此岸到彼岸，作减；用表示从彼岸到此岸，作加。S k：表示第k步可取状态向量（S k属于s）；d k：表示第k步可取转移向量（d k属于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，则允许状态集合为：S={（x，y）|x = 0或3，y = 0，1，2，3，x = y = 1，2} （1）又设第k次渡船上的商人数为u k，随从数为v k，将二维向量 d k=（u k+ v k）定义为决策。则允许决策集合为： D={（u，v）| u + v = 1，2} （2） 数学建模商人过河(hjh) 问题 随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货. 乘船渡河的方案由商人决定.商人们怎样才能安全过河? 分析问题 （1）,数据及其关系？（2）如何存储？（3）过程中数据上的操作？ （4）操作过程中需借助什么结构实现？ 解答 （1）数据：河两岸的商人数x∈（0，3）和随从人数y∈（0，3） 关系：线性关系 （2）存储：用二维数组来实现。 （3）操作：前进（过河）、后退（返回） （4）操作过程中需借助栈结构实现 具体分析 此岸商人数与随从人数为C【x】【y】，彼岸商人数与随从人数为B【3-x】【3-y】，C与B数组中x必须大于等于y。C与B数组中，各个数组中每相邻两个二维数组|x+y|之差不得超过2。其中过河途中船上人数用数组A表示A【x1】【y1】，返回途中船上人数A【x2】【y2】。x1，x2，y1，y2=0，1，2。x1+y1=1或2；y2+x2=1或2。 从此岸来考察，要从最开始的C【3】【3】变到C【0】【0】。 1，C【3】【3】→C【3】【1】，C【3】【1】→C【3】【2】； 2，C【3】【2】→C【3】【0】，C【3】【0】→C【3】【1】； 3，C【3】【1】→C【1】【1】，C【1】【1】→C【2】【2】；4，C【2】【2】→C【0】【2】，C【0】【2】→C【0】【3】；5，C【0】【3】→C【0】【1】，C【0】【1】→C【0】【2】；6，C【0】【2】→C【0】【0】。 操作过程中需借助栈结构实现，具体如下图所示： 此岸人数已经全部转移到彼岸，任务圆满完成，商人们安全过河。 商人过河问题 一、三名商人各带一名随从的情况 1．问题（略） 2．模型假设 ①当一边岸满足随从数大于商人数，但商人数为0时仍为一种安全状态； ②小船至多可容纳2人，且渡河时由随从（或者商人）来划船。 3．分析与建模 商人过河需要一步一步实现，比如第一步：两个仆人过河，第二步：一个仆人驾船回来，第三步：又是两个仆人过河，第四步：…… 其中每一步都使当前状态发生变化，而且是从一种安全状态变为另一种安全状态。如果我们把每一种安全状态看成一个点，又如果存在某种过河方式使状态a变到状态b，则在点a和点b之间连一条边，这样我们把商人过河问题和图联系起来，有可能用图论方法来解决商人过河问题。 建模步骤：?首先要确定过河过程中的所有安全状态，我们用二元数组(,) x y 表示一个安全状态（不管此岸还是彼岸），其中x表示留在此岸的主人数，y表示留在此岸的随从数。两岸各有十种安全状态： (0,0),(0,1),(0,2),(0,3),(2,2),(1,1),(3,0),(3,1),(3,2),(3,3) ?在两岸的安全状态之间，如存在一种渡河方法能使一种状态变为另一种安全状态，则在这两种状态之间连一条边。这样，得到如下一个二部图（图1），其中下方顶点表示此岸状态，上方顶点表示彼岸状态。我们的目的是要找出一条从此岸(3,3)到彼岸(0,0)的最短路。 ?观察发现此岸的状态(0,0)，(3,0)和彼岸的状态(0,3)，(3,3)都是孤立点，在求最短路的过程中不涉及这些点，把它们删去。两岸的点用1,2,……，16重新标号。 （3,3）（3,2）（3,1）（3,0）（1,1）（2,2）（0,3）（0,2）（0,3）（0,0）○②④⑥⑧⑩○○12○14○16 ①③⑤○⑦⑨○11○13○15○（3,3）（3,2）（3,1）（3,0）（1,1）（2,2）（0,3）（0,2）（0,3）（0,0） (图1) 4．模型求解 求最短路程的matlab程序sroute.m如下： function route=sroute(G,opt) %求图的最短路的Dijkstra算法程序，规定起点为1，顶点连续编号 %G是给定图的邻接矩阵或弧表矩阵，程序能够自动识别商人过河问题数学建模修订稿
数学建模题型
数学建模题型
人猫鸡米渡河问题的数学模型
商人过河问题数学建模
基于商人过河游戏的数学建模-最新教育文档
数学建模 商人过河
数学建模作业——实验1
数学建模商人过河__论文
数学建模作业(商人过河问题)
数学建模与数学实验课后习题答案
商人过河matlab程序以及解析
商人安全过河问题
商人过河问题数学建模
商人过河优化模型
数学模型实验商人过河
商人过河的数学模型及编程解决
数学建模 商人过河
商人过河问题