商人过河问题数学建模

1、作业1、2 :商人过河一、问题的再研究问题1 :四个商人带着四个随从过河。 过河的工具只有小船，包括划船的人，只能同时载两个人。 侍从们的密约是，在河的每一岸，侍从的人数比商人多的话，就会杀人。 坐船渡河的方案由商人决定。 商人们怎么能安全地过河？问题2 :如果能容纳三个小船的话，最大数量的商人可以分别带着随从安全地过河。二、问题分析问题可以认为是一个多阶段的决策过程。 一步一步地从这岸到彼岸和彼岸到达这岸船的人们在安全的前提下(两岸的随从人数不比商人多)，以有限的步伐把全体人员渡过了对岸。 用状态变量表示某岸的人员状况，用决策变量表示船的人员状况，可以找到状态根据决策而变化的规律。 问题在于

2、状态允许变化的范围内(即安全渡河条件)，确定所有步骤的决定，实现安全渡河的目标。三.问题的前提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)次渡轮上的商数u(k )、v(k)

3、=0、1、2；v(k)第k次渡轮上的随从人数k=1，2d(k)=(u(k )，v(k)进程的决策d决策许可集合d=u，v|uvv=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 )。商人x随从y数学模型： (1)(2)(3)(4)(5)模型分析：可以从(2)(3)(5)中得到简单化综合(4)可获得和(6)不得不考虑。(7)可以把(2)、(3)带入(7)中简单化(8)得到综合(6)、(7)、(8)式在满足条件

4、的情况下满足下式(九)因此，满足条件的点如上图所示，点的移动(8)到达(6)有时认为渡河结束了。因为移动的格子数为2以下，从中心点(2，2 )到(6)点和(8)点的距离为2，所以中心点(2，2 )成为渡河的点。如果我们移到(2，2 )点的话，就做不到。所以4个商人，4个随从，船的容量是2人的情况下，不能安全地渡过。在问题2中，可以建立以下模型：(十)(十一)(十二)(十三)(十四)u(k )、v(k)=0、1、2、3； (十五)按照与问题1类似的顺序，坐标上的点为(3，3 )，可知最多有5名商人随行。需要确认五个商人带五个随从的方案可行，六个商人带六个随从的方案不可行如果一五个商人带了五个随从

5、：(1)首先，三个商人不能先过河。 两个商人一个随从过河。 一个商人两个随从过河(2)三个随从先过河(5，2 )，一个随从(5，3 )，过去两个随从(5，1 )一个随从(5，2 )，过去三个商人(2，2 )，一个商人一个随从(3，3 )，过去三个商人(0，3 )，一个随从(0，4 )，过去由此可见，五个商人带着五个随从，小船可以载着三个人过河如果两六个商人带了六个随从：(1)首先，三个商人不能先过河。 两个商人一个随从过河。 一个商人两个随从过河(2)三个随从先过河(6，3 )，一个随从(6，4 )，过去两个随从(6，3 )，过去三个商人(3，3 )，此时两岸都是(3，3 )，坐标法表明这是离终点最近的临界点，但回来时一定是一个人如上所述，六个商人带着六个随从，小船三个的话就过不去了据一、二，小船上最多坐三个人时，最多能有五个商人各带一个随从过河。5 .模