商人过河模型问题的求解

1、数学建模实验课程考试试题-商人安全过河数学建模与求解一问题提出：4名商人带4名随从乘一条小船过河，小船每次自能承载至多两人。随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货.乘船渡河的方案由商人决定，商人们如何才能安全渡河呢？二模型假设：商人和随从都会划船，天气很好，无大风大浪，且船的质量很好，可以保证很多次安全的运载商人和随从。三问题分析：商随过河问题可以视为一个多步决策过程，通过多次优化，最后获取一个全局最优的决策方案。对于每一步，即船由此岸驶向彼岸或由彼岸驶向此岸，都要对船上的人员作出决策，在保证两岸的商人数不少于随从数的前提下，在有限步内使全部人员过河。用状态变量表示

2、某一岸的人员状况，决策变量表示船上的人员状况，可以找出状态随决策变化的规律，问题转化为在状态的允许变化范围内(即安全渡河条件)，确定每一步的决策，达到安全渡河的目标。四模型构成：第k次渡河前此岸的商人数，第k次渡河前此岸的随从数, =0,1,2,3,4; k=1,2, =(, )过程的状态,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第k次渡船上的商人数第k次渡船上的随从数=(, )决策，D=(u , v)| , =0,1,2 允许决策集合k=1,2, 因为k为奇数时船从此岸驶向彼岸，k为偶数时船从彼岸驶向此

3、岸，所以状态随决策的变化规律是=+状态转移律求D(k=1,2, n), 使S, 并按转移律由=(4,4)到达状态=(0,0)。五模型求解：1.图解法：对于人数不多的情况，可以利用图解法来求解。在xoy平面坐标系上画出如图所示的方格，方格点表示状态s=(x,y)，允许状态集合S是圆点标出的13个格子点，允许决策是沿方格线移动1格或2格，k为奇数时向左、下方移动，k为偶数时向右、上方移动。要确定一系列的使由=(4,4)经过那些圆点最终移动到原点(0,0)。由初始状态(4,4)到原点(0,0)，无论怎样走，都要经过(2,2)，但是无论怎样变化人数，也只能到达此点后不能继续走下去，只能循环走(由d7状

4、态无法不重复循环地走下去)，达不到最终的目标(0,0)，因此该问题无解。 yd1 d7d6 d2 d2 d5 d4 4 3 d1 2 d3 1 0 1 2 3 4 x2. 穷举法：根据分析可以通过编程上机求解，所用的c程序如下所示：#include <stdio.h>#define N 30int xN,yN,u6,v6,k;/* x,y：状态值，分别表示此岸商人、随从数*/*u,v：决策值，分别表示船上商人、随从数*/* k：决策步数；k的奇偶性标志着船在河的此岸或彼岸 */next(int k,int i)/*计算下一状态*/ if(k%2) /* k+1 为偶数，船从此岸到彼

5、岸 */ xk+1=xk-ui; yk+1=yk-vi; else /* k+1 为奇数，船从彼岸到此岸 */ xk+1=xk+ui; yk+1=yk+vi; return;allow(int p,int q)/* 判定状态是否允许,是否重复 */ int ok,j; /* ok:标记状态是否允许,是否重复；j:循环变量 */ if(p<0|p>x1|p!=0&&q>p|(x1-p)!=0&&(y1-q)>(x1-p)|q<0|q>y1) ok=0; /* 此时状态不属于允许集 */ else for(j=k-1;j>0

6、;j-=2) /* 是否重复与船在河的哪一岸有关 */ if(p=xj && q=yj ) ok=0; /* 此时状态出现重复 */ break; if(j<=0) ok=1; /* 此时状态属于允许集，且不重复 */ return ok;void main() int i,j,mN,flag=1;/* m:采用的决策序号，flag:回溯标记 */ u1=2; v1=0; /* 给决策编号并赋值 */ u2=0; v2=2; u3=1; v3=0; u4=0; v4=1; u5=1; v5=1; k=1; /* 从初始状态出发 */ printf("请输入商人和

7、随从的初始状态:n商人数="); scanf("%d",&xk); printf("随从数="); scanf("%d",&yk); while(flag) for(i=1;i<6;i+) /* 遍历各种决策 */ next(k,i); /* 计算下一状态 */ if(allow(xk+1,yk+1) /* 若新状态允许且不重复 */ mk=i; /* 记录采用的决策序号 */ if(xk+1=0 && yk+1=0) /* 若到达目标状态,输出结果 */ printf("初始值:商人%d随从%dn",x1,y1); for(j=1;j<=k;j+) printf(" 第 %2d 次 %d %dn",j,xj+1,yj+1); flag=0; break; else /* 若未到达目标状态 */ k+; /* 生成下一步的步数值 */ break; /* 遍历终止，进入下一步 */ else /* 若新状态不允许或重复 */ while(i=5) /* 本步决策已经遍历时 */ if(k=1) printf("本题无解!n"); flag=0; break; else /* 未到达初始状态 */ k