整数线性规划.ppt

整数规划(Integer Programming) 分枝定界法的理论基础： 对于求最大的整数规划，上界是通过松弛方法得到，作用是判断最优，下界找可行解得到，作用是剪枝。上界定不好难以得到最优解，下界定不好难以剪枝，仅仅是多计算几步。 对于不满足整数约束的变量就行分枝； 如何分枝和定界 上下界的作用 1、概述 匈牙利法是用来解决人员分配问题的一个解法。1955年，库恩（W.W.Kuhn)利用匈牙利数学家康尼格（D.Kǒnig)的一个定理构造了这个解法，故称为匈牙利法。 人员分配问题：设某单位现有n个人员A1,A2…An来完成n项工作B1,B2,……Bn。按工作要求，每个人员需干一项工作，每项工作也需一人去完成。已知人员Ai做工作Bj的效率是cij。问应如何分配，才使总效率最好。 四、指派问题及匈牙利法 令xij表示对人员Ai完成工作Bj的决策变量 表示分配Ai干工作Bj 表示不分配Ai干工作Bj 按问题要求，建立该问题的数学模型为： 这就是一般分配问题的数学模型. 此模型也可以看成一个特殊的运输问题，如果用表上作业法得出的一个最优解又满足“xij =0,1”的条件，这个解也是分配问题的最优解。用表上作业法求解的过程往往出现退化情况。 注：人员分配问题有各种提法。 如果完成任务的效率表现为资源的消耗，则所谓的效率最好是指消耗的资源最少，分配问题就是一个最小化问题； 如果完成任务的效率表现为生产效率的高底，则分配问题就是一个最大化问题。 所有分配问题可以建立相同的数学模型. 2、相关概念 * * 王广民 中国地质大学 经济管理学院 wgm97@163.com 1、概述 整数规划（Integer Programming，简记IP)主要是指整数线性规划,是近二、三十年来发展起来的数学规划当中的一个重要分支，讨论整数规划对研究管理问题有重要意义， 比如项目投资问题、人员分配问题等都可以化为一个整数规划问题（因为如人员分配等的一些问题显然不可能出现小数或者分数的情况）,可分为： 纯整数规划（所有变量都限制为整数） 混合整数规划（一部分变量限制为整数） 0-1规划（所有变量的取值都限制为0或1） 一、整数规划问题及其数学模型 所谓整数规划是指具有下列模型的线性规划问题 其中A矩阵、b、c向量中所有的元素数都是整数或有理数. (1)、模型阐述 2、整数规划问题的模型 其实，如果不考虑（IP）问题中“X是整数”的条件，则整数规划问题仍可看成一个一般的线性规划（LP）问题： 称为该整数规划问题的松弛问题(slack Problem). (2)、整数规划的例子 例 投资问题 设某公司在m个时段里有n项投资计划，由于资金限制不能全部进行。已知 1、第 i 个时段里该公司可动用的资金是bi， 2、第 j 项投资计划所需要的资金是aij ,能够得到的利润是cij。 问该公司如何选择投资计划，使m个时段内的总利润最大. 解：设xij表示在第i个时段内对第j个投资计划的决策变量 即当xij =1时，表示第i 个时段内选中并执行第j个投资计划，当xij =0时，表示第i 时段内未选中第j个投资计划.因此,可以建立该投资问题的数学模型为： 例 工作分配问题 设某单位现有n个人员A1,A2……An来完成n项工作B1, B2, …Bn。按工作要求，每个人员需干一项工作，每项工作也需一人去完成。已知人员Ai做工作Bj的效率是cij。问应如何分配，才使总效率最好. 解：令xij表示对人员Ai完成工作Bj的决策变量 即xij =1表示分配Ai干工作Bj， xij= 0表示不分配Ai干工作Bj。按问题要求，建立该问题的数学模型为： 线性规划（LP）的任一整数可行解都是整数规划（IP）的一个可行解，显然（IP）的所有解（包括可行解）对应于（LP）的整数可行解。 当（LP）的最优解不是一个整数解时，一般情况下不可以通过对非整数解进行“四舍五入”、 “凑整法”得出（IP）问题的最优解。 整数线性规划及其松弛问题，从解的特点上来说，二者之间既有密切的联系，又有本质的区别. 进一步地，如果（LP）的最优解是一个整数解，那么，这个解也一定是（IP）问题的最优解。 一般情况下，（LP）的最优解不会恰好是一个整数解，自然就不是（IP）的最优解， （ IP）的最优值不会优于（LP）的最优值. 3、关于整数规划的解 例如 ：求下列整数规划的最优解 解：在先不考虑“x1,x2是整数”的条件下，对相应的线性规划问题易由图解法得出最优解是： X=（3.25,2.5） 通过凑整法，可以得出4种组合(4,3),(4,2),(3,3),(3,2)。 (4,3),(4,2),(3,3)都不是可行解，(3,2)虽是可行解，但不是最优解 满足问题的整数最优解是(4,1) ，最优值是14。而最优解(4,