1、Page 1 1.对选手的计算机能力提出了更高的要求对选手的计算机能力提出了更高的要求：赛题的解决依赖计算机，题目的数据较多，手工计算赛题的解决依赖计算机，题目的数据较多，手工计算不能完成不能完成;某些问题需要使用计算机软件，如某些问题需要使用计算机软件，如01A;问题的数据读问题的数据读取需要计算机技术，如取需要计算机技术，如04A（数据库数据，数据库方（数据库数据，数据库方法，统计软件包）。法，统计软件包）。计算机模拟和以算法形式给出最终结果计算机模拟和以算法形式给出最终结果,如如09B，11B。2.赛题的开放性增大赛题的开放性增大:题意的开放性，思路的开放题意的开放性，思路的开放性，方法
2、的开放性，结果的开放性。性，方法的开放性，结果的开放性。开放性还表现在开放性还表现在对模型假设和对数据处理上。如对模型假设和对数据处理上。如10BPage 2请你们根据中国国情，收集诸如国家生均拨款、培养费用、请你们根据中国国情，收集诸如国家生均拨款、培养费用、家庭收入等相关数据，并据此通过数学建模的方法，就几家庭收入等相关数据，并据此通过数学建模的方法，就几类学校或专业的学费标准进行定量分析，得出明确、有说类学校或专业的学费标准进行定量分析，得出明确、有说服力的结论。数据的收集和分析是你们建模分析的基础和服力的结论。数据的收集和分析是你们建模分析的基础和重要组成部分。你们的论文必须观点鲜明、
3、分析有据、结重要组成部分。你们的论文必须观点鲜明、分析有据、结论明确。论明确。最后，根据你们建模分析的结果，给有关部门写一份报告，最后，根据你们建模分析的结果，给有关部门写一份报告，提出具体建议。提出具体建议。Page 3 3.试题向大规模数据处理方向发展试题向大规模数据处理方向发展:从从05年开始，基本上每年都有一大数据量的赛题；数年开始，基本上每年都有一大数据量的赛题；数据结构的复杂性：数据的真实性，数据的海量性，数据结构的复杂性：数据的真实性，数据的海量性，数据的不完备性，数据的冗余性据的不完备性，数据的冗余性 4.求解算法和各类现代算法的融合求解算法和各类现代算法的融合；如：；如：11
4、B 5.实用性实用性：问题和数据来自于实际，解决方法切合于问题和数据来自于实际，解决方法切合于实际，模型和结果可以应用于实际。实际，模型和结果可以应用于实际。6.即时性：即时性：国内外的大事，社会的热点，生活的焦点，国内外的大事，社会的热点，生活的焦点，近期发生和即将发生被关注的问题。近期发生和即将发生被关注的问题。Page 4拿到赛题后大家需要思考的问题 题目属于哪种类型：连续的、离散的需要解决什么问题:最优化方案、预测模型、最短路径等等；将问题分解。可以用哪些相关模型、算法求解、需 要什么数学工具。Page 5(2)整个数学建模过程应当由三个阶段：整个数学建模过程应当由三个阶段：1.建立模
5、型：实际问题建立模型：实际问题数学问题；数学问题；2.数学解答：数学问题数学解答：数学问题数学解；数学解；3.模型检验：数学解模型检验：数学解实际问题的解决。实际问题的解决。(1)流程图流程图模型应用模型应用问题分析问题分析模型假设模型假设建立模型建立模型模型求解模型求解模型分析模型分析模型检验模型检验Page 6 重要的是参赛选手具备编程计算、计算机仿真重要的是参赛选手具备编程计算、计算机仿真、模拟能力。、模拟能力。赛题常用的计算软件：赛题常用的计算软件：MatlabMatlab,SPSS,SPSS，EXCEL等等Page 71 全国大学生数学建模竞赛网：全国大学生数学建模竞赛网：http:
6、/2 数学中国网站数学中国网站 http:/3 中国数学建模网站：中国数学建模网站：http:/Page 8 涉及到的涉及到的数学建模方法数学建模方法：几何理论、组合概率、统计几何理论、组合概率、统计(回归回归)分析分析;优化方法（规划）、图论与网络优化、层次优化方法（规划）、图论与网络优化、层次分析分析;差分方法、微分方程、模糊数学、随机决差分方法、微分方程、模糊数学、随机决策、多目标决策策、多目标决策;插值与拟合、灰色系统理论、神经网络、时插值与拟合、灰色系统理论、神经网络、时间序列间序列;综合评价、机理分析等方法综合评价、机理分析等方法;Page 9 用的最多的方法是用的最多的方法是优化
7、方法和概率统计优化方法和概率统计用到用到优化方法优化方法的共有的共有26个题，其中整数规划个题，其中整数规划4个，线性规划个，线性规划7个，非线性规划个，非线性规划14个个,多目标规划多目标规划6个个。用到用到概率统计概率统计方法的有方法的有21个题，平均每年至个题，平均每年至少有一个题目用到概率统计的方法。少有一个题目用到概率统计的方法。用到用到图论与网络优化图论与网络优化方法的问题有方法的问题有6个；个；用到用到层次分析层次分析方法的问题有个；方法的问题有个；Page 10 用到插值拟合的问题有用到插值拟合的问题有6个；个；用灰色系统理论的用灰色系统理论的4个个;用到时间序列分析的至少用到
8、时间序列分析的至少2个个;用到综合评价方法的至少用到综合评价方法的至少3个；个；大部分题目都可以用两种以上的方法来解决大部分题目都可以用两种以上的方法来解决,即综合性较强的题目有即综合性较强的题目有26个个Page 11从数学意义上说，最优化方法是一种求极值的方法，即在一组约束为等式或不等式的条件下，使系统的目标函数达到极值，即最大值或最小值。从经济意义上说，是在一定的人力、物力和财力资源条件下，使经济效果达到最大（如产值、利润），或者在完成规定的生产或经济任务下，使投入的人力、物力和财力等资源为最少。Page 12所有类似的这种课题统称为最优化问题，研究解决这些问题的科学一般就总称之为最优化
9、理论和方法另外也可用学术味更浓的名称：“运筹学”。由于最优化问题背景十分广泛，涉及的知识不尽相同，学科分枝很多，因此这个学科名下到底包含哪些分枝，其说法也不一致。比较公认的是：“规划论”（包括线性和非线性规划、整数规划、动态规划、多目标规划和随机规划等），“组合最优化”，“对策论”及“最优控制”等等。Page 132000B 钢管订购和运输问题 组合优化2001B 公交车优化调度图论2002B 彩票中的数学 决策分析2003B 露天矿生产的车辆安排问题 离散优化2004A 奥运会临时超市网点设计问题 图论2005B DVD在线租赁 离散优化2006A 出版社的资源配置问题 决策分析Page 1
10、407B 乘公交，看奥运 图论 整数规划08B 高等教育学费探讨 层次分析法 多目标优化09B 眼科病床的合理安排动态规划10B 上海世博会经济影响力定量评估 决策分析11B 交巡警服务平台的设置与调度图论 多目标规划12B 太阳能小屋的设计 离散优化13A 车道被占用对城市道路通行能力的影响 离散优化Page 15从数学上来看，所谓最优化问题可以概括为这样一种数学模型：给定一个“函数”，F(X)，以及“自变量”X应满足的一定条件，求X为怎样的值时，F(X)取得其最大值或最小值。通常，称F(X)为“目标函数”，X应满足的条件为“约束条件”。约束条件一般用一个集合D表示为：XD。求目标函数F(X
11、)在约束条件XD下的最小值或最大值问题，就是一般最优问题的数学模型Page 16无约束最优化问题无约束最优化问题)(minxfnRx 目标函数目标函数 约束最优化问题约束最优化问题IixcEixctsxfii ,0)(,0)(.)(min约束函数约束函数 最优解；最优值最优解；最优值Page 17分类分类1 1：无约束最优化无约束最优化 约束最优化约束最优化 非线性规划：非线性规划：目标函数与约束函数中至少有一个目标函数与约束函数中至少有一个是变量是变量x x的非线性函数；的非线性函数；线性规划：线性规划：目标函数与约束函数均为线性函数；目标函数与约束函数均为线性函数；分类分类2 2：线性规划
12、线性规划 非线性规划非线性规划Page 18 分类分类3 3（根据决策变量、（根据决策变量、目标函数和要求目标函数和要求不同）不同）整数规划整数规划动态规划动态规划网络规划网络规划随机规划随机规划多目标规划多目标规划Page 19函数最优化函数最优化组合最优化组合最优化分类分类函数最优化：函数最优化：决策变量是一定区间内的连续变决策变量是一定区间内的连续变量量 组合最优化：组合最优化：决策变量是离散状态，同时可行域决策变量是离散状态，同时可行域是由有限个点组成的集合是由有限个点组成的集合 Page 20（1）确定变量，写出目标函数和有关约束条件，建立数学模型。（2）分析模型，搞清它属于运筹学哪
13、一分枝，选择合适的最优化方法；（3）编程求解；尽量利用现有的数学软件或最优化软件，比如 Matlab，Mathematica，Lindo，Lingo等，来计算。（4）最优解的验证和实施。Chapter1 线性规划线性规划(Linear Programming)LP的数学模型的数学模型 LP模型的应用模型的应用Page 221.规划问题规划问题生产和经营管理中经常提出如何合理安排，使人力、生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。这就是规划问题。（1 1）当任务或目标确定后，如何统筹兼顾，
14、合理安排，用）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源最少的资源 （如资金、设备、原材料、人工、时间等）去（如资金、设备、原材料、人工、时间等）去完成确定的任务或目标完成确定的任务或目标（2 2）在一定的资源条件限制下，如何组织安排生产获得最）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多好的经济效益（如产品量最多 、利润最大、利润最大.）Page 23例例1 某企业计划生产甲、乙两种产品。这些产品分别某企业计划生产甲、乙两种产品。这些产品分别要在要在A、B、C、D、四种不同的设备上加工。按工艺、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备
15、上加工所需要的台时资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使企如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？业总的利润最大？设设 备备产产 品品 A B C D利润（元）利润（元）甲甲 2 1 4 0 2 乙乙 2 2 0 4 3 有有 效效 台台 时时 12 8 16 12Page 24解：设解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：分别为甲、乙两种产品的产量，则数学模型为：Page 25 这是一个典型的利润最大化的生产计划问题。这是一个典型的利润最大化的生产计划问题。其中，其中，“Max”Max”是英文单词是英
16、文单词“Maximize”Maximize”的缩写，的缩写，含义为含义为“最大化最大化”；“s.t.”s.t.”是是“subject to”subject to”的缩写，表示的缩写，表示“满足于满足于”。因此，上述模型的。因此，上述模型的含义是：在给定条件限制下，求使目标函数含义是：在给定条件限制下，求使目标函数 z 达达到最大的到最大的x1,x2 的取值。的取值。Page 26Page 2700 )()(min)max12211112121112211 nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcz)21(j 0 )21(i )(Z (min)max 11nxmbxax
17、cjnjijijnjjj 简写为：简写为：Page 28 mnmnaaaaA1111 0)(min)maxXBAXCXZ其中：其中：)(21ncccC nxxX1 mbbB1Page 293.线性规划问题的标准形式线性规划问题的标准形式minjxbxatsxcZjnjijijnjjj,2,1,2,1,0.max11 特点：特点：(1)目标函数求最大值。目标函数求最大值。(2)约束条件都为等式方程，且右端常数项约束条件都为等式方程，且右端常数项bi都大于或等于零都大于或等于零(3)决策变量决策变量xj为非负。为非负。Page 30 目标函数的转换目标函数的转换 如果是求极小值即如果是求极小值即
18、，则可将目标函数乘以，则可将目标函数乘以(-1)(-1)，可，可化为求极大值问题。化为求极大值问题。jjxczmin也就是：令也就是：令 ，可得到上式。，可得到上式。zz jjxczzmax即即 若存在取值无约束的变量若存在取值无约束的变量 ,可令可令 其中：其中：jxjjjxxx 0,jjxx 变量的变换变量的变换Page 31 约束方程的转换：由不等式转换为等式。约束方程的转换：由不等式转换为等式。ijijbxa0 iniinjijxbxxa称为松弛变量称为松弛变量 ijijbxa0 iniinjijxbxxa称为剩余变量称为剩余变量 变量变量 的变换的变换 可令可令0 jxjjxx 0
19、jxPage 324.4.线性规划问题的解线性规划问题的解 )3(,2,1,0)2(),2,1(.)1(max11njxmibxatsxcZjnjijijnjjj线性规划问题线性规划问题求解线性规划问题，就是从满足约束条件求解线性规划问题，就是从满足约束条件(2)、(3)的方程组的方程组中找出一个解，使目标函数中找出一个解，使目标函数(1)达到最大值。达到最大值。Page 33 可行解可行解：满足约束条件：满足约束条件、的解为可行解。所的解为可行解。所有可行解的集合为可行域。有可行解的集合为可行域。最优解最优解：使目标函数达到最大值的可行解。：使目标函数达到最大值的可行解。线性规划解的情况：有
20、线性规划解的情况：有唯一最优解；有无穷多最唯一最优解；有无穷多最优解；无界解；无可行解优解；无界解；无可行解 Page 34 建立线性规划模型的过程可以分为四个步骤：建立线性规划模型的过程可以分为四个步骤：(1)(1)设立决策变量；设立决策变量；(2)(2)明确所有的约束条件并用决策变量的线性等式或不明确所有的约束条件并用决策变量的线性等式或不等式表示出来；等式表示出来；(3)(3)用决策变量的线性函数表示目标，并确定是求极大用决策变量的线性函数表示目标，并确定是求极大（MaxMax）还是极小（）还是极小（MinMin）；）；(4)(4)根据决策变量的物理性质研究变量是否有非负性。根据决策变量
21、的物理性质研究变量是否有非负性。求解方法：用求解方法：用MATLABMATLAB软件直接求解。软件直接求解。运输问题的数学模型运输问题的数学模型运输问题的应用运输问题的应用 Page 36问题的提出问题的提出 一般的运输问题就是要解决把某种产品从若一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输运输单价的前提下，如何确定一个使得总的运输费用最小的方案。费用最小的方案。Page 37例例2.1 某公
22、司从两个产地某公司从两个产地A1、A2将物品运往三个销地将物品运往三个销地B1,B2,B3，各产地的产量、各销地的销量和各产地运往各销地每件，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最物品的运费如下表所示，问：应如何调运可使总运输费用最小？小？B1B2B3产量产量A1646200A2655300销量销量150150200Page 38解：产销平衡问题：总产量解：产销平衡问题：总产量=总销量总销量500 设设 xij 为从产地为从产地Ai运往销地运往销地Bj的运输量，得到下列运输量的运输量，得到下列运输量表：表：B1B2B3产量产量A1x
23、11x12x13200A2x21x22x23300销量销量150150200Min C=6x11+4x12+6x13+6x21+5x22+5x23 s.t.x11+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）Page 39运输问题的一般形式：产销平衡运输问题的一般形式：产销平衡A1、A2、Am 表示某物资的表示某物资的m个产地；个产地；B1、B2、Bn 表示表示某物质的某物质的n个销地；个销地；ai 表示产地表示产地Ai的产量；的产量；bj 表示销地表示销地Bj 的销量
24、；的销量；cij 表示把物资从产地表示把物资从产地Ai运往销地运往销地Bj的单位运价。设的单位运价。设 xij 为从产地为从产地Ai运往销地运往销地Bj的运输量，得到下列一般运输量问题的模型：的运输量，得到下列一般运输量问题的模型：minjijijxcz11min njmixnjbxmiaxtsijjmiijnjiij,1;,1,0,1,1.11Page 40变化：变化：1）有时目标函数为求最大值。如求利润最大或营业额最）有时目标函数为求最大值。如求利润最大或营业额最大；大；2）当某些运输线路上的能力有限制时，在模型中直接加）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等
25、式约束入约束条件（等式或不等式约束)；3）产销不平衡时，可加入假想的产地（销大于产时）或）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。销地（产大于销时）。Page 413.当总产量与总销量不相等时当总产量与总销量不相等时,称为不平衡运输问题称为不平衡运输问题.这类这类运输问题在实际中常常碰到运输问题在实际中常常碰到,它的求解方法是将不平衡问题它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。化为平衡问题再按平衡问题求解。当产大于销时，即：当产大于销时，即：minjjiba11数学模型为：数学模型为：minjijijxcZ11min njmixnjbxmiaxijmi
26、jijnjiij,2,1;,2,10,2,1,2,111，Page 42由于总产量大于总销量，必有部分产地的产量不能全部运送完，由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，假设该仓库为一个虚拟必须就地库存，即每个产地设一个仓库，假设该仓库为一个虚拟销地销地Bn+1，bn+1作为一个虚设销地作为一个虚设销地Bn+1的销量的销量(即库存量即库存量)。各产地。各产地Ai到到Bn+1的运价为零，即的运价为零，即Ci,n+1=0,（i=1，m）。则平衡问题的）。则平衡问题的数学模型为：数学模型为：minjijijxcZ11min1111,2,1,2,10,
27、1,2,1,2,1nijijmijjiijxaimxbjnximjn；Page 43 当销大于产时，即：当销大于产时，即：minjjiba11 minjijijxCZ11min ,2,1;,2,1,0,2,1,2,111jmixnjbxmiaxijmijijnjiij数学模型为：数学模型为：由于总销量大于总产由于总销量大于总产量量,故一定有些需求地故一定有些需求地不完全满足不完全满足,这时虚设这时虚设一个产地一个产地Am+1，产量，产量为：为：miinjjab11Page 44销大于产化为平衡问题的数学模型为销大于产化为平衡问题的数学模型为：minjijijxcZ11min njmixnjbx
28、miaxijmijijnjiji,2,11,2,1,0,2,11,2,1111；具体计算时，在运价表的下方增加一行具体计算时，在运价表的下方增加一行Am+1，运价为零。产，运价为零。产量为量为am+1即可。即可。整数规划的特点及应用整数规划的特点及应用指配问题与匈牙利法指配问题与匈牙利法Page 46引言引言 整数规划是规划论中近几十年才发展起来的一个整数规划是规划论中近几十年才发展起来的一个重要分支，主要是由于经济管理中的大量问题在抽重要分支，主要是由于经济管理中的大量问题在抽象成模型时，人们发现许多量具有不可分割性，因象成模型时，人们发现许多量具有不可分割性，因此当它们被作为变量引入到规划
29、中时，常要求满足此当它们被作为变量引入到规划中时，常要求满足取整条件取整条件.如生产计划中，生产机器多少台如生产计划中，生产机器多少台(整数整数)；人力资源管理中，招聘员工多少人人力资源管理中，招聘员工多少人(整数整数)；运输问题；运输问题中，从一个港口到另一个港口的集装箱调运数量中，从一个港口到另一个港口的集装箱调运数量(整整数数)；另外，运作管理中的决策问题：如工厂选址、；另外，运作管理中的决策问题：如工厂选址、人员的工作指派、设备购置和配置等人员的工作指派、设备购置和配置等.Page 47一辆车最大装载重量为7吨，容量为12立方米。现有两种物品，每种物品数量无限。各种物品每件的体积、重量
30、、价格如下表：物品1物品2体积（立方米/件）34重量（吨/件）42价值（万元/件）43求这辆车中装入每种物品各多少件，使物品总价值最高。背包问题背包问题Page 48设三种物品的件数各为设三种物品的件数各为x1，x2件，总价值为件，总价值为z max z=4x1+3x2 s.t.3x1+4x212 4x1+2x2 7 x1，x20，x1，x2为整数为整数Page 49要求一部分或全部决策变量取整数值的规划问题称为整要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件构数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题
31、的松弛问题。若该松弛问成的规划问题称为该整数规划问题的松弛问题。若该松弛问题是一个线性规划，则称该整数规划为整数线性规划。题是一个线性规划，则称该整数规划为整数线性规划。整数线性规划数学模型的一般形式：整数线性规划数学模型的一般形式：11max(min)(,)(1,2)0(j1.2n)njjjnijjijjZZc xa xbimx 或且部分或全部为整数Page 50 纯整数规划：指全部决策变量都必须取整数值的整数规划。纯整数规划：指全部决策变量都必须取整数值的整数规划。混合整数规划：决策变量中有一部分必须取整数值，另一混合整数规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数规
32、划。部分可以不取整数值的整数规划。0-1型整数规划：决策变量只能取值型整数规划：决策变量只能取值0或或1的整数规划。的整数规划。Page 51 整数规划问题的可行解集合是它松弛问题可行解集合的一整数规划问题的可行解集合是它松弛问题可行解集合的一个子集，任意两个可行解的凸组合不一定满足整数约束条件，个子集，任意两个可行解的凸组合不一定满足整数约束条件，因而不一定仍为可行解。因而不一定仍为可行解。整数规划问题的可行解一定是它的松弛问题的可行解（反整数规划问题的可行解一定是它的松弛问题的可行解（反之不一定），但其最优解的目标函数值不会优于后者最优解之不一定），但其最优解的目标函数值不会优于后者最优解
33、的目标函数值。的目标函数值。Page 52 0-1整数规划是整数规划中的特殊情形，它的变量整数规划是整数规划中的特殊情形，它的变量仅取值仅取值0或者或者1，我们通常称为，我们通常称为0-1变量或逻辑变量变量或逻辑变量.在实在实践中，许多问题只回答是或否践中，许多问题只回答是或否.例如，对某个项目是否例如，对某个项目是否投资，对某个应聘者是否聘用，对某种新产品是否研发投资，对某个应聘者是否聘用，对某种新产品是否研发等，这类问题都可以用等，这类问题都可以用0-1变量来描绘变量来描绘.Page 53整数规划问题的求解方法：整数规划问题的求解方法：分支定界法和割平面法分支定界法和割平面法 匈牙利法（指
34、派问题）匈牙利法（指派问题）求解整数规划模型的数学软件有：求解整数规划模型的数学软件有：Lindo,Lingo和和Matlab,其中其中Lindo和和Lingo是专业的优化软件是专业的优化软件.Page 54 在生活中经常遇到这样的问题，某单位需完成在生活中经常遇到这样的问题，某单位需完成n项项任务，恰好有任务，恰好有n个人可以承担这些任务个人可以承担这些任务.一项任务只能由一项任务只能由一个人完成，一个人只能完成一项任务。一个人完成，一个人只能完成一项任务。由于每人的由于每人的专长不同，每个人完成各项任务的效率不同专长不同，每个人完成各项任务的效率不同.于是产生于是产生应指派哪个人去完成哪项
35、任务，使完成应指派哪个人去完成哪项任务，使完成n项任务的总效项任务的总效率最高率最高(或所需总时间最小，费用最低）。或所需总时间最小，费用最低）。Page 55设设n 个人被分配去做个人被分配去做n 件工作，规定每个人只做一件工作，件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第每件工作只有一个人去做。已知第i个人去做第个人去做第j 件工作的件工作的 时时间或费用为间或费用为Cij(i=1.2n;j=1.2n)并假设并假设Cij 0。问应如何分配。问应如何分配才能使总效率最高？才能使总效率最高？设决策变量设决策变量 1j(,1,2,.,)0ijijxi jn指派第i个人做第 件事
36、不指派第 个人做第 件事Page 56指派问题的数学模型为：指派问题的数学模型为：).2.1,1(0).2.1(1).2.1(1min1111njixnjxnixxcZijniijnjijninjijij或或取取Page 57例例2 2 指派问题：人事部门欲安排四人到四个不同岗位工作，指派问题：人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表所示，如何安排他们的工作使总成绩最好。如表所示，如何安排他们的工作使总成绩最好。工作工作人员人员ABCD甲甲85927390乙乙95877895丙丙82837
37、990丁丁86908088Page 58设设 工工作作时时人人做做不不分分配配第第工工作作时时人人做做分分配配第第jijixij01数学模型如下：数学模型如下：4443424134333231242322211413121188809086907983829578879590739285maxxxxxxxxxxxxxxxxxZ 要求每人做一项工作，约束条件为：要求每人做一项工作，约束条件为：111144434241343332312423222114131211xxxxxxxxxxxxxxxxPage 59每项工作只能安排一人，约束条件为：每项工作只能安排一人，约束条件为：1111443424
38、14433323134232221241312111xxxxxxxxxxxxxxxx变量约束：变量约束：011,2,3,4ijxij或，、对于指派问题等对于指派问题等 0-1 整数规划问题，可以直接利用整数规划问题，可以直接利用Matlab 的函数的函数bintprog 进行求解。进行求解。Page 60 在许多实际问题中，衡量一个方案的好坏标准往往不止一个，例如设计一个导弹，既要射程最远，又要燃料最省，还要精度最高.这一类问题统称为多目标最优化问题或多目标规划问题.我们先来看一个生产计划的例子.Page 61Page 62Page 63Page 64Page 65Page 66Page 67
39、Page 68Page 69图的基本概念与模型图的基本概念与模型树与图的最小树树与图的最小树最短路问题最短路问题网络的最大流网络的最大流Page 71近代图论的历史可追溯到近代图论的历史可追溯到18世纪的七桥问题世纪的七桥问题穿过穿过Knigsberg城的七座桥，要求每座桥通过一次且仅通过一次。城的七座桥，要求每座桥通过一次且仅通过一次。这就是著名的这就是著名的“哥尼斯堡哥尼斯堡 7 桥桥”难题。难题。Euler1736年证明了不年证明了不可能存在这样的路线。可能存在这样的路线。Page 72图论中图是由点和边构成，可以反映一些对象之间的关系。图论中图是由点和边构成，可以反映一些对象之间的关系
40、。一般情况下图中点的相对位置如何、点与点之间联线的长短一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。曲直，对于反映对象之间的关系并不是重要的。若用点表示研究的对象，用边表示这些对象之间的联系，若用点表示研究的对象，用边表示这些对象之间的联系，则图则图G可以定义为点和边的集合，记作：可以定义为点和边的集合，记作：,EVG 其中其中:V点集点集 E边集边集 图图G区别于几何学中的图。这里只关心图中有多少个点以区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。及哪些点之间有连线。Page 73(v1)赵赵(v2)钱钱孙孙(v3)李李(v
41、4)周周(v5)吴吴(v6)陈陈(v7)e2e1e3e4e5(v1)赵赵(v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈e2e1e3e4e5可见图论中的图与几何图、工程图是不一样的。可见图论中的图与几何图、工程图是不一样的。例如：在一个人群中，对相互认识这个关系我们可以用图来例如：在一个人群中，对相互认识这个关系我们可以用图来表示。表示。Page 74定义定义:图中的点用图中的点用v表示，边用表示，边用e表示。对每条边可用它所连表示。对每条边可用它所连接的点表示，记作：接的点表示，记作：e1=v1,v1;e2=v1,v2;v3e7e4e8e5e6e1e2e3v1v2v4
42、v5 端点端点,关联边关联边,相邻相邻若有边若有边e可表示为可表示为e=vi,vj，称，称vi和和vj是边是边e的的端点端点，反之称边，反之称边e为点为点vi或或vj的的关联边关联边。若点。若点vi、vj与同一条边关与同一条边关联，称点联，称点vi和和vj相邻；若边相邻；若边ei和和ej具具有公共的端点，称边有公共的端点，称边ei和和ej相邻相邻。Page 75 环环,多重边多重边,简单图简单图如果边如果边e的两个端点相重，称该边为的两个端点相重，称该边为环环。如右图中边。如右图中边e1为环。如果两个点为环。如果两个点之间多于一条，称为之间多于一条，称为多重边多重边，如右图，如右图中的中的e4
43、和和e5，对无环、无多重边的图，对无环、无多重边的图称作称作简单图简单图。v3e7e4e8e5e6e1e2e3v1v2v4v5Page 76 次，奇点，偶点，孤立点次，奇点，偶点，孤立点与某一个点与某一个点vi相关联的边的数目称为相关联的边的数目称为点点vi的的次次（也叫做度），记作（也叫做度），记作d(vi)。右图中右图中d(v1),d(v3)=5,d(v5)=1。次。次为奇数的点称作为奇数的点称作奇点奇点，次为偶数的，次为偶数的点称作点称作偶点偶点，次为，次为1的点称为的点称为悬挂点悬挂点，次为次为0的点称作的点称作孤立点孤立点。v3e7e4e8e5e6e1e2e3v1v2v4v5图的次图
44、的次:一个图的次等于各点的次之和。一个图的次等于各点的次之和。Page 77 链，圈，连通图链，圈，连通图图中某些点和边的交替序列，若其图中某些点和边的交替序列，若其中各边互不相同，且对任意中各边互不相同，且对任意vi,t-1和和vit均相邻称为均相邻称为链链。用。用 表示：表示：v3e7e4e8e5e6e1e2e3v1v2v4v5,110kkvevev 起点与终点重合的链称作起点与终点重合的链称作圈圈。如。如果每一对顶点之间至少存在一条果每一对顶点之间至少存在一条链，称这样的图为链，称这样的图为连通图连通图，否则，否则称图不连通。称图不连通。Page 78 二部图（偶图）二部图（偶图）图图G
45、=(V,E)的点集的点集V可以分为两各非空子集可以分为两各非空子集X，Y，集，集XY=V,XY=,使得同一集合中任意两个顶点均不使得同一集合中任意两个顶点均不相邻，称这样的图为偶图。相邻，称这样的图为偶图。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明显为二部图，明显为二部图，(b)也是二部图，但不明显，改画为也是二部图，但不明显，改画为(c)时可以清楚看出。时可以清楚看出。Page 79 子图，部分图子图，部分图(支撑子图支撑子图)图图G1=V1、E1和图和图G2=V2，E2如果有如果有 称称G1是是G2的一个的一个子图子图。若有若有 ，则称，则称G1是是
46、G2的一的一个个部分图部分图(支撑子图支撑子图)。2121EEVV 和和2121EEVV，v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)（G图）图）Page 80 网络（赋权图）网络（赋权图）设图设图G（V，E），对），对G的每一条边的每一条边(vi,vj)相应赋予数量指标相应赋予数量指标wij，wij称为边称为边(vi,vj)的的权权,赋予权的图赋予权的图G称为网络称为网络(或或赋权图）赋权图）。权可以代表距离、费用、通过能力权可以代表距离、费用、通过能力(容量容量)等等。等等。端点无序的赋权图称为
47、端点无序的赋权图称为无向网络无向网络，端点有序的赋权图称为，端点有序的赋权图称为有有向网络。向网络。910201571419256Page 81 出次与入次出次与入次 有向图中，以有向图中，以vi为始点的边数称为点为始点的边数称为点vi的的出次出次，用，用d+(vi)表表示；以示；以vi为终点的边数称为点为终点的边数称为点vi 的的入次入次，用表示，用表示d-(vi)；vi 点点的出次和入次之和就是该点的次。的出次和入次之和就是该点的次。有向图中，所有顶点的入次之和等于所有顶点的出次之有向图中，所有顶点的入次之和等于所有顶点的出次之和。和。Page 82例例6.1 有甲有甲,乙乙,丙丙,丁丁,
48、戊戊,己己6名运动员报名参加名运动员报名参加A,B,C,D,E,F 6个项目的比赛。下表中打个项目的比赛。下表中打的是各运动员报告参加的比赛项的是各运动员报告参加的比赛项目。问目。问6个项目的比赛顺序应如何安排，做到每名运动员都个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。不连续地参加两项比赛。ABCDEF甲甲乙乙丙丙丁丁戊戊己己Page 83解：用图来建模。把比赛项目作为研究对象，用点表示。如解：用图来建模。把比赛项目作为研究对象，用点表示。如果果2个项目有同一名运动员参加，在代表这两个项目的点之个项目有同一名运动员参加，在代表这两个项目的点之间连一条线，可得下图。间连一
49、条线，可得下图。ABCDEF在图中找到一个点序在图中找到一个点序列，使得依次排列的列，使得依次排列的两点不相邻，即能满两点不相邻，即能满足要求。如：足要求。如：1)A,C,B,F,E,D2)D,E,F,B,C,APage 84图的矩阵描述：图的矩阵描述：如何在计算机中存储一个图呢？现在已有很多存储的方法，如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有：也根据所关心的问题不同而有：邻接矩阵、关联矩阵、权矩阵等。邻接矩阵、关联矩阵、权矩阵等。1.邻接矩阵邻接矩阵对
50、于图对于图G=（V，E），），|V|=n，|E|=m，有，有n n阶方阶方矩阵矩阵A=(aij)n n，其中其中 其它其它之间有关联边时之间有关联边时与与当且仅档当且仅档0vv1jiijaPage 85v5v1v2v3v4v64332256437 010101101001010111101010001101111010 65432166654321 vvvvvvAvvvvvv例例6.2 下图所表示的图可以构造邻接矩阵下图所表示的图可以构造邻接矩阵A如下如下Page 86对于赋权图对于赋权图G=(V,E),其中边其中边 有权有权 ,构造矩阵构造矩阵B=(bij)n n 其中：其中：对于图对于图G
