求解夫妻过河问题83275933

求解夫妻过河问题83275933本科生毕业论文论文题目:matlab求解夫妻过河问题摘要渡河问题.1始于公元8世纪，至今它仍是一个逻辑难题，许多数学建模教材上已经提到.这个问题指的是：有不同的对象或生物，他们其中一些相互不共存，逐步地让一小群体从河的一岸到另一岸，经过有限步后，该群体全部从一岸达到另一岸，并且要求没有任何损失．在渡河问题的夫妻过河问题中我们发现状态转移问题有时不一定有解，有时的解又不一定有规律，本文对于夫妻过河问题利用图解法和matlab编写程序求解5对、6对夫妻过河是否有解，并推广到n对夫妻与船的运载能力m对于能否安全渡河时它们之间的关系。关键词：多步决策matlab数学模型渡河问题ProblemofcouplesacrosstheriverAbstract:theproblemofcrossingtheriver.Inthe8thcentury,itstillisalogicalproblem,manymathematicalmodelingteachingmaterialhasbeenmentioned.Thequestionis:havedifferentobjectsorcreatures,theylacksomemutualcoexistence,graduallytoasmallgroupfromonebanktoanotherbankoftheriver,afterfinitesteps,thegroupallfromonesidetotheothershore,andrequiresnolosses.Incrossingtheriverproblemofcouplesacrosstheriver,wefoundthatstatetransitionproblemsometimesdoesnotnecessarilyhaveasolution,sometimesthesolutionisnotnecessarilyregular,inthispaper,usingthegraphicalmethodfortheproblemofcouplesacrosstheriverandthematlabprogramtosolvethe5,6forcoupleacrossariverifthereisasolution,Andderivedtoncouplewiththeabilitytorunmtosafecrossingtheriverwhentherelationshipbetweenthem.Keywords:MultistepdecisionMatlabMathematicalmodelProblemofcrossingtheriver目录1引言................................................................12文献综述............................................................12.1国内外研究现状......................................................12.2国内外研究现状评价..................................................22.3问题提出............................................................23模型假设............................................................24符号说明............................................................25重述3、4对夫妻过河问题的解.........................................35.13对夫妻过河的解.....................................................35.24对夫妻过河的解.....................................................36五对夫妻过河模型....................................................46.1模型构成............................................................46.2模型建立............................................................46.3模型求解............................................................46.31Matlab编程求解.....................................................46.32图解法.............................................................77六对夫妻过河模型....................................................87.1模型构成............................................................87.2模型求解............................................................98n对夫妻过河情况....................................................108.1求解...............................................................108.2验证...............................................................119总结与展望.........................................................129.1总结...............................................................129.2后续研究工作展望....................................................13参考文献...............................................................14附录..................................................................1511引言这是一个古老的阿拉伯数学问题。有3对夫妻要过河，船最多可载2人，约束条件是根据阿拉伯法律，任一女子不得在其丈夫不在场的情况下与其他男子在一起，问此时这3对夫妻能否过河？如果是4对夫妻过河，其他条件不变的情况下，夫妻能否过河？就这一问题我们发现状态转移问题有时不一定有解，有时的解又不一定有规律（当4对夫妻过河，其他条件不变的情况下，夫妻能否过河？我们发现此问题是无解的），但是当我们改变条件船最多可载3人时有解.就其数学建模思想来说,一般采用将该问题转化为一个多步决策模型,模型求解的方法大多为图解法然而一旦问题的条件(例如丈夫、妻子或者小船上每次渡河人数等)发生变化,图解法求解犹如大海捞针!很难奏效.因此计算机编程求解模型的方法就显得非常重要了.该题求解编程的难点在于允许状态与决策这两个方面的处理与实现2.此问题中利用的多目标决策方法是从20世纪70年代中期发展起来的一种决策分析方法.决策分析是在系统规划、设计和制造等阶段为解决当前或未来可能发生的问题，在若干可选的方案中选择和决定最佳方案的一种分析过程.在社会经济系统的研究控制过程中我们所面临的系统决策问题常常是多目标的，例如我们在研究生产过程的组织决策时，既要考虑生产系统的产量最大，又要使产品质量高，生产成本低等。这些目标之间相互作用和矛盾，使决策过程相当复杂使决策者常常很难轻易作出决策.这类具有多个目标的决策总是就是多目标决策.多目标决策方法现已广泛地应用于工艺过程、工艺设计、配方配比、水资源利用、能源、环境、人口、教育、经济管理等领域.2文献综述2.1国内外研究现状渡河问题有不同的版本，从目前参阅的文献资料中了解的信息来看文献[1]、[5]、[6]的商人和随从渡河问题利用通过遍历状态空间树来搜索可行的渡河方案、建立多步决策模型、计算机编程等方法解决,文献[3]、[4]的传教士和食人族难题3仿照整数(二元)规划的图示方法、用矩阵表示与迭代算法4等方法解决，文献[5]军官渡河问题和人与机器渡河问题5利用Dijkstra算法,文献[13]的人、猫、鸡、米过河问题利用计算机C语言编程求解，文献[6]、[15]的人、狼、羊、菜过河问题利用多为向量的方法解2决6.但是解决方法是类似的,都是要找到允许状态和允许决策7.2.2国内外研究现状评价综上所述，渡河问题至今仍是一个逻辑难题.国内外对于过河问题的研究很多，但是不是很全面，由于渡河问题的种类很多，尽管研究方法大体相同，但是他的解却是有很多种，或者有的问题根本无解，就夫妻过河问题而言当4对夫妻过河，船只能载2人时问题无解.本文在夫妻过河问题的基础上从3对、4对夫妻研究至5对、6对，并推至n对夫妻过河情况，利用图解法和matlab编程解决.2.3问题提出问题1：若船最多能载3人，5对夫妻能否过河？六对夫妻呢？如果不可以那么船最多能载几人才可以？问题2：n对夫妻要过河，船最多能载m人，n和m有怎样的关系？任务：用matlab编写程序求问题1的解，并用已有程序验证问题2.3模型假设1.不考虑过河环境因素的影响情况；2.夫妻过河只能依靠小船；3.每个男人和女人都会划船；4符号说明i表示渡河的夫妻对数kF表示第k次渡河前此岸丈夫的人数kQ表示第k次渡河前此岸妻子的人数kx表示第k次过渡船上丈夫的人数ky表示第k次过渡船上妻子的人数k表示第几次渡河n表示渡河的次数S表示允许状态集合D表示允许决策集合3ks表示状态kd表示决策5重述3、4对夫妻过河问题的解有3对夫妻要过河，船最多可载2人，约束条件是根据阿拉伯法律，任一女子不得在其丈夫不在场的情况下与其他男子在一起，问此时这3对夫妻能否过河？如果是4对夫妻过河，其他条件不变的情况下，夫妻能否过河？记k次过河前此岸丈夫的人数为kF，妻子的人数为kQ.记ks表示状态，ks=（FQ）,记kd表示决策，kd=（xy）。5.13对夫妻过河的解5.24对夫妻过河的解可看出问题无法再解下去（3,3）去二女（3,2）去二女（3,1）回一女（3,0）回一女（3,1）去二男（1,1）回一男一女（2,2）去二男（0,2）去一女（0,3）去二女（0,1）回一女（0,2）去二女（0,0）（4,4）去二女（4,2）回一女（4,3）去二女（4,1）回一女（4,2）（4,0）去两女去两男（4,0）46五对夫妻过河模型6.1模型构成记第k次过河前此岸丈夫的人数为kF，妻子的人数为kQ，k=1,2，3……由已知条件知可取状态为（0,1）（0,2）（0,3）（0,4）（0,5）（0,0）（5,5）（5,4）（5,3）（5,2）（5,1）（5,0）（1,1）（2,2）（3,3）（4,4）共16种，用S表示可取状态集合，成为允许状态集合，不难验证，S对此岸和彼岸都是可行的.记第k次过渡船上的丈夫的人数为kx，妻子的人数为ky，由已知条件知可取状态为（0,1）（0,2）（0,3）（1,0）（2,0）（3,0）