商人过河模型问题的求解.doc

《数学建模实验》课程考试试题----:4名商人带4名随从乘一条小船过河,小船每次自能承载至多两人。随从们密约,在河的任一岸,一旦随从的人数比商人多,就***,商人们如何才能安全渡河呢?:商人和随从都会划船,天气很好,无大风大浪,且船的质量很好,可以保证很多次安全的运载商人和随从。:商随过河问题可以视为一个多步决策过程,通过多次优化,最后获取一个全局最优的决策方案。对于每一步,即船由此岸驶向彼岸或由彼岸驶向此岸,都要对船上的人员作出决策,在保证两岸的商人数不少于随从数的前提下,在有限步内使全部人员过河。用状态变量表示某一岸的人员状况,决策变量表示船上的人员状况,可以找出状态随决策变化的规律,问题转化为在状态的允许变化范围内(即安全渡河条件),确定每一步的决策,达到安全渡河的目标。:~第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为偶数时船从彼岸驶向此岸,所以状态随决策的变化规律是=+~状态转移律求∈D(k=1,2,…n),使∈S,并按转移律由=(4,4)到达状态=(0,0)。::对于人数不多的情况,可以利用图解法来求解。在xoy平面坐标系上画出如图所示的方格,方格点表示状态s=(x,y),允许状态集合S是圆点标出的13个格子点,允许决策是沿方格线移动1格或2格,k为奇数时向左、下方移动,k为偶数时向右、上方移动。要确定一系列的使由=(4,4)经过那些圆点最终移动到原点(0,0)。由初始状态(4,4)到原点(0,0),无论怎样走,都要经过(2,2),但是无论怎样变化人数,也只能到达此点后不能继续走下去,只能循环走(由d7状态无法不重复循环地走下去),达不到最终的目标(0,0),因此该问题无解。yd1d7d6d2d2d5d443d12d3101234x穷举法:根据分析可以通过编程上机求解,所用的c程序如下所示:#include<>#defineN30intx[N],y[N],u[6],v[6],k;/*x,y:状态值,分别表示此岸商人、随从数*//*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:标记状态是否允许,是否重复;j:循环变量*/if(p<0||p>x[1]||p!=0&&q>p||(x[1]-p)!=0&&(y[1]-q