《整数规划》课件.ppt

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