线性代数与运筹学-第一讲

1、线性代数与运筹学初步电子教案,运 筹 学（Operations Research）,上 海 海 事 大 学,任课教师：邓 伟,邮 箱：,课程安排,参考书目,运筹学张伯生 科学出版社 2007年,管理运筹学第三版 韩伯棠 高等教育出版社 2010年,工程数学线性代数同济大学数学系 高等教育 出版社,运筹学简介,运筹学（Operations Research）,系统工程的最重要的理论基础之一，在美国有学者把运筹学称之为管理科学（Management Science）。,运筹学所研究的问题，可简单地归结为一句话：,“依照给定条件和目标，从众多方案中选择最佳方案。”,故有人称之为最优化技术。,运筹学简

2、介,运筹学（Operations Research）,运筹学是一门应用科学，至今没有统一的定义。 据 大英百科全书释义： “运筹学是一门应用于管理有组织系统的科学”， “运筹学为掌管这类系统的人提供决策目标和数量分析的工具”。,运筹学简介,运筹学（Operations Research）,运筹学是一门应用科学，至今没有统一的定义。 据 大英百科全书释义： “运筹学是一门应用于管理有组织系统的科学”， “运筹学为掌管这类系统的人提供决策目标和数量分析的工具”。,运筹学简介,运筹学（Operations Research）,中国大百科全书的释义为： 运筹学 “用数学方法研究经济、民政和国防等部门在

3、内外环境的约束条件下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测发展趋势，制定行动规划或优选可行方案”。,运筹学简介,运筹学（Operations Research）,中国管理百科全书的释义为： “运筹学是应用分析、试验、量化的方法，对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。”,运筹学简介,运筹学（Operations Research）,运筹学是运用科学的方法(如分析、试验、量化等)来决定如何最佳地运营和设计各种系统的一门学科。 简而言之，运筹学就是一门研究系统优化的学科。 运筹学强调以量化为基础，

4、广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据，具有多学科交叉的特点。 通常以最优、最佳等作为决策目标，避开最劣的方案。,运筹学简介,运筹学的历史,在英国称为: Operational Research 在美国称为: “Operations Research” 可直译为“运用研究”“作业研究”“运作研究”。 1957 年，我国科技工作者从 “夫运筹帷幄之中，决胜千里之外”（史记 高祖本记）这句古语中摘取 “运筹” 二字，将 O.R. 正式译作运筹学。,运筹学简介,运筹学的历史,中国古代：朴素的运筹学思想(田忌赛马（对策论）、孙子兵法),战国时期

5、，齐王与大臣赛马：,齐 王: 上 中 下 田 忌: 下 上 中 田忌两胜一负，以劣势净得千金。,故有人称之为最优化技术。,“运筹帷幄之中，决胜千里之外”,运筹学简介,运筹学的历史,北宋真宗年间，皇城失火，皇宫被毁，朝廷决定 重建皇宫，时间非常紧迫。宋真宗：“没有皇宫,如何上朝,如何议政,如何安居呢?” 宰相丁谓(9621033)负责修缮宫殿。,瓦砾：失火中毁坏和修路中废弃的瓦砾填沟筑 路。,解决三项任务：取土、外地材料运输、处理瓦砾,取土：皇宫外的大街上挖沟取土；,运输：引开封附近汴水入沟，使载运外地材料的船 只直接抵达宫前；,运筹学简介,运筹学的历史,“Operational Researc

6、h”这一名词最早出现在第二次世界大战期间 美、英等国家的作战研究小组为了解决作战中所遇到的许多错综复杂的战略、战术问题而提出的。,运筹学简介,运筹学的历史,1946年,二次世界大战期间，英美国家都发明制造了一些新式武器，如雷达，单武器的有效使用却落后于武器的制造，难以正确评估和迅速提高这些武器的使用效率。 1935年，英国军方成立了科学小组，研究如何有效地运用英国的一支力量有限的空军，来抵抗敌人的空袭和对付敌人的潜艇。 反潜战争、运输问题、商船编队和舰队护航、武器质量控制和检测,运筹学简介,运筹学的历史,1946年,“运作研究(Operational Research)小组”:解决复杂的战略和

7、战术问题。例如： 如何合理运用雷达有效地对付德军德空袭 对商船如何进行编队护航，使船队遭受德国潜艇攻击时损失最少； 在各种情况下如何调整反潜深水炸弹的爆炸深度，才能增加对德国潜艇的杀伤力等。,运筹学简介,运筹学的历史,1947年-1960年代上半期,主要用于企业管理，理论上趋于成熟 。从军事运筹研究转向国民经济各个部门，取得了良好的效果。,基础理论的研究，使之科学化、条理化,研究运筹学的新方法,企业管理,运筹学简介,运筹学的历史,1960年代下半期,运筹学的内容越来越丰富，分工越来越细，产生了许多新的分支。,研究的系统由小而大，逐渐和系统分析相结合。,在时间上由短到长，逐渐和未来学结合。,研究

8、的因素由技术性转向非技术性，和社会科学结合。,运筹学简介,运筹学的历史,战后这些研究成果被应用到生产、经济领域，并得到迅速发展有关理论和方法的研究、实践不断深入。 1947年美国数学家丹捷格(G.B.Dantzig）提出了求解线性规划的有效方法单纯形法。 数学对运筹学的作用是有关理论和方法的研究基础，是建立运筹学模型的工具。 计算机的发展，促进运筹学的进一步发展高速、可靠的计算是运筹学解决问题的基本保障。,运筹学简介,1.选址问题,3.切割问题,4.路线选择问题,5.NEWSBOY问题,6.飞行员排班问题,2.装箱问题,典型运筹学问题,7.排队服务问题,8.人员招聘问题,运筹学简介,运筹学学科

9、体系：,规划理论（线性规划、运输问题、整数规划、目标规划、非线性规划、动态规划、多目标规划）,网络流分析、图与网络计划,库存分析,决策分析,对策分析,排队分析,运筹学简介,运筹学研究问题的主要步骤：,运筹学简介,目前国际、国内著名的运筹学刊物有：,Management Science Operations Research Journal of Operational Research Society European Journal of Operations Research 运筹学学报 运筹与管理,运筹学简介,运筹学方法在中国使用情况(随机抽样) ：,运筹学简介,运筹学界对于运筹学的发展

10、方向的观点：,从强调数学模型到强调应用、建模协调发展，重视多学科的横向交叉联系和解决实际问题的研究； 引入非数学方法(AHP方法，Pareto解)； 人机对话和现代优化算法(决策支持系统、专家系统；遗传算法、神经网络、模拟退火、进化算法、禁忌搜索等)。,第一讲 行列式的概念,用消元法解二元线性方程组,一、二阶行列式的引入,方程组的解为,由方程组的四个系数确定.,由四个数排成二行二列（横排称行、竖排 称列）的数表,定义,即,主对角线,副对角线,对角线法则,二阶行列式的计算,若记,对于二元线性方程组,系数行列式,则二元线性方程组的解为,注意 分母都为原方程组的系数行列式.,例1,解,二、三阶行列式

11、,定义,记,（6）式称为数表（5）所确定的三阶行列式.,(1)沙路法,三阶行列式的计算,(2)对角线法则,注意 红线上三元素的乘积冠以正号，蓝线上三 元素的乘积冠以负号,说明1 对角线法则只适用于二阶与三阶行列式,如果三元线性方程组,的系数行列式,利用三阶行列式求解三元线性方程组,若记,或,记,即,得,得,则三元线性方程组的解为:,例,解,按对角线法则，有,例3,解,方程左端,例4 解线性方程组,解,由于方程组的系数行列式,同理可得,故方程组的解为:,二阶和三阶行列式是由解二元和三元线性方 程组引入的.,三、小结,一、概念的引入,引例,用1、2、3三个数字，可以组成多少个没有重复数字的三位数？

12、,解,1 2 3,1,2,3,百位,3种放法,十位,1,2,3,1,个位,1,2,3,2种放法,1种放法,种放法.,共有,二、全排列及其逆序数,问题,定义,把 个不同的元素排成一列，叫做这 个元素的全排列（或排列）.,个不同的元素的所有排列的种数，通常用 表示.,由引例,同理,在一个排列 中，若数 则称这两个数组成一个逆序.,例如 排列32514 中，,定义,我们规定各元素之间有一个标准次序, n 个不同的自然数，规定由小到大为标准次序.,排列的逆序数,3 2 5 1 4,定义 一个排列中所有逆序的总数称为此排列的逆序数.,例如 排列32514 中，,3 2 5 1 4,逆序数为3,1,故此排

13、列的逆序数为3+1+0+1+0=5.,计算排列逆序数的方法,方法1,分别计算出排在 前面比它大的数 码之和即分别算出 这 个元素 的逆序数，这个元素的逆序数的总和即为所求 排列的逆序数.,逆序数为奇数的排列称为奇排列;,逆序数为偶数的排列称为偶排列.,排列的奇偶性,分别计算出排列中每个元素前面比它大的数码 个数之和，即算出排列中每个元素的逆序数， 这每个元素的逆序数之总和即为所求排列的逆 序数.,方法2,例1 求排列32514的逆序数.,解,在排列32514中,3排在首位,逆序数为0;,2的前面比2大的数只有一个3,故逆序数为1;,3 2 5 1 4,于是排列32514的逆序数为,5的前面没有

14、比5大的数,其逆序数为0;,1的前面比1大的数有3个,故逆序数为3;,4的前面比4大的数有1个,故逆序数为1;,例2 计算下列排列的逆序数，并讨论它们的奇偶性.,解,此排列为偶排列.,解,当 时为偶排列；,当 时为奇排列.,2 排列具有奇偶性.,3 计算排列逆序数常用的方法有2 种.,1 个不同的元素的所有排列种数为,三、小结,一、概念的引入,三阶行列式,说明,（1）三阶行列式共有 项，即 项,（2）每项都是位于不同行不同列的三个元素的 乘积,（3）每项的正负号都取决于位于不同行不同列 的三个元素的下标排列,例如,列标排列的逆序数为,列标排列的逆序数为,偶排列,奇排列,二、n阶行列式的定义,定

15、义,说明,1、行列式是一种特定的算式，它是根据求解方程个数和未知量个数相同的一次方程组的需要而定义的;,2、 阶行列式是 项的代数和;,3、 阶行列式的每项都是位于不同行、不同列 个元素的乘积;,4、 一阶行列式 不要与绝对值记号相混淆;,5、 的符号为,例1计算行列式,分析,展开式中项的一般形式是,否则这个项为零。,所以 只能等于 ,同理可得,解,即行列式中不为零的项为,例2 计算上三角行列式,分析,展开式中项的一般形式是,所以不为零的项只有,解,例3,同理可得下三角行列式,例4 证明对角行列式,证明,第一式是显然的,下面证第二式.,若记,则依行列式定义,证毕,一、行列式的性质,性质1 行列

16、式与它的转置行列式相等.,行列式 称为行列式 的转置行列式.,记,例如,推论 如果行列式有两行（列）完全相同，则此行列式为零.,说明 行列式中行与列具有同等的地位, 因此行列 式的性质凡是对行成立的对列也同样成立.,性质2 互换行列式的两行（列）,行列式变号.,性质3 行列式的某一行（列）中所有的元素都乘以同一数 ，等于用数 乘此行列式.,推论行列式的某一行（列）中所有元素的公因子可以提到行列式符号的外面,性质行列式中如果有两行（列）元素成比例，则此行列式为零,证明,性质5若行列式的某一列（行）的元素都是两数之和.,则D等于下列两个行列式之和：,例如,性质把行列式的某一列（行）的各元素乘以同一

17、数然后加到另一列(行)对应的元素上去，行列式不变,例如,例,二、应用举例,计算行列式常用方法：利用运算把行列式化为上三角形行列式，从而算得行列式的值,解,习题8(2):计算n阶行列式,解,将第 都加到第一列得,例10,证明,证明,对D1进行行变换,对D前k行进行行变换,对D前k行进行行变换,对D2进行列变换,对D后n列进行列变换,例11 计算2n阶行列式,解 第2n行依次与第2n1、第2行对换(2n2次),再把第2n列依次与第2n1、第2列对换(2n2次)得,还有别的方法吗？,例如,一、余子式与代数余子式,叫做元素 的代数余子式,例如,引理 一个 阶行列式，如果其中第 行所有元素除 外都为零，

18、那末这行列式等于 与它的代数余子式的乘积，即 ,例如,定理 行列式等于它的任一行（列）的各元素与其对应的代数余子式乘积之和，即,证,二、行列式按行（列）展开法则,例1,证,用数学归纳法,n-1阶范德蒙德行列式,推论 行列式任一行（列）的元素与另一行（列）的对应元素的代数余子式乘积之和等于零，即,证,同理,关于代数余子式的重要性质,例 计算行列式,解,计算2n阶行列式,将D2n先按第1列展开, 再分别按第2n -1列展开, 得,克莱姆(Gabriel Cramer, 公元1704年7月31日公元1752年1月4日)瑞士数学家。他一生未婚，专心治学，平易近人且德高望重，先後当选为伦敦皇家学会、柏林

19、研究院和法国、意大利等学会的成员。,1.7 Cramer法则,1.7 Cramer法则,他的主要著作是在1750年出版的代数曲缐的分析引论, 首先定义了正则、非正则、超越曲缐和无理曲缐等概念, 第一次正式引入坐标系的纵轴(y轴), 然後讨论曲缐变换，并依据曲缐方程的阶数将曲缐进行分类。为了确定经过5个点的一般二次曲缐的系数,应用了著名的Cramers Rule, 即由缐性方程组的系数确定方程组解的表达式。该法则於1729年由英国数学家马克劳林(Maclaurin)得到, 1748年发表, 但克莱姆的优越符号使之流传。此外，他还留下若干数学史笔记，提出应用於数理经济和概率论的“数学效益”概念。,

20、一、克拉默法则,如果线性方程组,的系数行列式不等于零，即,其中 是把系数行列式 中第 列的元素用方程 组右端的常数项代替后所得到的 阶行列式，即,那么线性方程组 有解，并且解是唯一的，解 可以表为,教材例14 用克拉默则解方程组,解,二、重要定理,定理1 如果线性方程组 的系数行列式 则 一定有解,且解是唯一的 .,定理2 如果线性方程组 无解或有两个不同的 解，则它的系数行列式必为零.,设线性方程组,则称此方程组为非,非齐次线性方程组;,此时称方程组为齐次线性方程组.,非齐次与齐次线性方程组的概念,齐次线性方程组的相关定理,定理 如果齐次线性方程组 的系数行列式 则齐次线性方程组 没有非零解

21、.,有非零解.,系数行列式,习题12 问 取何值时，齐次方程组,有非零解？,注意: (1)与教材上的例16类似，自学例16. (2)讲过的习题都是作业题.,解,齐次方程组有非零解，则,所以 或 时齐次方程组有非零解.,1. 用克拉默法则解方程组的两个条件,(1)方程个数等于未知量个数;,(2)系数行列式不等于零.,2. 克拉默法则建立了线性方程组的解和已知的系 数与常数项之间的关系.它主要适用于理论推导.,三、小结,思考题,当线性方程组的系数行列式为零时, 能否用克拉默 法则解方程组? 为什么? 此时方程组的解为何?,思考题解答,不能, 此时方程组的解为无解或有无穷多解.,把 个不同的元素排成一列，叫做这 个元 素的全排列（或排列）,个不同的元素的所有排列的种数用 表示， 且,第一章内容概要,全排列,逆序数为奇数的排列称为奇排列，逆序数为 偶数的排列称为偶排列,在一个排列 中，若数 ， 则称这两个数组成一个逆序,一个排列中所有逆序的总数称为此排列的逆 序数,逆序数,分别