第四章
浙江大学数学建模 实践基地
基于线性代数与 差分方程方法的模型
在第三章中,我们有多处对不连续变化的变量采取了连续
化的方法,从而建立了相应的微分方程模型。但是由于以
下原因:
第一,有时变量事实上只能取自一个有限的集合;
第二,有时采取连续化方法后建立的模型比较复杂,无法
求出问题的解,从而只能求它们的数值解。也就是说,在
建模时我们对离散变量作了连续化处理,而在求解时,又
对连续变量作了离散化处理,使之重新变为离散变量。所
以采取连续化方法的效果有时并不很好,因而是不可取的。
电子计算机的广泛应用为我们处理大量信息
提供了实现的可能,这就十分自然地提出了
一个问题,对具有离散变量的实际问题直接
建立一个离散模型是否更为可取?本章介绍
的几个模型就是基于这种想法建立起来的。
§ 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,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,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,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 )
?
?
?
?
?
?
?
?
?
?

以下可继续进行下去,直至转移目的实现。上述分析实际
上采用的是穷举法,对于规模较大的问题是不宜采用的。
例 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)的转移问题。和上题一样,
我们既可以用计算机求解,也可以分析求解,此外,本题还
可用 作图 方法来求解。
在 H~W平面坐标中,以, ·”表示可取状态,从 A(3,3)经奇数
次转移到 达 O(0,0)。奇数次 转移时向左或下移 动 1-2格而落
在一个可取状态上,偶数次 转移时向右或上移 动 1-2格而落在
一个可取状态上。为了区分起见,用 红 箭线表示 奇 数次转移,
用 蓝 箭线表示第 偶 数 次转移,下图给出了一种可实现的方案,

A(3,3)
O(0,0) H
W
这 三 对夫妻是可以过河的 。假如按
这样的方案过 河,共需经过 十一 次摆
渡。
不难看出,在上述规则下,4对夫妻就
无法过河了,读者可以自行证明之,类
似可以讨论船每次可载三人的情况,
其结果 是 5对夫妻是可以过河的,而
六 对以上时就 无法过河 了。