1、整数规划整数规划 n教学内容教学内容：整数规划的模型、分支定界法、切平面法，0-1整数规划，指派问题n教学重点教学重点：分支定界法、切平面法2021/8/171整数规划的数学模型整数规划的数学模型2021/8/172 整数线性规划问题可以分为下列几种类型：n1.纯整数线性规划（pure integer linear programming）：指全部决策变量都必须取整数值的整数线性规划。有时，也称为全整数规划。n2.混合整数线性规划（mixed integer linear programming）：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。n3.01型整数线性规划
2、（zero-one integer linear programming）：指决策变量只能取值0或1的整数线性规划。本章仅讨论整数线性规划。后面提到的整数规划，一般都是指整数线性规划。2021/8/173解的特点n松弛问题作为一个线性规划问题，其可行解的集合是一个凸集，任意两个可行解的凸组合仍为可行解。整数规划问题的可行解集合是它的松弛问题可行解集合的一个子集，任意两个可行解的凸组合不一定满足整数约束条件，因而不一定为可行解。由于整数规划问题的可行解一定也是它的松弛问题的可行解（反之则不一定），所以。前者最优解的目标函数值不会优于后者最优解的目标函数值。n在一般情况下，松弛问题的最优解不会刚好
3、满足变量的整数约束条件，因而不是整数规划的可行解，自然就不是整数规划的最优解。此时，若对松弛问题的这个最优解中不符合整数要求的分量简单地取整，所得到的解不一定是整数规划问题的最优解，甚至也不一定是整数规划问题的可行解。2021/8/1742021/8/1752021/8/176解纯整数规划的割平面法解纯整数规划的割平面法 2021/8/1772021/8/1782021/8/1792021/8/1710分支定界法分支定界法 2021/8/17112021/8/17122021/8/17132021/8/17142021/8/1715 第四节第四节 01型整数规划型整数规划n定义n例7-9，20
4、21/8/1716解法2021/8/17172021/8/17185.指派问题指派问题2021/8/17192021/8/17202021/8/17212021/8/1722匈牙利解法 n从上述数学模型可知，标准的指派问题是一类特殊的整数规划问题，又是特殊的01规划问题和特殊的运输问题，因此，它可以用多种相应的解法来求解。但是，这些解法都没有充分利用指派问题的特殊性质，有效的减少其计算量。1955年，库恩（W.W.Kuhn）利用匈牙利数学家康尼格的关于矩阵中独立零元素的定理，提出了指派问题的一种算法，习惯上称之为匈牙利解法。2021/8/17232021/8/1724n匈牙利解法的一般步骤，见p1432021/8/1725非标准形式的指派问题n最大化指派问题 n人数和事数不等的指派问题n一个人可做几件事的指派问题n某事一定不能由某人做的指派问题2021/8/1726
