商人过河模型问题的求解

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

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

3、从彼岸驶向此岸，所以状态Sk随决策dk的变化规律是Ski=Sk+(1)kdktfcS转移律求dkeD(k=1,2,-n),使SkeS,并按转移律由Si=(4,4)到达X犬态Sn1=(0,0)。五.模型求解：1 .图解法：对于人数不多的情况，可以利用图解法来求解。在xofRW坐标系上画出如图所示的方格，方格点表示状态s=(x,y),允许状态集合S是圆点标出的13个格子点，允许决策dk是沿方格线移动1格或2格,k为奇数时向左、下方移动，k为偶数时向右、上方移动。要确定一系列的dk使由S=(4,4)经过那些圆点最终移动到原点(0,0)。由初始状态(4,4)到原点(0,0),无论怎样走，都要经过(2,

4、2),但是无论怎样变(由d7状态无法不重复化人数，也只能到达此点后不能继续走下去，只能循环走循环地走下去)，达不到最终的目标(0,0),因此该问题无解2 .穷举法：根据分析可以通过编程上机求解，所用的甜序如下所示:#include<>#defineN30intxN,yN,u6,v6,k;/*x,y:状态值，分别表示此岸商人、随从数*/*u,v:决策值，分别表示船上商人、随从数*/*k：决策步数；k的奇偶性标志着船在河的此岸或彼岸*/next(intk,inti)/*计算下一状态*/if(k%2)/*k+1为偶数，船从此岸到彼岸*/xk+1=xk-ui;yk+1=yk-vi;else

5、/*k+1为奇数，船从彼岸到此岸*/xk+1=xk+ui;yk+1=yk+vi;return;allow(intp,intq)/*判定状态是否允许,是否重复*/intok,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;/*此时状态不属于允许集*/elsefor(j=k-1;j>0;j-=2)/*是否重复与船在河的哪一岸有关*/if(p=xj&&q=yj)ok=0;/*此时状

6、态出现重复*/break;if(j<=0)ok=1;/*此时状态属于允许集，且不重复*/returnok;voidmain()inti,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("请输入商人和随从的初始状态:n商人数=");scanf("%d",&xk);printf("随从数=");scanf("%d",&

7、amp;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+;/*生成下一

8、步的步数值*/break;/*遍历终止，进入下一步*/else/*若新状态不允许或重复*/while(i=5)/*本步决策已经遍历时*/if(k=1)printf("本题无解!n");flag=0;break;else/*未到达初始状态*/k-;/*回溯退回1步，寻找新路径*/i=mk;if(flag)continue;/*本步决策尚未遍历时*/elsebreak;/*本步决策遍历时*/当冏人数和随从数分别取(2,2)(3,3)(4,4)时,程序输出结果如下：I&in叵r*E;DRbugT商人过河问题启k初始值:商人2随从2第1次i2第次第4次第5次'i"bs&any22Si0keyt;a0continue，EDgbug'，