离散优化数学建模精选文档.ppt

《离散优化数学建模精选文档.ppt》由会员分享，可在线阅读，更多相关《离散优化数学建模精选文档.ppt（102页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、离散优化数学建模离散优化数学建模本讲稿第一页，共一百零二页2008年年B B题题 高等教育学费标准探讨高等教育学费标准探讨请你们根据中国国情，收集诸如国家生均拨款、培养费用、请你们根据中国国情，收集诸如国家生均拨款、培养费用、家庭收入等相关数据，并据此通过数学建模的方法，就几类家庭收入等相关数据，并据此通过数学建模的方法，就几类学校或专业的学费标准进行定量分析，得出明确、有说服力学校或专业的学费标准进行定量分析，得出明确、有说服力的结论。数据的收集和分析是你们建模分析的基础和重要组的结论。数据的收集和分析是你们建模分析的基础和重要组成部分。你们的论文必须观点鲜明、分析有据、结论明确。成部分。你

2、们的论文必须观点鲜明、分析有据、结论明确。最后，根据你们建模分析的结果，给有关部门写一份报告，最后，根据你们建模分析的结果，给有关部门写一份报告，提出具体建议。提出具体建议。本讲稿第二页，共一百零二页 3.试题向大规模数据处理方向发展试题向大规模数据处理方向发展:从从05年开始，基本上每年都有一大数据量的赛题；数据结构年开始，基本上每年都有一大数据量的赛题；数据结构的复杂性：数据的真实性，数据的海量性，数据的不完备性，的复杂性：数据的真实性，数据的海量性，数据的不完备性，数据的冗余性数据的冗余性 4.求解算法和各类现代算法的融合求解算法和各类现代算法的融合；如：；如：11B 5.实用性实用性：

3、问题和数据来自于实际，解决方法切合于实际，问题和数据来自于实际，解决方法切合于实际，模型和结果可以应用于实际。模型和结果可以应用于实际。6.即时性：即时性：国内外的大事，社会的热点，生活的焦点，近期国内外的大事，社会的热点，生活的焦点，近期发生和即将发生被关注的问题。发生和即将发生被关注的问题。本讲稿第三页，共一百零二页拿到赛题后大家需要思考的问题 题目属于哪种类型：连续的、离散的需要解决什么问题:最优化方案、预测模型、最短路径等等；将问题分解。可以用哪些相关模型、算法求解、需 要什么数学工具。本讲稿第四页，共一百零二页1、数学建模的过程、数学建模的过程(2)整个数学建模过程应当由三个阶段：整

4、个数学建模过程应当由三个阶段：1.建立模型：实际问题建立模型：实际问题数学问题；数学问题；2.数学解答：数学问题数学解答：数学问题数学解；数学解；3.模型检验：数学解模型检验：数学解实际问题的解决。实际问题的解决。(1)流程图流程图模型应用模型应用问题分析问题分析模型假设模型假设建立模型建立模型模型求解模型求解模型分析模型分析模型检验模型检验本讲稿第五页，共一百零二页 解决问题涉及到的计算软件分析解决问题涉及到的计算软件分析 重要的是参赛选手具备编程计算、计算机仿真、重要的是参赛选手具备编程计算、计算机仿真、模拟能力。模拟能力。赛题常用的计算软件：赛题常用的计算软件：Matlab,SPSSMa

5、tlab,SPSS，EXCEL等等本讲稿第六页，共一百零二页参考网站1 全国大学生数学建模竞赛网：全国大学生数学建模竞赛网：http:/2 数学中国网站数学中国网站 http:/3 中国数学建模网站：中国数学建模网站：http:/本讲稿第七页，共一百零二页 从问题的解决方法上分析从问题的解决方法上分析 涉及到的涉及到的数学建模方法数学建模方法：几何理论、组合概率、统计几何理论、组合概率、统计(回归回归)分析分析;优化方法（规划）、图论与网络优化、层次分析优化方法（规划）、图论与网络优化、层次分析;差分方法、微分方程、模糊数学、随机决策、多差分方法、微分方程、模糊数学、随机决策、多目标决策目标决

6、策;插值与拟合、灰色系统理论、神经网络、时间序插值与拟合、灰色系统理论、神经网络、时间序列列;综合评价、机理分析等方法综合评价、机理分析等方法;本讲稿第八页，共一百零二页 用的最多的方法是用的最多的方法是优化方法和概率统计优化方法和概率统计用用到到优优化化方方法法的的共共有有26个个题题，其其中中整整数数规规划划4个个，线性规划线性规划7个，非线性规划个，非线性规划14个个,多目标规划多目标规划6个个。用到用到概率统计概率统计方法的有方法的有21个题，平均每年至少有个题，平均每年至少有一个题目用到概率统计的方法。一个题目用到概率统计的方法。用到用到图论与网络优化图论与网络优化方法的问题有方法的

7、问题有6个；个；用到用到层次分析层次分析方法的问题有个；方法的问题有个；本讲稿第九页，共一百零二页 用到插值拟合的问题有用到插值拟合的问题有6个；个；用灰色系统理论的用灰色系统理论的4个个;用到时间序列分析的至少用到时间序列分析的至少2个个;用到综合评价方法的至少用到综合评价方法的至少3个；个；大部分题目都可以用两种以上的方法来解决大部分题目都可以用两种以上的方法来解决,即综即综合性较强的题目有合性较强的题目有26个个本讲稿第十页，共一百零二页最优化概论最优化概论从数学意义上说，最优化方法是一种求极值的方法，即在一组约束为等式或不等式的条件下，使系统的目标函数达到极值，即最大值或最小值。从经济

8、意义上说，是在一定的人力、物力和财力资源条件下，使经济效果达到最大（如产值、利润），或者在完成规定的生产或经济任务下，使投入的人力、物力和财力等资源为最少。本讲稿第十一页，共一百零二页一、最优化概念一、最优化概念所有类似的这种课题统称为最优化问题，研究解决这些问题的科学一般就总称之为最优化理论和方法另外也可用学术味更浓的名称：“运筹学”。由于最优化问题背景十分广泛，涉及的知识不尽相同，学科分枝很多，因此这个学科名下到底包含哪些分枝，其说法也不一致。比较公认的是：“规划论”（包括线性和非线性规划、整数规划、动态规划、多目标规划和随机规划等），“组合最优化”，“对策论”及“最优控制”等等。本讲稿第

9、十二页，共一百零二页数学建模竞赛中的优化问题数学建模竞赛中的优化问题2000B 钢管订购和运输问题 组合优化2001B 公交车优化调度图论2002B 彩票中的数学 决策分析2003B 露天矿生产的车辆安排问题 离散优化2004A 奥运会临时超市网点设计问题 图论2005B DVD在线租赁 离散优化2006A 出版社的资源配置问题 决策分析本讲稿第十三页，共一百零二页07B 乘公交，看奥运 图论 整数规划08B 高等教育学费探讨 层次分析法 多目标优化09B 眼科病床的合理安排动态规划10B 上海世博会经济影响力定量评估 决策分析11B 交巡警服务平台的设置与调度图论 多目标规划12B 太阳能小

10、屋的设计 离散优化13A 车道被占用对城市道路通行能力的影响 离散优化本讲稿第十四页，共一百零二页从数学上来看，所谓最优化问题可以概括为这样一种数学模型：给定一个“函数”，F(X)，以及“自变量”X应满足的一定条件，求X为怎样的值时，F(X)取得其最大值或最小值。通常，称F(X)为“目标函数”，X应满足的条件为“约束条件”。约束条件一般用一个集合D表示为：XD。求目标函数F(X)在约束条件XD下的最小值或最大值问题，就是一般最优问题的数学模型本讲稿第十五页，共一百零二页无约束最优化问题无约束最优化问题目标函数目标函数 二、最优化问题的一般形式二、最优化问题的一般形式约束最优化问题约束最优化问题

11、约束函数约束函数 最优解；最优值最优解；最优值本讲稿第十六页，共一百零二页三、最优化问题分类三、最优化问题分类分类分类1 1：无约束最优化无约束最优化 约束最优化约束最优化 非线性规划：非线性规划：目标函数与约束函数中至少有一个是变目标函数与约束函数中至少有一个是变量量x x的非线性函数；的非线性函数；线性规划：线性规划：目标函数与约束函数均为线性函数；目标函数与约束函数均为线性函数；分类分类2 2：线性规划线性规划 非线性规划非线性规划本讲稿第十七页，共一百零二页三、最优化问题分类三、最优化问题分类 分类分类3 3（根据决策变量、（根据决策变量、目标函数和要求不目标函数和要求不同）同）整数规

12、划整数规划动态规划动态规划网络规划网络规划随机规划随机规划多目标规划多目标规划本讲稿第十八页，共一百零二页三、最优化问题分类三、最优化问题分类函数最优化函数最优化组合最优化组合最优化分类分类函数最优化：函数最优化：决策变量是一定区间内的连续变量决策变量是一定区间内的连续变量 组合最优化：组合最优化：决策变量是离散状态，同时可行域是由决策变量是离散状态，同时可行域是由有限个点组成的集合有限个点组成的集合 本讲稿第十九页，共一百零二页最优化方法解决问题的步骤最优化方法解决问题的步骤最优化方法解决问题的步骤最优化方法解决问题的步骤（1）确定变量，写出目标函数和有关约束条件，建立数学模型。（2）分析模

13、型，搞清它属于运筹学哪一分枝，选择合适的最优化方法；（3）编程求解；尽量利用现有的数学软件或最优化软件，比如 Matlab，Mathematica，Lindo，Lingo等，来计算。（4）最优解的验证和实施。本讲稿第二十页，共一百零二页Chapter1 线性规划线性规划(Linear Programming)(Linear Programming)LP的数学模型的数学模型 LP模型的应用模型的应用本章主要内容：本章主要内容：本章主要内容：本章主要内容：本讲稿第二十一页，共一百零二页线性规划问题的数学模型线性规划问题的数学模型1.规划问题规划问题生产和经营管理中经常提出如何合理安排，使人力、物力

14、生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划等各种资源得到充分利用，获得最大的效益，这就是规划问题。问题。线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：（1 1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源资源 （如资金、设备、原材料、人工、时间等）去完成确定的任务（如资金、设备、原材料、人工、时间等）去完成确定的任务或目标或目标（2 2）在一定的资源条件限制下，如何组织安排生产获得最好的）在一定的资

15、源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多经济效益（如产品量最多 、利润最大、利润最大.）本讲稿第二十二页，共一百零二页线性规划问题的数学模型线性规划问题的数学模型例例1 某企业计划生产甲、乙两种产品。这些产品分别要在某企业计划生产甲、乙两种产品。这些产品分别要在A、B、C、D、四种不同的设备上加工。按工艺资料规定，单件、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？者应如何安排生产计划，使企业总的利润最大？设 备产 品 A B C

16、D利润（元）甲 2 1 4 0 2 乙 2 2 0 4 3 有 效 台 时 12 8 16 12本讲稿第二十三页，共一百零二页线性规划问题的数学模型线性规划问题的数学模型解：设解：设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 12本讲稿第二十四页，共一百零二页 这这是是一一个个典典型型的的利

17、利润润最最大大化化的的生生产产计计划划问问题题。其其中中，“Max”Max”是是英英文文单单词词“Maximize”Maximize”的的缩缩写写，含含义义为为“最最大大化化”；“s.t.”s.t.”是是“subject subject to”to”的的缩缩写写，表表示示“满满足足于于”。因因此此，上上述述模模型型的的含含义义是是：在在给给定定条条件件限限制制下下，求求使使目目标标函函数数 z 达达到到最最大大的的x1,x2 的取值。的取值。本讲稿第二十五页，共一百零二页线性规划问题的数学模型线性规划问题的数学模型2.2.2.2.线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成

18、线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成决策变量决策变量决策变量决策变量 Decision variables Decision variables 目标函数目标函数目标函数目标函数 Objective function Objective function约束条件约束条件约束条件约束条件 Constraints Constraints其特征是：其特征是：其特征是：其特征是：（1 1 1 1）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的线性线性线性线性函数，通常是求函数，通常是求函数，通常

19、是求函数，通常是求最大值或最小值；最大值或最小值；最大值或最小值；最大值或最小值；（2 2 2 2）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的线性线性线性线性不等式不等式不等式不等式或等式。或等式。或等式。或等式。怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？本讲稿第二十六页，共一百零二页线性规划问题的数学模型线性规划问题的数学模型目标函数：目标函数：目标函数：目标函数：约束条件：约束条件：约束条件：约束条件：3.

20、3.线性规划数学模型的一般形式线性规划数学模型的一般形式线性规划数学模型的一般形式线性规划数学模型的一般形式简写为：简写为：本讲稿第二十七页，共一百零二页线性规划问题的数学模型线性规划问题的数学模型矩阵形式：矩阵形式：矩阵形式：矩阵形式：其中：其中：本讲稿第二十八页，共一百零二页线性规划问题的数学模型线性规划问题的数学模型3.线性规划问题的标准形式线性规划问题的标准形式特点：特点：(1)目标函数求最大值。目标函数求最大值。(2)约束条件都为等式方程，且右端常数项约束条件都为等式方程，且右端常数项bi都大于或等于零都大于或等于零(3)决策变量决策变量xj为非负。为非负。本讲稿第二十九页，共一百零

21、二页线性规划问题的数学模型线性规划问题的数学模型（2 2 2 2）如何化标准形式）如何化标准形式）如何化标准形式）如何化标准形式 目标函数的转换目标函数的转换 如果是求极小值即如果是求极小值即 ，则可将目标函数乘以，则可将目标函数乘以(-1)(-1)，可化，可化为求极大值问题。为求极大值问题。也就是：令也就是：令 ，可得到上式。，可得到上式。即即 若存在取值无约束的变量若存在取值无约束的变量 ,可令可令 其中：其中：变量的变换变量的变换本讲稿第三十页，共一百零二页线性规划问题的数学模型线性规划问题的数学模型 约束方程的转换：由不等式转换为等式。约束方程的转换：由不等式转换为等式。称为松弛变量称

22、为松弛变量称为剩余变量称为剩余变量 变量变量 的变换的变换 可令可令本讲稿第三十一页，共一百零二页线性规划问题的数学模型线性规划问题的数学模型4.4.线性规划问题的解线性规划问题的解线性规划问题线性规划问题求解线性规划问题，就是从满足约束条件求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一的方程组中找出一个解，使目标函数个解，使目标函数(1)达到最大值。达到最大值。本讲稿第三十二页，共一百零二页线性规划问题的数学模型线性规划问题的数学模型 可行解可行解：满足约束条件：满足约束条件、的解为可行解。所有可行解的解为可行解。所有可行解的集合为可行域。的集合为可行域。最优解最优解：使

23、目标函数达到最大值的可行解。：使目标函数达到最大值的可行解。线性规划解的情况：有线性规划解的情况：有唯一最优解；有无穷多最优解；唯一最优解；有无穷多最优解；无界解；无可行解无界解；无可行解 本讲稿第三十三页，共一百零二页 建立线性规划模型的过程可以分为四个步骤：建立线性规划模型的过程可以分为四个步骤：(1)(1)设立决策变量；设立决策变量；(2)(2)明明确确所所有有的的约约束束条条件件并并用用决决策策变变量量的的线线性性等等式式或或不不等等式式表表示示出来；出来；(3)(3)用用决决策策变变量量的的线线性性函函数数表表示示目目标标，并并确确定定是是求求极极大大（MaxMax）还是极小（）还是

24、极小（MinMin）；）；(4)(4)根据决策变量的物理性质研究变量是否有非负性。根据决策变量的物理性质研究变量是否有非负性。求解方法：用求解方法：用MATLABMATLAB软件直接求解。软件直接求解。本讲稿第三十四页，共一百零二页Chapter2 运输运输问题问题(Transportation Problem)(Transportation Problem)运输问题的数学模型运输问题的数学模型运输问题的应用运输问题的应用 本章主要内容：本章主要内容：本章主要内容：本章主要内容：本讲稿第三十五页，共一百零二页1.运输问题模型及有关概念问题的提出问题的提出 一一般般的的运运输输问问题题就就是是要

25、要解解决决把把某某种种产产品品从从若若干干个个产产地地调调运运到到若若干干个个销销地地，在在每每个个产产地地的的供供应应量量与与每每个个销销地地的的需需求求量量已已知知，并并知知道道各各地地之之间间的的运运输输单单价价的的前前提提下下，如如何何确确定定一一个个使使得得总总的的运运输输费费用用最最小小的方案。的方案。本讲稿第三十六页，共一百零二页运输问题的数学模型运输问题的数学模型例例2.1 某公司从两个产地某公司从两个产地A1、A2将物品运往三个销地将物品运往三个销地B1,B2,B3，各产地的产量、各销地的销量和各产地运往各销地每件，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如

26、下表所示，问：应如何调运可使总运输费用最物品的运费如下表所示，问：应如何调运可使总运输费用最小？小？B1B2B3产量A1646200A2655300销量150150200本讲稿第三十七页，共一百零二页运输问题的数学模型运输问题的数学模型解：产销平衡问题：总产量解：产销平衡问题：总产量=总销量总销量500 设设 xij 为从产地为从产地Ai运往销地运往销地Bj的运输量，得到下列运输量的运输量，得到下列运输量表：表：B1B2B3产量A1x11x12x13200A2x21x22x23300销量150150200Min C=6x11+4x12+6x13+6x21+5x22+5x23 s.t.x11+x

27、12+x13=200 x21+x22+x23=300 x11+x21=150 x12+x22=150 x13+x23=200 xij 0 (i=1、2；j=1、2、3）本讲稿第三十八页，共一百零二页运输问题的数学模型运输问题的数学模型运输问题的一般形式：产销平衡运输问题的一般形式：产销平衡A1、A2、Am 表示某物资的表示某物资的m个产地；个产地；B1、B2、Bn 表示某物质的表示某物质的n个销地；个销地；ai 表示产地表示产地Ai的产量；的产量；bj 表示销地表示销地Bj 的销量；的销量；cij 表示把物资从产表示把物资从产地地Ai运往销地运往销地Bj的单位运价。设的单位运价。设 xij 为

28、从产地为从产地Ai运往销地运往销地Bj的运输量，得到下的运输量，得到下列一般运输量问题的模型：列一般运输量问题的模型：本讲稿第三十九页，共一百零二页运输问题的数学模型运输问题的数学模型变化：变化：1）有时目标函数为求最大值。如求利润最大或营业额最大；）有时目标函数为求最大值。如求利润最大或营业额最大；2）当某些运输线路上的能力有限制时，在模型中直接加入约）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束束条件（等式或不等式约束)；3）产销不平衡时，可加入假想的产地（销大于产时）或销）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。地（产大于销时）。本

29、讲稿第四十页，共一百零二页运输问题的应用运输问题的应用2.2.产销不平衡的运输问题产销不平衡的运输问题产销不平衡的运输问题产销不平衡的运输问题3.当总产量与总销量不相等时当总产量与总销量不相等时,称为不平衡运输问题称为不平衡运输问题.这这类运输问题在实际中常常碰到类运输问题在实际中常常碰到,它的求解方法是将不平衡问它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。题化为平衡问题再按平衡问题求解。当产大于销时，即：当产大于销时，即：数学模型为：数学模型为：本讲稿第四十一页，共一百零二页运输问题的应用运输问题的应用由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，由于总产

30、量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，假设该仓库为一个虚拟销地即每个产地设一个仓库，假设该仓库为一个虚拟销地Bn+1，bn+1作为一个虚设作为一个虚设销地销地Bn+1的销量的销量(即库存量即库存量)。各产地。各产地Ai到到Bn+1的运价为零，即的运价为零，即Ci,n+1=0,（i=1，m）。则平衡问题的数学模型为：）。则平衡问题的数学模型为：本讲稿第四十二页，共一百零二页运输问题的应用运输问题的应用 当销大于产时，即：当销大于产时，即：数学模型为：数学模型为：由于总销量大于总产由于总销量大于总产量量,故一定有些需求地故一定有些需求地不完全满足不完全

31、满足,这时虚设这时虚设一个产地一个产地Am+1，产量为：，产量为：本讲稿第四十三页，共一百零二页运输问题的应用运输问题的应用销大于产化为平衡问题的数学模型为销大于产化为平衡问题的数学模型为：具体计算时，在运价表的下方增加一行具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为，运价为零。产量为am+1即即可。可。本讲稿第四十四页，共一百零二页Chapter3 整数规划整数规划(Integer Programming)(Integer Programming)整数规划的特点及应用整数规划的特点及应用指配问题与匈牙利法指配问题与匈牙利法本章主要内容：本章主要内容：本章主要内容：本章主要内容

32、：本讲稿第四十五页，共一百零二页引言引言 整数规划是规划论中近几十年才发展起来的一个重整数规划是规划论中近几十年才发展起来的一个重要分支，主要是由于经济管理中的大量问题在抽象成要分支，主要是由于经济管理中的大量问题在抽象成模型时，人们发现许多量具有不可分割性，因此当它模型时，人们发现许多量具有不可分割性，因此当它们被作为变量引入到规划中时，常要求满足取整条件们被作为变量引入到规划中时，常要求满足取整条件.如生产计划中，生产机器多少台如生产计划中，生产机器多少台(整数整数)；人力资源管；人力资源管理中，招聘员工多少人理中，招聘员工多少人(整数整数)；运输问题中，从一个；运输问题中，从一个港口到另

33、一个港口的集装箱调运数量港口到另一个港口的集装箱调运数量(整数整数)；另外，；另外，运作管理中的决策问题：如工厂选址、人员的工作指运作管理中的决策问题：如工厂选址、人员的工作指派、设备购置和配置等派、设备购置和配置等.本讲稿第四十六页，共一百零二页一辆车最大装载重量为7吨，容量为12立方米。现有两种物品，每种物品数量无限。各种物品每件的体积、重量、价格如下表：物品1物品2体积（立方米/件）34重量（吨/件）42价值（万元/件）43求这辆车中装入每种物品各多少件，使物品总价值最高。背包问题背包问题本讲稿第四十七页，共一百零二页设三种物品的件数各为设三种物品的件数各为x1，x2件，总价值为件，总价

34、值为z max z=4x1+3x2 s.t.3x1+4x212 4x1+2x2 7 x1，x20，x1，x2为整数为整数本讲稿第四十八页，共一百零二页整数规划的特点及应用整数规划的特点及应用整数规划（简称：整数规划（简称：整数规划（简称：整数规划（简称：IPIP）要求一部分或全部决策变量取整数值的规划问题称为要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若该松弛构成的规划问题称为该整数规划问题的松弛问题。若该松弛问题是一个线性规划，则称该整数规划为

35、整数线性规划。问题是一个线性规划，则称该整数规划为整数线性规划。整数线性规划数学模型的一般形式：整数线性规划数学模型的一般形式：本讲稿第四十九页，共一百零二页整数规划的特点及应用整数规划的特点及应用整数规划问题的种类：整数规划问题的种类：整数规划问题的种类：整数规划问题的种类：纯整数规划：指全部决策变量都必须取整数值的整数规划。纯整数规划：指全部决策变量都必须取整数值的整数规划。混合整数规划：决策变量中有一部分必须取整数值，另一部分可混合整数规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数规划。以不取整数值的整数规划。0-1型整数规划：决策变量只能取值型整数规划：决策变量只能

36、取值0或或1的整数规划。的整数规划。本讲稿第五十页，共一百零二页整数规划的特点及应用整数规划的特点及应用整数规划问题解的特征：整数规划问题解的特征：整数规划问题解的特征：整数规划问题解的特征：整数规划问题的可行解集合是它松弛问题可行解集合的一个子集，整数规划问题的可行解集合是它松弛问题可行解集合的一个子集，任意两个可行解的凸组合不一定满足整数约束条件，因而不一定仍任意两个可行解的凸组合不一定满足整数约束条件，因而不一定仍为可行解。为可行解。整数规划问题的可行解一定是它的松弛问题的可行解（反之不整数规划问题的可行解一定是它的松弛问题的可行解（反之不一定），但其最优解的目标函数值不会优于后者最优解

37、的目标函一定），但其最优解的目标函数值不会优于后者最优解的目标函数值。数值。本讲稿第五十一页，共一百零二页0-1整数规划整数规划 0-1整数规划是整数规划中的特殊情形，它的变量仅整数规划是整数规划中的特殊情形，它的变量仅取值取值0或者或者1，我们通常称为，我们通常称为0-1变量或逻辑变量变量或逻辑变量.在实践中，在实践中，许多问题只回答是或否许多问题只回答是或否.例如，对某个项目是否投资，对例如，对某个项目是否投资，对某个应聘者是否聘用，对某种新产品是否研发等，这类问某个应聘者是否聘用，对某种新产品是否研发等，这类问题都可以用题都可以用0-1变量来描绘变量来描绘.本讲稿第五十二页，共一百零二页

38、整数规划的特点及应用整数规划的特点及应用整数规划问题的求解方法：整数规划问题的求解方法：分支定界法和割平面法分支定界法和割平面法 匈牙利法（指派问题）匈牙利法（指派问题）求解整数规划模型的数学软件有：求解整数规划模型的数学软件有：Lindo,Lingo和和Matlab,其中其中Lindo和和Lingo是专业的优化软件是专业的优化软件.本讲稿第五十三页，共一百零二页指派问题指派问题 Assignment Problem 在生活中经常遇到这样的问题，某单位需完成在生活中经常遇到这样的问题，某单位需完成n项任务，项任务，恰好有恰好有n个人可以承担这些任务个人可以承担这些任务.一项任务只能由一个人完成

39、，一项任务只能由一个人完成，一个人只能完成一项任务。一个人只能完成一项任务。由于每人的专长不同，每个人完由于每人的专长不同，每个人完成各项任务的效率不同成各项任务的效率不同.于是产生应指派哪个人去完成哪项于是产生应指派哪个人去完成哪项任务，使完成任务，使完成n项任务的总效率最高项任务的总效率最高(或所需总时间最小，费或所需总时间最小，费用最低）。用最低）。本讲稿第五十四页，共一百零二页指派问题指派问题指派问题的数学模型的标准形式：指派问题的数学模型的标准形式：指派问题的数学模型的标准形式：指派问题的数学模型的标准形式：设设n 个人被分配去做个人被分配去做n 件工作，规定每个人只做一件工作，件工

40、作，规定每个人只做一件工作，每件工作只有一个人去做。已知第每件工作只有一个人去做。已知第i个人去做第个人去做第j 件工作的件工作的 时间或时间或费用为费用为Cij(i=1.2n;j=1.2n)并假设并假设Cij 0。问应如何分配才能使总。问应如何分配才能使总效率最高？效率最高？设决策变量设决策变量 本讲稿第五十五页，共一百零二页指派问题的数学模型为：指派问题的数学模型为：本讲稿第五十六页，共一百零二页整数规划的特点及应用整数规划的特点及应用例例2 2 指派问题：人事部门欲安排四人到四个不同岗位工作，指派问题：人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分

41、制）每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表所示，如何安排他们的工作使总成绩最好。如表所示，如何安排他们的工作使总成绩最好。工作人员ABCD甲85927390乙95877895丙82837990丁86908088本讲稿第五十七页，共一百零二页整数规划的特点及应用整数规划的特点及应用设设 数学模型如下：数学模型如下：要求每人做一项工作，约束条件为：要求每人做一项工作，约束条件为：本讲稿第五十八页，共一百零二页整数规划的特点及应用整数规划的特点及应用每项工作只能安排一人，约束条件为：每项工作只能安排一人，约束条件为：变量约束：变量约束：对于指派问题等对于指派问题等 0-1 整数规划

42、问题，可以直接利用整数规划问题，可以直接利用Matlab 的函的函数数bintprog 进行求解。进行求解。本讲稿第五十九页，共一百零二页多目标规划模型多目标规划模型 在许多实际问题中，衡量一个方案的好坏标准往往不止一个，例如设计一个导弹，既要射程最远，又要燃料最省，还要精度最高.这一类问题统称为多目标最优化问题或多目标规划问题.我们先来看一个生产计划的例子.本讲稿第六十页，共一百零二页本讲稿第六十一页，共一百零二页本讲稿第六十二页，共一百零二页本讲稿第六十三页，共一百零二页本讲稿第六十四页，共一百零二页本讲稿第六十五页，共一百零二页本讲稿第六十六页，共一百零二页本讲稿第六十七页，共一百零二页

43、本讲稿第六十八页，共一百零二页本讲稿第六十九页，共一百零二页Chapter4 图与网络分析图与网络分析(Graph Theory and Network Analysis)(Graph Theory and Network Analysis)图的基本概念与模型图的基本概念与模型树与图的最小树树与图的最小树最短路问题最短路问题网络的最大流网络的最大流本章主要内容：本章主要内容：本章主要内容：本章主要内容：本讲稿第七十页，共一百零二页近代图论的历史可追溯到近代图论的历史可追溯到18世纪的七桥问题世纪的七桥问题穿过穿过Knigsberg城城的七座桥，要求每座桥通过一次且仅通过一次。的七座桥，要求每座

44、桥通过一次且仅通过一次。这就是著名的这就是著名的“哥尼斯堡哥尼斯堡 7 桥桥”难题。难题。Euler1736年证明了不可能存在这样的路线。年证明了不可能存在这样的路线。图的基本概念与模型图的基本概念与模型KnigsbergKnigsberg桥对应的图桥对应的图本讲稿第七十一页，共一百零二页图的基本概念与模型图的基本概念与模型图论中图是由点和边构成，可以反映一些对象之间的关系。图论中图是由点和边构成，可以反映一些对象之间的关系。一般情况下图中点的相对位置如何、点与点之间联线的长短一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。曲直，对于反映对象之间的

45、关系并不是重要的。图的定义：图的定义：图的定义：图的定义：若用点表示研究的对象，用边表示这些对象之间的联系，则图若用点表示研究的对象，用边表示这些对象之间的联系，则图G可可以定义为点和边的集合，记作：以定义为点和边的集合，记作：其中其中:V点集点集 E边集边集 图图G区别于几何学中的图。这里只关心图中有多少个点以及哪些区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。点之间有连线。本讲稿第七十二页，共一百零二页图的基本概念与模型图的基本概念与模型(v1)赵赵(v2)钱钱孙孙(v3)李李(v4)周周(v5)吴吴(v6)陈陈(v7)e2e1e3e4e5(v1)赵赵(v2)钱钱(v3

46、)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈e2e1e3e4e5可见图论中的图与几何图、工程图是不一样的。可见图论中的图与几何图、工程图是不一样的。例如：在一个人群中，对相互认识这个关系我们可以用图来表示。例如：在一个人群中，对相互认识这个关系我们可以用图来表示。本讲稿第七十三页，共一百零二页图的基本概念与模型图的基本概念与模型定义定义:图中的点用图中的点用v表示，边用表示，边用e表示。对每条边可用它所连表示。对每条边可用它所连接的点表示，记作：接的点表示，记作：e1=v1,v1;e2=v1,v2;v3e7e4e8e5e6e1e2e3v1v2v4v5 端点端点,关联边关联边,相邻相邻

47、若有边若有边e可表示为可表示为e=vi,vj，称，称vi和和vj是边是边e的的端点端点，反之称边，反之称边e为点为点vi或或vj的的关联边关联边。若点若点vi、vj与同一条边关联，称点与同一条边关联，称点vi和和vj相邻；若边相邻；若边ei和和ej具有公共的端点，具有公共的端点，称边称边ei和和ej相邻相邻。本讲稿第七十四页，共一百零二页图的基本概念与模型图的基本概念与模型 环环,多重边多重边,简单图简单图如果边如果边e的两个端点相重，称该边为的两个端点相重，称该边为环环。如。如右图中边右图中边e1为环。如果两个点之间多于一条，为环。如果两个点之间多于一条，称为称为多重边多重边，如右图中的，如

48、右图中的e4和和e5，对无环、，对无环、无多重边的图称作无多重边的图称作简单图简单图。v3e7e4e8e5e6e1e2e3v1v2v4v5本讲稿第七十五页，共一百零二页图的基本概念与模型图的基本概念与模型 次，奇点，偶点，孤立点次，奇点，偶点，孤立点与某一个点与某一个点vi相关联的边的数目称为点相关联的边的数目称为点vi的的次次（也叫做度），记作（也叫做度），记作d(vi)。右图中。右图中d(v1),d(v3)=5,d(v5)=1。次为奇数的点。次为奇数的点称作称作奇点奇点，次为偶数的点称作，次为偶数的点称作偶点偶点，次，次为为1的点称为的点称为悬挂点悬挂点，次为，次为0的点称作的点称作孤孤立

49、点立点。v3e7e4e8e5e6e1e2e3v1v2v4v5图的次图的次:一个图的次等于各点的次之和。一个图的次等于各点的次之和。本讲稿第七十六页，共一百零二页图的基本概念与模型图的基本概念与模型 链，圈，连通图链，圈，连通图图中某些点和边的交替序列，若其中图中某些点和边的交替序列，若其中各边互不相同，且对任意各边互不相同，且对任意vi,t-1和和vit均均相邻称为相邻称为链链。用。用 表示：表示：v3e7e4e8e5e6e1e2e3v1v2v4v5起点与终点重合的链称作起点与终点重合的链称作圈圈。如果每。如果每一对顶点之间至少存在一条链，称一对顶点之间至少存在一条链，称这样的图为这样的图为连

50、通图连通图，否则称图不连，否则称图不连通。通。本讲稿第七十七页，共一百零二页图的基本概念与模型图的基本概念与模型 二部图（偶图）二部图（偶图）图图G=(V,E)的点集的点集V可以分为两各非空子集可以分为两各非空子集X，Y，集，集XY=V,XY=,使得同一集合中任意两个顶点均不相邻，称使得同一集合中任意两个顶点均不相邻，称这样的图为偶图。这样的图为偶图。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明显为二部图，明显为二部图，(b)也是二部图，但不明显，改画为也是二部图，但不明显，改画为(c)时可以清时可以清楚看出。楚看出。本讲稿第七十八页，共一百零二页图的基本