山大《运筹学》课件03整数线性规划

1、第一节 整数线性规划问题整数线性规划问题举例解整数线性规划问题的困难性整数线性规划问题整数线性规划（ILP）具有下述形式0-1整数线性规划模型混合整数线性规划1. 整数线性规划问题举例例 3.1.1例3.1.1 投资决策问题分析变量每个项目是否投资约束总金额不超过限制目标总收益最大例3.1.1 投资决策问题数学模型旅行售货员问题此外，运筹学还有一个著名的问题：旅行售货员问题（TSP）显示问题2. 解整数线性规划问题的困难性整数规划可行解是松弛问题的可行解最优值大于等于松弛问题的最优值松弛的线性规划问题与线性规划的关系：2. 解整数线性规划问题的困难性LP的可行集合费用下降方向LP问题的最优解I

2、LP问题的最优解2. 解整数线性规划问题的困难性续最优解不一定在顶点上达到最优解不一定是松弛问题最优解的邻近整数解整数可行解远多于松弛问题的顶点，枚举法不可取解ILP问题要远难于解松弛的LP问题如果松弛的LP问题无解，显然原ILP问题无解。反之，不一定成立。如果松弛的LP问题无界呢？可以证明原ILP问题也无界第二节 Gomory割平面法Gomory 割平面法基本思想Gomory 割平面法计算步骤1. Gomory 割平面法基本思想整数规划松弛的线性规划问题( )( 两个问题具有如下明显关系：(1) ( )的可行域 ( )的可行域;(2) 若( )无可行解，则( )无可行解；(3) ( )的最优

3、值是( )的最优值的一个下界；(4) 若( )的最优解是整数向量，则它也是( )的最优解.)Gomory 割平面法基本思想续一由松弛问题的可行域向整数规划的可行域逼近方法利用超平面切除要求 整数解保留 松弛问题最优值增加割平面法生成方法割平面生成方法条件-保留整数解删除非整数的最优解!下面是求c松弛问题的最后一张单纯形表：割平面法生成方法续整数可行解加入松弛变量s 割平面Gomory 割平面法基本思想续二Gomory 割平面法基本思想续三Gomory 割平面法基本思想续四Gomory 割平面法基本思想续五 Gomory 割平面法基本思想续六Gomory 割平面法基本思想续七2. Gomory

4、割平面法计算步骤求松弛问题的最优基可行解判断是否为整数解是得到最优解否在单纯性表中加入一列利用对偶单纯形算法求最优解2. Gomory 割平面法计算步骤-例题例3.2.1求解ILP问题(1,1.5)第三节 分枝定界法分枝定界法基本思想分枝定界法计算步骤1. 分枝定界法基本思想最优值比界坏 最优解为整数最优值比界好 最优解为非整数最优值比界好分 枝边 界分 枝舍 弃1. 分枝定界法基本思想续条件-保留整数解删除最优解!下面是求松弛问题的最后一张单纯形表：1. 分支定界法基本思想续分枝的方法1. 分枝定界法基本思想续分枝方法示意图1. 分枝定界法基本思想续定界1. 当前得到的最好整数解的目标函数值2. 分枝后计算松弛的线性规划的最优解整数解且目标值小于原有最好解的值则替代原有最好解整数解且目标值大于原有最好解的值则 删除该分支其中无最优解非整数解且目标值小于原有最好解的值则继