运筹学完整教案

第一章线性规划与单纯形法1、教学计划第第1 次课2学时123授课章节授课方式□√理论课□讨论课□实验课□习题课□其他了解线性规划模型的背景、掌握建模方法以及线性规划的标准形式。课堂教学掌握两个决策变量线性规划问题可行域（凸集）、最优解的位置；了解无解（无界解、无可行解）、有解（唯目的及要求一解、无穷多个解）的几何意义。重点：线性规划的数学模型及其标准形。在数学模型中，要求熟悉矩阵形式；在标准形中，要求学生掌握课堂教学非标准形式的几种具体情形及其相应的标准化方法；如何用几何的方法求两个决策变量的线性规划问题的重点及难点最优解。难点：线性规划的基本概念，例如基、基变量、基解、基可行解和可行基；多个最优解如何表示。教学过程教学方法及手段引言多媒体讲解运筹学模型，运筹学发展历史与现状，研究方法；考核方法与教学大纲等。实例讲解1.1线性规划问题及其数学模型教学过程线性规划的数学模型：变量的确定、约束条件与目标函数。线性规划问题的标准形式线性规划的标准形式及非标准形式的标准化处理。线性规划问题的解基、基变量、基解、基可行解和可行基。第2第2次课 2学时授课章节4授课方式□√理论课□讨论课□实验课□习题课□其他课堂教学掌握单纯形法思想以及具体操作过程。目的及要求课堂教学重点：单纯形法迭代过程（）换入基变量的确定；（）换出基变量的确定（）判定当前解已经最优。重点及难点难点：单纯形法思想。教学过程教学过程教学方法及手段1.41.4多媒体讲解单纯形数表的构造，要注意代数形式和表格形式的一一对应性。实例讲解单纯形法迭代过程（）换入基变量的确定；（）换出基变量的确定；（3）判定当前解已经最优。第3第3次课 2学时授课章节5授课方式□√理论课□讨论课□实验课□习题课□其他课堂教学掌握人工变量法的基本思想以及大M法和两阶段法的求解。目的及要求课堂教学重点：人工变量法的基本思想。重点及难点难点：大M法和两阶段法的求解。教学过程教学方法及手段多媒体讲解教学过程1.5单纯形法的进一步讨论及小结人工变量法的思想，大M法和两阶段法的求解思路和步骤。实例讲解单纯形法小结2、课件线性规划问题及其数学模型线性规划模型的建立就是将现实问题用数学的语言表达出来。例1：某工厂要安排生产Ⅰ、Ⅱ两种产品，每单位产品生产所需的设备、材料消耗及其利润如下表所示。问应如何安排生产计划使工厂获利最多？ⅠⅡ设备128台时原材料A4016kg原材料B0412kg单位产品的利润（元）23解：设生产产品Ⅰ、Ⅱ的数量分别为x和x。1 2首先，我们的目标是要获得最大利润，即maxz2x3x1 2其次，该生产计划受到一系列现实条件的约束，设备台时约束：生产所用的设备台时不得超过所拥有的设备台时，即x 2x 81 2原材料约束：生产所用的两种原材料A、B不得超过所用有的原材料总数，即4x1614x 122非负约束：生产的产品数必然为非负的，即

x01 2由此可得该问题的数学规划模型：

maxz2x3x1 2x 2x 81 24x1614x 122x01 2总结：线性规划的一般建模步骤如下：确定决策变量111

x

。确定决策变量是建立数学规划模型的关键所在。确定目标函数确定目标函数就是将问题所追求的目标用决策变量的函数表示出来。确定约束条件将现实的约束用数学公式表示出来。线性规划数学模型的特点小化。问题中的约束条件表示现实的限制，可以用线性等式或不等式表示。找到最优的决策方案（使目标函数最大或最小，从选择方案的角度看，这是规划问题，从目标函数最大或最小的角度看，这是最优化问题。线性规划问题的标准形式根据问题的性质，线性规划有多种形式，目标函数有要求最大化的，也有要求最小化的；约束条件可以是“”或“ 的不等式，也可以是；虽然决策变量一般是非负的，但也可是无约束的，即，可以(, )取值。为了分析问题的简化，一般规定如下的标准形式：maxzcx11

cx ...cx22 nnax111

ax122

x b1nn 1ax ax x b211 222 2nn 2.........ax ax x bm11 m22 mn n mx1 2

,..,0n非标准形式转化为标准形式：若目标函数要求实现最小化minz'z，可将原问题的目标函数转化为max即可。若约束方程为“”的左边加上非负的松弛变量；若约束方程为“”的左边减去非负的剩余变量。若存在取值无约束的变量

x

x' x"，其中，x'0。k k k k k k12122x3x612xx412xx312

minzx 2xx 2

无约束解：33

4x4

342，其中，x0；3456其次，在第一个约束条件的左端加上非负的松弛变量x；再次，在第二个约束条件的左端减去非负的剩余变量x56'z，将求minz改为求max。由此，可得标准形如下：maxx2x 2x1 3 4

0x 0x5 62x3x 3x x 61 3 4 5x x x x 41 3 4 6x1x

x x 33 401 3 4 5 6首先，将线性问题的标准形式用矩阵和向量形式表示如下：maxzAX BX 0其中，C

,..)；X x

,..T，Bb

,..T1 2

1 2 na a11 12a a

1 2 m...a1n...aA 21..am1

22...am2

2n........amn1、可行解和最优解1满足约束条件的所有解X 1

n2xTn2最优解。2、基和基解设A为约束方程组的mn维矩阵其秩为m设B为矩阵A中的mm阶非奇异子矩（B0则称B为线性规划的一个基。B不妨设前m个变量的系数矩阵为线性规划的一个基，则XB

1

T为对应于这个基的基变量。用高斯m消去法可求得一个解m

X 1 2

,....Tn该解得非零分量的数目不大于方程个数m，称X为基解。3、基可行解X4、可行基对应于基可行解的基，成为可行基。单纯形法一、单纯形表考察一种最简单的形式：目标函数最大化、所有约束条件均为“”。利用所有约束条件化为等号的方法，在每个约束条件的左端加一个松弛变量，并整理，重新对变量及系数矩阵进行编号，得x a x1 1m1

...ax b1nn 1x a x2 1m1

...ax b2nn 2.....x a x

...ax bm m1m1 mn n mx 0,jj11将其与目标函数的变换形式 zcx11

cx x22 m

cxm1m1

xnn

0n1个1m2变量、m1个方程的方程组。若将z看成不参与基变换的基变量，它与xx.,1m2将c将1

.,变为零，则可得m12mmm12mm1n010...0a ... ab11n1001...0a ... ab

...x x

... x b1 2n 2............... ... .. .. ...0 0 0...1

m,m1

... a bmn mm m m1 0 0...0c ca ...c ca cbm1 i1

i1

iii1据此，可设计如下的数表c c … cj 1 mC X b x … xB B 1 m

c … cm1 nix … xm1 nc x b1 1 1

1 … 0

a … a1 1n 1c x 2 2

0 … 0 a … a2 1 2n 2… … … … … … … … … …c x b 0 … 1 a … am m mc z

m1 mn m0 … m … mj j cm1

caii1

c can iini11BX列表示基变量，在这里为1B

x,..,；2 m；1BC1B

x.,对应的价值系数；m2b列为约束方程的右端项；m2jc行为所有变量的价值系数；ji列的数字是在确定换入变量后，按规则计算后填入；最后一行为各变量的检验数，尤其要注意的是非基变量的检验数。例，求解maxz2x3x1 2x 2x 81 24x1614x 122首先将其转换为标准形式，

maxz2x1

x01 23x 0x 0x 0x2 3 4 5x 2x x 81 2 34x x 161 44x x 122 5构造初始单纯形表如下：

x1

03 4 5jc 2 3 0 0 0jiC X b x x x x xB B 1 2 3 4 50 x 8 13

2 1 0 0 40 x 16 4 0 0 1 0 -40 x 12 0 [4] 0 0 1 35j c z 2 3 0 0 j 由上表可得初始基可行解

X0) 112T1和1和

x的检验数大于零，表明上述解不是最优解，由于

的检验数更大，所以，先以x

为换入变量。根据 规22522252

为换出变量，计算得新表如下：cj 2 3 0 0 0iC X b x x x x xB B 1 2 3 4 5023x [1] 023

1 0 -1/2 20 x 16 4 0 0 1 0 443 x 3 0 1 0 0 1/4 -2j c z j 可得新解X) 10T，目标函数取值z9。x的检验数为2，换入。根据 规则，可确定x为换出变量，计算得新表如下：1 3jc 2 3 0 0 0jiC X b x x x x xB B 1 2 3 4 52 x 2 11

0 1

-1/2 -0 x 8 0 0 -4 1 [2] 443 x 3 0 1 0 0 1/4 12cjcjzj00-201/4得新解X(2)00T，目标函数取值z13。35x的检验数为1/4，换入。根据 规则，可确定35

为换出变量，计算得：jc 2 3 0 0 0jiC X b x x x x xB B 1 2 3 4 52 x 4 11

0 0 1/4 00 x 4 0 0 -2 1/2 153 x 2 0 1 1/2 -1/8 02j c z 0 0 -3/2 -1/8 j 得解X3) 004T，目标函数取值z14。由于所有的检验都小于零，达到最优。PS：如果目标函数是求最小化，则，检验数的最优准则为检验数大于零。单纯形法的进一步讨论及小结一、人工变量法如果初始约束条件不全是小于等于号，则不能直接得到初始基（单位基）在迭代结束后，如果最后基变量中不再含有非零的人工变量，表示原问题有解；反之，则表示无可行解。例：minz 3x x x1 2 3x2x1 2

x 1134x x 2x 31 2 32x x 11 3x01 2 3在第一个约束条件中加入松弛变量x

4；在第二个约束条件中加入剩余变量x

；在第三个约束条件中加入567人工变量x。567（1）大M在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对目标函数值不产生影响，可假定人工变量在目标函数中的系数为-（M为很大的正数现最大化。对上例求解，加入人工变量后，规划问题变成minz3x1x2x30x 0x45Mx6Mx7x12x2x3x114x x 2x x x 31 2 3 5 62x x x 11 3 7x1 2

3

05 6 7然后，利用单纯形法求解，详见P33。（2）两阶段法最小化；然后用单纯形法求解，若得到该规划的最优解为零，说明原问题存在基可行解，否则原问题无可行解，停止计算。解。前一个例子的两阶段法求解如下：构造出第一阶段的数学模型如下：minzx x6 7x2x1 2

x x1134x x 2x x x 31 2 3 5 62x x x 11 3 7x1 2000000011bxxxxxxxj

3

05 6 7C XB B 1 2 3 4

i5 6 70 x 11 1 -2 14

1 0 0

0 111 x 3 -4 1 2 0 -1 1 0 3/261 x 1 -2 0 [1] 0 0 0 1 17j c z 6 -1 -3 0 1 0 j 000000011bxxxxxxxjC XB B 1 2 3 4

i5 6 70 x 10 3 -2 04

1 0 0

-1 -1 x 1 0 [1] 0 0 -1 1 -2 160 x 1 -2 0 1 0 0 0 1 -3j c z 0 -1 0 0 1 0 j 000000011bxxxxxxxjC XB B 1 2 3 4

i5 6 70 x 12 3 0 04

1 -2

2 -5 -0 x 1 0 1 0 0 -1 1 -2 120 x 1 -2 0 13c z 0 0 0j j

0 0 0 1 -0 01 167得最优解X 120T。由于人工变量x x 0，说明X 120T是原问题的基可67行解，可进行第二阶段运算。利用单纯形法，从下表开始：jc -3 1 1 0 0jC X b x xB B 1 2

ix x x3 4 50 x 124

[3]

0 1 -2 -1 x 1 0 1 0 0 -1 121 x 1 -2 0 13j c z -1 0 j jc -3 1 j

0 0 -0 10 0C X b x xB B 1 2

ix x x3 4 5-3 x11 x21 x3

4 1 0 1 0 1 9 0 0

1/3 -2/3 -0 -1 12/3 -4/3 -j c z 0 0 j 二、解的退化所有的检验数均 0j对于任一检验数 0，若对应的系数向量P 0，则有无界解单纯形法小结jx 0j

1/3 1/3不需处理j变量 x 0j

x' xx 0令；j j j令；x无约束

令x x'

x"，x'0j j b0

j j j不需处理b0约束条件=

xsiaixsiai减剩余变量x，加人工变量x目标函数

maxz

si aiminz加入变量的系数

松弛变量xsi 0人工变量xai M第三章运输问题1、教学计划第4次课2学时授课章节

第三章授课方式课堂教学课堂教学

□√理论课□讨论课□实验课□习题课□其他当前解是否最优解的判断，闭回路调整方法；非平衡运输问题的求解。重点：运输问题的求解方法。难点：初始基可行解的确定、判断，非平衡问题的求解思路。教学过程运输问题的提出及其模型特征运输问题的提出背景及其模型特征运输问题的求解：表上作业法教学过程 表上作业法的思路和步骤如初始基可行解的确定（最小元素法和伏尔法，最优解的判断方法，闭回路调整方法。产销不平衡的运输问题将不平衡问题转化为平衡问题。2、课件1、背景

教学方法及手段多媒体讲解实例讲解2、模型特征销地产地1 2 … n 销地产地c c11 12…21…21…22 2n… .. …2…mcm1c cm2 mnam

… c a1n 1… c a销量 b b … b1 2 nm nminz cxijiji1j1mx bij i1nx aij ij1x 0ij

jimnmnmn1此，其可行解中的基变量个数必然是mn1。系数矩阵：变量x的系数向量P除第i个分量和第m 个为1外其余为零。ij ij运输问题的求解：表上作业法表上作业法实际上是单纯形法在求解运输问题时的一个简化，主要步骤：（1）找出初始基可行解：最小元素法和伏格尔（Vogel）法最小元素法：优先满足运价最小的供销关系销地产地销地产地B B B B 产量（吨）1 2 3 4A 31A 12A 73销量（吨） 3

11 3 10 79 2 8 44 10 5 96 5 6销地产地B B B B 产量（吨）销地产地1 2 3 4A 3 111A 1 92

3 10 72 8 4A3销量（吨）

（3）7 4 10 5 93 6 5 6销地产地销地产地1 2 3 4A1 3 11 3 10 71（3）1（3）92（1）8474105936562A3销地B销地B1B2B3B4产量（吨）产地A1A2A3销量（吨）311310719（4）284（3）（1）7410593656销地销地B1B2B3B4产量（吨）产地A13113107（4）A219284（3）（1）A3741059（6）销量（吨）3656销地B1B2B3B4产量（吨）产地A 3 11 31

10 7（4） （3）A21（3）92（1）84A3741059（6）（3）销量（吨）3656销地B1B2B3B4产量（吨）产地A1437A2314A3639销量（吨）3656伏格尔法：优先满足最小运价与次小运价差值最大的行、列中的最小运价所对应的供销关系。销地产地销地产地1 2 3 431131131001928174105125131A2A3列差求各非基变量（空格）的检验数。销地产地90度（也可不转，空格处绝不转1销地产地B B B B 产量（吨）1 2 3 4②431③②431③636561A 3 42A 93销量（吨） 3销地产地销地产地1 2 3 443④143④16⑥36561A 3 42A ⑤ 93销量（吨） 3如空格AB7*1-5*1+10*1-3*1+2*1-1*1=1031AB8*1-2*1+3*1-10*1=-124位势法：i j ij i 构造位势U和V(j；由基变量的检验数C V)0，可i j ij i ij i j i j C U VU(、V(j其中之一为零，可求得其他U(ij i j i j j ij i V(j2.；最后，由C U V)j ij i 销地产地销地产地1 2 3 4 iA 3-1A 12A 7-(-8+5)3V -8j

119-(9-1)4-1

3210-(-7+5)-7

10 108-(9+0) 95 50销地产地若存在检验数为负的空格，用闭回路法进行调整，检验数最小的空格优先调整。调整时，以相应的空格位调入格（应的非基变量为换入变量销地产地B B B B 产量（吨）1 2 3 4A 4 3 71A 3 1 42A 6 3 93销量（吨） 3 6 5 6三、运输问题的特殊情况：1、多重解2、退化该行、该列的任意空格处添一个零。②闭回路调整时，如出现两个或两个以上调出格的数值相等，此时只能选择其中一个作为调出格，另一个格中必须填零。产销不平衡的运输问题相对于标准形式的运输问题，产销不平衡问题的求解关键在于将其转化为标准形式的运输问题，即产销平衡问题。。际的供给，因此，由虚拟产地运往各销地的运费为。产销不平衡问题转化为产销平衡问题之后，利用表上作业法进行求解的思路和步骤和前一节的内容完全相同。销地产地销地产地1 2 3 4 5A 31A 12A 73销量（吨） 3

11 3 10 0 79 2 8 0 44 10 5 0 96 5 3 3需求地区单位运输费用应用是一个很大的正数M。需求地区1 2 3 4 产量A1613221750B1413191560C192023M50D50最低需求3070010最高需求50703060需求地区1’ 1” 2 3 4’ 4” 产量需求地区化肥厂A16161322171750B14141319151560C19192023MM50DM0M0M050销量302070301050第第5 次课2学时第四章授课章节授课方式□√理论课□讨论课□实验课□习题课□其他课堂教学了解目标规划的数学模型、目标规划的图解法，掌握目标规划数学模型的建立方法及其单纯形解法和灵敏目的及要求度分析。重点：目标规划的数学模型特征，建立目标规划的数学模型，目标规划的单纯形法及其灵敏度分析。课堂教学重点及难点 难点：目标规划数学模型的建立、单纯形解法及灵敏度分析。教学过程教学方法及手段4.1目标规划的数学模型多媒体讲解目标规划数学模型的特征教学过程实例讲解目标规划的图解法两决策变量目标规划的图解法。目标规划的单纯形解法及灵敏度分析2、课件目标规划的数学模型前面所讲的线性规划模型是在一种静态、理想环境中的最优决策行为。但现实决策的背景要复杂得多，某些约束条件、目标均是“软”的。目标规划数学模型具有下列特征：对于决策目标来说，它允许一定的偏差，这直接表现为决策变量可以有某种偏差

或dd为正偏差变量，表示决策超过目标值的部分，d

为负偏差变量，表示决策未达到目标值的部分。考虑到决策值不可能超过同时又未达到目标值，所以，d d 0绝对约束和目标约束束则可将右端项视为要达到的目标，但允许发生证或负的偏差，因此在这些约束中加入正、负偏差变量。在线性规划的硬约束中加入正负偏差变量（加上负偏差变量、减去正偏差变量，将符号变为等号就转变为目标约束。优先因子（优先等级）与权系数k，k1在现实的决策背景下，决策者往往具有多个目标，但这些目标是有主次轻重的不同。赋予优先因子，规P Pk，k1表示k级目标比k1级具有绝对的优先权，在优先保证k级目标时可不考虑k1权系数可区别同级目标中两个目标的差异。目标规划的目标函数尽可能地缩小偏离目标值。因此，目标规划的目标函数只能是minz,)，其基本形式有三种：① 要求恰好达到目标值，即正负偏差都要求尽可能地小，此时minzd)②要求不超过目标值，即允许达不到目标值，就是正偏差要尽可能地小，即minzf(d)③要求超过目标值，即超过量不限，就是负偏差要尽可能地小，此时minzf(d)目标规划的图解法与线性规划相同，具有两变量的目标规划也可以用图解法进行求解。具体步骤与线性规划的图解法相似。目标规划的单纯形解法及灵敏度分析目标规划的单纯形解法目标规划的单纯形解法与线性规划的单纯形解法基本相似，当然也具有一些独特之处：j ①由于目标函数都市要求最小化，所以c z 0j ②非基变量的检验数中含有不同等级的优先因子，即c z aPj j kjkj2..，k2..,11

P ...P2

，因此，检验数的正、负取决于其中所含最高优先因子的系数的正负。例略。灵敏度分析目标规划的灵敏度分析与线性规划也很相似，但还有优先因子的变化问题。数，看是否还需要进一步的处理。第第6 次课2学时授课章节第五章授课方式□√理论课□讨论课□实验课□习题课□其他课堂教学掌握整数规划的数学模型、特点以及求解方法；用匈牙利法求解指派问题。目的及要求重点：用匈牙利法求解指派问题。课堂教学重点及难点 难点：用匈牙利法求解指派问题。教学过程教学方法及手段5.1整数规划问题的提出及一般求解方法多媒体讲解教学过程整数规划的数学模型及特点，一般求解方法简介：分支定界法和割平面法。实例讲解5.2指派问题指派问题的匈牙利法求解。2、课件整数规划的数学模型的提出及一般求解方法要求一部分或全部决策变量必须取整数值得规划问题称为整数规划。其模型为：njj或min)z= cxjjj1nax (,

imijij ij1js.t x 0x,j1 2 n

jn中部分或全部取整数若要求决策变量只能取值010-1对于一般的整数规划问题，可采用分支定界法和割平面法进行求解。指派问题及其应用一．指派问题的标准形式及数学模型在现实生活中，有各种性质的指派问题。例如，有若干项工作需要分配给若干人（或部门）择若干个投标者来承包；有若干班级需要安排在各教室上课等等。诸如此类的问题，它们的基本要求是在满足特定的指派要求条件下，使指派方案的总体效果最佳。由于指派问题的多样性，有必要定义指派问题的标准形式。指派问题的标准形（以人和事为例nnij

(i,j1,2,n)，ij要求确定人和事之间的一一对应的指派方案，是完成这n件事的总费用最少。为了建立标准指派问题的数学模型，引入n20-10 若不指派第i人作第jx

，j=1,,nij 1这样，问题的数学模型可写成

若指派第i人作第j件事n nminz c

（5.1）ijiji1j1nx 1 jiji1n

（5.2）s.t x 1 in （5.3）ijj1ijx n ij（5.）表示每件事必优且只有一个人去做（5.）表示每个人必做且只做一件事。注：1指派问题是产量（a、销量（bj）相等，且a=bj=1，，j=1,2…n的运输问题。2有时也称c为第i个人完成第j效率系数（或价值系数。并称矩阵ijC=)

c c11 12c c= 21

c1nc2n （5.5）ijnn

c c cn1 n2 nn效率矩阵（或价值系数矩阵。并称决策变量x排成的n×n矩阵ijX=)

x x11 12x x= 21

x1nx2n （5.6）ijnn

x x xn1 n2 nn为决策变量矩阵。(5.6)的特征是它有n个1，其它都是0。这n个1位于不同行、不同列。每一种情况为指派问题的一个可行解。共n!个解。其总的费用z=C⊙X这里的⊙表示两矩阵对应元素的积，然后相加。问题是：把这n1Xn2个位置的什么地方可使耗费的总资源最少？（解最优1已知效率矩阵5050202300056748000100000110000010则（1）（2）01（1）（2）0100001010000001都是指派问题的最优解例12/P-149：某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知建筑A（i=1，2，…5）B（1，2，…5）的建造费用的报价（万元）为c（i，j=1,2,…5）。商业公司应i j ij当对5家建筑公司怎样分派建筑任务，才能使总的建筑费用最少？cijcijB1B2B3B4B5A14871512A279171410A3691287A46714610A56912106解：这是一标准的指派问题。若设0-1变量x 1 =0

i承建Bj

i,j=125ij

i不承建Bj时则问题的数学模型为11Minz=4x11

x+812+8

+…+10x x54+655554+655x 1 j5iji15s.t xij

1 i5j1x 5ijB1B2B3B4B5B1B2B3B4B5任务店店公司A1（4） （8） （7） （15） （12） 1x11x12x13x14x15A2（7） (9)(17)(14)(10)1x21x22x23x24x25A3(6)(9)(12)(8)(7)1x31x32x33x34x35A4(6)(7)(14)(6)(10)1x41x42x43x44x45A5(6)(9)(12)(10)(6)1x51x52x53x54x55所选的公司数 111115当然，第一行的1应放在（1，1）位置，此位置同时是第一列的费用最小。但一般情况下没有这么好。需找一适合一般的方法。二．匈牙利解法原理：0-11955年，库恩（W.W.Kuhn）提出了匈牙利法。设指派问题的效率矩阵为C=

，若将该矩阵的某一行（或某一列）的各个元素都减去统一常数t（t可ijnn正可负，得到新的效率矩阵C

(c)ijnn

，则以C为效率矩阵的新的指派问题与原指派问题的最优解相同。但其最优解比原最优解之减少t.证明：设式（5.1）～（5.4）为原指派问题。现在C矩阵的第k行个元素东减去同一常数t,记新的指派问题的目标函数为Z.则有n n n n n n nZ= cx= cx+ cx= c

n+

t)xijij

ijij kjkj ij

kj kji1 j1 i1i

j1 j

i1 j1 j1ikn n= c

n+ c

n-t

n n= c

-t·1=Z-ti1 jik

ij

kjj1

kjj1 i1 j

ijij因此有MinZ=min(Z-t)=minZ-t而新问题的约束方程同原指派问题。因此其最优解比相同，而最优解差一个常数。的最优解。证明：结论是显然的。只要反复运用定理1便可得证。当将效率矩阵的每一行都减去各行的最小元素，将所得的矩阵的每一列在减去当前列中最小元素，则最后得到新效率矩阵C中必然出现一些零元素。设c=0，从第i行来看，它表示第i个人去干第j项工作效率（相对）最好。而从第j列来看，ij这个0表示第j项工作以第i人来干效率(相对)最高。502025020230005674800C=c则｛c=0，c=0， =0，c=0｝是一个独立零元素组c

=0，

=0，

=0，c=012 24 31 43cc c c cc

12 24c

31 43c c｛12=0，23=0，31=0，44=0｝也是一个独立零元素组，而｛14=0，23=0，31=0，44=0｝就不是一个独c c立零元素组，因为14=0与44=0这两个零元素位于同一列中。根据以上对效率矩阵中零元素的分析，对效率矩阵C中出现的的独立零元素组中零元素所处的位置，在决策变量矩阵中令相应的x=1，其余的x=0。就可找到指派问题的一个最优解。ij ij就上例中就是一个最优解。同理也是一个最优解。

X = ，010100000110000010（2）01（2）0100001010000001但是在有的问题中发现效率矩阵C中独立零元素的个数不够n个，这样就无法求出最优指派方案，需作进一步的分析。首先给出下述定理。2效率矩阵C我们不证它，说一下意思：例3：已知矩阵50202705020270202230004300005572，C=3033550202300056748004848004680040636504143分别用最少直线去覆盖各自矩阵中的零元素：，50202702，5020270202230004300005572，C=3033550202300056748001 248004680040636504143可见，C最少需要4条线，C最少需要4条线，C最少需要5条线，方能划掉矩阵中所有的零。即它们独立零元素组中零1 2 3元素最多分别为4，4，5。三．匈牙利法求解步骤：2151342151341041415914161378119C=求解该指派问题。解：ⅰ）变换效率矩阵，将各行各列都减去当前各行、各列中最小元素。min104141546换01011换104141546换01011换699141613 057405327 8119 7 01420100C= =C9Min 0 0 4 2这样得到的新矩阵C中，每行每列都必然出现零元素。ⅱ）用圈0法求出新矩阵C中独立零元素。进行行检验对CC230137060690532001370606905320100C =C在第i行只有一个零元素ci=0i人干第j件工作效率最好。因此优先指派第i人干第j项工作，而划去第j列其它未标记的零元素，表示第j（即使其它人干该项工作也相对有最好的效率。重复行检验，直到每一行都没有未被标记的零元素或至少有两个未被标记的零元素时为止。本题C

11C14c14443列中未被标记的零元素。这是第4c，再用○圈起，见C43013706001370606905320100进行列检验然后技改元素所在行的其他未被标记的零元素打×。重复上述列检验，直到每一列都没有未被标记的零元素或有两个未被标记的零元素为止。这时可能出现以下三种情况：1每一行均有圈0出现，圈0的个数m恰好等于nm=n.2存在未标记的零元素，但他们所在的行和列中，为标记过的零元素均至少有两个。3不存在未被标记过的零元素，当圈0的个数m<若情况1出现，则可进行试指派：令圈0为止的决策变量取值为停止计算。上例中得到C

后，出现了情况1，可令

=1，

=1，x31=1，

=1

i=。即为最优指派。142243若情况2出现，则在对每行、每列的其它未被标记的零元素任选一个，加上标记○，即圈上该零元素。然后给同行、同列的其它未被标记的零元素加标记×。然后再进行行、列检验，可能出现情况13，出现情况1142243停止计算。若情况3出现，则要转入下一步。ⅳ我们还以例12来说明过程：12487151279171410C69128767146106912106先对各行元素分别减去本行的最小元素，然后对各列也如此，即0404311803011802107301773

列变换C0362C036210232101804005040364002340此时，C中各行各列都已出现零元素。为了确定C中的独立零元素，对C加圈，即0303011801773=023210050402340由于只有4个独立零元素，少于系数矩阵阶数n=5,不能进行指派，为了增加独立零元素的个数，需要对矩阵作进一步的变换，变换步骤如下：对C03对打√的行中，所有零元素所在的列打√，如第102重复上述（）步，直到不能进一步打√为止。对未打√的每一行划一直线，如第1，3，510最少直线数。见C。03011803011803011801773017730232102321=C00504005040234002340Ⅴ：对矩阵

作进一步变换，以增加0元素。（避免打√行中出现负元素，这样就增加了零元素的个数。如C中未被直线覆盖过的元素中，最小元素为cc35=12，31元素都加上1，得到矩阵C0

。30118

301181066200662C1121001210=C00504105040234012340Ⅵ：回到步骤Ⅱ，对已增加了零元素的矩阵，再用圈0法找出独立零元素组。1301113011800662012101050412340C500100010001000100000001000001承建也就是说，最优指派方案是：让A B承建1 3A B2 2A B3 1A B4 4A B5 5这样按排能使总的建造费最少，为z=7＋9＋6＋6＋6=34（万元）四．一般的指派问题在实际应用中，常会遇到非标准形式，解决的思路是：先化成标准形式，然后再用匈牙利法求解。其一般形式为n nmaxz cxijiji1j1nx 1 jniji1ns.t xij

1 inj1x nij处理办法：设最大化的指派问题的系数矩阵为C=)，m=max｛c,

｝,令ijnn 11 12 nnB=

=

c)，则以B为系数矩阵的最小化指派问题和以C为系数矩阵的原最大化指派问题有相同的最优解。ijnn ijnn5：4A，A，A，A4B，B，B，B车床BBBB车床BBBB1 2 3 4工人A11098 7A23 45 6A32 11 2A44 35 6解：C=(c)=

10910987345621124356ijnn0123012300137012301230013765432103100899801100000675423102200ijnn ijnn=B=n=4,所以10X=00即为最优解。

000001100010

（5.7）从而产值最大的分配方案也为5.Z=10＋6＋1＋5=22人数和事数不等的指派问题。1若人数<事数，添一些虚拟的“人，理解为这些费用实际上不会发生。工作B1 2BB3B4B5工人A 10 11 4281工作B1 2BB3B4B5工人A 10 11 4281A 711 10 14 122A 56912 143A 13 15 11 10 74问指派那个人去完成哪项工作，可是总消耗最小？解：添加虚拟人A，构造标准耗时阵：1011101142889206711101412行变换04375569121401479=C131511107684300000000000C=所圈0数=4<5=n,下找最少覆盖0的直线。8920689206043750147968430000009920603264=003687843010000从未划去的元素中找最小者｛9920603264=003687843010000C000001010000=010000000100100X从而最少耗时为z=2＋7＋6＋7=223.一个人可做几件事的指派问题。若某人可作几件事，则可将该人化作相同的几个“人”来接受指派。这几个“人”做同一件事的费用系数当然一样。例6：对例12的指派问题，为了保证工程质量，经研究决定，舍弃建筑公司A和A，让技术力量较强的建筑公司A、A、A来4 5 1 2 3承建。根据实际情况，可以允许每家建筑公司承建一家或两家商店。求使总费用最少的指派方案。12解：反映投标费用的系数矩阵为： BB12

B3B4 B5A4871512A1A79171410A269128

A3由于每家建筑公司最多可承建建筑公司化作相同的两家建筑公司Ai由于每家建筑公司最多可承建建筑公司化作相同的两家建筑公司Ai系数矩阵变为：48B17B215B312B4B54871512791714107917141069121276912127上面的系数矩阵有6行5列，为了使“人”和“事”的数目相同，引入一件虚拟事，使之成为标准的指派问题，其系数矩阵为：B1B2B3B4 B5B648487151204871512079171410079171410069128706912870000750000750000750列变换31106303110630215000215000的◎数=5<0=000750=0007500007510007500007513110630√-12095203110630√-1209520215000215001215000215001从而得一最优指派：010X=0

01000000001000000001

承建公司 商店A1B1AB32000010 A B2000100 23A3总费用为z=7＋4＋9＋7＋8=35(万元)4．某事不能由某人去做的指派问题某事不能由某人去做，可将此人做此时的费用取作足够大的M。

B6=ψψBB5例分配甲、乙、丙、丁四个人去完成BCDE虑：a).任务E必须完成，其它4项任务可选3项完成。但甲不能做A项工作。b)其中有一人完成两项，其他人每人完成一项。任务 A B任务 A BC D E人甲甲2529314237乙3938262033丙3427284032丁2442362345解：这是一人数与工作不等的指派问题，若用匈牙利法求解，需作一下处理。由于任务数大于人数，所以需要有一个虚拟的人，设为戊。因为工作E必须完成，故设戊完成E的时间为M（M为非常大的数，即戊不能做工作，其余的假想时间为，建立的效率矩阵表如下：务人任务人任ABCDE甲M29314237乙3938262033丙3427284032丁2442362345戊0000M用匈牙利法求解过程如下：M29314237M02133938262033 行变换191860342734272840327011324423623451191300000M0000M021331918608701130119130170000MC= 522M

列变换由于◎数=4<5=阶数，下找最少覆盖0的直线M0213M021331918608√-1701130=119130170000M√-1M021331817507m=｛19,18.6.13,1,19,13,22｝=12、4M021331817507甲 BC= 7 0 1140 从而得最优指派： 乙 D018120160 0 0 1M 丙 E丁 A最少的耗时数z=29＋20＋32＋24=105.1方案2方案3方案4方案5○，丁，。这些思路都比较烦，请看下面的思路：设有虚拟人戊，它集五人优势为一身。即戊的费用是每人的最低。戊所做的工作即为此项工作的费用最低者的工作。务人任ABCDE甲2529314237乙3938262033丙3427284032丁2442362345戊2427262032以下用匈牙利法求解：25292529314237046171239343827262820403332行变换19718061013135244236234519130222427262032476012 C=046171219186013701135=C1913022476012对C0=3<5=n0040461712191860137011351913022476012C=√√在未划去的数中选最小者1，未划取得行都减去1，划去的列都加上1得：045187181740770004518718174077001400811016364064，未划取得行都减去这个4，划去的列都加上这个4，得C：0010011831813103110018004701232002C= 再圈0试指派，结果为： 乙 丙 丁 A戊 C其中戊是虚拟人，不能真作，它作C工作是借乙（此列最小时数26是C所创业绩）优势，应由C来作。即C做两件工作：D，C。第7次课2学时第五章第7次课2学时第五章授课章节授课方式□√理论课□讨论课□实验课□习题课□其他课堂教学了解动态规划模型的基本概念，理解无后效性，掌握最短路问题的求解方法。目的及要求课堂教学重点：动态规划模型的基本概念和最短路问题。重点及难点难点：最短路问题。教学过程教学方法及手段8.1动态规划的基本概念多媒体讲解教学过程动态规划的基本概念。实例讲解8.2最短路问题无后效性与最短路问题的求解。2、课件动态规划的基本概念动态规划（DynamicProgramming）2050Bellman）发展起来的一种解多阶段决策问题的优化方法。所谓多阶段决策问题是指一类活动过程。它可按时间或空间把问题分为若干个相互联系的阶段。在每一阶段都要作出选择决策（从而称为动态规划策略。所谓多阶段决策问题就是求一个策略，使各个阶段的效益总和达到最优。概念：先把问题从中间站B，C，D，E用空间位置分成5个阶段，阶段用阶段变量k来描述，状态与状态变量：每一阶段的左端点（初始条件）状态（即开始的客观条件，或称阶段初态。如第三阶段有四个状态S=｛C,C，C，C｝,第四阶段有三个状态S=｛D,D,D｝, …3 1 2 3 4 4 1 2 3描述过程状态的变量称为状态变量：用小写s,s,s…表示第一，第二，第三…阶段的状态变量。当处在状态C时，我1 2 3 2们可记s=C3 2正像离散型R.V“X=2”代表一事件一样。(3)决策与决策变量：如当处于CDD2 1 2处于某一阶段的某一状态时，可以作出不同的决策（或选择，从而确定下一阶段的状态，这种决定（或选择）决策。如选择D，记2u3（C2）=D2说，当处于C2状态时，下一步的决策为D2。kk其中u(skk

)表示第k阶段当状态处于s

时的决策变量。kk kk

表示第k

出发的允许决策集合。如k3 D(C)k3 1 2k显然，uk

)∈k∈

(s)。k k。策略与最优策略，u)u，1 1 2

)u，3，

)u，3 4 ，

)u，5，

)5策略这里的最短路径成为最优策略。动态规划就是在允许策略集中选最优策略。状态转移方程：是描述由第kk+1=s T=k1 k

)k k上例中状态转移方程为：=s u=k1 k

)k指标函数。相当于动态的目标函数，最后一个k阶段的目标函数就是总的目标函数。它分阶段指标函数和过程指标函数。阶段指标函数是指第k阶段，从状态sk

出发，采用决策uk

时的效益，用d

k

)表示。最优指标函数是指从第k阶段状态s

采用最优策略到过程终止时的最佳效益值，用kkfkkk

)表示。最短路问题思路算法。这一点与线性规划不同。线性规划是一种算法。下面从一典型的例子去说明动态规划的基本思想与原理：CC15A28A284D1B331C526E145683D2C2F73314E2B2378D3C445第一阶段 第二阶段 第三阶段 第四阶段 第五阶段逆序递推法：倒退着从F向A走，每倒退一步，思想上问自己F的距离最短？”我们分5步来解决问题：k=5求f

S｛E，E，故分情况讨论，先说f

)=？若最佳路径从A出发通过E的话，由E到5 5 5 1 2 5 1 1 1终点F的最短距离为1f15

(E)=5

f5

)=3（只有唯一的选择）故最优决策为：u

(E)=F，u

)=F25152k=225152求f求4 4

)=？由于S｛D,D,D，下分四种情况进行讨论：4 1 2 3d)f) 34f4 1 1 5 1 =min =7, u

)=E4 1 d4

,E)f(E1 2 5

) 532

4 1 1.f4

)=min

d42d2

)f2 1 5 ,E)f(E

) 64)=min 23=5, u4

)=E22.24 2 2 5 2d)f) 14f4 3 1 5 1 =min =5, u

)=E4 3 d4

,E)f(E3 2 5

) 332

4 3 1.(3) k=3时 S=｛C,C，C，C｝,3 1 2 3 4f

)=min

d3 1

)f1 4

) 571 =min =12, u

)=D3 1 d3 1

)f2 4

) 852

3 1 1.32同理，f32

u

)=D22.233f333

u

)=D32.334f343

u

)=D43.43（4）k=4时 S=｛B,B｝32 1 2d22 12

)f1 3

) 21222122f2 1

d

1

)f2 3

)=min 310=13, u

(B)=C12.1d)f) 682 1 3 3 3

f2

u

C23.22（5）k=1时， S=｛A｝21d)ff(A)=min 1 1 2

) 4131 =min =17,

=B1 d1 2

)f2

) 515

1 1.再按计算顺序的反推可得最优策略：12u(A)=B u121.

(B)=C12.1

u3

)=D22.2

u4

)=E22.2

u5

)=F2.2从而得最优路径：A—B—C—D—E—F1 2 2 2最短距离为

1fA)=17。1由上面的过程可以看出，在求解的各个阶段利用了第k段和第k+1段的如下关系：fk k

) mindkuk

k

)fk1 k

)}kf(s)06 6

(7.3b)（7.3b）边界条件。逆向标号法每退到一站，看终点F，找最短路径及最短路径的距离，标号。画路径。C15C152（7）（13）8（10）4D13（4）B1354C2（17）65E1（5）4A（8）68（15）3D22（3）F5C73134B（5）E2237（9）8D3C44此时的（？）？=最优指标函数值f.得最优路径：—C—D—E—F1 2 2 2总距离为17.顺序递推法：此法类似于逆序递推法。从起点A向终点F倒退。k=1fA)=0，此为初始条件。退向允许决策集SB｝此时退向BAf

)=4，01 此时路径（或最优决策）是唯一的：u=A；1

1 1 2 1 1 1f(B)41 1

f)51 2u)Au)A1 1 1 2k=2f2

)d1 1

)f1 1

)246u(C2

)B1 1d

3485634856475f

min

1 2 1

min 72 2 d)f)2 2 1 2u)B2 2 1

d

)f)f2 3

min

1d2

3 1 1)f3 1 2

min 10u)B2 3 1f2

)d4 2

)f4 1

)7512u)B2 4 2k=3

d)f

) 56f

min

1 1 2

min 113 1 d)f) 472 1 2 2u)C, u)C3 1 1 3 1 2类似的f3

)12 f2 3

)143u(D)C，3 2 2

u(D)C3 3 3同理，f)14 f4 1 4

)142u(E)D，4 1 1

u(E)D4 2 2最后f)175u)E5 2逆推最优策略：A—B—C—D—E—F。与前相同。1 2 2 2全部计算情况如图7-3（6）CC152（4）883（7）4D13（14）4B1C5265E（12）14A（10）6（17）83D22（14）F5C（5）73134E2B（14）2（12）D3783C44递推关系式：fk k

) mindkuk

(s,uk1

)fk1

)}kf(s)00 1

(7.5b)始状态又给定了终止状态，则两种方法均可使用。如习题7.2/P237，终点有三个，用逆序解法较好。资源分配问题例：公司计划在三个不同的地区设置4个销售店，根据市场预测，在不同的地区设置不同数量的销售店，每月可获得的利润如下表所示。试问应如何设置，才能使每月所获得的总利润最大？其值是多少？（15分）利利地123润区店数00001161210225171433021164322217设：sknk(xkxk k k k k(sknsk k kx3s3x3s3P3 3f3 3x30 1 2 3 400001101012141423316163417174x2Px2P)fx)2 2201234000010+1012+012120+1412+101722130+1612+1417+102127240+1712+1617+1421+1022312，3s22 23 22f)x*x1s1x1s1P(x)f(4x)1 1 2 1f)1 1x*10 1 2 3 440+3116+2725+2230+1232+047211

2x*、2、

1、3、

147。第8次课2学时1第8次课2学时12授课章节授课方式□√理论课□讨论课□实验课□习题课□其他课堂教学理解图、树的基本概念，掌握最小支撑树的求解方法目的及要求课堂教学重点：图、树的基本概念，最小支撑树的求解。重点及难点难点：最小支撑树的求解方法——破圈法和避圈法。教学过程教学方法及手段8.1动态规划的基本概念多媒体讲解教学过程动态规划的基本概念。实例讲解8.2最短路问题树的基本概念与性质，最小支撑树的求解方法破圈法和避圈法。第9次课2学时3授课章节授课方式□√理论课□讨论课□实验课□习题课□其他课堂教学了解路的概念，掌握最短路问题的求解方法。目的及要求课堂教学重点：最短路问题的Dijkstra算法。重点及难点难点：最短路问题的Dijkstra算法。教学过程教学方法及手段教学过程10.3多媒体讲解路的基本概念，最短路问题的Dijkstra算法思想及步骤。实例讲解第10次课2学时授课章节4授课方式□√理论课□讨论课□实验课□习题课□其他课堂教学了解网络、流、可行流、增广链、截集与截量的基本概念，掌握最大流问题的求解方法。目的及要求课堂教学课堂教学重点：网络、流、可行流、增广链、截集与截量的基本概念，最大流问题的求解。重点及难点难点：增广链的寻找方法，最大流的标号法。教学过程教学方法及手段多媒体讲解教学过程10.4最大流问题网络、流、可行流、增广链、截集与截量的基本概念，增广链的寻找方法，最大流的标号法。 实例讲解第11次课2学时授课章节第11次课2学时授课章节5授课方式□√理论课□讨论课□实验课□习题课□其他课堂教学了解最小费用最大流的基本概念，掌握最小费用最大流问题的求解方法。目的及要求课堂教学重点：最小费用最大流的基本概念，最小费用最大流的求解方法。重点及难点难点：构造赋权有向图。教学过程教学方法及手段教学过程10.5最小费用最大流问题多媒体讲解最小费用最大流的基本概念，最小费用最大流的求解方法。实例讲解第12次课2学时授课章节6授课方式□√理论课□讨论课□实验课□习题课□其他课堂教学了解中国邮递员问题的基本概念入欧拉链、欧拉圈，掌握中国邮递员问题的求解方法。目的及要求课堂教学重点：动态规划模型的基本概念和最短路问题。重点及难点难点：最短路问题。教学过程教学方法及手段10.5多媒体讲解教学过程一笔画与欧拉链、欧拉圈概念，中国邮递员问题的求解思路和步骤。实例讲解2、课件图的定义：图是在纸上用点和线画出反映对象之间关系的示意图。图中点的相对位置如何、长短曲直并不重要。例1图10-2（P252）是我国北京、上海等十个城市间的铁路交通图。这里的点代表城市，点与点的连线代表两个城市间的铁路线。例2P252种图10-3与图10-5没有本质的区别。关系的种类及其表示：对称性的关系甲与乙有这种关系，同时乙与甲也有这种关系。如同学关系非对称的关系甲与乙有这种关系，乙与甲未必有这种关系。如甲认识乙，乙未必认识甲；一场比赛中，球队A胜球队B，球队B不能胜球队A。图的构造：一个图是由一些点及点之间的连线（带箭头或不带箭头）所组成。不带箭头的连线称为边，带箭头的连线称为弧。如果一个图是由点及边组成的，则称为无向图，记为G )。V、E分别为图G的点集合和边集合，一条连iij。j结点vV的边记为]iij。j如果一个图是由点及弧所构成的，则称为有向图，记为D ,A)。V、A分别为图D的点集合和弧集合，一条从ijv指向从ij

,v)。j。i若e[是ee是u及v的关连边。若图G重某个边的两个端点相同，则称e是环；i若两个点之间有多于一条的边，则称这些边为多重边；一个无环、无多重边的图称为简单图；无环但有多重边的图成为多重图。G以点v为端点的边的个数称为v的次，记为d(d。环在计算次时算两次。G次数为奇数的点称为奇点；次数为偶数的点称为偶点；次数为1的点称为悬挂点，它的关连边称为悬挂边，次为零的点为孤立点。图G )中，所有点的次数之和是边数的两倍定理任何一个图中，奇点的个数必为偶数。i图G )中，一个点、边交错序列i1

,e,vi i1

i i ik1 k1

)，如果满足eiti

]i it t1（t.,1，则称为一条联结v和

，称点

为链的中间i i i i i i i i1 k 1 2 k 2 3 k1点。链

v

)；若链中所有的点都是不同的，i i i i i1 2 k 1 k

i i i i1 2 k1 1ii则称为初等链；若圈中的点v,vii1 2

ik1

以后所涉及到的链（圈，除非特别交代，均指初等链（圈。若链（圈）中含的边均不相同，则称为简单圈。图G中，如任何两点之间至少有一条链，则称G分图。给定图G VE，如果图G'VE)，有VV、E'E，则称G是G的一个支撑子图。给定有向图D ,A)，去掉其所有弧上的箭头，就得到一个无向图，该图为D的基础图，记为G。D中的一条弧a(，称u为av为a的终点。iii设点弧交错序列(v,a,viii1 1 2

i i ik1 k1

在基础图G中所对应的点边序列是一条链，则称该点弧交错iD的一条链；而且如果满足ei

到i 到

)（t.,1，则称为从v

v的一条路；如果第一t t t1 1 kii点和最后一点相同，则称之为回路。ii一、树及其性质定义：一个无圈的连通图称为树。定理：设图G VE是一个树，pG)2（点数，则G中至少有两个悬挂点。定理图G )是一个树的充分必要条件是G不含圈，且恰有p1条边。定理5：图G定理6：图G

VE是一个树的充分必要条件是G（边数）qG)pG)1。是一个树的充分必要条件是任意两顶点之间恰有一条链。推论T的一个支撑树。：图

是图G )的一个支撑子图如果图T恰好又是一棵树则称T是G有支撑树的充分必要条件是图G是连通的。6直到不能进行为止。例7：给图G

上所有的边

]都赋予一个数w

，则称这样的图为赋权图，w

为边

]上的i j ij ij i j权。这里的权是指与边有关的数量指标，根据实际问题可表示距离，时间，费用等等。：如果图

是图G )的一个支撑树，称E中所有边的权之和为支撑树T的权w)，w) wij[v,v]Tij如果支撑树T*w*)是G的所有支撑树的权中最小者，则称T*是G的最小支撑树。最小支撑树的求解方法：避圈法首先选一条最小权的边，然后每一步总从与已选边不构成圈的那些未选边中选择一条权最小的边（的边都是权最小的边，任选其中一条，重复此步骤直到不能进行为止。破圈法任取一个圈，从圈中去掉一条权最大的边（如果有两条或两条以上的边都是权最大的边，任意去掉一条复该步骤直到不能进行为止。例：求下图的最小支撑树。（1） 避圈法v5 vv53467

5 vv5v3461 3 v 1 7 3 vv 6 v 61 15 4 5 422vv v v22v2 4 2 4vv5 v 5 vvv5 53 4 3 46 61 7 3 v 1 7 3 vv 6 v 61 15 4 5 424v534624v53467354222 4v v53 46v61 7 3 v vv6v 6 115 424v v v2 2 v242 4（2）破圈法vv5 v 5vv35 v 5364 3 4663 1 7 3 v 13 vv 6 6v1 15 4 5 42v 2v 2 4 2 2 vv5 v v 5 4v35 3 536 4 6 4v1 7 3 v 1 7 3 vvv 6 61 15 4 5 42v v v 2 v2v35v5v35v541734v5 vv3536 4或1 7 3 vv v或v 66 v 61 15 4v 2 v2

v 2 v2 4最短路问题问题的引出：i存在一个赋权有向图D ,A)，对其中每一个弧ai

j)，相应地有权w)j

ij；给定D中的两ij、s个顶点v、s

vPD中从v

vPPw。最短路问题到tsts就是要在所有从v到tsts

v的路中，寻找一条权w*)最小的路，使到tw*)minw)到tp到sP*是从v到s

vw*)也成为从v

v的距离。到tsts即，最短路问题的本质是在在一个赋权有向图中，求出从给定一个点v到tsts

到任一点v

的最短路。t最短路问题的算法：tij（1）权w 0的情形：Dijkstra算法ijDijkstra（1930-2002），toPV最短路径算法的创造者，第一个Algol60和开发者。s 基本思想：从初始点v出发，与每个点对应，记录下一个数（称为这个点的标号，它或者表示从vs ss的权（称为P标号，或者是从v到该点的最短路的权的上界（称为T标号，方法的每一步是去修改TTPDPp1步，就可求出从v到各点的最短路。ss步骤：0 s s s 开始（i0，令S v}，Pv)0， v)0，对于每一个vv，令T) 0 s s s M，令ks。i①如果S i

，算法终止，此时，对于每个vSd

Pi k j j i j j k kj ②考察每个使)A且v S的点v，如果T)P)w，则把T)修i k j j i j j k kj k kj P)w，把修改为kk kj j③令Tj

)

T

) v

P

)T)，j，i vSj i

i i ijjjj令Sijjjj

S i

}，k ji换成ivSijiji

d，s，

P而对每一个vSid)T。例：求下图中v1到各顶点的最短路。v 1 v2 526 2 v6 93v v6 3 331 3 4 101 2 v2v4 827v 10 v4 6解：i0，

}，P)0，)0；T) ，)M，0 1 1 1 i ii,令k1；1考察所有从v1

出发指向其余点的弧（经1步可达到的不属于S

vvv2，，3 2，，0P02

)P)w1

6T<2<

) ，所以，将T

)修改为

6，

)1；同样的方法可得22T223

)3 、3、

)1T，4，

)1 、4、

)1。4在所有的TT4

)1P

)1，得S

S 0

}1

k4。41、14i1，考察从41、14

v出发指向其余点的弧（经1S

vvv2，，2，，641可得T641

)P(v)w4

11 、6、

)4 T，3，

)3 、3、

)1T，2，

)6、32)1。所有T标号中，T32

)3最小，得P

)3S，2，

S 1

}61 6

，k3。31、3i2，考察从31、3

vv出发指向其余点的弧（经1S

v。、2，得4 2T、2，得4 22

)5 、2、

)3T(v，6，

)11 、6、

)4。所有TT

)5最小，因此，2P25，625，6

)5S，3，

S 2

}1

3

}，k2。1i3，考察从1

vv v、、、4 3 、、、

出发指向其余点的弧（经1步可以达到的不属于S

v。得3T得35

)6 、5、

)2T，6，

)11 、6、

)4。所有TT

)6最小，因此，5P5、545、54

)6S，4，

S 3

}1

3

,v}，k5。15i4，考察从15

vvv、、、4 3 、、、

v出发指向其余点的弧（经1S

vvv6，，6，，得T得6

10 、6、

)5T(v，7，

)9 、7、

)5T(v，8，

)12 、8、

)5。所有T标号7T7

9P

)9S6，，5856，，58

S 4

}1

3

5

k7。71i5，考察从71

vvv、、、4 3 、、、

vv出发指向其余点的弧（经1S

v。、、得5 T、、得5 6

)10 、6、

)5T(v，8，

)12 、8、

)5。所有TT

)10最小，因此，6P66

)10S，6，

S 5

}1

3

5

,v}，k6。16i6，考察从16

vvv、、、4 3 、、、

vvv、、、5 7 、、、

出发指向其余点的弧（经1步可以达到的不属于S

v。8得6P8得68

)12 、8、

)5S，7，

S 6

}1

3

5

6

}，k8。9i7，只剩余9

，没有任何指向v

T

) )M，。9，。99计算完毕。99综合计算结果：P1

)0P(v，4，

)1P，3，

)3P(v，2，

)5P(v，5，

)6P(v，7，

)9P(v，6，

)10，P8

)12T(v)，。9，。，)0 ，1

)1 ，3，

)1 ，2，

)3 ，5，

)2 ，7，

)5 ，6，

)5，，)5 ，8

)M。ij若是无向图（如P26，例11，则将其任何一边vij

视为两条具有相同权的弧

)和j i j 和j i

)，然后把ik jDijkstraik j任何一点的最短路（也叫最短链。

A且v S的点v，采用同样的思路可求得无向图中某一点到其余（2）含负权的情形ijDijkstra算法只适用于w 0的情形，在含负权的情况下，算法实效。如下图，ijv21-3v12 v31到ii到sjsiDijkstra1到ii到sjsi

v1，但事实上，从

经由v

v的权为-1。13到22s引理：如果从v13到22s

到vj

的最短路是从v

)到j到

，则，从v

v的这条路到s必然是从v到s

v的最短路，可记为d

,v)。i。s j s is从v到v的最短路ds j s isd

)

)w}s j i

s i ij为求得该方程的解，可用如下地推公式：ds

)j

（j..）sj对t

d))w

}，js j i

s j ij若进行到某一步k，对所有j，有ds

)dj

,v)jsds

v)（j）为v

s到各点最短路的权。swwijd)1 j点v1v2v3v4v5v6j例：求下图中从v1到各点的最短路。jv2-1vv2-1v562-1-2-3v3-51v6-3117382-5v4-1v71 8vvvvvvvvt1t2t3t4123456780-1-230000602-1-5-5-5-30-51-2-2-2-2023-7-7-7-101-3-31017-1-1-1vv7v8-105-5-5-3-5066链的确定：（1）采用类似于Dijkstra的方法，在迭代过程中，如果d

))

}d)ws j)ikj 0。k

s j ij

s i ij0 0s