欢迎来到天天文库
浏览记录
ID:56518130
大小:43.50 KB
页数:15页
时间:2020-06-26
《商人过河的数学模型及编程解决.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、14对商仆过河问题题目有14名商人各带一名仆人要过河,但船最多能载4人。商人已获得仆人的阴谋:在河的任意一岸,只要仆人数超过商人数,仆人会将商人杀死并窃取货物。安排如何乘船的权利权利在商人手上,试为商人制定一个安全的过河方案。一.摘要n对商仆过河,一只船最多载m人,船上和岸上的仆人数都不能多于商人数,否则商人有危险。安排合理的渡河方案,保证商人能安全渡河。(可利用向量,矩阵,图解等方法)。二.问题提出:有14对商仆乘船过河,一只船最多载4人,由商人和仆人自己划船渡河,在河的任意一岸,一旦仆人数多于商人数,仆人就可将商人杀死,谋取利益,但是乘船渡河的主动权掌握在商人们手中,商
2、人们如何安排渡河方案,才能安全渡河?三.问题分析商仆安全渡河问题可以视为一个多步决策过程,多步决策是指决策过程难以一次完成,而是多步优化,最后获取一个全局最优方案的决策方法。对于每一步,即船由此岸驶向彼岸,或者船由彼岸驶向此岸的决策,不仅会影响到该过程的效果,而且还会影响到下一步的初始状态,从而对整个过程都会有影响。所以,在每一次过河时,就不能只从这一次过河本身考虑,还要把它看成是整个过河过程中的一个部分。在对船上的人员做决策时,要保证两岸的商人数不能少于仆人数,用最少的步伐是人员全部过河。应用状态向量和运载向量,找出状态随运载变化的规律,此问题就转化为状态在允许范围内(即
3、安全渡河条件),确定每一次该如何过河,从而达到渡河的目标。现在我们都把它们数量化:即用数学语言来表示。四.模型假设与符号假设(一)模型假设商人和仆人都会划船,天气很好,无大风大浪,船的质量很好,船桨足够很多次的运载商人和仆人。(二)符号假设设(x,y)是状态向量,表示任一岸的商人和仆人数,且x,y分别要大于等于0,小于等于M。1.设(m,n)是运载向量,表示运载的商人数和仆人数,0<=m<=N,0<=n<=N,0<=m+n<=N。2.设用s表示所有的可取状态向量的集合。3.设用d表示所有运载向量的集合。4.设用表示从此岸到彼岸,作减;用表示从彼岸到此岸,作加。Sk:表示第k
4、步可取状态向量(Sk属于s);dk:表示第k步可取转移向量(dk属于d);五.模型的建立我们以3名商人为例。设第k次渡河前此岸的商人数为xk,随从数为yk,k=1,2,…,xk,yk=0,1,2,3,将二维向量Sk=(xk,yk)定义为状态。安全渡河条件下的状态集合称为允许状态集合,记为S,则允许状态集合为:S={(x,y)
5、x=0或3,y=0,1,2,3,x=y=1,2}(1)又设第k次渡船上的商人数为uk,随从数为vk,将二维向量dk=(uk+vk)定义为决策。则允许决策集合为:D={(u,v)
6、u+v=1,2}(2)因为k为奇数时船从此岸驶向彼岸,k为偶数时船由彼岸驶
7、向此岸,所以状态Sk随着决策dk变化的规律即状态转移规律是:Sk+1=Sk+(-1)kdk(3)这样,制定安全渡河方案归结为如下的多步决策问题:求决策dk∈D(k=1,2,…,n),使状态Sk∈S按照规律(3),由初始状态S1=(3,3)经有限步(设为n)到达状态Sn+1=(0,0)。六.模型的简化与求解下面通过程序给出这个多步决策问题的一个解:a[1]={0,0};a[2]={0,1};a[3]={0,2};a[4]={0,3};a[5]={3,0};a[6]={3,1};a[7]={3,2};a[8]={3,3};a[9]={1,1};a[10]={2,2};(*以上给
8、出10个允许的状态*)d[1]={0,2};d[2]={2,0};d[3]={1,1};d[4]={0,1};d[5]={1,0};(*以上表示给出5个允许的决策*)i=1;j=1;k=1;s[0]=s[1]={3,3};Print[″此岸————船上————对岸″];Do[Do[s[i+1]=s[i]+(-1)^id[j];t=0;Do[If[s[i+1]==a[k],t=1],{k,1,10}];If[t==0,Continue[]];(*以上是保证状态属于允许的状态*)l=Mod[i+1,2];m=l;u=0;If[i+1>=3,Do[If[s[i+1]==s[m],
9、u=1,Break[]],{m,l,i-1,2}]];If[u==0,c[i+1]=d[j];Break[]],{j,1,5}];If[t==0,Print[No,Result];Break[]];b[i+1]={3,3}-s[i+1];Print[s[i],″----″,c[i+1],″----″,b[i+1]];If[s[i+1]=={0,0},Break[]],{i,1,12}]程序运行结果如下:此岸——————船上——————对岸{3,3}——————{0,2}——————{0,2}{3,1}——————{
此文档下载收益归作者所有