《运筹学》教案

《运筹学Ⅰ》教案

课程名称：运筹学 授课教师：孔造杰 课程学时：64

开课时间：第三学年第一学期

授课方式：课堂教学为主，实验教学为辅

2011年1月

时间安排：周学时4，共16周，总学时64，

授课方式：课堂教学与实验教学结合，以课堂教学为。初步安排课堂教学52学时左右，实验教学8-10学时，实验课以上机为主，辅以习题课。

时 间：第一周第一次 授课方式：课堂教学 教学内容：

一、绪论

1． 运筹学的起源与发展：?起源于二次大战的一门边缘交叉学科?由于战争的需要而

产生与发展；战后在经济、管理和机关学校及科研单位继续研究；我国于1982

年加入IFORS，并于1999年8月组织了第15届大会。

2． 运筹学的特点及研究对象：运筹学是一门边缘性的、综合性的应用科学。它是以应

用数学为主要技术手段，综合应用经济、军事、心理学、社会学、物理学、化学以及工农业生产的一些理论和方法，对实际问题找出最优的或满意的解决方案的一门科学。

3． 运筹学解决问题的方法步骤：?明确问题?建立模型?设计算法?整理数据?求解模型?

评价结果?实施控制 4． 运筹学的主要内容

5． 运筹学的主要应用领域

二、第一章：线性规划基础——§1-1问题的提出，§1-2LP模型与解的概念

1． 问题的提出：从两个生产与经济问题的实例出发，引导学生认识实际问题同数学模

型之间的联系，认识规划模型同一般的数学方程、数学函数之间的区别，认识用数学方法解决实际问题的基本思维模式和方法途径。

2． 线性规划的一般数学模型：掌握线性规划的构成形式及要素：决策变量、约束条件、

目标函数。 线性规划的一般模型为：

目标函数：max(min)z?c1x1?c2x2???cnxn 约束条件：s.t.

a11x1?a12x2???a1nxn?(?,?)b1 a21x1?a22x2???a2nxn?(?,?)b2

? ? ?

am1x1?am2x2???amnxn?(?,?)bm

x1,x2,?,xn?0

3．线性规划解的概念：可行解——满足所有约束条件包括非负条件的解；最优解——使目标函数①达到最大值的可行解；基；基本解——非零分量的数目不大于方程

数m，则称X为基本解；基本可行解——满足非负条件的基本解；可行基——对应于基本可行解的基。

时 间：第一周第二次 授课方式：课堂教学 教学内容：

一、线性规划图解法（§1-3）

1. 用图解的方法解上一节提出的线性规划模型。通过图解，使学生较直观地看到线性

规划模型的求解过程及其意义，掌握图解法的基本方法和技巧，清楚地认识到线性规划有解的条件和最优解可能存在的位置。

2. 通过图解法直观地认识线性规划解的集中特殊情况：当目标方程直线与某一约束直

线平行时，最优值不唯一；有可行域，但无最优解，即目标函数的值z???无

可行解；当约束条件出现相互矛盾时，则没有可行域。

二、线性规划的求解基础（§1-4）

1. 线性规划的标准式：

maxz?c1x1?c2x2???cnxn

s.t. a11x1?a12x2???a1nxn?b1

a21x1?a22x2???a2nxn?b2

? ?

am1x1?am2x2???amnxn?bm x1,x2,?xn?0

2. 化一般模型为标准模型：分成三种情况：若问题的目标函数为最小化minZ?CX；

若约束条件为不等式；若某一决策变量xk无非负约束。 3. 从解线性方程组引申到解线性规划模型

4. 线性规划求解理论：凸集、 凸组合、顶点、三个定理

时 间：第二周第一次 授课方式：课堂教学 教学内容：

线性规划的应用§1-5

分成人力资源问题、生产计划问题、套裁下料问题、配料生产问题、投资问题等若干方面进行实例分析，主要引导学生学习怎样从实际问题列出其规划模型。

时 间：第二周第二次 授课方式：课堂教学 教学内容：

一、单纯形法及其计算步骤（§2-1）

1. 单纯形表的形式及其构成：在单纯形表中不仅反映增广系数矩阵，而且反映检验数?、?规则判定值，以及目标函数的取值。 2. 计算步骤：

1) 找出初始可行基，建立初始单纯形表，确定初始基本可行解。

2) 检查对应于非基变量的检验数?j ，若所有的?j?0,(j?m?1~n)，则当前解为

最优解，停止迭代；否则转入下一步。

3) 在所有?j?0的列中，若有一个?k所对应变量xk的系数列向量中的各分量均小于

''T,?,amk)?0，则此问题无最优解，停止迭代；否则转下等于零，即pk?(a1'k,a2k一步。

?j?0)??k，确定xk为进基变量；根据?规则?l?min(4) 根据max(ibi│aikaik?0)?bl，确定xl为出基变量。于是得到迭代主元素alk，转入下一步。 alk5) 以alk为主元素进行迭代运算（高斯消元法迭代），即把alk变为1，而把同列的其它

元素变为零，得到新的基本可行解所对应的新的单纯形表。转入2。

三、人工变量的处理（§2-2） 大M求解法

在“≥”、“=”约束中，为了构造单纯形表的初始基，一般就需要加入人工变量。人工变量是实际问题模型中没有的人为的虚拟变量，所以这些变量在最终解中不能为基变量，而必须是非基变量（以确保其等于零），为确保这一点，就需采取一定的措施，大M法就是措施之一。

为确保人工变量从基中退出，以不影响目标函数的取值，在目标函数中给每一个人工变量设定一个很大的负系数?M（M为任意大的正数），这样，只要人工变量没有退出基，目标函数就不可能取到最大值。此即所谓大M法。 两阶段法

第一阶段：判断原问题是否有解。为此，需要建立一个辅助线性规划，并求解。辅助问题是这样的：目标函数取成所有的人工变量之和，并取其极小化；约束条件为加入人工变量后的原约束。

第二阶段：求原问题的最优解。对于上述第一种情况，在当前基中不含有人工变量，将目标函数变为原问题的目标函数，在单纯形表中将价值系数行换为原问题的价值系数。划去人工变量所在的列即得到原问题的初始单纯形表。然后重新求检验数，继续迭代，直到求得原问题的最优解。

时 间：第三周第一次 授课方式：课堂教学 教学内容：

改进单纯形法（§2-3）

1. 单纯形表的矩阵描述 基变量 XB 检验数行 非基变量 XN1 BN1 ?1对应于松弛变量的 矩阵XS ?1I 0 B?1Bb?1 CN?CBBN1 ?1?CBB CBBb?1

2. 对于小型的线性规划模型用单纯形法，手工求解还是比较方便的，但我们也发现每次迭代都需计算很多无关的数字，对于大型的线性规划模型，不但手工解比较困难，就是借助计算机也会占用更多的空间和时间。为适应计算机计算的需要，提出一种改进的办法。

LP的计算机求解§2-4

介绍用Excel求解线性规划的方法、步骤和注意事项

案例分析§2-5

时 间：第三周第二次 授课方式：课堂教学 教学内容：

一、对偶问题的提出（§3-1）

1. 从经济意义上提出对偶问题：针对第一章中例1的实际生产问题从另一个角度提出，

并进行具体分析、建模； 2. 从数学模型上提出对偶问题：根据线性规划的矩阵描述和单纯形表的矩阵描述，从

数学上定义一个新的模型，这个模型同原模型不仅有同样的解值，而且有着一一晖映

的对应关系。

二、写对偶问题（§3-2）

1. 为便于叙述和记忆对偶问题，通常规定一个标准形式，一般规定原规划为“≤”约

束，对偶规划为“≥”约束，变量均≥0的对偶问题为标准形式。把它们之间的关系

用表格形式表示出来，可以写成表3-2的形式

xj yi 原关系 x1 x2 ┅ xn minw y1 y2 ┇ a11 a12 ┅ a1n a21 a22 ┅ a2n ┇ ┇ ┇ ≤ ≤ ┇ ≤ b1 b2 ┇ ym 对偶关系 am1 am2 ┅ amn ≥ ≥ ┅ ≥ bm maxz?minw maxz c1 c2 ┅ cn 2. 原问题模型于对偶模型之间的对应关系 原问题（或对偶问题） 目标函数maxz 资源条件（约束右端常数项） 价值系数（目标函数系数） 变 量 约束条件

n个变量 ≥0 ≤0 无约束 m个约束 ≤ ≥ ＝ 对偶问题（或原问题） 目标函数minw 价值系数（目标函数系数） 资源条件（约束右端常数项） 约束条件 变 量 n个约束 ≥ ≤ ＝ m个变量 ≥0 ≤0 无约束 时 间：第四周第一次 授课方式：课堂教学 教学内容：

一、对偶问题的性质：

1. 对称性：对偶问题的对偶是原问题。

2. 弱对偶性：若X是原问题的可行解，Y是对偶问题的可行解，则存在CX?Yb

??Y?b时，?是对偶问题的可行解，当CX?是原问题的可行解，Y3. 等值最优性：设X?,Y?分别是原问题和对偶问题的最优解。 X4. 对偶定理：若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等。

?,Y?分别是原问题和对偶问题的可行解，X,Y分5. 互补松弛定理（松紧定理）：若Xss?为最优解时，有?与Y别是原问题和对偶问题的松弛变量，那么，当且仅当X??0和X?Y?0 。 XsYs6. 原问题的检验数对应对偶问题的一个解。

为了使学生掌握这些定理和性质，对上述性质进行必要的证明于说明，使学生能够真正理解其原理。

二、影子价格

影子价格是对偶规划问题的经济解释。

在单纯形法的的每一步迭代中，目标函数取值z=CBB－1b，和检验数CN－CBB－1N中都有乘子Y=CBB－1，

变量yi*的经济意义是在其他条件不便的情况下，单位资源变化所引起的目标函数的最优值的变化。

所以，yi*代表对第I种资源的价格估计，这种估计是针对具体工厂的具体产品而存在的一种特殊价格，称其为影子价格。

时 间：第四周第二次 授课方式：课堂教学 教学内容：

对偶单纯形法（§3-4）

对偶单纯形法并非将原问题写成对偶问题，再用单纯形表求解，而是利用对偶问题的性质求解线性规划模型，它提供了单纯形表的另一种用法。

在单纯形表中，b列对应于原问题的一个基本可行解，而检验数行则对应其对偶问题的一个基本解。在前面我们进行单纯形表的迭代中，始终保持原问题为基本可行解（即b列大于等于零），而对偶问题为基本非可行解（即检验数行含有正值），一旦检验数行有基本非可行解变为基本可行解，则原问题和对偶问题同时达到最优解。

根据对偶问题的对称性，单纯形表的迭代过程也可以反过来进行，即保持对偶问题始终是基本可行解（即保持??C?CBB?1A?0），而使原问题从基本非可行解逐步迭代到基本可行解，从而使原问题和对偶问题同时得到最优解。这种单纯形表的应用方法称为对偶单纯形法。

对偶单纯形法的解题步骤，用流程图表述如图3-1。

x以alk为主元素进行单纯形表迭代 所有?j?0? N 单纯形法迭代求解 问题无解停止 Y 所有a?0? ljN Y 列出初始单纯形表 引入人工变量 重列单纯形表 Y 所有b?0? iN 得最优解停止 所有?j?0? Y 确定出基变量 N minBbi|Bbi?0?Bbi???1???1????1?lx确定进基变量 ?cj?zj?c?zk??min?|alj?0??kjalk?alj?图3-1：对偶单纯形法流程图

时 间：第五周第一次 授课方式：课堂教学 教学内容：

习题课

系统总结第一章至第三章线性规划的所有内容，讲解重点习题的正确解法和思路，留出20分钟进行课堂答疑。

时 间：第五周第二次 授课方式：课堂教学 教学内容：

一、灵敏度分析——目标函数系数的变化（§4-1）

1. cj是非基变量xj的系数

在单纯形表中，cj的变化仅影响到其检验数，而且当cj是非基变量xj的系数时，仅影响该非基变量xj的检验数。

非基变量的检验数为 ?j?cj?CBB?1Pj

当cj变化了?cj后 ?'j?cj??cj?CBB?1Pj

??cj?CBBPj?cj

?12．cr是基变量xr在目标函数中的系数 单纯形表中的检验数为 ?j?cj?CBB?1Pj

由于cr是基变量的系数，所以它的变化不仅影响其对应变量的检验数，而且影响到CB的变化，进而影响除基变量之外的所有变量的检验数。 由此得到?cr的变化范围为：

max{?j/arjarj?0}??cr?min{?j/arjarj?0}

jj''''二、灵敏度分析——右端常数项的变化

在最终单纯形表中，右端常数项表示最终基变量的取值，因而不能为负。这时我们谈最优解不变，是指最优基不变。

在单纯形表的最终表中，基变量的取值为：XB?Bb?b

若b中第r个分量br变化了Δbr，即b?b??b 其中 ?b?(0,...,?br,...,0) 则变化后的基变量取值为： XB?Bb?B(b??b)

?Bb?B?b ?b?B?1?1?'T'?1'?1?1?1?0??br?0?

T?有Max{?bi/airair?0}??br?Min{?bi/airair?0}

ii时 间：第六周第一次 授课方式：课堂教学 教学内容：

系数矩阵A的变化（§4-3）

1. 由于aij属于非基变量的系数列向量，所以它的变化仅仅影响到该非基变量的检验数，

而不影响其它任何量。因为Y?0，所以当yi?0时有：?aij??j/yi

2. 系数矩阵A中某列向量变化后的分析：如果系数矩阵A中某一列向量Pj 发生了变化，

且其对应的变量xj为非基变量，那么Pj的变化仅影响最终表中的检验数?j。如果

?'j?0，则说明Pj变化后并不影响当前解；如果??1''j?0，则说明Pj变化后要影响

到当前解，需要求出最终表中第j列的新数据BPj填入第j列，然后以xj为进基变量继续迭代，直到得到最优解。

3. 如果系数矩阵A中发生变化的列向量Pj为基变量，则Pj变化后不仅影响变量xj的检

验数，而且影响到最终表中的Pj也不再是单位列向量，即B和B?1都要变。这时要做的是求出最终表中xj列的数，并通过迭代使该列恢复单位向量，再根据恢复后的状态予以处理。

4. 系数矩阵A中增加一列或一行的分析（通过例题分析说明A中增加一行或一列之后

对最优解的影响。总结如下：

① 若修正后的原问题与对偶问题的解都是可行解，则修正后的解仍是可行解； ② 若出现原问题是可行解，对偶问题是非可行解，则按单纯形法继续迭代求出最优解；

③ 若对偶问题是可行解，原问题是非可行解，则按对偶单纯形法继续求出最优解； ④ 若原问题与对偶问题的解均是非可行解，这时就要引入人工变量，建立新的单纯形表重新计算。

计算机求解中Excel灵敏度报告

时 间：第六周第二次 授课方式：课堂教学/答疑 教学内容：

一、运输问题提出与建模（§5-1）

运输是社会经济生活中必不可少的一个环节，也是我们身边司空见惯的现象，例如，煤炭、粮食、木材等物资在全国各地的调运；企业生产所需原材料及产成品的运进运出；商业部门对销售网点的货物配送等等。

若用xij表示从产地Ai运往销地Bj的运输量，那么在产销平衡条件下，要求总运费最省的运输方案可表示为：

mnijMinZ???ci?1j?1?xij

n满足条件： ?xij?ai （i=1，…,m）

j?1m?xi?1ij?bj （j=1，…,n）

xij?0

解运输问题通常采用表上作业法，这一过程通常分为三个阶段： （1） 给出初始可行方案； （2） 判断是否最优方案； （3） 调整方案。

二、基变量与闭回路（§5-2）

讲解求解运输问题模型的理论基础：基本量的个数，构成基变量应该满足的条件等。

二、初始解的确定方法

1 最小元素法：

最小元素法的基本思想就是就近供应。即从单位运价表中最小运价开始确定产销关系，依次类推，一直到给出初始方案为止。 2 伏格尔法（Vogel）

伏格尔法（Vogel）是对最小元素法的改进，但相对要复杂些。（具体略） Vogel法是对最小元素法的改进，由Vogel法得到的初始方案一般更接近于最优方案。需注意的是用Vogel法所求得初始方案的过程中也可能遇到最小元素法所遇到的问题，以可以用同样的方法去解决。

时 间：第七周第一次 授课方式：课堂教学 教学内容：

运输问题的单纯形方法：（§5-3）

一初始方案的给出 1 最小元素法：

最小元素法的基本思想就是就近供应。即从单位运价表中最小运价开始确定产销关系，依次类推，一直到给出初始方案为止。 2伏格尔法（Vogel）

伏格尔法（Vogel）是对最小元素法的改进，但相对要复杂些。（具体略） Vogel法是对最小元素法的改进，由Vogel法得到的初始方案一般更接近于最优方案。需注意的是用Vogel法所求得初始方案的过程中也可能遇到最小元素法所遇到的问题，以可以用同样的方法去解决。

二、运输问题解的最优性判定

1. 闭回路法：在给出的初始方案计算表上，除了m+n-1个有数字格外，还有m×n-（m+n-1）个空格。从每一空格出发，沿水平或垂直方向前进，当遇到有数字格时可以任意转90度继续前进，也可以串过有数字格继续前进，直到回到起始点。这样总可以找到一个且只有一个闭回路。在这个闭回路中，除了起始点为空格外，其余角点都是有数字点。

如果检验数为正，表明沿此闭回路的调整会使总费用增加；如果检验数为负，表明沿此闭回路的调整会使总费用减少。 如果求得所有空格点的检验数都大于等于零，则当前运输方案为最优方案；如果还有空格的检验数小于零，则还要进一步调整当前运输方案。

2. 位势法：用闭回路法求检验数，思路很清晰简单，但当产销点较多时是十分麻烦的，而位势法是比较简单易行的。

（1） 在表5-13的右端增加一列，记为ui, i=1~m。 在下面增加一行，记为vj，j=1~n。使其满足cij=ui+vj。

（2） 求出所有的空格的位势ui+vj，并将其填入表5-15中。（任一格的位势等于其行位

势加列位势） （3） 在表5-13的右端增加一列，记为ui, i=1~m。 在下面增加一行，记为

vj，j=1~n。使其满足cij=ui+vj。

（4） 由单位运价表中的每一数据cij减去位势表中对应格的位势，得到每个变量的检

验数（如本例的表5-16所示）（注：对应基变量的检验数必为0，可以不写）。 （5） 判定：若所有检验数均大于等于零，则当前解为最优解；若有一个或一个以上的格为负数，则当前解为非最优解，还需进一步调整改进。 三、案的调整：无论是用最小元素法还是用Vogel法给出的初始方案，也不论是用闭回路法

还是用位势法进行最优性判定。当解为非最优解时，也就是存在负的检验数时，都要用闭回路法进行调整。

运输问题的变体（§5-4）

前面三节所述运输问题的理论与表上作业法的计算，都是以产销平衡为前提的 。即各产地的总产出等于各销地的总销量。即：

mni?ai?1??bj?1j

但在实际的运输问题中，其产销往往是不平衡的，为了应用上述理论和表上作业法进行计算，就需要一定的技术措施，把产销不平衡的运输问题化为产销平衡的运输问题来处理。

1. 产大于销 2. 销大于产

运输问题的应用§5-5

时 间：第九周第二次

授课方式：课堂教学 教学内容：

目标规划模型（§7-1）

一、目标规划——多目标规划模型及求解

1. 多目标规划的矩阵示： maxZ?CX S.t. AX?b

X?0

?z1???z2其中：Z??? C??cij??????zm??c11?c21??????cm1c12c22cm2??c1n??c2n? 其余同LP ???cmn??m?n?2. 多目标规划求解思想：

（1） 权系数法（或效用系数法）：这类方法是力图在诸目标之间寻找一种统一的度量标准

——权系数（又称效用值），然后将多目标模型转化为单一目标的模型。

（2） 优先等级方法：这类方法也是力图将多目标间转化为单目标模型，但它避免了去找诸

目标的一个很难找到的权系数，而代之以将各个目标按重要程度分成优先等级。这一点对于大多数决策者来说还是容易做到的。然后根据这个优先等级的先后次序来求解。

（3） 有效解法：这类方法与前两类方法有很大的区别，它避免了去寻找多目标间的权系数

或优先等级，而是力图求出所有的有效解。如果能够找到全部的有效解，则把它们提供给决策者，而由他们决定哪一个方案最有吸引力。

二、目标规划模型的建立

将一个多目标线性规划模型转化为目标规划模型的具体方法步骤如下：

1． 设立目标函数的期望值E??e1,e2,??,em?T 2． 引入正、负偏差变量di、di?i?1,2,?,m?

??3． 建立新的目标函数（或称达成函数） 4． 目标的权系数和优先级别

目标规划的图解（§7-2）

时 间：第十周第一次 授课方式：课堂教学 教学内容：

一、目标规划模型的求解（§7-3） 1. 多阶段解法：（简介） 2. 线性规划法：

如果我们把目标优先等级系数Pi(i?1,2,?,k)，理解为一种特殊的正常数，且注意到各等级系数之间有关系P1??P2?????Pk。则可以用线性规划方法求解。在求解中注意到：目标函数系数为Pk的组合，所以在单纯形表中的检验数行是Pk的线性组合，分析当前解是否是最优解要依次看P1，P2，?，PK的系数的正负号。

**二、目标规划解的灵敏度分析（§7-4）（简介，不要求）

目标规划中灵敏度的分析同线性规划中灵敏度分析的区别，表现在其目标函数的变化上。在目标规划的目标函数是由体现各目标优先程度的优先因子组成的，而这些优先因子是相对而言的，所以其变化至少是两个或两个以上优先因子的变化。

同线性规划一样，当这些优先因子调整后，仅仅影响其检验数；同线性规划不同之处，它不能讨论目标系数的变化范围，而是讨论当目标的优先级发生变化后，当前解还是否为满意解，若不是，则进一步求得当前优先级下的满意解。 例7-6：（P107，例5）。

第八章，图与网络分析

图的基本概念§8-1

图的基本概念：包括图、简单图、多重图、连通图、不连通图、子图、基础图等以及次的概念和两个定理

时 间：第十周第二次 授课方式：课堂教学 教学内容：

第八章 图与网络分析

最小树问题§8-2

1. 树的概念和最小部分树：树是一类特殊的图，它在实际生活中有着广泛的应用。

定义：一个无圈的连通图称之为树 2. 最小部分树问题 （1） 赋权图

定义：给图G=（V，E）中的每条边[vi,vj]一个权数wij，则该图G称为赋权图。称wij为边[vi,vj]的权。 （2） 最小树定理

若T是赋权图G的一棵树，则它是最小树时当且仅当对T外的每条边[vi,vj]，有：

wij?max{wii,wii,...,wi112k?1**

j}

i其中， (vi v,vi，… vi12k?1,vj)是树T*中连接点vi和vj的唯一的链。

最小树的求法

算法1：“避圈法”：在连通赋权图G中，每一步从未选的边中，选一条最小权的

边，使其与以选的边不构成圈。 算法2：“破圈法”：任取一圈，从圈中去掉一条最大权的边，在余下的图中，重

复这一步骤，直到无圈时为止，即求得最小树。

二、最短路问题（§8-3）

1. 标号法（Dijkstra算法或T—P标号法）——适用于非负路权的情况

该算法是1959年由Dijkstra首先提出的。 2. 网络漫游法（表格法）（适应于任意路权）

3. 迭代法：迭代法适用于任意路权，即wij可以是负数

时 间：第十一周第一次 授课方式：课堂教学 教学内容：

最大流问题（§8-4）

一、基本概念与基本定理

1. 网络：给定一有向图D=（V，A）在V中指定一点，称为发点（记为vs），另一点称

为收点（记为vt），其余的点叫中间点。对于每一个弧(vi,vj)?A，对应一个c(vi,vj)?0（或简写为cij）称为弧的容量。通常我们把这样的D叫做一个网络，记为D=（V，A，C）。

2. 流：所谓网络上的流，是指定义在弧集合A上的一个函数f={f(vi,vj)}，并称f(vi,vj)

为弧(vi,vj)上的流量。

3. 可行流：在一个网络中满足下述条件的流称为可行流——容量限制条件平衡条件 4. 增广链：设f是一个可行流，u是从vs到vt的一条链，若u满足前向弧非饱和、后向

弧非零流的条件，称之为（关于可行流f的）一条增广链。

5. 定理1：可行流f*是最大流，当且仅当不存在关于f*的增广链。

6. 定理2：最大流量最小截集定理：任一个网络D中，从vs到vt的最大流的流量等于

分离vs和vt的最小截集的容量。

二、用标号法寻找最大流

1. 基本思路：寻求最大流的标号法是从一个可行流出发（若网络中没有给定可行流f，

则可以设f是零流），经过标号过程与调整过程的反复循环，逐渐增大可行流的流量，直到网络不在有增广链为止。

2. 标号过程（目的是寻找增广链）：标号过程开始，首先给vs标上（0,+∞）。这时vs是

标号而未检查的点，其余都是未标号点。一般地，取一个标号而未检查的点vi，对一切未标号点vj：

3. 调整过程：首先按各个标号点的第一个标号从vt开始，“反向追踪”找出增广链?，

以vt的第二个标号值作为这个增广链的调整量θ，即，θ=l(vt)，进行调整。增广链

?上的前向弧加上θ，后向弧减去θ，非增广链?上的弧的流量不变。

时 间：第十一周第二次 授课方式：课堂教学 教学内容：

一、第九章：网络计划技术——PERT网络的建立（§9-1）

1. 概念：

网络分析方法用于编制计划，则称之为网络计划技术，又称为计划评审技术（PERT）

——（Program Evaluation and Review Technology）。用箭头线表示工序，用结点表示事项的网络图，称之为箭线式网络图。 2. 网络图的绘制规则：§9-2

包括：方向、时序与编号；紧前工序与紧后工序；缺口与回路；虚工序；始点和终点

二、网络图中的时间参数（§9-3中的一部分） 1. 路与关键路线

一般而言，从始点到终点各条路的作业时间是不等的。其中，完成各道工序所需时间最长的路，称为关键路线，它是制约整个工程完工时间的路。 2. 时间参数

（1） 工序时间t(i,j)：为完成某工序所需的时间称为工序时间。

工序时间的确定有两种方法：一种是根据工时定额资料或相关的统计资料确定；在不具备以上资料的情况下，可以采用三点时间估计法来确定工序时间。

1） 最乐观时间：完成工序的最短时间，记为a；

2） 最保守时间：完成工序的最长时间，记为b； 3） 最可能时间：记为m；

则平均工序时间为ti?则平均工序时间为ti?a?4m?b6a?4m?b6； 其方差为?i?(； 其方差为?i?(22b?a6b?a6) )

22在一项工程中，工程完工时间等于各道关键工序的平均工序时间之和。若在关键路线上有很多道工序，则工程完工时间就可以认为是一个以TE（工程平均完工时间）为均值，以?为均方差的正态分布，其中

sTE??i?1sai?4mi?bi6?bi?ai???6??2s??ti?1i

??

?i?1

时 间：第十二周第一次 授课方式：课堂教学 教学内容：

一、PERT时间参数计算（§9-3部分）

2．工序最早可能开工时间tES(i,j)等于其紧前工序的最早可能完工时间。 3．工序最早可能完工时间tEF(i,j)?tES(i,j)?t(i,j)

4．工程最早完工时间TE：网络图中的各道关键工序都按最早可能开工时间开工，这时工程的完工时间称为工程的最早完工时间。

5．工序最迟必须开工时间tLS(i,j)：在不影响工程最早完工时间的前提下，工序最迟必须开工的时间。

6．工序最迟必须完工时间tLF(i,j)?tLS(i,j)?t(i,j)。

7．事项最早时间tE(i)：tE(i)是一个事项最早可能开始的时间，它等于从始点起到本事项的最长路线上各道工序的工序时间之和，且tE(1)?0。

8．事项最迟时间tL(j)：一个事项若晚于某一时间，就会推迟工程最早完工时间，这样的时间称为事项最迟时间。

9．工序总时差R(i,j)：在不影响工程最早完工时间的前提下，工序的完工期可以推迟的时间，称之为总时差。

10．工序单时差r(i,j)：在不影响紧后工序的最早可能开工时间的前提下，工序最早可能完工时间可以推迟的时间，称之为工序单时差。 二、随机工序时间§9-4 三、网络图的优化§9-5

网络图的优化就是要制订出最优的计划方案。所谓最优是依据一定的标准而言，这要根据编制计划的要求，综合地考虑进度、费用和资源等目标。它包括： 1． 缩短工程进度 2． 最低成本日程 3． 有限资源的合理安排

时 间：第十二周第二次 授课方式：课堂教学 教学内容：

第十章 动态规划——§10-1 多阶段决策问题

通过两个实例引进多阶段决策问题。

若干个相互联系的阶段，如例10-1的地理上的分段和例10-2中的时间上的分段；其次在每一阶段都需要问现在的条件是什么？现在该怎么办？前者即所谓“状态”，后者就是“决策”；这样就构成了一个状态决策序列（如图10-2所示）。这样一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。

所谓多阶段决策问题是指这样一类活动的过程，由于它的特殊性，可将过程划分为若干相互联系的阶段，在它的每一个阶段都需要作出决策，并且一阶段的决策确定以后，常影响下一阶段的决策，从而影响整个过程的活动路线。动态规划方法就是一种从多种可能的过程活动路线中找出一条最优路线的方法。

动态规划的基本概念§10-2

动态规划的基本概念：

（1） 阶段与阶段变量：把所给问题的过程，恰当地划分为若干个相互联系的阶段，以

便于求解，所给问题的过程不同，阶段数就可能不同，它可以用一个变量来描述。用于描述阶段数的变量称为阶段变量，

（2） 状态与状态变量：状态表示每个阶段的出发位置（即阶段的起始状况），它表示每个阶段开始时所面临的自然状态或客观条件。过程的状态通常可以用一个或一

组变数来描述，用来描述过程状态的变数，称为状态变量。

决策：决策就是某阶段状态给定以后，从该状态演变到下一个阶段某一状态的选择。用来描述决策的变量，称为决策变量。

时 间：第十三周第一次 授课方式：课堂教学 教学内容：

一、动态规划的基本概念（§10-2部分）

4. 策略：由过程的第1阶段开始到其终点为止的过程称为问题的全过程。在此全过程

中由每一阶段的决策ui(xi)（i=1,2,…,n）组成的决策函数序列就称为全过程策略，简称为策略，记为P1,n 。

5. 状态转移方程：给定第k阶段状态变量xk的值后，如果这一阶段的决策变量uk的值

一旦确定，则第k+1阶段的状态变量xk?1也就完全确定，常用xk?1?Tk(xk,uk)表示。这就是从第k阶段到第k+1阶段的状态转移规律，称之为状态转移方程。

6. 指标函数和最优指标函数：在多阶段决策过程最优化问题中，指标函数是用来衡量

所实现过程优劣的一种数量指标，它是定义在全过程和所有后部子过程上的确定数量函数，常用Vk,n表示为：Vk,n?Vk,n(xk,uk,xk?1,uk?1,...,xn?1)

7. 指标函数的最优值，称为相应的最优指标函数，记为fk(xk)。

fk(xk)?optVk,n(xk,uk,?)

uk二、动态规划的最优化原理§10-3

1. 动态规划的最优化原理——贝尔曼（R. Bellman）原理：作为整个过程的最优策略具

有这样的性质：即无论过去的状态和决策如何，对于由前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。换句话说，每个最优的策略只能有最优的子策略所组成。

2. 动态规划的基本思想：多阶段决策过程的最优策略和某一段的最优选择的答案一般

是不同的。所以，在多阶段决策过程中，动态规划方法是既把当前一阶段和未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。 3. 构成动态规划模型的条件：

（1） 正确选择状态变量xk，使它既能描述过程的状态，又要满足无后效性。 （2） 确定决策变量uk及每段的允许决策集合Dk(xk)?{uk} （3） 写出状态转移方程：xk?1?Tk(xk,uk)

（4） 根据题意，列出指标函数Vk,n关系，并要满足递推性。

时 间：第十三周第二次 授课方式：课堂教学 教学内容：

动态规划原理（§10-3部分内容）

动态规划应用§10-4

按动态规划过程的演变特征（状态转移规律），通常将其划分为确定型和离散型两大类，如果在确定的状态和决策的前提下，其状态的转移过程是确定的，则称之为确定型动态规划。 确定离散型动态规划：当动态规划问题中的状态变量和决策变量都是离散情况下，在用动态规划方程解题过程中的每一个阶段，通常作法是：将可列个状态及可列个决策变量的取值列成表格一一枚举出来，针对每一个可能的状态根据指标函数值选取最优的决策，从而得到本阶段各个可能状态下的最优决策，并以此为基础由状态转移方程转入到前一阶段，一直到第一个阶段时，则根据其初始状态（边界条件），就可以反方向推出各个阶段的最优的状态决策序列，从而得到问题的解。

通过例题讲解下述几个方面的问题：

（1） 最短路问题

（2） 生产与存储问题 （3） 资源分配问题 （4） 设备更新问题

时 间：第十四周第一次 授课方式：课堂教学/习题课 教学内容：

系统总结第七章、第八章、第九章和第十章的教学内容，示范求解过程，解答难点和疑点 20分钟课堂答疑

时 间：第十四周第二次至第十六周第一次 授课方式：实验教学 教学内容：

（1） 使学生熟悉Excel的优化功能，并运用此功能求解优化问题。

（2） 用该软件求解线性规划、整数规划、运输问题、指派问题、最短路问题、最大流

问题、目标规划问题等； （3） 让学生了解QSB优化软件；

（4） 让学生了解北京理工大学的运筹学软件；

时 间：第十六周第二次 授课方式：课堂教学/课堂答疑

教学内容：总复习

（1） 对课程的全部内容进行系统总结和归纳，并提炼出各章的核心知识点； （2） 进行课堂答疑。

本文来源：https://www.bwwdw.com/article/b1va.html