0-1整数规划解法.ppt

《0-1整数规划解法.ppt》由会员分享，可在线阅读，更多相关《0-1整数规划解法.ppt（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、二二 0-10-1型整数规划的一般解法型整数规划的一般解法-隐枚举法隐枚举法解解0-10-1型型整整数数规规划划最最容容易易想想到到的的方方法法，和和一一般般整整数数线线性性规规划划的的情情形形一一样样，就就是是穷穷举举法法，即即检检查查变变量量取取值值为为0 0或或1 1的的每每一一种种组组合合，比比较较目目标标函函数数值值以以求求得得最最优优解解，这这就就需需要要检检查查变变量取值的量取值的2 2n n个组合。个组合。对于变量个数对于变量个数n n较大较大(例如例如n n10)10)，这几乎是不可能的。这几乎是不可能的。而而隐隐枚枚举举法法就就是是在在此此基基础础上上改改进进的的，通通过过

2、加加入入一一定定的的条条件件，就能较快的求得最优解。就能较快的求得最优解。只只检检查查变变量量取取值值的的组组合合的的一一部部分分，就就能能求求到到问问题题的的最最优优解解，这这样样的的方方法法称称为为隐隐枚枚举举法法(implicit(implicit enumeration)enumeration)，分分枝枝定定界界法法也是一种隐枚举法。其也是一种隐枚举法。其解题关键是寻找可行解，产生过滤条件。解题关键是寻找可行解，产生过滤条件。过滤条件：是满足目标函数值优于计算过的可行解目标函数过滤条件：是满足目标函数值优于计算过的可行解目标函数值的约束条件。值的约束条件。下面举例说明求解下面举例说明求

3、解0-10-1型整数规划的隐枚举法型整数规划的隐枚举法例例例例4.4.6:6:目标函数目标函数 max z=3x1-2x2+5x3 约束条件：约束条件：x1+2x2-x32 （1）x1+4x2+x34 （2）x1+x23 （3）4x2+x36 （4）x1，x2，x3=0或或1 （5）解题时先通过试探的方法找一个可行解，容易看出解题时先通过试探的方法找一个可行解，容易看出(x(x1 1，x x2 2，x x3 3)=(1)=(1，0 0，0)0)，满足（，满足（1 1）（）（4 4）条件，算出相应的目标函数值）条件，算出相应的目标函数值z=3z=3。我我们们在在求求最最优优解解时时，对对于于极极

4、大大化化问问题题，当当然然希希望望z3，于于是是增增加加一一个约束条件：个约束条件：3x1-2x2+5x33 称为过滤的条件称为过滤的条件称为过滤的条件称为过滤的条件(filtering constraint)(filtering constraint)。这样，原问题的。这样，原问题的。这样，原问题的。这样，原问题的线性约束条件就变成线性约束条件就变成线性约束条件就变成线性约束条件就变成5 5个。个。个。个。用全部枚举的方法，用全部枚举的方法，3个变量共有个变量共有23=8个解，原来个解，原来4个约束条个约束条件，共需件，共需件，共需件，共需3232次运算。次运算。次运算。次运算。现在增加了过

5、滤条件现在增加了过滤条件，如按下述方法进行，就可减少运算，如按下述方法进行，就可减少运算次数。将次数。将次数。将次数。将5 5个约束条件按个约束条件按个约束条件按个约束条件按（4 4）顺序排好。）顺序排好。）顺序排好。）顺序排好。对每个解，依次代入约束条件左侧，求出数值，看是否适合对每个解，依次代入约束条件左侧，求出数值，看是否适合不等式条件，如某一条件不适合，同行以下各条件就不必再不等式条件，如某一条件不适合，同行以下各条件就不必再不等式条件，如某一条件不适合，同行以下各条件就不必再不等式条件，如某一条件不适合，同行以下各条件就不必再检查，因而就减少了运算次数。检查，因而就减少了运算次数。检

6、查，因而就减少了运算次数。检查，因而就减少了运算次数。在计算过程中，若遇到在计算过程中，若遇到z z值已超过条件值已超过条件右边的值，应改变右边的值，应改变条件条件，使右边值为迄今为止最大者，使右边值为迄今为止最大者，然后继续作。然后继续作。例如，当检查点例如，当检查点(0(0，0 0，1)1)时，因时，因z=5(z=5(3)3)，所以改进过滤条件，用所以改进过滤条件，用3x1-2x2+5x35 代替代替，继续进，继续进行。行。这种对过滤条件的改进，更可以减少计算量。这种对过滤条件的改进，更可以减少计算量。v再改进过滤条件，用再改进过滤条件，用3x3x1 1-2x-2x2 2+5x+5x3 3

7、88代替代替，再继续进，再继续进行。行。至至此此，z z值值已已不不能能改改进进，即即得得到到最最优优解解，解解答答如如前前，但但计算已简化。计算已简化。本例计算过程实际只作本例计算过程实际只作1616次运算。次运算。即求得最优解即求得最优解(x(x1 1，x x2 2，x x3 3)=(1)=(1，0 0，1),max z=81),max z=8注意：注意：一般常重新排列一般常重新排列x xi i的顺序使目标函数中的顺序使目标函数中x xi i的系数是递增的系数是递增(不不减减)的，在上例中，的，在上例中，改写改写 z=3xz=3x1 1-2x-2x2 2+5x+5x3 3=-2x=-2x2

8、 2+3x+3x1 1+5x+5x3 3因为因为-2-2，3 3，5 5是递增的，变量是递增的，变量(x(x2 2，x x1 1，x x3 3)也按下述顺序取也按下述顺序取值：值：(0(0，0 0，0)0)，(0(0，0 0，1)1)，(0(0，1 1，0)0)，(0(0，1 1，1)1)，这样，最优解容易比较早的发现。这样，最优解容易比较早的发现。再结合过滤条件的改进，更可使计算简化再结合过滤条件的改进，更可使计算简化步骤：步骤：(1)(1)、用试探法，求出一个可行解，以它的目标值作、用试探法，求出一个可行解，以它的目标值作为当前最好值为当前最好值Z Z0 0(2)(2)、增加过滤条件增加过

9、滤条件Z Z Z Z0 0(3)(3)、将、将x xi i 按按c ci i由小由小大排列。最小化问题反之。大排列。最小化问题反之。maxZ=3x1-2x2+5x3x1+2x2-x3 2 （1）x1+4x2+x3 4 （2）x1+x2 3 （3）4x2+x3 6 （4）x1,x2,x3为为0或或1解：解：1.观察得解观察得解(x1,x2,x3)=(1,0,0)，Z0=3 2.过滤条件过滤条件：3x1-2x2+5x3 3 3.将将(x1 x2 x3)(x2 x1 x3)点点(x2 x1 x3)目标值目标值 Z0 （1）（）（2）（）（3）（）（4）当前最好值当前最好值 (0,0,0)0 5 (0

10、,1,0)3 8 (1,0,0)-2 (1,0,1)3 (1,1,0)1 (1,1,1)6 最优解最优解 x=(1,0,1)T ，Z=8maxZ=-2x2+3x1+5x3x1+2x2 -x3 2 （1）x1+4x2+x3 4 （2）x1+x2 3 （3）4x2+x3 6 （4）指派问指派问题与匈牙利法题与匈牙利法指派问题的求解步骤：指派问题的求解步骤：指派问题的求解步骤：指派问题的求解步骤：1)变变换换指指派派问问题题的的系系数数矩矩阵阵(cij)为为(bij)，使使在在(bij)的的各各行行各各列列中都出现中都出现0元素，即元素，即 从从(cij)的每行元素都减去该行的最小元素；的每行元素都

11、减去该行的最小元素；再从所得新系数矩阵的每列元素中减去该列的最小元素。再从所得新系数矩阵的每列元素中减去该列的最小元素。2)进行试指派，以寻求最优解。进行试指派，以寻求最优解。在在(bij)中中找找尽尽可可能能多多的的独独立立0元元素素，若若能能找找出出n个个独独立立0元元素素，就就以以这这n个个独独立立0元元素素对对应应解解矩矩阵阵(xij)中中的的元元素素为为1，其其余余为为0，这就得到最优解。，这就得到最优解。指派问指派问题与匈牙利法题与匈牙利法找独立找独立0元素，常用的步骤为：元素，常用的步骤为：从只有一个从只有一个0元素的行开始，给该行中的元素的行开始，给该行中的0元素加圈，记作元素

12、加圈，记作。然后划去。然后划去 所在列的其它所在列的其它0元素，记作元素，记作；这表示该列所代表；这表示该列所代表的任务已指派完，不必再考虑别人了。依次进行到最后一行。的任务已指派完，不必再考虑别人了。依次进行到最后一行。从只有一个从只有一个0元素的列开始（画元素的列开始（画的不计在内），给该列中的的不计在内），给该列中的0元素加圈，记作元素加圈，记作；然后划去；然后划去 所在行的所在行的0元素，记作元素，记作 ，表示，表示此人已有任务，不再为其指派其他任务了。依次进行到最后一列。此人已有任务，不再为其指派其他任务了。依次进行到最后一列。若仍有没有划圈的若仍有没有划圈的0元素，且同行元素，且同

13、行(列列)的的0元素至少有两个，比元素至少有两个，比较这行各较这行各0元素所在列中元素所在列中0元素的数目，选择元素的数目，选择0元素少这个元素少这个0元素元素加圈加圈(表示选择性多的要表示选择性多的要“礼让礼让”选择性少的选择性少的)。然后划掉同行同。然后划掉同行同列的其它列的其它0元素。可反复进行，直到所有元素。可反复进行，直到所有0元素都已圈出和划掉为元素都已圈出和划掉为止。止。指派问指派问题与匈牙利法题与匈牙利法 若若 元素的数目元素的数目m 等于矩阵的阶数等于矩阵的阶数n（即：（即：mn），那么这，那么这指派问题的最优解已得到。若指派问题的最优解已得到。若m n,则转入下一步。则转入

14、下一步。3)用最少的直线通过所有用最少的直线通过所有0元素。其方法：元素。其方法：对没有对没有的行打的行打“”；对已打对已打“”的行中所有含的行中所有含元素的列打元素的列打“”；再对打有再对打有“”的列中含的列中含 元素的行打元素的行打“”；重复重复、直到得不出新的打直到得不出新的打号的行、列为止；号的行、列为止；对没有打对没有打号的行画横线，有打号的行画横线，有打号的列画纵线，这就得到覆盖号的列画纵线，这就得到覆盖所有所有0元素的最少直线数元素的最少直线数 l。注注：l 应应等等于于m，若若不不相相等等，说说明明试试指指派派过过程程有有误误，回回到到第第2步步，另另行行试试指指派派；若若 l

15、m n，表表示示还还不不能能确确定定最最优优指指派派方方案案，须须再再变变换换当当前前的的系系数矩阵，以找到数矩阵，以找到n个独立的个独立的0元素，为此转第元素，为此转第4步。步。指派问指派问题与匈牙利法题与匈牙利法4)变换矩阵变换矩阵(bij)以增加以增加0元素元素在没有被直线通过的所有元素中找出最小值，没有被直线在没有被直线通过的所有元素中找出最小值，没有被直线通过的所有元素减去这个最小元素；直线交点处的元素加上这个通过的所有元素减去这个最小元素；直线交点处的元素加上这个最小值。新系数矩阵的最优解和原问题仍相同。转回第最小值。新系数矩阵的最优解和原问题仍相同。转回第2步。步。指派问指派问题

16、与匈牙利法题与匈牙利法例例7 有一份中文说明书，需译成英、日、德、俄四种文字，有一份中文说明书，需译成英、日、德、俄四种文字，分别记作分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？如何分派任务，可使总时间最少？任务任务人员人员ABCD甲甲67112乙乙4598丙丙31104丁丁5982指派问指派问题与匈牙利法题与匈牙利法解：解：1）变换系数矩阵，增加变换系数矩阵，增加0元素。元素。52）试指派（找独立）试指派（找独立0元素

17、）元素）找到找到 3 个独立零元素个独立零元素 但但 m=3 n=4指派问指派问题与匈牙利法题与匈牙利法3）作最少的直线覆盖所有作最少的直线覆盖所有0元素元素 独立零元素的个数独立零元素的个数m等于最少等于最少直线数直线数l，即，即lm=3n=4；4）没有被直线通过的元素中选择最小值为）没有被直线通过的元素中选择最小值为1，变换系数矩阵，将没有被直线通，变换系数矩阵，将没有被直线通过的所有元素减去这个最小元素；直线交点处的元素加上这个最小值。得到新过的所有元素减去这个最小元素；直线交点处的元素加上这个最小值。得到新的矩阵，重复的矩阵，重复2）步进行试指派）步进行试指派指派问指派问题与匈牙利法题

18、与匈牙利法000 0 00试指派试指派 得到得到4个独立零元素，个独立零元素，所以最优解矩阵为：所以最优解矩阵为：即完成即完成4个任务的总时间最少为：个任务的总时间最少为：241+8=15指派问指派问题与匈牙利法题与匈牙利法练习练习 已知五人分别完成五项工作耗费如下表，求最已知五人分别完成五项工作耗费如下表，求最优指派方优指派方案。案。任务任务人员人员ABCDE甲甲759811乙乙9127119丙丙85468丁丁73696戊戊467511指派问指派问题与匈牙利法题与匈牙利法-1-2解：解：1）变换系数矩阵，增加）变换系数矩阵，增加0元素。元素。指派问指派问题与匈牙利法题与匈牙利法 2）试指派（

19、找独立）试指派（找独立0元素）元素）独立独立0元素的个数元素的个数l45，故画直线调整矩阵。，故画直线调整矩阵。指派问指派问题与匈牙利法题与匈牙利法 选择直线外的最小元素选择直线外的最小元素为为1；直线外元素减；直线外元素减1，直线交点元素加直线交点元素加1，其，其他保持不变。他保持不变。指派问指派问题与匈牙利法题与匈牙利法 l=m=4 n=5选择直线外最小元素为选择直线外最小元素为1，直线外元素减，直线外元素减1，直线，直线交点元素加交点元素加1，其他保持，其他保持不变，得到新的系数矩阵。不变，得到新的系数矩阵。指派问指派问题与匈牙利法题与匈牙利法 总费用为总费用为=5+7+6+6+4=28

20、=5+7+6+6+4=28注：此问题有多个最优解注：此问题有多个最优解指派问指派问题与匈牙利法题与匈牙利法 总费用为总费用为=8+9+4+3+4=28=8+9+4+3+4=28指派问指派问题与匈牙利法题与匈牙利法2.2.不平衡的指派问题不平衡的指派问题不平衡的指派问题不平衡的指派问题 当人数当人数m大于工作数大于工作数n时，加上时，加上mn项虚拟工作，项虚拟工作，例如：例如：当人数当人数m小于工作数小于工作数n时，加上时，加上nm个人，个人，例如例如指派问指派问题与匈牙利法题与匈牙利法3.3.一个人可做几件事的指派问题一个人可做几件事的指派问题一个人可做几件事的指派问题一个人可做几件事的指派问

21、题若某人可做几件事，则将该人化作相同的几个若某人可做几件事，则将该人化作相同的几个“人人”来接受指派，且费用系数来接受指派，且费用系数取值相同。取值相同。例如：丙可以同时任职例如：丙可以同时任职A和和C工作，求最优指派方案。工作，求最优指派方案。指派问指派问题与匈牙利法题与匈牙利法4.4.某事一定不能由某人做的指派问题某事一定不能由某人做的指派问题某事一定不能由某人做的指派问题某事一定不能由某人做的指派问题将该人做此事的效率系数取做足够大的数，可用将该人做此事的效率系数取做足够大的数，可用M表示。表示。练习练习 指派甲指派甲、乙、丙、丁四个人去完成、乙、丙、丁四个人去完成A、B、C、D、E五项

22、任五项任务。每个人完成各项任务的时间如表所示。由于任务数多于人数，务。每个人完成各项任务的时间如表所示。由于任务数多于人数，考虑任务考虑任务E必须完成，其他必须完成，其他4项中可任选项中可任选3项完成。试确定最项完成。试确定最优指优指派方派方案，使完成任务的总时间最少。案，使完成任务的总时间最少。任务任务人员人员ABCDE甲甲2529314237乙乙3938262033丙丙3427284032丁丁2442362345指派问指派问题与匈牙利法题与匈牙利法解解:1)这是不平衡的指派问题，首先转换为标准型，再用匈牙利这是不平衡的指派问题，首先转换为标准型，再用匈牙利法求解。法求解。2)由于任务数多于

23、人数，所以假定一名虚拟人，设为戊。因为工由于任务数多于人数，所以假定一名虚拟人，设为戊。因为工作作E必须完成，故设戊完成必须完成，故设戊完成E的时间为的时间为M（M为非常大的数），其为非常大的数），其余效率系数为余效率系数为0，则标准型的效率矩阵表示为：，则标准型的效率矩阵表示为：任务任务人员人员ABCDE甲甲2529314237乙乙3938262033丙丙3427284032丁丁2442362345戊戊0000M指派问指派问题与匈牙利法题与匈牙利法用匈牙利法求出最优指派方案为：用匈牙利法求出最优指派方案为：即甲即甲B，乙，乙D，丙，丙E，丁，丁A,任务任务C放弃。放弃。最少时间为最少时间为105。