1、 本科 毕业 论文 （ 20 届） 线性代数原理的几个应用 所在学院 专业班级 数学与应用数学 学生姓名 学号 指导教师 职称 完成日期 年 月 摘要 ： 线性代数作为一独立的数学分 支 有着自身独特 的 思想方法和处理问题的手法 。并且随现代科学技术的不断发展， 线性代数 理论及其方法 在科学研究 、经济 投入产出、 工程技术等领域的应用越来越广泛 、 深入 。 本课题 侧重于 线性代数的理论知识的实际运用，即 从问题实例出发，建立合适的数学模型，利用线性代数的知识解决问题。 从而提高在实际中运用线性代数原理以及其他所学知识的能力，提高分析问题，解决实际问题的能力。 关键词 ： 数学模型；指
2、派问题；马尔可夫链模；层次分析法Some Applications of Linear Algebra Theory Abstract： As an independent branch of mathematics, Linear Algebra has its own unique way of thinking and approach of problem solving. With the continuous development of modern science and technology, the theory of Linear Algebra and its meth
3、ods, which have more and more widely, in-depth applications in scientific research, economic input-output, engineering and other fields. This issue mainly focuses on linear algebra practical application of theoretical knowledge, that starting from the practical problems, then setting up appropriate
4、mathematical model with the theory of Linear Algebra to solve problems. To improve the capacity of using theories of Linear Algebra, analyzing and solving practical problems in practice. Key words： Mathematical model； Assignment problem; Markov chain model; Analytic Hierarchy Process 目 录 1. 引言 . 1 1
5、.1 研究背景 . 1 1.2 研究意义 . 1 1.3 研究方法 . 2 1.4 研究目标 . 2 2 指派问题模型 . 2 2.1 指派问题的定义 . 2 2.1.1 指派问题数学模型 . 2 2.1.2 指派问题最优解的性质 . 3 2.1.3 匈牙 利法的介绍 . 3 2.1.4 指派问题的极大化 . 4 2.2 指派问题实例 . 5 2.2.1 指派问题 LINGO程序 . 7 3 马尔可夫链模型 . 8 3.1 马尔可夫链 . 8 3.1.1 马尔可夫过程介绍 . 8 3.1.2 马尔可夫链的数学定义 . 8 3.1.3 转移概率矩阵 . 9 3.1.4 马尔可夫链的基本方程 .
6、9 3.1.5 相关定义及定理 . 10 3.2 马尔可夫链的应用实例 . 10 3.2.1 模型建立及求解 . 10 4 层次分析法 . 12 4.1 层次分析法的产生背景 . 12 4.1.1 层次分析法的广泛应用 . 12 4.1.2 层次分析法的基本步骤 . 13 4.2 层次分析法的预备知识 . 13 4.2.1 比较尺度的确定 . 13 4.2.2 构造成对比较矩阵及其权向量计算 . 14 4.2.3 一致阵的介绍 . 14 4.2.4 关于一致性检验 . 14 4.2.5 组合权向量的确定 . 15 4.3 层次分析法的实际应用 . 15 4.3.1 模型建立 . 16 4.3.
7、2 层次分析法的实际应用过程 . 16 4.3.3 层次分析法中和法的 Matlab程序 . 18 4.4 层次分析法的优缺点 . 19 4.4.1 层次分析法的优点 . 19 4.4.2 层次分析法的局限性 . 19 5 结束语 . 20 6 致谢 . 错误 !未定义书签。 7 参考文献 . 21 1 1. 引言 1.1 研究背景 历史上线性代数的第一个问题是关于解线性方程组的问题，最初的线性方程组问题大都是来源于生活实践 1，正是实际应用问题刺激了线性代数这一学科的诞生与发展。 线性代数的这种发展主要是由于人们所研究的问题的规模愈来愈大，愈来愈复杂，牵涉的变量成百上千，这样复杂的问题，目前
8、只能把变 量之间的关系简化为线性才好解。 线性代数作为一独立的数学分 支 有着自身独特的概念 、 思想方法和处理问题的手法 ,它更多的是从离散的角度研究客观世界 的空间形式和数量关系。而线性代数课程在大学数学中占有重要的地位，它是高等院校普遍开设的一门基础性数学课程 2。 线性代数主要是对理科、特别是数学系开设的。由于它广泛的应用价值，理、工、经、管 等 各个大学专业都把它列为必修课。但由 于 数学系开课，其内容和要求难免带有很深的数学专业的烙印，很难适应大量工科学生的要求。针对这种情况，美国的线性代数教育从 1990 年起开始了一次大的改革，一些有名望的数学家们组成了线性代数课程研究组 (L
9、inear Algebra Curriculum Study Group-LACSG) 探究线性代数教育如何满足数学和非数学专业的不同需求 , 以及如何使线性代数的教育得到更大的关注 3。同年 8月，美国国家科学基金会赞助了大学线性代数课程计划的一次会议，它把数学界和其他专业的许多代表聚集在一起。会产议生了 以下 重要的建议，简称为 LACSG Recommendation它们是： （ 1） 线性代数一定要满足非数学专业的需要； （ 2） 这一门课程应该是面向矩阵的 ； (3) 这一门课程应该是根据学生的需要来组织的； (4) 这一门课程应该利用新的计算技术 第 (1)条建议强调了非数学专业的
10、学生要更多注重于 应用 ，并且 教材中大量的应用篇幅可以提高学生的理解水平和学习动力；第 (2)条建议强调矩阵运算，即教材中要摆脱单个元素运算的中学方法；第 (3)条建议强调从学生需要而不是教师思路出发，这里有两个要点：一是阐述问题应该从具体到抽象 ； 二是要让学生主动学习，就是要 “ 带着问题学 ” ，而不是从定义出发。第 (4)条建议使用数学软件或图形计算器 . 大多数的教材今天都采用了 MATLAB4。因此对于普及线性代数原理的实践就十分的有必要和有实际运用价值，数学模型这个词汇也就应运而生了，并且越来越多的出现在现代生产、工作中。 1.2 研究意义 随着科学技术的迅速发展，线性代数的含
11、义也在不断扩大， 它 在科学研究 、 经济 投入产2 出、 工程技术等领域的应用越来越广泛 、 深入 。 而线性代数的原理都体现在基于在实际问题而建立的数学模型中，比如城市规划工作者需要建立一个包括人口、经济 5、交通、环境等大系统的数学模型，为领导层对城市发展规划的决策提供科学根据；电气工程师必须建立所要控制的生产过程的数学模型，用这个模型对控制装置做出相应的设计和计算；就是在日常活动如访友、采购当中，人们也会谈论找到一个数学模型 6，优化一下出行的路线。由此可见，线性代 数的原理已经融入生活的方方面面 , 本 课题 侧重对 线性代数的理论知识的实际运用就显得 很有理论意义和实际意义。 1.
12、3 研究方法 针对实际生活的例子，为了某个指定目的将其某一部分信息简缩、提炼而构成的数学模型。其中将会运用到线性代数的许多理论，并且还会借助计算机辅助模型求解，比如运用 Lingo、Matlab 等数学软件。 1.4 研究目标 通过本课题的研究， 希望能够用建模思想建设线性代数，引入线性代数的有关原理应用到实际中去。从问题实例出发，建立合适的数学模型利用线性代数的知识解决问题 7。 能够对数据进 行合理分析与预测，提高实际的建模能力。 2 指派问题模型 2.1 指派问题的定义 在生活中经常遇到这样的问题，某单位需完成 n 项任务，恰好有 n 个人可承担这些任务。由于每人的专长不同，各人完成任务
13、不同，效率也不同。于是产生应该指派哪个人去完成哪些任务，使完成 n 项任务的效率最高。这类问题称为指派问题 8。 2.1.1 指派问题数学模型 当问题要求极小化时数学 模型是： m in 11 , 1 , 2 , , 21 , 1 , 2 , , 31 0 4ij ijijijiijjijz c xx j nx i nx 或系数矩阵，其元素 0ijc , 1, 2, ,i j n 表示指派第 i 个人去完成第 j 项任务时的效率。3 解题时需引入变量 ijx ；其取值只能是 1或 0 。并令 10ijx 当 指 派 第 i 人 去 完 成 第 j 项 任 务当 不 指 派 第 i 人 去 完
14、成 第 j 项 任 务 约束条件 2 说明第 j 项任务只能由 1人去完成；约束条件 3 说明第 i 人只能完成 1项任务。满足约束条件 2 4 的可行解 ijx 也可写成表格或矩阵形式，称为解矩阵。 2.1.2 指派问题最优解的性质 指派问题的最优解有这样性质，若从系数矩阵 ijc一行（列）各元素中分别减去该行（列）的最小元素，得到新矩阵 ijb，那么以 ijb为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。利用这个性质，可使原系数矩阵变换为含有很多 0元素的新系数矩阵，而最优解保持不变，在系数矩阵 ijb中，我们关心位于不同行不同列的 0元素，以下简称为独立的 0元素。若能在系数矩阵
15、 ijb中找出 n 个独立的 0元素；则令解矩阵 ijx中对应这 n 个独立的 0元素的元素取值为 1，其他元素为 0。将其代入目标函数中得到 0bz ，它一定是最小。即就是原问题的最优解。 2.1.3 匈牙利法的介绍 库恩于 1955年提出了指派问题的解法，他引用了匈牙利数学家康尼格一个关于矩阵中 0元素中元素的定理：系数矩阵中独立 0元素的最多个数等于能覆盖所有 0元素的最少直线数。这解法称为匈牙利法 8。以后在方法上虽有不断改进，但仍沿用这个名称。 第一步： 使指派问题的系数矩阵经变换，在各行各列中都出现 0元素。 （ 1） 从系数矩阵的每行元素减去该行的最小元素； （ 2） 再从所得系
16、数矩阵的每列元素中减去该列的最小元素。 若某行（列）已有 0元素，那就不必再减了。 第二步： 进行试指派，以寻求最优解。按以下步骤进行。 经第一步变换后，系数矩阵中每行每列都已有了 0元素；但需要找出 n 个独立的 0元素。若能找出，就以这些独立 0元素对应解矩阵 ijx中的元素为 1，其余为 0，这就得到最优解。 （ 1）从只有一个 0 元素的行（列）开始，给这个 0元素加圈，记作。这元素对这行所代表的人，只有一种任务可指派。然后划去所在列（行）的其他 0 元素，记作 。这表示这列所代表的任务已指派完，不必再考虑别人 了。 4 （ 2）给只有一个 0 元素列（行）的 0 元素加圈，记作；然后
17、划去所在行的 0元素，记作 。 （ 3）反复进行（ 1），（ 2）两步，直到所有 0元素都被圈出或划掉为止。 （ 4）若仍有没有划圈的 0 元素，且同行（列）的 0元素至少有两个。从剩有 0 元素最少的行列开始，比较这行各 0元素所在列中 0元素的数目，选择 0元素少的那列的这个 0元素加圈，然后划掉同行同列的其他 0元素。可反复进行，直到所有 0元素都已圈出和划掉为止。 （ 5）若元素的数目 m 等于矩阵的阶数 n ，那么指派问题的最优解已得到。若 mn ，则转入下一步。 第三步： 作最少的直线覆盖所有 0元素，以确定该系数矩阵中能找到最多的独立元素数。为此按以下步骤进行： （ 1） 对没有
18、的行打号； （ 2） 对已有打号的列中含元素的行打号； （ 3） 再对打有号的列含有元素的行打号； （ 4） 重复（ 2），（ 3）直到得不出新的打号的行、列为止 （ 5） 对没有打号的行画一横线，有打号的列画一纵线，这就得到覆盖所有 0元素的最 少直线数。 令这直线数为 l ，若 ln ，说明必须再变换当前的系数矩阵，才能找到 n 个独立的 0元素，为此转第四步：若 ln ，而 mn ，应回到第二步（ 4），另行试探。 第四步 ： 对矩阵进行变换的目的是增加 0 元素。为此在没有被直线覆盖的部分中找出最小元素。然后在打行各元素中都减去这 最小元素，而在打列的各元素都加上这最小元素，以保证原来
19、 0元素不变，这样得到新系数矩阵，若得到 n 个独立的 0元素，则已得最优解，否则回到第三步重复进行。 当指派问题的系数矩阵，经过变换得到了同行和同列中都有两个或者两个以上 0元素时。这时可以任选一行（列）中某一个 0元素，再划去同行（列）的其他 0元素。 2.1.4 指派问题的极大化 对于极大化的问题，即求 m ax ij ijijz c x 可令 ij ijb M c 其中 M 是足够大的常数，这时系数矩阵可变换为 ijBb5 这时 0ijb ，符合匈牙利法的条件。目标函数经变换后，即解 m in ij ijijz b x 所得最小解就是原问题的最大解，因为 ij ij ij iji j
20、i jb x M c x ij ij iji j i jM x c x ij ijijnM c x因 nM 为常数，所以当ij ijijbx取最小时，ij ijijcx便为最大。 2.2 指派问题实例 实例： 9某校经过预赛选出 A ， B ， C ， D 四名学生，将派他们去参加该地区各学校之间的竞赛 。此次竞赛的四门功课考试在同一时间进行，因此每人只能参加一门，比赛结果将以总分计名次（不计个人名次）。下表是四名学生选拔时的成绩，应如何组队较好？ 科目 学生 数学 物理 化学 英语 A 90 95 78 83 B 85 89 73 80 C 93 91 88 79 D 79 85 84 87
21、 解：本题目是极大化的指派问题，即要求 4名学生每人各参加一门科目的总分之和最高，那么我们就可以根据极大化的问题来建立模型。 4名学生的各科失分表 科目 学生 数学 物理 化学 英语 A 10 5 22 17 B 15 11 27 20 C 7 9 12 21 D 21 15 16 13 那么只要 4名学生指派后的扣分之和最小，即他们的成绩之和最优。 6 失分矩阵 1 0 5 2 2 1 71 5 1 1 2 7 2 07 9 1 2 2 12 1 1 5 1 6 1 3ijBb目标函数： m inij ijijz b x 1, 1, 2 , , 41, 1, 2 , , 410ijiijji
22、jxjxix 或匈牙利法： 第一步：矩阵经变换，在各行各列中都出现 0元素。 10 5 22 1715 11 27 207 9 12 2121 15 16 13ijb min511713min 35 0 17 124 0 16 90 2 5 148 2 3 05 0 14 124 0 13 90 2 2 148 2 0 0第二步：进行试指派，以寻求最优解 5 0 14 124 0 13 90 2 2 148 2 0 05 14 124 13 92 2 14825 14 124 13 92 2 1482 减去最小元素 4得到1 0 10 80 0 9 50 6 2 148 6 0 01 10 8956 2 14861 10 8956 2 1486 减去最小元素 2得到1 0 8 60 0 7 30 6 0 1210 8 0 01 8 6736 1210 8因此它具有 4个独立的 0元素，这就得到了最优解，
