对商仆过河问题数学建模论.docx

数学建模 题目：商仆过河问题 组员： 班级：指导老师：目录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.模型的