第四章 + 浙江大学学建模实溅基地
第四章 浙江大学数学建模 实践基地
基于线性代数与差分方程方法的模型 在第三章中,我们有多处对不连续变化的变量采取了连续 化的方法,从而建立了相应的微分方程模型。但是由于以 下原因: 第一,有时变量事实上只能取自一个有限的集合; 第二,有时采取连续化方法后建立的横刑比较复,无法 求出间题的电子计算机的广泛应用为我们处理大量信息 建模时我们提供了实现的可能,这就十分自然地提出了 对连续变量一个问题,对具有离散变量的实际间题直接 以采取连续建立一个离散模型是否更为可取?本章介绍 的几个模型就是基于这种想法建立起来的
基于线性代数与 差分方程方法的模型 在第三章中，我们有多处对不连续变化的变量采取了连续 化的方法，从而建立了相应的微分方程模型。但是由于以 下原因： 第一，有时变量事实上只能取自一个有限的集合； 第二，有时采取连续化方法后建立的模型比较复杂，无法 求出问题的解，从而只能求它们的数值解。也就是说，在 建模时我们对离散变量作了连续化处理，而在求解时，又 对连续变量作了离散化处理，使之重新变为离散变量。所 以采取连续化方法的效果有时并不很好，因而是不可取的。 电子计算机的广泛应用为我们处理大量信息 提供了实现的可能，这就十分自然地提出了 一个问题，对具有离散变量的实际问题直接 建立一个离散模型是否更为可取？本章介绍 的几个模型就是基于这种想法建立起来的
s41状态转移问题g 所谓状态转移问题讨论的是在一定的条件下,系统由一状态 逐步转移到另一状态是否可能,如果可以转移的话,应如何 具体实现? 例4.1人、狗、鸡、米过河问题 这是一个人所共知而又十分简单的智力游戏。某人要带狗、 鸡、米过河,但小船除需要人划外,最多只能载一物过河, 而当人不在场时,狗要咬鸡、鸡要吃米,问此人应如何过河 在本问题中,可采取如下方法:一物在此岸时相应分量为1, 而在彼岸时则取为0,例如(1,0,1,0)表示人和鸡在此岸, 而狗和米则在对岸
§4.1 状态转移问题 所谓状态转移问题讨论的是在一定的条件下，系统由一状态 逐步转移到另一状态是否可能，如果可以转移的话，应如何 具体实现？ 例4.1 人、狗、鸡、米过河问题 这是一个人所共知而又十分简单的智力游戏。某人要带狗、 鸡、米过河，但小船除需要人划外，最多只能载一物过河， 而当人不在场时，狗要咬鸡、鸡要吃米，问此人应如何过河。 在本问题中，可采取如下方法：一物在此岸时相应分量为1， 而在彼岸时则取 为0，例如（1,0,1,0）表示人和鸡在此岸， 而狗和米则在对岸
(i)可取状态:根据题意,并非所有状态都是允许的,例如 (0,1,1,0)就是一个不可取的状态。本题中可取状态(即系 统允许的状态)可以用穷举法列出来,它们是: 在此岸 人在对岸 1,1,1,1)(0,0,0,0) 1,1,1,0)(0,0,0,1) 1,0,1 1,0,1 ,, 1)(0,1,0,0) 0)(0,1,0,1 共有十个可取状态,对一般情况,应找出状态为可取的充 条件。 (i)可取运算:状态转移需经状态运算来实现。在实际问题 ,摆一次渡即可改变现有状态。为此也引入一个四维向量 (转移向量),用它来反映摆渡情况。例如(1,1,0,0) 示人带狗摆渡过河。根据题意,允许使用的转移向量只能 (1,0,0,0,)、(1,1,0,0)、(1,0,1,0) 0,1)四个
（i）可取状态：根据题意，并非所有状态都是允许的，例如 （0,1,1,0）就是一个不可取的状态。本题中可取状态（即系 统允许的状态）可以用穷举法列出来，它们是： 人在此岸 人在对岸 (1，1，1，1) (0，0，0，0) (1，1，1，0) (0，0，0，1) (1，1，0，1) (0，0，1，0) (1，0，1，1) (0，1，0，0) (1，0，1，0) (0，1，0，1) 总共有十个可取状态，对一般情况，应找出状态为可取的充 要条件。 （ii）可取运算：状态转移需经状态运算来实现。在实际问题 中，摆一次渡即可改变现有状态。为此也引入一个四维向量 （转移向量），用它来反映摆渡情况。例如 （1，1，0，0） 表示人带狗摆渡过河。根据题意，允许使用的转移向量只能 有（1，0，0，0，）、（1，1，0，0）、（1，0，1，0）、 （1，0，0，1）四个
规定一个状态向量与转移向量之间的运算。规定状态向量与 转移向量之和为一新的状态向量,其运算为对应分量相加, 且规定0+0=0,10=0+1=1,1+1=0。 在具体转移时,只考虑由可取状态到可取状态的转移。问题 化为: 由初始状态(1,1,1,1)出发,经奇数次上述运算转化为 (0,0,0,0)的转移过程。 我们可以如下进行分析 (第一次渡河) (1,1,0,0)(0,0,1,1)×(不可取) (1,1,1,1) (1,0,1,0)(0,1,0,1) (可取) (1,0,0,1)(0,1,1,0)×(不可取) (1,0,0,0)(0,1,1,1)×(不可取)
规定一个状态向量与转移向量之间的运算。规定状态向量与 转移向量之和为一新的状态向量，其运算为对应分量相加， 且规定0+0=0，1+0=0+1=1，1+1=0。 在具体转移时，只考虑由可取状态到可取状态的转移。问题 化为： 由初始状态（1，1，1，1）出发，经奇数次上述运算转化为 （0，0，0，0）的转移过程。 我们可以如下进行分析 ： （第一次渡河） (不可取) (不可取) (可取) (不可取) (0,1,1,1) (0,1,1,0) (0,1,0,1) (0,0,1,1) (1,0,0,0) (1,0,0,1) (1,0,1,0) (1,1,0,0) (1,1,1,1) = +
(第二次渡河) (1,1,0,「(1,0,0,1 (不可取) (1,0,1,(1,1,1,1(循环,回到原先出班的状态 (0,1,0,1 (1,0,0,(1,1,0,0) (不可取) (1,0,0,(1,1,0,1) (可取) 以下可继续进行下去,直至转移目的实现。上述分析实际 上采用的是穷举法,对于规模较大的问题是不宜采用的
（第二次渡河） + (1,0,0,0) (1,0,0,1) (1,0,1,0) (1,1,0,0) (0,1,0,1) (可取) (不可取) (循环,回到原先出现过的状态) (不可取) (1,1,0,1) (1,1,0,0) (1,1,1,1) (1,0,0,1) ＝ 以下可继续进行下去，直至转移目的实现。上述分析实际 上采用的是穷举法，对于规模较大的问题是不宜采用的
例42夫妻过河间题 这是一个故可如下定义 过河,可取状态:用H和W分别表示此岸的男子和女子 法律,数,状态可用矢量(H,W表示,其中0≤H 他男子/W3。可取状态为(0,),(,(3,,053 i为可取状态,这是因为总可以适当安排而使他 们是对夫妻 (i)可取运算 过河方式可以是一对夫妻、两个男人或两个女人, d当然也可以是一人过河。转移向量可取成( 1)ym2(-1ym),其中m、n可取0、1、2,但必须 满足1mm≤2。当为奇数时表示过河。当为偶 数时表示由对岸回来,运算规则同普通向量的加 法
例4.2 夫妻过河问题 这是一个古老的阿拉伯数学问题。有三对夫妻要 过河，船最多可载两人，约束条件是根据阿拉伯 法律，任一女子不得在其丈夫不场的情况下与其 他男子在一起，问此时这三对夫妻能否过河？ 这一问题的状态和运算与 前一问题有所不同，根据 题意，状态应能反映出两 岸的男女人数，过河也同 样要反映出性别 故可如下定义： （i） 可取状态： 用H和W分别表示此岸的男子和女子 数，状态可用矢量 （H，W）表示，其中0≤H、 W≤3。可取状态为（0,i），(i,i)，(3,i)，0≤i≤3。 (i,i)为可取状态，这是因为总可以适当安排而使他 们是 i对夫妻。 （ii）可取运算： 过河方式可以是一对夫妻、两个男人或两个女人， 当然也可以是一人过河。转移向量可取成 ((－ 1)im,(－1)in)，其中m、n可取0、1、2，但必须 满足1≤m+n≤2。当j为奇数时表示过河。 当j为偶 数时表示由对岸回来，运算规则同普通向量的加 法
问题归结为由状态(3,3经奇数次可取运算,即由可取状 态到可取状态的转移,转化为(0,0的转移问题。和上题一样, 我们既可以用计算机求解,也可以分析求解,此外,本题还 可用作图方法来求解 在HW平面坐标中,以“”表示可取状态,从A(33)经奇数 次转移到达o(00)。奇数次转移时向左或下移动1-2格而落 在一个可取状态上,偶数次转移时向右或上移动1-2格而落在 个可取状态上。为了区分起见,用红箭线表示奇数次转移 用蓝箭线表示第偶数次转移,下图给出了一种可实现的方案, 故 这三对夫妻是可以过河的。假如按 WL111A(3)这样的方案过河,共需经过十次摆 渡 不难看出,在上述规则下,4对夫妻就 无法过河了,读者可以自行证明之类 似可以讨论船每次可载三人的情况, o(0,0) H其结果是5对夫妻是可以过河的而 六对以上时就无法过河了
问题归结为由状态 (3,3)经奇数次可取运算，即由可取状 态到可取状态的转移，转化 为(0,0)的转移问题。和上题一样， 我们既可以用计算机求解，也可以分析求解，此外，本题还 可用作图方法来求解。 在H~W平面坐标中，以 “·”表示可取状态， 从A(3,3)经奇数 次转移到 达O(0,0)。奇数次转移时向左或下移 动1-2格而落 在一个可取状态上，偶数次转移时向右或上移 动1-2格而落在 一个可取状态上。为了区分起见 ,用红箭线表示奇数次转移， 用蓝箭线表示第偶数 次转移,下图给出了一种可实现的方案 , 故 A(3,3) O(0,0) H W 这三对夫妻是可以过河的 。假如按 这样的方案过 河,共需经过十一次摆 渡。 不难看出 ,在上述规则下,4对夫妻就 无法过河了,读者可以自行证明之.类 似可以讨论船每次可载三人的情况, 其结果 是5对夫妻是可以过河的,而 六对以上时就 无法过河了