离散优化数学建模

1、离散优化数学建模第1页，共102页，2022年，5月20日，11点4分，星期五2008年B题 高等教育学费标准探讨请你们根据中国国情，收集诸如国家生均拨款、培养费用、家庭收入等相关数据，并据此通过数学建模的方法，就几类学校或专业的学费标准进行定量分析，得出明确、有说服力的结论。数据的收集和分析是你们建模分析的基础和重要组成部分。你们的论文必须观点鲜明、分析有据、结论明确。最后，根据你们建模分析的结果，给有关部门写一份报告，提出具体建议。第2页，共102页，2022年，5月20日，11点4分，星期五 3. 试题向大规模数据处理方向发展:从05年开始，基本上每年都有一大数据量的赛题；数据结构的复杂

2、性：数据的真实性，数据的海量性，数据的不完备性，数据的冗余性 4. 求解算法和各类现代算法的融合；如：11B 5.实用性：问题和数据来自于实际，解决方法切合于实际，模型和结果可以应用于实际。6.即时性：国内外的大事，社会的热点，生活的焦点，近期发生和即将发生被关注的问题。第3页，共102页，2022年，5月20日，11点4分，星期五拿到赛题后大家需要思考的问题 题目属于哪种类型：连续的、离散的需要解决什么问题:最优化方案、预测模型、最短路径等等；将问题分解。可以用哪些相关模型、算法求解、需 要什么数学工具。 第4页，共102页，2022年，5月20日，11点4分，星期五1、数学建模的过程(2)

3、整个数学建模过程应当由三个阶段： 1.建立模型：实际问题数学问题； 2.数学解答：数学问题数学解； 3.模型检验：数学解实际问题的解决。(1)流程图模型应用问题分析模型假设建立模型模型求解模型分析模型检验第5页，共102页，2022年，5月20日，11点4分，星期五 解决问题涉及到的计算软件分析 重要的是参赛选手具备编程计算、计算机仿真、模拟能力。赛题常用的计算软件：Matlab, SPSS， EXCEL等第6页，共102页，2022年，5月20日，11点4分，星期五参考网站1 全国大学生数学建模竞赛网： 2 数学中国网站 3 中国数学建模网站： 第7页，共102页，2022年，5月20日，1

4、1点4分，星期五 从问题的解决方法上分析 涉及到的数学建模方法： 几何理论、组合概率、统计(回归)分析; 优化方法（规划）、图论与网络优化、层次分析; 差分方法、微分方程、模糊数学、随机决策、多目标决策; 插值与拟合、灰色系统理论、神经网络、时间序列; 综合评价、机理分析等方法;第8页，共102页，2022年，5月20日，11点4分，星期五 用的最多的方法是优化方法和概率统计用到优化方法的共有26个题，其中整数规划4个，线性规划7个，非线性规划14个,多目标规划6个。用到概率统计方法的有21个题，平均每年至少有一个题目用到概率统计的方法。用到图论与网络优化方法的问题有6个；用到层次分析方法的问

5、题有个；第9页，共102页，2022年，5月20日，11点4分，星期五 用到插值拟合的问题有6个；用灰色系统理论的4个;用到时间序列分析的至少2个;用到综合评价方法的至少3个；大部分题目都可以用两种以上的方法来解决,即综合性较强的题目有26个第10页，共102页，2022年，5月20日，11点4分，星期五最优化概论从数学意义上说，最优化方法是一种求极值的方法，即在一组约束为等式或不等式的条件下，使系统的目标函数达到极值，即最大值或最小值。从经济意义上说，是在一定的人力、物力和财力资源条件下，使经济效果达到最大（如产值、利润），或者在完成规定的生产或经济任务下，使投入的人力、物力和财力等资源为最

6、少。第11页，共102页，2022年，5月20日，11点4分，星期五一、最优化概念所有类似的这种课题统称为最优化问题，研究解决这些问题的科学一般就总称之为最优化理论和方法另外也可用学术味更浓的名称：“运筹学”。由于最优化问题背景十分广泛，涉及的知识不尽相同，学科分枝很多，因此这个学科名下到底包含哪些分枝，其说法也不一致。比较公认的是：“规划论”（包括线性和非线性规划、整数规划、动态规划、多目标规划和随机规划等），“组合最优化”，“对策论”及“最优控制”等等。 第12页，共102页，2022年，5月20日，11点4分，星期五数学建模竞赛中的优化问题2000B 钢管订购和运输问题 组合优化2001

7、B 公交车优化调度图论2002B 彩票中的数学 决策分析2003B 露天矿生产的车辆安排问题 离散优化2004A 奥运会临时超市网点设计问题 图论2005B DVD在线租赁 离散优化2006A 出版社的资源配置问题 决策分析第13页，共102页，2022年，5月20日，11点4分，星期五07B 乘公交，看奥运 图论 整数规划08B 高等教育学费探讨 层次分析法 多目标优化09B 眼科病床的合理安排动态规划10B 上海世博会经济影响力定量评估 决策分析11B 交巡警服务平台的设置与调度图论 多目标规划12B 太阳能小屋的设计 离散优化13A 车道被占用对城市道路通行能力的影响 离散优化第14页，

8、共102页，2022年，5月20日，11点4分，星期五从数学上来看，所谓最优化问题可以概括为这样一种数学模型：给定一个“函数”，F(X)，以及“自变量”X应满足的一定条件，求X为怎样的值时，F(X)取得其最大值或最小值。通常，称F(X)为“目标函数”，X应满足的条件为“约束条件”。约束条件一般用一个集合D表示为：XD。求目标函数F(X)在约束条件XD下的最小值或最大值问题，就是一般最优问题的数学模型第15页，共102页，2022年，5月20日，11点4分，星期五无约束最优化问题目标函数 二、最优化问题的一般形式约束最优化问题约束函数 最优解；最优值第16页，共102页，2022年，5月20日，

9、11点4分，星期五三、最优化问题分类分类1：无约束最优化 约束最优化 非线性规划：目标函数与约束函数中至少有一个是变量x的非线性函数； 线性规划：目标函数与约束函数均为线性函数；分类2：线性规划 非线性规划第17页，共102页，2022年，5月20日，11点4分，星期五三、最优化问题分类 分类3（根据决策变量、目标函数和要求不同）整数规划动态规划网络规划随机规划多目标规划第18页，共102页，2022年，5月20日，11点4分，星期五三、最优化问题分类函数最优化组合最优化分类函数最优化：决策变量是一定区间内的连续变量 组合最优化：决策变量是离散状态，同时可行域是由有限个点组成的集合 第19页，

10、共102页，2022年，5月20日，11点4分，星期五最优化方法解决问题的步骤（1）确定变量，写出目标函数和有关约束条件，建立数学模型。（2）分析模型，搞清它属于运筹学哪一分枝，选择合适的最优化方法；（3）编程求解；尽量利用现有的数学软件或最优化软件，比如 Matlab，Mathematica， Lindo， Lingo等，来计算。（4）最优解的验证和实施。第20页，共102页，2022年，5月20日，11点4分，星期五Chapter1 线性规划 (Linear Programming) LP的数学模型 LP模型的应用本章主要内容：第21页，共102页，2022年，5月20日，11点4分，星期

11、五线性规划问题的数学模型1. 规划问题生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。线性规划通常解决下列两类问题：（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源 （如资金、设备、原材料、人工、时间等）去完成确定的任务或目标（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多 、利润最大.）第22页，共102页，2022年，5月20日，11点4分，星期五线性规划问题的数学模型例1 某企业计划生产甲、乙两种产品。这些产品分别要在A、B、C、D、四种不同的设备上加工。按工艺资料规定，单件产品在不同设

12、备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？ 设 备产 品 A B C D利润（元） 甲 2 1 4 0 2 乙 2 2 0 4 3 有 效 台 时 12 8 16 12第23页，共102页，2022年，5月20日，11点4分，星期五线性规划问题的数学模型解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：max Z = 2x1 + 3x2 x1 0 , x2 0s.t. 2x1 + 2x2 12 x1 + 2x2 8 4x1 16 4x2 12第24页，共102页，2022年，5月20日，11点4分，星期五 这是一个典型的利润最大化的生产计划问题。

13、其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subject to”的缩写，表示“满足于”。因此，上述模型的含义是：在给定条件限制下，求使目标函数 z 达到最大的x1 ,x2 的取值。第25页，共102页，2022年，5月20日，11点4分，星期五线性规划问题的数学模型2. 线性规划的数学模型由三个要素构成决策变量 Decision variables 目标函数 Objective function约束条件 Constraints其特征是：（1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；（2）问题的约束条件是一组多个决策变量的线性

14、不等式或等式。 怎样辨别一个模型是线性规划模型？ 第26页，共102页，2022年，5月20日，11点4分，星期五线性规划问题的数学模型目标函数：约束条件：3. 线性规划数学模型的一般形式简写为：第27页，共102页，2022年，5月20日，11点4分，星期五线性规划问题的数学模型矩阵形式：其中：第28页，共102页，2022年，5月20日，11点4分，星期五线性规划问题的数学模型3. 线性规划问题的标准形式特点：(1) 目标函数求最大值。(2) 约束条件都为等式方程，且右端常数项bi都大于或等于零(3) 决策变量xj为非负。第29页，共102页，2022年，5月20日，11点4分，星期五线性

15、规划问题的数学模型（2）如何化标准形式 目标函数的转换 如果是求极小值即 ，则可将目标函数乘以(-1)，可化为求极大值问题。也就是：令 ，可得到上式。即 若存在取值无约束的变量 ,可令 其中： 变量的变换第30页，共102页，2022年，5月20日，11点4分，星期五线性规划问题的数学模型 约束方程的转换：由不等式转换为等式。称为松弛变量称为剩余变量 变量 的变换 可令第31页，共102页，2022年，5月20日，11点4分，星期五线性规划问题的数学模型4. 线性规划问题的解线性规划问题求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数(1)达到最大值。第32页

16、，共102页，2022年，5月20日，11点4分，星期五线性规划问题的数学模型 可行解：满足约束条件、的解为可行解。所有可行解的集合为可行域。 最优解：使目标函数达到最大值的可行解。 线性规划解的情况：有唯一最优解；有无穷多最优解；无界解；无可行解 第33页，共102页，2022年，5月20日，11点4分，星期五 建立线性规划模型的过程可以分为四个步骤：(1)设立决策变量；(2)明确所有的约束条件并用决策变量的线性等式或不等式表示出来；(3)用决策变量的线性函数表示目标，并确定是求极大（Max）还是极小（Min）；(4)根据决策变量的物理性质研究变量是否有非负性。求解方法：用MATLAB软件直

17、接求解。第34页，共102页，2022年，5月20日，11点4分，星期五Chapter2 运输问题( Transportation Problem )运输问题的数学模型运输问题的应用 本章主要内容：第35页，共102页，2022年，5月20日，11点4分，星期五1.运输问题模型及有关概念问题的提出 一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。第36页，共102页，2022年，5月20日，11点4分，星期五运输问题的数学模型例2.1 某公司从两个产地A1、A2将

18、物品运往三个销地B1, B2, B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？B1B2B3产量A1646200A2655300销量150150200第37页，共102页，2022年，5月20日，11点4分，星期五运输问题的数学模型解：产销平衡问题：总产量 = 总销量500 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表：B1B2B3产量A1x11x12x13200A2x21x22x23300销量150150200Min C = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+

19、 x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij 0 ( i = 1、2；j = 1、2、3）第38页，共102页，2022年，5月20日，11点4分，星期五运输问题的数学模型运输问题的一般形式：产销平衡A1、 A2、 Am 表示某物资的m个产地； B1、B2、Bn 表示某物质的n个销地；ai 表示产地Ai的产量； bj 表示销地Bj 的销量； cij 表示把物资从产地Ai运往销地Bj的单位运价。设 xij 为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的

20、模型：第39页，共102页，2022年，5月20日，11点4分，星期五运输问题的数学模型变化： 1）有时目标函数为求最大值。如求利润最大或营业额最大； 2）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束)； 3）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。第40页，共102页，2022年，5月20日，11点4分，星期五运输问题的应用 产销不平衡的运输问题当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。 当产大于销时，即：数学模型为：第41页，共102页，2022

21、年，5月20日，11点4分，星期五运输问题的应用由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，假设该仓库为一个虚拟销地Bn+1， bn+1作为一个虚设销地Bn+1的销量(即库存量)。各产地Ai到Bn+1的运价为零，即Ci,n+1=0,（i=1，m）。则平衡问题的数学模型为：第42页，共102页，2022年，5月20日，11点4分，星期五运输问题的应用 当销大于产时，即：数学模型为：由于总销量大于总产量,故一定有些需求地不完全满足,这时虚设一个产地Am+1，产量为：第43页，共102页，2022年，5月20日，11点4分，星期五运输问题的应用销大于产

22、化为平衡问题的数学模型为 ：具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为am+1即可。 第44页，共102页，2022年，5月20日，11点4分，星期五Chapter3 整数规划( Integer Programming )整数规划的特点及应用指配问题与匈牙利法本章主要内容：第45页，共102页，2022年，5月20日，11点4分，星期五引言 整数规划是规划论中近几十年才发展起来的一个重要分支，主要是由于经济管理中的大量问题在抽象成模型时，人们发现许多量具有不可分割性，因此当它们被作为变量引入到规划中时，常要求满足取整条件. 如生产计划中，生产机器多少台(整数)；人力资源管理中

23、，招聘员工多少人(整数)；运输问题中，从一个港口到另一个港口的集装箱调运数量(整数)；另外，运作管理中的决策问题：如工厂选址、人员的工作指派、设备购置和配置等. 第46页，共102页，2022年，5月20日，11点4分，星期五一辆车最大装载重量为7吨，容量为12立方米。现有两种物品，每种物品数量无限。各种物品每件的体积、重量、价格如下表：物品1物品2体积（立方米/件）34重量（吨/件）42价值（万元/件）43求这辆车中装入每种物品各多少件，使物品总价值最高。背包问题第47页，共102页，2022年，5月20日，11点4分，星期五设三种物品的件数各为x1，x2件，总价值为z max z=4x1+

24、3x2 s.t. 3x1+4x212 4x1+2x2 7 x1，x20 ，x1，x2为整数第48页，共102页，2022年，5月20日，11点4分，星期五整数规划的特点及应用整数规划（简称：IP）要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若该松弛问题是一个线性规划，则称该整数规划为整数线性规划。整数线性规划数学模型的一般形式：第49页，共102页，2022年，5月20日，11点4分，星期五整数规划的特点及应用整数规划问题的种类： 纯整数规划：指全部决策变量都必须取整数值的整数规划。 混合整数规划

25、：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数规划。 0-1型整数规划：决策变量只能取值0或1的整数规划。第50页，共102页，2022年，5月20日，11点4分，星期五整数规划的特点及应用整数规划问题解的特征： 整数规划问题的可行解集合是它松弛问题可行解集合的一个子集，任意两个可行解的凸组合不一定满足整数约束条件，因而不一定仍为可行解。 整数规划问题的可行解一定是它的松弛问题的可行解（反之不一定），但其最优解的目标函数值不会优于后者最优解的目标函数值。第51页，共102页，2022年，5月20日，11点4分，星期五0-1整数规划 0-1整数规划是整数规划中的特殊情形，它的变量

26、仅取值0或者1，我们通常称为0-1变量或逻辑变量. 在实践中，许多问题只回答是或否. 例如，对某个项目是否投资，对某个应聘者是否聘用，对某种新产品是否研发等，这类问题都可以用0-1变量来描绘.第52页，共102页，2022年，5月20日，11点4分，星期五整数规划的特点及应用整数规划问题的求解方法： 分支定界法和割平面法 匈牙利法（指派问题）求解整数规划模型的数学软件有：Lindo, Lingo和Matlab,其中Lindo和Lingo是专业的优化软件.第53页，共102页，2022年，5月20日，11点4分，星期五指派问题 Assignment Problem 在生活中经常遇到这样的问题，某

27、单位需完成n项任务，恰好有n个人可以承担这些任务.一项任务只能由一个人完成，一个人只能完成一项任务。 由于每人的专长不同，每个人完成各项任务的效率不同. 于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高(或所需总时间最小，费用最低）。第54页，共102页，2022年，5月20日，11点4分，星期五指派问题指派问题的数学模型的标准形式：设n 个人被分配去做n 件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第i个人去做第j 件工作的 时间或费用为Cij(i=1.2n;j=1.2n)并假设Cij 0。问应如何分配才能使总效率最高？设决策变量 第55页，共102页，2022

28、年，5月20日，11点4分，星期五指派问题的数学模型为：第56页，共102页，2022年，5月20日，11点4分，星期五整数规划的特点及应用例2 指派问题：人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表所示，如何安排他们的工作使总成绩最好。 工作人员ABCD甲85927390乙95877895丙82837990丁86908088第57页，共102页，2022年，5月20日，11点4分，星期五整数规划的特点及应用设 数学模型如下：要求每人做一项工作，约束条件为：第58页，共102页，2022年，5月20日，11点4分，星期五整数规划的特点及应用每项

29、工作只能安排一人，约束条件为：变量约束：对于指派问题等 0-1 整数规划问题，可以直接利用Matlab 的函数bintprog 进行求解。 第59页，共102页，2022年，5月20日，11点4分，星期五多目标规划模型 在许多实际问题中，衡量一个方案的好坏标准往往不止一个，例如设计一个导弹，既要射程最远，又要燃料最省，还要精度最高. 这一类问题统称为多目标最优化问题或多目标规划问题. 我们先来看一个生产计划的例子.第60页，共102页，2022年，5月20日，11点4分，星期五第61页，共102页，2022年，5月20日，11点4分，星期五第62页，共102页，2022年，5月20日，11点4

30、分，星期五第63页，共102页，2022年，5月20日，11点4分，星期五第64页，共102页，2022年，5月20日，11点4分，星期五第65页，共102页，2022年，5月20日，11点4分，星期五第66页，共102页，2022年，5月20日，11点4分，星期五第67页，共102页，2022年，5月20日，11点4分，星期五第68页，共102页，2022年，5月20日，11点4分，星期五第69页，共102页，2022年，5月20日，11点4分，星期五Chapter4 图与网络分析( Graph Theory and Network Analysis )图的基本概念与模型树与图的最小树最短路

31、问题网络的最大流本章主要内容：第70页，共102页，2022年，5月20日，11点4分，星期五近代图论的历史可追溯到18世纪的七桥问题穿过Knigsberg城的七座桥，要求每座桥通过一次且仅通过一次。 这就是著名的“哥尼斯堡 7 桥”难题。Euler1736年证明了不可能存在这样的路线。图的基本概念与模型Knigsberg桥对应的图第71页，共102页，2022年，5月20日，11点4分，星期五图的基本概念与模型图论中图是由点和边构成，可以反映一些对象之间的关系。一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。图的定义：若用点表示研究的对象，用边表

32、示这些对象之间的联系，则图G可以定义为点和边的集合，记作：其中: V点集 E边集 图G区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。第72页，共102页，2022年，5月20日，11点4分，星期五图的基本概念与模型(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5可见图论中的图与几何图、工程图是不一样的。例如：在一个人群中，对相互认识这个关系我们可以用图来表示。第73页，共102页，2022年，5月20日，11点4分，星期五图的基本概念与模型定义

33、: 图中的点用v表示，边用e表示。对每条边可用它所连接的点表示，记作：e1=v1,v1; e2=v1,v2; v3e7e4e8e5e6e1e2e3v1v2v4v5 端点,关联边,相邻若有边e可表示为e=vi,vj，称vi和vj是边e的端点，反之称边e为点vi或vj的关联边。若点vi、vj与同一条边关联，称点vi和vj相邻；若边ei和ej具有公共的端点，称边ei和ej相邻。第74页，共102页，2022年，5月20日，11点4分，星期五图的基本概念与模型 环, 多重边, 简单图如果边e的两个端点相重，称该边为环。如右图中边e1为环。如果两个点之间多于一条，称为多重边，如右图中的e4和e5，对无环

34、、无多重边的图称作简单图。v3e7e4e8e5e6e1e2e3v1v2v4v5第75页，共102页，2022年，5月20日，11点4分，星期五图的基本概念与模型 次，奇点，偶点，孤立点与某一个点vi相关联的边的数目称为点vi的次（也叫做度），记作d(vi)。右图中d(v1),d(v3)=5,d(v5)=1。次为奇数的点称作奇点，次为偶数的点称作偶点，次为1的点称为悬挂点，次为0的点称作孤立点。v3e7e4e8e5e6e1e2e3v1v2v4v5图的次: 一个图的次等于各点的次之和。第76页，共102页，2022年，5月20日，11点4分，星期五图的基本概念与模型 链，圈，连通图图中某些点和边的

35、交替序列，若其中各边互不相同，且对任意vi,t-1和vit均相邻称为链。用表示：v3e7e4e8e5e6e1e2e3v1v2v4v5起点与终点重合的链称作圈。如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称图不连通。第77页，共102页，2022年，5月20日，11点4分，星期五图的基本概念与模型 二部图（偶图）图G=(V,E)的点集V可以分为两各非空子集X，Y，集XY=V,XY=,使得同一集合中任意两个顶点均不相邻，称这样的图为偶图。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明显为二部图，(b)也是二部图，但不明显，改画为(c)时可以清楚看出

36、。第78页，共102页，2022年，5月20日，11点4分，星期五图的基本概念与模型 子图，部分图(支撑子图)图G1=V1、E1和图G2=V2，E2如果有 称G1是G2的一个子图。若有 ，则称G1是G2的一个部分图(支撑子图)。v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)（G图）第79页，共102页，2022年，5月20日，11点4分，星期五图的基本概念与模型 网络（赋权图）设图G（V，E），对G的每一条边(vi,vj)相应赋予数量指标wij，wij称为边(vi,vj)的权,赋予权的图G称为网络(或

37、赋权图）。权可以代表距离、费用、通过能力(容量)等等。端点无序的赋权图称为无向网络，端点有序的赋权图称为有向网络。910201571419256第80页，共102页，2022年，5月20日，11点4分，星期五图的基本概念与模型 出次与入次 有向图中，以vi为始点的边数称为点vi的出次，用d+(vi)表示；以vi为终点的边数称为点vi 的入次，用表示d-(vi) ；vi 点的出次和入次之和就是该点的次。 有向图中，所有顶点的入次之和等于所有顶点的出次之和。第81页，共102页，2022年，5月20日，11点4分，星期五图的基本概念与模型图的模型应用例6.1 有甲,乙,丙,丁,戊,己6名运动员报名

38、参加A,B,C,D,E,F 6个项目的比赛。下表中打的是各运动员报告参加的比赛项目。问6个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。ABCDEF甲乙丙丁戊己第82页，共102页，2022年，5月20日，11点4分，星期五图的基本概念与模型解：用图来建模。把比赛项目作为研究对象，用点表示。如果2个项目有同一名运动员参加，在代表这两个项目的点之间连一条线，可得下图。ABCDEF在图中找到一个点序列，使得依次排列的两点不相邻，即能满足要求。如：1) A,C,B,F,E,D2) D,E,F,B,C,A第83页，共102页，2022年，5月20日，11点4分，星期五图的基本概念与模

39、型图的矩阵描述：如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有：邻接矩阵、关联矩阵、权矩阵等。1. 邻接矩阵对于图G=（V，E），| V |=n， | E |=m，有nn阶方矩阵A=(aij) nn，其中第84页，共102页，2022年，5月20日，11点4分，星期五图的基本概念与模型v5v1v2v3v4v64332256437例6.2 下图所表示的图可以构造邻接矩阵A如下第85页，共102页，2022年，5月20日，11点4分，星期五对于赋权图G=(V,E), 其中边 有权 , 构造矩阵B=(bij) nn

40、其中：图的基本概念与模型2. 关联矩阵对于图G=(V,E), | V |=n, | E |=m, 有mn阶矩阵M=(mij) mn，其中:3. 权矩阵第86页，共102页，2022年，5月20日，11点4分，星期五树与图的最小树树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。例6.2 乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。ABCDEFGH运动员第87页，共102页，2022年，5月20日，11点4分，星期五树与图的最小树例6.3 某企业的组织机构图也可用树图表示。厂长人事科财务科总工程师生产副厂长经营副厂长开发科技术科生产科设备科供应科销售科检验科动力科第

41、88页，共102页，2022年，5月20日，11点4分，星期五树与图的最小树 树：无圈的连通图即为树性质1：任何树中必存在次为1的点。性质2：n 个顶点的树必有n-1 条边。性质3：树中任意两个顶点之间，恰有且仅有一条链。性质4：树连通，但去掉任一条边，必变为不连通。性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。v1v2v3v4v5v6第89页，共102页，2022年，5月20日，11点4分，星期五最短路问题问题描述：就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路 .有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为

42、求最短路的问题。因此这类问题在生产实际中得到广泛应用。第90页，共102页，2022年，5月20日，11点4分，星期五最短路问题求最短路有两种算法: 狄克斯屈拉(Dijkstra)标号算法 逐次逼近算法第91页，共102页，2022年，5月20日，11点4分，星期五最短路问题狄克斯屈拉(Dijkstra)标号算法的基本思路：若序列 vs,v1.vn-1,vn 是从vs到vt间的最短路，则序列 vs,v1.vn-1 必为从vs 到vn-1的最短路。假定v1v2 v3 v4是v1 v4的最短路，则v1 v2 v3一定是v1 v3的最短路，v2 v3 v4也一定是v2 v4的最短路。v1v2v3v4

43、v5第92页，共102页，2022年，5月20日，11点4分，星期五最短路问题求网络图的最短路，设图的起点是vs,终点是vt ,以vi为起点vj为终点的弧记为 (i, j) 距离为dijP标号(点标号)：b(j) 起点vs到点vj的最短路长；T标号(边标号)： k(i,j)=b(i)+dij，步骤： 1. 令起点的标号；b(s)0。 2. 找出所有vi已标号vj未标号的弧集合 B=(i, j) 如果这样的弧不存在或vt已标号则计算结束；3. 计算集合B中弧k(i，j)=b(i)+dij的标号4. 选一个点标号 在终点vl处标号b(l), 返回到第2步。第93页，共102页，2022年，5月20日，11点4分，星期五最短路问题例6.5 求下图v1到v7的最短路长及最短路线86252353421057086225441114751071211v7已标号，计算结束。从v1到v7的最短路长是 11,最短路线： v1 v4 v6 v7P标号T标号第94页，共10