最新商人过河的数学模型及编程解决

数学建模实验一报告实验题目：研究商人过河问题一、实验目的：编写一个程序（可以是C,C++或Mathlab ）实现商人安全过河问题。

二、实验环境：Turbo c 2.0、Microsoft Visual C++ 6.0、Matlab 6.0以上 三、实验要求：要求该程序不仅能找出一组安全过河的可行方案，还可以得到所有的安全过河可行方案。

并且该程序具有一定的可扩展性，即不仅可以实现3个商人，3个随从的过河问题。

还应能实现 n 个商人，n 个随从的过河问题以及n 个不同对象且每个对象有m 个元素问题(说明：对于3个商人，3个随从问题分别对应于n=2,m=3)的过河问题。

从而给出课后习题5（n=4,m=1）的全部安全过河方案。

四、实验步骤：第一步：问题分析。

这是一个多步决策过程，涉及到每一次船上的人员以及要考虑此岸和彼岸上剩余的商人数和随从数，在安全的条件下（两岸的随从数不比商人多），经有限步使全体人员过河。

第二步：分析模型的构成。

记第k 次渡河前此岸的商人数为k x ，随从数为k y ，2,1=k ，n y x k k 2,1,=，（具有可扩展性），将）（k k y x ,定义为状态，状态集合成为允许状态集合（S ）。

S={2,1;3,2,1,0,3;3,2,1,0,0|,======y x y x y x y x ）（}记第k 次渡船的商人数为k u ，随从数为k v ，决策为),(k k v u ，安全渡河条件下，决策的集合为允许决策集合。

允许决策集合记作D ，所以D={2,1,0,,21|,=<+<v u v u v u ）（|1<u+v<2,u,v=0,1,2},因为k 为奇数时船从此岸驶向彼岸，k 为偶数时船由彼岸驶向此岸，所以状态k s 随决策k d 变化的规律是k k k k d s s )1(1-+=-，此式为状态转移律。

制定安全渡河方案归结为如下的多步决策模型：求决策)2,1(n k D d k =∈，使状态S s k ∈按照转移律，由初始状态)3,3(1=s 经有限n 步到达)0,0(1=+n s第三步：模型求解。

《数学建模实验》课程考试试题----商人安全过河数学建模与求解一．问题提出：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)。

商人过河问题的Java编程解决转自：“电脑编程技巧与维护”/摘要为商人过河问题建立数学模型，归结为路径搜索问题，并给出一个通用的Jav程序来解决此类问题。

关键词商人过河，二元组，链表，集合一、描述商人过河问题是一个传统的智力问题。

其描述如下：三名商人各带一名随从乘船渡河，—只小船只能容纳二人，由他们自己划行。

随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。

但是如何乘船渡河的大权掌握在商人们手中，商人们怎样才能安全渡河呢？商人过河问题可以看作一个多步决策过程，通过一系列决策步骤逼近决策目标，并最终达到决策目标。

对于该问题的每一步决策，就是要对船由此岸驶向彼岸或由彼岸驶回此岸的人员（包括商人和随从）作出规划，在保证商人安全的前提下，通过有限的步骤，实现人员全部过河的目标。

二、分析针对这一具体问题，可以经过一番精心安排，找到一个解决方案。

不过，本文希望对这一问题进行发展和延伸，建立起数学模型，发现其中蕴含的规律，并借助计算机的运算能力，找到一个通用的一般解法。

在商人过河问题中，用一个二元组来表示岸上商人和随从的组成(m，s)，其中m表示商人人数，s表示随从人数，每个组合可以视为一种状态。

所有可能的状态可以表示为集合：S0={(m, s)| 0≤m≤3; 0≤s≤3}安全状态要求商人人数为0，或者大于等于随从人数，因此，所有的安全状态可以表示为集合：S1={(m, s)| m=0, s=0,1,2,3; m=3, s=0,1,2,3; m=s=1,2}二元组(m，s)也可以表示一次渡河方案，其中m表示船载的商人人数，s表示船载的随从人数。

则所有的渡河方案可以表示为集合：S2={(m , s)|0≤m；0≤s；0≤m+s≤2 }一次渡河决策可以表示为：(m, s)K+1 = (m , s)K- (-1)K(u, v)KK = 0,1,2,3…(m , s)K 为第K次渡河时，岸上的商人和随从的组成，(u, v)K为第K次渡河方案，K从0开始。

作业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 +k k D （-1）（1） '4k k x x += （2）'4k k y y +=（3）k.k x y ≥ （4）''k k x y ≥（5）模型分析：由（2）（3）（5）可得化简得综合（4）可得k k x y =和 {}(,)|0,0,1,2,3,4k k k k k S x y x y ===（6）还要考虑{}'(',')|'0,'0,1,2,3,4k k k k k S x y x y === （7）把（2）（3）带入（7）可得化简得 {}(,)|4,0,1,2,3,4k k k k k S x y x y === （8）综合（6）（7）（8）式可得满足条件的状况满足下式 {}(,)|0,4,0,1,2,3,4;k k k k k k k S x y x y x y ====（9）以是我们晓得满足条件的点如上图所示：点挪动由 {}(,)|4,0,1,2,3,4k k k k k S x y x y === （8）到达 {}(,)|0,0,1,2,3,4k k k k k S x y x y ===（6）时，可以以为完成渡河. 由于挪动的格数小于等于2，只要中心点（2，2）到（6）点和（8）点的距离为2，以是中心点（2,2）成为渡河的关键点.当我们挪动到（2,2）点时，就无法进行下往.故4个贩子，4个随从，船容量为2人时，无法安全渡河. 对于成绩二，我们可以建立模型为：k+1k S =S +k k D （-1）（10）'k k x x M += （11）'k k y y M += （12）k.k x y ≥（13）''k k x y ≥ （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日。

数学建模作业（四）——商人过河问题一．问题描述有四名商人各带一名仆人过河，但船最多能载二人，商人已获得仆人的阴谋：在河的任一岸，只要仆人数超过商人数，仆人会将商人杀死并窃取财物且安排如何乘船的权力掌握在商人手中。

试为商人制定一个安全过河的方案。

二．解决方案用递归的源程序如下：开始时商人，强盗所在的河的这边设为0状态，另一边设为1状态（也就是船开始时的一边设为0，当船驶到对岸是设为1状态，在这两个状态时，都必须符合条件）#include <stdlib.h>struct node /*建立一个类似栈的数据结构并且可以浏览每一个数据点*/ {int x;int y;int state;struct node *next;};typedef struct node state;typedef state *link;link PPointer1=NULL;link PPointer2=NULL;int a1,b1;int a2,b2;/*栈中每个数据都分为0，1状态*/void Push(int a,int b,int n){link newnode;newnode=(link)malloc(sizeof(state));newnode-> x=a;newnode-> y=b;newnode-> state=n;newnode-> next=NULL;if(PPointer1==NULL){PPointer1=newnode;PPointer2=newnode;}else{PPointer2-> next=newnode;PPointer2=newnode;}}void Pop()/*弹栈*/{link pointer;if(PPointer1==PPointer2){free(PPointer1);PPointer1=NULL;PPointer2=NULL;}pointer=PPointer1;while(pointer-> next!=PPointer2)pointer=pointer-> next;free(PPointer2);PPointer2=pointer;PPointer2-> next=NULL;}int history(int a,int b,int n) /*比较输入的数据和栈中是否有重复的*/ {link pointer;if(PPointer1==NULL)return 1;else{pointer=PPointer1;while(pointer!=NULL){if(pointer-> x==a&&pointer-> y==b&&pointer-> state==n)return 0;pointer=pointer-> next;}return 1;}}int judge(int a,int b,int c,int d,int n)/*判断这个状态是否可行，其中使用了history函数*/{if(history(a,b,n)==0) return 0;if(a> =0&&b> =0&&a <=3&&b <=3&&c> =0&&d> =0&&c <=3&&d <=3&&a+c==3&&b+d==3){switch(n){case 1:{if(a==3){Push(a,b,n);return 1;}else if(a==0){Push(a,b,n);return 1;}else if(a==b){Push(a,b,n);return 1;}else return 0;}case 0:{if(a==3){Push(a,b,n);return 1;}else if(a==0){Push(a,b,n);return 1;}else if(a> =b){Push(a,b,n);return 1;}else return 0;}}}else return 0;}int Duhe(int a,int b,int n)/*递归法解决商人渡河问题，如果这一个状态符合*/ {/*则判断下一个状态，直至问题解决*/ if(a==0&&b==0) return 1;if(n==0)/*判断0状态时，商匪状态是否符合要求*/{if(judge(a-1,b-1,4-a,4-b,1)){if(Duhe(a-1,b-1,1)==1)return 1;}if(judge(a,b-2,3-a,5-b,1)){if(Duhe(a,b-2,1)==1)return 1;}if(judge(a-2,b,5-a,3-b,1)){if(Duhe(a-2,b,1)==1)return 1;if(judge(a-1,b,4-a,3-b,1)){if(Duhe(a-1,b,1)==1)return 1;}if(judge(a,b-1,3-a,4-b,1)){if(Duhe(a,b-1,1)==1)return 1;}else{Pop(0);return 0;}}if(n==1)/*判断0状态时，商匪状态是否符合要求*/{if(judge(a+1,b+1,2-a,2-b,0)){if(Duhe(a+1,b+1,0)==1)return 1;}if(judge(a,b+2,3-a,1-b,0)){if(Duhe(a,b+2,0)==1)return 1;}if(judge(a+2,b,1-a,3-b,0)){if(Duhe(a+2,b,0)==1)return 1;}if(judge(a+1,b,2-a,3-b,0)){if(Duhe(a+1,b,0)==1)return 1;}if(judge(a,b+1,3-a,2-b,0))if(Duhe(a,b+1,0)==1)return 1;}else{Pop(1);return 0;}}return 0;}main(){link pointer;Push(3,3,0);Duhe(3,3,0);pointer=PPointer1;while(pointer!=NULL){printf( "%d,%d---%d\n ",pointer-> x,pointer-> y,pointer-> state);pointer=pointer-> next;}getch();}。

#include<stdio.h>#include<conio.h>#include<stdlib.h>struct Node{int x;int y;int state;struct Node *next;};typedef struct Node state;typedef state *link;link pt1=NULL;link pt2=NULL;int a1,b1;int a2,b2;/*栈中每个数据都分为，状态*/void Push(int a,int b,int n){link newNode;newNode=(link)malloc(sizeof(state)); newNode-> x=a;newNode-> y=b;newNode-> state=n;newNode-> next=NULL;if(pt1==NULL){pt1=newNode;pt2=newNode;}else{pt2-> next=newNode;pt2=newNode;}}void Pop() /*弹栈*/{link pointer;if(pt1==pt2){free(pt1);pt1=NULL;pt2=NULL;}pointer=pt1;while(pointer-> next!=pt2)pointer=pointer-> next;free(pt2);pt2=pointer;pt2-> next=NULL;}int origin(int a,int b,int n)/*比较输入的数据和栈中是否有重复的*/ {link pointer;if(pt1==NULL)return 1;else{pointer=pt1;while(pointer!=NULL){if(pointer-> x==a&&pointer-> y==b&&pointer-> state==n) return 0;pointer=pointer-> next;}return 1;}}int judge(int a,int b,int c,int d,int n)/*判断状态是否可行*/{if(origin(a,b,n)==0) return 0;if(a>=0&&b>=0&&a<=3&&b<=3&&c>=0&&d>=0&&c<=3&&d<=3&&a+c==3 &&b+d==3){switch(n){case 1:{if(a==3){Push(a,b,n);return 1;}else if(a==0){Push(a,b,n);return 1;}else if(a==b){Push(a,b,n);return 1;}else return 0;}case 0:{if(a==3){Push(a,b,n);return 1;}else if(a==0){Push(a,b,n);return 1;}else if(a>=b){Push(a,b,n);return 1;}else return 0;}}}else return 0;}int Duhe(int a,int b,int n) /*递归*/ {if(a==0&&b==0) return 1;if(n==0) /*判断状态时，商人和随从状态是否符合要求*/ {if(judge(a-1,b-1,4-a,4-b,1)){if(Duhe(a-1,b-1,1)==1)return 1;}if(judge(a,b-2,3-a,5-b,1)){if(Duhe(a,b-2,1)==1)return 1;}if(judge(a-2,b,5-a,3-b,1)){if(Duhe(a-2,b,1)==1)return 1;}if(judge(a-1,b,4-a,3-b,1)){if(Duhe(a-1,b,1)==1)return 1;}if(judge(a,b-1,3-a,4-b,1)){if(Duhe(a,b-1,1)==1)return 1;}else{Pop();return 0;}if(n==1) /*判断状态时，商人和随从状态是否符合要求*/ {if(judge(a+1,b+1,2-a,2-b,0)){if(Duhe(a+1,b+1,0)==1)return 1;}if(judge(a,b+2,3-a,1-b,0)){if(Duhe(a,b+2,0)==1)return 1;}if(judge(a+2,b,1-a,3-b,0)){if(Duhe(a+2,b,0)==1)return 1;}if(judge(a+1,b,2-a,3-b,0)){if(Duhe(a+1,b,0)==1)return 1;}if(judge(a,b+1,3-a,2-b,0)){if(Duhe(a,b+1,0)==1)return 1;}else{Pop();return 0;}}return 0;}main(){link pointer;Push(3,3,0);Duhe(3,3,0);pointer=pt1;printf("第一个数是此岸商人数量，第二个数是此岸随从数量,0表示船在此岸，代表船在彼岸:\n");while(pointer!=NULL){printf("%d,%d——%d\n",pointer-> x,pointer-> y,pointer-> state);pointer=pointer-> next;}}。

数学建模商人过河(hjh)
问题
随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货.
乘船渡河的方案由商人决定.商人们怎样才能安全过河?
分析问题
（1）,数据及其关系？（2）如何存储？（3）过程中数据上的操作？
（4）操作过程中需借助什么结构实现？
解答
（1）数据：河两岸的商人数x∈（0，3）和随从人数y∈（0，3）
关系：线性关系
（2）存储：用二维数组来实现。

（3）操作：前进（过河）、后退（返回）
（4）操作过程中需借助栈结构实现
具体分析
此岸商人数与随从人数为C【x】【y】，彼岸商人数与随从人数为B【3-x】【3-y】，C与B数组中x必须大于等于y。

C与B数组中，各个数组中每相邻两个二维数组|x+y|之差不得超过2。

其中过河途中船上人数用数组A表示A【x1】【y1】，返回途中船上人数A【x2】【y2】。

x1，x2，y1，y2=0，1，2。

x1+y1=1或2；y2+x2=1或2。

从此岸来考察，要从最开始的C【3】【3】变到C【0】【0】。

1，C【3】【3】→C【3】【1】，C【3】【1】→C【3】【2】；
2，C【3】【2】→C【3】【0】，C【3】【0】→C【3】【1】；3，C【3】【1】→C【1】【1】，C【1】【1】→C【2】【2】；4，C【2】【2】→C【0】【2】，C【0】【2】→C【0】【3】；5，C【0】【3】→C【0】【1】，C【0】【1】→C【0】【2】；6，C【0】【2】→C【0】【0】。

操作过程中需借助栈结构实现，具体如下图所示：
此岸人数已经全部转移到彼岸，任务圆满完成，商人们安全过河。

商人过河一、问题重述问题一：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;k（1） kv(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）随从 y商人 x数学模型：S k+1=S +（-1）D kx + x ' = 4kky + y ' = 4k k（2）（3）x ≥ y k.k （4）x ' ≥ y 'kk模型分析：由（2）（3）（5）可得（5）4 - x ≥ 4 - ykk化简得(( ( (( ( k（10） k综合（4）可得x = yk还要考虑x ≤ ykkk 和 S k = { x k , y k ) | x k = 0, y k = 0,1,2,3,4 }（6）S ' = { x ', y ') | x ' = 0, y ' = 0,1,2,3,4 }kkkkk（7）把（2）（3）带入（7）可得S = {(4 - x ,4 - y ) | 4 - x = 0,4 - y = 0,1,2,3,4 }kk k k k化简得S = { x , y ) | x = 4, y = 0,1,2,3,4 }kk k k k综合（6）（7）（8）式可得满足条件的情况满足下式S = { x , y ) | x = 0,4, y = 0,1,2,3,4; x = ykkkkk k k所以我们知道满足条件的点如上图所示：点移动由}（8）（9）S = { x , y ) | x = 4, y = 0,1,2,3,4 }kkkkk（8）到达S = { x , y ) | x = 0, y = 0,1,2,3,4 }kkkkk（6）时，可以认为完成渡河。

商人过河问题数学建模c语言商人过河问题是一个经典的数学建模问题，通过建立数学模型，我们可以更深入地理解问题的本质，并找到最优的解决方案。

本文将通过C语言来实现这个问题的数学建模。

一、问题描述假设有n个商人要过河，每艘船只能承载一定数量的货物，而过河需要消耗一定的时间。

为了在最短的时间内完成过河任务，我们需要考虑商人的数量、船只的承载量以及过河的时间等因素，建立相应的数学模型。

二、数学建模1. 变量定义我们需要定义一些变量来描述过河过程中的各种因素，如商人的数量、船只的数量、船只的承载量、过河的时间等。

2. 算法设计算法的核心思想是利用贪心策略，尽可能多地利用船只，以减少过河的时间。

具体步骤如下：(1) 分配船只：根据船只的承载量，将商人分配到不同的船只上；(2) 计算过河时间：根据当前船只的位置和目标河岸的位置，计算每艘船只的过河时间；(3) 更新船只位置：根据过河时间，更新每艘船只的位置；(4) 重复以上步骤，直到所有商人过河。

3. C语言实现以下是一个简单的C语言程序，实现了上述算法：```c#include <stdio.h>#include <stdlib.h>int main() {int n, m, t, i, j, k;scanf("%d%d", &n, &m); // 输入商人数量和船只数量int cargo[n], time[n]; // 定义变量数组，用于存储商人和船只的信息scanf("%d%d", &cargo[0], &time[0]); // 输入第一个商人和他的过河时间for (i = 1; i < n; i++) { // 输入剩余商人和他们的过河时间scanf("%d%d", &cargo[i], &time[i]);}int boat[m]; // 定义船只数组，用于存储船只的承载量和位置信息for (j = 0; j < m; j++) { // 输入船只的承载量和位置信息scanf("%d", &boat[j]);}for (k = 0; k < n; k++) { // 模拟过河过程for (j = 0; j < m; j++) { // 遍历所有船只if (boat[j] >= cargo[k]) { // 如果船只承载量足够承载当前商人time[k] += time[k] / boat[j]; // 根据过河时间和船只速度计算剩余时间boat[j] += cargo[k]; // 将商人转移到指定位置的船只上break; // 如果找到了足够承载商人的船只，跳出当前循环继续下一轮操作}}}printf("%d\n", time[n - 1]); // 输出最后一个商人的过河时间return 0;}```三、总结通过上述C语言程序，我们可以实现商人过河问题的数学建模。

商人们怎样安全过河的数学模型示例文章篇一：话说啊，商人们遇到了一个棘手的问题：他们得带着随从们一起过河，但随从们可不是省油的灯，一有机会就想着害商人抢货。

这河又不宽不窄，一只小船每次只能载两个人，怎么过河才能确保安全呢？咱们来聊聊这个问题吧。

首先，商人们得明白，随从们人多势众，要是他们比商人多了，那可就危险了。

所以，商人们得想个法子，让随从们没法儿耍花招。

其实啊，这个问题可以变成一个数学模型。

想象一下，我们把每次过河的人都看成是一个状态，就像打游戏一样，每过一次河就是进入了一个新的关卡。

在这个关卡里，商人们得保证自己的人数不能少于随从们。

那具体怎么做呢？咱们得先设定一些规则。

比如说，每次过河的人数只能是两个，这是小船的容量决定的。

然后，商人们得选择让哪些人过河，这就得靠他们的智慧和策略了。

想象一下这个场景：商人们先让两个随从过河，然后一个商人再带一个随从回来。

这样，河对岸的随从人数虽然多了，但商人这边还有足够的人手可以应对。

接下来，两个商人再过河，这样河对岸的商人数就比随从数多了，安全就得到了保障。

然后，再让一个商人带一个随从回来，这样河这边也有足够的商人保护随从不敢造次。

最后，两个随从再过河，问题就解决了。

这个数学模型虽然简单，但却非常实用。

它告诉我们，在面对困难和挑战时，只要我们善于运用智慧和策略，就一定能够找到解决问题的方法。

所以，商人们要想安全过河，就得靠他们的智慧和勇气了。

示例文章篇二：话说啊，有这么一个古老的谜题，叫做“商人过河”。

话说有三名聪明的商人，他们各自带着一个狡猾的随从，准备乘船过河。

这船啊，一次只能载两个人，问题就在于，这些随从们心里都有个小九九，他们密谋着，只要到了河的对岸，随从人数多于商人人数，就立马动手抢货。

这商人们也不是吃素的，他们知道随从们的阴谋，但他们毕竟都是聪明人，于是就想出了一个绝妙的策略。

咱们来想想啊，这过河其实就是一个多步决策的过程。

每次渡河，船上的人员选择都至关重要。

商人渡河数学模型
1、商人渡河数学模型
商人渡河是一类有趣的动态规划问题，其本质是一类路径规划问题，用数学模型可以描述为：
假设有n种物品，体积大小分别为W1，W2，……，Wn，以及一艘能承重V的船，每次船只能装载一些物品，要求在尽可能少的船次内，将物品搬运到对岸。

令Xij表示第i次船运载物品的状态，其中0≤Xij≤1，Xij=1表示船上装有第j个物品，Xij=0表示船上没有第j个物品，那么商人渡河问题就可以用下面的数学模型表示：
目标函数：
(1) Min Z=X11+X12+ (Xi)
约束条件：
(2) W1X11+W2X12+……+WnXin≤V
(3) X11+X12+……+Xin=1
(4) 0≤Xij≤1
其中，约束条件(2)表示第i次船运的负载不超过容量V，约束条件(3)表示每次船运必须装一些物品，约束条件(4)表示每次船运的物品的数量限制在0与1之间。

商人过河设有三名商人，各带一个随从，欲乘一小船渡河，小船只能容纳两人，须由他们自己划行。

随从们密约，在河的任何一岸，一旦随从的人数比商人多，就杀人越货。

而如何乘船渡河的大权掌握在商人们的手中。

商人们怎样才能安全渡河呢？因这已经是一个相当清晰的理想化问题，所以直接讨论其模型描述以及模型求解。

这里将其描述为一个动态决策问题：记第k次渡河前此岸的商人数为，随从数为, k=1,…,n。

将二维向量定义为状态，安全渡河条件下的状态集合称为允许状态集合，记作S, 。

记第k次渡船上的商人数为，随从数为, k=1,…,n。

将二维向量定义为决策。

考虑小船载人数的限制，应满足，而称为允许决策集合。

因为k为奇数时，船从此岸驶向彼岸；k为偶数时，船从彼岸驶回此岸，所以状态随决策的变化规律是（状态转移规律）。

求决策，使状态按照状态转移规律，由初始状态经有限步n到达状态。

接下来讨论模型的求解，设是某个可行的渡河方案所对应的状态序列，若存在某，且同为奇数或同为偶数，满足，则称所对应的渡河方案是可约的。

这时也是某个可行的渡河方案所对应的状态序列。

显然，一个有效的渡河方案应当是不可约的。

设渡河已进行到第k步，为当前的状态，记，，为保证构造的渡河方案不可约，则当前的决策除了应满足：1），且当k为奇数时，，当k为偶数时，；还须满足：2）当k为奇数时，；当k为偶数时，。

通过作图，可以得到两种不可约的渡河方案，如下图：思考题：（1）四名商人各带一名随从的情况（小船同前）。

（2）n名商人各带n名随从的情况（小船同前）。

作业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+1k S =S +k k D （-1） （1）'4k k x x += （2）'4k k y y += （3）k.k x y ≥ （4）''k k x y ≥ （5）模型分析：由（2）（3）（5）可得44kk x y -≥- 化简得k k x y ≤综合（4）可得k k x y = 和 {}(,)|0,0,1,2,3,4k k k k k S x y x y === （6）还要考虑 {}'(',')|'0,'0,1,2,3,4kk k k k S x y x y === （7） 把（2）（3）带入（7）可得{}(4,4)|40,40,1,2,3,4k k k k k S x y x y =---=-=化简得{}(,)|4,0,1,2,3,4k k k k k S x y x y === （8） 综合（6）（7）（8）式可得满足条件的情况满足下式{}(,)|0,4,0,1,2,3,4;k k k k k k k S x y x y x y ==== （9）所以我们知道满足条件的点如上图所示：点移动由{}(,)|4,0,1,2,3,4k k k k k S x y x y === （8） 到达{}(,)|0,0,1,2,3,4k k k k k S x y x y === （6）时，可以认为完成渡河。

商人们怎样安全过河随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货.但是乘船渡河的方案由商人决定.商人们怎样才能安全过河?问题分析：决策~ 每一步(此岸到彼岸或彼岸到此岸)船上的人员要求~在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河. 建立模型xk~第k次渡河前此岸的商人数 xk, yk=0,1,2,3;yk~第k次渡河前此岸的随从数 k=1,2,|....sk=(xk , yk)~过程的状态 S ~ 允许状态集合S={(x , y) x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2}uk~第k次渡船上的商人数 uk, vk=0,1,2;vk~第k次渡船上的随从数 k=1,2,.....dk=(uk , vk)~决策 D={(u , v) u+v=1, 2} ~允许决策集合~状态转移律多步决策问题求dk D(k=1,2, n), 使sk S, 并按转移律由s1=(3,3)到达 sn+1=(0,0).模型求解穷举法~ 编程上机S={(x , y) x=0, y=0,1,2,3;x=3, y=0,1,2,3;x=y=1,2}图解法状态s=(x,y) ~ 16个格点允许状态~ 10个点允许决策 ~ 移动1或2格; k奇,左下移; k偶,右上移.d1,.......，d11给出安全渡河方案评注和思考规格化方法,易于推广考虑4名商人各带一随从的情况程序%%%%%%%%%%%%%%%% 开始 %%%%%%%%%%%%%%%%%%%%%%function jueche=guoheclear allclc%%%%%%%%%%程序开始需要知道商人和仆人数；%%%%%%%%%%%%%shangren=input('输入商人数目: ');puren=input('输入仆人数目: ');rongliang=input('输入船的最大容量: ');if puren>shangrenshangren=input('输入商人数目:');puren=input('输入仆人数目:');rongliang=input('输入船的最大容量:');end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 决策生成jc=1; %决策向量放在矩阵d中，jc为插入新元素的行标初始为1；for i=0:rongliangfor j=0:rongliangif (i+j<=rongliang)&(i+j>0) % 满足条D={(u,v)|1<=u+v<=rongliang,u,v=0,1,2}d(jc,1:3)=[i,j ,1]; %生成一个决策向量立刻扩充为三维；d(jc+1,1:3)=[-i,-j,-1]; % 同时生成他的负向量；jc=jc+2; % 由于生成两个决策向量，则jc要向下移动两个；endendj=0;end%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 状态数组生成kx=1; % 状态向量放在A矩阵中，生成方法同矩阵生成；for i=shangren:-1:0for j=puren:-1:0if ((i>=j)&((shangren-i)>=(puren-j)))|((i==0)|(i==shangren))% (i>=j)&((shangren-i)>=(puren-j)))|((i==0)|(i==shangren))为可以存在的状态的约束条件 A(kx,1:3)=[i,j,1]; %生成状态数组集合D `A(kx+1,1:3)=[i,j,0];kx=kx+2;endj=puren;end;%%%%%%%%%%%%%%% 将状态向量生成抽象矩阵%%%%%%%%%%%%%%%%%%%k=(1/2)*size(A,1);CX=zeros(2*k,2*k);a=size(d,1);for i=1:2*kfor j=1:ac=A(i,:)+d(j,:) ;x=find((A(:,1)==c(1))&(A(:,2)==c(2))&(A(:,3)==c(3))) ; v(i,x)=1; %x为空不会改变v值endend%%%%%%%%%%%%%%%%%%%%%%dijstra算法%%%%%%%%%%%%%%%%%%%%%%%%%%x=1; y=size(A,1);m=size(v,1);T=zeros(m,1);T=T.^-1;lmd=T;P=T;S=zeros(m,1);S(x)=1;P(x)=0; lmd(x)=0;k=x;while(1)a=find(S==0);aa=find(S==1);if size(aa,1)==mbreak;endfor j=1:size(a,1)pp=a(j,1);if v(k,pp)~=0if T(pp)>(P(k)+v(k,pp))T(pp)=(P(k)+v(k,pp));lmd(pp)=k;endendendmi=min(T(a));if mi==infbreak;d=find(T==mi);d=d(1);P(d)=mi;T(d)=inf;k=d;S(d)=1;endendif lmd(y)==infjueche='can not reach(不能过河)';return;endjueche(1)=y;g=2; h=y;while(1)if h==xbreak;endjueche(g)=lmd(h);g=g+1;h=lmd(h);endjueche=A(jueche,:);jueche(:,3)=[]; %%%%%%%%%%%%%%%%%% 程序完 %%%%%%%%%%%%%%%%%%欢迎您的下载，资料仅供参考！致力为企业和个人提供合同协议，策划案计划书，学习资料等等打造全网一站式需求。

重庆大学（商仆过河模型）开课课程：数学模型指导教师：黄光辉小组成员：庄楚斌（20134760）自动化07班张俊铭（20133227）材料加工01班吴慧（20131966）数学01班时间：2015年3月8日一、问题提出3名商人带3名随从乘一条小船过河，小船每次只能承载至多两人。

随从们密约, 在河的任一岸, 一旦随从的人数比商人多,就杀人越货.乘船渡河的方案由商人决定，商人们如何才能安全渡河呢？二、问题分析商人与随从过河问题可以视为是一个多步决策的过程，通过多次优化，从而得到一个全局最优的决策方案。

决策的每一步，即船从此岸到达彼岸，都要对船上的商人和仆人数做出决策。

在保证河的任一岸均有商人数比随从人数多和小船每次最多只能承载两人的前提下，经有限步使所有人员到达彼岸。

三、模型假设商人和随从都会划船，天气很好，无大风大浪，且船的质量很好，可以保证很多次安全的运载商人和随从。

四、模型建立x~第k次渡河前此岸的商人数，k y~第k次渡河前此岸的随从数kx, k y=0,1,2,3; k=1,2,……kS=(k x, k y, c k )~过程的状态，其中k x, k y, c k 分别表示对应时刻此k岸的商人，仆人数以及船的行进方向，其中c 取值1表示即将向彼岸运行，为0表示即将向此岸运行S ~ 允许状态集合，S={(x , y )| x =0, y =0,1,2,3; x =3 ,y =0,1,2,3; x =y =1,2} 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 =(3,3,1)到达状态1+n S =(0,0,0(1))。