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