浙大城院数学建模4分析.ppt

第四章、线性代数模型 ;§ 4.1 几个数学游戏; 接下来，人可以带狗过河，也可以带米过河，但回来时有一定要将鸡带回，……，按此推导下去，读者不难找到过河方法。我们研究本例的目的不在于找出答案，而是想设计出一种让计算机自行有哪些信誉好的足球投注网站寻找答案的方法。为此目的，我们先把例1转化为状态转移问题。首先，应当如何表达状态呢？不同的情况应采取不同的方法，在本例中，人鸡狗米都只有两种可能状态，即在此岸或在彼岸（不在此岸）。我们将用向量来表示状态，可采取如下方法：一物在此岸时相应分量取1，而在彼岸时则相应分量取为0，例如（1,0,1,0）表示人和鸡在此岸，而狗和米则在彼岸。;(i) 可取状态：根据题意，并非所有状态都是允许的，例如（0,1,1,0）就是一个不可取的状态，因为狗会咬鸡。本题中可取状态（即系统允许的状态）可以用穷举法列出来，它们是：;(ii) 可取运算：状态转移需要经过状态运算来实现。在实际问题中，摆一次渡即可改变现有状态。为此再引入一个四维向量(转移向量)，用它来反映摆渡情况。例如(1，1，0，0)表示人带狗摆渡过河。根据题意，允许使用的转移向量只能有(1，0，0，0)、(1，1，0，0)、(1，0，1，0)、（1，0，0，1)四个。; 在具体转移时，只考虑由可取状态到可取状态的转移。问题化为：由初始状态(1，1，1，1)出发，经过奇数次的上述运算能否转化为(0，0，0，0)的转化问题，进而，如果能，我们还想知道具体应当如何转化 。;(第二次渡河);例4.2 夫妻过河问题;(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）; 关于夫妻过河还可以编出许多其他形式的问题，下面我们来讨论一些同样有趣的问题。为了叙述简便，先约定一些符号，这些符号将被应用于以下的各个问题之中。记想过河的夫妻对数为n，船可载的人数为m，n对夫妻过河所需的最少摆渡次数为k。;(问题1) 2对夫妻要过河，船每次只能渡2人，应如何过河，最少摆渡几次？(即n=2，m=2，求k=?);德兰努瓦(M. Delannoy)证明：; 有些较为复杂的问题，开始时常常给人以一种变幻莫测的感觉。但经过细微的分析研究，可以发现其中存在着某些内在的关系。在使用适当的数学工具后，这些内在关系就被一一揭露出来了。;1、Dürer魔方; 按不同的要求，它可以具有某些特定的性质，n称为此魔方的阶。例如，上面给出的Dürer魔方是4阶的，它的每一行数字之和为34，每一列数字之和为34，把对角线(或反对角线)上的数字加起来是34，每个小方块中的数字之和也是34，若把四个角上的数字加起来还是34，多么奇妙！最后一行中间两个数字恰好是铜币的铸造时间——1514年。;(被人称为洛书的3阶魔方); 我们先来看n是奇数的情况，奇数阶魔方的构造方法如下： ;作为练习，请你给出一个7阶的魔方(见习题)。;第二步 利用图11-9中的A、B、C、D容易拼出一个6阶的魔方。为了保证性质的成立，还需要作一些调整，如果你有兴趣，不妨可以找一下调整的方法，(调整后得到的6阶魔方见图4-2所示);(图4-2 ); 上述方法并非构造魔方的唯一方法，但不论采用什么方法来构造魔方，都应当尽可能利用某种形式的对称性。在魔方的构造中包含了许多有趣的数学问题，但由于很多人研究过这些问题，我们一般只能把它们当成一些练习题。;2、松驰问题的讨论;不妨仍以4阶方阵为例。首先，定义0-方与1-方如下：;Date; 显然，D中任何一个元素都可以用Q1，Q2，…，Q8来线性表示，它们能否构成D的一组基，关键在于它们是否线性无关。; 等号两边对应元素相比较，得r1=r2=…=r7=0，所以Q1，Q2，…，Q7是线性无关的。Q1，Q2，…，Q7是D空间的一组基，D中任何元素都可以由Q1，Q2，…，Q7的线性组合生成。可以这样认为：{ Q