资源预览内容
第1页 / 共16页
第2页 / 共16页
第3页 / 共16页
第4页 / 共16页
第5页 / 共16页
第6页 / 共16页
第7页 / 共16页
第8页 / 共16页
第9页 / 共16页
第10页 / 共16页
亲,该文档总共16页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
数学建模 题目:商仆过河问题 组员: 班级:指导老师:目录1. 摘要32. 问题的提出.33. 问题的分析.44. 模型的假设.55. 模型的建立与解.56. 模型的符号.67. 模型的解.68. 模型的图解.89. 关于C语言的程序算法.1010. 模型的优缺点.1411. 参考文献.15摘要: 本文针对商人安全渡河问题,采用多步决策的过程建立数学模型,求解得到了在随从没杀人越货的情况下的渡河方案。 对于本题而言,在3(15)对商仆、船最大容量为2(8)人的情况下,首先定义了渡河前此岸的状态,并设安全渡河条件下的状态集合定义为允许状态集合,接着得到渡河方案的允许决策集合,然后得到状态随从渡河方案变化的规律。利用c软件编译运行程序得到了一种商人安全渡河的方案,并输出了允许的状态向量和允许的决策向量。关键词:船载量、允许状态向量、允许决策向量一 问题的提出仆人们密约,在河的任何一边,只要仆人的数量超过商人的数量,仆人就会联合起来将商人杀死并抢夺其财物,三名商人各带一个随从乘船渡河,一只小船只能容纳两人,由他们自己划行。在河的任意一岸,一旦随从的人数比商人多,商人就有危险但是如何乘船渡河的大权掌握在商人们手中。商人们怎样才能安全渡河呢?同时,推广到十五名商人带十五名随从又如何?二 问题的分析1. 安全渡河问题可以看成一个多步决策过程,船由此岸驶向彼岸或从彼岸驶回此岸,都要对船上的人员(商人随从各几人)作出决策。2. 状态向量:用二维坐标向量表示(商,仆):0=H=3(11), 0=S=3(11),例如:(3,3,)(5,0)(6,4)等均成立3. 允许向量:由题意可知,仆人数少于商人数被选定为允许向量。4. 运载向量:利用二维向量(m,n)表示船只上的商仆数量。5. 可行的运载向量:满足二维向量(m,n),0=n=m=3(15)。枚举所有可能的算法:(1,0)(2,0)(3,0)(4,0)(5,0)(6,0)(7,0)(8,0)(1,1)(2,2)(3,3)(4,4)(2,1)(3,2)(4,3)6. 可取用状态向量:利用穷举法表示状态,利用递归算法进行模型的建立与运算7. 运载向量:使用二维向量进行表示(商,仆):0=商=3(11),0=仆=3(11)8. 该模型使用逻辑运算法则进行数学模型的建立三 模型的假设(1) 每个商人和他的随从均会划船(2) 只有一条船,且船只的承载数量为8人(3) 船在划行的状况下不受任何的外力干扰 (4)不存在任意几人不能同时坐船的情况四 模型的建立与解由题目可知,3(15)对商仆过河,船载量为2(8)人,现记第K次渡河前的商人数为Xk,仆人数为Yk,k=1,2,(2)8,再记一组二维向量Ak=(Xk,Yk),Ak为给定时的状态量,可记做C的表达式为: C=(x,y)|x=0,y=0,1,(3)15=y=0,1,(3)15=y=0,1,(3)15再记第K次渡河时船上的商人数为uk,仆人数为vk,记二维向量Bk=(uk,vk),可知小船此时的运载为D,D的表达式为; D =(u,v)|1=u+v=n且u=v,且m+n-1=u+v 或m+n-2=u+v。(3) Z从0变为1时,即从河的彼岸到此案,则此案的人数增加1或2;即(u,v,0) (m,n,1)时,两岸的人数满足m=n , u=v ,m+n+1=u+v或m+n+2=u+v。(4)对重复出现过的状态不计入安全状态,如(3,3,1)(3,2,0)(3,3,1)最终,我们可以得到如下的四种解法:第一种解法:第二种解法:第三种解法:第四种解法:(2) 利用C的程序来求解过河问题1. 建立一维数组P1,P2,pp,分别代表河的一岸的商仆数,船只承载的商仆数,河的另一岸的商仆数。2. 已知船只承载量,利用动态规划的核心思想,统筹规划选定第一次过河的商仆数,保证P1,P2,PP数组均无冲突变量产生。3. 完成一次单向承载后,保证在船只可以有人划行返回的状况下,P1,P2,PP不发生冲突。4. 利用递归的方法,以此类推,在第2次到第K次的船只运输时,保证P1,P2,PP不发生冲突。5. 重复第4步骤直到完成过河。6. 此模型的过河方案的步骤记作第1次方案7. 利用动态规划思想重新设计渡河方案,完成k次运算结果。8. 利用贪心算法比较数据,选出对此模型的最优解。七 模型的图解(1) 关于渡河时可完成任务的条件图例1.原始状况下仅有3对商仆时的情形图例:1.关于当商仆数为3时的标准作图:第一步:0商2仆过河 0商1仆返回第二步:0商2仆过河 0商1仆返回第三步:0仆2商过河 1商1仆返回第四步:0仆2商过河 0商1仆返回第五步:0商2仆过河 0商1仆返回第六步:0商2仆过河 完成2.由3对商仆延伸至15对商仆时:第一步:0商7仆过河 0商1仆返回第二步:7商1仆过河 1商1仆返回第三步 4商4仆过河 1商1仆返回第四步:4商4仆过河 1商1仆返回第五步:3商3仆过河 完成(2)关于渡河时的商仆数与船只承载量的关系:八 关于C语言的程序算法(1)关于过河问题的C语言程序#include #include#includestruct node int x1;int y1;int state;struct node *next;typedef struct node state;typedef state *link;link PP1=NULL;link PP2=NULL;int a1,b1;int a2,b2;void Push(int a,int b,int n)link newnode;newnode=(link)malloc(sizeof(state);newnode- x1=a;newnode- y1=b;newnode- state=n;newnode- next=NULL;if(PP1=NULL)PP1=newnode;PP2=newnode;elsePP2- next=newnode;PP2=newnode;void Pop()link p;if(PP1=PP2)free(PP1);PP1=NULL;PP2=NULL;p=PP1;while(p- next!=PP2)p=p- next;free(PP2);PP2=pr;PP2- next=NULL;int history(int a,int b,int n) link pr;if(PP1=NULL)return 1;elsep=PP1;while(p!=NULL)if(p- x=a&p- y=b&p- state=n)return 0;p=p- next;return 1;int judge(int a,int b,int c,int d,int n) if(history(a,b,n)=0) return 0;if(a=0&b=0&a=3&b=0&d=0&c=3&d =b)Push(a,b,n);return 1;else return 0;else return 0;main()Judge(); Switch(Push);Getch(); (2)关于上述程序运算过后的图解实例:1.三对商仆的初始问题图例2.十一对商仆过河问题图例九 模型的优缺点1.模型的优点(1)采用了较为成熟的数学理论建立模型,可行度比较高; (2)运用程序显示成TXT文档,易于读写插入; (3)模型的求解运用了强大的Dev cpp 7.5软件,结果准确度较高,便于推广与使用; (4)通过C程序,能判断出“当任意个商人任意个随从船的容量任意时,商人能否安全渡河?”的问题,使得所建模型更加全面。 2.模型的缺点 (1)没有找到商人数随从数及船的容量之间的数量关系; 十 参考文献1. 数学建模与实验 王涛等著 清华大学出版社2. 初等数学建模 黄忠裕著 四川大学出版社3. 数学建模原理与案例 冯杰等著 科学出版社4. 数学建模实验(2000版)赫孝良著 西安交通大学出版社5. 数学建模导论(2003版) 陈理荣等著 北京邮电大学出版社1. 基于C8051F单片机直流电动机反馈控
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号