商人过河的数学模型及编程解决.doc

《商人过河的数学模型及编程解决.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、14对商仆过河问题题目有14名商人各带一名仆人要过河，但船最多能载4人。商人已获得仆人的阴谋：在河的任意一岸，只要仆人数超过商人数，仆人会将商人杀死并窃取货物。安排如何乘船的权利权利在商人手上，试为商人制定一个安全的过河方案。一．摘要n对商仆过河，一只船最多载m人，船上和岸上的仆人数都不能多于商人数，否则商人有危险。安排合理的渡河方案，保证商人能安全渡河。（可利用向量，矩阵，图解等方法）。二．问题提出：有14对商仆乘船过河，一只船最多载4人，由商人和仆人自己划船渡河，在河的任意一岸，一旦仆人数多于商人数，仆人就可将商人杀死，谋取利益，但是乘船渡河的主动权掌握在商人们手中，商

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

3、安全渡河条件），确定每一次该如何过河，从而达到渡河的目标。现在我们都把它们数量化：即用数学语言来表示。四．模型假设与符号假设（一）模型假设商人和仆人都会划船，天气很好，无大风大浪，船的质量很好，船桨足够很多次的运载商人和仆人。（二）符号假设设（x，y）是状态向量，表示任一岸的商人和仆人数，且x，y分别要大于等于0，小于等于M。1.设（m，n）是运载向量，表示运载的商人数和仆人数，0<=m<=N，0<=n<=N，0<=m+n<=N。2.设用s表示所有的可取状态向量的集合。3.设用d表示所有运载向量的集合。4.设用表示从此岸到彼岸，作减；用表示从彼岸到此岸，作加。Sk：表示第k

4、步可取状态向量（Sk属于s）；dk：表示第k步可取转移向量（dk属于d）；五．模型的建立我们以3名商人为例。设第k次渡河前此岸的商人数为xk，随从数为yk，k=1，2，…，xk，yk=0，1，2，3，将二维向量Sk=（xk，yk）定义为状态。安全渡河条件下的状态集合称为允许状态集合，记为S，则允许状态集合为：S={（x，y）

5、x=0或3，y=0，1，2，3，x=y=1，2}（1）又设第k次渡船上的商人数为uk，随从数为vk，将二维向量dk=（uk+vk）定义为决策。则允许决策集合为：D={（u，v）

6、u+v=1，2}（2）因为k为奇数时船从此岸驶向彼岸，k为偶数时船由彼岸驶

7、向此岸，所以状态Sk随着决策dk变化的规律即状态转移规律是：Sk+1=Sk+（-1）kdk（3）这样，制定安全渡河方案归结为如下的多步决策问题：求决策dk∈D（k=1，2，…，n），使状态Sk∈S按照规律（3），由初始状态S1=（3，3）经有限步（设为n）到达状态Sn+1=（0，0）。六．模型的简化与求解下面通过程序给出这个多步决策问题的一个解：a[1]={0，0}；a[2]={0，1}；a[3]={0，2}；a[4]={0，3}；a[5]={3，0}；a[6]={3，1}；a[7]={3，2}；a[8]={3，3}；a[9]={1，1}；a[10]={2，2}；（*以上给

8、出10个允许的状态*）d[1]={0，2}；d[2]={2，0}；d[3]={1，1}；d[4]={0，1}；d[5]={1，0}；（*以上表示给出5个允许的决策*）i=1；j=1；k=1；s[0]=s[1]={3，3}；Print[″此岸————船上————对岸″]；Do[Do[s[i+1]=s[i]+（-1）^id[j]；t=0；Do[If[s[i+1]==a[k]，t=1]，{k，1，10}]；If[t==0，Continue[]]；（*以上是保证状态属于允许的状态*）l=Mod[i+1，2]；m=l；u=0；If[i+1>=3，Do[If[s[i+1]==s[m]，

9、u=1，Break[]]，{m，l，i-1，2}]]；If[u==0，c[i+1]=d[j]；Break[]]，{j，1，5}]；If[t==0，Print[No，Result]；Break[]]；b[i+1]={3，3}-s[i+1]；Print[s[i]，″----″，c[i+1]，″----″，b[i+1]]；If[s[i+1]=={0，0}，Break[]]，{i，1，12}]程序运行结果如下：此岸——————船上——————对岸{3，3}——————{0，2}——————{0，2}{3，1}——————{