资源描述：
《商人过河模型问题的求解.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、《数学建模实验》课程考试试题----商人安全过河数学建模与求解一．问题提出：4名商人带4名随从乘一条小船过河，小船每次自能承载至多两人。随从们密约,在河的任一岸,一旦随从的人数比商人多,就杀人越货.乘船渡河的方案由商人决定，商人们如何才能安全渡河呢？二．模型假设：商人和随从都会划船，天气很好，无大风大浪，且船的质量很好，可以保证很多次安全的运载商人和随从。三．问题分析：商随过河问题可以视为一个多步决策过程，通过多次优化，最后获取一个全局最优的决策方案。对于每一步，即船由此岸驶向彼岸或由彼岸驶向此岸，都要对船上的人员作出决策，在
2、保证两岸的商人数不少于随从数的前提下，在有限步内使全部人员过河。用状态变量表示某一岸的人员状况，决策变量表示船上的人员状况，可以找出状态随决策变化的规律，问题转化为在状态的允许变化范围内(即安全渡河条件)，确定每一步的决策，达到安全渡河的目标。四．模型构成：~第k次渡河前此岸的商人数，~第k次渡河前此岸的随从数,=0,1,2,3,4;k=1,2,……=(,)~过程的状态,S~允许状态集合，S={(x,y)
3、x=0,y=0,1,2,3,4;x=4,y=0,1,2,3,4;x=y=1,2,3}~第k次渡船上的商人数~第k次渡船上的
4、随从数=(,)~决策，D={(u,v)
5、,,=0,1,2}~允许决策集合k=1,2,……因为k为奇数时船从此岸驶向彼岸，k为偶数时船从彼岸驶向此岸，所以状态随决策的变化规律是=+~状态转移律求∈D(k=1,2,…n),使∈S,并按转移律由=(4,4)到达状态=(0,0)。五．模型求解：1.图解法：对于人数不多的情况，可以利用图解法来求解。在xoy平面坐标系上画出如图所示的方格，方格点表示状态s=(x,y)，允许状态集合S是圆点标出的13个格子点，允许决策是沿方格线移动1格或2格，k为奇数时向左、下方移动，k为偶数时向右、上方移
6、动。要确定一系列的使由=(4,4)经过那些圆点最终移动到原点(0,0)。由初始状态(4,4)到原点(0,0)，无论怎样走，都要经过(2,2)，但是无论怎样变化人数，也只能到达此点后不能继续走下去，只能循环走(由d7状态无法不重复循环地走下去)，达不到最终的目标(0,0)，因此该问题无解。yd1d7d6d2d2d5d443d12d3101234x2.穷举法：根据分析可以通过编程上机求解，所用的c程序如下所示：#include#defineN30intx[N],y[N],u[6],v[6],k;/*x,y：状态值
7、，分别表示此岸商人、随从数*//*u,v：决策值，分别表示船上商人、随从数*//*k：决策步数；k的奇偶性标志着船在河的此岸或彼岸*/next(intk,inti)/*计算下一状态*/{if(k%2)/*k+1为偶数，船从此岸到彼岸*/{x[k+1]=x[k]-u[i];y[k+1]=y[k]-v[i];}else/*k+1为奇数，船从彼岸到此岸*/{x[k+1]=x[k]+u[i];y[k+1]=y[k]+v[i];}return;}allow(intp,intq)/*判定状态是否允许,是否重复*/{intok,j;/*ok
8、:标记状态是否允许,是否重复；j:循环变量*/if(p<0
9、
10、p>x[1]
11、
12、p!=0&&q>p
13、
14、(x[1]-p)!=0&&(y[1]-q)>(x[1]-p)
15、
16、q<0
17、
18、q>y[1])ok=0;/*此时状态不属于允许集*/else{for(j=k-1;j>0;j-=2)/*是否重复与船在河的哪一岸有关*/if(p==x[j]&&q==y[j]){ok=0;/*此时状态出现重复*/break;}if(j<=0)ok=1;/*此时状态属于允许集，且不重复*/}returnok;}voidmain(){inti,j,m[N],f
19、lag=1;/*m:采用的决策序号，flag:回溯标记*/u[1]=2;v[1]=0;/*给决策编号并赋值*/u[2]=0;v[2]=2;u[3]=1;v[3]=0;u[4]=0;v[4]=1;u[5]=1;v[5]=1;k=1;/*从初始状态出发*/printf("请输入商人和随从的初始状态:商人数=");scanf("%d",&x[k]);printf("随从数=");scanf("%d",&y[k]);while(flag){for(i=1;i<6;i++)/*遍历各种决策*/{next(k,i);/*计算下一状态*
20、/if(allow(x[k+1],y[k+1]))/*若新状态允许且不重复*/{m[k]=i;/*记录采用的决策序号*/if(x[k+1]==0&&y[k+1]==0)/*若到达目标状态,输出结果*/{printf("初始值:商人%d随从%d",x[1],y[1]);fo
