第6章整数规划 第1整数线性规划间题的提出 第2节分支定界解法 第3节割平面解法 第4节使用 MATLAB求解整数规划问题 第5节0-1型整数线性规划 第6节指派问题 清华大学出版社
清华大学出版社 2 第6章 整数规划 ◼第1节 整数线性规划问题的提出 ◼第2节 分支定界解法 ◼第3节 割平面解法 ◼第4节 使用MATLAB求解整数规划问题 ◼第5节 0-1型整数线性规划 ◼第6节 指派问题
第1节整数线性规划问题的提出 令在前面讨论的线性规划问题中,有些最优解可能是分 数或小数,但对于某些问题,常要求解必须是整数(称 为整数解)。例如,所求解是机器的台数、完成工作的 人数或装货的车数等。 令为满足整数解的要求,初看起来,似乎只要把已得到 的带有分数或小数的解经过“舍入化整”就可以了。 但这常常是不行的,因为化整后不见得是可行解;或 虽是可行解,但不一定是最优解。 令因此,对求最优整数解的问题,有必要另行研究。我 们称这样的问题为整数线性规划( integer linear programmIng),简称‖LP。 清华大学出版社
清华大学出版社 3 第1节 整数线性规划问题的提出 ❖ 在前面讨论的线性规划问题中，有些最优解可能是分 数或小数，但对于某些问题，常要求解必须是整数(称 为整数解)。例如，所求解是机器的台数、完成工作的 人数或装货的车数等。 ❖ 为满足整数解的要求，初看起来，似乎只要把已得到 的带有分数或小数的解经过“舍入化整”就可以了。 但这常常是不行的，因为化整后不见得是可行解；或 虽是可行解，但不一定是最优解。 ❖ 因此，对求最优整数解的问题，有必要另行研究。我 们称这样的问题为整数线性规划(integer linear programming)，简称ILP
第1节整数线性规划问题的提出 整数线性规划的分类 如果所有的变量都限制为(非负)整数,就称为纯整数线性规 划( pure integer linear programming)或称为全整数线性规划 (all integer linear programming o如果仅一部分变量限制为整数,则称为混合整数规划(mied integer linear programming 整数线性规划的一种特殊情形是0-1规划,即变量的取值仅 限于0或1。本章最后讲到的指派问题就是一个0-1规划问题。 清华大学出版社
清华大学出版社 4 第1节 整数线性规划问题的提出 ❖ 整数线性规划的分类 如果所有的变量都限制为(非负)整数，就称为纯整数线性规 划(pure integer linear programming)或称为全整数线性规划 (all integer linear programming) 如果仅一部分变量限制为整数，则称为混合整数规划(mixed integer linear programming)。 整数线性规划的一种特殊情形是0-1规划，即变量的取值仅 限于0或1。本章最后讲到的指派问题就是一个0-1规划问题
第1节整数线性规划问题的提出 令现举例说明用单纯形法求得的解不能保证是整数最优 解 令例1某厂拟用集装箱托运甲乙两种货物,每箱的体积、 重量、可获利润以及托运所受限制如表5-1所示。问 两种货物各托运多少箱,可使获得利润为最大? 表5-1 货物体积(m/箱)重量(00g箱)利润(10元/箱) 甲 5 2 20 4 10 托运限制「24m 1300kg 清华大学出版社
清华大学出版社 5 第1节 整数线性规划问题的提出 ❖ 现举例说明用单纯形法求得的解不能保证是整数最优 解。 ❖ 例1 某厂拟用集装箱托运甲乙两种货物，每箱的体积、 重量、可获利润以及托运所受限制如表5-1所示。问 两种货物各托运多少箱，可使获得利润为最大? 货物 体积(m3 /箱) 重量(100kg/箱) 利润(100 元/箱) 甲 乙 5 4 2 5 20 10 托运限制 24m3 1300kg 表5-1
第1节整数线性规划问题的提出 解:设x,x2分别为甲、乙两种货物的托运箱数(当然 都是非负整数),这就是一个(纯)整数线性规划问题, 用数学模型可表示为: maxz=20x1+10x2① 5X1+4x2<24 2x1+5X2<13 ②③④⑤ (5.1) X1,X2≥0 x1,x,整数 该问题和线性规划问题的区别仅在于最后一个约束条件⑤ 现在我们暂不考虑这一条件,即解由①~④构成的线性规划问题 (以后我们称这样的问题为与原问题相应的线性规划问题) 清华大学出版社
清华大学出版社 6 第1节 整数线性规划问题的提出 ❖ 解：设x1，x2分别为甲、乙两种货物的托运箱数(当然 都是非负整数)，这就是一个(纯)整数线性规划问题， 用数学模型可表示为： max z =20x1+10x2 ① 5x1+4x2 ≤24 ② 2x1+5x2 ≤13 ③ (5.1) x1，x2 ≥0 ④ x1，x2整数 ⑤ 该问题和线性规划问题的区别仅在于最后一个约束条件⑤。 现在我们暂不考虑这一条件，即解由①～④构成的线性规划问题 (以后我们称这样的问题为与原问题相应的线性规划问题)