当前位置：文档之家 › 商人过河问题数学建模

商人过河问题数学建模

  • 格式：doc
  • 大小：72.00 KB
  • 文档页数：5

作业1、2：之相礼和热创作

贩子过河

一、 成绩重述

成绩一：4个贩子带着4个随从过河，过河的工具只要一艘小船，只能同时载两个人过河，包含划船的人.随从们密约, 在河的任一岸, 一旦随从的人数比贩子多, 就舍己为人.乘船渡河的方案由贩子决定.贩子们怎样才能安全过河?

成绩二：假如小船可以容3人，叨教最多可以有几名贩子各带一名随从安全过河.

二、成绩分析

成绩可以看做一个多步决策过程.每一步由此岸到此岸或此岸到此岸船上的人员在安全的前提下(两岸的随从数不比贩子多),经无限步使全体人员过河.用形态变量暗示某一岸的人员状况，决策变量暗示船上的人员状况，可以找出形态随决策变更的规律.成绩就转换为在形态的容许变更范围内（即安全渡河条件），确定每一步的决策，达到安全渡河的目的.

三．成绩假设

1. 过河途中不会出现不成抗力的自然要素.

2. 当随从人数大于贩子数时，随从们不会改变杀人的计划.

3．船的质量很好，在多次满载的状况下也能正常运作.

4. 随从会遵从贩子的调度.

四、模型构成 x(k)~第k次渡河前此岸的贩子数 x(k),y(k)=0,1,2,3,4;

y(k)~第k次渡河前此岸的随从数 k=1,2,…..

s(k)=[ x(k), y(k)]~过程的形态 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}

u(k)~第k次渡船上的贩子数 u(k), v(k)=0,1,2;

v(k)~ 第k次渡船上的随从数 k=1,2…..

d(k)=( u(k), v(k))~过程的决策 D~容许决策集合

D={u,v|u+v=1,2,u,v=0,1,2}

形态因决策而改变s(k+1)=s(k)+(-1)^k*d(k)~形态转移律

求d(k)ÎD(k=1,2,….n),使s(k)ÎS并按转移律s(k+1)=s(k)+(-1)^k*d(k)由（4,4）到达（0,0）

数学模型： k+1kS=S+kkD（-1）（1）

'4kkxx （2）

'4kkyy（3） 随从y

贩子x k.kxy （4）

''kkxy（5）

模型分析：

由（2）（3）（5）可得

化简得

综合（4）可得

kkxy和 (,)|0,0,1,2,3,4kkkkkSxyxy（6）

还要考虑

'(',')|'0,'0,1,2,3,4kkkkkSxyxy （7）

把（2）（3）带入（7）可得

化简得

(,)|4,0,1,2,3,4kkkkkSxyxy （8）

综合（6）（7）（8）式可得

满足条件的状况满足下式

(,)|0,4,0,1,2,3,4;kkkkkkkSxyxyxy（9）

以是我们晓得满足条件的点如上图所示：点挪动由

(,)|4,0,1,2,3,4kkkkkSxyxy （8）

到达

(,)|0,0,1,2,3,4kkkkkSxyxy（6）

时，可以以为完成渡河.

由于挪动的格数小于等于2，只要中心点（2，2）到（6）点和（8）点的距离为2，以是中心点（2,2）成为渡河的关键点.

当我们挪动到（2,2）点时，就无法进行下往.

故4个贩子，4个随从，船容量为2人时，无法安全渡河.

对于成绩二，我们可以建立模型为：

k+1kS=S+kkD（-1）（10）

'kkxxM （11）

'kkyyM （12）

k.kxy（13）

''kkxy （14）

u(k), v(k)=0,1,2,3; （15）

经过类似于成绩一的步调可以晓得：坐标上的关键点是（3,3），最多可以五名贩子带五名随从过往.

必要确定五名贩子带五名随从的方案可行再确定六名贩子带六名随从的方案不成行

1、五名贩子带五名随从的状况：

（1）首先不成能有三名贩子先过河，两名贩子一名随从过河，一名贩子两名随从过河

（2）三个随从先过河（5,2），回来一个随从（5,3），过往两个随从（5,1）回来一个随从（5,2），再过往三个贩子（2,2），回来一个贩子一个随从（3,3），再过往三个贩子（0,3），回来一个随从（0,4），过往三个随从（0,1），回来一个随从（0,2）再过往两个随从（0,0） 综上可知：五名贩子带五名随从，小船可以载三个人可以过河

2、六名贩子带六名随从的状况：

（1）首先不成能有三名贩子先过河，两名贩子一名随从过河，一名贩子两名随从过河

（2）三个随从先过河（6,3），回来一个随从（6,4），过往两个随从（6,2）回来一个随从（6,3），过往三个贩子（3,3），此时两岸都是（3,3），由坐标法分析知，这是最接近尽头的临界点，但是假如回来的时分肯定是回来一个贩子和一个随从，假如这一步可行，后面就进行不往

综上所述，六个贩子带六个随从，小船载三个人的状况下不克不及渡河

结合1、2知，当小船最多载三个人的时分，最多五名贩子各带一个随从可以过河.

五、模型的检验与评价

由多数人的过河成绩推行到了更多数人的过河成绩，使得成绩变得明了有规律.

六、参考文献

[1]章胤，2014年燕山大学天下大门生数学建模竞赛培训ppt，2014年4月17日

合集下载

基于商人过河游戏的数学建模-最新教育文档

基于商人过河游戏的数学建模-最新教育文档

1 / 4

基于商人过河游戏的数学建模

1提出问题

文献[1]给出一个智力游戏：“三名商人各带一个随从渡河，一只小船只能容纳二人，由他们自己划行。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。但是如何乘船的大权掌握在商人们手中。商人怎样才能安全渡河呢？”此类智力问题当然可以通过一番思考，拼凑出一个可行的方案来。文献[1]中通过图解法给出了解答，但是当商人数与随从数发生变化，船能容纳的人数不是二人时，图解法就会变得繁复而难以解决问题。

因此，将上述游戏改为n名商人各带一个随从过河，船每次至多运p个人，至少要有一个人划船，由他们自己划行。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。

但是如何乘船的大权掌握在商人们手中。商人怎样才能安全渡河的问题。

除此之外，考虑了随着船载人数的增多，以及商人与仆人的对数增多到多少时，会影响商人的安全渡河的问题。

2问题分析

由于这个虚拟的游戏已经理想化了，所以不必再作假设。我们希望能找出这类问题的规律性，建立数学模型，并通过计算机编程进行求解。安全渡河游戏可以看做是一个多步决策过程，分步优化，船由此岸驶向彼岸或由彼岸驶回此岸的每一步，都要对船上的商人和随从做出决策，在保证商人安全的前提下，在无限步内使全部人员过河。用状态表示某一岸的人员状况，决策表示船上的人员情况，可以找出状态随决策变化的规律。问题转化为在状态的允许范围内，确定每一步的决策，最后获取一个全局最优方案的决策方案，达到渡河的目标。

除此以外，我们还要找出，随着船载人数的增加，商人与仆人对数达到多少时，会影响到商人不能安全过河。这里要对船载人数进行限制，因为船载人数过多时，此智力游戏会变得相当繁复，就会失去作为游戏的本来意义。

3模型构成

2 / 4

记第k次渡河前此岸的商人数为，随从数为，，，。

将二维向量定义为过程的状态。

安全渡河条件下的状态集合称为允许状态集合，记作S。

商人过河优化模型.docx

商人过河优化模型.docx

2012高教社杯全国大学生数学建模竞赛

承诺书

我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子 邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关 的问题。

我们知道，抄袭别人的成果是违反竞赛规则的，如果引用别人的成果或其他 公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正 文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违 反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： A

我们的参赛报名号为（如果赛区设置报名号的话）： J2202 __________

所属学校（请填写完整的全名）： 江西环境工程职业学院

参赛队员（打印并签名）：1. ___________________________________

2. ___________________________________________

3. ___________________________________

指导教师或指导教师组负责人（打印并签名）：教练组 _____________________________

日期：2012年8月9日

赛区评阅编号（由赛区组委会评阅前进行编号）： 2012高教社杯全国大学生数学建模竞赛

编号专用页

赛区评阅编号（由赛区组委会评阅前进行编号）:

赛区评阅记录（可供赛区评阅时使用）：

全国统一编号（由赛区组委会送交全国前编号）：

全国评阅编号（由全国组委会评阅前进行编号）：评阅人

评分

备注

商人过河

摘要

本文针对商人安全渡河的问题，采用多步决策的过程建立数学模型，求解 得到了在随从没有杀人越货的情况下的渡河方案。

对于本题而言，在3名商人、3名随从、船的最大容量为2的情况下，首 先定义了渡河前此岸的状态，并设安全渡河条件下的状态集定义为允许状态集 合，接着得到渡河方案的允许决策集合，然后得到状态随渡河方案变化的规律, 最后利用平而坐标分析法，并利用计算机进行了仿真，得到了一种商人安全渡 河的方案。

数学建模：研究商人过河问题

数学建模：研究商人过河问题

第1页，共17页 数学建模试验一陈述 【1 】

试验标题：研讨商人过河问题

一.试验目标：编写一个程序（可所以C,C++或Mathlab）实现商人安然过河问题.

二.试验情形：Turbo c 2.0..Matlab 6.0以上

三.试验请求：请求该程序不但能找出一组安然过河的可行筹划,还可以得到所有的安然过河可行筹划.并且该程序具有必定的可扩大性,即不但可以实现3个商人,3个侍从的过河问题.还应能实现

n个商人,n个侍从的过河问题以及n个不合对象且每个对象有m个元素问题(解释：对于3个商人,3个侍从问题分离对应于n=2,m=3)的过河问题.从而给出课后习题5（n=4,m=1）的全部安然过河筹划.

四.试验步调：

第一步：问题剖析.这是一个多步决议计划进程,涉及到每一次船上的人员以及要斟酌此岸和此岸上残剩的商人数和侍从数,在安然的前提下（两岸的侍从数不比商人多）,经有限步使全部人员过河.

第二步：剖析模子的组成.记第k次渡河前此岸的商人数为kx,侍从数为ky,2,1k,nyxkk2,1,,（具有可扩大性）,将）（kkyx,界说为状况,状况聚集成为许可状况聚集（S）.S={2,1;3,2,1,0,3;3,2,1,0,0|,yxyxyxyx）（}记第k次渡船的商人数为ku,侍从数为kv,决议计划为),(kkvu,安然渡河前提下,决议计划的聚集为许可决议计划聚集.许可决议计划聚集记作D,所以 第2页，共17页 D={2,1,0,,21|,vuvuvu）（|1

第三步：模子求解.

#include "stdio.h"

#include "string.h"

#include

#include

#include

using namespace std;

#include "conio.h"

FILE *fp;/*设立文件指针,以便将它用于其他函数中*/

struct a{

商人过河的数学模型及编程解决【范本模板】

商人过河的数学模型及编程解决【范本模板】

14对商仆过河问题

题目

有14名商人各带一名仆人要过河,但船最多能载4人。商人已获得仆人的阴谋：在河的任意一岸，只要仆人数超过商人数，仆人会将商人杀死并窃取货物。安排如何乘船的权利权利在商人手上，试为商人制定一个安全的过河方案。

一．摘要

n对商仆过河,一只船最多载m人，船上和岸上的仆人数都不能多于商人数,否则商人有危险。安排合理的渡河方案，保证商人能安全渡河。（可利用向量，矩阵，图解等方法）。

二．问题提出：

有14对商仆乘船过河,一只船最多载4人，由商人和仆人自己划船渡河，在河的任意一岸，一旦仆人数多于商人数，仆人就可将商人杀死,谋取利益，但是乘船渡河的主动权掌握在商人们手中，商人们如何安排渡河方案，才能安全渡河？

三．问题分析

商仆安全渡河问题可以视为一个多步决策过程，多步决策是指决策过程难以一次完成,而是多步优化，最后获取一个全局最优方案的决策方法。对于每一步，即船由此岸驶向彼岸，或者船由彼岸驶向此岸的决策，不仅会影响到该过程的效果，而且还会影响到下一步的初始状态,从而对整个过程都会有影响。所以，在每一次过河时，就不能只从这一次过河本身考虑，还要把它看成是整个过河过程中的一个部分。在对船上的人员做决策时，要保证两岸的商人数不能少于仆人数,用最少的步伐是人员全部过河.应用状态向量和运载向量，找出状态随运载变化的规律，此问题就转化为状态在允许范围内（即安全渡河条件)，确定每一次该如何过河，从而达到渡河的目标。现在我们都把它们数量化：即用数学语言来表示。

四．模型假设与符号假设

（一）模型假设

商人和仆人都会划船，天气很好，无大风大浪，船的质量很好，船桨足够很多次的运载商人和仆人。

（二）符号假设

设（x，y）是状态向量，表示任一岸的商人和仆人数,且x，y分别要大于等于0，小于等于M。

1.设(m,n)是运载向量，表示运载的商人数和仆人数，0<=m<=N，0<=n<=N，0〈=m+n〈=N。