离散优化数学建模 (2).ppt

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