第五章 整数规划51 整数规划模型 52 纯整数规划的割平面法54 分支定界法57 最优分配问题本章基本要求v 掌握整数规划的数学模型的建摸技巧；v 掌握 0-1规划模型v 了解割平面公式；v 掌握分支定界法；v 掌握匈牙利法解决最优分配问题。 整数规划v整数规划：决策变量全体或部分约束为整数的数学规划问题 .v整数规划又分线性整数规划和非线性整数规划 .v线性整数规划也叫整数线性规划(ILP),简称整数规划 ,简记 (IP).整数线性规划的分类v纯整数规划 :所有的决策变量均取整数 . 简记（）v混合整数规划 :只有部分决策变量取整数值 . 简记（）v0-1整数规划 :整数变量只能取 0或 1.简记（）问 题1、去掉整数约束的规划问题的最优解与整数规划的最优解有何关系？2、如何建立整数规划模型？如何求解整数规划问题？例 5-1 求解整数规划(1.5, 3.33)最优值是 -4.83v放松整数约束得到的线性规划问题为该整数规划松弛问题v任何一个整数规划都可以看成是一个线性规划松弛问题再加上整数约束构成v整数规划的可行域是线性规划松弛问题可行域的一个子集 .整数规划最优解和线性规划松弛问题最优解的关系v对于最大化问题松弛问题最优解 整数规划最优解v对于最小化问题松弛问题最优解 整数规划最优解
