整数线性规划.ppt

本章重点了解整数线性规划模型及其特点；掌握Gomory割平面法和分枝界定法的基本思想和算法步骤；能够利用上述两种方法解决一般的整数线性规划问题。**第四章整数线性规划1、整数线性规划模型简称：ILP问题（integerlinearprogramming）具体的问题背景，请阅读教材P77-78。退出前一页后一页1、整数线性规划模型简介；2、Gomory割平面法；3、分枝界定法；本课解决如下问题：退出前一页后一页整数线性规划模型分类：?若I={0,1},J={1,…,n}，即全部的决策变量仅取0或1，称之为0-1规划；?若J是{1,2…n}的非空真子集，即仅有部分决策变量要求取整数，称为混合整数线性规划；?若J={1,2,…n}，即全部的决策变量都取整数，称为纯整数线性规划；退出前一页后一页解整数线性规划问题的困难性：去掉最后一个约束，即为标准线性规划问题：退出前一页后一页思路1：可否解决相应的线性规划问题，最后舍入到最近的整数解？?如图，舍入后可能根本不可行；?某些整数约束本质上是描述的非线性性质，比如：限制xi取0或者1，其实就是等式：（1-xi）xi=0退出前一页后一页思路2：由于纯整数线性规划的可行集合就是一些离散的格点，可否用穷举的方法寻找最优解？?当格点个数较少时，这种方法可以；?对一般的ILP问题，穷举方法无能为力。退出前一页后一页2、Gomory割平面法考虑纯整数线性规划问题：（P）（p0）问题（P）的松弛问题退出前一页后一页问题P和P0的关系：?P的可行区域是P0的可行区域的子集；?如果P0无可行解，则P无可行解；?P0的最优值是P的最优值的一个下界；?若P0的最优解为整数向量，则它也是P的最优解；（P）（p0）退出前一页后一页割平面法的基本思想：?如果松弛问题(P0)无解，则(P)无解；?如果(P0)的最优解为整数向量，则也是(P)的最优解；?如果(P0)的解含有非整数分量，则对(P0)增加割平面条件：即对(P0)增加一个线性约束，将(P0)的可行区域割掉一块，使得非整数解恰好在割掉的一块中，但又没有割掉原问题(P)的可行解，得到问题(P1)，重复上述的过程。退出前一页后一页割平面法的算法流程：解P0无可行解问题无界P无解解x0为整数向量x0为P的解x0有非整分量对P0增加线性约束将P0的可行区域割掉一块,使得x0在割掉的区域中,而原问题P的任意可行解都没有割去,得到P1退出前一页后一页例：解：利用图解法可以看出，最优解为（1，1）.Gomory割平面法的算法过程如下：0x1x223z11退出前一页后一页1、去掉整数约束，得到松弛问题，增加松弛变量，得到松弛问题的第一张表格：603210-320100100退出前一页后一页2、单纯形方法解决这个问题，得到最优单纯形表格：13/2101/6-1/6011/41/4-3/200-1/4-1/4最优解（1，3/2）不是整数向量，需要引入割平面以得到改进的松弛问题。因为最后一列有两个非整数，这时有两种方法生成割平面：?利用第2行；?利用第0行；两种方法相互等价。退出前一页后一页生成方法：将全部的非基变量系数和右端常数取分数部分，分别得到1/4，1/4，1/2，于是割平面条件为:13/2101/6-1/6011/41/4-3/200-1/4-1/43、生成割平面条件(利用第2行)：退出前一页后一页并将此方程加入到松弛问题的最优单纯形表格中13/2-1/2101/6-1/60011/4