时 间：第七周第二次 授课方式：课堂教学 教学内容：
一、整数规划的模型与特点（§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． 就这两章中学生提出的典型问题进行课堂答疑。