时 间：第九周第二次
授课方式：课堂教学 教学内容：
目标规划模型（§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