第8章 整数线性规划

8.1整数线性规划问题的提出在前面讨论的线性规划问题中，最优解可能是分数或小数，但对于某些具体问题常要求最优解是整数。我们称这样的线性规划问题为整数线性规划问题（IntegerLinearProgramming简记为ILP）。在整数规划中如果所有的变量都限制为整数，就称为纯整数规划（PureILP）,如果仅一部分变量限制为整数，就称为混合整数规划（MixedILP）,整数规划的一个特例就是0—1规划，它的变量仅取0或1。例8-1投资决策问题某部门在今后五年中可用于投资的资金总额为B万元，有n(n2)个可以投资的项目，假定每个项目最多投资一次，第j（nj）个项目所需投资资金为jb万元，获得的利润为jc万元，问如何选择投资项目，才能使获得的总利润最大。8.1整数线性规划问题的提出解设投资决策变量为个项目不投资第个项目投资第jjjx01nj,,2,1设获得的总利润为z，则上述问题的数学模型为10st.max11或jnjjjnjjjxBxbxcz(8.1)该问题是决策变量只能取0或1的整数规划问题。8.1整数线性规划问题的提出例8-2某厂拟用集装箱托运甲、乙两种货物，货物的体积、重量、可获得的利润及托运所受的限制如表8-1所示。表8-1货物的体积、重量、可获得的利润及托运所受限制表货物体积每箱（米3）重量每箱（百公斤）利润每箱（百元）甲5220乙4510托运限制2413两种货物各托运多少箱，可使得利润最大？8.1整数线性规划问题的提出解设21,xx分别为甲、乙两种货物的托运箱数，设获得的总利润为z，则上述问题的数学模型为且为整数0x,x13x5x224x4x5st.x10x20zmax21212121(8.2)这是纯整数规划问题。8.1整数线性规划问题的提出例8-3旅行售货员问题。有一推销员，从城市0v出发，要遍访城市nvvv,,,21各一次，最后返回0v，已知从iv到jv的旅费为ijc，问他应按怎样的次序访问这些城市，才能使得总旅费最少？解对每一对城市设一个变量ijx，令其他情况直接进入从,0,1jvjvijx8.1整数线性规划问题的提出则上述问题的数学模型为：njiijijxcz0,minniunjixnjinnxuunixnjxiijijjinjijniij,,2,1,,,1,0,,1或01,1,,1,0,1,,1,0,1st.00为连续变量（8.3）8.1整数线性规划问题的提出对于目标函数的极小而言，令Miic（M为充分大正数），迫使0iix，n,,,i10。第一组约束条件表示各城市恰好进入一次；第二组约束条件表示各城市恰好离开一次；第三组约束条件用以防止出现多于一个互不连通的旅行路线图，且不排除任何可能的旅行路线。例如，对于六个城市)5(n的货郎担问题，若令：1201201xxx，1534534xxx，其它0ijx8.1整数线性规划问题的提出0v1v2v3v4v5v图8-1售货员旅行路线图示如图8-1中所示的两个互不连通的旅行路线图，这样一组ijx满足第一、二组约束条件，但不满足第三组约束条件，因为其中的三个不等式为：454545355443uuuuuu这三个不等式相加，不论543u,u,u取任何实数值均导致45的矛盾，第三组约束所起的这个作用是可以严格证明。根据定义，旅行售货员问题是一个混合整数线性规划问题。有许多实际应用问题的数学模型都是（8.3）的形式，如生产顺序表问题、集成电路的布线问题等。8.2整数规划的图解法关于两个变量的纯整数规划问题，可以用图解法进行求解，求解的方法和线性规划的图解方法基本上相同，只是在平移目标函数等值线时有所不同。定义1一个纯整数线性规划问题，去掉整数限制以后的线性规划，就称为该纯整数线性规划问题相应的线性规划问题。例8-4且为整数,0,103213322st.4max21212121xxxxxxxxz(8.4)8.2整数规划的图解法用图解法求解方法如下：首先用图解法求解相应线性规划模型的最优解，求得最优解为：)2,2(A32，最优值为3212；因最优解中含有分数，不符合整数要求，因此将目标函数线向左下方平移，相交的第一个整数点就是符合约束条件的整数最优解。对于本题平移目标函数线得最优解为)3,2(B，最优值为11。)2,322(A3,2B12343211x2x图8-2例8-4图解法8.2整数规划的图解法从此题可以看到，整数线性规划有如下特点：1．任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于等于相应的线性规划的最大目标函数值；任何最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于等于相应的线性规划的最小目标函数值。2．相应的线性规划可行域有界时，整数可行解为有限个。8.3整数线性规划问题的求解——割平面法1．基本思想给出整数规划)(P)0st.minmin,n1,2,jjxz整数（XbAXCX(8.5)可先求其相应的线性规划问题)(0P0st.minminXbAXCXz(8.6)8.3整数线性规划问题的求解——割平面法如果)(0P中的最优解满足)(P中的整数要求，则已求得)(P的整数最优解。如果)(0P的最优解的分量不全是整数，就对)(0P增加一个约束条件（称它为割平面方程），新增加的割平面方程将)(0P的可行域割去一块，并且非整数的最优解恰好在这一块中，即非整数的最优解被割去，而)(P的全部整数可行解保留，然后再解新的线性规划，检查其最优解是否满足整数要求，这样继续进行下去，直至得到最优解满足整数要求为止。8.3整数线性规划问题的求解——割平面法2．割平面法求解ILP问题的一般步骤Step1用单纯形法求解ILP问题)(P的相应的LP问题)(0P,如果)(0P没有最优解，则计算停止，)(P也没有最优解。如果)(0P有最优解，)(0P的最优解为bB1，如果bB1全为整数，则bB1也是)(P的最优解，计算停止，否则转入下一步。Step2切割方程的确定如果bB1不全为整数，可设ijx是)(0P问题中最优解为分数值的一个基变量，由单纯形表的最终表得到,0Rjjijijxbbxi(8.7)8.3整数线性规划问题的求解——割平面法将0ib和ijb分解为整数部分与非负真分数部分之和，即10,][10,][0000ijijijijiiiiffbbffbb其中][ijb表示不超过ijb的最大整数部分。将0ib和ijb代入到方程(8.7)中，则有RjRjjijijijijxffxbbxi00][][。现要求变量为非负整数，对于问题)(0P作新的约束条件00Rjjijixff，称此约束为切平面方程。8.3整数线性规划问题的求解——割平面法Step3将切割平面方程加入松弛变量，Rjiijijissxff0,0，然后加入到Step1。相应的在单纯形表中就增加了最后一行。Step4用对偶单纯形法迭代求解,若求得的最优解为整数则计算停止，已求得最优整数解，若对偶问题是无界的，表明原ILP问题不可行，停止计算。否则，返回Step2。Gomory的切割法自1958年提出后，引起人们广泛的注意，但至今完全用它解决问题仍是少数，其原因是经常遇到收敛很慢的情形，但若和其他方法（分枝定界法）配合使用也是有效的。8.4整数线性规划问题的求解—分枝定界法1．基本思想分枝定界法（BranchandBoundMethod）求解整数规划问题的基本思想是，通过分枝枚举来寻找最优解。实施的作法是，首先不考虑对变量的整数要求，求解相应的线性规划问题，如求得的最优解不符合整数要求，则把原问题分解为两部分，每一部分都增加新的约束条件以减小相应线性规划问题的可行域。通过不断地分解，逐步逼近满足要求的整数最优解，在这个过程中包括了“分枝”和“定界”两个关键步骤。8.4整数线性规划问题的求解—分枝定界法2．分枝定界法求解ILP问题的一般步骤根据分枝定界法的基本思想，人们归纳总结出了分枝定界法求解整数规划问题的一般步骤，这里以求目标函数值最大化问题为例加以说明：给出整数规划)(P0st.maxmax)21,n,,jjxz整数（XbAXCX(8.8)可先求其对应的线性规划问题)(0P0st.maxmaxXbAXCXz(8.9)8.4整数线性规划问题的求解—分枝定界法Step1求解相应的线性规划问题)(0P，并确定初始上、下界求解相应的线性规划问题)(0P，若)(0P无解，则)(P无解，停止计算；若)(0P的最优解满足整数要求，就得到)(P的最优解，计算完毕；若)(0P的最优解中有非整数分量，其最优目标函数值是)(P的初始上界，记为z，任意选的一个整数可行解（一般可取njxj,2,1,0），求得其目标函数值作为初始下界，并记为z，以*z表示问题)(P的最优目标函数值；这时有zzz8.4整数线性规划问题的求解—分枝定界法Step2分枝并求解在非整数最优解中，任选一个不满足整数约束条件的变量jjbx以][jb表示小于jb的最大整数，构造两个约束条件1][],[jjjjbxbx将这两个约束条件，分别加入)(0P中，得到线性规划问题，求解这两个后继线性规划问题。Step3定界下界的修改,若后继问题为某一个分枝标明求得的最优解，符合整数条件，最优目标函数值比原来的下界更大，则以它代替原来的成为新的下界，在整个分枝定界法的求解过程中，下界的值不断增大。上界的修改,新的上界是后继问题求得的目标函数值和未被分枝的问题中目标函数值中最大的一个，在整个分枝定界法的求解过程中，上界的值不断减小。8.4整数线性规划问题的求解—分枝定界法Step4比较与剪枝出现下列三种情形之一者，均应剪枝。(1)该枝无可行解；(2)该枝已得到整数最优解；（3）该枝得到非整数最优解，且目标函数值zz。如果zz，返回Step2继续分枝。直到*zzz，此时得到)(P的最优解，目标函数值*zzz。分枝定界法可用于解纯整数规划问题，也可以用于求混合整数规划问题，求混合整数规划问题时，只须队整数要求的变量进行分枝就可求得最优解。在20世纪60年代初由Land和Dong提出经Dakin修正的，其优点是方法灵活便于计算机求解，所以现在它已成为求解整数规划的重要方法之一，目前已成功地应用于求解整数规划问题、生产进度表问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。8.4整数线性规划问题的求解—分枝定界法例8-5用分枝定界法求解下列整数规划模型。且为整数,0,702075679st.9040max21212121xxxxxxxxz(8.10)8.4整数线性规划问题的求解—分枝定界法解该问题的分枝定界过程如下图。0LP81.41x82.12x356z0PL41x1.22x349z0PL51x57.12x341z41x52x356z0z0PL41x22x340z42.11x32x327z0PL44.51x12x308z无可行解21x11x32x22x349z0z341z340z340*zzz0PL0PL图8-3分枝定界求解过程图8.5线性规划问题的求解1．枚举法（Enumeration）当变量的个数较少时，0-1规划可用枚举法。即列出变量组的全部取值，一般的当变量组个数为k时，其全部取值有k2。在逐一检查他们是否满足约束条件，也就是判断它们是否为可行解，然后通过计算全部可行解的目标函数值，从而比较出最优解。1．隐枚举法（ImplicitEnumeration）通过试探法先找一个可行解，对于求最大化问题，则目标函数值一定大于这个可行解对应的目标函数值。这样就构造了