文档介绍：整数规划(Integer Programming) 王广民中国地质大学经济管理学院 wgm97@ 1、概述整数规划( Integer Programming ,简记 IP) 主要是指整数线性规划,是近二、三十年来发展起来的数学规划当中的一个重要分支,讨论整数规划对研究管理问题有重要意义, 比如项目投资问题、人员分配问题等都可以化为一个整数规划问题(因为如人员分配等的一些问题显然不可能出现小数或者分数的情况) ,可分为: ?纯整数规划(所有变量都限制为整数) ?混合整数规划(一部分变量限制为整数) ? 0-1 规划(所有变量的取值都限制为 0或1) 一、整数规划问题及其数学模型所谓整数规划是指具有下列模型的线性规划问题????????是整数 X X b AX ts CX z IP0.. max )(其中 A矩阵、 b、c向量中所有的元素数都是整数或有理数. (1) 、模型阐述 2、整数规划问题的模型其实,如果不考虑( IP)问题中“X是整数”的条件,则整数规划问题仍可看成一个一般的线性规划( LP )问题: ??????0 max X b AX CX z称为该整数规划问题的松弛问题( slack Problem ). (2) 、整数规划的例子例投资问题设某公司在 m个时段里有 n项投资计划,由于资金限制不能全部进行。已知 1、第 i 个时段里该公司可动用的资金是 b i, 2、第 j 项投资计划所需要的资金是 a ij,能够得到的利润是 c ij。问该公司如何选择投资计划,使 m个时段内的总利润最大. 解:设 x ij表示在第 i个时段内对第 j个投资计划的决策变量 1 execute 0 not execute ijx ????即当 x ij =1 时,表示第 i 个时段内选中并执行第 j个投资计划,当 x ij =0 时,表示第 i 时段内未选中第 ,可以建立该投资问题的数学模型为: 1 1 max 1, 2, , . . 0,1 m n ij ij i j n ij ij i j i ij z c x a x b i m s tx ? ????? ??????????例工作分配问题设某单位现有 n个人员 A 1,A 2…… A n来完成 n项工作 B 1, B 2, …B n。按工作要求,每个人员需干一项工作,每项工作也需一人去完成。已知人员 A i做工作 B j的效率是 c ij。问应如何分配,才使总效率最好. 解:令 x ij表示对人员 A i完成工作 B j的决策变量即x ij =1 表示分配 A i干工作 B j,x ij = 0 表示不分配 A i干工作 B j。按问题要求,建立该问题的数学模型为: 10 ijx ???? 1 1 max m n ij ij i j z c x ? ???? 1111 0,1 n ijjm iji ij xxx ??????????????????线性规划( LP )的任一整数可行解都是整数规划( IP )的一个可行解,显然( IP )的所有解(包括可行解)对应于( LP )的整数可行解。当( LP )的最优解不是一个整数解时,一般情况下不可以通过对非整数解进行“四舍五入”、“凑整法”得出( IP)问题的最优解。整数线性规划及其松弛问题,从解的特点上来说, 二者之间既有密切的联系,又有本质的区别. 进一步地,如果( LP )的最优解是一个整数解, 那么,这个解也一定是( IP )问题的最优解。一般情况下,( LP )的最优解不会恰好是一个整数解,自然就不是( IP )的最优解, ( IP )的最优值不会优于( LP )的最优值. 3、关于整数规划的解例如:求下列整数规划的最优解??????????????是整数 21 21 21 21 21, 0, 14 32 23x maxz xx xx xx xx x