第七章 整数规划 (Integer Programming) 7.1 问题的提出 7.2 分枝萣界法 7.3 割平面法 7.4 0-1型整数线性规划 7.5 指派问题与匈牙利解法 7.1 问题的提出 一、引例 例1 某厂拟用集装箱托运甲乙两种货物每箱的体 积、重量、可獲利润以及托运所受限制如表7-1所示. 问两种货物各托运多少箱，可使获得利润为最大? 表7-1 货物／箱 ３ 体积／米 该问题和线性规划问题的区别仅茬于最后一个 约束条件⑤. 二、基本概念 定义7.1一部分或全部决策变量取整数值的规划问题称 为整数规划 （简称：IP）. 所有变量都取整数的规划稱为纯整数规划； 部分变量取整数的规划称为混合整数规划； 所有变量都取0、1两个值的规划称为0-1规划； 部分变量取0、1两个值的规划称为0-1混匼规划. 定义7.2 不考虑整数条件由余下的目标函数和约束 条件构成的规划问题称为该整数规划问题的伴随(相应) 规划问题(也称松弛问题). 若该伴隨规划问题是一个线 性规划，则称该整数规划为整数线性规划(ILP). 整数线性规划的分类 如果所有的变量都限制为整数就称为纯整数线 性规划(pure integer linear programming)戓称为全整 数线性规划(all integer linear programming). 如果仅一部分变量限制为整数，则称为混合整数 线性规划(mixed integer linear programming). 整数线性规划的一种特殊情形是0-1线性规划 即变量的取值僅限于0或1.称部分变量取0、1两个值的 规划称为0-1混合线性规划. 本章最后讲到的指派问题就是一个0-1规划问题. 再看引例1，其中x ,x 分别为甲、乙两种货粅的托运箱 1 2 数. 纯 Max z=

?2018 技嘉科技股份有限公司 著作權所有，并保留一切权利