5对夫妻要过河问题

数学建模论文题目：夫妻过河问题题目：夫妻过河有5对夫妻要过河，船至多可载3人，条件是任一女子不能在其丈夫不在场的情况下与另外的男子在一起，问如何安排这5对夫妻过河？摘要：主要运用状态转移矩阵的方法分析类似于夫妻过河等问题。一个系统的某些因素在转移中，第k+1次结果只受第k的结果影响，即只与当前所处状态有关，而与过去状态无关。引入状态转移这个概念。所谓状态是指客观事物可能出现或存在的状态；状态转移是指客观事物由一种状态转移到另一种状态的概率。关键词：状态转移，状态集合，图解法。正文：•问题的复述：有5对夫妻要过河，船至多可载3人，条件是任一女子不能在其丈夫不在场的情况下与另外的男子在一起，问如何安排这5对夫妻过河？•问题分析：多步决策过程：决策：每一步（此岸到彼岸或彼岸到此岸）船上的人员。过约束条件：1五对夫妻（十人）；2只有一条仅可容三人的小船；3妻子必须有丈夫在身旁。•模型假设：1不考虑五对夫妻及所带物品的重量；2五对夫妻只能依靠小船过河；•符号说明：1此岸有H个男人(丈夫),F个女人(妻子)，k为小船的行驶次数。2满足妻子必须有丈夫在身旁称允许状态，允许状态集合S。3u,v分别表示小船离岸时船上男人与女人的数量。4规定第k次运算(-1)*(u,v)由第k+1个状态57+1减去第n个状态S#来确定。建模目的：确定一系列的允许运算(k=l,2,…，m)•模型分析：假设由北岸往南岸渡河，用向量(H,F)表示有H个男子、F个女子在北岸，其中OWH,FW5,称向量(H,F)为状态向量；由条件知，有些状态是可取的，有些是不可取的，如(2,3)是不可取的，而状态(5,1)是可取的。可取状态：由己知条件知可取状态为(0,1),(1,2),(5,2),0WIW5。(1,1)为可取状态，这是因为总可以适当安排而使他们是i对夫妻。总共有16种(5,4)(5,3)(5,2)(5,1)(5,0)(0,4)(0,3)(0,2)(0,1)(0,0)(1,1)(2,2)(3,3) (4,4)(5,5)(0,5)用S表示可取状态的集合，成为允许状态集合。可取运载：(0,1),(0,2),(0,3)(1,0) (2,0),(3,0)(1,1),(2,1)其中(1,1)表示1对夫妻。用d表示可取运载集合，称为允许决策集合。•模型建立:记载k次渡河前北岸男子数为Ha，女子数为Fk，S=(H,F)称为状态；记第k次渡河船上的男子数位u,女子数为v.可取运载：取可取运载向量为也二(-1)1(u,V)其中u,v=0,1,2,3且1Wu+vW3,k=l,2,3……当k为奇数时，负向量表示过河；当k为偶数时，正向量表示由对岸返回来。贝V,我们把方程 Sh=S^dk称为状态转移律。•模型解决与结果：求解.实际上是要一步一步地考虑由一个允许状态加上一个允许运算，得出另一个允许状态的过程，试图寻求一条由初始状态(5,5)转为期望状态(0,0)的路径(当然对有些问题这种路径不一定存在)，也就是要确定一系列的允许运算d.(k=l，2,・・・,in),使得(5'5)+次+北+……+dm=(°，°)由于本问题涉及的变量不多，约束条件也不多，我们可以凭简单的用图解法进行求解。图解过程如下图图所示:(5,5)去三女K5,2)—回一女■(5,3)去两女.(5,1)回一女・去三男〈2,2)回一女一男・去三男夕0,3)—回一女.(0,4)去三女KQ1)—回•女.所以经过11次决策即可完成。(0,2)去两女.(0,0) 五对夫妻可过河！结语状态转移问题一般并不一定有解存在，有解时解法乂不一定唯一.当解法不唯一时,