商人过河问题数学建模

商人过河问题数学建模．

作业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~允许状态集合

x=0,y=0,1,2,3,4; x=4,y=0,1,2,3,4;x=y=1,2,3} S={(x,y)?u(k), v(k)=0,1,2;

次渡船上的商人数k第u(k)~

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

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

u+v=1,2,u,v=0,1,2}

?D={u,v

状态转移律状态因决策而改变s(k+1)=s(k)+(-1)^k*d(k)~律按转移.n),使s(k)并?求d(k)S?D(k=1,2,…）到达（0,0）

s(k+1)=s(k)+(-1)^k*d(k)由（4,随商

k D（-1）S=S+（1数学模型：）k kk+1

4x?x'?kk（2）

4y'?y?kk 3）（x?y k k.（4）

'?'xy kk（5）模型分析：）可得5（）3（）2由（．

y?x?44?kk化简得x?y

kk综合（4）可得

x?y??,10?,y)?|x0yS?,(x和kk kkkkk 6（）还要考虑??,2,3,4?0,1'y')|x'?0,?'yS(x',（7）kkkkk把（2）（3）带入（7）可得

??,2,3,4?0,10,4?yy)|4?x?S?,4(4?x?kkkkk

化简得

??,2,3,40,1??(x,y)|x4,y?S（8 ）kkkkk 综合（6）（7）（8）式可得

满足条件的情况满足下式

??yx?y?0,1,2,3,4;,(xy)|x?S?0,4,（9 ）kkkkkkk

所以我们知道满足条件的点如上图所示：点移动由

??,2,3,40,1xS?(x,y)|?4,y?）8 （kkkkk到达

??,2,3,4?0,y0,1?)?S,(xy|x（6）kkkkk时，可以认为完成渡河。

因为移动的格数小于等于2，只有中心点（2，2）到（6）点和（8）点的距离为2，所以中心点（2,2）成为渡河的关键点。

当我们移动到（2,2）点时，就无法进行下去。

人时，无法安全渡河。2个随从，船容量为4个商人，4故．

对于问题二，我们可以建立模型为：

k D（-1）S=S+k k+1k（10）

x?x'?M kk

（11）

y?y'?M kk（12）

x?y k k.（13）

x'?y'kk（14）

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

通过类似于问题一的步骤可以知道：坐标上的关键点是（3,3），最多可以五名商人带五名随从过去。

需要确定五名商人带五名随从的方案可行再确定六名商人带六名随从的方案不可行

1、五名商人带五名随从的情况：