第3单元 整数规划.ppt

文档介绍：第3章整数规划
主要内容
整数规划的基本问题
分支定界法
割平面法
指派问题与匈牙利法
由于整数规划解的离散性,使得各种连续系统优化技术很难直接用于求解整数规划。
本章介绍的各种类型整数规划的特殊解法,都是根据它们的特殊性质设计的。
现实生活中的指派问题是一种特殊的整数规划问题,其基本要求是在满足特定的指派要求的情况下,使指派方案的总体效果最佳,
本章最后对求解指派问题的匈牙利法做了详细介绍。

要求一部分或全部决策变量必须取整数值的规划问题称为整数规划(integer programming,简记IP)。
不考虑整数条件,由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松驰问题(slack problem)。
若松驰问题是一个线性规划,则称该整数规划为整数线性规划(integer linear programming)。
整数线性规划数学模型的一般形式:
整数线性规划问题可以分为下列几种类型:
纯整数线性规划:指全部决策变量都必须取整数值的整数线性规划。
混合整数线性规划:指决策变量中有一部分必须取整数值,另一部分可以不取整数值的整数线性规划。
0-1型整数线性规划:指决策变量只能取值0或1的整数线性规划。
本章讨论整数线性规划。后面提到的整数规划,一般都是指整数线性规划。