整数规划的产生和发展报告课件.pptx

1、PPT模板下载：行业PPT模板：节日PPT模板：PPT素材下载：PPT背景图片：PPT图表下载：优秀PPT下载：PPT教程：Word教程：Excel教程：资料下载：PPT课件下载：范文下载：试卷下载：教案下载：整数规划报告第五章第五章 整数规划整数规划 引言v 什么是整数规划 在第4章中的线性规划问题，其设计变量都是连续变量，其最优解可以出现分数或小数。但当设计变量表示零件数、劳动力人数、设备的台数时，其取值则必须为非负整数，此时一般的线性规划求解方法就可能失效。我们称要求设计设计变量的部分分量或者全部分量取整数值变量的部分分量或者全部分量取整数值的最优化问题为整数规划问题v 整数规划的产生和

2、发展 整数规划（Integer Programming，简写为IP）和线性规划一样属于运筹学中数学规划的一个分支，其研究的问题包括整数线性规划和整数非线性规划 整数规划是从1958年由R.E.Gomory提出割平面法之后形成独立分支的。之后在该领域虽然也发展出诸如分枝定界法和割平面法等主流方法，但它仍是数学规划中稍弱的一个分支，目前的方法仅适合解中等规模的整数线性规划问题，而对于大规模整数线性规划和整数非线性规划问题，还没有成熟的办法v 整数规划的分类 纯整数规划：全部设计变量都取整数 混合整数规划：部分设计变量取整数 0-1规划：设计变量仅取0或l两个值典型的整数规划问题 v 装载问题 有一

3、列用于运货的火车，其最大承载能力为b。现有n种不同的货物p1,p2,pn可供装载，设每件pi的重量为ai，装载收费为ci(i=1,2,n)，则应采用何种装载方案能够使得该列火车载货的收入最大？设xj为列车上装载pj的数量，则xj必为非负整数，根据该货船最大可承载b吨货 物可知所有集装箱的重量之和必须b，故有约束条件：由对每个j种货物收费为cj，可知载货的总收入为：该例的目标即使得目标函数f最大化。综合上述分析可得如下整数规划问题：1nj jja xb=1nj jjfc x=11(1,2,.,)m axs.t.0,nj jinj jjjjnfc xa xbx=且取整数值典型的整数规划问题v 工厂

4、选址问题 某地区有m座铁矿A1,A2,Am，Ai每年的产量为ai(i=1,2,m)，该地区已有一个钢铁厂B0，每年铁的用量为p0，每年固定运营费用为r0。由于当地经济的发展，政府拟建立一个新的钢铁厂，于是今后该地区的m座铁矿将全部用于支持这两个钢铁厂的生产运营。现在有n个备选的厂址，分别为B1,B2,Bn，若在Bj(j=1,2,n)处建厂，则每年固定的运营费用为rj。由Ai向Bj每运送1t钢铁的运输费用为cij(i=1,2,m;j=0,1,n)。那么应当如何选择新厂厂址，铁矿所开采出来的铁矿石又当如何分配给两个钢铁厂，才能使每年的总费用（固定运营费用和煤的运费）最低？钢铁厂B0每年需要用铁p0

5、，而且今后该地区m座铁矿将全部用于支持这两个钢铁厂的生产，故新的钢铁厂每年用铁量p为该m座铁矿的总产量减去B0的用铁量：令设计变量为vi，若vi=1则表示选择Bi作为新厂厂址，否则vi=0：01miipap=-1(1,2,.,)iiiBvinB=作为新厂厂址不作为新厂厂址0典型的整数规划问题v 工厂选址问题 设xij为每年从Ai运往Bj的钢铁数量，于是每年的总费用为：由铁矿Ai运出的所有钢铁将等于铁矿Ai的产量ai 原钢铁厂B0钢铁的用量p0为m座铁矿为其供应，故其收量应当等于m座铁矿对分别对其供应量的总和，即：同样的，对于备选厂Bj，可知其钢铁的用量为p，且由m座铁矿供应，由于备选厂址只有一

6、座，故在p前面需要乘以系数vj，即代表如果选择Bj为备选厂址，则用铁矿，否则，则该厂不存在，不需要使用铁矿，此时，对应的xij将全部取零值，故：由Ai向Bj钢铁的运输量均为非负实数 备选的钢铁厂只有一处 0101mnnij ijj jijjfc xrvv=+邋0(1,2,.,)nijijxaim=001miixp=1(1,2,.,)mijjixpvjn=0(1,2,.,;0,1,.,)ijximjn蕹=11njjv=典型的整数规划问题v 工厂选址问题 根据如上分析，根据设计变量的取值规则，要么建厂取0，要么不建厂取1，同时该问题还要确定如果选择了厂址，应当如何分配m座铁矿对两个钢铁厂的钢铁供应

7、量xij，而该变量的取值为非负实数即可，故该问题为一混合整数规划问题，且为混合0-1规划，可以归纳为如下形式：0101000111m i ns.t.(1,2,.,)(1,2,.,)1(01)0(1,2,.,;0,1,.,)mnnij ijj jijjnijijmiimijjinjjjijfc xrvvxaimxpxpvjnvvximjn=+=邋取 或典型的整数规划问题v 背包问题 夫妇两人要赴A地进行长途旅行，需要整理行李，现有3个旅行包，其容积大小分别为10升、15升和20升，两人在列出物品清单后根据需要已经整理出了10个包装袋，其中一些包装袋中装的是必带物品，共有7件，其体积大小分别为4升

8、、3升、1.5升、2.5升、4.5升、7.6升和1.9升。尚有8个包装袋可带可不带，不带则可在A地购买，这些可选包装袋的容积和其对应物品在A地的价格如表所示。试根据上述信息给出一个合理的打包方案。在这个问题中，我们需要确定的是，选带哪几个可选的包装袋，且将必带物品和选带物品放到哪个旅行包中。为此我们设第i个包装袋是否放在第j个旅行包中，并以此作为设计变量。同时，设第i个包装袋的容积可以用wi(i=1,2,3,15)来表示，可选包装袋对应的价格用pi(i=8,9,10,15)来表示。由于第i个包装袋要么在第j个旅行包中，要么在要么不在，故设只取0和1，且表述如下：物品12345678容积2.54

9、5.54.83.71.67.54.5价格20501057555802001001(1,2,.,15;1,2,3)ijijxijij=包装袋 在旅行包 中0包装袋 不在旅行包 中典型的整数规划问题v 背包问题 由于每个旅行包的容积确定，故装入第j个旅行包中的所有包装袋的容积的总和必须小于第j个旅行包的容积，即需要满足约束条件：由于旅行袋中有7件为必带，故这7个包装袋必然在3个旅行包中的其一，设包装袋的编号为i，则在设计变量xi1、xi2和xi3中必有一个取值为1，另外两个取值为0，其和为1。根据上述分析，对于7件必带的包装袋必须满足如下约束：对于可选的包装袋，则其要么在某个旅行包中，要么不在旅行

10、包中，设包装袋的编号为i，如果它在某个旅行包中，则设计变量xi1、xi2和xi3取值之和为1，如果它不在旅行包之中，则设计变量xi1、xi2和xi3取值之和为0，故对于可选的包装袋必须满足如下约束：151(1,2,3)i ijjiw xrj=311(1,2,.,7)ijjxi=311(8,2.,15)ijjxi=典型的整数规划问题v 背包问题 我们的目标就是使得在到达A地之后，所买物品的价格最低，即不在旅行包中的包装袋的总价格最低，如果某包装袋i不在旅行包中，则有：故其价格可以用 来表示，故所有不在旅行包中的包装袋的价值f可表达如下 我们确定打包方案的原则就是使得 f 取得最小值，故综合以上分

11、析，该背包问题的数学模型为：310ijjx=311iijjpx=骣-桫153811iijijfpx=骣=-桫邋153811513131m i n1s.t.(1,2,3)1(1,2,.,7)1(8,2.,15)1,0(1,2.,15,1,2,3)iijiji ijjiijjijjijfpxw xrjxixixij=骣=-桫=邋整数规划问题的数学模型 v 一般形式 在整数规划中还有许多其他典型的问题，例如在第3章中提到的分派问题，还有旅行商问题、下料问题等，其问题均可以归结为如下的一般形式 上述形式是仿照线性规划中的标准型给出的，其中设计变量x为n维的列向量，c为n维的行向量，A为mn的矩阵，且A

12、行满秩，b为m维列向量。在模型中，(1)可以是最大化也可以是最小化，对于约束(2)，可以是等式的形式也可以是不等式的形式。对于对设计变量的约束(3)，如果要求x全部分量为整数，则为纯整数规划；如果要求x的部分分量为整数，则为混合整数规划，如果要求x分量的取值只能为0和1，则为0-1规划。m ax(1)s.t.(2)0,(3)f=cxcxA xbA xbx x且全部或者部分取整数值整数规划的求解 v 直观想法 既然整数规划问题的可行方案数目有限，则我们经过枚举比较枚举比较之后，总能求出最好方案，这种想法对于维数很低的整数规划问题行得通，但是随着设计变量维数的增加，该方法的计算量是不可想象的，因而

13、此种想法不可行。另一种想法更为直接，因为整数规划问题实际上是在线性规划问题的基础上增加了整数约束，因而是否可以考虑先忽略整数约束，解一个线性规划问题，然后用四舍五入法取得其整数解四舍五入法取得其整数解？但事实证明，这样经过四舍五入的结果甚至不是问题的可行解v 可行否 枚举法随着变量维数增加呈指数增长，不可行！四舍五入可能都不是可行解，不可行！12*1212*12m ax58915s.t.644 2 459451654,0,Tfxxxxxxfx x=+轾=+犏臌揶=+=x xx x且取整数值四舍五入后的解四舍五入后的解不是可行解！不是可行解！整数规划的求解v 求解思路 由上述分析可知，舍入法一般

14、是不可取的，当然如果对应线性规划的最优解恰好满足整数要求，则该解也是整数规划的最优解，那么何时才能满足此要求呢？我们直接给出一个结论：假设由整数规划问题除去整数要求之后得到的线性规划标准型中，等式假设由整数规划问题除去整数要求之后得到的线性规划标准型中，等式约束个数等于决策变量个数约束个数等于决策变量个数(m=n)，则此时的等式约束构成一个线性方程组，则此时的等式约束构成一个线性方程组Ax=b，如果，如果det(A)=1或或-1，则解，则解x一定是整数向量，当然这种情况在解决一定是整数向量，当然这种情况在解决实际问题的过程中一般还是比较少见的。实际问题的过程中一般还是比较少见的。对于整数规划问

15、题的解法，一般有利用分解技术的算法和不利用分解技术的算法 利用分解技术的算法有分枝定界法和针对0-1规划的隐枚举法 不利用分解技术的算法为割平面法和群论方法 针对特定的问题还有特定的简化方法，例如求解分派问题的匈牙利方法，等等。求解整数规划的理论基础v 利用分解技术求解整数规划中的几个概念 分解 对于整数规划问题P，令F(P)表示P的可行域。对问题P的子问题P1,Pm，若满足下述条件：则称P问题被分解成为子问题P1,Pm之和，最常用的方法就是两分法，例如若xj是P的0-1变量，则问题P可以按照条件xj=0和xj=1分解成两个问题之和。松弛 凡是放弃问题P的某些约束后所得到的问题Q都称为P的松弛

16、问题。通常的松弛方式是放弃设计变量的整数约束，若P是整数规划，则Q就是线性规划。由于对于P的任何松弛问题Q，都有 ，故问题P与其松弛问题Q之间的关系为：若Q没有可行解，则P也没有可行解；对于最大化的目标函数而言，P的最大值小于或者等于Q的最大值，对于最小化的目标函数而言，P的最小值大于或者等于Q的最小值；如果Q的一个最优解x是P的可行解，则x也是P的一个最优解。1()()()()(1,1,)miiijF PF PF PF Pimjmij=疲()()F PF Q求解整数规划的理论基础v 利用分解技术求解整数规划中的几个概念 探测 假设按照某种规则，已经将问题P分解称为子问题P1,Pm之和，Pi对

17、应的松弛问题为Qi。且问题需要最大化目标函数，则有如下结论：如果Qi没有可行解，则Pi也无可行解，因此可将Pi从P的分解表上删去；假设已知P的一个可行解x*，其对应的目标函数值为f*。若Qi的目标函数的最大值小于或者等于f*，则说明Pi中没有比x*更好的可行解，因此可将Pi从P的分解表上删去；如果Qi的最优解是Pi的可行解，则已求得Pi的最优解，故无须进一步考虑Pi，可从表上删去，若Pi的最优解比x*好，则以Pi的最优解代替x*如果分解表上各个Qi的目标函数值均不大于x*，则x*便是P的一个最优解v 求解整数规划的步骤 首先按照某种方式确定P的松弛问题Q，若Q无可行解则P也无可行解，若Q的最优

18、解为P的可行解，则也是P的最优解。若Q的最优解不是P的可行解，则要么以一种更好的方式确定松弛问题Q，继续探测P，要么将P分解成为几个子问题之和，然后逐个探测，当某个子问题已被探明时，就从表中删除，否则继续对子问题进行分解求解整数规划的分枝定界法 v 分枝定界法的思想 根据理论基础，若整数规划问题P除去整数约束的松弛问题Q为线性规划，则有如下几个推论 若Q无可行解，则P也一定无可行解 若Q的一个最优解是整数解，则这个解也是整数规划P的最优解 若Q的最优解不是整数解，则P的最优目标函数值不会好于Q的最优值。因此，Q的最优目标函数值是P的最优目标函数值的一个界，在最大化目标函数值时为上界，在最小化目

19、标函数值是下界 如果在求解过程中已经找到一个整数解，则最优整数解一定不会劣于该整数解，因此，它也是最优目标函数值的一个界，在最大化目标函数值时为下界，在最小化目标函数值是上界 如果用f表示Q的最优值，用fi表示已经找到的最佳整数解的最优值，f*为P的最优值，lb表示下界，ub表示上界，则对于最大化目标函数的问题，一定存在关系 ，而对于最小化目标函数的问题，则为 ，分枝定界法的思想就是不断降低上界，提高不断降低上界，提高下界下界，最后使得下界接近或者等于上界，通过这个方法来缩小搜索的范围，进而找到问题的最优整数解。*il bfffub=*il bfffub=求解整数规划的分枝定界法v 分枝定界法

20、的求解步骤 求解其松弛线性规划，如果得到整数解，该解即为整数规划的最优解。否则，所得线性规划的解可作为该问题最优整数解的初始上界，初始下界一般设为-。建立分枝树：在任何一个（子）问题中，从不满足整数要求的变量中选出一个进行处理，通过加入一对互斥的约束将一个（子）问题分枝成为两个受到进一步约束的子问题，并强迫不为整数的变量进一步逼近整数值，一次去掉两个整数之间的非整数域，缩小搜索的区域，由此，子问题若不满足整数要求则继续向下进行分枝，可以形成一个分枝树。定界与剪枝：通过不断的分枝和求解各个子问题，分枝定界法将不断修正上下界。上界通常由子问题的最大目标函数值确定，而下界则由已经得到的最优的整数解来

21、确定。求解任何一个（子）问题都有可能出现以下结果：无可行解，此时无需继续向下分枝；得到一个整数解，则不必继续向下分枝，如果该整数解是目前得到的最好的整数解，则被记录下来，并用它的值作为新的下界；得到一个非整数解，如果目标函数值大于剪枝界，则继续向下分枝，否则该子问题被剪枝 按照上述步骤搜索迭代，在每次搜索的过程中，每当下界被修改以后，都应检查所有的还没有求解过的子问题并剪去那些目标函数值小于新的下界的子问题，此时如果没有找到任何整数解，则该问题没有整数解；否则。搜索过程中已经得到的最优的整数解就是该问题的最优解。求解整数规划的分枝定界法v 说明 对于上述求解步骤中的第(4)步，特别说明如下：如

22、果在计算过程中已得到某一个分枝的整数最优解，其最优值为f0。而此时在其他分枝过程中，如果求得某一线性规划所得的目标函数值小于f0，即可停止该枝的计算。因为进一步求解的结果的最优值也只可能比f0更差，这也就是如何检查下界对分枝树进行剪如何检查下界对分枝树进行剪枝的原则枝的原则。求解整数规划的分枝定界法v 如何选择分枝的节点 深度优先搜索 先选择最后的还没有求解过的子问题并剪去那些目标函数值小于新下界的子问题。在搜索的过程中，如果某子节点的上界小于当前原问题的某一可行解的值，则将该子节点删去不再进行分枝。该方法可以较早的实现剪枝的过程，很快的搜索到分枝树的较底层找到一个整数解，且存储空间小，缺点就

23、是未顾很快的搜索到分枝树的较底层找到一个整数解，且存储空间小，缺点就是未顾及其他分枝，找到的整数解的质量未必高。及其他分枝，找到的整数解的质量未必高。广度优先搜索 始终选择由最大目标函数值的子问题继续向下分枝，在搜索的过程中，如果某子节点的上界小于当前原问题的某一可行解的值，则将该子节点删去不再进行分枝。因为它每次都以最大上界的子问题进行处理，故用该搜索方法找故用该搜索方法找到整数解的质量较高，缺点是该方法要在整个分枝树上搜索，故存储空间比深到整数解的质量较高，缺点是该方法要在整个分枝树上搜索，故存储空间比深度优先搜索大，求解时间也较长。度优先搜索大，求解时间也较长。预估法 利用一些先验知识和

24、相关技巧预先估计还未求解过的子问题的最好可能整数解，并选择最好预估值的子问题向下分枝，该方法是上述两种方法的折中折中选择。选择。求解整数规划的分枝定界法v 如何选择分枝变量 按照目标函数系数选择 选择目标函数中对应系数绝对值最大的设计变量进行分枝 按非整数变量选择 选择与整数值相差最大的非整数变量首先进行分枝 按人为给定的顺序选择 例如选择者按整数变量在问题中的相对重要性排序求解整数规划的分枝定界法v 算法描述Step1求P的松弛线性规划问题Q，若Q无可行解，则P也无可行解，算法结束；若其最优解符合整数条件，则找到最优解，算法结束，若不满足转(2)Step2按照分枝节点和分枝变量的原则选择不符

25、合整数约束条件的设计变量xi=bi，令bi为bi的整数部分（向下取整），构造两个互斥的约束条件xibi和xibi+1，形成两个整数规划子问题P1和P2，转Step3Step3求解P1和P2的松弛线性规划问题Q1和Q2，则根据如下情况进一步求解：Q1无可行解，Q2无可行解，则整数规划P无可行解，算法结束；Q1无可行解，Q2有整数解，则该解为P的最优解，算法按结束；Q1无可行解，Q2有非整数解，则对Q2进行分枝转Step2Q1有整数解，Q2有整数解，则较优的一个为P的最优解，算法结束；Q1有整数解且目标函数值优于Q2，Q2有非整数解，则Q1的整数解为P的最优解Q1有整数解，Q2有非整数解且目标函数

26、值优于Q1，则Q1停止分枝，其整数解为新的界，对Q2转Step2Q1无整数解，Q2也无整数解，可以按照设定的规则选取一枝先进行分枝计算，其中一枝若计算得到的最优解为整数解，且最优值优于另一枝，则所得的整数解就是P的最优解，无须对另一枝进行分枝；若得到的最优值劣于另一枝，则对另一枝进行分枝转Step2求解整数规划的分枝定界法v 求解整数规划问题P 首先求解P的松弛线性规划问题Q，可知其最优解为：，在最优解处取得的函数最大值为：fQ=4，此时上界为上界为4，由于xQ的两个分量均不为整数，故需要对问题P进行分枝，在此，人为取x1进行分枝，对xP1=1.5向下取整得1，故加上互斥的约束条件x11和x1

27、2，那么加入该组互斥条件的作用在于：排除了区间(1,2)之内的非整数解，缩小了搜索的范围；形成了整数规划P的两个子问题P1和P2121212212m ax421s.t.421121,0,fxxxxxxxx x=+-+且取整数值3522TQx轾=犏臌()1212121211211m ax421s.t.4211211,0,35122TQQfxxxxxxPxxx xxf=+-+轾=犏臌且取整数值松弛问题的最优解，()1212122211222m ax421s.t.4211212,0,37222TQQfxxxxxxPxxx xxf=+-+轾=犏臌且取整数值松弛问题的最优解，求解整数规划的分枝定界法 由

28、于现在已经存在两个子节点P1和P2，下一步选取哪个节点进行分枝需要采用合适的策略，在此我们采用广度优先搜索的方法，由于Q2的目标函数值较大，故对问题P2进行分枝，加入互斥的约束x21和x22，形成P2的两个子问题P3和P4。当加入新的约束之后，有可能出现三种情况：(1)新加入的条件和原问题的条件独立，即互不影响，此时直接将约束加入到问题中；(2)新加入的条件和原问题的条件相矛盾，此时新的问题无可行解；(3)新加入的约束和原约束存在交集，则此时选择其交集作为作为新问题的约束条件。()12121223211233m ax421s.t.42112112,0,913144TQQfxxxxxxxPxxx

29、 xxf=+-+轾=犏臌且取整数值松弛问题的最优解，()12121242112444m ax421s.t.421122,0,fxxxxxxPxxx xQPP=+-+且取整数值松弛问题无可行解，故也无可行解，停止对的分枝求解整数规划的分枝定界法 由于Q3的目标函数值fQ3大于Q1的目标函数值fQ1，故下一步对P3进行分枝，加入互斥的约束x12和x13，形成P3的两个子问题P5和P6。现在我们已经在P2的分枝上找到了一组整数解，现在比较fQ5和fQ1，由于现在已有整数解的目标函数值fQ5大于fQ1，而P1的最优目标函数值不会大于fQ1，故该分枝的解不会对目标函数值有任何的改善，所以对P1进行剪枝，

30、即停止对P1的向下分枝，我们已经搜索到了的最优解。这里需要注意注意的，如果我们发现已经求得整数解的最优值fQ5要小于fQ1，则P的上界还并未确定，于是问题还需要继续分解下去。()12121225211255m ax421s.t.4211211=2,0,213TQQfxxxxxxxPxxx xxf=+-+轾=犏臌且取整数值松弛问题的最优解，()12121226211266m ax421s.t.42112113,0,fxxxxxxxPxxx xPP=+-+且取整数值无可行解，停止对的分枝求解整数规划的分枝定界法v 上述求解过程示意图求解0-1规划的隐枚举法 v 隐枚举法的提出 由E Balas在1

31、965年提出的，该方法只检查一部分变量组合，在这过程中根据已有信息自动舍弃许多不可能成为最优解的组合以求得最优解，从而大大减少了工作量，隐枚举法只需比较目标函数在一小部分组合点上的取值大小就能求得最优解和最优值。v 隐枚举法的思想 隐枚举法可以看作是分枝定界法的特殊情况，在求解的过程中，它不需要求解其松弛线性规划问题，利用变量只能取0或1对问题进行分枝。其思路是先将0-1规划问题转化为既定的标准型标准型，该标准型一般是要最小化目标函数的值，在此前提下，首先令全部变量取全部变量取0值值（当求最大值时，令全部变量取1值），检验解是否满足约束条件，若均满足，已得最优解；若不全满足，则令一个变量分枝取

32、值为0或1，该分枝变量称为固定变量，将模型分成两个子模型，其余未被指定取值的变量称为自由变量，通过这种方法，依次指定一些变量为1，直至得到一个可行解，并将它作为目前最好的可行解并记录下来。此后，经过几次检验后，或者停止分枝，或者将另一个自由变量转为固定变量，令其值为0或l，如此继续进行，依次试探变量等于0或l的某些组合，使目前最好的可行解不断逼近最优值可行解不断逼近最优值，直至没有自由变量或全部子问题停止分枝为止，就求出了0-1规划的最优解，求解0-1规划的隐枚举法v 取试探解的理由 为什么从全0作出初始的试探解，这是因为0-1规划的标准型要求对目标函数求最小值，而对于最小化目标函数的问题，由

33、于在后面我们会提到0-1规划标准型中cj0，故因此自由变量为0与固定变量组成的子模型能够使得目标函数值最小。同理，如果不用标准型求解，例如对目标函数求最大值的问题，则是将全1作为初始的试探解进行分枝计算v 隐枚举法和穷举法的不同 隐枚举法和穷举法不同，穷举法需要将所有可行的变量组合逐个列举，而隐枚举法通过试探、分析和判断，排除了许多变量组合作为最优解的可能性。也就是说，它们被隐含枚举了，这也是称其为隐枚举法的原因v 隐枚举法的实质 从算法描述可以看出，隐枚举法的实质也是分枝定界法，隐枚举法在求解过程中与一般的分枝定界法不同之处只在于在分枝产生子问题时变量被固定为0或1，而不是两个范围之值的形式

34、。求解0-1规划的隐枚举法v 隐枚举法的0-1规划标准型 v 非标准型的标准化 若原问题为求max f，则可令f=-f 将问题转化为min f。或者不改变求最值的属性，将全1作为0-1规划的初始试探解 当某个系数cji ij jjijfc xc xc=+求解0-1规划的隐枚举法v 在用隐枚举法进行设计变量分枝的时候，同样面临选取分枝节点和分枝变量的问题，在选择分枝节点时，如果没有先验考察，则我们常按照目标函数中设计变量的系数从小到大排列进行顺序分枝（如果是求最大值，则按照从大到小的顺序）。除此之外，还可以按照自然序或者人为设定的序列选取。求解0-1规划的隐枚举法v 隐枚举法的算法描述 (1)将

35、P转化成为标准型 (2)令所有设计变量均为自由变量，初始试探解为x=0，检验该解是否为可行解，如果为可行解，则x=0为P的最优解，算法结束。否则，转(3)；(3)按照既定的法则选取一个自由变量xk，将其转化为固定变量进行分枝，加入互 斥的条件xk=0和xk=1，将P分为两个子问题，其他的自由变量取值不变，仍为0。然后对针对各个分枝进行试探，转(4);(4)检查已有的子问题，如果有某一个子问题满足下列条件之一，就可对该子问题 进行剪枝，即该子问题停止向下分枝，可以在分枝树中用相应的符号来表示，例如等。此时继续检查其他子问题，转(3);试探解为自由变量均取0值、固定变量取设定值，若满足所有约束条件

36、，则为可行解，该解对应的目标函数值为P的目标函数值的一个上界，同时该子问题停止向下分枝；若该子问题所有试探解均不是可行解，即自由变量任取0或1时，都不能满足某一个或者多个约束条件，则该子问题无可行解，也停止向下分枝；设自由变量均取0值与固定变量的值一起代入目标函数，得到的目标值为f，此时对应的自由变量的系数为列向量c，若f与c中任一分量的和大于已经记录的上界中的最小值，则说明在该子问题中固定任何自由试探解不是P的可行解，且此时所有变量均已设为固定变量，则该子问题也应该被剪枝，停止向下分枝。变量都不可能对P的最优值有所改善，已无更好的可行解，则该子问题被剪枝，停止向下分枝；求解0-1规划的隐枚举

37、法v 隐枚举法的算法描述（续）(5)直到所有子问题检查完毕，转(6)(6)在探明所有的分枝之后算法终止。比较记录下来的可行解的上界，其中最小者 所对应的可行解即为P的最优解，相应的目标函数值即为最优目标值，如果该 问题没有记录任何上界，则说明P无可行解，即该0-1规划无解。求解0-1规划的隐枚举法v 求解0-1规划P (1)化为标准型 (2)令所有设计变量为0，试探解x=0 0 0 0T不是P的可行解，需要分枝 (3)按照目标函数中各设计变量的系数从大到小的顺序来选择分枝固定变量，即以 x1、x4、x3、x2的顺序设置固定变量进行问题的试探1234123412341234423m ax2068

38、9s.t.10652197224112101201(1,2,3,4)ifxxxxxxxxxxxxxxxxxxxxi=+=或1234123412341234234m i n20689s.t.106524722442102101(1,2,3,4)ifxxxxxxxxxxxxxxxxxxxxi=+-+-=或求解0-1规划的隐枚举法 首先以x1作为固定变量，加入互斥的条件x1=1和x1=0将P分枝成为两个子问题P1和P2。下面对子问题进行探查。P1的试探解为xP1=1 0 0 0T，它是P的可行解，此时目标函数值为fP1=20，将其记录下来，作为P的一个上界。此时，对子问题P1进行剪枝，停止向下分枝。

39、此时P1已经探明。P2与P相同，故xP2为不可行解，以x4作为固定变量，加入互斥的条件x4=1和x4=0将P2分枝成为两个子问题P3和P4。P3的试探解为xP3=0 0 0 1T为不可行解。P4与P相同，故xP4为不可行解，两个问题都需要继续分枝，以x3作为固定变量，加入互斥的条件x3=1和x3=0，将P3分枝成为两个子问题P5和P6，将P4分枝成为两个子问题P7和P8。P5的试探解为xP5=0 0 1 1T为P的可行解，此时目标函数值为fP5=17，此时对应的自由变量为x2，x2对应的系数为c2=6，而此时记录下来的P的上界为fP1=20，由fP5+c2fP1，故停止向下分枝。按照上述方法不

40、断试探，最后可得所有可行解中，P9所对应的xP9=0 1 0 1T所取得的目标函数值最小为fP9=15，故xP9为P的最优解。求解过程示意图如下一页所示。求解0-1规划的隐枚举法v 求解过程示意图求解分派问题的匈牙利算法 v 匈牙利算法的应用对象 用以解决分派问题 分派问题是一种特殊形式的整数规划。该问题可以总结为，有n项任务需要n个人分别去完成，每个人只能完成其中的一项，而每项工作也只能由一个人完成，在问题中会以各种形式给出各个人的专长和工作效率，需要求解的问题是考虑分配哪个人去完成哪项任务才能使得总效率最高或者花费的总时间最短。v 匈牙利算法的提出 由于分派问题属于0-1规划，故我们可以用

41、隐枚举法进行求解，但是鉴于上述问题的特殊性，可以有更简便的方法求解此类问题，由于这种方法是基于匈牙利数学家狄柯尼格（D Knig）证明的两个定理而发展的，故称之为匈牙利法。求解分派问题的匈牙利算法v 匈牙利算法的0-1规划标准型 匈牙利算法是解决最优模型可归结为与分派问题结构一致的最优化问题的有效算法，那么首先回顾一下分派问题的数学模型，假设由第i个人完成第j项工作的时间为Eij，又设问题中的设计变量为xij，其意义如下：则分派问题的标准型为：需要注意的是，标准型中要求的是最小化最小化目标函数的值，且对应于各设计变量的系数均不小于零系数均不小于零。这是应用匈牙利算法的前提条件。10ijijij

42、x=当指派第 个人去完成第 个任务时当不指派第 个人去完成第 个任务时1111m i ns.t.1(1,2,.,)1(1,2,.,)01(1,2,.,;1,2,.,)nnij ijijnijjnijiijfE xxinxjnxin jn=邋或求解分派问题的匈牙利算法v 非标准型的标准化 目标函数中设计变量xmn对应的系数为负数Emn(,)(,)ij ijm nm nm nijm nfE xExE=+11m axnnij ijijfE x=邋ijijFME=-m ax()(1,2,.,;1,2,.,)ijMEin jn=()111111nnnnnnij ijijijij ijijijijfF x

43、MExnME x=-=-邋邋邋fnMf=-求解分派问题的匈牙利算法v 匈牙利算法的基本思想 在分派问题的数学模型中，目标函数的系数可以写成nn维的矩阵形式，我们可以用效率矩阵E来表示这组参量：而匈牙利法就是通过对效率矩阵E的处理来获得分派问题的最优解。在匈牙利法中，要求矩阵E的所有元素均为非负，即Eij0。其基本的思想就是如果在矩阵E中存在一组（n个）位于不同行且不同列的零元素，则最优方案就是令对应于这些零元素位置的xij=1，其他位置的xij=0。但是很显然的，我们建立的分派模型的效率矩阵E中几乎没有零元素，要实现上述设想就必须找到合适的方法对矩阵E进行变换，来获得这一组位于不同行且不同列的

44、零元素。111212122212nnnnnnEEEEEEEEE轾犏犏犏=犏犏犏犏犏臌E ELLMMOML求解分派问题的匈牙利算法v 匈牙利算法的理论基础 引理1：如果将效率矩阵E的第i行每个元素减去一个常数ui，将第j列中每个元 素减去一个常数vj，得到新的效率矩阵F，其第i行第j列的元素为Fij=aij-ui-vj，则分别对应于E和F的两个分派问题的最优解等价，其最优值相差 推论1：如果将效率矩阵E的每一行（或每一列）各元素分别减去该行（或该列）的最小元素，由此得到的新的效率矩阵F，则分别对应于E和F的两个分派问题的最优解等价 引理2：若矩阵E的元素可以分成“0”元素和“非0”元素两部分，则

45、覆盖所有“0”元素的最少直线（将直线上的元素全部划去之后矩阵就不再有“0”元素，这样所需直线数的最小值）等于位于不同行且不同列的“0”元素的最大个数。根据上面的结论，用匈牙利法求解分派问题的原理即通过对原效率矩阵E各行各列元素的同加或者同减运算，构造出等价最优解的效率矩阵F，且F的所有元素非负且具有n个不同行且不同列的“0”元素。这样，n个“0”元素所对应的人做对应的工作就是分派问题的最优解11nnijijuv=+邋求解分派问题的匈牙利算法v用匈牙利算法求解第一步，使得每一行和每一列都出现0元素将E的每行元素减去该行中的最小元素，使得每一行至少出现一个0元素；将所得矩阵的每列元素减去该列中的最

46、小元素，使得每一列都至少出现一个0元素如果某行或者某列已经有零元素，则不必再减 对例题中的E，操作如下：44114141m i ns.t.1(1,2,3,4)1(1,2,3,4)01ij ijijijjijiijfE xxixjx=邋或20123326221529232113312422163223轾犏犏犏=犏犏犏犏臌E E(I)(II)2012332680211420772215292370148100121133124801811204422163223601670020轾轾轾犏犏犏犏犏犏犏犏犏犏犏犏犏犏犏犏犏犏犏犏犏臌臌臌uuuuuruuuuuu r求解分派问题的匈牙利算法 第二步，最优

47、性检验，进行试指派，即找出不同行不同列的0元素(I)给只有一个0元素的行中的0打上括号，记作(0)，并划去与其同列的其余0元素，记作；(II)给只有一个0元素的列中的0打上括号，记作(0)，并划去与其同行的其余0元素，记作；(III)反复进行(I)和(II)，直至所有的0都被标记为止；(IV)若仍有没有被标记的0元素，则可从剩余的0元素最少的行（列）开始，选择0元素少的那列（行）的0元素加括号（表示选择性多的要礼让选择性少的）。然后，划去同行同列的其它0元素，反复进行，直到所有0元素都已被标记为止。(V)若(0)元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已经找到，若mn，转下一步(I

48、)(II)2(0)7720772(0)7710011011(0)1204424424400200202(0)轾轾轾犏犏犏犏犏犏哪犏犏犏犏犏犏哪犏犏犏犏犏犏犏犏犏哪犏臌臌臌uuuuuruuuuuu r求解分派问题的匈牙利算法第三步，矩阵变换作能覆盖所有0元素的最少直线(a)对没有(0)的行标记“*”；(b)对标记“*”行上含有0元素的列标记“*”；(c)对标记“*”列上有(0)的行标记“*”(d)重复(b)(c)直到无法标记“*”为止(e)对标记“*”的列画纵线，未标记“*”的行画横线，这就是能覆盖所有0元素的最少直线移动0元素在未被划去的元素中找出最小元素s，将其作为矩阵变换的调整量；将标记“

49、*”行的所有元素都减去s将标记“*”列的所有元素都加上s 结果将得到一个新的效率矩阵，转第二步。(a)(b)(c)2(0)772(0)772(0)772(0)77*1(0)11(0)11(0)11(0)1244244*244*244*2(0)2(0)2(0)2(0)*求解分派问题的匈牙利算法 对于本例的示例矩阵，未被划去的元素中最小者为2，故首先将第1行和第3行减去2，然后将第2列加上2，获得新的效率矩阵：返回第二步，即尝试在上述矩阵中找到不同行且不同列的n个0元素(b)(c)005520770255100110011001002220440222002000200020-轾轾轾犏犏犏犏犏犏犏

50、犏犏犏犏犏-犏犏犏犏犏犏犏犏犏臌臌臌uuuuuu ruuuuur12(0)551(0)1:(0)22005510012(0)0022(0)5500201(0)1:(0)222(0)MM扉涅犏犏犏犏犏轾犏犏犏犏哪犏犏臌犏槟犏犏犏犏犏犏臌犏犏 犏犏哪犏 铍试指派求解分派问题的匈牙利算法v 由以上求解结果，可以知道有两种最优的指派方式，相应的分派方案 1号成员完成2号任务，2号完成3号任务，3号完成1号任务，4号完成4号任务；1号完成1号任务，2号完成3号任务，3号完成2号任务，4号完成4号任务v 最优方案耗时M1：f=21+12+29+23=85M2：f=20+13+29+23=85 一般整数规划