3-1整数线性规划问题.ppt

文档介绍：第一节整数线性规划问题
§ 整数线性规划问题举例
§ 解整数线性规划问题的困难性
精品课程《运筹学》
§ 整数线性规划问题举例
整数线性规划(Integer Linear Programming,ILP)
0-1规划问题
混合整数线性规划问题
纯整数线性规划问题
精品课程《运筹学》
例
投资决策问题
精品课程《运筹学》
解
投资决策变量
精品课程《运筹学》
设获得的总利润为z,则上述问题的数学模型为
变量限制为整数本质上是一个非线性约束,它不可能用线性约束来代替它.
精品课程《运筹学》

精品课程《运筹学》
解
这是一个纯整数线性规划问题.
精品课程《运筹学》
例
旅行售货员问题(货郎担问题)(TSP问题)
精品课程《运筹学》
解
首先,每个城市恰好进入一次,即
其次,每个城市恰好离开一次,即
精品课程《运筹学》
第三,不能出现多于一个互不连通的旅行路线圈,且不排除任何可能的旅行路线
如:六个城市的货郎担问题
令
可归结为ILP的问题
精品课程《运筹学》