运筹学48复习指导

1、运筹学复习指导,经管类48课时 2015年,试题类型,判断题 16分 选择题15分 分析解答题 60 分 实际问题建模题 9分,考试内容及分值（1）,第一章 线性规划与单纯形法（25分） 1、了解线性规划问题及其数学模型，理解线性规划模型的基本概念，线性规划的解的基本性质和单纯形法的基本原理； 2、掌握线性规划的可行解、基可行解、最优解、基等重要概念、线性规划的标准形式、单纯形表的步骤和解的类型的判定； 3、熟练掌握线性规划的图解法、单纯形法、大M法、两阶段法、线性规划问题的建模。,考试内容及分值（2）,第二章 对偶理论与灵敏度分析 （15分） 1、了解对偶问题的意义，理解对偶性质、对偶单纯形

2、法的基本原理； 2、掌握原问题与其对偶问题的对偶关系、对偶理论、影子价格的经济解释、对偶单纯形法和； 3、熟练掌握弱（强）对偶定理、互补松驰定理、灵敏度分析。,考试内容及分值（3）,第三章 运输问题 （15分） 1、了解运输问题的数学模型的特点，理解表上作业法和单纯形法的联系； 2、掌握运输问题模型的结构，表上作业法的基本原理和步骤，产销不平衡的运输问题的概念及其模型的结构，表上作业法求解产销不平衡的运输问题的方法； 、熟练掌握求解运输问题的表上作业法求解产销平衡（不平衡）运输问题，以及实际问题的建模与LINGO求解。,考试内容及分值（4）,第四章 整数规划 （ 15分） 了解整数规划的数学模

3、型及特点，理解整数规划的分支定界方法的基本思想。 掌握整数规划与其对应的线性规划问题之间的关系 熟练掌握求解指派问题的匈牙利法以及实际问题的建模,考试内容及分值（5）,第五章 目标规划（10分） 了解目标规划的基本概念。 掌握目标规划的图解法； 熟练掌握目标规划的建模。,考试内容及分值（6）,第六章 图与网络分析 （ 15分） 了解图与网络的基本知识 掌握树的概念与性质，最大流问题中割集、割量和增广链等概念和判定； 熟练掌握求解最小树问题、最短路问题、最大流问题,考试内容及分值（7）,第七章 计划评审方法（10分） 1、理解PERT网络中作业、事件、关键路线和关键作业等概念； 2、掌握PERT

4、网络的优化，以及三点估计法、期望作业时间和方差计算公式； 3、熟练掌握实际问题的PERT网络模型的构建，时间参数的计算和关键路线的确定。,考点详解（1）,简单线性规划模型及其图解法,常山机器厂生产 I、II 两型产品.这两型产品都分别要在A、B、C三种不同设备上加工.按工艺规定,生产每件产品的单位利润、消耗三种设备的工时以及各种设备工时的限额如表2-1所示，如何安排生产才能使总的利润最大？,最优解：x1=3 x2=3,考点详解（2）,线性规划模型建立方法：列表分析数据及其相互关系，合理选择决策变量，构建目标函数,找出所有约束条件,某工地需要30套三角架,每套需要1.4米长的钢材毛坯2根，3米长

5、的毛坯2根以及1.7米长的毛坯1根.仓库现有长6.5米的钢材.应如何下料,使消耗的钢材最少？,某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下表。设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?,线性规划问题的标准形式如式：,考点详解（3）,将下列线性规划模型化为标准形式.,A=(aij)为约束方程组的mn阶系数矩阵(设nm),且A的秩为m.若矩阵B是A的一个m阶可逆子矩阵,则称B是线性规划问题的一个基矩阵(简称为基) 基解：某一确定的基B，令非基变量等于零，由约束条件方程AX=b解出基变量

6、，称这组解为基解。 基解的总数不会超过 个,在每个基解中取值非0的变量个数不会大于m.,考点详解（4）,线性规划模型的基本概念与性质,基可行解 满足变量非负取值的基解称为基可行解(或基本可行解). 可行基 对应于基可行解的基称为可行基. 基最优解 使目标函数达到最大值的基可行解称为基最优解. 最优基 对应于基最优解的基称为最优基.,最优解,基本最优解,线性规划各类解的关系,线性规划解的性质 定理2.1 若线性规划问题存在可行域,则其可行域一定是凸集. 引理2.1 线性规划问题的可行解X为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的. 定理2.2 线性规划模型的基可行解对应其可行

7、域的顶点. 定理2.3 若线性规划模型有最优解,则一定存在一个基可行解为最优解. 定理2.4 若可行域有界,则线性规划的目标函数一定可以在可行域的顶点上达到最优.,单纯形法适用的问题 约束条件全部为，右边常数全部为非负，对目标函数的系数没有要求。 对偶单纯形法应用的条件 约束条件中至少有一个是，相应的右边常数为非负，目标函数系数全部为非负。,min z=3x1-2x2 s.t. x1+2x212 2x1+ x218 x1,x20,min z=3x1+2x2 s.t. x1+2x212 2x1+ x218 x1,x20,考点详解（5）,单纯形法的计算步骤,例10 用单纯形法求解,解：先标准化,取

8、A中后3列对应的单位矩阵为基, 得到初始基可行解X=(0,0,12,16,15)T,单纯形法的计算步骤,列出初始单纯形表,由上表可知（？），初始基可行解X=(0,0,12,16,15)T , 因变量x1,x2的检验数大于0，故该解不为最优解。 问：哪一个变量选作入基变量？哪一个选作出基变量？,单纯形法的计算步骤,新的单纯形表,对应新的基可行解X=(0,3,6,16,0)T. 因变量x1的检验数大于0，故该解不为最优解。,单纯形法的计算步骤,新的单纯形表,所有检验数均非正,表明X=(3,3,0,4,0)T为最优解,此时zmax=15. 进一步由于非基变量的检验数全小于0, 该问题是唯一最优解.,

9、单纯形法的进一步讨论两阶段法,先化原问题为标准形：略 第一阶段的线性规划问题可写为：,例 用 两阶段法求解：,第一阶段单纯形法迭代的过程见下表 （注意：没有化为极大化问题）,第一阶段问题的最优解为X=(0, 1, 1, 12, 0, 0, 0),第一阶段问题的最优单纯表为,单纯形法的进一步讨论两阶段法,第一阶段问题的最优解为X=(0, 1, 1, 12, 0, 0, 0)，其中人工变量为0，X=(0, 1, 1, 12, 0)为原问题的可行解，但不一定是最优解，故转第二阶段。 第二阶段： 在第一阶段的最终表中，去掉人工变量，将目标函数的系数换成原问题的目标函数系数，作为第二阶段计算的初始表（用

10、单纯形法计算），即求解如下问题：,单纯形法的进一步讨论两阶段法,第二阶段：,原问题的最优解为（4 1 9 0 0），目标函数 Z = 2,考点详解（6）,单纯形法 的 矩阵描述,考点详解（7）,初始单纯形表,最终单纯形表,初始表中的基变量是x3, x4, x5，它们在最终表的系数列P3, P4, P5构成矩阵B-1,min z= 2x1+4x2-x3 s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15,max y=6w1+12w2+8w3+15w4 s.t. 3w1- w2+2w3+ w4 2 -w1+2w2+ w3+3w4

11、4 2w1- 3w2+2w3- w4 -1 w1 0,w2 ,w3 0,w4 0,=,unr,=,x10,x20,x3: unr,考点详解（8）,对偶问题的基本性质,弱对偶性(或弱对偶原理)：设X和Y分别是问题P 和D的可行解,则必有CXbTY. 最优性：若X*和Y*分别是P和D的可行解且CX* = bTY*,则X*,Y*分别是问题P和D的最优解. 无界性：若原问题有无界解,则对偶问题无可行解.或叙述为,若对偶问题有无界解,则原问题无可行解. 注意：无界性的逆命题不成立.即若原问题无可行解,则对偶问题可能无可行解,也可能有无界解,强对偶性(对偶定理)：若原问题有最优解,则对偶问题一定有最优解,

12、且有相同的目标函数值即 zmax=wmin . 注意：（1）若原问题有最优解,则在最优单纯形表中,原问题的最优解在第三列而对偶问题的最优解是松弛变量检验数的相反数. （2）通常把最优解中取值非零的变量称为松变量,而取值为0的变量称为紧变量；将最优解代入约束条件中成为严格不等式的称为松约束,而成为严格等式的称为紧约束.,max z=3x1+4x2-x3 s.t. 4x1+2x2+5x338 -x1+3x2- x318 2x1- x2+3x326 3x1+ x2- 2x3 10 x1, x2, x30,min y=38w1+18w2+26w3+10w4 s.t. 4w1- w2+2w3+3w4 3

13、 2w1+3w2- w3+ w4 4 5w1- w2+3w3-2w4 -1 w10,w20,w30,w40,| 变量 | 松弛变量 | (x1, x2, x3, x4, x5, x6, x7) ( 0, 19, 0, 0, 39, 45, 9 ),( 2, 0, 0, 0, 5, 0, 11) (w1, w2, w3, w4, w5, w6, w7) | 变量 |松弛变量|,互补松弛关系,+x4 =38,-x5 =18,+x6 =26,-x7=10,x4, x5, x6, x7 0,-w5 =3 3,-w6 =4,-w7 =-1,w5,w6,w70,原始问题,对偶问题,原始问题的每一个变量和对

14、偶问题相应的松弛变量组成互补松弛对，每一对变量中至少有一个等于0。,对偶问题的每一个变量和原始问题相应的松弛变量组成互补松弛对，每一对变量中至少有一个等于0。,(互补松弛定理)：若和分别是原问题和对偶问题的可行解，它们为最优解的充要条件是， 和 。 互补松弛性可以叙述为,在最优解下原问题中的松变量对应对偶问题中的紧约束,而原问题中的松约束对应对偶问题中的紧变量.常把互补松弛性称为“由松得紧性”.,考点详解（9）,单纯形表的灵敏度分析 目标函数中变量系数的灵敏度分析（1）非基变量系数的灵敏度分析 要使原来的最优解仍为最优解，只要 （2）基变量系数的灵敏度分析要使原来的最优解仍为最优解，只要 约束

15、方程中常数项的灵敏度分析基变换矩阵的确定要使原来的最优基仍为最优基，只要,例 已知线性规划问题的标准形式为：,问：（1）当c1由-1变为4时，求新问题的最优解。（2）讨论c2在什么范围内变化时，原有的最优解仍是最优解。,其最优单纯形表如下所示,考点详解（10）,运输问题的建模,考点详解（11）,运输问题的表上作业法 一、闭回路的特征： （1）每一顶点都是“转角点”； （2）每一条边都是水平或垂直的； （3）每一行（一列）若有闭回路顶点，则必有两个。 二、基本可行解的特征： （1）基变量的个数为（m+n1）个。 （2）（m+n1）个变量组成基变量组的充分必要条件是：它不构成闭回路。 三、初始基本

16、可行解的求法最小元素法 最小元素法是从单位运价表中最小的运价开始确定产销关系，依次类推，直到得到初始解为止。,给出运输问题的 初始基础可行解,伏格尔法,最小元素法,求出各非基 变量的检验数,位势法,闭回路法,确定离基变量,确定进基变量,调整运量,用最小元素法得到一个初始基础可行解,125,85,180,30,35,75,7,求非基变量x11的检验数,125,85,180,30,35,75,7,8,求非基变量x14的检验数,125,85,180,30,35,75,7,8,4,求非基变量x22的检验数,125,85,180,30,35,75,7,8,4,7,求非基变量x31的检验数,125,85,

17、180,30,35,75,7,8,4,7,-1,求非基变量x32的检验数,125,85,180,30,35,75,7,8,4,7,-1,-4,求非基变量x33的检验数,125,85,180,30,35,75,7,8,6,7,-1,-4,x33=75进基，x23=0离基，x24=30+75=105，x34=180-75=105,确定进基变量和离基变量,125,85,105,35,8,求非基变量x11的检验数,3,4,4,7,3,得到最优解：x12=85, x13=35, x21=125, x24=105, x33=75, x34=105 min z = 3660,考点详解（12）,指派问题 匈牙

18、利法的依据： 从系数矩阵（cij）的一行（列）各元素分别减去该行（列）的最小元素得到新矩阵（bij），以（bij）为系数矩阵的最优解xij和原问题的最优解相同。 匈牙利法基于这样一个明显的事实：如果系数矩阵的所有元素满足cij0，而其中有n个位于不同行不同列的一组0元素，则只要令对应于这些0元素位置的xij1，其余的xij0，就得到最优解。,ij,指派问题的匈牙利法求解步骤：,1) 变换指派问题的系数矩阵(cij)为(bij)，使在(bij)的各行各列中都出现0元素，即 从(cij)的每行元素都减去该行的最小元素； 再从所得新系数矩阵的每列元素中减去该列的最小元素。,2) 进行试指派，以寻求最

19、优解。 在(bij)中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。,确定独立零元素及最少直线覆盖： 寻找不同行不同列的0元素（称为独立零元素），圈之；将所在行和列其它0元素划掉。具体步骤如下： (1) 从第一行开始，若该行只有一个“0”元素，就对这个“0”元素打上“( )”，表示该人只能做该任务，对“”元素所在列画一条直线，表示该任务已经安排；若该行有多个“0”元素（已划去的不计在内），则转下一行，一直到最后一行为止； (2) 从第一列开始，若该列只有一个“0”元素，就对这个“0”元素打上“( )”，对“”元素

20、所在行画一条直线；若该列有多个“0”元素（已划去的不计在内），则转下一列，一直到最后一列为止。,(3) 重复(1)，(2)，可能出现三种情况： 矩阵每行都有一个“(0)”元素，很显然，按上述步骤得到的“(0)”元素都位于不同行、不同列，只要令对应“(0)”元素的，其余的，就得到问题的最优解； 有多于两行或两列存在两个以上“0”元素，即出现了“0”元素的闭合回路，这时可顺着闭回路的走向，对每个间隔的零元素打“( )”号，然后对“”元素所在列画一条直线，如：, 矩阵中所有“0”元素或被打上“( )”或被划去，但不是每一行都有“(0)”，由于尚未找到最优解，需要继续往下进行操作。 3) 调整方案 在

21、没有被直线通过的所有元素中找出最小值，没有被直线通过的所有元素减去这个最小元素；直线交点处的元素加上这个最小值。新系数矩阵的最优解和原问题仍相同。转回第2步。,考点详解（12）,指派问题 匈牙利法的依据： 从系数矩阵（cij）的一行（列）各元素分别减去该行（列）的最小元素得到新矩阵（bij），以（bij）为系数矩阵的最优解xij和原问题的最优解相同。 指派问题的一般解法如下：第一步：使系数矩阵出现0元素。 （1）列一张方阵的系数矩阵表； （2）如果题目求极大值，则需求缩减矩阵 （3）每行元素减去该行最小元素； （4）再从所得系数矩阵的每列元素中减去该列的最小元素。 若某行（列）已有0元素，就不

22、断再减了。,ij,第二步：进行试指派，以寻求最优解 试找不同行不同列的0元素常用方法： 由有0元素最少的行开始，圈出一个0元素，用0表示，然后划去同行同列的其它0元素，用表示。这样依次做完各行，已划去的就不能再圈了。如果这样能得到n个0，就得最优解。如果圈出的0不够n个，解题过程就没完，继续第三步。 第三步：作能覆盖所有0元素的最少数的直线集合。 （1）对没有0的行打号； （2）对已打号的行中所有含0元素的列打号； （3）再对打有号的列中有0的行打号； （4）重复（2）、（3）直到得不出新的打号的行、列为止； （5）对没有打号的行画一横线，有打号的列画一纵线，这就得到覆盖所有0元素的最少直线数

23、。,第四步：变换矩阵使0元素移动，以达到每行都有元素的目的。为此在没有被直线覆盖的部分中找出最小元素：（1）对打行，各元素都减去这最小元素；（2）对打列，各元素都加这最小元素，得到新矩阵。如已有n个不同行不同列的0元素，则求解完成，否则回到第三步重复进行。,分配问题与匈牙利法,例4.6 有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？,分配问题与匈牙利法,解：1）变换系数矩阵，增加0元素。,5,2）试指派（找独立0元素）,找到 3 个独立零元素 但 m = 3

24、 n = 4,分配问题与匈牙利法,3）作最少的直线覆盖所有0元素,独立零元素的个数m等于最少直线数l，即lm=3n=4；,4）没有被直线通过的元素中选择最小值为1，变换系数矩阵，将没有被直线通过的所有元素减去这个最小元素；直线交点处的元素加上这个最小值。得到新的矩阵，重复2）步进行试指派,分配问题与匈牙利法,试指派,得到4个独立零元素， 所以最优解矩阵为：,即完成4个任务的总时间最少为：241+8=15,分配问题与匈牙利法,例4.8 已知五人分别完成五项工作耗费如下表，求最优分配方案。,分配问题与匈牙利法,-1,-2,解：1）变换系数矩阵，增加0元素。,分配问题与匈牙利法,2）试指派（找独立0

25、元素）,独立0元素的个数l45，故画直线调整矩阵。,分配问题与匈牙利法,选择直线外的最小元素为1；直线外元素减1，直线交点元素加1，其他保持不变。,分配问题与匈牙利法,l =m=4 n=5,选择直线外最小元素为1，直线外元素减1，直线交点元素加1，其他保持不变，得到新的系数矩阵。,分配问题与匈牙利法,总费用为=5+7+6+6+4=28,注：此问题有多个最优解,分配问题与匈牙利法,总费用为=7+9+4+3+5=28,分配问题与匈牙利法,总费用为=8+9+4+3+4=28,考点详解（13）,目标规划问题及其数学模型,1. 设置偏差变量，用来表明实际值同目标值之间的差异,偏差变量用下列符号表示：,d

26、+超出目标的偏差，称正偏差变量 d-未达到目标的偏差，称负偏差变量,正负偏差变量两者必有一个为0。 当实际值超出目标值时： d+0, d-=0; 当实际值未达到目标值时： d+=0, d-0; 当实际值同目标值恰好一致时： d+=0, d-=0;,2. 统一处理目标和约束,对有严格限制的资源使用建立系统约束，数学形式同线性规划中的约束条件。,对不严格限制的约束，连同原线性规划建模时的目标，均通过目标约束来表达。,3. 设置目标的优先级与权系数,在一个目标规划的模型中，为达到某一目标可牺牲其他一些目标，称这些目标是属于不同层次的优先级。优先级层次的高低可分别通过优先因子P1,P2,表示。 对于同

27、一层次优先级的不同目标，按其重要程度可分别乘上不同的权系数。权系数是一个个具体数字，乘上的权系数越大，表明该目标越重要。,目标规划建模的步骤：,1、根据要研究的问题所提出的各目标与条件，列出绝对约束和目标约束（即约束左边加上负偏差变量与正偏差变量之差）；,3、根据目标要求，写出目标函数。,2、给各目标赋予相应的优先因子 Pi（i=1.2L）。对同一优先等级中的各偏差变量，若需要可按其重要程度的不同，赋予相应的权系数。,目标规划的目标函数,从决策者的要求来分析，总希望得到的结果与规定的指标值之间的偏差量愈小愈好。由此可构造一个使总偏差量为最小化的目标函数，即 min Z = f（d +，d -）

28、 其中 f 由各目标约束的正、负偏差变量及相应的优先因子和权系数构成。,（1） 要求恰好达到目标值，即正、负偏差变量都要尽可能地小 。构造的目标函数是 min Z = f（ d + d - ） （2） 要求不超过目标值，但允许达不到目标值，即只有使正偏差量要尽可能地小（实现最少或为零） min Z = f（ d +） （3） 要求超过目标值，即超过量不限。要求超额完成规定目标，要实现负偏差量为零或为最小 min Z = f（ d -）,目标规划的目标函数基本形式有三种：,练习 某厂生产、两种产品，有关数据如表所示。试求获利最大的生产方案？,并在此基础上考虑如下各级目标： 1、产品I的产量低于产

29、品的产量； 2、充分利用设备有效台时，不加班； 3、利润不小于 56 元。,解：设生产、 各x1、x2件，则总利润为8x1+10 x2 ，实际原材料消耗量为2x1+x2， 设备实际使用台时为 x1+2x2 ，根据题目要求，有 绝对约束： 2x1+x2 11， x1, x2 0,P1: 产品的产量不低于产品的产量； P2: 充分利用设备有效台时，不加班； P3: 利润不小于 56 元。,目标约束：x1 - x2 + d1- - d1+ = 0 x1 +2x2 + d2- - d2+ =10 8x1 +10 x2 + d3- - d3+ =56 di- ,di+ 0,目标函数：,第二目标P2 ：

30、P2 (d2- + d2+ ),第三目标P3 ： P3 d3-,第一目标P1: P1 d1+,目标规划模型：,考点详解（14）,图与网络的基本概念 无向图G=(V,E)，其中V点集，E边集；链；连通图； 有向图G=(V,A)，其中V点集，A弧集；路；回路； 赋权图G=(V,E,W)或G=(V,A,W), 其中wij为边（弧）vij的权重； 网络有一收点和发点的有向赋权图； 以点v为端点的边的个数称为点v的次； 任一个图中，所有顶点次的和，等于边数的二倍； 任一个图中，奇点的个数必为偶数；,欧拉回路,定义 连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条道路为欧拉道路。若存在一条回路经

31、过每边一次也仅一次，则称这条回路为欧拉回路。 具有欧拉回路的图称为欧拉图（E图）。,定理3 无向连通图G是欧拉图，当且仅当G中无奇点,欧拉回路,推论1 无向连通图G为欧拉图，当且仅当G的边集可以划分为若干个初等回路。 推论2 无向连通图G中有欧拉道路，当且仅当G中恰好有两个奇点。,树是一个无圈的连通图； 生成子图是一个无向图G=(V,E)删除所有的边或部分的边所获得的子图； 在树中，任意两顶点之间必有一条且仅有一条链； 在树中去掉任一条边，则树成为不连通图； 在树中不相邻的两个顶点间添上一条边，恰好得到一个圈； 设T为p个顶点的一棵树，则T的边数为p1条； 任一个连通图必有生成（部分）树；,考

32、点详解（15）,最小支撑树（最小生成树）设有一连通图G =（V，E），对于每一条边e = vi，vj，有一个权wij0。最小部分树问题就是求图G的生成树T *，使得权重之和取得极小值。 算法1 （Kruskal算法）每步从未选的边中，选一条最小权的边，使与已选边不构成圈。 算法2（破圈法）任取一圈，从圈上去掉一条最大权的边，在余下的图中，重复这个步骤，直到无圈时为止，即可求出最小树。,练习：设A、B、C、D、E、F、G七个城市之间的公路交通情况如下. 其中线旁的数字表示距离，现要求在它们之间沿公路架上电缆，使各个城市都能相互通讯，问如何架线，使线路长度为最短？,最小生成树问题,最小生成树的权为

33、14,Dijkstra算法基于以下原理：最短路的任意两点间的路仍是最短的。 算法的计算过程是从v0出发，依次向外探寻最短路。,例如：假定v1v2 v3 v4是v1 v4的最短路，则v1 v2 v3一定是v1 v3的最短路，v2 v3 v4也一定是v2 v4的最短路。,考点详解（16）,通常采用节点标号法实施狄克斯屈拉(Dijkstra)算法。 节点标号有两种状态：永久标号和临时标号。,记Sk为第k步迭代时相互连通的顶点集合，Tk=VSk 设vi Sk，vjTk，记uj为起点v0到节点vj的最短距离，dij为边i,j(或弧(i,j)的权。 算法给与已标号点vi相邻的点vj的临时标号： （1）若v

34、j无标号，则给vj 临时标号(ui+dij, vi)； （2）若vj有标号，且ujui+dij，则将vj临时标号修改为(ui+dij, vi)，否则，不变更标号。 从节点的临时标号中选择路长最短的永久标号（若有多个，任选其一）。,狄克斯屈拉(Dijkstra)算法： Step0：初始化k=0, ；给起点永久标号0, vs。 Step1：考虑与节点viSk相邻的没有永久标号的节点vjTk： （1）若vj无标号，则给vj 临时标号(ui+dij, vi)； （2）若vj有标号，且ujui+dij，则将vj临时标号修改为(ui+dij, vi)。 Step2：若所有节点都获得永久标号，则算法终止；否

35、则，从节点的临时标号中选择路长最短的标号（若有多个，任选其一），如uk最小，将vk临时标号(uk, vi)状态修改为永久标号uk, vi 。置Sk= Skvk, Tk=Tkvk ，返回step 1。,例 求v1到v6的最短路,（1）首先给v1以P标号：0，V1,0，V1,永久标号以 形式标在结点旁边 0：表示从V1到该点的最短距离 V1：表示从V1到该点的最短路中上一个顶点。,狄克斯屈拉(Dijkstra)算法,0，V1,（2） S：V1 T：V2，V3，V4，V5，V6 求出（S T）所有弧， 分别计算： S12 =0 + 3=3 S13 =0 + 5=5 Min Sij=S12=3 给V2

36、 标号3，V1,3，V1,狄克斯屈拉(Dijkstra)算法,0，V1,（3） S：V1，V2 T：V3，V4，V5，V6 求出（S T）所有弧，分别计算： S24 =3 + 6=9 S23 =3 + 1=4 S13 =0 + 5=5 Min Sij=S23=4 给V3 标号4，V2,3，V1,4，V2,狄克斯屈拉(Dijkstra)算法,0，V1,（4） S：V1，V2，V3 T：V4，V5，V6 求出（S T）所有弧，分别计算： S24 =3 + 6=9 S34 =4 + 4=8 S35 =4 + 1=5 Min Sij=S35=5 给V5 标号5，V3,3，V1,4，V2,5，V3,狄克

37、斯屈拉(Dijkstra)算法,0，V1,（5） S：V1，V2，V3，V5 T：V4，V6 求出（S T）所有弧，分别计算： S24 =3 + 6=9 S34 =4 + 4=8 S54 =5 + 2=7 S56=5 + 6=11 Min Sij=S54 给V4 标号7，V5,3，V1,4，V2,5，V3,7，V5,狄克斯屈拉(Dijkstra)算法,0，V1,（6） S：V1，V2，V3，V4，V5 T：V6 求出（S T）所有弧， 分别计算： S46 =7 + 3=10 S56= 5 + 6=11 Min Sij=S46 给V6 标号（10，V4）,3，V1,4，V2,5，V3,7，V5,

38、10，V4,狄克斯屈拉(Dijkstra)算法,(7) 标出最短路 最短路径是： V1V2V3V5V4V6 路长10。同时得到起点到其余各点的最短路。,(10),狄克斯屈拉(Dijkstra)算法,最短路问题,注：无向图最短路的求法只将上述步骤2将弧改成边即可。,注意：Dijkstra算法只适用于所有wij 0的情形，当赋权有向图中存在负权时，则算法失效。,如右图所示中按dijkstra算法可得P(v1)=5为从vsv1的最短路长显然是错误的，从vsv2v1路长只有3。,v2,vs,v1,5,-5,8,考点详解（16）,最大流问题基本概念： 1. 容量网络：队网络上的每条弧(vi,vj)都给出

39、一个最大的通过能力，称为该弧的容量，简记为cij。容量网络中通常规定一个发点(也称源点，记为vs)和一个收点(也称汇点，记为vt)，网络中其他点称为中间点。,vs,vt,4,8,4,4,1,2,2,6,7,9,考点详解（17）,2. 流与可行流 流是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上的载量记为fij。若fij=0，称为零流。 满足以下条件的一组流称为可行流。,容量限制条件。容量网络上所有的弧满足：0fijcij 中间点平衡条件。,若以v(f)表示网络中从vsvt的流量，则有：,最大流问题可归结为如下线性规划问题：,3. 网络的最大流 是指网络中从发点到收点之间允许通过的最大

40、流量的可行流。,最大流问题,4. 割集,容量网络G =（V，E，C），vs为始点，vt为终点。如果把V分成两个非空集合 ，使 ，则所有始点属于S，而终点属于 的弧的集合，称为由S决定的割集,记作 。割集中由S到 所有前向弧的容量之和，称为这个割集的容量，记为,最大流最小割定理： 对于任一容量网络，从发点到收点的最大流量等于最小割量。,瓶颈原理:由发点vs到收点vt任一可行流量V(f)必受割集 容量的限制，即有：,容量最小的割集称为最小割集.,最大流问题,我们可用瓶颈原理判别可行流是否是最大流。,设是网络D中连接发点s和收点vt的一条链。定义链的方向是从vs到vt，于是链上的弧被分为两类：,最大

41、流问题,一是弧的方向与链的方向相同，叫做前向弧，前向弧的集合记做+。 二是弧的方向与链的方向相反，叫做后向弧，后向弧的集合记做-。,设流f =fij是网络D上的一个可行流。我们把D中: fij=cij 的弧叫做饱和弧 fij0 的弧叫做非零流弧 fij=0 的弧叫做零流弧,图中，流量为可行流，(v4,v3 )是饱和弧，其他的弧是非饱和弧，并且都是非零流弧。,最大流问题,增广链：如果链满足以下条件： 1在弧（vi,vj）+上，有0=fijcij,即+中的每一条弧是非饱和弧。 2在弧（vi,vj）-上，有0fij=cij,即-中的每一条弧是非零流弧。,例如图中，链 =（vs,v1,v2,v3,v4

42、,vt） 就是一条增广链。,最大流问题,最大流问题,一般地，在一条增广链上， 若(vi, vj)是前向非饱和弧，则此弧的调整量为fij=cij-fij 若(vi, vj)是后向非零弧，则此弧的调整量为fij=fij 而增广链的调整量为,思考：如何调整？ 对增广链上所有前向弧，流量增加； 对增广链上所有后向弧，流量减少； 对非增广链上的弧，流量不变。 链=（vs,v1,v2,v3,v4,vt），调整量为3，则 调整后如右图所示：,求网络最大流的标号算法：,（1）找出第一个可行流（如零流），给发点s标号(s, ),标号中第一个字母表示弧的发点，第二个数字表示允许的最大调整量1= 。 （2）用标号的

43、方法找一条增广链,列出一个已标号点 vi 的相邻的所有未标号点； 设弧的起点为vi，若fij=cij ，则不给vj标号；若fij0，则给vj标号(-vi, j)，其中j = mini , fji ,(3) 重复第(2)步，可能出现两种结局：,标号过程中断，收点t 无法标号，说明网络中不存在增广链，目前流量为最大流。同时可以确定最小割集，记已标号的点集为V,未标号的点集合为V,(V,V)为网络的最小割； t 得到标号，反向追踪在网络中找到一条从s到t得由标号点及相应的弧连接而成的增广链。继续第(4)步。,(4) 修改流量。设原图可行流为f，收点的调整量为(t),令,得到网络上一个新的可行流f。,

44、(5) 擦除图上所有标号，重复(2-(4)步。,V4,V1,V2,V3,Vs,（2,1）,（3,0）,（4,3）,（3,3）,（5,1）,（2,2）,（5,3）,（1,1）,（1,1）,(Cij,fij),Vt,例 求网络最大流,最大流问题,解：1.标号过程。（1）首先给vs标号（0，+）,（0，+）,V4,V1,V2,V3,Vs,（2,1）,（3,0）,（4,3）,（3,3）,（5,1）,（2,2）,（5,3）,（1,1）,（1,1）,(Cij,fij),Vt,例 求网络最大流,最大流问题,（0，+）,（2）检查vs:在弧(vs,v2)上,fs2=cs3=3,不具备标号条件。在弧(vs,v1

45、)上,fs1=1cs1=5,故给v1标号(vs, l(v1),其中: l(v1)=minl(vs),(cs1-fs1)=min+,5-1=4.,(vs, 4）,V4,V1,V2,V3,Vs,（2,1）,（3,0）,（4,3）,（3,3）,（5,1）,（2,2）,（5,3）,（1,1）,（1,1）,(Cij,fij),Vt,例 求网络最大流,最大流问题,（0，+）,（3）检查v1:在弧（v1,v3）上,f13=c13=2,不具备标号条件.在弧(v2,v1)上,f21=10,故给v2标号（-v1, l(v2)）,其中l(v2)=minl(v1),f21=min4,1=1.,(vs, 4）,（-v1, 1）,V4,V1,V2,V3,Vs,（2,1）,（3,0）,（4,3）,（3,3）,（5,1）,（2,2