整数线规划问题教学.ppt

精品课程运筹学,第一节 整数线性规划问题,1.1 整数线性规划问题举例,1.2 解整数线性规划问题的困难性,精品课程运筹学,1.1 整数线性规划问题举例,整数线性规划(Integer Linear Programming，ILP),01规划问题,混合整数线性规划问题,纯整数线性规划问题,精品课程运筹学,例,投资决策问题,精品课程运筹学,解,投资决策变量,精品课程运筹学,设获得的总利润为z，则上述问题的数学模型为,变量限制为整数本质上是一个非线性约束，它不可能用线性约束来代替它.,精品课程运筹学,例,精品课程运筹学,解,这是一个纯整数线性规划问题.,精品课程运筹学,例,旅行售货员问题（货郎担问题）(TSP问题）,精品课程运筹学,解,首先，每个城市恰好进入一次，即,其次，每个城市恰好离开一次，即,精品课程运筹学,第三，不能出现多于一个互不连通的旅行路线圈，且不排除任何可能的旅行路线,如：六个城市的货郎担问题,令,可归结为ILP的问题,精品课程运筹学,如：六个城市的货郎担问题,令,精品课程运筹学,1.2 解整数线性规划问题的困难性,第一个问题：为什么不解对应的LP，然后将其解舍入到最靠近的整数解呢？,精品课程运筹学,第二个问题是：可否用枚举法来解ILP问题呢？,