第4章 线性代数模型

陕西科技大学理学院第四章线性代数模型§4.1几个数学游戏向量、向量空间、矩阵等都是线性代数中的重要概念，本节将通过一些简单的实例来说明它们在实际中的应用。例4.1（人、狗、鸡、米过河问题）这是一个人所共知而又十分简单的智力游戏。某人要带狗、鸡、米过河，但小船除了需要有人去划以外，最多只能载一物过河，而当人不在场时，狗要咬鸡、鸡要吃米，问此人应如何过河。要知道例4.1的答案并不困难。第一次，人只能带鸡过河。到了对岸，人只有自己回来，将鸡留在对岸，否则，又返回了初始状态。接下来，人可以带狗过河，也可以带米过河，但回来时有一定要将鸡带回，……，按此推导下去，读者不难找到过河方法。我们研究本例的目的不在于找出答案，而是想设计出一种让计算机自行搜索寻找答案的方法。为此目的，我们先把例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）+（1，0，1，0）=（0，1，0，1），其实际意义为人狗鸡米原来均在此岸，人带鸡过河，转变为新的状态此岸仅剩狗和米，（注：此处作这样的运算规定完全是为了与实际情况相符）。在具体转移时，只考虑由可取状态到可取状态的转移。问题化为：由初始状态（1，1，1，1）出发，经过奇数次的上述运算能否转化为（0，0，0，0）的转化问题，进而，如果能，我们还想知道具体应当如何转化。由于规定的运算十分容易在计算机上实现，这样一来就把一个数学游戏转化为了一个可以在计算机上计算的数学问题（即建模）。当然，像本题这样简单的问题，也可通过笔算方法求解，具体可如下进行分析（第一次渡河）)()()()()1,1,1,0()0,1,1,0()1,0,1,0()1,1,0,0()0,0,0,1()1,0,0,1()0,1,0,1()0,0,1,1()1,1,1,1(不可取不可取可取不可取（第二次渡河）)0,0,0,1()1,0,0,1()0,1,0,1()0,0,1,1()1,0,1,0(=)()(),()()1,0,1,1()0,0,1,1()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格而落在一个可取状态上。另外，由于奇数次与偶数次过河产生的效果是不同的，为了区分起见，用实箭线表示奇数次转移，用虚箭线表示第偶数转移，图4-1给出了一种可实现的方案，故（图4-1）这三对夫妻是可以过河的。假如按这样的方案过河，共需经过十一次摆渡。不难看出，在上述规则下，4对夫妻就无法过河了，读者可以自行证明之。类似可以讨论船每次可载三人的情况，其结果是5对夫妻是可以过河的，而六对以上时就无法过河了。假如船每次可以载四人，则任意多对夫妻均可过河，最易看出的一个方案是让一对夫妻当船员工即可。关于夫妻过河还可以编出许多其他形式的问题，下面我们来讨论一些同样有趣的问题。为了叙述简便，先约定一些符号，这些符号将被应用于以下的各个问题之中。记想过河的夫妻对数为n，船可载的人数为m，n对夫妻过河所需的最少摆渡次数为k。（问题1）2对夫妻要过河，船每次只能渡2人，应如何过河，最少摆渡几次？（即n=2，m=2，求k=?）本问题很容易解答，读者可自行完成（答案为k=5）。（问题2）n对夫妻要过河，船每次可载n-1人，应如何过河，最少要摆几次渡？（n=m-1，求k=?）。答案如下：（1）n=3，m=2，k=11（2）n=4，m=3，k=9（3）n≥5，m=n-1，k=7（问题3）1883年，吕卡斯（Récréations）提出以下问题：n对夫妻要过河，船至少应可载几人（m≥?）他们才可能过河，最少摆渡次数为多少？德兰努瓦（M.Delannoy）证明：（1）n=2，m=2，k=5（2）n=3，m=3，k=11（3）n=4，m=3，k=9（4）n=5，m=3，k=11（5）n≥6，m=4,k=2n-3（问题4）德丰特内（M.DeFonteney）指出，如果河中有一个岛，那么，不管有多少对夫妻，只要有一只可载2人的船，他们均能过河（2对、3对时不需要岛），最少摆渡次数为68n。更难的还可以考虑如下一类问题：（1）阿拉伯妇女生活于闺阁之中，她们应不会划船，此时问题又会怎样？（2）阿拉伯男子可以娶妾，假如有n位男人带着他们各自的妻妾过河，问题的结果又会变成怎样？这些问题因过于复杂，我们就此搁笔，不再继续讨论下去了。上面介绍的几个例子本身并无多大实际意义，但它们展示了如何将实际问题转化为状态转移问题的方法，这种方法是值得借鉴的。§4.2Dürer魔方（或幻方）问题有些较为复杂的问题，开始时常常给人以一种变幻莫测的感觉。但经过细微的分析研究，可以发现其中存在着某些内在的关系。在使用适当的数学工具后，这些内在关系就被一一揭露出来了。德国著名的艺术家AlbrechtDürer(1471-1521)于1514年曾铸造了一枚名为“MelencotiaI”的铜币。令人奇怪的是在这枚铜币的画面上充满了数学符号、数字及几何图形。这里，我们仅研究铜币右上角的数字问题。1、Dürer魔方这是一个由自然数组成的方块，称之为Dürer魔方，其数字排列如下：49516156103147112112813什么是魔方？我们来下一个定义。我们所谓的魔方是指由1~n2这n2个正整数按一定规则排列成的一个n行n列的正方形。按不同的要求，它可以具有某些特定的性质，n称为此魔方的阶。例如，上面给出的Dürer魔方是4阶的，它的每一行数字之和为34，每一列数字之和为34，把对角线（或反对角线）上的数字加起来是34，每个小方块中的数字之和也是34，若把四个角上的数字加起来还是34，多么奇妙！最后一行中间两个数字恰好是铜币的铸造时间——1514年。构造魔方是一个古老的数学游戏，起初它还和神灵联系在一起，带有深厚的迷信色彩。传说三千二百多年前（公元前2200年），因治水出名的皇帝大禹就构造了三阶魔方（被人们称“洛书”），至今还有人把它当作符咒用于某些迷信活动，438951276（被人称为洛书的3阶魔方）大约在十五世纪时，魔方传到了西方，著名的科尼利厄斯·阿格里帕（1486-1535）先后构造出了3~9阶的魔方。如何构造出各种阶数的魔方呢？假如你知道方法，构造它其实并不困难。在构造n阶魔方时，首先要看清n是奇数还是偶数，在构造时要巧妙地利用某种形式的对称性。我们先来看n是奇数的情况，奇数阶魔方的构造方法如下：首先，在第一行中间写1；然后每次向右上方移一格，依次填由小到大排列的下一个数，（注：向上移出界时填下一列最后一行的小方格；向右移出界时填第一列上一行的小方格，就好像上下边是相连的、左右边也是相连的一样）。此外，当下面想填的格已填过数或已达到魔方的右上角时，改填刚才填的格子正下方的小方格，此后继续按原方法填，直至完全填完所有小方格。例如，按上述方法可构造出下面的5阶魔方：11104231718126524251913712212014893221615作为练习，请你给出一个7阶的魔方（见习题）。偶数阶的魔方可以利用奇数阶魔方拼接而成，拉尔夫·斯特雷奇给出了一种拼接的方法。限于篇幅的限止，我们不在此详细介绍了，作为一个例子，我们采用他的方法构造一个6阶的魔方。第一步利用1-9，10-18，19-27及28-36构造出4个3阶的魔方，它们分别是：638941275131217181410111615222126272319202524313035363228293433第二步利用图11-9中的A、B、C、D容易拼出一个6阶的魔方。为了保证性质的成立，还需要作一些调整，如果你有兴趣，不妨可以找一下调整的方法，（调整后得到的6阶魔方见图4-2所示）图4-2上述方法并非构造魔方的唯一方法，但不论采用什么方法来构造魔方，都应当尽可能利用某种形式的对称性。在魔方的构造中包含了许多有趣的数学问题，但由于很多人研究过这些问题，我们一般只能把它们当成一些练习题。互不相同的同阶魔方究竟有多少个？人们知道，三阶魔方只有一个，当然，通过镜面反射和绕中心旋转可以产生8种不同的表现形式。四阶魔方共有880个，而通过反射与旋转可有7040种不同的形式。没有人知道五阶或更高阶魔方的数量。例如，对五阶魔方，人们可用某种办法作出实质上不同的57600个（不含反射与旋转而得出的），如加上用其他方法构造的，已知的五阶魔方总数远远超过了一千三百万个，魔方数量随阶数n增长已达到了惊人的速度，令人目瞪口呆。2、松驰问题的讨论假如我们放松对构造魔方的数必须是1-n2的要求而允许它们取任意实数，（就像将整数规划或0-1规划松驰成相应的线性规划那样），问题也许会简单得多。我们仍要求它们具有某些特定的性质，并不妨仍把它们称为魔方，当然，此时问题已发生了实质性的变化，不再是原先讨论的问题了。为简单起见，我们用n阶方阵来记这样的魔方。易见，若A与B均为具有指定性质的魔方，则