59运筹学整数规划

第一节问题的提出例子：某厂拟采用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表货物体积每箱（m3）重量每箱（吨）利润每箱（百元）甲424乙513托运限制206问两种货物托运多少箱，可使获得利润为最大？第三章整数规划（IntegerProgramming)分类：1.纯整数线性规划（PureIntegerLinearProgramming）2.混合整数线性规划（MixedIntegerLinearProgramming）3.0-1型整数线性规划（Zero-OneIntegerLinearProgramming）解：设x1，x2分别表示两种货物托运的箱数，那么其线性规划为取整数,0,622054.34max2121212121xxxxxxxxtsxxZ0,622054.34max21212121xxxxxxtsxxZ可得最优解为x*=（5/3，8/3)T。如果选用“向上凑整”的方法可得到x(1)=(2,3)T,则此时已破坏了体积约束,超出可行域的范围;如果“舍去小数”可得x(2)=(1,2)T,则此时虽是可行解,值为10，不是最优解,因为当x*=(2,2)T是,其利润为14.由于托运的箱数不能为分数，故上述规划问题是整数规划问题。若不考虑整数约束，其相应的线性规划问题为：第二节分枝定界法(BranchandBoundmethod)引言：穷举法对小规模的问题可以。大规模问题则不行。一、基本思想和算法依据基本思想是：先求出相应的线性规划最优解，若此解不符合整数条件，那么其目标函数的值就是整数规划问题最优值的上界，而任意满足整数条件的可行解的目标函数值将是其下界（定界），然后将相应的线性规划问题进行分枝，分别求解后续的分枝问题。如果后续分枝问题的最优值小于上述下界,则剪掉此枝;如果后续某一分枝问题的最优解满足整数条件，且其最优值大于上述下界，则用其取代上述下界，继续考虑其它分枝，直到最终求得最优的整数解。算法的依据在于：“整数规划的最优解不会优于相应的线性规划问题的最优解”。具体说就是，对极大化问题，与整数规划问题相应的线性规划问题的目标函数值，是该整数规划问题目标函数的上界；任何满足整数条件的可行解的目标函数值将是其下界。二、具体步骤（以例子说明）取整数,0,702075679.9040max2121212121xxxxxxxxtsxxZ解：第一步：先不考虑整数约束条件，求解相应的线性规划问题，得最优解和最优值如下x1=4.81,x2=1.82,Z=356此解不满足整数解条件。定出整数规划问题目标函数的上下界。上界为Z=356；用观察法可知x1=0，x2=0是可行解，从而其整数规划问题目标函数的下界应为0，即0Z*3569x1+7x2=567x1+20x2=70Z=40x1+90x2LP-1LP-2第二步：分枝与定界过程。•将其中一个非整数变量的解，比如x1,进行分枝，即x14.81=4,x14.81=5并分别加入LP问题的约束条件中,得两个子LP规划问题LP-1,LP-2,分别求解此两个子线性规划问题,其最优解分别是LP-1:x1=4,x2=2.1,Z1=349LP-2:x1=5,x2=1.57,Z2=341没有得到全部决策变量均是整数的解。再次定出上下界0Z*349•继续对问题LP-1，LP-2进行分枝。先对目标函数值大的子问题进行分枝，即分别将x22.1=2,x22.1=3加入到约束条件中去,得子问题LP-3,LP-4,分别求解得LP-3:x1=4,x2=2,Z3=340（是整数解，定下界）LP-4:x1=1.42,x2=3,Z4=327（剪掉）问题LP-3的所有解均是整数解,而问题LP-4还有非整数解,但由于Z3Z4,对LP-4分枝已没有必要，剪掉。上下界为340Z*349•在对问题LP-2进行分枝,x21.57=1，x21.57=2,得子问题LP-5,LP-6,求解得LP-5:x1=5.44,x2=1,Z5=308(下界340,剪掉)LP-6:无可行解（剪掉）于是得到原整数规划问题的最优解为LP:x1=4,x2=2,Z3=340x1=4.81LP:x2=1.82Z=356LP-1:x1=4x14x2=2.1Z=349LP-2:x1=5x15x2=1.57Z=341LP-3:x1=4x14x2=2x22Z=340LP-6x15无可行解剪掉x22LP-4:x1=1.42x14x2=3剪掉x23Z=327LP-5:x1=5.44x15x2=1剪掉x21Z=308整个过程如下:步骤:1求解相应的线性规划问题的最优解和最优值,如果a)没有可行解,停止;b)若有满足整数条件的最优解,则已得到整数规划问题的最优解,停止;c)若有最优解,但不满足整数条件,记此最优值为原整数规划问题Z*的上界,然后,用观察法求出下界。2分枝、定界，直到得到最优解为止。注意：a）在以后的各枝中，若某一子规划问题的最优解满足整数条件，则用其最优值置换Z*的下界。B）若某一分枝的最优值小于Z*的下界，则剪掉此枝，即以后不再考虑此枝。三、算法需要注意的几点（以极大化问题为例）1在计算过程中，若已得到一个整数可行解x(0)，其相应的目标函数值为Z0，那么在计算其它分枝过程中，如果解某一线性规划所得的目标函数值ZZ0，即可停止计算。因为进一步的分枝结果的最优值只能比Z更差。2分枝变量的选取。分枝变量的选取方式不同，可使整个问题的求解在简繁程度上有很大的差异，选取原则为：选取相应的线性规划解中具有最大分数值的变量作为分枝变量。对要求取整的变量按其重要程度（比如该变量在整数规划模型中代表比较重要的决策；该变量在目标函数中利润系数远远大于其它变量的利润系数等等）排定优先顺序，按优先顺序的先后选取分枝变量。3若有若干个待求解的分枝，先选取目标函数值最大的那一枝。练习：用分支定界法求解下述整数规划问题取整数,0,622054.34max2121212121xxxxxxxxtsxxZx1=5/3LP:x2=8/3Z=44/3LP-1:x1=1x11x2=16/5剪掉Z=68/5LP-2:x1=2x12x2=2Z=14第三节割平面解法(CuttingPlaneApproach)割平面法是1958年美国学者R.E.Gomory提出的。基本思想是：先不考虑变量的取整数约束，求解相应的线性规划，然后不断增加线性约束条件（即割平面），将原可行域割掉不含整数可行解的一部分，最终得到一个具有整数坐标顶点的可行域，而该顶点恰好是原整数规划问题的最优解。例：求解取整数,0,431.max2121212121xxxxxxxxtsxxZ加松弛变量x3、x4，使其变成标准形（如有非整数的系数，则将其所在的方程乘以某一常数，变成具有整数系数的约束方程），用单纯形法求解得cj1100CBXBbx1x2x3x400x3x414-13111001初始表0110011x1x23/47/41001-1/43/41/41/4最终表00-1/2-1/2最优解x1=3/4，x2=7/4，x3=x4=0，最优值为Z=5/2，是非整数解。寻求割平面：由最终表得x1-1/4x3+1/4x4=3/4x2+3/4x3+1/4x4=7/4任选一取分数值的基变量，比如x1，将该式中所有变量的系数、右端常数项均改写成整数与非负真分数之和的形式，并移项得x1-x3=3/4-（3/4x3+1/4x4）（注：所有的x均是整数。x3、x4可通过在原约束条件中乘以某一常数变成整数。）则整数约束条件可由下式替代3/4-（3/4x3+1/4x4）0即得割平面方程-3x3-x4-3引入松弛变量x5，将其加入到原规划的约束条件中，利用上述最终表得cj11000CBXBbx1x2x3x4x500x3x414-13111001初始表01100110x1x2x53/47/4-3100010-1/43/4-31/41/4-1001最终表00-1/2-1/20用对偶单纯形算法进行计算。x5作换出变量，x3换入变量，迭代得cj11000CBXBbx1x2x3x4x5110x1x2x31111000100011/301/31/121/4-1/3000-1/3-1/6已得到整数解，最优解为x1=1，x2=1，最优值为2。注：新约束-3x3-x4-3的几何意义。上述约束中以x1，x2表示x3，x4，得x21，其图形见下图。3x1+x2=4-x1+x2=1x21求切平面的基本步骤：1令xi是相应线性规划问题最优解中为分数解的一个基变量，由单纯形最终表得到xi+aikxk=bi，其中i为基变量的标号；k为非基变量的标号。2将bi和aik都分解成整数部分N与非负真分数部分f之和，即bi=Ni+fi，其中0fi1aik=Nik+fik,其中0≤fik1将上式代入式xi+aikxk=bi中得xi+Nikxk-Ni=fi-fikxk3切平面方程为fi-fikxk0练习:用切平面法求解下列整数规划问题取整数,0,622054.34max2121212121xxxxxxxxtsxxZ解:1求解相应的线性规划得cj4300CBXBbx1x2x3x400x3x420642511001检验数0430004x3x4830131/210-21/2检验数-12010-234x2x18/35/301101/3-1/6-2/35/6检验数-44/300-1/3-4/32.对x2引入切平面方程2/3-1/3x3-1/3x40,整理得x3+x42加入原约束中,增加剩余变量x5,用对偶单纯形法求解得最优解为x1=x2=x3=2,最优值为Z=14.(画出切平面)cj43000CBXBbx1x2x3x4x5340x2x1x58/35/3-20101001/3-1/6-1-2/35/6-1001检验数00-1/3-4/30340x2x1x3222010100001-1111/3-1/6-1检验数-14000-1-1/3