数模商人过河问题报告

《数模商人过河问题报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、班级：020991姓名：刘琼学号：02099055商人安全过河问题数学建模与求解摘要本文针对商人渡河的问题，建立分步决策模型，采用分步法和状态平面分析法求解。根据题意用三维向量表示商人、随从和船的状态，并且定义此岸允许状态集合、彼岸允许状态集合及决策变量集合。然后把此岸允许状态集合和彼岸允许状态集合中的每个元素视为节点，按照状态转移规律连接这些节点构成了一个连通图，寻找安全的渡河方案最终转化为从起始状态（节点）到最终状态（节点）的路径，每一条路径对应一种渡河方案。1问题重述4名商人带4名随从乘一条小船过河，小船每次自能承载至多两人。随从们密约,在河的任一岸,一旦随从的人数比商人多,

2、就杀人越货.乘船渡河的方案由商人决定.要解决的问题：1.建立问题的数学模型；2.给出至少一个商人过河的方案；3.假如船每渡一次河需花费10元钱，尝试找出最省钱的渡河方案和安全渡河的最小费用。2模型假设（1）商人和仆人都会划船，并且仆人听从商人的调度（2）商人和仆人每次渡船都能安全到达（3）船的质量很好，在多次满载情况也能正常运作3符号说明(1)s第k次渡河前此岸商人和仆人的数量称为状态向量；k(2)s第k次渡河前彼岸商人和仆人的数量称为状态向量；k(3)S所有安全渡河条件下状态向量的集合；(4)S所有安全渡河条件下状态向量的集合；(5)d第k次渡河船上商人和仆人的数称为决策向量

3、；k(6)D所有安全渡河条件下决策向量的集合；(7)x第k次渡河前此岸的商人数；k(8)x第k次渡河前彼岸的商人数；k(9)y第k次渡河前此岸的仆人数；k(10)y第k次渡河前此岸的仆人数；k(11)u第k次渡船上的商人数；k(12)v第k次渡船上的仆人数。k4模型的建立与求解4.1问题一：模型的建立用三维向量(,xy,1)，表示安全渡河条件下此岸商人、随从和船的状态，用kk''三维向量(,xy,0)，表示安全渡河条件下彼岸商人、随从和船的状态。xx,表kkkk示商人数，yy,表示随从数，xy,的取值范围是{0,1,2,34}，；kkkk记第k次渡河前此岸的商人数为x，随从

4、数为y，k1,2,，kkxy,0,1,2,34，。将三维向量s(,xy,1)定义为此岸状态，安全渡河条件下此kkkkk岸状态集合称为此岸允许状态集合，记作S。S{(,,1)

5、xyx0或x4,y0,1,2,3,4;xy1,2,3}(1)''记第k次渡河前彼岸的商人数为x，随从数为y，k1,2,，kk'''xy,0,1,2,34，。将三维向量s(,xy,0)定义为彼岸状态，安全渡河条件下彼kkkkk'岸状态集合称为彼岸允许状态集合，记作S。'''S{(,,0)

6、xyx4或x0,y0,1,2,3,4;xy1,2,3}(2)记第k次渡船上的商人数为u，随

7、从人数为v，将二维向量d(,)uv定义kkkkk为决策变量。允许决策集合记作D，由船的容量可知D{(,)

8、1uvuv2,,uv0,1,2}(3)这样状态转移时满足以下规律''1．当k为奇数时，船从此岸到彼岸，即(,xy,1)(,xy,0)时此岸和彼岸人数kkkk变化为xxuk1kk(4)yyvk1kk''xxuk1kk(5)''yyvk1kk''2.当k为偶数时，船从彼岸到此岸，即(,xy,0)(,xy,1)时彼岸和此岸人数变kkkk化为''xxuk1kk(6)''yyvk1kkxxuk1kk(7)y

9、yvk1kk(4)(7)式称为状态转移规律。这样制定安全渡河方案归结为多步骤决策模型。4.2问题二：给出至少一个商人过河方案模型求解一（分步求解法）求解多步决策模型，即求决策变量dDk(1,2,,)n，使状态sS且kksS按照转移规律(4)(7)式，由初始状态s(4,4,1)经有限步到达状态k1's(4,4,0)。k把此岸允许状态集合S的每一个元素（状态）都当作是一个节点，同理把彼岸允许状态集合S的每一个元素（状态）也都当作是一个节点，从状态s(4,4,1)1开始，在彼岸S集合中找到满足公式(5)的节点（状态），如果在S中找到能找到了相应的节点（状态

10、），假设为sss,,则把s和sss,,用线段连接起来；1231123然后分别从sss,,出发按(6)~(7)式在S中找出满足(7)式的节点（元素），如123果在S中找到能找到了相应的节点（状态），假设为ss,则把节点sss,,分23123'别和相应ss,用线段连接，如此循环，直到到达s(4,4,0)节点。23k这样寻找安全的渡河方案就是要在图2中找到从节点s(4,4,1)到节点1's(4,4,0)的所有路径；问题转化为图论的求路径的问题，