《运筹学Ⅰ》教案

《运筹学Ⅰ》教案

课程名称：运筹学 授课教师：孔造杰 课程学时：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

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

一、整数规划的模型与特点（§6-1）

在前面我们所讨论的线性规划模型中，一般情况下都限定决策变量X≥0。但在实际问题中往往会有其它限制，如决策变量只能取整数，只能取0、1两个值等等。若对原线性规划问题增加这种限制，则称之为整数规划问题。所以整数规划也是一种特殊的线性规划。 整数规划有很现实的实际意义，因为在很多线性规划问题中，决策变量往往代表的是人数、机器台数等等，这时非整数解显然是不合要求的。

整数规划有很现实的实际意义，因为在很多线性规划问题中，决策变量往往代表的是人数、机器台数等等，这时非整数解显然是不合要求的。对于处理这一类要求有整数解的线性规划问题，通常人们首先想到的是先不管整数条件的限制，直接使用单纯形法求解，然后将所得到的非整数解经四舍五入化为整数。但是这种办法往往是行不通的，这是因为由舍入化整所得的整数解不一定是可行解，即便是可行解，也不一定是最优解。

目前，解整数规划问题通常采用的方法是分支定界法和割平面法。

二、分枝定界法（§6-2）

1. 分枝定界法是以求相应的线性规划问题的最优解为出发点的。如果得到的线性规划

问题的最优解不符合整数条件，就将原问题分解成两个或几个子问题，而每一子问题都是在原线性规划问题的基础上增加相应的整数约束条件，从而在其可行域的边界附近除去一部分原来的可行域，但所除去的可行域是不包含有整数解的。这样，可以使靠近可行域边界的整数点逐步地暴露在新可行域的边界上，在分解后的缩小了的可行域内继续求相应的线性规划问题，直到得到所要求的最优整数解。 2. 解体步骤：

1．称原问题（整数规划）为A，称相应的线性规划（即不考虑整数条件）为B，解B。

2． 如果问题B没有可行解，则问题A也没有可行解。

3． 如果已得问题B的最优解，检查它是否合于整数条件。若是，则它就是原问题A

的最优解；若否转入下步。 4． 在问题B的解中，任选一个不符合整数条件的变量xj，如果xj的值是bj，作两个

后继问题，它们是对问题B分别各增加一个约束条件：

a) b)

xj?（小于bj的最大整数） xj?（大于bj的最小整数）

不考虑整数条件，解这两个后继问题。

5． 在现有的、且还没有分解后继问题的各可行解中，选目标函数值为最优的问题，重

新称这个问题为问题B，回到第3步。重复进行，直到得到整数最优解。

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

割平面法（§6-3）

一．解法思想：

首先不考虑整数条件，解线性规划问题，若得整数解即为所求，若有非整数解，则增加线性约束条件（即割平面法），使得由原可行域中切割掉一部分，切掉的这部分只包含非整数解，而没有切割掉任何整数可行解。

二． 利用最终单纯形表求割平面方程的基本步骤：

1. 从最终单纯形表中引出诱导方程。

xi??akikxk?bi ①

xi——基变量之一； xk——所有非基变量；

aik——相对应非基变量在最终表中的系数； bi——最终表中对应于xi的取值，bi非整数。

2. 将aik、bi都分解成整数部分N与非负真分数f之和。

即aik?Nik?fik，其中0?fik?1 bi?Ni?fi，其中0?fi?1

其中N为不超过aik（或bi）的最大整数。 所以上述①式变为：xi??Nkikxk?Ni?fi??kfikxk ②

3. 现在提出整数条件，即xi,xk均为整数。

可见②式左边为整数，因而其右端也就必为整数。 又?0?fi?1 , 0?fik?1

?必有 fi??kfikxik?0 ③

此即所求割平面方程。

4. 给割平面方程③加入非负松弛变量y得到

即fi??fikxik?y?0 ④

k然后以y为基变量把此方程④填入最终计算表继续迭代，重复以上过程，直到得到整数最优解。

0-1整数规划（§6-4）

0-1整数规划的解法：枚举法（穷举法），隐枚举法

1. 枚举法就是对于各种可能情况的组合及结果一一列出。对于有n个变量的0-1规划用

枚举法，需计算2n种组合情况下的目标值，并进行大小比较，选其最大值所对应的方案作为最优解。显然当n较大时，这种方法几乎是不可能的。

2. 隐枚举法：先试探一个解，根据此解，以目标函数方程及其取值作为增加的约束条

件——称之为过滤约束条件。当求解优于当前最优值的时候，则修改这一过滤条件的右端常数项的取值。

注：为方便分析，一般常重新排列决策变量的顺序使目标函数中的各决策变量的系数是递增（不减）的。

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

指派问题（匈牙利法）（§6-5）

解题步骤：

1） 使目标系数矩阵的各行各列出现“0”元素（在系数矩阵位置填写的目标系数

值所构成的矩阵）。具体作法是以系数矩阵的每一行减去该行元素的最小值，然后再将无“0”的列减去该列元素的最小值。

2） 最优解判别：由有“0”元素最少的行开始，圈出一个“0”以◎表示，然后

划去同行同列的其它“0”元素，用φ表示；或者按列检查，以“0”元素最少的列开始，圈出一个“0”记号为◎，划去同行同列的其它“0”，记号为φ。 若能圈出n个不同行不同列的“0”元素◎，即为所求最优解，否则进行下一步。

3） 作能覆盖所有“0”元素的最少数的直线集。

a） 对没有◎的行打√号；

b） 对打√号行上所有有“0”元素的列打√号； c） 再对打√号的列上有◎的行打√；

d） 重复a)、b)、c)直到得不出新的打√号的行列为止；

e） 对没有打√号的行画横线，所有打√号的列画纵线。这就是能覆盖所有

“0”元素的最少数直线集合。 4） 变换矩阵，使“0”元素增加

在没有被直线覆盖的部分中找出最小元素，在没有划线的行中减去这个最小元素，在有画线的列中都加上这个最小元素，然后回到第2）步，重复进行。

IP的计算机解法§6-6 IP的应用及案例§6-7

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

习题课：

1． 对运输问题和整数规划部分总结核心点； 2． 讲授运输问题部分的应用举例（p.92）; 3． 课堂讲解98页习题中的部分难题；

4． 课堂讲解134页整数规划习题中的部分难题； 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

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

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

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

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

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

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

教学内容：总复习

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

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