运筹学第五章整数规划

1第五章整数规划(IntegerProgramming)1整数规划的模型2分支定界法3割平面法40－1整数规划5指派问题2一、整数规划的一般形式1、实例例1某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表1：货物体积每箱（米3）重量每箱（百斤）利润每箱（百元）甲乙54252010托运限制2413问两种货物各托运多少箱，可使获得的利润为最大？第一节整数规划问题的提出3，且为整数，013522445:102021212121xxxxxxSTxxMaxZ部分或全部为整数iixxbAXSTCXMaxZ,0:2、整数规划一般形式解：设托运甲、乙两种货物x1，x2箱，用数学式可表示为：4从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得倒的解是整数可行解。3、与LP问题的关系（1）求解方法方面5例2设整数规划问题如下且为整数01365191421212121xxxxxxxxZ,max首先不考虑整数约束，得到线性规划问题（一般称为松弛问题,或者B问题，原问题又称为A问题）。01365191421212121xxxxxxxxZ,max6用图解法求出最优解x1＝3/2,x2=10/3且有Z=29/6x1x2⑴⑵33(3/2,10/3)现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3)(2，3)(1，4)(2，4)。显然，它们都不可能是整数规划的最优解。按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。7因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。如上例：其中（2，2）（3，1）点为最大值，Z=4。目前，常用的求解整数规划的方法有：分支定界法和割平面法；对于特别的0－1规划问题采用隐枚举法和匈牙利法。8例3做图分析例1的最优解(直观)IP问题可行域不为凸集（2）理论方面x1x24840Z=961235673125x1+4x2=242x1+5x2=13C(4.8,0)Z=90(最优解)B(4,1)Z=80。，则为若问题，则为若问题由此可见：*B*A*B*AminA;maxAZZZZ94、IP问题的求解思路通过上面的分析，该法不可行。（1）对问题B的最优解“舍入取整”由于IP问题的可行解数量有限，可以全部列出，相应目标函数最优者为最优解。但若决策变量较多时，计算效率低，且容易丢失最优解。（2）枚举法设计某种算法，只检查部分可行解，就可找到最优解，提高计算效率。本章讨论的所有方法都是隐枚举法。（3）隐枚举法10全为整数iijba,二、整数规划的分类1、全整数规划问题全部为整数iixxbAXSTCXMaxZ,0:2、纯整数规划问题在下列IP问题中，在上述IP问题中，为有理数且全为整数iijjbax,,,0113、0-1规划问题在上述IP问题中，10或jx4、混合整数规划问题为整数部分jx在上述IP问题中，12一、分支的几何解释适用范围：全整数规划问题纯整数规划问题0-1规划问题混合整数规划问题例1求解A，且为整数，0702075679:904021212121xxxxxxSTxxMaxZ第二节分支定界法（BranchandBoundMethod）13解：图解法x1x2012345678910123456789x1+7x2=567x1+20x2=70BCx(0)=(4.81,1.82)Z0=356问题B1Z1=349x1=4.00x2=2.10问题B2Z2=341x1=5.00x2=1.57x1=[x(0)]x1=[x(0)]+114，且为整数，0702075679:904021212121xxxxxxSTxxMaxZ已知，求得B问题的最优解x(0)=(4.81,1.82)Z0=356由于不满足整数条件，选择一个决策变量进行分支。选x1。X1=4.81，按进行分支，相当于分别增加了一个约束条件。xr≤和xr≥＋1rbrb问题B1：MaxZ=40X1+90X29X1+7X2≤56①B17X1+20X2≤70②X1≤4X1,X2≥0X1,X2为整数问题B2：MaxZ=40X1+90X29X1+7X2≤56①B27X1+20X2≤70②X1≥5X1,X2≥0X1,X2为整数分支15B01234567X154321X2(4.81,1.82)整数规划问题A：MaxZ=40X1+90X29X1+7X2≤56①B7X1+20X2≤70②AX1,X2≥0X1,X2为整数问题B1：MaxZ=40X1+90X29X1+7X2≤56①B17X1+20X2≤70②X1≤4X1,X2≥0X1,X2为整数问题B2：MaxZ=40X1+90X29X1+7X2≤56①B27X1+20X2≤70②X1≥5X1,X2≥0X1,X2为整数分别解B1,B2得x=(4,2.1)和x=(5,1.57),仍不满足整数条件。先对B1分枝,在B1中分别加入X2≤2形成B3,加入X2≥3形成B4。同理对B2分枝,见下页。X1≤4X1≥5B1B2B3B416B01234567X154321X2(4.81,1.82)问题B3：MaxZ=40X1+90X29X1+7X2≤56①7X1+20X2≤70②X1≤4X2≤2X1,X2≥0X1,X2为整数问题B4：MaxZ=40X1+90X29X1+7X2≤56①7X1+20X2≤70②X1≤4X2≥3X1,X2≥0X1,X2为整数先对B1分枝得B3B4,X1≤4X1≥5B1B2B5问题B5：MaxZ=40X1+90X29X1+7X2≤56①7X1+20X2≤70②X1≥5X2≤1X1,X2≥0X1,X2为整数再对B2分枝,分别添加X2≤1和X2≥2得B5和B6后者无可行解（无可行域）B3B417用单纯形法求IP问题的最优解。二、基本思路分支对问题B增加约束条件，形成多个LP子问题，这一过程并没有使问题A的可行解丢失，但可使问题A的可行解成为LP子问题可行域的顶点。这样用单纯形法求解这些LP子问题所得最优解才可能为整数解。定界通过比较LP子问题的最优目标函数值，确定问题A的最优目标函数取值范围。当某个LP子问题的最优目标函数值不在该范围，表明没有必要再检查该LP子问题中的整数可行解，从而提高计算的效率。18三、定界规则max问题：每一次分支求解后都要定下界，整数分支中目标值最大的一个为新的下界；小于下界的分支要剪支；上界不影响结果，可以不用定上界。（其实就是选择最大的整数分支）min问题：每一次分支求解后都要定上界，整数分支中目标值最小的一个为新的上界；大于上界的分支要剪支；下界不影响结果，可以不用定下界。（其实就是选择最小的整数分支）19问题Bx1=4.81x2=1.82Z0=356问题B1x1=4.00x2=2.10Z1=349问题B2x1=5.00x2=1.57Z2=341问题B3x1=4.00x2=2.00Z3=340问题B4x1=1.42x2=3.00Z4=327问题B5x1=5.44x2=1.00Z5=308问题B6无可行解0ZA*340ZAZA*=340x14x15x22x23x21x22定界与剪支20且全为整数0,4306525min211212121xxxxxxxxxZ例2用分支定界法求解整数规划问题21LP1x1=1,x2=3Z(1)＝－16LPx1=18/11,x2=40/11Z(0)＝－19.8LP2x1=2,x2=10/3Z(2)＝－18.5LP3x1=12/5,x2=3Z(3)＝－17.4LP4无可行解LP5x1=2,x2=3Z(5)＝－17LP6x1=3,x2=5/2Z(6)＝－15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃ZA*-16ZA*-17221、求松弛问题的最优解：先不考虑整数约束，解(IP)的松弛问题(LP)，可能得到以下情况之一：⑴.若(LP)没有可行解，则(IP)也没有可行解，停止计算。⑵.若(LP)有最优解，并符合(IP)的整数条件，则(LP)的最优解即为(IP)的最优解，停止计算。⑶.若(LP)有最优解，但不符合(IP)的整数条件，转入下一步。为讨论方便，设(LP)的最优解为：不全为整数其中目标函数最优值为),,2,1(.Z)0,,0,,,,,,((0)21)0(mibbbbbXiTmr四、分支定界法步骤232、分支：（分支后并求解）在(LP)的最优解X(0)中，任选一个不符合整数条件的变量，例如xr=（不为整数），以表示不超过的最大整数。构造两个约束条件xr≤和xr≥＋1rbrbrbrbrb将这两个约束条件分别加入问题(IP)，形成两个子问题(IP1)和(IP2)，再解这两个问题的松弛问题。(LP1)(LP2)称为新的分支，原问题不再称为分支。24如此反复进行，直到得到Z＝Z*＝为止（或者所有分支都已经分析或剪支），即得最优解X*。3、定界：(1)max问题：从已符合整数条件的分枝中，找出目标函数值最大者作为新的下界。(2)min问题：从已符合整数条件的分枝中，找出目标函数值最小者作为新的上界。4、比较与剪支：各分枝的目标函数值中，若有小于Z者，则剪掉此枝，表明此子问题已经探清，不必再分枝了;否则继续分枝。剪枝不再是分支。无可行解也要剪支。Z25例3求解下列IP问题)(0,721342:4621212121整数xxxxxxSTxxMaxZ21)49,2()(,0,20721342:46*)1(21212121ZXxxxxxxSTxxMaxZ整数22)1,3()(,0,3721342:46*)2(21212121ZXxxxxxxSTxxMaxZ整数松弛问题的最优解为：X*=(5/2,2),Z*=23分枝B1:x12分枝B2:x1326问题I问题IIx123x29/41Z2122问题II的解即问题A的最优解可能存在两个分枝都是非整数解的情况，则需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程当存在很多变量有整数约束时，分枝既广又深，在最坏情况下相当于组合所有可能的整数解一般整数规划问题属于一类未解决的难题，NP-complete，只有少数特殊问题有好的算法，如任务分配问题、匹配问题分枝问题的松弛解27方法1：图解法x1x2012345678910123456782x1+x2=72x1+4x2=13x*=(5/2,2)Z*=23x1*=(2,9/4)Z*=21x2*=(3,1)Z*=2228方法2：单纯型表cj6400CBXBbx1x2x3x44x26x125/2011/3-1/310-1/62/3j-2300-1/3-8/3松弛问题最优单纯形表如下：)(0,721342:4621212121整数xxxxxxSTxxMaxZ29将约束条件直接写入单纯形表：21x251xxCj6400CBxBbx1x2x3x44x26x125/2011/3-1/310-1/62/3j-2300-1/3-8/3Cj64000CBxBbx1x2x3x4x54x26x10x525/2-1/2011/3-1/3010-1/62/30001/6[-2/3]1j-2300-1/3-2/300x5210001x50000[1]30Cj64000CBxBbx1x2x3x4x54x26x10x49/423/4011/40-1/21000100-1/41-3/2j-2100-1/2