Page1赛题发展的特点： 1.对选手的计算机能力提出了更高的要求对选手的计算机能力提出了更高的要求：赛题的解决依赖计算机，题目的数据较多，手工计算赛题的解决依赖计算机，题目的数据较多，手工计算不能完成不能完成;某些问题需要使用计算机软件，如某些问题需要使用计算机软件，如01A;问题的数据读问题的数据读取需要计算机技术，如取需要计算机技术，如04A（数据库数据，数据库方（数据库数据，数据库方法，统计软件包）。法，统计软件包）。计算机模拟和以算法形式给出最终结果计算机模拟和以算法形式给出最终结果,如如09B，11B。 2.赛题的开放性增大赛题的开放性增大:题意的开放性，思路的开放性，题意的开放性，思路的开放性，方法的开放性，结果的开放性。方法的开放性，结果的开放性。开放性还表现在对模开放性还表现在对模型假设和对数据处理上。如型假设和对数据处理上。如10BPage22008年年B题题高等教育学费标准探讨高等教育学费标准探讨请你们根据中国国情，收集诸如国家生均拨款、培养费用、请你们根据中国国情，收集诸如国家生均拨款、培养费用、家庭收入等相关数据，并据此通过数学建模的方法，就几类家庭收入等相关数据，并据此通过数学建模的方法，就几类学校或专业的学费标准进行定量分析，得出明确、有说服力学校或专业的学费标准进行定量分析，得出明确、有说服力的结论。数据的收集和分析是你们建模分析的基础和重要组的结论。数据的收集和分析是你们建模分析的基础和重要组成部分。你们的论文必须观点鲜明、分析有据、结论明确。成部分。你们的论文必须观点鲜明、分析有据、结论明确。最后，根据你们建模分析的结果，给有关部门写一份报告，最后，根据你们建模分析的结果，给有关部门写一份报告，提出具体建议。提出具体建议。Page33.试题向大规模数据处理方向发展试题向大规模数据处理方向发展:从从05年开始，基本上每年都有一大数据量的赛题；数年开始，基本上每年都有一大数据量的赛题；数据结构的复杂性：数据的真实性，数据的海量性，数据结构的复杂性：数据的真实性，数据的海量性，数据的不完备性，数据的冗余性据的不完备性，数据的冗余性4.求解算法和各类现代算法的融合求解算法和各类现代算法的融合；如：；如：11B 5.实用性实用性：问题和数据来自于实际，解决方法切合于问题和数据来自于实际，解决方法切合于实际，模型和结果可以应用于实际。实际，模型和结果可以应用于实际。6.即时性：即时性：国内外的大事，社会的热点，生活的焦点，国内外的大事，社会的热点，生活的焦点，近期发生和即将发生被关注的问题。近期发生和即将发生被关注的问题。Page4拿到赛题后大家需要思考的问题 题目属于哪种类型：连续的、离散的需要解决什么问题:最优化方案、预测模型、最短路径等等；将问题分解。可以用哪些相关模型、算法求解、需 要什么数学工具。 Page51、数学建模的过程、数学建模的过程(2)整个数学建模过程应当由三个阶段：整个数学建模过程应当由三个阶段： 1.建立模型：实际问题建立模型：实际问题数学问题；数学问题； 2.数学解答：数学问题数学解答：数学问题数学解；数学解； 3.模型检验：数学解模型检验：数学解实际问题的解决。实际问题的解决。(1)流程图流程图模型应用模型应用问题分析问题分析模型假设模型假设建立模型建立模型模型求解模型求解模型分析模型分析模型检验模型检验Page6 解决问题涉及到的计算软件分析解决问题涉及到的计算软件分析 重要的是参赛选手具备编程计算、计算机仿真、重要的是参赛选手具备编程计算、计算机仿真、模拟能力。模拟能力。赛题常用的计算软件：赛题常用的计算软件：MatlabMatlab, SPSS, SPSS， EXCEL等等Page7参考网站1全国大学生数学建模竞赛网：全国大学生数学建模竞赛网：http:/www.mcm.edu.cn2数学中国网站数学中国网站http:/www.madio.net3中国数学建模网站：中国数学建模网站：http:/www.shumo.comPage8从问题的解决方法上分析从问题的解决方法上分析涉及到的涉及到的数学建模方法数学建模方法：几何理论、组合概率、统计几何理论、组合概率、统计(回归回归)分析分析;优化方法（规划）、图论与网络优化、层次优化方法（规划）、图论与网络优化、层次分析分析;差分方法、微分方程、模糊数学、随机决差分方法、微分方程、模糊数学、随机决策、多目标决策策、多目标决策;插值与拟合、灰色系统理论、神经网络、时插值与拟合、灰色系统理论、神经网络、时间序列间序列;综合评价、机理分析等方法综合评价、机理分析等方法;Page9用的最多的方法是用的最多的方法是优化方法和概率统计优化方法和概率统计用用到到优优化化方方法法的的共共有有26个个题题，其其中中整整数数规规划划4个个，线线性性规规划划7个个，非非线线性性规规划划14个个,多多目目标标规规划划6个个。用到用到概率统计概率统计方法的有方法的有21个题，平均每年至个题，平均每年至少有一个题目用到概率统计的方法。少有一个题目用到概率统计的方法。用到用到图论与网络优化图论与网络优化方法的问题有方法的问题有6个；个；用到用到层次分析层次分析方法的问题有个；方法的问题有个；Page10用到插值拟合的问题有用到插值拟合的问题有6个；个；用灰色系统理论的用灰色系统理论的4个个;用到时间序列分析的至少用到时间序列分析的至少2个个;用到综合评价方法的至少用到综合评价方法的至少3个；个；大部分题目都可以用两种以上的方法来解决大部分题目都可以用两种以上的方法来解决,即综合性较强的题目有即综合性较强的题目有26个个Page11最优化概论最优化概论从数学意义上说，最优化方法是一种求极值的方法，即在一组约束为等式或不等式的条件下，使系统的目标函数达到极值，即最大值或最小值。从经济意义上说，是在一定的人力、物力和财力资源条件下，使经济效果达到最大（如产值、利润），或者在完成规定的生产或经济任务下，使投入的人力、物力和财力等资源为最少。Page12一、最优化概念一、最优化概念所有类似的这种课题统称为最优化问题，研究解决这些问题的科学一般就总称之为最优化理论和方法另外也可用学术味更浓的名称：“运筹学”。由于最优化问题背景十分广泛，涉及的知识不尽相同，学科分枝很多，因此这个学科名下到底包含哪些分枝，其说法也不一致。比较公认的是：“规划论”（包括线性和非线性规划、整数规划、动态规划、多目标规划和随机规划等），“组合最优化”，“对策论”及“最优控制”等等。 Page13数学建模竞赛中的优化问题数学建模竞赛中的优化问题2000B 钢管订购和运输问题 组合优化2001B 公交车优化调度图论2002B 彩票中的数学 决策分析2003B 露天矿生产的车辆安排问题 离散优化2004A 奥运会临时超市网点设计问题 图论2005B DVD在线租赁 离散优化2006A 出版社的资源配置问题 决策分析Page1407B 乘公交，看奥运 图论 整数规划08B 高等教育学费探讨 层次分析法 多目标优化09B 眼科病床的合理安排动态规划10B 上海世博会经济影响力定量评估 决策分析11B 交巡警服务平台的设置与调度图论 多目标规划12B 太阳能小屋的设计 离散优化13A 车道被占用对城市道路通行能力的影响 离散优化Page15从数学上来看，所谓最优化问题可以概括为这样一种数学模型：给定一个“函数”，F(X)，以及“自变量”X应满足的一定条件，求X为怎样的值时，F(X)取得其最大值或最小值。通常，称F(X)为“目标函数”，X应满足的条件为“约束条件”。约束条件一般用一个集合D表示为：XD。求目标函数F(X)在约束条件XD下的最小值或最大值问题，就是一般最优问题的数学模型Page16无无约束最优化问题约束最优化问题目标函数目标函数 二、最优化问题的一般形式二、最优化问题的一般形式约束最优化问题约束最优化问题约束函数约束函数 最优解；最优值最优解；最优值Page17三、最优化问题分类三、最优化问题分类分类分类1 1：无约束最优化无约束最优化 约束最优化约束最优化非线性规划：非线性规划：目标函数与约束函数中至少有一个目标函数与约束函数中至少有一个是变量是变量x x的非线性函数；的非线性函数；线性规划：线性规划：目标函数与约束函数均为线性函数；目标函数与约束函数均为线性函数；分类分类2 2：线性规划线性规划 非线性规划非线性规划Page18三、最优化问题分类三、最优化问题分类 分类分类3 3（根据决策变量、（根据决策变量、目标函数和要求目标函数和要求不同）不同）整数规划整数规划动态规划动态规划网络规划网络规划随机规划随机规划多目标规划多目标规划Page19三、最优化问题分类三、最优化问题分类函数最优化函数最优化组合最优化组合最优化分类分类函数最优化：函数最优化：决策变量是一定区间内的连续变量决策变量是一定区间内的连续变量 组合最优化：组合最优化：决策变量是离散状态，同时可行域是决策变量是离散状态，同时可行域是由有限个点组成的集合由有限个点组成的集合 Page20最优化方法解决问题的步骤最优化方法解决问题的步骤最优化方法解决问题的步骤最优化方法解决问题的步骤（1）确定变量，写出目标函数和有关约束条件，建立数学模型。（2）分析模型，搞清它属于运筹学哪一分枝，选择合适的最优化方法；（3）编程求解；尽量利用现有的数学软件或最优化软件，比如 Matlab，Mathematica， Lindo， Lingo等，来计算。（4）最优解的验证和实施。Chapter1线性规划线性规划(LinearProgramming)LP的数学模型的数学模型LP模型的应用模型的应用本章主要内容：本章主要内容：本章主要内容：本章主要内容：Page22线性规划问题的数学模型线性规划问题的数学模型1.规划问题规划问题生产和经营管理中经常提出如何合理安排，使人力、生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。这就是规划问题。线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：（1 1）当任务或目标确定后，如何统筹兼顾，合理安排，用）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源最少的资源 （如资金、设备、原材料、人工、时间等）去（如资金、设备、原材料、人工、时间等）去完成确定的任务或目标完成确定的任务或目标（2 2）在一定的资源条件限制下，如何组织安排生产获得最）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多好的经济效益（如产品量最多 、利润最大、利润最大. .）Page23线性规划问题的数学模型线性规划问题的数学模型例例1某企业计划生产甲、乙两种产品。这些产品分别某企业计划生产甲、乙两种产品。这些产品分别要在要在A、B、C、D、四种不同的设备上加工。按工艺四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使企如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？业总的利润最大？设设备备产产品品ABCD利润（元）利润（元）甲甲21402乙乙22043有有效效台台时时1281612Page24线性规划问题的数学模型线性规划问题的数学模型解：设解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：分别为甲、乙两种产品的产量，则数学模型为：maxZ=2xmaxZ=2x1 1+3x+3x2 2 xx1 10,x0,x2 200s.t.s.t.2x2x1 1+2x+2x2 21212xx1 1+2x+2x2 2884x4x1 116164x4x2 21212Page25 这这是是一一个个典典型型的的利利润润最最大大化化的的生生产产计计划划问问题题。其其中中，“Max”Max”是是英英文文单单词词“Maximize”Maximize”的的缩缩写写，含含义义为为“最最大大化化”；“s.t.”s.t.”是是“subject subject to”to”的的缩缩写写，表表示示“满满足足于于”。因因此此，上上述述模模型型的的含含义义是是：在在给给定定条条件件限限制制下下，求求使使目目标标函函数数 z 达达到最大的到最大的x1 ,x2 的取值。的取值。Page26线性规划问题的数学模型线性规划问题的数学模型2. 2. 2. 2. 线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成决策变量决策变量决策变量决策变量DecisionvariablesDecisionvariables目标函数目标函数目标函数目标函数ObjectivefunctionObjectivefunction约束条件约束条件约束条件约束条件ConstraintsConstraints其特征是：其特征是：其特征是：其特征是：（1 1 1 1）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的线性线性线性线性函数，函数，函数，函数，通常是求最大值或最小值；通常是求最大值或最小值；通常是求最大值或最小值；通常是求最大值或最小值；（2 2 2 2）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的线性线性线性线性不不不不等式或等式。等式或等式。等式或等式。等式或等式。 怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？ Page27线性规划问题的数学模型线性规划问题的数学模型目标函数：目标函数：目标函数：目标函数：约束条件：约束条件：约束条件：约束条件：3.3.线性规划数学模型的一般形式线性规划数学模型的一般形式线性规划数学模型的一般形式线性规划数学模型的一般形式简写为：简写为：Page28线性规划问题的数学模型线性规划问题的数学模型矩阵形式：矩阵形式：矩阵形式：矩阵形式：其中：其中：Page29线性规划问题的数学模型线性规划问题的数学模型3.线性规划问题的标准形式线性规划问题的标准形式特点：特点：(1)目标函数求最大值。目标函数求最大值。(2)约束条件都为等式方程，且右端常数项约束条件都为等式方程，且右端常数项bi都大于或等于零都大于或等于零(3)决策变量决策变量xj为非负。为非负。Page30线性规划问题的数学模型线性规划问题的数学模型（2 2 2 2）如何化标准形式）如何化标准形式）如何化标准形式）如何化标准形式 目标函数的转换目标函数的转换 如果是求极小值即如果是求极小值即 ，则可将目标函数乘以，则可将目标函数乘以(-1)(-1)，可化为求极大值问题。，可化为求极大值问题。也就是：令也就是：令 ，可得到上式。，可得到上式。即即 若存在取值无约束的变量若存在取值无约束的变量 , ,可令可令 其中：其中： 变量的变换变量的变换Page31线性规划问题的数学模型线性规划问题的数学模型 约束方程的转换：由不等式转换为等式。约束方程的转换：由不等式转换为等式。称为松弛变量称为松弛变量称为剩余变量称为剩余变量 变量变量 的变换的变换 可令可令Page32线性规划问题的数学模型线性规划问题的数学模型4. 4. 线性规划问题的解线性规划问题的解线性规划问题线性规划问题求解线性规划问题，就是从满足约束条件求解线性规划问题，就是从满足约束条件(2)、(3)的方程的方程组中找出一个解，使目标函数组中找出一个解，使目标函数(1)达到最大值。达到最大值。Page33线性规划问题的数学模型线性规划问题的数学模型 可行解可行解：满足：满足约束条件约束条件、的解为可行解。所的解为可行解。所有可行解的集合为可行域。有可行解的集合为可行域。 最优解最优解：使目标函数达到最大值的可行解。：使目标函数达到最大值的可行解。 线性规划解的情况：有线性规划解的情况：有唯一最优解；有无穷多最唯一最优解；有无穷多最优解；无界解；无可行解优解；无界解；无可行解Page34 建立线性规划模型的过程可以分为四个步骤：建立线性规划模型的过程可以分为四个步骤：(1)(1)设立决策变量；设立决策变量；(2)(2)明明确确所所有有的的约约束束条条件件并并用用决决策策变变量量的的线线性性等等式式或或不不等式表示出来；等式表示出来；(3)(3)用用决决策策变变量量的的线线性性函函数数表表示示目目标标，并并确确定定是是求求极极大大（MaxMax）还是极小（还是极小（MinMin）；）；(4)(4)根据决策变量的物理性质研究变量是否有非负性。根据决策变量的物理性质研究变量是否有非负性。求解方法：用求解方法：用MATLABMATLAB软件直接求解。软件直接求解。Chapter2运输运输问题问题(TransportationProblem)(TransportationProblem)运输问题的数学模型运输问题的数学模型运输问题的应用运输问题的应用本章主要内容：本章主要内容：本章主要内容：本章主要内容：Page361.运输问题模型及有关概念问题的提出问题的提出 一一般般的的运运输输问问题题就就是是要要解解决决把把某某种种产产品品从从若若干干个个产产地地调调运运到到若若干干个个销销地地，在在每每个个产产地地的的供供应应量量与与每每个个销销地地的的需需求求量量已已知知，并并知知道道各各地地之之间间的的运运输输单单价价的的前前提提下下，如如何何确确定定一一个个使使得得总总的的运运输输费用最小的方案。费用最小的方案。Page37运输问题的数学模型运输问题的数学模型例例2.1某公司从两个产地某公司从两个产地A1、A2将物品运往三个销地将物品运往三个销地B1,B2,B3，各产地的产量、各销地的销量和各产地运往各销地，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？用最小？B1B2B3产量产量A1646200A2655300销量销量150150200Page38运输问题的数学模型运输问题的数学模型解：产销平衡问题：总产量解：产销平衡问题：总产量=总销量总销量500设设xij为从产地为从产地Ai运往销地运往销地Bj的运输量，得到下列运输量的运输量，得到下列运输量表：表：B1B2B3产量产量A1x11x12x13200A2x21x22x23300销量销量150150200MinC=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200 xij0(i=1、2；j=1、2、3）Page39运输问题的数学模型运输问题的数学模型运输问题的一般形式：产销平衡运输问题的一般形式：产销平衡A1、A2、Am表示某物资的表示某物资的m个产地；个产地；B1、B2、Bn表示表示某物质的某物质的n个销地；个销地；ai表示产地表示产地Ai的产量；的产量；bj表示销地表示销地Bj的销量；的销量；cij表示把物资从产地表示把物资从产地Ai运往销地运往销地Bj的单位运价。设的单位运价。设xij为从产地为从产地Ai运往销地运往销地Bj的运输量，得到下列一般运输量问题的模型：的运输量，得到下列一般运输量问题的模型：Page40运输问题的数学模型运输问题的数学模型变化：变化：1）有时目标函数为求最大值。如求利润最大或营业额最）有时目标函数为求最大值。如求利润最大或营业额最大；大；2）当某些运输线路上的能力有限制时，在模型中直接加）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束入约束条件（等式或不等式约束)；3）产销不平衡时，可加入假想的产地（销大于产时）或）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。销地（产大于销时）。Page41运输问题的应用运输问题的应用2. 2. 产销不平衡的运输问题产销不平衡的运输问题产销不平衡的运输问题产销不平衡的运输问题3.当总产量与总销量不相等时当总产量与总销量不相等时,称为不平衡运输问题称为不平衡运输问题.这这类运输问题在实际中常常碰到类运输问题在实际中常常碰到,它的求解方法是将不平衡问它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。题化为平衡问题再按平衡问题求解。当产大于销时，即：当产大于销时，即：数学模型为：数学模型为：Page42运输问题的应用运输问题的应用由于总产量大于总销量，必有部分产地的产量不能全部运送完，由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，必须就地库存，即每个产地设一个仓库，假设该仓库为一个虚拟假设该仓库为一个虚拟销地销地Bn+1，bn+1作为一个虚设销地作为一个虚设销地Bn+1的销量的销量(即库存量即库存量)。各产地。各产地Ai到到Bn+1的运价为零，即的运价为零，即Ci,n+1=0,（i=1，m）。则平衡问题的）。则平衡问题的数学模型为：数学模型为：Page43运输问题的应用运输问题的应用当销大于产时，即：当销大于产时，即：数学模型为：数学模型为：由于总销量大于总产由于总销量大于总产量量,故一定有些需求故一定有些需求地不完全满足地不完全满足,这时这时虚设一个产地虚设一个产地Am+1，产量为：产量为：Page44运输问题的应用运输问题的应用销大于产化为平衡问题的数学模型为销大于产化为平衡问题的数学模型为：具体计算时，在运价表的下方增加一行具体计算时，在运价表的下方增加一行Am+1，运价为零。产，运价为零。产量为量为am+1即可。即可。Chapter3整数规划整数规划(IntegerProgramming)(IntegerProgramming)整数规划的特点及应用整数规划的特点及应用指配问题与匈牙利法指配问题与匈牙利法本章主要内容：本章主要内容：本章主要内容：本章主要内容：Page46引言引言 整数规划是规划论中近几十年才发展起来的一个整数规划是规划论中近几十年才发展起来的一个重要分支，主要是由于经济管理中的大量问题在抽重要分支，主要是由于经济管理中的大量问题在抽象成模型时，人们发现许多量具有不可分割性，因象成模型时，人们发现许多量具有不可分割性，因此当它们被作为变量引入到规划中时，常要求满足此当它们被作为变量引入到规划中时，常要求满足取整条件取整条件.如生产计划中，生产机器多少台如生产计划中，生产机器多少台(整数整数)；人力资源管理中，招聘员工多少人；人力资源管理中，招聘员工多少人(整数整数)；运输；运输问题中，从一个港口到另一个港口的集装箱调运数问题中，从一个港口到另一个港口的集装箱调运数量量(整数整数)；另外，运作管理中的决策问题：如工厂；另外，运作管理中的决策问题：如工厂选址、人员的工作指派、设备购置和配置等选址、人员的工作指派、设备购置和配置等.Page47一辆车最大装载重量为7吨，容量为12立方米。现有两种物品，每种物品数量无限。各种物品每件的体积、重量、价格如下表：物品1物品2体积（立方米/件）34重量（吨/件）42价值（万元/件）43求这辆车中装入每种物品各多少件，使物品总价值最高。背包问题背包问题Page48设三种物品的件数各为设三种物品的件数各为x1，x2件，总价值为件，总价值为z max z=4x1+3x2 s.t. 3x1+4x212 4x1+2x2 7 x1，x20 ，x1，x2为整数为整数Page49整数规划的特点及应用整数规划的特点及应用整数规划（简称：整数规划（简称：整数规划（简称：整数规划（简称：IPIP）要求一部分或全部决策变量取整数值的规划问题称为要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若该松弛构成的规划问题称为该整数规划问题的松弛问题。若该松弛问题是一个线性规划，则称该整数规划为整数线性规划。问题是一个线性规划，则称该整数规划为整数线性规划。整数线性规划数学模型的一般形式：整数线性规划数学模型的一般形式：Page50整数规划的特点及应用整数规划的特点及应用整数规划问题的种类：整数规划问题的种类：整数规划问题的种类：整数规划问题的种类：纯整数规划：指全部决策变量都必须取整数值的整数规划。纯整数规划：指全部决策变量都必须取整数值的整数规划。混合整数规划：决策变量中有一部分必须取整数值，另一混合整数规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数规划。部分可以不取整数值的整数规划。0-1型整数规划：决策变量只能取值型整数规划：决策变量只能取值0或或1的整数规划。的整数规划。Page51整数规划的特点及应用整数规划的特点及应用整数规划问题解的特征：整数规划问题解的特征：整数规划问题解的特征：整数规划问题解的特征：整数规划问题的可行解集合是它松弛问题可行解集合的一整数规划问题的可行解集合是它松弛问题可行解集合的一个子集，任意两个可行解的凸组合不一定满足整数约束条件，个子集，任意两个可行解的凸组合不一定满足整数约束条件，因而不一定仍为可行解。因而不一定仍为可行解。整数规划问题的可行解一定是它的松弛问题的可行解（反整数规划问题的可行解一定是它的松弛问题的可行解（反之不一定），但其最优解的目标函数值不会优于后者最优解之不一定），但其最优解的目标函数值不会优于后者最优解的目标函数值。的目标函数值。Page520-1整数规划整数规划 0-1整数规划是整数规划中的特殊情形，它的变量整数规划是整数规划中的特殊情形，它的变量仅取值仅取值0或者或者1，我们通常称为，我们通常称为0-1变量或逻辑变量变量或逻辑变量.在实在实践中，许多问题只回答是或否践中，许多问题只回答是或否.例如，对某个项目是否例如，对某个项目是否投资，对某个应聘者是否聘用，对某种新产品是否研发投资，对某个应聘者是否聘用，对某种新产品是否研发等，这类问题都可以用等，这类问题都可以用0-1变量来描绘变量来描绘.Page53整数规划的特点及应用整数规划的特点及应用整数规划问题的求解方法：整数规划问题的求解方法：分支定界法和割平面法分支定界法和割平面法匈牙利法（指派问题）匈牙利法（指派问题）求解整数规划模型的数学软件有：求解整数规划模型的数学软件有：Lindo,Lingo和和Matlab,其中其中Lindo和和Lingo是专业的优化软件是专业的优化软件.Page54指派问题指派问题AssignmentProblem 在生活中经常遇到这样的问题，某单位需完成在生活中经常遇到这样的问题，某单位需完成n项项任务，恰好有任务，恰好有n个人可以承担这些任务个人可以承担这些任务.一项任务只能由一项任务只能由一个人完成，一个人只能完成一项任务。一个人完成，一个人只能完成一项任务。由于每人的由于每人的专长不同，每个人完成各项任务的效率不同专长不同，每个人完成各项任务的效率不同.于是产生于是产生应指派哪个人去完成哪项任务，使完成应指派哪个人去完成哪项任务，使完成n项任务的总效项任务的总效率最高率最高(或所需总时间最小，费用最低）。或所需总时间最小，费用最低）。Page55指派问题指派问题指派问题的数学模型的标准形式：指派问题的数学模型的标准形式：指派问题的数学模型的标准形式：指派问题的数学模型的标准形式：设设n个人被分配去做个人被分配去做n件工作，规定每个人只做一件工作，件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第每件工作只有一个人去做。已知第i个人去做第个人去做第j件工作的件工作的时时间或费用为间或费用为Cij(i=1.2n;j=1.2n)并假设并假设Cij0。问应如何分。问应如何分配才能使总效率最高？配才能使总效率最高？设决策变量设决策变量Page56指派问题的数学模型为：指派问题的数学模型为：Page57整数规划的特点及应用整数规划的特点及应用例例2 2 指派问题：人事部门欲安排四人到四个不同岗位工作，指派问题：人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表所示，如何安排他们的工作使总成绩最好。如表所示，如何安排他们的工作使总成绩最好。工作工作人员人员ABCD甲甲85927390乙乙95877895丙丙82837990丁丁86908088Page58整数规划的特点及应用整数规划的特点及应用设设 数学模型如下：数学模型如下：要求每人做一项工作，约束条件为：要求每人做一项工作，约束条件为：Page59整数规划的特点及应用整数规划的特点及应用每项工作只能安排一人，约束条件为：每项工作只能安排一人，约束条件为：变量约束：变量约束：对于指派问题等对于指派问题等0-1整数规划问题，可以直接利用整数规划问题，可以直接利用Matlab的函数的函数bintprog进行求解。进行求解。Page60多目标规划模型多目标规划模型在许多实际问题中，衡量一个方案的好坏标准往往不止一个，例如设计一个导弹，既要射程最远，又要燃料最省，还要精度最高. 这一类问题统称为多目标最优化问题或多目标规划问题. 我们先来看一个生产计划的例子.Page61Page62Page63Page64Page65Page66Page67Page68Page69Chapter4图与网络分析图与网络分析(GraphTheoryandNetworkAnalysis)(GraphTheoryandNetworkAnalysis)图的基本概念与模型图的基本概念与模型树与图的最小树树与图的最小树最短路问题最短路问题网络的最大流网络的最大流本章主要内容：本章主要内容：本章主要内容：本章主要内容：Page71近代图论的历史可追溯到近代图论的历史可追溯到18世纪的七桥问题世纪的七桥问题穿过穿过Knigsberg城的七座桥，要求每座桥通过一次且仅通过一次。城的七座桥，要求每座桥通过一次且仅通过一次。这就是著名的这就是著名的“哥尼斯堡哥尼斯堡7桥桥”难题。难题。Euler1736年证明了不年证明了不可能存在这样的路线。可能存在这样的路线。图的基本概念与模型图的基本概念与模型KnigsbergKnigsberg桥对应的图桥对应的图Page72图的基本概念与模型图的基本概念与模型图论中图是由点和边构成，可以反映一些对象之间的关系。图论中图是由点和边构成，可以反映一些对象之间的关系。一般情况下图中点的相对位置如何、点与点之间联线的长短一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。曲直，对于反映对象之间的关系并不是重要的。图的定义：图的定义：图的定义：图的定义：若用点表示研究的对象，用边表示这些对象之间的联系，若用点表示研究的对象，用边表示这些对象之间的联系，则图则图G可以定义为点和边的集合，记作：可以定义为点和边的集合，记作：其中其中:V点集点集E边集边集图图G区别于几何学中的图。这里只关心图中有多少个点以区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。及哪些点之间有连线。Page73图的基本概念与模型图的基本概念与模型(v1)赵赵(v2)钱钱孙孙(v3) 李李(v4)周周(v5)吴吴(v6)陈陈(v7)e2e1e3e4e5(v1)赵赵(v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈e2e1e3e4e5可见图论中的图与几何图、工程图是不一样的。可见图论中的图与几何图、工程图是不一样的。例如：在一个人群中，对相互认识这个关系我们可以用图来例如：在一个人群中，对相互认识这个关系我们可以用图来表示。表示。Page74图的基本概念与模型图的基本概念与模型定义定义:图中的点用图中的点用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相邻相邻。Page75图的基本概念与模型图的基本概念与模型环环,多重边多重边,简单图简单图如果边如果边e的两个端点相重，称该边为的两个端点相重，称该边为环环。如右图中边。如右图中边e1为环。如果两个点为环。如果两个点之间多于一条，称为之间多于一条，称为多重边多重边，如右图，如右图中的中的e4和和e5，对无环、无多重边的图，对无环、无多重边的图称作称作简单图简单图。v3e7e4e8e5e6e1e2e3v1v2v4v5Page76图的基本概念与模型图的基本概念与模型次，奇点，偶点，孤立点次，奇点，偶点，孤立点与某一个点与某一个点vi相关联的边的数目称为相关联的边的数目称为点点vi的的次次（也叫做度），记作（也叫做度），记作d(vi)。右图中右图中d(v1),d(v3)=5,d(v5)=1。次为奇数的点称作次为奇数的点称作奇点奇点，次为偶数，次为偶数的点称作的点称作偶点偶点，次为，次为1的点称为的点称为悬挂悬挂点点，次为，次为0的点称作的点称作孤立点孤立点。v3e7e4e8e5e6e1e2e3v1v2v4v5图的次图的次:一个图的次等于各点的次之和。一个图的次等于各点的次之和。Page77图的基本概念与模型图的基本概念与模型链，圈，连通图链，圈，连通图图中某些点和边的交替序列，若其图中某些点和边的交替序列，若其中各边互不相同，且对任意中各边互不相同，且对任意vi,t-1和和vit均相邻称为均相邻称为链链。用。用表示：表示：v3e7e4e8e5e6e1e2e3v1v2v4v5起点与终点重合的链称作起点与终点重合的链称作圈圈。如。如果每一对顶点之间至少存在一条果每一对顶点之间至少存在一条链，称这样的图为链，称这样的图为连通图连通图，否则，否则称图不连通。称图不连通。Page78图的基本概念与模型图的基本概念与模型二部图（偶图）二部图（偶图）图图G=(V,E)的点集的点集V可以分为两各非空子集可以分为两各非空子集X，Y，集，集XY=V,XY=,使得同一集合中任意两个顶点均不使得同一集合中任意两个顶点均不相邻，称这样的图为偶图。相邻，称这样的图为偶图。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明显为二部图，明显为二部图，(b)也是二部图，但不明显，改画为也是二部图，但不明显，改画为(c)时可以清楚看出。时可以清楚看出。Page79图的基本概念与模型图的基本概念与模型子图，部分图子图，部分图(支撑子图支撑子图)图图G1=V1、E1和图和图G2=V2，E2如果有如果有称称G1是是G2的一个的一个子图子图。若有若有，则称，则称G1是是G2的的一个一个部分图部分图(支撑子图支撑子图)。v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)（G图）图）Page80图的基本概念与模型图的基本概念与模型网络（赋权图）网络（赋权图）设图设图G（V，E），对），对G的每一条边的每一条边(vi,vj)相应赋予数量指标相应赋予数量指标wij，wij称为边称为边(vi,vj)的的权权,赋予权的图赋予权的图G称为网络称为网络(或或赋权图）赋权图）。权可以代表距离、费用、通过能力权可以代表距离、费用、通过能力(容量容量)等等。等等。端点无序的赋权图称为端点无序的赋权图称为无向网络无向网络，端点有序的赋权图称为，端点有序的赋权图称为有有向网络。向网络。910201571419256Page81图的基本概念与模型图的基本概念与模型出次与入次出次与入次有有向向图图中中，以以vi为为始始点点的的边边数数称称为为点点vi的的出出次次，用用d+(vi)表表示示；以以vi为为终终点点的的边边数数称称为为点点vi 的的入入次次，用用表表示示d-(vi)；vi 点点的出次和入次之和就是该点的次。的出次和入次之和就是该点的次。有向图中，所有顶点的入次之和等于所有顶点的出次之有向图中，所有顶点的入次之和等于所有顶点的出次之和。和。Page82图的基本概念与模型图的基本概念与模型图的模型应用图的模型应用图的模型应用图的模型应用例例6.1有甲有甲,乙乙,丙丙,丁丁,戊戊,己己6名运动员报名参加名运动员报名参加A,B,C,D,E,F6个项目的比赛。下表中打个项目的比赛。下表中打的是各运动员报告参加的比赛项的是各运动员报告参加的比赛项目。问目。问6个项目的比赛顺序应如何安排，做到每名运动员都个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。不连续地参加两项比赛。ABCDEF甲甲乙乙丙丙丁丁戊戊己己Page83图的基本概念与模型图的基本概念与模型解：用图来建模。把比赛项目作为研究对象，用点表示。如解：用图来建模。把比赛项目作为研究对象，用点表示。如果果2个项目有同一名运动员参加，在代表这两个项目的点之个项目有同一名运动员参加，在代表这两个项目的点之间连一条线，可得下图。间连一条线，可得下图。ABCDEF在图中找到一个点序在图中找到一个点序列，使得依次排列的列，使得依次排列的两点不相邻，即能满两点不相邻，即能满足要求。如：足要求。如：1)A,C,B,F,E,D2)D,E,F,B,C,APage84图的基本概念与模型图的基本概念与模型图的矩阵描述：图的矩阵描述：如何在计算机中存储一个图呢？现在已有很多存储的方法，如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有：也根据所关心的问题不同而有：邻接矩阵、关联矩阵、权矩阵等。邻接矩阵、关联矩阵、权矩阵等。1.邻接矩阵邻接矩阵对于图对于图G=（V，E），），|V|=n，|E|=m，有，有n n阶方阶方矩阵矩阵A=(aij)n n，其中其中Page85图的基本概念与模型图的基本概念与模型v5v1v2v3v4v64332256437例例6.2下图所表示的图可以构造邻接矩阵下图所表示的图可以构造邻接矩阵A如下如下Page86对于赋权图对于赋权图G=(V,E),其中边其中边有权有权,构造矩阵构造矩阵B=(bij)n n其中：其中：图的基本概念与模型图的基本概念与模型2.2.关联矩阵关联矩阵关联矩阵关联矩阵对于图对于图G=(V,E),|V|=n,|E|=m,有有m n阶阶矩阵矩阵M=(mij)m n，其中其中:3.3.权矩阵权矩阵权矩阵权矩阵Page87树与图的最小树树与图的最小树树是图论中结构最简单但又十分重要的图。在自然和社会领树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。域应用极为广泛。例例6.2乒乓求单打比赛抽签后，可用图来表示相遇情况，如乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。下图所示。AB CDEF GH运动员运动员Page88树与图的最小树树与图的最小树例例6.3某企业的组织机构图也可用树图表示。某企业的组织机构图也可用树图表示。厂长厂长人事科人事科财务科财务科总工总工程师程师生产副生产副厂长厂长经营副经营副厂长厂长开发科开发科技术科技术科生产科生产科设备科设备科供应科供应科销售科销售科检验科检验科动力科动力科Page89树与图的最小树树与图的最小树树：无圈的连通图即为树树：无圈的连通图即为树性质性质1：任何树中必存在次为：任何树中必存在次为1的点。的点。性质性质2：n个顶点的树必有个顶点的树必有n-1条边。条边。性质性质3：树中任意两个顶点之间，恰有且仅有一条链。：树中任意两个顶点之间，恰有且仅有一条链。性质性质4：树连通，但去掉任一条边，必变为不连通。：树连通，但去掉任一条边，必变为不连通。性质性质5：树无回圈，但不相邻的两个点之间加一条边，恰：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。得到一个圈。v1v2v3v4v5v6Page90最短路问题最短路问题问题描述：问题描述：就是从给定的网络图中找出一点到各点或任意两点之就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路间距离最短的一条路.有些问题，如选址、管道铺设时的选线、设备更新、有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。短路的问题。因此这类问题在生产实际中得到广泛应用。Page91最短路问题最短路问题求最短路有两种算法求最短路有两种算法:狄克斯屈拉狄克斯屈拉(Dijkstra)标号算法标号算法逐次逼近算法逐次逼近算法Page92最短路问题最短路问题狄克斯屈拉狄克斯屈拉狄克斯屈拉狄克斯屈拉( (DijkstraDijkstra) )标号算法的基本思路：标号算法的基本思路：标号算法的基本思路：标号算法的基本思路：若序列若序列vs,v1.vn-1,vn 是从是从vs到到vt间的最短路，则序列间的最短路，则序列vs,v1.vn-1 必为从必为从vs 到到vn-1的最短路。的最短路。假定假定v1v2v3v4是是v1v4的最短路，则的最短路，则v1v2v3一定是一定是v1v3的最短路，的最短路，v2v3v4也一定是也一定是v2v4的最短路。的最短路。v1v2v3v4v5Page93最短路问题最短路问题求网络图的最短路，设图的起点是求网络图的最短路，设图的起点是vs,终点是终点是vt ,以以vi为起点为起点vj为终点的弧记为为终点的弧记为(i,j) 距离为距离为dijP P标号标号标号标号( (点标号点标号点标号点标号) )：b(j)起点起点vs到点到点vj的最短路长；的最短路长；T 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步。步。Page94最短路问题最短路问题例例6.5求下图求下图v1到到v7的最短路长及最短路线的最短路长及最短路线86252353421057086225441114751071211v7已标号，计算结束。从已标号，计算结束。从v1到到v7的最短路长是的最短路长是11,最短路线：最短路线：v1v4v6v7P标号标号T标号标号Page95网络的最大流网络的最大流基本概念：基本概念：1.1.容量网络：容量网络：容量网络：容量网络：队网络上的每条弧队网络上的每条弧(vi,vj)都给出一个最大的都给出一个最大的通过能力，称为该弧的通过能力，称为该弧的容量容量容量容量，简记为，简记为cij。容量网络中通常规。容量网络中通常规定一个定一个发点发点发点发点(也称源点，记为也称源点，记为s)和一个和一个收点收点收点收点(也称汇点，记为也称汇点，记为t)，网络中其他点称为，网络中其他点称为中间点中间点中间点中间点。st4844122679Page96网络的最大流网络的最大流2.网络的最大流网络的最大流是指网络中从发点到收点之间允许通过的最大流量。是指网络中从发点到收点之间允许通过的最大流量。3.流与可行流流与可行流流流是指加在网络各条弧上的实际流量，对加在弧是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上上的负载量记为的负载量记为fij。若。若fij=0，称为零流。，称为零流。满足以下条件的一组流称为满足以下条件的一组流称为可行流可行流。容量限制条件。容量网络上所有的弧满足：容量限制条件。容量网络上所有的弧满足：0fijcij中间点平衡条件。中间点平衡条件。若以若以v(f)表示网络中从表示网络中从st的流量，则有：的流量，则有：Page97网络的最大流网络的最大流结论：任何网络上一定存在可行流。（零流即是结论：任何网络上一定存在可行流。（零流即是可行流）可行流）网络最大流问题：网络最大流问题：指满足容量限制条件和中间点平衡的条件下，使指满足容量限制条件和中间点平衡的条件下，使v(f)值值达到最大。达到最大。Page98网络的最大流网络的最大流割与割集割与割集割是指容量网络中的发点和收点分割开，并使割是指容量网络中的发点和收点分割开，并使st的流中断的流中断的一组弧的集合。割容量是组成割集合中的各条弧的容量之的一组弧的集合。割容量是组成割集合中的各条弧的容量之和，用和，用表示。表示。如下图中，如下图中，AA将网络上的点分割成将网络上的点分割成两个集合。并有两个集合。并有，称弧的集合，称弧的集合(v1,v3),(v2,v4)是一个割，且是一个割，且的流量为的流量为18。Page99网络的最大流网络的最大流stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(3)7(6)AABBPage100网络的最大流网络的最大流定理定理定理定理1 1设网络设网络N中一个从中一个从s 到到t的流的流f 的流量为的流量为v(f)，(V,V)为任意一个割集，则为任意一个割集，则v(f)=f(V,V) f(V,V)推论推论推论推论1 1对网络对网络N中任意流量中任意流量v(f)和割集和割集(V,V)，有，有v(f) c(V,V)证明证明w=f(V,V) f(V,V) f(V,V) c(V,V)推论推论推论推论2 2最大流量最大流量v(f)不大于最小割集的容量，即：不大于最小割集的容量，即：v(f) minc(V,V)定理定理定理定理2 2在网络中在网络中st的最大流量等于它的最小割集的容量，的最大流量等于它的最小割集的容量，即：即：v(f)=c (V,V)Page101网络的最大流网络的最大流求网络最大流的标号算法：求网络最大流的标号算法： 基本思想基本思想基本思想基本思想由一个流开始，系统地搜寻增广链，然后在此链上增由一个流开始，系统地搜寻增广链，然后在此链上增流，继续这个增流过程，直至不存在增广链。流，继续这个增流过程，直至不存在增广链。 基本方法基本方法基本方法基本方法 (1)找出第一个可行流，（例如所有弧的流量找出第一个可行流，（例如所有弧的流量fij =0。）。）(2)用标号的方法找一条增广链用标号的方法找一条增广链首先给发点首先给发点s标号标号(),标号中的数字表示允许的最大调整标号中的数字表示允许的最大调整量。量。选择一个点选择一个点vi 已标号并且另一端未标号的弧沿着某条链已标号并且另一端未标号的弧沿着某条链向收点检查：向收点检查：Page102网络的最大流网络的最大流如果弧的起点为如果弧的起点为vi，并且有，并且有fij0，则，则vj标号标号(fji)(3)重复第重复第(2)步，可能出现两种结局：步，可能出现两种结局：标号过程中断，标号过程中断，t无法标号，说明网络中不存在增广链，无法标号，说明网络中不存在增广链，目前流量为最大流。同时可以确定最小割集，目前流量为最大流。同时可以确定最小割集，记已标号的点记已标号的点集为集为V,未标号的点集合为未标号的点集合为V,(V,V)为网络的最小割。为网络的最小割。t得到标号，反向追踪在网络中找到一条从得到标号，反向追踪在网络中找到一条从s到到t得由标号得由标号点及相应的弧连接而成的增广链。继续第点及相应的弧连接而成的增广链。继续第(4)步步