[企业管理]管理运筹学i本科

1,管 理 运 筹 学,主讲：陈鼎藩社科系工商管理教研室,2,目 录,第1章 线性规划第2章 对偶理论第3章 运输问题第4章 整数规划与分配问题 第5章 图与网络分析第6章 计划评审法和关键路线法第7章 目标规划,3,第1章 线性规划,1.1 线性规划的数学模型1.2 图解法1.3 单纯形法原理与计算步骤1.4 单纯形法进一步讨论1.5 线性规划建模,4,ex1.1:甲企业计划生产两种产品、，这两种产品都要分别在A、B、C、D四种不同设备上加工，已知每生产一件产品的设备加工工时、设备生产能力、产品单位利润如下表，问、各生产多少使利润达到最大？,1.1 线性规划数学模型,5,解 设分别生产、产品数量为x1、x2 则利润Z=2x1+3x2,考虑到设备的生产能力则应受到以下条件的限制使得,2x1+2x212,x1 +2x28,4x1 164x2 12,x1，x2 0,利润目标为,max z=2x1+3x2,A 设备生产能力约束,B 设备生产能力约束,C、D 设备生产能力约束,现实问题变量非负,Z=2x1 +3x2 max,6,线性规划模型三要素,决策变量（variable）：指决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。,目标函数（objective）：问题要达到的目的要求。,约束条件(constrains)：决策变量取值时受到的各种资源的限制。,目标函数和约束条件皆为决策变量的线性函数,7,线性规划数学模型的几种形式,目标函数：max（min）z=c1x1 +c2x2 + +cnxn,a11x1 +a12 x2+ +a1n xn(,=)b1 a21x1 +a22 x2+ +a2n xn (,=)b2 am1x1 +am2 x2+ +amn xn(,=)bm x1 ,x2 ,xn 0,.,约束条件s.t.,简写形式,8,矩阵形式,向量形式,9,标准形式：,非标准形式如何转化？,目标函数为求极小值,约束条件为不等式,变量取值无约束,目标函数求最大值约束条件取等式变量非负,ex1.2,10,1.2 图解法,优点：直观性强，便于了解线性规划问题解的情况,计算步骤：,缺点：只能求解两个变量的线性规划模型,建立坐标系,图示约束条件，确定满足约束的解的范围,画出目标函数直线族,确定最优解,11,可行域,目标函数等值线,最优解,6,4,-8,6,0,x1,x2,12,线性规划问题解的情况,唯一最优解（交于一点）,无穷多个最优解（交于一条线段）,无解（无可行域）,无界解,13,1.3 单纯形法,解的概念,可行解：满足约束条件的解X=（x1, , xn）T称为线性规划问题的可行解。,可行域：可行解的集合。,最优解：使目标函数达到最大值的可行解。,基：若A为约束方程组的mn阶系数矩阵，R（A）= m, B是A的mm阶满秩子矩阵，则称B为线性规划问题的一个基。,14,基向量：B中的每一个列向量pj称为基向量。,基变量：基向量pj对应的变量xj称为基变量。,基解：在约束方程组 A X = b 中，令所有的非基变量都为零，即 xm+1 = xm+2 = = xn=0， ,又因为B满秩，根据克拉姆法则，由m个约束方程组可解出m个基变量的唯一解XBXB=（x1,x2, xm ）,将这个解加上非基变量取0的值有X= （x1,x2, xm，0， 0 ）T，称X为线性规划问题的基解。,基可行解：若基解X0，则X为基可行解。,可行基：对应于基可行解的基称为可行基。,15,ex1.7 找出下列线性规划问题的基解、基可行解,16,凸集及其顶点,凸集,凸集,不是凸集,顶点,凸集：如果集合C上任意两个点X1、X2，其连线上的所有点都在集合C上，则C是凸集。,顶点:,17,基本定理,定理1：若线性规划问题存在可行解，则问题的可行域是凸集。,引理1：线性规划问题的可行解X=（x1,xn）T为基可行解的充分必要条件是X的正分量所对应的系数列向量是线性无关的。,定理2：线性规划问题的基可行解X对应线性规划问题可行域（凸集）的顶点。,定理3：若线性规划问题有最优解，一定存在一个基可行解是最优解。,推论：若线性规划问题有最优解，至少在可行域的一个顶点取得最优。,18,单纯形法计算步骤：,化为标准型,求初始基可行解，列出初始单纯形表,最优性检验,从一个基可行解转换到相邻的基可行解,迭代,19,单纯形表,c1 c2 cm cj cn,x1 x2 xm xj xn,cj ,c1 x1 b1c2 x2 b2: : : : :cm xm bm,cB 基 b,1 0 0 a1j a1n0 1 0 a2j a2n: : : : : : : : :0 0 1 amj amj,cj - zj,0 0 0 ,20,ex1.8 用单纯性法求解下列线性规划问题,21,ex1.9 用单纯性法求解下列线性规划问题,22,1.4 单纯形法进一步讨论,人工变量法,23,化为标准型：,添加人工变量x6、x7：,24,两阶段法,第一阶段：,求解一个目标函数中只包含人工变量的线性规划模型,第二阶段：,若第一阶段的模型目标函数值为0,则原问题有可行解。,25,解的判别：,唯一最优解,基变量不含人工变量,所有的检验数 0,所有的非基变量的检验数 =700X1+0.5X2+0.2X3+2X4+0.5X5=300.5X1+X2+0.2X3+2X4+0.8X5=100END,LINDO 输入文件：,LP OPTIMUM FOUND AT STEP 1 OBJECTIVE FUNCTION VALUE 1) 32.43590 VARIABLE VALUE REDUCED COST X1 0.000000 0.059615 X2 0.000000 0.593590 X3 0.000000 0.352564 X4 39.743591 0.000000 X5 25.641026 0.000000,LINDO 输出文件：,31,Ex1.11 某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙，已知各种牌号糖果中A、B、C含量、原料成本、各种原料的每月限用量，三种牌号糖果的单位加工费及售价如下表所示，问该厂每月生产这三种糖果各多少千克，使该厂获利最大，建立此问题的数学模型并求解。,甲 乙 丙 原料成本 每月限用量 （元/kg） (kg),A 60% 30% 2.00 2000B 1.50 2500C 20% 50% 60% 1.00 1200,加工费（元/kg）,售价（元/kg）,3.40 2.85 2.25,0.5 0.4 0.3,32,MAX (3.40-0.5)(X11+X21+X31)+(2.85-0.4)()+(2.25-0.3)(X13+X23+X33)-2.0(X11+X12+X13)-1.50(X21+X22+X23)-1.0(X31+X32+X33)=0.9X11+1.4X21+1.9X31+0.45X12+0.95X22+1.45X32-0.05X13+0.45X23+0.95X33STX11+X12+X13=0.6（X11+X21+X31）X31=0.3 (X12+X22+X32 )X32=0.5（X12+X22+X32）X33=0.6（X13+X23+X33）END,原始模型：,33,MAX 0.9X11+1.4X21+1.9X31+0.45X12+0.95X22+1.45X32-0.05X13+0.45X23+0.95X33STX11+X12+X13=0X31-0.2X11-0.2X21-0.2X31=0X32-0.5X12-0.5X22-0.5X32=0X33-0.6X13-0.6X23-0.6X330） ,则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。,50,ex 2.3 已知线性规划问题：,要求：（1）写出其对偶问题；（2）已知原问题最优解为X*=（2，2，4，0），试根据对偶理论，直接求出对偶问题的最优解。,51,（6）基解的互补性 和变量的对应关系：,线性规划问题原问题和对偶问题之间存在一对互补的基解，其中原问题的松弛变量对应于对偶问题的变量，对偶问题的剩余变量对应原问题的变量，这些互相对应的变量如果在一个问题的解中是基变量，则在另一个问题的解中是非基变量。将这对互补的基解分别代入原问题和对偶问题的目标函数中，有z=.,52,LP1,LP2,y1 对应 x3,y2 对应x4,y3对应x5,x1对应y4,x2对应y5,53,LP1的最终单纯行表：,LP2的最终单纯行表,54,2.4 影子价格,bi 是线性规划问题约束的右端项，代表第i种资源的拥有量 。而对偶变量 yi 的意义代表对一个单位第i种资源的估价，这种估价不是资源的市场价格，是根据资源在生产中做出的贡献而作的估价，称之为影子价格。,55,（1）影子价格与市场价格的区别：,市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的影子价格随之改变。,56,（2）影子价格 是一种边际价格,57,（3）资源的影子价格又 是一种机会成本,在纯市场经济条件下，在ex2.4中，当第3种资源的市场价格低于1/5时，可以买进这种资源；当市场价格高于影子价格时，就会卖出这种资源。影子价格最终会与市场价格处于同等水平。,58,（4）互补松弛性的经济含义,59,（5）检验数的经济意义,cj 代表第j种产品的产值， 是生产该种产品所消耗各项资源影子价格的总和，即产品的隐含成本。当产品的产值大于成本时，生产该产品有利可图，应安排该种产品（检验数大于零的变量作为进基变量）。,60,（6）资源影子价格的应用,对线性规划的求解是确定资源的最有效分配方案，而对其对偶问题的求解则是确定资源的恰当估价，这种估价直接涉及到资源的最有效利用。 资源的影子价格可以作为公司内部的结算价格；社会上可对一些最紧缺的资源，借助影子价格规定使用这种资源一单位时必须上交的利润额，以控制某些公司超低成本使用社会资源，侵蚀公众福利。,61,2.5 对偶单纯形法,62,2.6 灵敏度分析,灵敏度分析：对系统或事物因周围条件变化显示出来的敏感程度的分析。,63,灵敏度分析的步骤,（1）将参数的改变计算反映到最终的单纯形表上,（2）检查原问题是否仍为可行解,（3）检查对偶问题是否仍为可行解,64,（3）检查对偶问题是否仍为可行解,（4）按下表所列情况得出结论和决定继续计算步骤,65,分析cj变化的影响,66,分析bi的变化范围,67,增加一个变量的分析,增加一个变量的分析在实际问题中反映为增加一种新产品。,ex 2.7 现在该公司计划增加一种新产品x6，已知该产品单位利润为4元，p6=(2 4 5)T，原有条件不变，试分析该公司是否生产这种新产品？,68,增加一个约束条件的分析,增加一个约束条件的分析在实际问题中反映为增加一道工序或者增加一种资源限制。,ex 2.8 增加一个约束条件 3x1+2x214，要求分析最优解变化。,69,第3章 运输问题,3.1 运输问题的数学模型3.2 表上作业法3.3 产销不平衡的运输问题及其应用,70,3.1 运输问题的数学模型,ex3.1 某食品公司经销的主要产品之一就是糖果，其下属三个生产厂，该公司把这些糖果分别运往四个地区门市部销售，已知各加工厂产量、各门市部销售量及从每个加工厂到各销售门市部每吨糖果的运价如下表所示，问该食品公司应如何调运，在满足各门市部需求量的情况下，使总的运费支出为最小。,运价,71,运价cij,一般运输问题的运输表,72,73,74,3.2 运输单纯形法 表上作业法,分析实际问题列出产销平衡表及单位运价表,确定初始调运方案（最小元素法orVogel法）,求检验数（闭回路法or 位势法）,找出绝对值最大的负检验数，闭回路法调整，得出新的调运方案,所有检验数0,是,否,得到最优方案算出总的运费,迭代,75,表3-1 表上作业法计算,运价,产地,76,3.3 产销不平衡的运输问题及其应用,ex3.2 设有A1、A2、A3三个产地生产某种物资，其产量分别为7t、5t、7t，B1、B2、B3、B4四个销售地需要该物资，销量分别为2t、3t、4t、6t，又知各产销地之间的单位运价如下表，试决定总运费最小的调运方案。,处理产销不平衡的思路：转化为产销平衡问题,77,运价,产地,表3-2,78,ex3.3 设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同，已知各化肥厂年产量，各地区需要量及从各化肥厂到各地区单位化肥的运价如表3-3所示，试决定使总的运费最节省的化肥调拨方案。,79,需求地区,化肥厂,表3-3,运价,80,ex3.4 江南厂按照合同要求需于每个季度末分别完成10、15、25、20台同一规格的柴油机。已知该厂每个季度生产能力及生产每台柴油机的成本如表3-4所示，又如果生产的柴油机当季不交货，每台每积压一个季度需储存、维护费用0.15万元。要求在完成合同的条件下，制订使该厂全年生产、储存和维护费用为最小的决策方案。,表3-4,81,ex3.5 东海造船厂根据合同要在当年算起的连续三年年末各提供三条规格相同的大型货轮。已知该厂今后三年的生产能力及生产成本如表3-5所示。 已知加班生产情况下每条货轮成本比正产生产时多出70万元，又知造出的货轮如当年不交货，每条货轮每积压一年将增加维护保养等费用为40万元。在签订合同时该厂已有两条当年制造的未交货的积压货轮。该厂希望在第三年年末在交完合同任务后能储存一条备用。问该厂应该如何生产计划，使在满足上述要求的条件下，使总的费用支出为最小？,82,表3-5,83,ex3.6 东兴煤炭公司下属吉祥、平安、双福三个煤矿，年生产能力分别为120、160、100万t ，公司同三个城市签订了下年度的供货合同：城市1-110万t,城市2-150万t,城市3-70万t,但城市3表示愿意购买剩余的全部煤炭。另有城市4虽未签订合同，但也表示只要公司有剩余煤炭，原全部收购。已知从各矿至四个城市的煤炭单位运价见表3-6。,表3 - 6,城市,煤矿,84,第4章 整数规划与分配问题,4.1 整数规划的特点及作用4.2 分配问题与匈牙利法4.3 分枝定界法 4.4 整数规划建模,85,4.1 整数规划的特点及作用,整数规划：要求一部分或全部决策变量必须取整数 的规划问题（整数线性规划）。,整数规划的定义和分类,86,纯整数规划：全部决策变量取整数的线性规划。,混合整数规划：只要求一部分决策变量取整数的线 性规划问题。,0-1规划：要求决策变量取0或1逻辑值的规划问题。,87,逻辑变量在建模中的用法,（1） m个约束条件中只有k个起作用,88,（2） 约束条件的右端项可能是r个值中的某一个,89,（3） 两组条件满足其中一组,90,（4） 用以表示含固定费用的函数,91,ex4.1 现有资金总额为B，可供选择的项目为n个。项目j（j=1n）所需投资额和预期收益分别为aj和cj。此外，由于种种原因，有三个附加条件：第一：若选择项目1就必须选择项目2；第二：项目3和4至少选择一个；第三：项目5、6、7恰好选择两个。问应当如何选择投资项目，才能使总收益最大？试建立此问题的数学模型。,92,4.2 分配问题与匈牙利法,m件任务分别由m个人完成，已知第j（j=1m）个人完成第i （i=1m）件任务的成本费用为cij，问应如何分配任务可使总费用最小。,成本 cij,分配问题（Assignment Problem）的数学模型,93,94,匈牙利法,1955年，库恩利用匈牙利数学家康尼格的关于矩阵中独立零元素的定理，提出了解分配问题的一种算法，习惯上称之为匈牙利法。,匈牙利法的关键是利用了分配问题最优解的下列性质：若从分配问题的系数矩阵（称为效率矩阵）的某行（或某列）的各元素分别减去一个常数k ，得到一个新的矩阵，则以新矩阵为系数矩阵的分配问题与原分配问题的最优解相同。因为系数矩阵的这种变化并不影响到数学模型的约束方程组，而只是使目标函数减少了常数k,所以最优解不发生变化。,95,变换效率矩阵,确定独立零元素,是否有m个独立零元素,N,Y,未划去零元素是否构成闭回路,每行减去本行最小元素每列减去本列最小元素,从“行”找，“列”画线从“列”找，“行”画线,Y,最优解,间隔指派沿闭回路,N,找到未被直线覆盖最小元素k，画线的行Ui=0，否则Ui=k,画线的列vj=-k，否则vj=0,匈牙利法计算步骤 :,每一元素分别减去Ui和vj,96,ex4.2 有一份说明书要分别翻译成英、日、德、俄四种文字，交给甲、乙、丙、丁四个人去完成。因个人专业不同，他们完成不同文字的翻译所需的时间如表4-1所示，应如何分配翻译任务，使这四个人分别完成四项任务总的时间为最小。,表4 - 1,人,工作,97,一般的分配问题,（1） 人数和事数不等的问题,人少事多，一人只做一件事：添上一些虚拟的人，这些虚拟人完成各事的费用系数为0，即这些费用不会发生的。,人少事多，事情必须全部完成：意味着某些人要完成若干件事情，则可将该人化作相同的几个人来接受指派，这几个“相同的人”做同一件事的费用系数当然也相同。,人多事少：添上一些虚拟的事，当然完成虚拟事的费用为0。,98,（2） 某事不能由某人做的分配问题,若某件事一定不能由某个人来做，则可将相应的费用系数取任意大的系数 M 即可。,（3） 最大化分配问题,目标函数是求最大值，按照下列方法转化为最小分配问题:找出效率矩阵B中最大的元素 m，用m 分别减去原效率矩阵 B 的每一个元素，得出新的效率矩阵 C,则以C为效率矩阵的最小化分配问题和以B为效率矩阵的最大化分配问题最优解相同，求解C 。,99,100,ex4.3 某商业公司计划开办5家新商店，为了尽早建成营业，商业公司决定由5家建筑公司分别承建，已知建筑公司Ai（i=15）对新商店Bi（i=15）的建造费用的报价是cij，见表4-3，商业公司如何来分配建造任务，才能使总的建造费用最少？,表4 - 3,建筑商,商店,报价,101,ex4.4 对于ex4.2中的分配问题，为了保证工程质量，经研究决定，舍弃建筑公司A4和A5，而让技术力量相对较强的建筑公司A1 、A2 和A3来承建。根据实际情况，可以允许每家建筑公司承建一家或二家商店。求使总费用最少的指派方案。,建筑商,商店,102,4.3 分枝定界法（Branch and Bound method）,103,分枝定界法的思路和步骤,（1）求解整数规划的松弛问题,设整数规划问题为A，它的松弛问题为B，则A的可行域是B 的可行域的子集 。若B无可行解则A无可行解；若B的最优解是A的可行解（满足A整数要求），则也是A的最优解；否则B的最优解（不满足A的整数要求）就是A最优解的上界（求极大时）或下界值（求极小时），转（2）。,104,（2）分枝,对问题B，任选一个不符合整数要求的变量进行分枝。,105,（3）定界,对B的子问题求最优解，若该解满足A的约束，即找到了A的一个可行解，否则该解为所属分枝的边界值（求极大化时为上界，求极小化时为下界）。 若所有的子问题的最优解均非A的可行解，则选取其边界值最大（求极大值时）或最小（求极小值时）的子问题进一步细分子问题求解 分枝过程一直进行下去，直到找到A的一个可行解为止。若计算时同时出现两个以上可行解，则选取其中最大（求极大值时）或最小（求极小值时）的一个保留，转（4）。,106,（4）剪枝,将各子问题的边界值与保留的可行解的值进行比较，把边界值劣于可行解的分枝剪去。若除保留下来的可行解外，其余分枝均被剪去，则该可行解就是A的最优解；否则回到（2），选取边界值最优的一个继续分枝。 若计算中又出现新的可行解，则与原可行解进行比较，保留最优的，并重复上述步骤。,107,L0X1=3.25 X2=2.5 Z=14.75,L1X1=3.5 X2=2 Z=14.5,L2X1=2.5 X2=3 Z=13.5,L11X1=3 X2=2 Z=13,L12X1=4 X2=1 Z=14,X22,X23,X13,X14,分枝定界过程,108,4.4 整数规划建模,ex4.6 东方大学计算机实验室聘用4名大学生（代号1、2、3、4）和2名研究生（代号5、6）值班答疑。已知每人从周一至周五每天最多可安排的值班时间及每人每小时值班报酬如下表,109,该实验室开放时间是8：00至晚上10：00，开放时间须有且仅须一名学生值班。规定大学生每周值班不少于8小时，研究生每周不少于7小时。每名学生每周值班不超过3次，每次值班不少于2小时，每天安排值班的学生不超过3人。且其中必须有一名研究生。试为该实验室安排一张人员的值班表，试总支付报酬最小。,110,Ex4.7 下表为某医院每天的护士值班最低需求人数。已知护士连续工作5天必须休息2天。在正常工作日（5天）周工资为300元；周六上班额外补助25元；周日上班额外补助35元。试安排护士值班计划，使医院的总工资支出最少。,111,Ex4.8 鞍山街邮局周一到周日每天所需值班人员如下表所示：,（1）规定邮局职工每周上班5天，休息2天，具体上班和休息时间由邮局安排，但保证每名职工每周至少有一个休息日安排在周六和周日。问该邮局至少应配备多少名职工，试建立数学模型并求解；,（2）在上述给定条件的基础上，又假定该邮局有主任、副主任各一人，上级规定每天值班人员中至少有一名主任或副主任，又同样保证主任或副主任每周至少休一个周六或周日，试建立数学模型并求解。,112,ex4.9 红星日用化工厂为发运产品,下一年度需6种不同容积的包装箱，每种包装箱的需求量及生产一个可变费用如下表：,由于生产不同容积包装箱时需进行专门准备、下料等，生产某一容积包装箱的固定费用为1200元。又若某一容积包装箱数量不够时，可用比它容积大的代替，试问该化工厂应订做哪几种代号的包装箱各多少个，使费用最节省。,113,ex4.10 春江市计划为新建的5个居民小区中的两个分别各设一所小学，下表给出了各小区内及各小区间的步行时间（min）,及各居民小区小学生人数。要求为该市提供决策建议，两所小学应分别建在哪两个小区，以及各居民小区的小学生应分到哪所小学上学，使学生总的上学步行时间为最短。,114,ex4.11 清远市下设8个区，下表给出救护车从一个区至另一个区的车程（min），该市拟建救护中心，要求各区离救护中心的车程必须在8min内，试为该市提供决策建议：至少建立多少个救护中心，建于何处？,115,ex4.12 某公司需生产2000件某种产品，该种产品可利用A、B、C、D设备中任意一种加工，已知每种设备的生产准备结束费、生产该产品时的单件成本以及每种设备限定的最大加工能力（件）如下表所示，问如何安排产品生产，使得总费用最低。试建立该问题的数学模型。,116,ex4.13 汉光汽车制造厂生产珠江、松花江、黄河三种牌号的汽车。已知各生产1台时的钢材、劳动力消耗及单位利润，每月可供使用的钢材及劳动力小时数见下表所示：,已知上述三种汽车的的经济批量均为月产1000台以上，即各牌号汽车或不生产或大于1000台/月，试为该厂找出一个使利润最大的生产计划方案。,117,第5章 图与网络分析,5.1 图的基本概念与模型5.2 树图和图的最小生成树5.3 最短路问题5.4 网络最大流5.5 最小费用流,118,5.1 图的基本概念与模型,哥尼斯堡七桥难题 （Seven Bridges Puzzle）,A,B,瑞士数学家欧拉（E Euler）于1736年发表了题为“依据几何位置的解题方法”的论文，有效地解决了七桥难题，被认为是图论的创始人。,119,环球旅行问题,1857年，爱尔兰数学家哈密尔顿（Hamilton）发明了一种游戏，他用一个实心正12面体象征地球，正12面体的20个顶点分别代表世界上20座名城，要求游戏者从任一城市出发，寻找一条可经由每个城市一次且仅一次再回到出发点的路，这就是“环球旅行问题”。,120,它与七桥问题不同，前者要在图中找一条经过每边一次且仅一次的路，通称欧拉回路，而后者是要在图中找一条经过每个点一次且仅一次的路，通称为哈密尔顿回路。 在这一时期，还有许多诸如迷宫问题、博奕问题以及棋盘上马的行走路线之类的游戏难题，吸引了许多学者。这些看起来似乎无足轻重的游戏却引出了许多有实用意义的新问题，开辟了新学科。 运筹学中的“中国邮路问题”：一个邮递员从邮局出发要走遍他所负责的每条街道去送信，问应如何选择适当的路线可使所走的总路程最短。这个问题是由我国管梅谷教授在1962年首先提出，因此国际上成为“中国邮路问题”。它与欧拉回路有密切的关系。而著名的“货郎担问题”则是一个带权的哈密尔顿回路问题。,121,庞加莱猜想,任何一个封闭的三维空间，只要它里面所有封闭曲线都可以收缩成一点，这个空间就一定是一个三维圆球这就是法国数学家庞加莱于1904年提出的猜想。2000年5月，美国的克莱数学研究所为每道题悬赏百万美元求解。,2006年6月3日，中山大学朱熹平教授和曹怀东以一篇长达300多页的论文，给出了庞加莱猜想的完全证明。破解了国际数学界关注上百年的重大难题庞加莱猜想。运用汉密尔顿、佩雷尔曼等的理论基础，朱熹平和曹怀东第一次成功处理了猜想中“奇异点”的难题，从而完全破解了困扰世界数学家多年的庞加莱猜想。,122,图：如果用点表示研究的对象，用边表示这些对象之间的联系，则图G可以定义为点和边的集合，记作G = V，E 。式中V是点的集合，E是边的集合当V、E都是有限集合时称G为有限图，否则为无限图。,网络图：如果给图中的点和边赋以具体的含义和权数，如距离、费用、容量等，把这样的图称为网络图，记作N。,123,上图中的点(又称顶点或节点)用“v” 表示，边用“e” 表示，对每条边可用它所联结的点表示，如记作e1=v1,v2。如果边vi, vj的端点有序，即它表示以vi为始点 ，vj为终点的有向边（或称弧）此时图G称之为有向图。否则为无向图。,图的表示,v4,v2,v3,v1,v2,v1,e1,124,端点，关联边，相邻 若有边e可表示为是e=vi, vj,称vi、 vj是边e的端点，反之称边e为点vi或vj关联边。 若点vi、vj与同一条边关联，称点vi和vj相邻；若边ei和ej具有公共的端点，称边 ei和ej相邻。,125,环，多重边，简单图 如果边e的两个端点相重，称该边为环。如果两个点之间的边多于一条，称为具有多重边。对无环、无多重边的图称作简单图。,次，奇点，偶点，孤立点 与某一个点vi相关联的边的数目称为点的次(也叫做度或线度)，记作d(vi)。次为奇数的点称作奇点，次为偶数的点称作偶点，次为0的点称作孤立点。 任何图中顶点次数的总合等于边数的两倍，任何图中奇点必为偶数个。,126,用点的次数来求解一笔画问题：,127,链，圈，路，回路，连通图 图中有些点和边的交替序列 = v0 , e1 ，v1, e2 ， ，ek ， vk ，若其中各边el，e2， ，ek 互不相同，且任意vi，t-1 和 vi，t (2tk)均相邻，称为链,如果链中所有的顶点 v0，v1， ，vk也不相同，这样的链称为路。,对起点与终点相重合的链称作圈，起点与终点重合的路称作回路,若在一个图中，如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称该图是不连通的,128,完全图，偶图 一个简单图中若任意两点之间均有边相连，称这样的图为完全图含有n个顶点的完全图，其边数有n(n-1)/2条,如果图的顶点能分成两个互不相交的非空集合V1和V2，使在同一集合中任意两个顶点均不相邻，称这样的图为偶图(也称二分图),如果偶图的顶点集合V1和V2之间的每一对不同顶点都有一条边相连，称这样的图为完全偶图 完全偶图中V1含m个顶点，V2含n个顶点，则其边数共mn条.,129,子图，部分图 图G1=V1，E1和图G2=V2，E2如果有V1 V2和E1 E2，称G1是G2的一个子图若有V1=V2，E1 E2，则称G1是G2的一个部分图. 注意部分图也是子图，但子图不一定是部分图,130,ex5.1 证明在9个工厂之间，不可能每个工厂只与其它3个工厂有业务联系，也不可能只有4个工厂与偶数个工厂有业务联系。,ex5.2 6个人围成圆圈就座，每个人恰好只与相邻者不相识，是否可以重新就座，使每个人都与邻座相识？,131,ex5.3 有甲、乙、丙、丁、戊、己六名运动员报名参加A、B、C、D、E、F六个项目的比赛下表中打“”的是各运动员报名参加的比赛项目问六个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛,132,5.2 树图和图的最小生成树,树图(简称树，记作T (V，E)是一类简单而十分有用的图树图的定义是无圈的连通图 这类图与大自然中树的特征相似，因而得名树图铁路专用线、管理组织机构、学科分类和一些决策过程往往都可以用树图的形式表示,2,4,3,5,1,133,性质1：任何树中必存在次为1的点,树的性质,以后称次为1的点为悬挂点，与悬挂点关联的边称为悬挂边很显然，如果从树图中拿掉悬挂点及与其关联的悬挂边，余下的点和边构成的图形仍连通且无圈，则还是一个树图,性质2：具有n个顶点的树的边数恰好为(n-1)条,性质3：任何具有n个顶点 、(n-1)条边的连通图是树,134,两点说明： （1）树是无圈连通图中边数最多的，在树图上只要任意再加上一条边，必定会出现圈 （2）由于树图是无圈的连通图，即树图的任意两个点之间有一条且仅有一条惟一通路因此树图也是最脆弱的连通图只要从树图中取走任一条边，图就不连通因此一些重要的网络不能按树的结构设计,135,图的最小生成树,定理1：图中任一个点i，若j是与i相邻点中距离最近的，则边i，j必含在该图的最小部分树内,如果G1是G2的部分图，又是树图，则称G1是G2的部分树(或支撑树)树图的各条边称为树枝(假定各边均有权重)，一般图G，含有多个部分树，其中树枝总长最小的部分树，称为该图的最小生成树(也称最小支撑树，minimum spanning tree),推论：把图的所有点分成V和 两个集合，则两集合之间连线的最短边一定包含在最小部分树。,136,用破圈法求最小生成树,方法：从网络图N中任取一回路，去掉这个回路中权数最大的一条边，得一子网络图N1在N1中再任取一回路，再去掉回路中权数最大的一条边，得N2如此继续下去，一直到剩下的子图中不再含回路止该子图就是N的最小部分树,v1,v2,v3,v5,v7,v6,v4,5,2,7,2,7,4,2,6,3,1,6,137,5.3 最短路问题,最短路问题，一般来说就是从给定的网络图中找出任意两点之间权数最短的一条路。权数可以是距离、时间、费用等。 有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划问题，也可以归结为求最短路问题。,求最短路有两种算法，一是求从某一点到其他各点之间最短距离的Dijkstra（1959）算法，另一种是求网络图上任意两点之间最短距离的矩阵算法。,138,Dijkstra算法(标号算法)的基本思路和步骤,Dijkstra算法由荷兰计算机大师Dijkstra于1959年提出，可用于求解指定两点间的最短路，或从指定点到其余点的最短路，目前被认为是求无负权网络最短路的最好算法。,139,2,4,3,5,1,全局最短，局部必最短。,若用dij表示图中两相邻点i和j的距离，若i和j不相邻，令dij =，显然dii =0，若用Lsi表示从s到i点的最短距离，现要求从s点到某一点t的最短路，用Dijkstra 算法的步骤如下：,140,（1）从点s出发，因Lss=0，将此值标在s旁的小方框内，表示s点已经标号；,（2）从s点出发，找出与s相邻的点中距离最小的一个，设为r,将Lsr = Lss +dsr的值标在r旁的小方框内，表明点r已有标号；,（3）从已标号的点出发，找出与这些点相邻的所有未标号点p，若有Lsp = min Lss+ dsp; Lsr + drp,则对p点标号，并将Lsp的值标注在p旁小方框中； （4）重复第3步，一直到t点得到标号为止。,141,ex5.5 一艘货轮在A港装货后驶往F港，中途需靠港加油和淡水，从A港到F港全部可能的航线及距离如下图所示，F港有三个码头F1、F2、F3，试求最合理的停靠的码头及航线，使总路程最短。,50,A,B1,B2,C1,C2,C3,D1,D2,F1,F2,F3,45,20,30,60,40,30,50,60,40,30,55,50,30,20,40,30,142,ex5.4 某工厂使用一台设备，每年年初工厂都要作出决策，如果继续使用旧的，要付维修费，若购买新设备，要付购买费。试制定一个5年的更新计划，使总支出最少。 已知设备在各年的购买费，及不同机器役龄时的残值与维修费，如下表所示：,143,Floyd算法（矩阵算法）,以任意两点i,j间的距离来构造矩阵：D=（d i j）n n，若i,j 相邻则d i j= l i j ,不相邻则 d i j = ，显然 d i i = 0。,144,v1,v2,v3,v5,v7,v6,v4,5,2,7,2,7,4,2,6,3,1,6,145,ex5.5 已知某地区的交通网络如下图所示，其中点代表居民小区，边代表公路，权值为公路距离，问区中心医院应该建在哪