运筹学 (第三版) 《运筹学》教材编写组 第5章整数线性规划 第1-4节 清华大学出版社
运筹学 （第三版） 《运筹学》教材编写组 第5章 整数线性规划 第1-4节 清华大学出版社
第5章整数线性规划 第1节整数线性规划问题的提出 第2节分支定界解法 第3节割平面解法 第4节0-1型整数线性规划 第5节指派问题
第5章 整数线性规划 • 第1节 整数线性规划问题的提出 • 第2节 分支定界解法 • 第3节 割平面解法 • 第4节 0-1型整数线性规划 • 第5节 指 派 问 题 •
第1节整数线性规划问题的提出 在前面讨论的线性规划问题中,有些最优解可能是 分数或小数,但对于某些具体问题,常有要求解答 必须是整数的情形(称为整数解)。例如,所求解是机 器的台数、完成工作的人数或装货的车数等,分数 或小数的解答就不合要求。为了满足整数解的要求, 初看起来,似乎只要把已得到的带有分数或小数的 解经过“舍入化整”就可以了。但这常常是不行的 因为化整后不见得是可行解;或虽是可行解,但不 定是最优解。因此,对求最优整数解的问题,有 必要另行研究。我们称这样的问题为整数线性规划 ( integer linear programming),简称IP,整数线性规 划是最近几十年来发展起来的规划论中的一个分支
第1节 整数线性规划问题的提出 • 在前面讨论的线性规划问题中，有些最优解可能是 分数或小数，但对于某些具体问题，常有要求解答 必须是整数的情形(称为整数解)。例如，所求解是机 器的台数、完成工作的人数或装货的车数等，分数 或小数的解答就不合要求。为了满足整数解的要求， 初看起来，似乎只要把已得到的带有分数或小数的 解经过“舍入化整”就可以了。但这常常是不行的， 因为化整后不见得是可行解；或虽是可行解，但不 一定是最优解。因此，对求最优整数解的问题，有 必要另行研究。我们称这样的问题为整数线性规划 (integer linear programming)，简称ILP，整数线性规 划是最近几十年来发展起来的规划论中的一个分支
·整数线性规划中如果所有的变数都限制为(非负) 整数,就称为纯整数线性规划φ pure integer linear programming或称为全整数线性规划(all integer linear programming);如果仅一部分变数 限制为整数,则称为混合整数计划( mixed integer linear programming)。整数线性规划的 种特殊情形是0-1规划,它的变数取值仅限于0 或1。本章最后讲到的指派问题就是一个0-1规 划问题
• 整数线性规划中如果所有的变数都限制为(非负) 整数，就称为纯整数线性规划(pure integer linear programming)或称为全整数线性规划(all integer linear programming)；如果仅一部分变数 限制为整数，则称为混合整数计划(mixed integer linear programming)。整数线性规划的一 种特殊情形是0-1规划，它的变数取值仅限于0 或1。本章最后讲到的指派问题就是一个0-1规 划问题
ρ现举例说明用前述单纯形法求得的解不能保证 是整数最优解。例1某厂拟用集装箱托运甲乙两 种货物,每箱的体积、重量、可获利润以及托 运所受限制如表5-1所示。问两种货物各托运多 箱,可使获得利润为最大?表5-1 货物体积(m/箱)重量(00/0销)利润(100元/箱) 甲 20 10 托运限制 24m3 1300kg
• 现举例说明用前述单纯形法求得的解不能保证 是整数最优解。例1某厂拟用集装箱托运甲乙两 种货物，每箱的体积、重量、可获利润以及托 运所受限制如表5-1所示。问两种货物各托运多 少箱，可使获得利润为最大?表5-1 货物 体积(m3 /箱) 重量(100kg/箱) 利润(100 元/箱) 甲 乙 5 4 2 5 20 10 托运限制 24m3 1300kg