运筹学第五章整数规划

1、第五章整数规划(Integer Programming),整数规划的模型 分支定界法 割平面法 01 整数规划 指派问题,一、整数规划的一般形式,1、实例,例1 某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表1：,问两种货物各托运多少箱，可使获得的利润为最大？,第一节 整数规划问题的提出,2、整数规划一般形式,解：设托运甲、乙两种货物x1，x2箱，用数学式可表示为：,从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时

2、甚至不能保证所得倒的解是整数可行解。,3、与LP问题的关系,（1）求解方法方面,例2 设整数规划问题如下,首先不考虑整数约束，得到线性规划问题（一般称为松弛问题,或者B问题，原问题又称为A问题）。,用图解法求出最优解 x13/2, x2 = 10/3 且有Z = 29/6,x1,x2,3,3,(3/2,10/3),现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3) (2，3)(1，4)(2，4)。显然，它们都不可能是整数规划的最优解。,按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。,因此，可将集合内的整数点一一

3、找出，其最大目标函数的值为最优解，此法为完全枚举法。 如上例：其中（2，2）（3，1）点为最大值，Z=4。,目前，常用的求解整数规划的方法有： 分支定界法和割平面法； 对于特别的01规划问题采用隐枚举法和匈牙利法。,例3 做图分析例1的最优解(直观),x1,x2,4,8,4,0,Z=96,1,2,3,5,6,7,3,1,2,5x1+4x2=24,2x1+5x2=13,C(4.8,0),Z=90(最优解),B(4,1),Z=80,4、IP问题的求解思路,通过上面的分析，该法不可行。,（1）对问题B的最优解“舍入取整”,由于IP问题的可行解数量有限，可以全部列出，相应目标函数最优者为最优解。但若决

4、策变量较多时，计算效率低，且容易丢失最优解。,（2）枚举法,设计某种算法，只检查部分可行解，就可找到最优解，提高计算效率。本章讨论的所有方法都是隐枚举法。,（3）隐枚举法,二、整数规划的分类,1、全整数规划问题,2、纯整数规划问题,在下列IP问题中，,在上述IP问题中，,3、0-1规划问题,在上述IP问题中，,4、混合整数规划问题,在上述IP问题中，,一、分支的几何解释,适用范围： 全整数规划问题 纯整数规划问题 0-1规划问题 混合整数规划问题,例1 求解A,第二节 分支定界法 （Branch and Bound Method）,解：图解法,x1,x2,0,1,2,3,4,5,6,7,8,9

5、,10,1,2,3,4,5,6,7,8,9x1+7x2=56,7x1+20 x2=70,B,C,问题B1 Z1=349 x1=4.00 x2=2.10,问题B2 Z2=341 x1=5.00 x2=1.57,x1=x(0),x1=x(0)+1,Z=40 x1+90 x2,已知，求得B问题的最优解x(0)=(4.81,1.82) Z0=356 由于不满足整数条件，选择一个决策变量进行分支。选x1。 X1=4.81，按 进行分支，相当于分别增加了一个约束条件。,xr 和xr 1,分支,0 1 2 3 4 5 6 7 X1,5 4 3 2 1,X2,(4.81,1.82),分别解B1,B2得x=(4

6、,2.1)和x=(5,1.57),仍不满足整数条件。先对B1分枝,在B1中分别加入X22形成B3, 加入X23形成B4。同理对B2分枝,见下页。,0 1 2 3 4 5 6 7 X1,5 4 3 2 1,X2,(4.81,1.82),先对B1分枝得B3 B4 ,再对B2分枝,分别添加X2 1和X2 2得B5和B6 后者无可行解（无可行域）,用单纯形法求IP问题的最优解。,二、基本思路,分支,对问题B增加约束条件，形成多个LP子问题，这一过程并没有使问题A的可行解丢失，但可使问题A的可行解成为LP子问题可行域的顶点。这样用单纯形法求解这些LP子问题所得最优解才可能为整数解。,定界,通过比较LP子

7、问题的最优目标函数值，确定问题A的最优目标函数取值范围。当某个LP子问题的最优目标函数值不在该范围，表明没有必要再检查该LP子问题中的整数可行解，从而提高计算的效率。,三、定界规则,max问题： 每一次分支求解后都要定下界，整数分支中目标值最大的一个为新的下界；小于下界的分支要剪支；上界不影响结果，可以不用定上界。（其实就是选择最大的整数分支） min问题： 每一次分支求解后都要定上界，整数分支中目标值最小的一个为新的上界；大于上界的分支要剪支；下界不影响结果，可以不用定下界。（其实就是选择最小的整数分支）,问题B x1=4.81 x2=1.82 Z0=356,问题B1 x1=4.00 x2=

8、2.10 Z1=349,问题B2 x1=5.00 x2=1.57 Z2=341,问题B3 x1=4.00 x2=2.00 Z3=340,问题B4 x1=1.42 x2=3.00 Z4=327,问题B5 x1=5.44 x2=1.00 Z5=308,问题B6 无可行解,0 ZA *,340 ZA,ZA*=340,x14,x15,x22,x23,x21,x22,定界与剪支,例2 用分支定界法求解整数规划问题,LP1 x1=1, x2=3 Z(1) 16,LP x1=18/11, x2=40/11 Z(0) 19.8,LP2 x1=2, x2=10/3 Z(2) 18.5,LP3 x1=12/5,

9、x2=3 Z(3) 17.4,LP4 无可 行解,LP5 x1=2, x2=3 Z(5) 17,LP6 x1=3, x2=5/2 Z(6) 15.5,x11,x12,x23,x24,x12,x13,ZA * -16,ZA * -17,1、求松弛问题的最优解：先不考虑整数约束，解( IP )的松弛问题( LP )，可能得到以下情况之一： .若( LP )没有可行解，则( IP )也没有可行解，停止计算。 .若( LP )有最优解，并符合( IP )的整数条件，则( LP )的最优解即为( IP )的最优解，停止计算。 .若( LP )有最优解，但不符合( IP )的整数条件，转入下一步。为讨论方

10、便，设( LP )的最优解为：,四、分支定界法步骤,2、分支：（分支后并求解） 在( LP )的最优解 X(0)中，任选一个不符合整数条件的变量，例如xr= （不为整数），以 表示不超过 的最大整数。构造两个约束条件 xr 和xr 1,将这两个约束条件分别加入问题( IP ) ，形成两个子问题( IP1)和( IP2 ) ，再解这两个问题的松弛问题。 ( LP1) ( LP2) 称为新的分支，原问题不再称为分支。,如此反复进行，直到得到ZZ* 为止（或者所有分支都已经分析或剪支），即得最优解 X* 。,3、定界： (1)max问题：从已符合整数条件的分枝中，找出目标函数值最大者作为新的下界。

11、(2)min问题：从已符合整数条件的分枝中，找出目标函数值最小者作为新的上界。,4、比较与剪支： 各分枝的目标函数值中，若有小于Z 者，则剪掉此枝，表明此子问题已经探清，不必再分枝了;否则继续分枝。剪枝不再是分支。无可行解也要剪支。,例3 求解下列IP问题,松弛问题的最优解为：X*=(5/2,2),Z*=23,分枝B1:x12,分枝B2:x13,问题II的解即问题A的最优解,可能存在两个分枝都是非整数解的情况，则需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程 当存在很多变量有整数约束时，分枝既广又深，在最坏情况下相当于组合所有可能的整数解 一般整数规划问题属于一类未解决的难题，NP

12、-complete，只有少数特殊问题有好的算法，如任务分配问题、匹配问题,分枝问题的松弛解,方法1：图解法,x1,x2,0,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,2x1+x2=7,2x1+4x2=13,方法2：单纯型表,松弛问题最优单纯形表如下：,将约束条件直接写入单纯形表：,0 x5,2,1,0,0,0,1,x5,0,0,0,0,1,将另一约束条件直接写入单纯形表：,0 x6,-3,-1,0,0,0,1,x6,0,0,0,0,适用范围：全整数规划问题,第三节 割平面法 （Comory Cutting Plain Algorithm）,一、基本原理,原理：

13、在不考虑整数约束的问题中，逐次增加一个新约束（割平面），它能割去该问题可行域中不含整数解的区域。逐次切割下去，直至切割出一个有整数坐标的顶点且恰好是问题的最优解。,(1,1),二、符号说明,例1：,三、Gomory 约束的推导,把(2)(3)代入(1)并移项得：,由于xj为非负整数，故上式左边为整数，而右边与之相等，故也必为整数。那么右边是个怎样的整数呢？由于右边第1项1,括号内0，故右边是1的整数，那这个整数就只可能以0为上限（即可能的整数是0，-1，-2，.）。上述结论是在xj 为整数条件下得出的。,四、计算步骤,All xi 为整数 ?,结束,写出Gomory约束,Y,N,解松弛问题,例

14、2,解：,0 x5,-1/2,0,0,-7/22,-1/22,1,x5,0,0,0,0,解：由单纯形法计算得最优表,0 x6,-4/7,0,0,0,-1/7,0,0,0,x6,0,0,1,-6/7,用对偶单纯形法进行计算，可得如下最优表,同样用对偶单纯形法进行计算，可得如下最优表，此时xi的值都已经是整数，解题完成。,五、几何解释：图解法求解,x1,x2,0,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,-x1+3x2=6,7x1+x2=35,Z=7x1+9x2,x(1)=(9/2,7/2) Z(1)=63,x2=3,x(2)=(32/7,3) Z(2)=59,x1

15、 +x2=7,X*=(4,3) Z*=55,一、问题的提出,1、实例,例1 某公司拟在市东、西-南三区建立门市部。拟议中有7个位置（点）Aj供选择。规定 在东区，由A1,A2,A3三个点中至多选两个； 在西区，由A4,A5两个点中至少选一个； 在南区，由A6,A7两个点中至少选一个。 如选用Aj点，设备投资估计为bj元，每年可获利润估计为cj元，但投资总额不能超过B元。问应选择那几个点可使年利润为最大？,则0-1规划模型为：,第四节 0-1整数规划,2、0-1整数规划的一般形式,0-1型整数规划是整数规划的特殊情形，它要求变量的值不仅是整数而且只能是0或1。这种模型常用于变量的物理意义并非数值

16、，而是表示只有2种非此即彼的选择，为了能用数学模型求解这类问题，需要将选择人为地赋予数字，通常用0和1对应于对2种结果的选择。,由于变量的值只能取0或1，理论上可用枚举法将所有变量都取01的所有组合列出来，然后对这些所有可能解依次检查可行性，再在可行解中找出最优解。,3、0-1整数规划的求解思路,为了加快检查的速度，先用观察法找1个可行解（如所有变量都取0），以该解的目标值为参照值（门槛）。 检查其它解，先看其目标值是否优于当前参照值，若不是，筛去。 若是，再检查其可行性，若不满足可行性，筛去，若满足，将其目标值作为新的参照值。 这样，将当前参照值作为对其它解检查的过滤条件以加快检查速度的做法

17、称为隐枚举法。 为了进一步提高速度，还有一个技巧：将目标函数按系数大小顺序排列，所有可能解中变量也按此顺序排列，这样就容易看出那些目标值不优于当前参照值的可能解，从而不需任何检查就被淘汰。,二、 0-1整数规划的隐枚举法,3、不断更换过滤条件,1、把目标函数的系数按升序排列max，约束条件做相应调整；,2、把所有的解x按一定的次序排列,例2 用隐枚举法求解下列0-1规划问题,解：对于01 规划问题，由于每个变量只取0，1两个值，一般会用穷举法来解，即将所有的0，1 组合找出，使目标函数达到极值要求就可求得最优解。但此法太繁琐，工作量相当大。而隐枚举法就是在此基础上，通过加入一定的条件，就能较快

18、的求得最优解。,由上表可知，问题的最优解为 X*=( x1 =1 x2=0 x3=1 ) 由上表可知： x1 =0 x2=0 x3=1 是一个可行解，为尽快找到最优解，可将3 x12 x25 x3 5 作为一个约束，凡是目标函数值小于5 的组合不必讨论，如下表。,三、0-1规划与全、纯整数规划的转换,1、结论,任何一个非负整数y都可表示为,2、 0-1规划与全、纯整数规划的转换,1) 0-1规划问题就是全、纯整数规划问题,2) 全、纯整数规划问题可以利用上述结论 转化为0-1规划问题,例3：,解：把,代入纯整数规划的目标函数和约束条件即可。,一、问题的提出,1、实例,例1 有四个熟练工人，他们

19、都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如下表所示，问如何分配任务使完成四项任务的总工时耗费最少？,第五节 指派问题,解：设,则此指派问题的模型为,二、指派问题最优解的性质,2、指派问题的一般形式,在原指派问题的效益矩阵中同行同列加上某一常数，所得指派问题与原问题同解。,证明：,上述任一种样式具有这样的特点：不同行不同列只有一个元素为0，这样的0称为独立0元素。若将这些0对应的xij取1，其余xij取0，则目标值Z=0，易知这是最优目标值，从而这样的解是最优解。,假设系数矩阵为下列样式中的任一种：,但实际系数矩阵一般不具上述类似样式，指

20、派问题最优解的性质告诉我们，可以将系数矩阵化为上述类似样式而不影响原最优解。根据这一性质，求指派问题就可归结为设法变换系数矩阵，使其含有n个独立0元素。,三、求解指派问题的步骤,例2 以例1为示例,step 1： 0变换，变换效率矩阵，使每行每列至少有一个零 行变换：找出每行最小元素，从该行各元素中减去之 列变换：找出每列最小元素，从该列各元素中减去之,匈牙利法,step 2：圈0试指派，以寻求最优解。 在矩阵中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。找独立0元素，常用的步骤为： (1)从只有一个0元素的行

21、(列)开始，给这个0元素加圈，记作 。然后划去 所在列(行)的其它0元素，记作 ；这表示这列所代表的任务已指派完，不必再考虑别人了。 (2)给只有一个0元素的列(行)中的0元素加圈，记作；然后划去 所在行的0元素，记作 (3)反复进行(1)，(2)两步，直到尽可能多的0元素都被圈出和划掉为止。,(4)若仍有没有划圈的0元素，且同行(列)的0元素至少有两个，则从剩有0元素最少的行(列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止。 (5)若 元素的数

22、目m 等于矩阵的阶数n，那么这指派问题的最优解已得到。若m n, 则转入下一步。,Step 3：覆盖所有0元素，作最少的直线覆盖所有0元素。 (1)对没有的行打号； (2)对已打号的行中所有含元素的列打号； (3)再对打有号的列中含 元素的行打号； (4)重复(2)，(3)直到得不出新的打号的行、列为止；（即从没有圈0行开始，圈0所在行，划0所在列，打勾） (5)（用最少的直线覆盖全部0元素） 对没有打号的行画横线，有打号的列画纵线，这就得到覆盖所有0元素的最少直线数 l 。l 应等于m，若不相等，说明试指派过程有误，回到Step 2(4)，另行试指派；若 lm n，须再变换当前的系数矩阵，以

23、找到n个独立的0元素，为此转Step 4。,例3 ： 有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？,求解过程如下： step 1： 0变换,5,step 2：圈0试指派,找到 3 个独立零元素 但 m = 3 n = 4,Step 3：覆盖所有0元素,Step 4：进一步变换系数矩阵，增加0元素, 在未划线的元素中找最小者，设为 对未被直线覆盖的各元素减去 对两条直线交叉点覆盖的元素加上 只有一条直线覆盖的元素保持不变,得到4个独立零元素， 所以最优解矩阵为：,答：最优分配方案为 x14= x21= x32 = x43 =1，其余为0， 即甲D，乙A，丙B，丁C，OBJ=15,在实际应用中，经常遇到非标准形式的指派问题。处理方法：化标准，再按匈牙利访法求解。, 最大化指派