整数规划及分支定界法全版.ppt

整数规划及分支定界法全版.ppt第三章整数规划;.;13-1整数规划问题整数规划是一类要求变量取整数值的数学规划,可分成线性和非线性两类。根据变量的取值性质,又可以分为全整数规划,混合整数规划,0-1整数规划等。;.;整数规划是数学规划中一个较弱的分支,目前只能解中等规模的线性整数规划问题,而非线性整数规划问题,还没有好的办法。;.;例3-1:一登山队员做登山准备,他需要携带的物品有:食品,氧气,冰镐,绳索,帐篷,照相机和通讯设备,每种物品的重要性系数和重量如下:假定登山队员可携带最大重量为25公斤。;.;;.;解:如果令xi=1表示登山队员携带物品i,xi=0表示登山队员不携带物品i,则问题表示成0-1规划:MaxZ=20x1+15x2+18x3+14x4+8x5+4x6++5x2+2x3+6x4+12x5+2x6+4x725xi=1或xi=0i=1,2,….7;.;例3-2背包问题(KnapsackProblem)一个旅行者,为了准备旅行的必须用品,要在背包内装一些最有用的东西,但有个数限制,最多只能装b公斤的物品,而每件物品只能整个携带,这样旅行者给每件物品规定了一个“价值”以表示其有用的程度,如果共有n件物品,第j件物品aj公斤,:在携带的物品总重量不超过b公斤条件下,携带哪些物品,可使总价值最大?;.;解:如果令xj=1表示携带物品j,xj=0表示不携带物品j,则问题表示成0-1规划:MaxZ=bxj=0或1;.;数学模型整数规划(IP)的一般数学模型:Max(min)Z=bi(i=1,2,…m)xj0且部分或全部是整数;.;解法概述当人们开始接触整数规划问题时,常会有如下两种初始想法:因为可行方案数目有限,因此经过一一比较后,总能求出最好方案,例如,背包问题充其量有2n-1种方式;连线问题充其量有n!种方式;实际上这种方法是不可行。;.;