数学建模

目录摘要关键词································2一、模型的假设································3二、参数······································3三、问题分析································3四、模型的建立及其求解························5五、模型的检验································9六、模型的合理性讨论··························10七、模型的改进方向····························10八、模型的推广································10九、参考文献··································10附录······································11数学建模设计书-2-商仆安全过河问题摘要我们知道，有m队商仆过河，一只船最多载多少人，船上和岸上的仆人数不能多于商人，否则商人就会有生命危险。便使得商人安全渡河问题的提出成为必然。本文就经典数学建模模型“商人过河们如何能够安全过河问题”,采用多步决策建立了数学模型，求解得到商人们安全过河的方案。将经典的商人过河问题进行了更为深入更广泛的讨论，在此基础上着重分析了安全渡河的状态空间，建立了满足问题需求的规则，从而得出了要求解问题的方案。模型主要通过穷举的方法对各种过河的方案进行一一列举，然后根据小船的容量和商人们要安全渡河为前提对各种方案进行层层筛选。最终，得到商人安全渡河的方案。此方案适用于不同对数商仆的情况下，求的安全渡河的最合理方法。最后本文就此问题在，当有m名商人m名随从且小船的容量为k时，将会得到几种解决方案给出了说明。关键词：穷举法多步决策图解法商人过河状态空间状态向量运载向量数学建模设计书-3-一、模型的假设1.商人和仆人都会划船。2.天气很好，无大风大浪，船的质量很好，船桨足够很多次的运载商人和仆人。3.所有人最终都能到达对岸，且安全。二、参数:M表示商人的数量:N表示随从的数量:Z表示船的容量:K表示船在此岸和彼岸（K=-1表示船去彼岸，K=1表示船回此岸）:k表示船运载动作执行的次数:m表示此岸的商人数量:n表示此岸随从的数量:u表示彼岸的商人数量:v表示彼岸的随从数量:x表示船上商人的数量:y表示船上仆人的数量三、问题分析商仆安全渡河问题可以视为一个多步决策过程，多步决策是指决策过程难以一次完成，而是多步优化，最后获取一个全局最优方案的决策方法。对于每一步，即船由此岸驶向彼岸，或者船由彼岸驶向此岸的决策，不仅会影响到该过程的效果，而且还会影响到下一步的初始状态，从而对整个过程都会有影响。所以，在每一次过河时，就不能只从这一次过河本身考虑，还要把它看成是整个过河过程中的一个部分。在对船上的人员做决策时，要保证两岸的商人数不能少于仆人数，用最少的步伐是人员全部过河。应用状态向量和运载向量，找出状态随运载变化的规律，此问题就转化为状态在允许范围内（即安全渡河条件），确定每一次该如何过河，从而达到渡河的目标。现在我们都把它们数量化：即用数学语言来表示。下面我们将以10对商仆过河，船每次最多可载5人为例进行说明。数学建模设计书-4-1.状态向量的选择用二维向量（M、N）表示总状态向量。M代表总商人数，N代表总仆人数。则:（M、N）=（10、10）用二维向量（m、n）和（u、v）分别表示此岸和彼岸的状态向量。m代表此岸商人数，n代表此岸仆人数，u代表彼岸商人数，v代表彼岸仆人数。则：0≤（m、n、u、v）≤10例：（10、10）（9、8）（5、4）（7、6）（3、3）等1.可取状态向量的选择为满足题目要求，即河的任意岸上仆人数均不能超过商人数。所以可取的状态向量有：2.运载向量的选择用二维向量（x、y）表示船的运载向量。其中:x表示船上商人的数量，y表示船上的仆人数量。则：0≤（x、y）≤10例：（10、10）（9、8）（5、4）（7、6）（3、3）等3.可取运载向量的选择为满足题目要求，即船每次最多可运载Z人；也就是说船的容量为Z。而此题中Z=5。所以可取运载向量有：（0、0）（1、0）（1、1）（2、0）（2、1）（2、2）（3、0）（3、1）（3、2）（3、3）（4、0）（4、1）（4、2）（4、3）（4、4）（5、0）（5、1）（5、2）（5、3）（5、4）（5、5）（6、0）（6、1）（6、2）（6、3）（6、4）（6、5）（6、6）（7、0）（7、1）（7、2）（7、3）（7、4）（7、5）（7、6）（7、7）（8、0）（8、1）（8、2）（8、3）（8、4）（8、5）（8、6）（8、7）（8、8）（9、0）（9、1）（9、2）（9、3）（9、4）（9、5）（9、6）（9、7）（9、8）（9、9）（10、0）（10、1）（10、2）（10、3）（10、4）（10、5）（10、6）（10、7）（10、8）（10、9）（10、10）（0、1）（0、2）（0、3）（0、4）（0、5）（1、0）（1、1）（1、2）（1、3）（1、4）（2、0）（2、1）（2、2）（2、3）（3、0）（3、1）（3、2）（4、0）（4、1）（5、0）数学建模设计书-5-4.过河步骤的实现船从此岸到彼岸此岸人数减少，彼岸人数增加，总人数不变。所以：（u、v）=（M、N）-[（m、n）-（x、y）]船从彼岸到此岸此岸人数增加，彼岸人数减少，总人数不变。所以：（u、v）=（M、N）-[（m、n）+（x、y）]船的来去数学化以K表示船从此岸到彼岸或者是船从彼岸到此岸，当K=-1时船从此岸到达彼岸，当K=1时船从彼岸返回此岸。则有：（u、v）=（M、N）-[（m、n）+K（x、y）]6.过河目的的实现过河的目的是指在满足各种限制条件的情况下，最终能够使10对商仆快速而有效地过河。为了达到此目的，我们希望每完成一次往复运载动作后此岸的人数会减少，彼岸的人数会增加。要使所有人都过河，船的最后一次运载一定是从此岸到彼岸。所谓的往复一次运载就是说，船从此岸到彼岸在从彼岸返回此岸的过程。以k表示船执行过河的动作次数，则有总的船执行过河的动作次数为2k+1，而为了达到过河目的，必须使：k1kvuvu、、并且k1knmnm、、四、模型的建立及其求解1.模型的建立我们建立了一个商仆过河问题的向量关系模型，此模型保证了河的两岸仆人数不会多于商人数；过河动作不会出现死循环现象。即商仆最终可以在即安全又快速的情况下完成过河目的。模型建立如下：符号介绍S：表示总的状态向量，即：S=（M、N）=（10、10）kH：表示第k次执行运载动作时此岸的可取状态向量，即：数学建模设计书-6-kH=（m、n）kW：表示第k次执行运载动作时彼岸的可取状态向量，即：kW=（u、v）kD：表示第k次执行运载动作时的可取运载限量，即：kD=（x、y）问题描述在满足条件：kW=S-[kH+KkD]和1kW≥kW并且1kH≤kH情况下：1)求解满足要求的情况下最终使kW=S，kH=0。2)求解最优的过河步骤，即k的最优值。初始条件：S=（M、N）=（10、10）0H=S0W=00D=0正整数rr2k11-r2k1-K2.模型的解解法一：算法根据过河的要求以及过河前后，河岸两边人数的变化关系建立以下过河的算法：vuyxKnm-NM、、、、此算法原理采用多步决策过程，多步决策是指决策过程难以一次完成，而是多步优化，最后获取一个全局最优方案的决策方法。多步决策每一步的完成不仅与前一步的结果有关，同时还影响着下一步的决策。此算法先进行初值确定，然后在进行计算，接下来判断结果选择正确的结果，最后整理结果等待下一次计算。数学建模设计书-7-当1k时：）、（）、（）、（）、（）、（）、（）、（⊙）、（）、（）、（）、（）、（）、（⊙）、（）、（⊙）、（⊙）、（⊙）、（⊙）、（⊙）、（此时此岸状态向量为）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（105961068797107788898108697989991095106107108109100514042313033222120241312111015040302010051404231303322212024131211101504030201010101010注：√：该向量是此刻的可取状态向量×：该向量不是此刻的可取状态向量⊙:此过河方式满足题目各种要求数学建模设计书-8-当2k时：）、（⊙）、（⊙）、（）、（⊙）、（）、（）、（）、（）、（⊙）、（）、（）、（⊙）、（⊙）、（⊙）、（⊙）、（）、（⊙）、（⊙）、（⊙）、（）、（⊙）、（⊙）、（）、（⊙）、（）、（此时此岸的状态向量为此处出现死循环）、（）、（）、（）、（）、（）、（）、（）、（此处出现死循环）、（）、（）、（此处出现死循环）、（）、（）、（）、（）、（此处出现死循环）、（）、（）、（）、（此处出现死循环）、（）、（）、（此处出现死循环）、（）、（此处出现死循环）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（）、（10109108101099989108981010910109101091081071061010109108107101010910810101091010100010200111210212001001001020304000102030001020001000051404231303322212024131211101504030201088995106107108109101010注：√：该向量是此刻的可取状态向量×：该向量不是此刻的可取状态向量⊙:此过河方式满足题目各种要求数学建模设计书-9-vn起始点010●19●●28●●●37●●●●46●●●●●55●●●●●●64●●●●●●●73●●●●●●●●82●●●●●●●●●91●●●●●●●●●●100●●●●●●●●●●●012345678910m终点109876543210u注：只能在各‘●’点之间移动以上是第一次往复运载执行的过程，由于每一步的分支太多此处不再一一介绍。具体计算结果参考本文【附件：1】商仆过河程序运行结果。解法