运筹学复习PPT课件.ppt

胡胡胡胡晓晓青青青青 1516813820515168138205（658205658205）运运 筹筹 学学（Operations Research）1.Page 2第一章第一章 线性性规划及划及单纯形法形法.Page 3 LP的数学模型的数学模型 图解法解法 单纯形法形法 单纯形法的形法的进一步一步讨论人工人工变量法量法 LP模型的模型的应用用本章主要内容：本章主要内容：本章主要内容：本章主要内容：.Page 4线性性规划划问题的数学模型的数学模型某企某企业计划生划生产甲、乙两种甲、乙两种产品。品。这些些产品分品分别要在要在A、B、C、D、四种不同的、四种不同的设备上加工。按工上加工。按工艺资料料规定，定，单件件产品在不同品在不同设备上加工所需要的台上加工所需要的台时如下如下表所示，企表所示，企业决策者决策者应如何安排生如何安排生产计划，使企划，使企业总的利的利润最大？最大？设 备产 品品 A B C D利利润（元）（元）甲甲 2 1 4 0 2 乙乙 2 2 0 4 3 有有 效效 台台 时 12 8 16 12.Page 5线性性规划划问题的数学模型的数学模型解：解：设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.Page 6例例1.2 营养配餐养配餐问题（成本最低）（成本最低）某某饲料公司希望用玉米、料公司希望用玉米、红薯两种原料配置一种混薯两种原料配置一种混合合饲料。各种原料包含的料。各种原料包含的营养成分和采养成分和采购成本都不成本都不相同，公司管理相同，公司管理层希望能希望能够确定混合确定混合饲料中两种原料中两种原料的数量，使得料的数量，使得饲料能料能够以最低的成本达到一定的以最低的成本达到一定的营养要求。研究者根据养要求。研究者根据这一目一目标收集到的有关数据收集到的有关数据如表所示如表所示营养成分养成分每公斤玉米每公斤玉米每公斤每公斤红薯薯营养要求养要求碳水化合物碳水化合物8420蛋白蛋白质3618维他命他命1516采采购成本成本1.81.6.Page 7问题分析分析决策决策变量：量：混合混合饲料中两种原料的数量，料中两种原料的数量，设采采购玉米玉米 斤，采斤，采购红薯薯 斤斤目目标函数：函数：成本最小，成本最小，则 约束条件：束条件：碳水化合物的碳水化合物的营养要求：养要求：蛋白蛋白质的的营养要求：养要求：维他命的他命的营养要求：养要求：非非负约束：束：.Page 8例例1.3 物流网物流网络配送配送问题（成本最低）（成本最低）某物流公司需将三个工厂（某物流公司需将三个工厂（1、2、3）生）生产的一种新的一种新产品运送到品运送到A、B两个两个仓库，工厂，工厂1和工厂和工厂2的的产品可品可以通以通过铁路运送到路运送到仓库A，数量不限；工厂，数量不限；工厂3的的产品品可以通可以通过铁路运送到路运送到仓库B，同，同样数量不限。由于数量不限。由于铁路运路运输成本成本较高，公司同高，公司同时考考虑用卡用卡车来运送，但来运送，但每个工厂要用卡每个工厂要用卡车先将先将产品运到配送中心（每个工品运到配送中心（每个工厂用卡厂用卡车最多运送最多运送60单位），再从配送中心用卡位），再从配送中心用卡车运到各个运到各个仓库（每个（每个仓库最多收到用卡最多收到用卡车送来的送来的货物物90单位）。公司管理位）。公司管理层希望以最小的成本来运送希望以最小的成本来运送所需的所需的货物。物。8.Page 9配送中心配送中心仓库A仓库B产量量工厂13.07.5100工厂23.58.280工厂33.49.270配送中心2.32.3需求量1201309.Page 10产量量BAT1322.32.33.03.49.23.5606060908.27.5901008070工厂工厂单位运位运输成本成本仓库需求量需求量120130.Page 11问题分析分析决策决策变量：量：各条路各条路线的运的运输量量 表示表示节点点 i 到到节点点 j 的数量的数量BAT132.Page 12目目标函数：函数：总运运输成本最小成本最小 问题分析分析.Page 13约束条件：束条件：问题分析分析 非非负约束：束：.Page 14线性性规划划问题的求解方法的求解方法一一 般般 有有三种方法三种方法图 解解 法法单纯形法形法计算机算机辅助助（ExcelExcel，LingoLingo等）等）两个两个变量、直角坐量、直角坐标三个三个变量、立体坐量、立体坐标适用于任意适用于任意变量、但必需将量、但必需将一般形式一般形式变成成标准形式准形式.Page 15图解法解法max Z=2X1+X2 X1+1.9X2 3.8 X1 -1.9X2 3.8s.t.X1+1.9X2 10.2 X1 -1.9X2 -3.8 X1 ，X2 0例例：用用图解法求解解法求解线性性规划划问题.Page 16图解法解法x1x2oX1-1.9X2=3.8()X1+1.9X2=3.8()X1-1.9X2=-3.8()X1+1.9X2=10.2()4=2X1+X2 20=2X1+X2 17.2=2X1+X2 11=2X1+X2 Lo：0=2X1+X2（7.6，2）Dmax Zmin Z此点是唯一最此点是唯一最优解，解，且最且最优目目标函数函数值 max Z=17.2可行域可行域max Z=2X1+X2.Page 17图解法解法max Z=3X1+5.7X2x1x2oX1-1.9X2=3.8()X1+1.9X2=3.8()X1-1.9X2=-3.8()X1+1.9X2=10.2()（7.6，2）DL0：0=3X1+5.7X2 max Z（3.8，4）34.2=3X1+5.7X2 蓝色色线段上的所有点都是最段上的所有点都是最优解解这种情形种情形为有无有无穷多最多最优解，但是最解，但是最优目目标函数函数值max Z=34.2是唯一的。是唯一的。可行域可行域.Page 18图解法解法min Z=5X1+4X2x1x2oX1-1.9X2=3.8()X1+1.9X2=3.8()X1+1.9X2=10.2()DL0：0=5X1+4X2 max Z min Z 8=5X1+4X2 43=5X1+4X2（0，2）可行域可行域此点是唯一最此点是唯一最优解解.Page 19图解法解法246x1x2246无界解无界解(无最无最优解解)max Z=x1+2x2例例1.6x1+x2=4()x1+3x2=6()3x1+x2=6()max Z min Z.Page 20 x1x2O10203040102030405050无可行解无可行解(即无最即无最优解解)max Z=3x1+4x2例例1.7.Page 21图解法解法学学习要点：要点：1.通通过图解法了解解法了解线性性规划有几种解的形式划有几种解的形式（唯一最（唯一最优解；无解；无穷多最多最优解；无界解；无可行解）解；无界解；无可行解）2.作作图的关的关键有三点：有三点：(1)可行解区域要画正确可行解区域要画正确(2)目目标函数增加的方向不能画函数增加的方向不能画错(3)目目标函数的直函数的直线怎怎样平行移平行移动.Page 22线性性规划划问题的数学模型的数学模型目目目目标标函数：函数：函数：函数：约约束条件：束条件：束条件：束条件：3.3.线线性性性性规规划数学模型的一般形式划数学模型的一般形式划数学模型的一般形式划数学模型的一般形式简写写为：.Page 23线性性规划划问题的数学模型的数学模型4.线线性性规规划划问题问题的的标标准形式准形式特点：特点：(1)目目标函数求最大函数求最大值（有（有时求最小求最小值）(2)约束条件都束条件都为等式方程，且右端常数等式方程，且右端常数项bi都大于或等于零都大于或等于零(3)决策决策变量量xj为非非负。.Page 24线性性规划划问题的数学模型的数学模型（2 2 2 2）如何化）如何化）如何化）如何化标标准形式准形式准形式准形式 目目标函数的函数的转换 如果是求极小如果是求极小值即即 ，则可将目可将目标函数乘以函数乘以(-(-1)1)，可化，可化为求极大求极大值问题。也就是：令也就是：令 ，可得到上式。，可得到上式。即即 若存在取若存在取值无无约束的束的变量量 ，可令，可令 其中：其中：变量的量的变换.Page 25线性性规划划问题的数学模型的数学模型 约束方程的束方程的转换：由不等式：由不等式转换为等式。等式。称称为松弛松弛变量量称称为剩余剩余变量量 变量量 的的变换 可令可令 ，显然然.Page 26线性性规划划问题的数学模型的数学模型例例1.3 将下列将下列线性性规划划问题化化为标准形式准形式用用 替替换 ，且，且 解解:（）因（）因为x3无符号要求无符号要求，即，即x3取正取正值也可取也可取负值，标准准型中要求型中要求变量非量非负，所以，所以.Page 27线性性规划划问题的数学模型的数学模型(2)第一个第一个约束条件是束条件是“”号，在号，在“”左端加入松左端加入松驰变量量x4，x40,化化为等式；等式；(3)第二个第二个约束条件是束条件是“”号，在号，在“”左端减去剩余左端减去剩余变量量x5，x50；(4)第第3个个约束方程右端常数束方程右端常数项为-5，方程两，方程两边同乘以同乘以(-1),将右将右端常数端常数项化化为正数；正数；(5)目目标函数是最小函数是最小值，为了化了化为求最大求最大值，令，令z=-z,得到得到max z=-z，即当，即当z达到最小达到最小值时z达到最大达到最大值，反之亦然，反之亦然;.Page 28线性性规划划问题的数学模型的数学模型标准形式如下：准形式如下：.Page 29线性性规划划问题的数学模型的数学模型4.4.线性性规划划问题的解的解线性性规划划问题求解求解线性性规划划问题，就是从，就是从满足足约束条件束条件(2)、(3)的方程的方程组中找出一个解，使目中找出一个解，使目标函数函数(1)达到最大达到最大值。.Page 30单纯形法的形法的计算步算步骤单纯单纯形法的思路形法的思路形法的思路形法的思路找出一个初始可行解找出一个初始可行解找出一个初始可行解找出一个初始可行解是否最是否最是否最是否最优优转转移到另一个基本可行解移到另一个基本可行解移到另一个基本可行解移到另一个基本可行解（找出更大的目（找出更大的目（找出更大的目（找出更大的目标标函数函数函数函数值值）最最最最优优解解解解是是是是否否否否循循循循环环核心是：核心是：核心是：核心是：变变量迭代量迭代量迭代量迭代结结束束束束.Page 31单纯形法的形法的计算步算步骤例例1.8 用用单纯形法求下列形法求下列线性性规划的最划的最优解解解：解：1）将将问题化化为标准型，加入松准型，加入松驰变量量x3、x4则标准型准型为:.Page 32单纯形法的形法的计算步算步骤2）求出）求出线性性规划的初始基可行解，列出初始划的初始基可行解，列出初始单纯形表。形表。cj3400icB基基bx1x2x3x40 x34021100 x43013013400检验数数.Page 33单纯形法的形法的计算步算步骤cj3400icB基基变量量bx1x2x3x40 x34021100 x430130134000 x34x23x14x2换入列入列bi/ai2，ai204010换出出行行将将3化化为15/311801/301/31011/3303005/304/3乘乘以以1/3后后得得到到103/51/518011/52/540011.Page 34单纯形法的形法的计算步算步骤例例1.9 用用单纯形法求解形法求解解：将数学模型化解：将数学模型化为标准形式：准形式：不不难看出看出x4、x5可作可作为初始基初始基变量，列量，列单纯形表形表计算。算。.Page 35单纯形法的形法的计算步算步骤cj12100icB基基变量量bx1x2x3x4x50 x4152-32100 x5201/31501121000 x42x220 x x2 22 21/3150120753017131/309022560 x x1 111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3.Page 36单纯形法的形法的计算步算步骤学学习要点：要点：1.线性性规划解的概念以及划解的概念以及3个基本定理个基本定理2.熟熟练掌握掌握单纯形法的解形法的解题思路及求解步思路及求解步骤.Page 37单纯形法的形法的进一步一步讨论人工人工变量法量法人工人工变量法：量法：前面前面讨论了在了在标准型中系数矩准型中系数矩阵有有单位矩位矩阵，很容易，很容易确定一确定一组基可行解。在基可行解。在实际问题中有些模型并不含有中有些模型并不含有单位位矩矩阵，为了得到一了得到一组基向量和初基可行解，在基向量和初基可行解，在约束条件的束条件的等式左端加一等式左端加一组虚虚拟变量，得到一量，得到一组基基变量。量。这种人种人为加加的的变量称量称为人工人工变量，构成的可行基称量，构成的可行基称为人工基，用大人工基，用大MM法或两法或两阶段法求解，段法求解，这种用人工种用人工变量作量作桥梁的求解方法称梁的求解方法称为人工人工变量法。量法。.Page 38单纯形法的形法的进一步一步讨论人工人工变量法量法例例1.10 用大用大M法解下列法解下列线线性性规规划划解：首先将数学模型化解：首先将数学模型化为标准形式准形式系数矩系数矩阵中不存在中不存在单位矩位矩阵，无法建，无法建立初始立初始单纯形表。形表。.Page 39单纯形法的形法的进一步一步讨论人工人工变量法量法故人故人为为添加两个添加两个单单位向量，得到人工位向量，得到人工变变量量单纯单纯形法数学模型：形法数学模型：其其中中：M是是一一个个很很大大的的抽抽象象的的数数，不不需需要要给出出具具体体的的数数值，可可以以理理解解为它它能能大大于于给定定的的任任何何一一个个确确定定数数值；再再用用前前面面介介绍的的单纯形法求解形法求解该模型，模型，计算算结果果见下表。下表。.Page 40单纯形法的形法的进一步一步讨论人工人工变量法量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7i0 x64-431-10104-Mx5101-1201005-Mx712-21000113-2M2+M-1+2M-M0 x63-650-1013/5-Mx58-3300108/3-1x312-210005-6M5M0-M002x23/56/5101/50-Mx531/53/5003/5131/3-1x311/52/5012/505 00002x213010123x131/310015/3-1x319/300102/3000-5-25/3.Page 41Chapter5 目目标规划划(Goal programming)(Goal programming)目目标规划划问题及其数学模型及其数学模型目目标规划的划的图解分析法解分析法目目标规划划应用用举例例本章主要内容：本章主要内容：本章主要内容：本章主要内容：.Page 42目目标规划划问题及其数学模型及其数学模型例例5.1 某企某企业计业计划生划生产产甲，乙两种甲，乙两种产产品，品，这这些些产产品分品分别别要在要在A,B,C,D四种不同四种不同设备设备上加工。按工上加工。按工艺艺文件文件规规定，如表所示。定，如表所示。ABCD单件利件利润甲甲11402乙乙22043最大最大负荷荷1281612.Page 43目目标规划划问题及其数学模型及其数学模型但企但企业的的经营目目标不不仅仅是利是利润，而且要考，而且要考虑多个方面，如：多个方面，如：(1)力求使利力求使利润指指标不低于不低于12元；元；(2)考考虑到市到市场需求，甲、乙两种需求，甲、乙两种产品的生品的生产量需保持量需保持1:1的比的比例；例；(3)C和和D为贵重重设备，严格禁止超格禁止超时使用；使用；(4)设备B必要必要时可以加班，但加班可以加班，但加班时间要控制；要控制；设备A即要求即要求充分利用，又尽可能不加班。充分利用，又尽可能不加班。要考要考要考要考虑虑上述多方面的目上述多方面的目上述多方面的目上述多方面的目标标，需要借助目，需要借助目，需要借助目，需要借助目标规标规划的方法。划的方法。划的方法。划的方法。.Page 44目目标规划划问题及其数学模型及其数学模型3.目目标的的优先先级与与权系数系数在一个目在一个目标规划的模型中，划的模型中，为达到某一目达到某一目标可可牺牲其他一些牲其他一些目目标，称，称这些目些目标是属于不同是属于不同层次的次的优先先级。优先先级层次的高低次的高低可分可分别通通过优先因子先因子P1,P2,表示。表示。对于同一于同一层次次优先先级的不同的不同目目标，按其重要程度可分，按其重要程度可分别乘上不同的乘上不同的权系数。系数。权系数是一个个系数是一个个具体数字，乘上的具体数字，乘上的权系数越大，表明系数越大，表明该目目标越重要。越重要。现假定：假定：第第1优先先级P1企企业利利润；第第2优先先级P2甲乙甲乙产品的品的产量保持量保持1:1的比例的比例 第第3优先先级P3设备A,B尽量不超尽量不超负荷荷工作。其中工作。其中设备A的重要性的重要性比比设备B大三倍。大三倍。.Page 45目目标规划划问题及其数学模型及其数学模型上述目上述目标规标规划模型可以表示划模型可以表示为为：.Page 46目目标规划划问题及其数学模型及其数学模型目目标规划数学模型的一般形式划数学模型的一般形式达成函数达成函数目目标约束束其中：其中：g gk k为第第k k个目个目标约束的束的预期目期目标值，和和 为p pl l 优先因先因子子对应各目各目标的的权系数。系数。.Page 47目目标规划的划的图解分析法解分析法目目目目标规标规划的划的划的划的图图解法：解法：解法：解法：适用两个适用两个变量的目量的目标规划划问题，但其操作，但其操作简单，原理一目了然。同原理一目了然。同时，也有助于理解一般目，也有助于理解一般目标规划划的求解原理和的求解原理和过程。程。图图解法解解法解解法解解法解题题步步步步骤骤：1.将所有将所有约束条件（包括目束条件（包括目标约束和束和绝对约束，束，暂不考不考虑正正负偏偏差差变量）的直量）的直线方程分方程分别标示于坐示于坐标平面上。平面上。2.确定系确定系统约束的可行域。束的可行域。3.在目在目标约束所代表的束所代表的边界界线上，用箭上，用箭头标出正、出正、负偏差偏差变量量值增大的方向增大的方向.Page 48目目标规划的划的图解分析法解分析法3.求求满足最高足最高优先等先等级目目标的解的解4.转到下一个到下一个优先等先等级的目的目标，再不破坏所有，再不破坏所有较高高优先等先等级目目标的前提下，求出的前提下，求出该优先等先等级目目标的解的解5.重复重复4，直到所有，直到所有优先等先等级的目的目标都已都已审查完完毕为止止6.确定最确定最优解和解和满意解。意解。.Page 49目目标规划的划的图解分析法解分析法例例5.2 用用图图解法求解下列目解法求解下列目标规标规划划问题问题.Page 50目目标规划的划的图解分析法解分析法(a)(b)(c)(d)x2x1(e)(f)d1-d1+d2+d2-d3-d3+d4-d4+满意解意解(3,3)04683462 2.Page 51目目标规划的划的图解分析法解分析法x1x2(a)(b)d1+d1-(c)d2-d2+(d)d3-d3+GD满意解是意解是线段段GD上任意点上任意点其中其中G点点X(2,4),D点点X(10/3,10/3)05.51055.6112,410/3,10/35107例例5.3.Page 52目目标规划的划的图解分析法解分析法Ox1x22040605020406050abd1-d1+d2-d2+cdd3-d3+d4-d4+(24,26)满意解意解X=(24，26)例例5.4.Page 53实 例例 设某公司生某公司生产两种型号的两种型号的电扇，一种扇，一种为普通型，装配一个普通型，装配一个需要需要1小小时，另一种，另一种为豪豪华型，装配一个需要型，装配一个需要2小小时。正。正常的装配常的装配时间每周限定每周限定为40小小时。市。市场调查表明每周表明每周销售普通型不超售普通型不超过30件，豪件，豪华型不超型不超过15件。普通型每件件。普通型每件的的净利利润为8元，豪元，豪华型型为每件每件12元。元。公司公司经理提出如下理提出如下优先次序的要求：先次序的要求：n n1 1计计划利划利划利划利润润不少于不少于不少于不少于400400元元元元n n2 2装配装配装配装配线线尽可能少加班尽可能少加班尽可能少加班尽可能少加班n n3 3根据市根据市根据市根据市场调场调研要求每周生研要求每周生研要求每周生研要求每周生产产的的的的产产品数不能多于品数不能多于品数不能多于品数不能多于销销售的数量，即普通型售的数量，即普通型售的数量，即普通型售的数量，即普通型电电扇扇扇扇为为3030件，豪件，豪件，豪件，豪华华型型型型电电扇扇扇扇为为1515件。件。件。件。.Page 54该问题的决策目的决策目标是：是：（1）总利利润不少于不少于400元；元；（2）尽可能少加班；）尽可能少加班；（3）生）生产数量不能超数量不能超过预销售数量。售数量。（4）绝对目目标约束。所束。所谓绝对目目标约束束就是必就是必须要要严格格满足的足的约束。束。绝对目目标约束是最高束是最高优先先级，在考，在考虑较低低优先先级的目的目标之前它之前它们必必须首先得到首先得到满足。足。实 例例.Page 55Chapter6 图与网与网络分析分析(Graph Theory and Network Analysis)(Graph Theory and Network Analysis)图的基本概念与模型的基本概念与模型树与与图的最小的最小树最短路最短路问题网网络的最大流的最大流本章主要内容：本章主要内容：本章主要内容：本章主要内容：.Page 56树与与图的最小的最小树 树：无圈的：无圈的连通通图即即为树性性质1：任何：任何树中必存在次中必存在次为1的点。的点。性性质2：n 个个顶点的点的树必有必有n-1 条条边。性性质3：树中任意两个中任意两个顶点之点之间，恰有且，恰有且仅有一条有一条链。性性质4：树连通，但去掉任一条通，但去掉任一条边，必，必变为不不连通。通。性性质5：树无回圈，但不相无回圈，但不相邻的两个点之的两个点之间加一条加一条边，恰，恰得到一个圈。得到一个圈。v1v2v3v4v5v6.Page 57树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636练习练习：应应用破圈法求最小用破圈法求最小用破圈法求最小用破圈法求最小树树.Page 58树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636.Page 59树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323.Page 60树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323.Page 61树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323.Page 62树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323.Page 63树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 9161625253 3282817174 41 12323.Page 64树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 9161625253 3282817174 41 12323.Page 65树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 12323.Page 66树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 12323.Page 67树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323.Page 68树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323.Page 69树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 317174 41 12323min=1+4+9+3+17+23=57.Page 70树与与图的最小的最小树练习练习：应应用避圈法求最小用避圈法求最小用避圈法求最小用避圈法求最小树树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636.Page 71树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636.Page 72树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636.Page 73树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636.Page 74树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636.Page 75树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636.Page 76树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636min=1+4+9+3+17+23=57min=1+4+9+3+17+23=57.Page 77某公司某公司铺设光光导纤维网网络某公司的管理某公司的管理层已已经决定决定铺设最先最先进的光的光导纤维网网络，为公公司的主要中心之司的主要中心之间提供高速通信（数据、声音、提供高速通信（数据、声音、图像等）。像等）。下下图中的中的节点点显示了示了该公司主要中心（包括公司的公司主要中心（包括公司的总部、部、巨型巨型计算机、研究区、生算机、研究区、生产和配送中心等）的分布和配送中心等）的分布图。虚。虚线是是铺设纤维光光缆的可能位置。每条虚的可能位置。每条虚线旁的数字表示了旁的数字表示了如果如果选择在在这个位置个位置铺设光光缆需要花需要花费的成本。的成本。ADCFEG43722B5445711.Page 78ADCFEG43722B2445711最最优解解图示示总成本成本为2+2+1+3+1+5=14.Page 79树与与图的最小的最小树课课堂堂堂堂练习练习：3749346321Min C(T)=12Min C(T)=15254173314475答案：答案：.Page 80树与与图的最小的最小树34122323242Min C(T)=12213638534567454321Min C(T)=18.Page 81最短路最短路问题从一特殊的从一特殊的节点出点出发，找出从，找出从该节点到网点到网络中任何其它中任何其它节点的最短路径点的最短路径问题GPS导航系航系统寻找最找最优路径路径问题描述：描述：就是从就是从给定的网定的网络图中找出一点到各点或任意两点之中找出一点到各点或任意两点之间距离最短的一条路距离最短的一条路.有些有些问题，如，如选址、管道址、管道铺设时的的选线、设备更新、投更新、投资、某些整数、某些整数规划和划和动态规划的划的问题，也可以，也可以归结为求最短求最短路的路的问题。因此。因此这类问题在生在生产实际中得到广泛中得到广泛应用。用。.Page 82最短路最短路问题求最短路有两种算法求最短路有两种算法:狄克斯屈拉狄克斯屈拉(Dijkstra)标号算法号算法 逐次逼近算法逐次逼近算法.Page 83最短路最短路问题例例6.5 求下求下图v1到到v7的最短路的最短路长及最短路及最短路线862523534210570862254411147510711v7已已标号，号，计算算结束。从束。从v1到到v7的最短路的最短路长是是 11,最短路最短路线：v1 v4 v6 v7P标号号T标号号12.Page 84最短路最短路问题从上例知，只要某点已从上例知，只要某点已标号，号，说明已找到起点明已找到起点vs到到该点的最短路点的最短路线及最短距离，因此可以将每个点及最短距离，因此可以将每个点标号，求出号，求出vs到任意点的最短路到任意点的最短路线，如果某个点，如果某个点vj不能不能标号，号，说明明vs不可达不可达vj。注：无向注：无向图最短路的求法只将上述步最短路的求法只将上述步骤2将弧改成将弧改成边即可。即可。.Page 85最短路最短路问题例例6.6 求下求下图v1到各点的最短距离及最短路到各点的最短距离及最短路线。4526178393261216180452231039612641166188122482418所有点都已所有点都已标号，点上的号，点上的标号就是号就是v1到到该点的最短距离，最短点的最短距离，最短路路线就是就是红色的色的链。.Page 86最短路最短路问题课堂堂练习：1.用用Dijkstra算法求下算法求下图从从v1到到v6的最短距离及路的最短距离及路线。v3v54v1v2v4v635222421v1到到v6的最短路的最短路为：.Page 87最短路最短路问题2.求从求从v1到到各点各点的最短路径的最短路径237184566134105275934682.Page 88最短路最短路问题237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10v1到到v8的最短路径的最短路径为v1v4v7v5v8，最短距离，最短距离为10.Page 89最短路最短路问题3.求下求下图中中v1点到另外任意一点的最短路径点到另外任意一点的最短路径v1v2v3v4v6v5322762133.Page 90最短路最短路问题v1V2V3V4 V6V5322762133024714.Page 91最短路最短路问题v1V2V3V4 V6V5322762133024714.Page 92网网络的最大流的最大流基本概念：基本概念：1.1.容量网容量网容量网容量网络络：对对网网络上的每条弧上的每条弧(vi,vj)都都给出一个最大的通出一个最大的通过能力，称能力，称为该弧的弧的容量容量容量容量，简记为cij。容量网。容量网络中通常中通常规定定一个一个发发点点点点(也称源点，也称源点，记为s)和一个和一个收点收点收点收点(也称也称汇点，点，记为t)，网网络中其他点称中其他点称为中中中中间间点点点点。st4844122679.Page 93最大流最大流问题例例5.2 某公司要从起点某公司要从起点VS（供（供应点）运送点）运送货物到目的地物到目的地VT（需求点），其网（需求点），其网络图如下所示。如下所示。图中每条弧（中每条弧（节点点i到到节点点j）旁的）旁的权 表示表示这条运条运输路路线的最大运的最大运输能力（容量）能力（容量）。要求制定一个运。要求制定一个运输方案，使得从方案，使得从VS到到VT的的货运量达到运量达到最大。最大。这个个问题是是寻求网求网络系系统的最大流的最大流问题。605040703040705080.Page 94问题分析分析决策决策变量：量：目目标函数：函数：约束条件：束条件：1 转运点运点 2 弧的容量限制弧的容量限制 3 非非负.Page 95数学模型数学模型.Page 9660504070304070508060204030204010最大流最大流问题的的变形形例例5.3：在例：在例5.2的基的基础上，增加了一个供上，增加了一个供应点点PS、一个需求点、一个需求点PT、两个、两个转运运点点P1和和P2以及与之相以及与之相连的的7条弧。目条弧。目标是从是从2个供个供应点点VS和和PS运出的运出的货物量物量最大。本最大。本问题是一个有是一个有2个供个供应点和点和2个需求点的最大流个需求点的最大流问题.Page 97最小最小费用流用流问题 对于网于网络图G中的弧，除中的弧，除标明弧的容明弧的容量量 外，外，还要要标明流明流过该弧弧单位位流量的流量的费用用 ，G的一个可行流的一个可行流 ，使得流的，使得流的总运运输费用：用：达到最小。达到最小。特特别，如果可行流是最大流，如果可行流是最大流时，此，此问题就是最小就是最小费用流用流问题。最小最小费用流用流问题上一上一节讨论的的寻求网求网络最大流最大流问题，只考，只考虑了流的数量，没有考了流的数量，没有考虑流流的的费用。用。实际上上许多多问题要考要考虑流的流的费用最小用最小问题。2453114,420,510,45,119,315,527,630,2.Page 98例例5.1某公司有两个工厂生某公司有两个工厂生产产品，品，这些些产品需要送到两个品需要送到两个仓库中。中。其配送网其配送网络图如下，目如下，目标是确定一个运是确定一个运输方案（即每条方案（即每条线路上运送多少路上运送多少单位的位的产品），使得通品），使得通过配送网配送网络的的总运运输成本最小。成本最小。90（50，300）（50，400）（50，200）（50，400）（无限制，（无限制，700）（无限制，（无限制，900）806070.Page 99数学模型构建数学模型构建.