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

数学建模论文

商仆过河问题

摘要

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

对于本题而言，在11名商人、11名随从、船的最大容量为6人的情况下，首先定义了渡河前此岸的状态，并设安全渡河条件下的状态集定义为允许状态集合，接着得到渡河方案的允许决策集合，然后得到状态随渡河方案变化的规律，利用matlab 7.0，win 7软件，编译运行程序得到了一种商人安全渡河的方案，并输出了允许的状态向量和允许的决策向量。

1

一 .问题的提出

当今社会每个人都想当王者，谁都想成为富翁，所以就在这个问题中仆人们也想成为商人。仆人们密约，在河的任何一边，只要仆人的数量超过商人的数量，仆人就会联合起来将商人杀死并抢夺其财物，十一名商人各带一个随从乘船渡河，一只小船只能容纳六人，由他们自己划行。在河的任意一岸，一旦随从的人数比商人多，商人就有危险．

二. 模型假设

3 模型假设

（1）每个商人和随从都会划船；

（2）只有一条船，且每条船上最多只能乘坐六个人；

（3）所有商人与随从之间没有矛盾，不会出现有人不愿意同坐一条船的现象；

（4）船在渡河的过程中不受外界环境的影响。

三． 问题符号说明

3符号说明

A 初始状态下，商人和随从所在的一岸；

B 初始状态下，商人和随从欲到达的一岸；

S 商仆对数

K 船最多载人的数目

四 .问题分析

安全渡河问题可以看成一个多步决策过程。每一步，即船由此岸驶向彼岸或从彼岸驶回此岸，都要对船上的人员(商人随从各几人)作出决策，在保证安全的前提下(两岸的商人数都不比随从数少)，在有限步内使人员全部过河。用状态(变量)表示某一岸的人员状况，决策(变量)表示船上的人员状况，可以找出状态随决策变化的规律。问题转化为在状态的允许变化范围内(即安全渡河条件)，确定每一步的决策，达到渡河的目的。

此类智力问题经过思考，可以拼凑出一个可行方案。但是，我们现在希望能找到求解这类问题的规律性，并建立数学模型，用以解决更为广泛的问题。

五. 模型的建立与求解

5.1 模型的建立

2

根据题意，可以作出商人渡河初始状态的示意图：

渡河目的：A——>B（选择A岸为参考点）

5.2matlab 程序

运行环境：matlab 7.0，win 7系统。 程序：见附件。

运行结果：部分截屏。

允许的状态向量

0 0

0 1

3

0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 0 11 1 11 2 11 3 11 4 11 5 11 6 11 7 11 8 11 9 11 10

:

0 1 0 2 0 3 0 4 0 5 0 6 1 0 1 1 2 0 2 1 2 2

4 允许的决策向量

3 0

3 1

3 2

3 3

4 0

4 1

4 2

5 0

5 1

6 0

过河步骤：

第1步：0商5仆过河，0商1仆返回

第2步：5商1仆过河，1商1仆返回

第3步：3商3仆过河，1商1仆返回

第4步：3商3仆过河，1商1仆返回

第5步：3商3仆过河，完成

过河过程中状态变化：

步骤 此岸商 此岸仆 方向 彼岸商 彼岸仆 1 11 6 ==> -8 -3 11 7 <== -8 -4 2 6 6 ==> -3 -3 7 7 <== -4 -4 3 4 4 ==> -1 -1 5 5 <== -2 -2 4 2 2 ==> 1 1 3 3 <== 0 0 5 0 0 ==> 3 3

六.结果分析

11对商仆，小船容量为2人时，问题无解：

5