整数规划的含义(ppt 58页)

整数规划的含义目录：
一、理解整数规划的含义
二、掌握分枝定界法的思想和方法
三、掌握0-1变量的含义和用法
四、掌握指派问题的算法
五、微机求解

 

 

整数规划的含义内容提要：
    决策问题中经常有整数要求，如人数、件数、机器台数、货物箱数……如何解决？四舍五入不行，枚举法太慢
   问题分类：纯整数规划、混合整数规划、0-1整数规划
   专门方法：分枝定界法、割平面法、隐枚举法、匈牙利法
   分枝定界法的解题步骤
1、不考虑整数约束，解相应LP问题
2、检查是否符合整数要求，是，则得最优解，完毕。否则，转下步
3、任取一个非整数变量xi=bi，构造两个新的约束条件：xi ≤[bi]   ,xi ≥ [bi]+1,分别加入到上一个LP问题，形成两个新的分枝问题。
4、不考虑整数要求，解分枝问题。若整数解的Z值>所有分枝末梢的Z值，则得最优解。否则， 取Z值最大的非整数解，继续分解，Go to 3      

..............................