第五章 整数规划

第五章 整数规划,在求解线性规划问题时，得到的最优解可能是分数或小数，但许多实际问题要求得到的解为整数才行。这种要求线性规划有整数解的问题,称为,整数规划,(Integer Programming),或简称,IP,。,第一节 整数规划的数学模型及解的特点,引例,某厂拟用火车装运甲、乙两种货物集装箱，每 箱的体积、重量、可获利润以及装运所受限制如下：,货物集装箱 体积,(,米,3),重量,(,百斤,),利润,(,百元,),甲,5 2 20,乙,4 5 10,托运限制,24 13,问两种货物各装运多少箱，可使获得利润最大？,是不是可通过把不考虑整数要求求得的最优解经过,“,化整,”,得到满足整数要求的最优解呢？,设甲、乙两种货物装运箱数分别为,x,1,和,x,2,。显然，,x,1,、,x,2,都要求为整数,于是可建立整数规划模型如下：,Max z,20 x,1,+10 x,2,(1),5x,1,+4x,2,24 (2),2x,1,+5x,2,13 (3),x,1,x,2,0 (4),x,1,x,2,为整数,(5),它和线性规划问题的区别在于条件,(5),。,此例可解得,x,1,=4.8,x,2,=0,，凑整为,x,1,=5,x,2,=0,，这就破坏了条件,(2),，因而不是可行解；如截断小数变为,x,1,=4,x,2,=0,，这当然满足所有约束条件，但不是最优解，因为对,x,1,=4,x,2,=0,有,z,80,，而对,x,1,=4,x,2,=1,（也是可行解）有,z,90,。因此要专门研究整数规划的解法。,整数规划的数学模型,若要求所有,x,j,的解为整数，称为纯整数规划,若要求部分,x,j,的解为整数，称为混合整数规划,对应没有整数解要求的线性规划称之为松弛问题,整数规划的解是可数个的，最优解不一定发生在极点,整数规划的最优解不会优于其松弛问题的最优解,第二节 分支定界法,分枝定界法是,20,世纪,60,年代由,Land-Doig,和,Dakin,等人提出的。这种方法既可用于,纯整数,规划问题，也可用于,混合整数,规划问题，而且便于用计算机求解，所以很快成为解整数规划的最主要的方法。,(1),用观察法求,R,的一个可行解，其目标值便是,R,的最优目标值,z,*,的一个下界,z,。,(2),求解,R,0,，得,R,0,的最优解,x,(0),和最优值,z,0,。若,x,(0),符合,R,的整数条件，则显然,x,(0),也是,R,的最优解，结束；否则，以,R,0,作为一个分枝标明求解的结果，,z,0,是问题,R,的最优目标值,z,*,的一个上界,z,。,(3),分枝。取目标函数值最大的一个枝,R,s,，在,R,s,的解中任选一不符合整数条件的变量,x,j,，其值为,b,j,，构造两个约束条件,x,j,b,j,和,x,j,b,j,+1,。将两个约束条件分别加入问题,R,s,，得两个后继规划问题,R,s1,和,R,s2,。不考虑整数条件求解这两个后继问题，以每个后继问题为一分枝标明求解的结果。,分支定界法的步骤,(4),定界。在各分枝中找出目标函数值最大者作为新的上界,z,；从已符合整数要求的各分枝中，找出目标函数值最大者作为新的下界,z,。,(5),比较与剪枝。各分枝的最优目标函数值中如果有小于,z,者，则剪掉这一枝（用打,表示），即以后不再考虑了。若已没有大于,z,的分枝，则已得到,R,的最优解，结束；否则，转,(3),。,下面看一具体的例题：,例 求解问题,Max z=40 x,1,+90 x,2,9x,1,+7x,2,56,7x,1,+20 x,2,70,x,1,x,2,0,整数,R,0,:z,0,=356,x,1,=4.81,x,2,=1.82,R,1,:z,1,=349,x,1,=4.00,x,2,=2.10,R,2,:z,2,=341,x,1,=5.00,x,2,=1.57,R,12,:,z,12,=327,x,1,=1.42,x,2,=3.00,x,2,3,R,11,:,z,11,=340,x,1,=4.00,x,2,=2.00,R,21,:,z,21,=308,x,1,=5.44,x,2,=1.00,R,22,:,无可,行解,x,1,4,x,1,1,x,1,5,x,1,2,问题,R,0,为,:,Max z=40 x,1,+90 x,2,9x,1,+7x,2,56,7x,1,+20 x,2,70,x,1,x,2,0,问题,R,2,为,:,Max z=40 x,1,+90 x,2,9x,1,+7x,2,56,7x,1,+20 x,2,70,x,1,5,x,1,x,2,0,问题,R,1,为,:,Max z=40 x,1,+90 x,2,9x,1,+7x,2,56,7x,1,+20 x,2,70,x,1,4,x,1,x,2,0,x,2,2,问题,R,11,为,:,Max z=40 x,1,+90 x,2,9x,1,+7x,2,56,7x,1,+20 x,2,70,x,1,4,x,2,2,x,1,x,2,0,问题,R,12,为,:,Max z=40 x,1,+90 x,2,9x,1,+7x,2,56,7x,1,+20 x,2,70,x,1,4,x,2,3,x,1,x,2,0,第三节,0-1,整数规划,0-1,型整数规划是整数规划的一种特殊形式，它的变量,xj,仅取值,0,或,1,。这种只能取,0,或,1,的变量称为,0-1,变量,或,二进制变量。,下面通过过一个例子说明一下：,例,:,某公司拟在市东、西、南三区建立门市部。拟议中有,7,个位置,A,i,（,i=1,2,7,）可供选择。规定：,(1),在东区,A,1,、,A,2,、,A,3,三个点中至多选两个；,(2),在西区,A,4,、,A,5,两个点中至少选一个；,(3),在南区,A,6,、,A,7,两个点中至少选一个。,如选用,A,i,点，设备投资估计为,b,i,元，每年可获利润估计为,c,i,元，但投资总额不超过,B,元。问应选择哪几个点可使年利润为最大？,建立模型如下所示：,引入,0-1,变量,x,i,（,i=1,2,7,）,令,1,当,A,i,点被选用,x,i,=,0,当,A,i,点没被选用。,（,i=1,2,7),Max z=c,1,x,1,+c,2,x,2,+c,7,x,7,b,1,x,1,+b,2,x,2,+b,7,x,7,B,x,1,+x,2,+x,3,2,x,4,+x,5,1,x,6,+x,7,1,x,i,=0,或,1,i=1,2,7,于是建立下列模型,:,例 求解,0-1,型整数规划问题,Max,z=8x,1,+2x,2,-4x,3,-7x,4,-5x,5,3x,1,+3x,2,+x,3,+2x,4,+3x,5,4,5x,1,+3x,2,-2x,3,-x,4,+x,5,4,x,j,=0,或,1,，,j=1,2,5,变成标准型，要求如下：目标函数求极大化。对于目标函数为,Min,z,的极小化问题，令,z,=-,z,，使其变为目标函数为,Max,z,的极大化问题。目标函数中所有变量的系数都为正数。如果目标函数中变量,x,j,的系数为负数，令,x,j,=1-x,j,，把模型中的,x,j,用,x,j,代换。变量的排列顺序按变量在目标函数中的系数值从小到大排列。,求解,0-1,型整数规划，可使用分枝定界法。下面用实例说明：,x,2,=x,3,=x,5,=x,4,=x,1,=1,z=10,不可行,z=6,不可行,z=5,不可行,z=3,不可行,z=2,不可行,x,2,=0,x,1,=0,z=4,可行,x,3,=0,x,3,=0,z=8,不可行,x,5,=0,x,5,=0,z=1,z=-2,x,4,=0,x,4,=0,最优解为,x,2,=0,，,x,3,=0,，,x,5,=1,，,x,4,=1,，,x,1,=1,。,于是，原问题的最优解为,z,*,=4,，,x,1,*,=1,，,x,2,*,=0,，,x,3,*,=1-0=1,，,x,4,*,=1-1=0,，,x,5,*,=1-1=0,令,x,3,=1-x,3,x,4,=1-x,4,x,5,=1-x,5,，得,Max,z=2x,2,+4x,3,+5x,5,+7x,4,+8x,1,-16,3x,2,-x,3,-3x,5,-2x,4,+3x,1,-2,3x,2,+2x,3,-x,5,+x,4,+5x,1,6,x,2,x,3,x,5,x,4,x,1,=0,或,1,第四节 指派问题,指派问题的标准形式,及其数学模型,匈牙利解法求解指派问题,一般的指派问题,有,n,项任务，恰好,n,个人承担，第,i,人完成第,j,项任务的花费,(,时间或费用等,),为,c,ij,，如何指派使总花费最省？,一、指派问题的标准形式,及其数学模型,指派问题的系数矩阵如下：,C,ij,的含义可以不同，如费用、成本、时间等。,系数矩阵,C,中，第,i,行中各元素表示第,i,人做各事的费用；第,j,列各元素表示第,j,事由各人做的费用。,为建立标准指派问题的数学模型，引入,nn,个,01,变量：,指派问题的数学模型可写成如下页形式：,若派第,i,人做第,j,事,0,若不派第,i,人做第,j,事,（,ij=1,，,2,，,n,）,第,j,项工作由一个人做,第,i,人做一项工作,指派问题的每个可行解，可用矩阵表示如下：,矩阵,X,中，每行各元素中只有,1,个元素为,1,其余各元素等,0,；每列各元素中也只有,1,个元素为,1,其余各元素等,0,。,指派问题有,n,！个可行解。,例,1,有一份中文说明书，需译成英、日、德、俄四种文字。分别记作,E,、,J,、,G,、,R,。现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种的说明书所需时间如下表。问应指派何人去完成何工作，使所需总时间最少？,指派问题的数学模型如下：,已知条件可用系数矩阵（,效率矩阵,）表示为：,其可行解也可用每行仅有一个,1,，每列也仅有,一,个,1,的矩阵表示，如：,匈牙利解法的关键是利用了指派问题最优解的如下性质：,若从指派问题的系数矩阵,C,的某行（或某列）各元素分别减去一个常数,k,，得到一个新的矩阵,C,，则以,C,和,C,为系数矩阵的两个指派问题有相同的最优解。,（系数矩阵的变化并不影响数学模型的约束方程组，而只是目标函数值减少了常数,k,，所以最优解不变）,二、匈牙利法解题步骤,1955,年，库恩利用匈牙利数学家康尼格的关于矩阵中独立零元素的定理，提出了解指派问题的一种算法，称为匈牙利解法。,-2,-4,-9,-7,若某行,(,列,),已有,0,元素，那就不必再减了。例,1,的计算为：,1.,使系数矩阵各行、各列出现零元素,作法：系数矩阵各行元素减去所在行的最小元素，再从所得矩阵的各列减去所在列最小元素。,(,因一行中,x,ij,取值一个,1,，其余为,0,，,c,ij,同时减去一常数不影响,x,ij,取值,),。,匈牙利法解题步骤如下：,-4 -2,这就保证每行每列至少有一个,0,元素，同时不出现,负元素,。,2.,试求最优解。如能找出,n,个位于不同行不同列的零元素，令对应的,x,ij,=1,，其余,x,ij,=0,，得最优解，结束；否则下一步。,作法：由独立,0,元素的行（列）开始，独立,0,元素处画 标记，在有 的行列中划去其它,0,元素；再在剩余的,0,元素中重复此做法，直至不能标记 为止。,例,2,求表中所示效率矩阵的指派问题的最小解。,任务,人,A,B,C,D,E,甲,12,7,9,7,9,乙,8,9,6,6,6,丙,7,17,12,14,9,丁,15,14,6,6,10,戊,4,10,7,10,9,经行运算即可得每行每列都有,0,元素的系数矩阵。,再按上述步骤运算，得到：,所画,0,元素少于,n,，未得到最优解。,3.,作能覆盖所有,0,元素的最少直线数的直线集合,(1),对没有 的行打,号；,(2),对已打,号的行中所有,0,元素的所在列打,号；,(3),再对打有,号的列中,0,元素的所在行打,号；,(4),重复,(2),(3),直到得不出新的打