运筹学完整教案

《运筹学》教案（本教案适用于32课时的班级）

第一章线性规划与单纯形法1、教学计划第1次课2学时授课章节绪论；第一章第1节、第2节、第3节授课方式□√理论课□讨论课□实验课□习题课□其他课堂教学目的及要求了解线性规划模型的背景、掌握建模方法以及线性规划的标准形式。掌握两个决策变量线性规划问题可行域（凸集）、最优解的位置；了解无解（无界解、无可行解）、有解（唯一解、无穷多个解）的几何意义。课堂教学重点及难点重点：线性规划的数学模型及其标准形。在数学模型中，要求熟悉矩阵形式；在标准形中，要求学生掌握非标准形式的几种具体情形及其相应的标准化方法；如何用几何的方法求两个决策变量的线性规划问题的最优解。难点：线性规划的基本概念，例如基、基变量、基解、基可行解和可行基；多个最优解如何表示。教学过程教学过程教学方法及手段引言 运筹学模型，运筹学发展历史与现状，研究方法；考核方法与教学大纲等。1.1线性规划问题及其数学模型线性规划的数学模型：变量的确定、约束条件与目标函数。1.2线性规划问题的标准形式线性规划的标准形式及非标准形式的标准化处理。1.3线性规划问题的解基、基变量、基解、基可行解和可行基。多媒体讲解实例讲解第2次课2学时授课章节第一章第4节授课方式□√理论课□讨论课□实验课□习题课□其他课堂教学目的及要求掌握单纯形法思想以及具体操作过程。课堂教学重点及难点重点：单纯形法迭代过程：（1）换入基变量的确定；（2）换出基变量的确定；（3）判定当前解已经最优。难点：单纯形法思想。教学过程教学过程教学方法及手段1.4单纯形法单纯形数表的构造，要注意代数形式和表格形式的一一对应性。单纯形法迭代过程：（1）换入基变量的确定；（2）换出基变量的确定；（3）判定当前解已经最优。多媒体讲解实例讲解第3次课2学时授课章节第一章第5节授课方式□√理论课□讨论课□实验课□习题课□其他课堂教学目的及要求掌握人工变量法的基本思想以及大M法和两阶段法的求解。课堂教学重点及难点重点：人工变量法的基本思想。难点：大M法和两阶段法的求解。教学过程教学过程教学方法及手段1.5单纯形法的进一步讨论及小结人工变量法的思想，大M法和两阶段法的求解思路和步骤。单纯形法小结多媒体讲解实例讲解2、课件1.1线性规划问题及其数学模型线性规划模型的建立就是将现实问题用数学的语言表达出来。例1：某工厂要安排生产Ⅰ、Ⅱ两种产品，每单位产品生产所需的设备、材料消耗及其利润如下表所示。问应如何安排生产计划使工厂获利最多？ⅠⅡ设备128台时原材料A4016kg原材料B0412kg单位产品的利润（元）23解：设生产产品Ⅰ、Ⅱ的数量分别为和。首先，我们的目标是要获得最大利润，即其次，该生产计划受到一系列现实条件的约束，设备台时约束：生产所用的设备台时不得超过所拥有的设备台时，即原材料约束：生产所用的两种原材料A、B不得超过所用有的原材料总数，即非负约束：生产的产品数必然为非负的，即由此可得该问题的数学规划模型：总结：线性规划的一般建模步骤如下：（1）确定决策变量确定决策变量就是将问题中的未知量用变量来表示，如例1中的和。确定决策变量是建立数学规划模型的关键所在。（2）确定目标函数确定目标函数就是将问题所追求的目标用决策变量的函数表示出来。（3）确定约束条件将现实的约束用数学公式表示出来。线性规划数学模型的特点（1）有一个追求的目标，该目标可表示为一组变量的线性函数，根据问题的不同，追求的目标可以是最大化，也可以是最小化。（2）问题中的约束条件表示现实的限制，可以用线性等式或不等式表示。（3）问题用一组决策变量表示一种方案，一般说来，问题有多种不同的备选方案，线性规划模型正式要在这众多的方案中找到最优的决策方案（使目标函数最大或最小），从选择方案的角度看，这是规划问题，从目标函数最大或最小的角度看，这是最优化问题。1.2线性规划问题的标准形式根据问题的性质，线性规划有多种形式，目标函数有要求最大化的，也有要求最小化的；约束条件可以是“”或“”的不等式，也可以是“=”；虽然决策变量一般是非负的，但也可是无约束的，即，可以在取值。为了分析问题的简化，一般规定如下的标准形式：非标准形式转化为标准形式：（1）若目标函数要求实现最小化，则可令，可将原问题的目标函数转化为即可。（2）若约束方程为“”，则可在“”的左边加上非负的松弛变量；若约束方程为“”，则可在“”的左边减去非负的剩余变量。（3）若存在取值无约束的变量，则可令，其中，。例：将如下问题转化为标准形式：解：首先，用替换，其中，；其次，在第一个约束条件的左端加上非负的松弛变量；再次，在第二个约束条件的左端减去非负的剩余变量；最后，令，将求改为求。由此，可得标准形如下：1.3线性规划问题的解首先，将线性问题的标准形式用矩阵和向量形式表示如下：其中，；，1、可行解和最优解满足约束条件的所有解成为线性规划问题的可行解，其中，使目标函数达到最大的可行解成为最优解。2、基和基解设为约束方程组的维矩阵，其秩为。设为矩阵中的阶非奇异子矩阵（），则称为线性规划的一个基。不妨设前个变量的系数矩阵为线性规划的一个基，则为对应于这个基的基变量。用高斯消去法可求得一个解该解得非零分量的数目不大于方程个数，称为基解。3、基可行解若基解满足非负约束，则称其为基可行解。4、可行基对应于基可行解的基，成为可行基。1.4单纯形法一、单纯形表考察一种最简单的形式：目标函数最大化、所有约束条件均为“”。利用所有约束条件化为等号的方法，在每个约束条件的左端加一个松弛变量，并整理，重新对变量及系数矩阵进行编号，得将其与目标函数的变换形式组成个变量、个方程的方程组。若将看成不参与基变换的基变量，它与的系数构成一个基，利用初等变换将变为零，则可得据此，可设计如下的数表…………1…0…0…0……………0…1…0……列表示基变量，在这里为；列为基变量对应的价值系数；列为约束方程的右端项；行为所有变量的价值系数；列的数字是在确定换入变量后，按规则计算后填入；最后一行为各变量的检验数，尤其要注意的是非基变量的检验数。例，求解首先将其转换为标准形式，构造初始单纯形表如下：230000812100401640010-0120[4]001323000由上表可得初始基可行解由于和的检验数大于零，表明上述解不是最优解，由于的检验数更大，所以，先以为换入变量。根据规则，可确定为换出变量，计算得新表如下：2300002[1]010-1/220164001043301001/4-2000-3/4可得新解，目标函数取值。的检验数为2，换入。根据规则，可确定为换出变量，计算得新表如下：23000221010-1/2-0800-41[2]43301001/41200-201/4得新解，目标函数取值。的检验数为1/4，换入。根据规则，可确定为换出变量，计算得：23000241001/400400-21/2132011/2-1/8000-3/2-1/80得解，目标函数取值。由于所有的检验都小于零，达到最优。PS：如果目标函数是求最小化，则，检验数的最优准则为检验数大于零。1.5单纯形法的进一步讨论及小结一、人工变量法如果初始约束条件不全是小于等于号，则不能直接得到初始基（单位基）和初始基可行解，此时必须要构造人工变量。在迭代结束后，如果最后基变量中不再含有非零的人工变量，表示原问题有解；反之，则表示无可行解。例：在第一个约束条件中加入松弛变量；在第二个约束条件中加入剩余变量和人工变量；在第三个约束条件中加入人工变量。（1）大M法：在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对目标函数值不产生影响，可假定人工变量在目标函数中的系数为（-M）（M为很大的正数），这样在目标函数要实现最大化时，必须将人工变量从基变量中换出，否则目标函数不会实现最大化。对上例求解，加入人工变量后，规划问题变成然后，利用单纯形法求解，详见P33。（2）两阶段法第一阶段：不考虑原问题是否有基可行解；给原线性规划问题加上人工变量后，构造仅含人工变量的目标函数和要求实现最小化；然后用单纯形法求解，若得到该规划的最优解为零，说明原问题存在基可行解，否则原问题无可行解，停止计算。第二阶段：将第一阶段的最重计算表出去人工变量，换回原目标函数的系数作为第二阶段计算的初始表，利用单纯形法求解。前一个例子的两阶段法求解如下：构造出第一阶段的数学模型如下：00000110111-2110001113-4120-1103/211-20[1]000116-1-3010000000110103-20100-1-110[1]00-11-2101-2010001-0-10010000000110123001-22-5-010100-11-2101-2010001-0000011得最优解。由于人工变量，说明是原问题的基可行解，可进行第二阶段运算。利用单纯形法，从下表开始：-31100012[3]001-2-110100-1111-20100--10001-31100-341001/3-2/3-110100-11190012/3-4/3-0001/31/3二、解的退化所有的检验数均1、基变量中有非零的人工变量，无可行解；2、某非基变量的检验数为零，有无穷多解；对于任一检验数，若对应的系数向量，则有无界解。单纯形法小结变量不需处理令；无约束令，约束条件不需处理约束条件两端同乘-1加松弛变量=加人工变量减剩余变量，加人工变量目标函数加入变量的系数松弛变量0人工变量

第三章运输问题1、教学计划第4次课2学时授课章节第三章授课方式□√理论课□讨论课□实验课□习题课□其他课堂教学目的及要求掌握运输问题的模型特点；熟悉表上作业法的基本步骤如初始调运方案的确定，非基变量检验数的确定方法，当前解是否最优解的判断，闭回路调整方法；非平衡运输问题的求解。课堂教学重点及难点重点：初始调运方案的确定，非基变量检验数的确定，判断当前解是否最优解，闭回路调整方法，非平衡运输问题的求解方法。难点：初始基可行解的确定、判断，非平衡问题的求解思路。教学过程教学过程教学方法及手段3.1运输问题的提出及其模型特征运输问题的提出背景及其模型特征3.2运输问题的求解：表上作业法表上作业法的思路和步骤如初始基可行解的确定（最小元素法和伏格尔法），最优解的判断方法，闭回路调整方法。3.3产销不平衡的运输问题将不平衡问题转化为平衡问题。多媒体讲解实例讲解2、课件3.1运输问题的提出及其模型特征1、背景大规模的物资调运，将物资从生产地点运往消费地点，要求在现有的交通网络下，制定出总费用最小的运输方案。2、模型特征销地产地12…产量1…2…………..……销量…个变量，个约束方程，但由于总产量等于总销量的关系存在，所以，独立的约束方程为，因此，其可行解中的基变量个数必然是。系数矩阵：变量的系数向量除第个分量和第个为1外其余为零。3.2运输问题的求解：表上作业法表上作业法实际上是单纯形法在求解运输问题时的一个简化，主要步骤：（1）找出初始基可行解：最小元素法和伏格尔（Vogel）法最小元素法：优先满足运价最小的供销关系例：销地产地B1B2B3B4产量（吨）A13113107A219284A3741059销量（吨）3656销地产地B1B2B3B4产量（吨）A13113107A2eq\o\ac(○,1)（3）9284A3741059销量（吨）3656销地产地B1B2B3B4产量（吨）A13113107A2eq\o\ac(○,1)（3）9eq\o\ac(○,2)（1）84A3741059销量（吨）3656销地产地B1B2B3B4产量（吨）A1311eq\o\ac(○,3)（4）107A2eq\o\ac(○,1)（3）9eq\o\ac(○,2)（1）84A3741059销量（吨）3656销地产地B1B2B3B4产量（吨）A1311eq\o\ac(○,3)（4）107A2eq\o\ac(○,1)（3）9eq\o\ac(○,2)（1）84A37eq\o\ac(○,4)（6）1059销量（吨）3656销地产地B1B2B3B4产量（吨）A1311eq\o\ac(○,3)（4）10（3）7A2eq\o\ac(○,1)（3）9eq\o\ac(○,2)（1）84A37eq\o\ac(○,4)（6）10eq\o\ac(○,5)（3）9销量（吨）3656销地产地B1B2B3B4产量（吨）A1437A2314A3639销量（吨）3656伏格尔法：优先满足最小运价与次小运价差值最大的行、列中的最小运价所对应的供销关系。销地产地B1B2B3B4行差A13113100A219281A37eq\o\ac(○,4)1051列差2513（2）求各非基变量（空格）的检验数。闭回路法：首先找到与空格对应的闭回路，规则是从要检验空格出发用水平或垂直线向前滑，碰到数字格转90度（也可不转，空格处绝不转），最后回到出发空格形成闭回路。然后，在该空格处试着增加1单位运量，并保持平衡，在闭回路作相应的调整，调整后回路的总运费相对于调整前的变动量就是该空格的检验数销地产地B1B2B3B4产量（吨）A1①②437A231③4A3639销量（吨）3656销地产地B1B2B3B4产量（吨）A1437A23④14A3⑤6⑥39销量（吨）3656如空格A3B1的检验数：7*1-5*1+10*1-3*1+2*1-1*1=10空格A2B4的检验数：8*1-2*1+3*1-10*1=-1位势法：构造位势和；由基变量的检验数，可得；任取、其中之一为零，可求得其他、；最后，由可求得个非基变量（空格）的检验数。销地产地B1B2B3B4UiA13-(-8+10)11-(10-1)31010A219-(9-1)28-(9+0)9A37-(-8+5)410-(-7+5)55Vj-8-1-70（3）若存在检验数为负的空格，用闭回路法进行调整，检验数最小的空格优先调整。调整时，以相应的空格位调入格（以它对应的非基变量为换入变量），以相应的闭回路进行调整，调入量为闭回路中数字格中所能调出量的最小者。销地产地B1B2B3B4产量（吨）A1437A2314A3639销量（吨）3656三、运输问题的特殊情况：1、多重解当非基变量的检验数为零时，会出现多重解。2、退化①当在某空格处填入数值时，恰好该处供应量等于需求量，在此填入相应的数值时须同时划去一行一列，此时，必须在划去的该行、该列的任意空格处添一个零。②闭回路调整时，如出现两个或两个以上调出格的数值相等，此时只能选择其中一个作为调出格，另一个格中必须填零。3.3产销不平衡的运输问题相对于标准形式的运输问题，产销不平衡问题的求解关键在于将其转化为标准形式的运输问题，即产销平衡问题。如果是产量大于销量，则可增加一个虚拟销地，任何运往虚拟销地的产量等同于就地储存，因此，所有产地运往虚拟销地的运费为0。如果是销量大于产量，则可增加一个虚拟产地，由虚拟产地运往各销地的运量实际上就是供给的缺口，表示现实中没有实际的供给，因此，由虚拟产地运往各销地的运费为0。产销不平衡问题转化为产销平衡问题之后，利用表上作业法进行求解的思路和步骤和前一节的内容完全相同。销地产地B1B2B3B4B5产量（吨）A131131007A2192804A37410509销量（吨）36533如果存在某些特定的约束，如某地存在一个最低的需求，则应注意该部分不能由虚拟产地供给，即，虚拟产地运往该地的单位运输费用应用是一个很大的正数M。需求地区化肥厂1234产量A1613221750B1413191560C192023M50D50最低需求3070010最高需求50703060需求地区化肥厂112344产量A16161322171750B14141319151560C19192023MM50DM0M0M050销量302070301050

第四章目标规划1、教学计划第5次课2学时授课章节第四章授课方式□√理论课□讨论课□实验课□习题课□其他课堂教学目的及要求了解目标规划的数学模型、目标规划的图解法，掌握目标规划数学模型的建立方法及其单纯形解法和灵敏度分析。课堂教学重点及难点重点：目标规划的数学模型特征，建立目标规划的数学模型，目标规划的单纯形法及其灵敏度分析。难点：目标规划数学模型的建立、单纯形解法及灵敏度分析。教学过程教学过程教学方法及手段4.1目标规划的数学模型目标规划数学模型的特征4.2目标规划的图解法两决策变量目标规划的图解法。4.3目标规划的单纯形解法及灵敏度分析目标规划的单纯形法与灵敏度分析。多媒体讲解实例讲解2、课件4.1目标规划的数学模型前面所讲的线性规划模型是在一种静态、理想环境中的最优决策行为。但现实决策的背景要复杂得多，某些约束条件、目标均是“软”的。目标规划数学模型具有下列特征：（1）对于决策目标来说，它允许一定的偏差，这直接表现为决策变量可以有某种偏差或；为正偏差变量，表示决策超过目标值的部分，为负偏差变量，表示决策未达到目标值的部分。考虑到决策值不可能超过同时又未达到目标值，所以，（2）绝对约束和目标约束绝对约束是指必须严格满足的等式约束和不等式约束，如线性规划中的约束，不能满足这些条件的即为非可行解。目标约束则可将右端项视为要达到的目标，但允许发生证或负的偏差，因此在这些约束中加入正、负偏差变量。在线性规划的硬约束中加入正负偏差变量（加上负偏差变量、减去正偏差变量），将符号变为等号就转变为目标约束。（3）优先因子（优先等级）与权系数在现实的决策背景下，决策者往往具有多个目标，但这些目标是有主次轻重的不同。赋予优先因子，规定，表示级目标比级具有绝对的优先权，在优先保证级目标时可不考虑级目标。权系数可区别同级目标中两个目标的差异。（4）目标规划的目标函数目标规划的目标函数由各目标约束的正负偏差变量和赋予相应的优先因子构造而成。当每一目标给定后，决策者的要求是尽可能地缩小偏离目标值。因此，目标规划的目标函数只能是，其基本形式有三种：要求恰好达到目标值，即正负偏差都要求尽可能地小，此时②要求不超过目标值，即允许达不到目标值，就是正偏差要尽可能地小，即③要求超过目标值，即超过量不限，就是负偏差要尽可能地小，此时4.2目标规划的图解法与线性规划相同，具有两变量的目标规划也可以用图解法进行求解。具体步骤与线性规划的图解法相似。4.3目标规划的单纯形解法及灵敏度分析（1）目标规划的单纯形解法目标规划的单纯形解法与线性规划的单纯形解法基本相似，当然也具有一些独特之处：①由于目标函数都市要求最小化，所以为最优准则；②非基变量的检验数中含有不同等级的优先因子，即，由于，因此，检验数的正、负取决于其中所含最高优先因子的系数的正负。例略。（2）灵敏度分析目标规划的灵敏度分析与线性规划也很相似，但还有优先因子的变化问题。当优先因子发生改变时，实际上就是将最终单纯形数表中各有优先因子对应的行向量交换位置即可，然后计算它们的检验数，看是否还需要进一步的处理。

第五章整数规划1、教学计划第6次课2学时授课章节第五章授课方式□√理论课□讨论课□实验课□习题课□其他课堂教学目的及要求掌握整数规划的数学模型、特点以及求解方法；用匈牙利法求解指派问题。课堂教学重点及难点重点：用匈牙利法求解指派问题。难点：用匈牙利法求解指派问题。教学过程教学过程教学方法及手段5.1整数规划问题的提出及一般求解方法整数规划的数学模型及特点，一般求解方法简介：分支定界法和割平面法。5.2指派问题指派问题的匈牙利法求解。多媒体讲解实例讲解2、课件5.1整数规划的数学模型的提出及一般求解方法要求一部分或全部决策变量必须取整数值得规划问题称为整数规划。其模型为：Max(或min)z=中部分或全部取整数s.t中部分或全部取整数若要求决策变量只能取值0或1的整数规划称为0-1型整数线性规划。对于一般的整数规划问题，可采用分支定界法和割平面法进行求解。5.2指派问题及其应用指派问题的标准形式及数学模型在现实生活中，有各种性质的指派问题。例如，有若干项工作需要分配给若干人（或部门）来完成；有若干项合同需要选择若干个投标者来承包；有若干班级需要安排在各教室上课等等。诸如此类的问题，它们的基本要求是在满足特定的指派要求条件下，使指派方案的总体效果最佳。由于指派问题的多样性，有必要定义指派问题的标准形式。指派问题的标准形式（以人和事为例）是：有n个人和n件事，已知第i个人作第j件事的费用为，要求确定人和事之间的一一对应的指派方案，是完成这n件事的总费用最少。为了建立标准指派问题的数学模型，引入个0-1变量：若指派第i人作第j件事若不指派第i人作第j事i，j=1,2,…n若指派第i人作第j件事若不指派第i人作第j事i，j=1,2,…n这样，问题的数学模型可写成（5.1）（5.4）（5.2）s.t（5.3）（5.4）（5.2）其中，（5.1）表示每件事必优且只有一个人去做，（5.2）表示每个人必做且只做一件事。注：eq\o\ac(○,1)指派问题是产量（）、销量（）相等，且==1，i，j=1,2,…n的运输问题。eq\o\ac(○,2)有时也称为第i个人完成第j件工作所需的资源数，称之为效率系数（或价值系数）。并称矩阵C==（5.5）为效率矩阵（或价值系数矩阵）。并称决策变量排成的n×n矩阵X==（5.6）为决策变量矩阵。(5.6)的特征是它有n个1，其它都是0。这n个1位于不同行、不同列。每一种情况为指派问题的一个可行解。共n!个解。其总的费用z=C⊙X这里的⊙表示两矩阵对应元素的积，然后相加。问题是：把这n个1放到X的个位置的什么地方可使耗费的总资源最少？（解最优）例1已知效率矩阵C=则X（1）=，X（2）=都是指派问题的最优解例12/P-149：某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知建筑公司Ai（i=1，2，…5）对新商店Bj（1，2，…5）的建造费用的报价（万元）为（i，j=1,2,…5）,见表5-9。商业公司应当对5家建筑公司怎样分派建筑任务，才能使总的建筑费用最少？表5-9B1B2B3B4B5A14871512A279171410A3691287A46714610A56912106解：这是一标准的指派问题。若设0-1变量i,j=1,2,…5当Ai不承建Bi,j=1,2,…5当Ai不承建Bj时当Ai承建Bj时则问题的数学模型为Minz=4+8+…+10+6s.t若看成运输问题，且如上所述，则表5-9为商店公司B1B2B3B4B5任务A1（4）（8）（7）（15）（12）1A2（7）(9)(17)(14)(10)1A3(6)(9)(12)(8)(7)1A4(6)(7)(14)(6)(10)1A5(6)(9)(12)(10)(6)1所选的公司数111115当然，第一行的1应放在（1，1）位置，此位置同时是第一列的费用最小。但一般情况下没有这么好。需找一适合一般的方法。匈牙利解法原理：虽然指派问题是一类特殊的整数规划问题，又是特殊的0-1规划问题和特殊的运输问题，因此，它可以用多种相应的解法来求解。但是，这些解法都没有充分利用指派问题的特殊性质，有效地减少计算量。1955年，库恩（W.W.Kuhn）提出了匈牙利法。定理1：设指派问题的效率矩阵为C=，若将该矩阵的某一行（或某一列）的各个元素都减去统一常数t（t可正可负），得到新的效率矩阵，则以为效率矩阵的新的指派问题与原指派问题的最优解相同。但其最优解比原最优解之减少t.证明：设式（5.1）～（5.4）为原指派问题。现在C矩阵的第k行个元素东减去同一常数t,记新的指派问题的目标函数为.则有==+=+=+-t=-t·1=Z-t因此有Min=min(Z-t)=minZ-t而新问题的约束方程同原指派问题。因此其最优解比相同，而最优解差一个常数。推论：若将指派问题的效率矩阵每一行即每一列分别减去各行及各列的最小元素，则得到新指派问题与原指派问题有相同的最优解。证明：结论是显然的。只要反复运用定理1便可得证。当将效率矩阵的每一行都减去各行的最小元素，将所得的矩阵的每一列在减去当前列中最小元素，则最后得到新效率矩阵中必然出现一些零元素。设=0，从第i行来看，它表示第i个人去干第j项工作效率（相对）最好。而从第j列来看，这个0表示第j项工作以第i人来干效率(相对)最高。定义：在效率矩阵C中，有一组在不同行不同列的零元素，称为独立零元素组，此时每个元素称为独立零元素。例2:已知C=则｛=0，=0，=0，=0｝是一个独立零元素组，=0，=0，=0，=0分别称为独立零元素。｛=0，=0，=0，=0｝也是一个独立零元素组，而｛=0，=0，=0，=0｝就不是一个独立零元素组，因为=0与=0这两个零元素位于同一列中。根据以上对效率矩阵中零元素的分析，对效率矩阵C中出现的的独立零元素组中零元素所处的位置，在决策变量矩阵中令相应的=1，其余的=0。就可找到指派问题的一个最优解。就上例中X（1）=，就是一个最优解。同理X（2）=也是一个最优解。但是在有的问题中发现效率矩阵C中独立零元素的个数不够n个，这样就无法求出最优指派方案，需作进一步的分析。首先给出下述定理。定理2效率矩阵C中独立零元素的最多个数等于能覆盖所有零元素的最少直线数。我们不证它，说一下意思：例3：已知矩阵C1=，C2=，C3=分别用最少直线去覆盖各自矩阵中的零元素：C1=，C2=，C3=可见，C1最少需要4条线，C2最少需要4条线，C3最少需要5条线，方能划掉矩阵中所有的零。即它们独立零元素组中零元素最多分别为4，4，5。匈牙利法求解步骤：我们以例题来说明指派问题如何求解：例4给定效率矩阵C=求解该指派问题。解：ⅰ）变换效率矩阵，将各行各列都减去当前各行、各列中最小元素。minmin列变换行变换7942C==列变换行变换7942MMin0042这样得到的新矩阵中，每行每列都必然出现零元素。ⅱ）用圈0法求出新矩阵中独立零元素。（1）进行行检验对进行逐行检验，对每行只有一个未标记的零元素时，用○记号将该零元素圈起。然后将被圈起的零元素所在的列的其它未标记的零元素用记号×划去。如中第2行、第3行都只有一个未标记的零元素，用○分别将它们圈起。然后用×划去第1列其它未被标记的零元素（第2列没有），见=在第i行只有一个零元素=0时，表示第i人干第j件工作效率最好。因此优先指派第i人干第j项工作，而划去第j列其它未标记的零元素，表示第j项工作不再指派其它人去干（即使其它人干该项工作也相对有最好的效率）。重复行检验，直到每一行都没有未被标记的零元素或至少有两个未被标记的零元素时为止。本题中第1行此时也只有1个未被标记的零元素。因此圈起中第1行第4列的零元素，然后用×划去第4列中未被标记的零元素。这是第4行也只有一个未被标记的零元素，再用○圈起，见=（2）进行列检验与进行行检验相似，对进行了行检验的矩阵逐列进行检验，对每列只有一个未被标记的零元素，用记号○将该元素圈起，然后技改元素所在行的其他未被标记的零元素打×。重复上述列检验，直到每一列都没有未被标记的零元素或有两个未被标记的零元素为止。这时可能出现以下三种情况：eq\o\ac(○,1)每一行均有圈0出现，圈0的个数m恰好等于n,即m=n.eq\o\ac(○,2)存在未标记的零元素，但他们所在的行和列中，为标记过的零元素均至少有两个。eq\o\ac(○,3)不存在未被标记过的零元素，当圈0的个数m<n.ⅲ)进行试指派若情况eq\o\ac(○,1)出现，则可进行试指派：令圈0为止的决策变量取值为1，其他决策变量取值均为零，得到一个最优指派方案，停止计算。上例中得到后，出现了情况eq\o\ac(○,1)，可令=1，=1，=1，=1，其余=0。即为最优指派。若情况eq\o\ac(○,2)出现，则在对每行、每列的其它未被标记的零元素任选一个，加上标记○，即圈上该零元素。然后给同行、同列的其它未被标记的零元素加标记×。然后再进行行、列检验，可能出现情况eq\o\ac(○,1)或eq\o\ac(○,3)，出现情况eq\o\ac(○,1)则由上述得到一最优指派，停止计算。若情况eq\o\ac(○,3)出现，则要转入下一步。ⅳ）：做最少直线覆盖当前所有零元素。我们还以例12来说明过程：已知例12指派问题的系数矩阵为：先对各行元素分别减去本行的最小元素，然后对各列也如此，即列变换行变换C=列变换行变换此时，中各行各列都已出现零元素。为了确定中的独立零元素，对加圈，即=由于只有4个独立零元素，少于系数矩阵阶数n=5,不能进行指派，为了增加独立零元素的个数，需要对矩阵作进一步的变换，变换步骤如下：（1）对中所有不含圈0元素的行打√，如第3行。（2）对打√的行中，所有零元素所在的列打√，如第1列。（3）对所有打√列中圈0元素所在行打√，如第2行。（4）重复上述（2），（3）步，直到不能进一步打√为止。（5）对未打√的每一行划一直线，如第1，3，5行。对已打√的每一列划一纵线，如第1列，既得到覆盖当前0元素的最少直线数。见。==Ⅴ）：对矩阵作进一步变换，以增加0元素。在未被直线覆盖过的元素中找最小元素，将打√行的各元素减去这个最小元素，将打√裂的各元素加上这个最小元素（以避免打√行中出现负元素），这样就增加了零元素的个数。如中未被直线覆盖过的元素中，最小元素为==1，对打√的第2，3行各元素都减去2，对打√的第1列各元素都加上1，得到矩阵。=Ⅵ）：回到步骤Ⅱ），对已增加了零元素的矩阵，再用圈0法找出独立零元素组。=中已有5个独立零元素，故可确定指派问题的最优方案。本例的最优解为承建X*=承建也就是说，最优指派方案是：让A1B3A2B2A3B1A4B4A5B5这样按排能使总的建造费最少，为z=7＋9＋6＋6＋6=34（万元）一般的指派问题在实际应用中，常会遇到非标准形式，解决的思路是：先化成标准形式，然后再用匈牙利法求解。最大化的指派问题其一般形式为s.t处理办法：设最大化的指派问题的系数矩阵为C=，m=max｛｝,令B==，则以B为系数矩阵的最小化指派问题和以C为系数矩阵的原最大化指派问题有相同的最优解。例5：某工厂有4名工人A1，A2，A3，A4，分别操作4台车床B1，B2，B3，B4。每小时单产量如下表，求产值最大的分配方案。车床工人B1B2B3B4A1A2A3A410987345621124356解：C==，m=max｛10,9,8,7,…5,6｝=10,B=====中的◎数=n=4,所以X=（5.7）即为最优解。从而产值最大的分配方案也为（5.7），最大产值为Z=10＋6＋1＋5=22人数和事数不等的指派问题。eq\o\ac(○,1)若人数<事数，添一些虚拟的“人”，此时这些虚拟的“人”做各件事的费用系数取为0，理解为这些费用实际上不会发生。eq\o\ac(○,2)若人数>事数，添一些虚拟的“事”，此时这些虚拟的“事”被各个人做的费用系数同样也取为0。例6：现有4个人，5件工作。每人做每件工作所耗时间如下表：工作工人B1B2B3B4B5A11011428A2711101412A35691214A4131511107问指派那个人去完成哪项工作，可是总消耗最小？解：添加虚拟人A5，构造标准耗时阵：行变换C==行变换所圈0数=4<5=n,下找最少覆盖0的直线。=从未划去的元素中找最小者：｛4，3，7，5，1，4，7，9｝=1。未划去的行减去此最小者1，划去的列加上次最小者1，得。=◎个数=n,从而的一最优指派：=从而最少耗时为z=2＋7＋6＋7=223.一个人可做几件事的指派问题。若某人可作几件事，则可将该人化作相同的几个“人”来接受指派。这几个“人”做同一件事的费用系数当然一样。例6：对例12的指派问题，为了保证工程质量，经研究决定，舍弃建筑公司A4和A5，让技术力量较强的建筑公司A1、A2、A3来承建。根据实际情况，可以允许每家建筑公司承建一家或两家商店。求使总费用最少的指派方案。B1B1B2B3B4B5A1AA1A2A3B1B2B1B2B3B4B5上面的系数矩阵有6行5列，为了使“人”和“事”的数目相同，引入一件虚拟事，使之成为标准的指派问题，其系数矩阵为：B1B1B2B3B4B5B6列变换C=列变换的◎数=5<6=n,下找0元素的最少直线覆盖。√-1√-1==√-1√-1从而得一最优指派：B4B5A3B2B6=ψψA2B1B3A1承建B4B5A3B2B6=ψψA2B1B3A1承建商店公司总费用为z=7＋4＋9＋7＋8=35(万元)4．某事不能由某人去做的指派问题某事不能由某人去做，可将此人做此时的费用取作足够大的M。例7：分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务，每人完成各项任务的时间如下表。由于任务重，人数少，考虑：a).任务E必须完成，其它4项任务可选3项完成。但甲不能做A项工作。b)其中有一人完成两项，其他人每人完成一项。试分别确定最优分配方案，使完成任务的总时间最少。任务人ABCDE甲乙丙丁2931423738262033272840322442362345解：这是一人数与工作不等的指派问题，若用匈牙利法求解，需作一下处理。a)由于任务数大于人数，所以需要有一个虚拟的人，设为戊。因为工作E必须完成，故设戊完成E的时间为M（M为非常大的数），即戊不能做工作E，其余的假想时间为0，建立的效率矩阵表如下：任务人ABCDE甲乙丙丁戊M293142373938262033342728403224423623450000M用匈牙利法求解过程如下：列变换行变换C=列变换行变换由于◎数=4<5=阶数，下找最少覆盖0的直线√-1√-1=√-1√-1m=｛19,18.6.13,1,19,13,22｝=1,第2、4行减去1，第4列加上1得：A丁E丙乙B甲D=从而得最优指派：A丁E丙乙B甲D最少的耗时数z=29＋20＋32＋24=105.b)思路：方案1：甲，eq\o\ac(○,甲)，乙，丙，丁。方案2：甲，乙，eq\o\ac(○,乙)，丙，丁。方案3：甲，乙，丙，eq\o\ac(○,丙)，丁。方案4：甲，乙，丙，丁，eq\o\ac(○,丁)。方案5：甲，eq\o\ac(○,甲)，乙，eq\o\ac(○,乙)，丙，eq\o\ac(○,丙)，丁，eq\o\ac(○,丁)。此为人；而工作：A，B，C，D，E，虚拟工作：F，G，H。这些思路都比较烦，请看下面的思路：设有虚拟人戊，它集五人优势为一身。即戊的费用是每人的最低。戊所做的工作即为此项工作的费用最低者的工作。任务人ABCDE甲乙丙丁戊25293142373938262033342728403224423623452427262032以下用匈牙利法求解：列变换行变换C=列变换行变换=对加圈确定独立0元素，◎个数=3<5=n,作0元素的最少直线覆盖：√√√=√√√在未划去的数中选最小者1，未划取得行都减去1，划去的列都加上1得：=再圈0且试指派：◎个数=3<5，再作0元素的最少直线覆盖。从未划取的元素中找最小者4，未划取得行都减去这个4，划去的列都加上这个4，得：BEDA丙丁乙甲=再圈0试指派，结果为：BEDA丙丁乙甲C戊C戊其中戊是虚拟人，不能真作，它作C工作是借乙（此列最小时数26是C所创业绩）优势，应由C来作。即C做两件工作：D，C。

第八章动态规划的基本方法1、教学计划第7次课2学时授课章节第五章授课方式□√理论课□讨论课□实验课□习题课□其他课堂教学目的及要求了解动态规划模型的基本概念，理解无后效性，掌握最短路问题的求解方法。课堂教学重点及难点重点：动态规划模型的基本概念和最短路问题。难点：最短路问题。教学过程教学过程教学方法及手段8.1动态规划的基本概念动态规划的基本概念。8.2最短路问题无后效性与最短路问题的求解。多媒体讲解实例讲解2、课件8.1动态规划的基本概念动态规划（DynamicProgramming）是20世纪50年代由美国数学家贝尔曼（RichardBellman）及他的学生们一同建立和发展起来的一种解多阶段决策问题的优化方法。所谓多阶段决策问题是指一类活动过程。它可按时间或空间把问题分为若干个相互联系的阶段。在每一阶段都要作出选择（决策），这个决策不仅仅决定这一阶段的效益，而且决定下一阶段的初始状态，从而决定整个过程的走向（从而称为动态规划）。每当一阶段的决策一一确定之后，就得到一个决策序列，称为策略。所谓多阶段决策问题就是求一个策略，使各个阶段的效益总和达到最优。概念：（1）阶段与阶段变量：先把问题从中间站B，C，D，E用空间位置分成5个阶段，阶段用阶段变量k来描述，k=1,表示第一阶段，k=2表示第二阶段，…（2）状态与状态变量：每一阶段的左端点（初始条件）集合称为本阶段的状态（即开始的客观条件，或称阶段初态）。如第三阶段有四个状态S3=｛C1,C2，C3，C4｝,第四阶段有三个状态S4=｛D1,D2,D3｝,…描述过程状态的变量称为状态变量：用小写s1,s2,s3…表示第一，第二，第三…阶段的状态变量。当处在状态C2时，我们可记s3=C2正像离散型R.V“X=2”代表一事件一样。(3)决策与决策变量：如当处于C2状态时，下一步怎么走？如何选择路线？即如何决策。是走向D1，还是走向D2？当过程处于某一阶段的某一状态时，可以作出不同的决策（或选择），从而确定下一阶段的状态，这种决定（或选择）叫决策。如选择D2，记u3（C2）=D2说，当处于C2状态时，下一步的决策为D2。其中表示第k阶段当状态处于时的决策变量。一般地，用表示第k阶段从状态出发的允许决策集合。如=｛D1，D2｝显然，∈。（4）策略与最优策略：每一阶段产生一个决策，5个阶段的决策就构成一个决策序列：，，，，称为一策略。所谓策略是指按一定的顺序排列的决策组成的集合，也称决策序列。这里的最短路径成为最优策略。动态规划就是在允许策略集中选最优策略。（5）状态转移方程：是描述由第k阶段到第k+1阶段状态转移规律的关系式。=上例中状态转移方程为：=（6）指标函数与最优指标函数：用于衡量所选定策略优劣的数量指标称为指标函数。相当于动态的目标函数，最后一个阶段的目标函数就是总的目标函数。它分阶段指标函数和过程指标函数。阶段指标函数是指第k阶段，从状态出发，采用决策时的效益，用表示。最优指标函数是指从第k阶段状态采用最优策略到过程终止时的最佳效益值，用表示。8.2最短路问题首先应该指出：下面研究的解决多阶段的决策问题的最优化的称之为动态规划的数学方法，仅仅是一种解决问题的思路，而不是一种算法。这一点与线性规划不同。线性规划是一种算法。下面从一典型的例子去说明动态规划的基本思想与原理：某地要从A向F地铺设一条输油管道，各点间连线上的数字表示距离。问应选择什么路线，可是总距离最短？5C5C1228D18D1433B433B154E1C254E1C26456E2C4C3F6456E2C4C3FA3D23D2328532851471473B2D33B2D3878744第一阶段第二阶段第三阶段第四阶段第五阶段逆序递推法：倒退着从F向A走，每倒退一步，思想上问自己：“从现在出发，退向何处？到F的距离最短？”我们分5步来解决问题：k=5时求=？此时状态集S5=｛E1，E2｝，故分情况讨论，先说=？若最佳路径从A出发通过E1的话，由E1到终点F的最短距离为=5同理，=3。（只有唯一的选择）故最优决策为：=F，=Fk=2时求=？由于S4=｛D1,D2,D3｝，下分四种情况进行讨论：=min=min=7,=E1.=min=min=5,=E2.=min=min=5,=E1.(3)k=3时S3=｛C1,C2，C3，C4｝,=min=min=12,=D1.同理，=10，=D2.=8，=D2.=9，=D3.（4）k=4时S2=｛B1,B2｝=min=min=13,=C2.同理，=15，=C3.（5）k=1时，S1=｛A｝=min=min=17,=B1.再按计算顺序的反推可得最优策略：=B1.=C2.=D2.=E2.=F.从而得最优路径：A—B1—C2—D2—E2—F最短距离为=17。由上面的过程可以看出，在求解的各个阶段利用了第k段和第k+1段的如下关系：这种递推关系称为动态规划的基本方程。（7.3b）式称为边界条件。逆向标号法每退到一站，看终点F，找最短路径及最短路径的距离，标号。画路径。（12）（7）C12（12）（7）C125（13）（13）（10）8D1（10）8D13（4）B14C24E153（4）B14C24E153（17）（5）（17）（5）（8）5646E2C4C3FA（8）5646E2C4C3FA23D223D2（15）1（3）385（15）1（3）385（5）47（5）47（9）3B2D3（9）3B2D3878744此时的（？）？=最优指标函数值f.得最优路径：A—B1—C2—D2—E2—F总距离为17.顺序递推法：此法类似于逆序递推法。从起点A向终点F倒退。k=1时，=0，此为初始条件。退向允许决策集S1=｛B1,B2｝此时退向B1时看起点A，最短距离为=4，此时路径（或最优决策）是唯一的：=A；记，同理，k=2时，直接用递推式：k=3时。类似的，同理，，最后逆推最优策略：A—B1—C2—D2—E2—F。与前相同。全部计算情况如图7-3（11）C152（6）（4）（11）C152（6）（4）（7）8D1（7）8D13（14）B1C2E144353（14）B1C2E14435（12）（12）（10）（17）5646E2C4C3FA（10）（17）5646E2C4C3FA23D223D2（14）（5）1385（14）（5）1385（14）47（14）47（12）3B2D3（12）3B2D3878744递推关系式：此与逆序法无本质的区别。一般来说，当初始状态给定时，用逆序解法，当终止状态给定时，用顺序解法。若既给定了初始状态又给定了终止状态，则两种方法均可使用。如习题7.2/P237，终点有三个，用逆序解法较好。8.3资源分配问题一维资源分配问题例：公司计划在三个不同的地区设置4个销售店，根据市场预测，在不同的地区设置不同数量的销售店，每月可获得的利润如下表所示。试问应如何设置，才能使每月所获得的总利润最大？其值是多少？（15分）地地区利润店数12300001161210225171433021164322217设：sk表示在第k地区至第n地区设置的销售店数量；xk表示在第k地区设置销售店数量；Pk(xk)表示在第k地区设置xk个销售店数量所得的利润；fk(sk)表示在第k地区至第n地区设置sk个销售店数量所得的最大利润总值。第一阶段：x3x3s3012340000110101214142316163417174第二阶段：x2x2s201234000010+1012+012120+1412+101722130+1612+1417+102127240+1712+1617+1421+1022312，3第三阶段：x1x1s10123440+3116+2725+2230+1232+0472因此，最优方案为、、。最大利润为47。

第十章图与网络优化1、教学计划第8次课2学时授课章节第十章第1节和第2节授课方式□√理论课□讨论课□实验课□习题课□其他课堂教学目的及要求理解图、树的基本概念，掌握最小支撑树的求解方法。。课堂教学重点及难点重点：图、树的基本概念，最小支撑树的求解。难点：最小支撑树的求解方法——破圈法和避圈法。教学过程教学过程教学方法及手段8.1动态规划的基本概念动态规划的基本概念。8.2最短路问题树的基本概念与性质，最小支撑树的求解方法破圈法和避圈法。多媒体讲解实例讲解第9次课2学时授课章节第十章第3节授课方式□√理论课□讨论课□实验课□习题课□其他课堂教学目的及要求了解路的概念，掌握最短路问题的求解方法。课堂教学重点及难点重点：最短路问题的Dijkstra算法。难点：最短路问题的Dijkstra算法。教学过程教学过程教学方法及手段10.3最短路问题路的基本概念，最短路问题的Dijkstra算法思想及步骤。多媒体讲解实例讲解第10次课2学时授课章节第五章第4节授课方式□√理论课□讨论课□实验课□习题课□其他课堂教学目的及要求了解网络、流、可行流、增广链、截集与截量的基本概念，掌握最大流问题的求解方法。课堂教学重点及难点重点：网络、流、可行流、增广链、截集与截量的基本概念，最大流问题的求解。难点：增广链的寻找方法，最大流的标号法。教学过程教学过程教学方法及手段10.4最大流问题网络、流、可行流、增广链、截集与截量的基本概念，增广链的寻找方法，最大流的标号法。多媒体讲解实例讲解第11次课2学时授课章节第五章第5节授课方式□√理论课□讨论课□实验课□习题课□其他课堂教学目的及要求了解最小费用最大流的基本概念，掌握最小费用最大流问题的求解方法。课堂教学重点及难点重点：最小费用最大流的基本概念，最小费用最大流的求解方法。难点：构造赋权有向图。教学过程教学过程教学方法及手段10.5最小费用最大流问题最小费用最大流的基本概念，最小费用最大流的求解方法。多媒体讲解实例讲解第12次课2学时授课章节第五章第6节授课方式□√理论课□讨论课□实验课□习题课□其他课堂教学目的及要求了解中国邮递员问题的基本概念入欧拉链、欧拉圈，掌握中国邮递员问题的求解方法。课堂教学重点及难点重点：动态规划模型的基本概念和最短路问题。难点：最短路问题。教学过程教学过程教学方法及手段10.5中国邮递员问题一笔画与欧拉链、欧拉圈概念，中国邮递员问题的求解思路和步骤。多媒体讲解实例讲解2、课件10.1图的基本概念图的定义：图是在纸上用点和线画出反映对象之间关系的示意图。图中点的相对位置如何、长短曲直并不重要。例1图10-2（P252）是我国北京、上海等十个城市间的铁路交通图。这里的点代表城市，点与点的连线代表两个城市间的铁路线。例2P252种图10-3与图10-5没有本质的区别。关系的种类及其表示：（1）对称性的关系甲与乙有这种关系，同时乙与甲也有这种关系。如同学关系（2）非对称的关系甲与乙有这种关系，乙与甲未必有这种关系。如甲认识乙，乙未必认识甲；一场比赛中，球队A胜球队B，球队B不能胜球队A。图的构造：一个图是由一些点及点之间的连线（带箭头或不带箭头）所组成。不带箭头的连线称为边，带箭头的连线称为弧。如果一个图是由点及边组成的，则称为无向图，记为。、分别为图的点集合和边集合，一条连结点的边记为。如果一个图是由点及弧所构成的，则称为有向图，记为。、分别为图的点集合和弧集合，一条从指向的弧记为。若，称是的端点，是相邻的，是及的关连边。若图重某个边的两个端点相同，则称是环；若两个点之间有多于一条的边，则称这些边为多重边；一个无环、无多重边的图称为简单图；无环但有多重边的图成为多重图。以点为端点的边的个数称为的次，记为或。环在计算次时算两次。次数为奇数的点称为奇点；次数为偶数的点称为偶点；次数为1的点称为悬挂点，它的关连边称为悬挂边，次为零的点为孤立点。定理1：图中，所有点的次数之和是边数的两倍。定理2：任何一个图中，奇点的个数必为偶数。图中，一个点、边交错序列，如果满足（），则称为一条联结和的链，记为，称点为链的中间点。链中，若，则称为一个圈，记为；若链中所有的点都是不同的，则称为初等链；若圈中的点都是不同的，则称之为初等圈；以后所涉及到的链（圈），除非特别交代，均指初等链（圈）。若链（圈）中含的边均不相同，则称为简单圈。图中，如任何两点之间至少有一条链，则称是连通图；否则为不连通图，不连通的每个连通的部分称为其一个连通分图。给定图，如果图，有、，则称是的一个支撑子图。给定有向图，去掉其所有弧上的箭头，就得到一个无向图，该图为的基础图，记为。给定中的一条弧，称为的始点，为的终点。设点弧交错序列在基础图中所对应的点边序列是一条链，则称该点弧交错序列是的一条链；而且如果满足（），则称为从到的一条路；如果第一点和最后一点相同，则称之为回路。10.2树的基本概念与性质一、树及其性质定义：一个无圈的连通图称为树。定理3：设图是一个树，（点数），则中至少有两个悬挂点。定理4：图是一个树的充分必要条件是不含圈，且恰有条边。定理5：图是一个树的充分必要条件是是连通图，且，（边数）。定理6：图是一个树的充分必要条件是任意两顶点之间恰有一条链。推论1：从一个树中去掉任意一条边，则余下的图是不连通的，因此，在点集合相同的所有图中，树是含边数最少的连通图。推论2：在树中不相邻的两点间添一条边，则恰好得到一个圈。二、图的支撑树定义：设图是图的一个支撑子图，如果图恰好又是一棵树，则称是的一个支撑树。定理7：图有支撑树的充分必要条件是图是连通的。破圈法：在任何一个图中，任取一个圈，从中能够去掉一边，然后重复此过程，直到不含圈为止，即得到一个支撑树。例6避圈法：在任何一个图中，任取一条边，找一条与该边不构成圈的边，再寻找一条与该两条边不构成圈的边，继续此过程，直到不能进行为止。例7三、最小支撑树定义3：给图上所有的边都赋予一个数，则称这样的图为赋权图，为边上的权。这里的权是指与边有关的数量指标，根据实际问题可表示距离，时间，费用等等。定义4：如果图是图的一个支撑树，称中所有边的权之和为支撑树的权，如果支撑树的权是的所有支撑树的权中最小者，则称是的最小支撑树。最小支撑树的求解方法：避圈法首先选一条最小权的边，然后每一步总从与已选边不构成圈的那些未选边中选择一条权最小的边（如果有两条或两条以上的边都是权最小的边，任选其中一条），重复此步骤直到不能进行为止。（2）破圈法任取一个圈，从圈中去掉一条权最大的边（如果有两条或两条以上的边都是权最大的边，任意去掉一条），在余下的图中重复该步骤直到不能进行为止。例：求下图的最小支撑树。避圈法（2）破圈法10.3最短路问题问题的引出：存在一个赋权有向图，对其中每一个弧，相应地有权；给定中的两个顶点、，设是中从到的一条路，定义路的权是中所有弧的权之和，记为。最短路问题就是要在所有从到的路中，寻找一条权最小的路，使称是从到的最短路，也成为从到的距离。即，最短路问题的本质是在在一个赋权有向图中，求出从给定一个点到任一点的最短路。最短路问题的算法：（1）权的情形：Dijkstra算法Dijkstra（1930-2002），二十世纪最伟大的计算机科学家之一，提出编程的“goto有害论，信号量和PV原语，解决了“哲学家聚餐”问题，Dijkstra最短路径算法的创造者，第一个Algol60编译器的设计者和实现者，THE操作系统的设计者和开发者。基本思想：从初始点出发，与每个点对应，记录下一个数（称为这个点的标号），它或者表示从到该点的最短路的权（称为P标号），或者是从到该点的最短路的权的上界（称为T标号），方法的每一步是去修改T标号，并且把某一个具有T标号的点变为P标号，使中P标号的顶点数多一个，如此，至多经过步，就可求出从到各点的最短路。步骤：开始（），令，，，对于每一个，令，，令。①如果，算法终止，此时，对于每个，；否则转入②；②考察每个使且的点，如果，则把修改为，把修改为，否则转入③；③令。如果，则把的标号变为标号，即，，令，，把换成，转入①；否则终止，此时对每一个，，而对每一个，。例：求下图中到各顶点的最短路。解：，，，；，，；令；考察所有从出发指向其余点的弧（经1步可达到的不属于点：，，）。<，所以，将修改为6，；同样的方法可得、，、。在所有的标号中，最小，所以，，得，。，考察从、出发指向其余点的弧（经1步可以达到的不属于点：，，）。可得、，、，、。所有标号中，最小，得，，。，考察从、、出发指向其余点的弧（经1步可以达到的不属于点：，）。得、，、。所有标号中，最小，因此，，，。，考察从、、、出发指向其余点的弧（经1步可以达到的不属于点：，）。得、，、。所有标号中，最小，因此，，，。，考察从、、、、出发指向其余点的弧（经1步可以达到的不属于点：，，）。得、，、，、。所有标号中，最小，因此，，，。，考察从、、、、、出发指向其余点的弧（经1步可以达到的不属于点：，）。得、，、。所有标号中，最小，因此，，，。，考察从、、、、、、出发指向其余点的弧（经1步可以达到的不属于点：）。得、，，。，只剩余，没有任何指向的弧，因此，，。计算完毕。综合计算结果：，，，，，，，，。，，，，，，，，。若是无向图（如P264，例11），则将其任何一边视为两条具有相同权的弧和，然后把Dijkstra方法的②改为“考察每个使且的点”，采用同样的思路可求得无向图中某一点到其余任何一点的最短路（也叫最短链）。（2）含负权的情形Dijkstra算法只适用于的情形，在含负权的情况下，算法实效。如下图，根据Dijkstra算法，得到的最短路的权是1，但事实上，从经由到的权为-1。引理：如果从到的最短路是从出发，经某一条路到点再沿到，则，从到的这条路必然是从到的最短路，可记为。从到的最短路必满足如下方程：为求得该方程的解，可用如下地推公式：，（）对，，若进行到某一步，对所有，有则，（）为到各点最短路的权。例：求下图中从到各点的最短路。点0-1-230000602-1-5-5-5-30-51-2-2-2-2023-7-7-7-101-3-31017-1-1-1-105-5-5-3-5066链的确定：（1）采用类似于Dijkstra的方法，在迭代过程中，如果则，。（2）反向追踪法：求出最短路之后，进行反向追踪。例如，已知，寻找点，使，记录下，再考察，寻找一点，使，记录下，依此类推，直到为止，从而求出到的最短路。10.4网络最大流问题一、基本概念与基本定理1网络与流给定有向图，在中指定了一点称为发点（记为），另一点称为受点（记为），其余点叫做中间点；对于每一个弧，对应有一个（或记为），称为弧的容量。称上述有向图为一个网络，记为网络上的流，是指定义在弧集合上的一个函数，并称为弧上的流量（也可记为）。2可行流与最大流通过运输网络的实际问题可知：一，每个弧上的流量不能超过该弧的最大通过能力（弧的容量）；二，中间点的净流量为零，即，流入量等于流出量，发点的净流出量等于收点的净流入量。因此，定义满足如下条件的流称为可行流：（1）容量限制：对于每一弧，有（2）平衡条件：对于中间点：流出量等于流入量，对于每个，有对于发点，有对于收点，有称为这个可行流的流量。可行流总是存在的。最大流问题就是求一个流使其流量达到最大，且满足：，3增广链给定一个可行流，网络中的弧称为饱和弧，的弧称为非饱和弧，的弧称为零流弧，的弧称为非零流弧。设是网络中联结发点和收点的一条链，并定义链的方向是从到，则链上的弧分为两类：方向与链的方向一致的弧称为前向弧，前向弧的全体记为；方向与链的方向相反的弧称为后向弧，后向弧的全体记为。定义：设是一个可行流，是从到的一条链，若满足如下条件，则称其为（关于可行流）的增广链。条件一，在弧上，，即中每一条弧是非饱和弧。条件二，在弧上，，即中每一条弧是非零流弧。4截集与截量定义给网络，若点集被剖分为两个非空集合和，使，，则把弧集（，）称为是分离和的截集。定义给一截集（，），把截集（，）所有弧的容量之和称为这个截集的容量，简称为截量，记为，即性质：任何一个可行流的流量都不会超过任何一个截集的容量，即，，当且仅当最大、最小时，二者取等号，定理可行流是最大流，当且仅当不存在关于的增广链。最大流量最小截量定理：任一个网络中，从到的最大流的流量等于分离和的最小截集的容量。寻求最大流的标号法：基本：思想根据上述定理，利用标号法进行求解：利用给顶点标号的方法来定义，在标号的过程中，有标号的顶点表示属于的点，无标号的顶点表示不属于的点；一旦有了标号，表示找到了一条增广链；如果标号进行不下去，而尚未标号，则说明不存在增广链，而且同时也得到一个截量最小的截集。具体步骤如下：（1）标号过程在整个过程中，网络中的点或者是标号点（已检查或未检查），或者是未标号点。每个标号点的标号汉两部分：第一个标号表示它的标号从哪一点得到的，目的是为了找出增广链；第二个标号是为了确定增广链的调整量的。首先，总给标上，此时，为标号而未检查的点，其余都是标号点。一般情况下，取一个标号而未检查过的点，对一切为标号的点：在弧上，，则给标号，；在弧上，，则给标号，。此时，成为标号、已检查的点。重复上述过程，一旦被标上号，标明得到一条从到的的增广链，转入调整过程。（2）调整过程首先按及其他点的第一个标号，利用反向追踪法找出增广链。调整量是标号点的第二个标号，为该增广链中各点所能调整的量中最小者，也就是，因为，根据标号的过程必有最小。令，去掉所有的标号，对新的可行流进行新的标号过程。例如：利用标号法求下图所示网络的最大流。弧旁的数是。（1）标号：①首先，给标上②检查，在弧上，，不满足标号条件。弧上，，则的标号为，③检查，在弧上，，不满足标号条件。弧上，，则给标号为，。④检查，在弧上，，给标号，在弧上，，给标号为，⑤在、中任选一个进行检查。在弧，，给标号为，。有了标号，转入调整过程。（2）调整按点的第一个标号找到一条从到的增广链，如下图所示。在此增广链中，调整，调整量。因此，在上：，在上，，其余弧的流量均不变，由此，得调整后网络的可行流，继续标号过程，结果发现，在给标号、给标号之后，无法继续标号，即找不到增广链了，因此，上图所示的流就是最大流，流量为5。同时找到了最小截集，，，此时，该截集的容量也