资源描述：
《运筹学第五章整数规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、整数规划整数规划整数规划的数学模型及解的特点解纯整数规划的割平面法*分支定界法0-1型整数规划*指派问题例1某厂拟用集装箱托运甲乙两种货物,每箱的体积、重量、可获利润以及托运所受限制见下表.问每集装箱中两种货物各装多少箱,可使所获利润最大?§1整数规划的数学模型一、问题的提出货物/箱体积/米3重量/百斤利润/百元甲5220乙4510托运限制/集装箱2413表3.1货物/箱体积/米3重量/百斤利润/百元甲5220乙4510托运限制/集装箱2413解设分别为甲、乙两种货物的托运箱数.则这是一个纯整数规划问题.其数学模型为:在许多线性规划问题中,要求最优解必须取整数.例如所求的解是机器的台数、人数
2、车辆船只数等.如果所得的解中决策变量为分数或小数则不符合实际问题的要求.二、整数规划问题的数学模型对于一个规划问题,如果要求全部决策变量都取整数,称为纯(或全)整数规划;如果仅要求部分决策变量取整数,称为混合整数规划问题.有的问题要求决策变量仅取0或l两个值,称为0-l规划问题.整数规划简称为IP问题.这里主要讨论的是整数线性规划问题,简称为ILP问题.(pureintegerlinearprogramming)(mixedintegerlinearprogramming)(zero-oneintegerlinearprogramming)若不考虑整数条件，由余下的目标函数和约束条件构成的规
3、划问题称为该整数规划问题的松弛问题（slackproblem）整数线性规划数学模型的一般形式该整数规划问题的松弛问题三、整数规划问题解的特点对于整数线性规划问题,为了得到整数解,初看起来,似乎只要先不管整数要求,而求线性规划的解,然后将求得的非整数最优解“舍零取整”就可以了.但实际上,这个想法却常常行不通,有时“舍零取整”后的整数解根本就不是可行解,有的虽然为可行解,却不是最优解.例1某厂拟用集装箱托运甲乙两种货物,每箱的体积、重量、可获利润以及托运所受限制见下表.问每集装箱中两种货物各装多少箱,可使所获利润最大?货物/箱体积/米3重量/百斤利润/百元甲5220乙4510托运限制/集装箱24
4、13解设分别为甲、乙两种货物的托运箱数.则这是一个纯整数规划问题.其数学模型为:（1）若暂且不考虑取整数这一条件.则(1)就变为下列线性规划:（2）我们将式(2)称为(1)的松弛问题.解(2)得到最优解:（3）但它不满足(1)的整数要求.因此它不是(1)的最优解,若把解(3)“舍零取整”,如取X1=(5,0)T,但它不是式(1)的可行解.因为它不满足(1)中的约束条件。若取X2=(4,0)T，X2是(1)的可行解,但它却不是(1)的最优解,因为当X2=(4,0)T时,Z2=80,但当X3=(4,1)T时,Z3=90>Z2。即伴随规划的最优解通过“舍零取整”得到的X1,X2都不是(1)的最优解
5、.因此通过松弛问题最优解的“舍零取整”的办法,一般得不到原整数规划问题的最优解.对上面的问题，我们从几何的角度来观察：若松弛问题(2)的可行域K是有界的,则原整数规划(1)的可行域K0应是K中有限个格点(整数点）的集合.见图1,图中“*"为整数点(格点).图1中四边形OABC是松弛问题(2)的可行域.它的最优解为C点(4.8,0)。而(1)的可行域为k0={(0,0),(0,1),(0,2),(1,0),(1,l),(1,2),(2,0),(2,1),(3,0),(3,1),(4,0),(4,l)}.将C点“舍零取整”后得到的X1=(5.0,0)T不在K0中,而X2=(4,0)T在K0中,但
6、不是(1)的最优解,最优解在B点左侧（4，1）。当然,我们也会想到能否用“穷举法”来求解整数规划.如(1)问题,将K0中所有整数点的目标函数值都计算出来,然后逐一比较找出最优解.这种方法对变量所能取的整数值个数较少时,勉强可以应用.如本例可取0,1,2,3,4共5个数值。而只能取0,1,2共三个数值,因此其组合最多为15个(其中有不可行的点).但对大型问题,这种组合数的个数可能大得惊人!如在指派问题中,有n项任务指派n个人去完成,不同的指派方案共有n!种.当n=20时,这个数超过2×1018.如果用穷举法每一个方案都计算一遍,就是用每秒百万次的计算机,也要几万年.显然“穷举法”并不是一种普遍
7、有效的方法因此研究求解整数规划的一般方法是有实际意义的.××整数规划解的特点整数线性规划及其松弛问题，从解的特点上来说，二者之间既有密切的联系，又有本质的区别。松弛问题作为一个线性规划问题，其可行解的集合是一个凸集，任意两个可行解的凸组合仍为可行解。整数规划问题的可行解集合是它的松弛问题可行解集合的一个子集，任意两个可行解凸组合不一定满足整数约束条件，因而不一定仍为可行解。由于整数规划问题的可行解是其松弛问题
