割平面法-运筹学整数规划.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,.,*,第一节 问题的提出,例子：某厂拟采用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表,问两种货物托运多少箱，可使获得利润为最大？,第三章 整数规划（,Integer Programming),分类：,1.,纯整数线性规划,（,Pure Integer Linear Programming,）,2.,混合整数线性规划（,Mixed Integer Linear Programming,）,3.0-1,型整数线性规划（,Zero-One Integer Linear Programming,）,1,.,分配问题与匈牙利法,21,2,.,分配问题与匈牙利法,48,21,答案：,3,.,解：设,x,1,，,x,2,分别表示两种货物托运的箱数，那么其线性规划为,可得最优解为,x,*,=,（,5/3,，,8/3),T,。,如果选用“向上凑整”的方法可得到,x,(1),=(2,3),T,则此时已破坏了体积约束,超出可行域的范围,;,如果“舍去小数”可得,x,(2),=(1,2),T,则此时虽是可行解,值为,10,，不是最优解,因为当,x*=(2,2),T,是,其利润为,14.,由于托运的箱数不能为分数，故上述规划问题是整数规划问题。,若不考虑整数约束，其相应的线性规划问题为：,4,.,第二节 分枝定界法,(Branch and Bound method),引言：穷举法对小规模的问题可以。大规模问题则不行。,一、基本思想和算法依据,基本思想,是：先求出相应的线性规划最优解，若此解不符合整数条件，那么其目标函数的值就是整数规划问题最优值的上界，而任意满足整数条件的可行解的目标函数值将是其下界（定界），然后将相应的线性规划问题进行分枝，分别求解后续的分枝问题。如果后续分枝问题的最优值小于上述下界,则剪掉此枝,;,如果后续某一分枝问题的最优解满足整数条件，且其最优值大于上述下界，则用其取代上述下界，继续考虑其它分枝，直到最终求得最优的整数解。,算法的依据,在于：“整数规划的最优解不会优于相应的线性规划问题的最优解”。具体说就是，对极大化问题，与整数规划问题相应的线性规划问题的目标函数值，是该整数规划问题目标函数的上界；任何满足整数条件的可行解的目标函数值将是其下界。,5,.,二、具体步骤（以例子说明）,解：,第一步：先不考虑整数约束条件，求解相应的线性规划问题，得最优解和最优值如下,x,1,=4.81,x,2,=1.82,Z=356,此解不满足整数解条件。定出整数规划问题目标函数的上下界。上界为,Z=356,；用观察法可知,x,1,=0,，,x,2,=0,是可行解，从而其整数规划问题目标函数的下界应为,0,，即,0,Z*356,6,.,9x,1,+7x,2,=56,7x,1,+20 x,2,=70,Z=40 x,1,+90 x,2,LP-1,LP-2,第二步：分枝与定界过程。,将其中一个非整数变量的解，比如,x,1,进行分枝，即,x,1,4.81 =4,x,1,4.81=5,并分别加入,LP,问题的约束条件中,得两个子,LP,规划问题,LP-1,LP-2,分别求解此两个子线性规划问题,其最优解分别是,LP-1:x,1,=4,x,2,=2.1,Z,1,=349,LP-2:x,1,=5,x,2,=1.57,Z,2,=341,7,.,没有得到全部决策变量均是整数的解。再次定出上下界,0,Z,*,349,继续对问题,LP-1,，,LP-2,进行分枝。先对目标函数值大的子问题进行分枝，即分别将,x,2,2.1 =2,x,2,2.1 =3,加入到约束条件中去,得子问题,LP-3,LP-4,分别求解得,LP-3:x,1,=4,x,2,=2,Z,3,=340,（是整数解，定下界）,LP-4:x,1,=1.42,x,2,=3,Z,4,=327,（剪掉）,问题,LP-3,的所有解均是整数解,而问题,LP-4,还有非整数解,但由于,Z,3,Z,4,对,LP-4,分枝已没有必要，剪掉。,上下界为,340,Z,*,349,在对问题,LP-2,进行分枝,x,2,1.57 =1,，,x,2,1.57 =2,得子问题,LP-5,LP-6,求解得,LP-5:x,1,=5.44,x,2,=1,Z,5,=308(,下界,340,剪掉,),LP-6:,无可行解（剪掉）,8,.,于是得到原整数规划问题的最优解为,LP:x,1,=4,x,2,=2,Z,3,=340,x,1,=4.81,LP,:x,2,=1.82,Z=356,LP-1,:x,1,=4,x,1,4,x,2,=2.1,Z=349,LP-2,:x,1,=5,x,1,5,x,2,=1.57,Z=341,LP-3,:x,1,=4,x,1,4,x,2,=2,x,2,2,Z=340,LP-6,x,1,5,无可行解 剪掉,x,2,2,LP-4,:x,1,=1.42,x,1,4,x,2,=3,剪掉,x,2,3,Z=327,LP-5,:x,1,=5.44,x,1,5,x,2,=1,剪掉,x,2,1,Z=308,整个过程如下,:,9,.,步骤,:,1,求解相应的线性规划问题的最优解和最优值,如果,a),没有可行解,停止,;b),若有满足整数条件的最优解,则已得到整数规划问题的最优解,停止,;c),若有最优解,但不满足整数条件,记此最优值为原整数规划问题,Z*,的上界,然后,用观察法求出下界。,2,分枝、定界，直到得到最优解为止。,注意：,a,）在以后的各枝中，若某一子规划问题的最优解满足整数条,件，则用其最优值置换,Z*,的下界。,B,）若某一分枝的最优值小于,Z*,的下界，则剪掉此枝，即以后不再考虑此枝。,10,.,三、算法需要注意的几点（以极大化问题为例）,1,在计算过程中，若已得到一个整数可行解,x,(0),，其相应的目标函数值为,Z,0,，那么在计算其它分枝过程中，如果解某一线性规划所得的目标函数值,ZZ,0,，即可停止计算。因为进一步的分枝结果的最优值只能比,Z,更差。,2,分枝变量的选取。分枝变量的选取方式不同，可使整个问题的求解在简繁程度上有很大的差异，选取原则为：,选取相应的线性规划解中具有最大分数值的变量作为分枝变量。,对要求取整的变量按其重要程度（比如该变量在整数规划模型中代表比较重要的决策；该变量在目标函数中利润系数远远大于其它变量的利润系数等等）排定优先顺序，按优先顺序的先后选取分枝变量。,3,若有若干个待求解的分枝，先选取目标函数值最大的那一枝。,11,.,练习：用分支定界法求解下述整数规划问题,x,1,=5/3,LP,:x,2,=8/3,Z=44/3,LP-1,:x,1,=1,x,1,1,x,2,=16/5,剪掉,Z=68/5,LP-2,:x,1,=2,x,1,2,x,2,=2,Z=14,12,.,第三节 割平面解法,(Cutting Plane Approach),割平面法是,1958,年美国学者,R.E.Gomory,提出的。,基本思想是：先不考虑变量的取整数约束，求解相应的线性规划，然后不断增加线性约束条件（即割平面），将原可行域割掉不含整数可行解的一部分，最终得到一个具有整数坐标顶点的可行域，而该顶点恰好是原整数规划问题的最优解。,例：求解,13,.,加松弛变量,x,3,、,x,4,，使其变成标准形（如有非整数的系数，则将其所在的方程乘以某一常数，变成具有整数系数的约束方程），用单纯形法求解得,14,.,最优解,x,1,=3/4,，,x,2,=7/4,，,x,3,=x,4,=0,，最优值为,Z=5/2,，是非整数解。,寻求割平面：由最终表得,x,1,-1/4x,3,+1/4x,4,=3/4,x,2,+3/4x,3,+1/4x,4,=7/4,任选一取分数值的基变量，比如,x1,，将该式中所有变量的系数、右端常数项均改写成,整数,与,非负真分数,之和的形式，并移项得,x,1,-x,3,=3/4 -,（,3/4x,3,+1/4x,4,）,（注,：所有的,x,均是整数。,x,3,、,x,4,可通过在原约束条件中乘以某一常数变成整数。）,则整数约束条件可由下式替代,3/4 -,（,3/4x,3,+1/4x,4,）,0,即得割平面方程,-3x,3,-x,4,-3,引入松弛变量,x,5,，将其加入到原规划的约束条件中，利用上述最终表得,15,.,用对偶单纯形算法进行计算。,x5,作换出变量，,x3,换入变量，迭代得,16,.,已得到整数解，最优解为,x,1,=1,，,x,2,=1,，最优值为,2,。,注：新约束,-3x,3,-x,4,-3,的几何意义。,上述约束中以,x1,，,x2,表示,x3,，,x4,，得,x,2,1,，其图形见下图。,17,.,3x,1,+x,2,=4,-x,1,+x,2,=1,x,2,1,求切平面的基本步骤：,1,令,x,i,是相应线性规划问题最优解中为分数解的一个基变量，由单纯形最终表得到,x,i,+,a,ik,x,k,=b,i,，其中,i,为基变量的标号；,k,为非基变量的标号。,2,将,b,i,和,a,ik,都分解成整数部分,N,与非负真分数部分,f,之和，即,b,i,=N,i,+f,i,，其中,0f,i,1,a,ik,=N,ik,+f,ik,其中,0f,ik,1,18,.,将上式代入式,x,i,+,a,ik,x,k,=b,i,中得,x,i,+,N,ik,x,k,-N,i,=f,i,-f,ik,x,k,3,切平面方程为,f,i,-f,ik,x,k,0,练习,:,用切平面法求解下列整数规划问题,19,.,解,:1,求解相应的线性规划得,20,.,2.,对,x2,引入切平面方程,2/3-1/3x,3,-1/3x,4,0,整理得,x,3,+x,4,2,加入原约束中,增加剩余变量,x,5,用对偶单纯形法求解得最优解为,x,1,=x,2,=x,3,=2,最优值为,Z=14.(,画出切平面,),21,.,