整数规划 学习.pptx

《整数规划 学习.pptx》由会员分享，可在线阅读，更多相关《整数规划 学习.pptx（82页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、引言什么是整数规划在第4章中的线性规划问题，其设计变量都是连续变量，其最优解可以出现分数或小数。但当设计变量表示零件数、劳动力人数、设备的台数时，其取值则必须为非负整数，此时一般的线性规划求解方法就可能失效。我们称要求设计变量的部分分量或者全部分量取整数值的最优化问题为整数规划问题整数规划的产生和发展整数规划（Integer Programming，简写为IP）和线性规划一样属于运筹学中数学规划的一个分支，其研究的问题包括整数线性规划和整数非线性规划整数规划是从1958年由R.E.Gomory提出割平面法之后形成独立分支的。之后在该领域虽然也发展出诸如分枝定界法和割平面法等主流方法，但它仍是数

2、学规划中稍弱的一个分支，目前的方法仅适合解中等规模的整数线性规划问题，而对于大规模整数线性规划和整数非线性规划问题，还没有成熟的办法整数规划的分类纯整数规划：全部设计变量都取整数混合整数规划：部分设计变量取整数0-1规划：设计变量仅取0或l两个值第1页/共82页典型的整数规划问题 装载问题 有一列用于运货的火车，其最大承载能力为b。现有n种不同的货物p1,p2,pn可供装载，设每件pi的重量为ai，装载收费为ci(i=1,2,n)，则应采用何种装载方案能够使得该列火车载货的收入最大？设xj为列车上装载pj的数量，则xj必为非负整数，根据该货船最大可承载b吨货 物可知所有集装箱的重量之和必须b，

3、故有约束条件：由对每个j种货物收费为cj，可知载货的总收入为：该例的目标即使得目标函数f最大化。综合上述分析可得如下整数规划问题：第2页/共82页典型的整数规划问题工厂选址问题 某地区有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;

4、j=0,1,n)。那么应当如何选择新厂厂址，铁矿所开采出来的铁矿石又当如何分配给两个钢铁厂，才能使每年的总费用（固定运营费用和煤的运费）最低？钢铁厂B0每年需要用铁p0，而且今后该地区m座铁矿将全部用于支持这两个钢铁厂的生产，故新的钢铁厂每年用铁量p为该m座铁矿的总产量减去B0的用铁量：令设计变量为vi，若vi=1则表示选择Bi作为新厂厂址，否则vi=0：第3页/共82页典型的整数规划问题工厂选址问题 设xij为每年从Ai运往Bj的钢铁数量，于是每年的总费用为：由铁矿Ai运出的所有钢铁将等于铁矿Ai的产量ai 原钢铁厂B0钢铁的用量p0为m座铁矿为其供应，故其收量应当等于m座铁矿对分别对其供应

5、量的总和，即：同样的，对于备选厂Bj，可知其钢铁的用量为p，且由m座铁矿供应，由于备选厂址只有一座，故在p前面需要乘以系数vj，即代表如果选择Bj为备选厂址，则用铁矿，否则，则该厂不存在，不需要使用铁矿，此时，对应的xij将全部取零值，故：由Ai向Bj钢铁的运输量均为非负实数 备选的钢铁厂只有一处 第4页/共82页典型的整数规划问题工厂选址问题 根据如上分析，根据设计变量的取值规则，要么建厂取0，要么不建厂取1，同时该问题还要确定如果选择了厂址，应当如何分配m座铁矿对两个钢铁厂的钢铁供应量xij，而该变量的取值为非负实数即可，故该问题为一混合整数规划问题，且为混合0-1规划，可以归纳为如下形式

6、：第5页/共82页典型的整数规划问题背包问题 夫妇两人要赴A地进行长途旅行，需要整理行李，现有3个旅行包，其容积大小分别为10升、15升和20升，两人在列出物品清单后根据需要已经整理出了10个包装袋，其中一些包装袋中装的是必带物品，共有7件，其体积大小分别为4升、3升、1.5升、2.5升、4.5升、7.6升和1.9升。尚有8个包装袋可带可不带，不带则可在A地购买，这些可选包装袋的容积和其对应物品在A地的价格如表所示。试根据上述信息给出一个合理的打包方案。在这个问题中，我们需要确定的是，选带哪几个可选的包装袋，且将必带物品和选带物品放到哪个旅行包中。为此我们设第i个包装袋是否放在第j个旅行包中，

7、并以此作为设计变量。同时，设第i个包装袋的容积可以用wi(i=1,2,3,15)来表示，可选包装袋对应的价格用pi(i=8,9,10,15)来表示。由于第i个包装袋要么在第j个旅行包中，要么在要么不在，故设只取0和1，且表述如下：物品12345678容积2.545.54.83.71.67.54.5价格2050105755580200100第6页/共82页典型的整数规划问题背包问题 由于每个旅行包的容积确定，故装入第j个旅行包中的所有包装袋的容积的总和必须小于第j个旅行包的容积，即需要满足约束条件：由于旅行袋中有7件为必带，故这7个包装袋必然在3个旅行包中的其一，设包装袋的编号为i，则在设计变量

8、xi1、xi2和xi3中必有一个取值为1，另外两个取值为0，其和为1。根据上述分析，对于7件必带的包装袋必须满足如下约束：对于可选的包装袋，则其要么在某个旅行包中，要么不在旅行包中，设包装袋的编号为i，如果它在某个旅行包中，则设计变量xi1、xi2和xi3取值之和为1，如果它不在旅行包之中，则设计变量xi1、xi2和xi3取值之和为0，故对于可选的包装袋必须满足如下约束：第7页/共82页典型的整数规划问题背包问题 我们的目标就是使得在到达A地之后，所买物品的价格最低，即不在旅行包中的包装袋的总价格最低，如果某包装袋i不在旅行包中，则有：故其价格可以用 来表示，故所有不在旅行包中的包装袋的价值f

9、可表达如下 我们确定打包方案的原则就是使得 f 取得最小值，故综合以上分析，该背包问题的数学模型为：第8页/共82页整数规划问题的数学模型 一般形式 在整数规划中还有许多其他典型的问题，例如在第3章中提到的分派问题，还有旅行商问题、下料问题等，其问题均可以归结为如下的一般形式 上述形式是仿照线性规划中的标准型给出的，其中设计变量x为n维的列向量，c为n维的行向量，A为mn的矩阵，且A行满秩，b为m维列向量。在模型中，(1)可以是最大化也可以是最小化，对于约束(2)，可以是等式的形式也可以是不等式的形式。对于对设计变量的约束(3)，如果要求x全部分量为整数，则为纯整数规划；如果要求x的部分分量为

10、整数，则为混合整数规划，如果要求x分量的取值只能为0和1，则为0-1规划。第9页/共82页整数规划的求解 直观想法既然整数规划问题的可行方案数目有限，则我们经过枚举比较之后，总能求出最好方案，这种想法对于维数很低的整数规划问题行得通，但是随着设计变量维数的增加，该方法的计算量是不可想象的，因而此种想法不可行。另一种想法更为直接，因为整数规划问题实际上是在线性规划问题的基础上增加了整数约束，因而是否可以考虑先忽略整数约束，解一个线性规划问题，然后用四舍五入法取得其整数解？但事实证明，这样经过四舍五入的结果甚至不是问题的可行解可行否枚举法随着变量维数增加呈指数增长，不可行！四舍五入可能都不是可行解

11、，不可行！四舍五入后的解不四舍五入后的解不是可行解！是可行解！第10页/共82页整数规划的求解求解思路由上述分析可知，舍入法一般是不可取的，当然如果对应线性规划的最优解恰好满足整数要求，则该解也是整数规划的最优解，那么何时才能满足此要求呢？我们直接给出一个结论：假设由整数规划问题除去整数要求之后得到的线性规划标准型中，等式约束个数等于决策变量个数(m=n)，则此时的等式约束构成一个线性方程组Ax=b，如果det(A)=1或-1，则解x一定是整数向量，当然这种情况在解决实际问题的过程中一般还是比较少见的。对于整数规划问题的解法，一般有利用分解技术的算法和不利用分解技术的算法利用分解技术的算法有分

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

13、性规划。由于对于P的任何松弛问题Q，都有 ，故问题P与其松弛问题Q之间的关系为：若Q没有可行解，则P也没有可行解；对于最大化的目标函数而言，P的最大值小于或者等于Q的最大值，对于最小化的目标函数而言，P的最小值大于或者等于Q的最小值；如果Q的一个最优解x是P的可行解，则x也是P的一个最优解。第12页/共82页求解整数规划的理论基础利用分解技术求解整数规划中的几个概念探测 假设按照某种规则，已经将问题P分解称为子问题P1,Pm之和，Pi对应的松弛问题为Qi。且问题需要最大化目标函数，则有如下结论：如果Qi没有可行解，则Pi也无可行解，因此可将Pi从P的分解表上删去；假设已知P的一个可行解x*，其

14、对应的目标函数值为f*。若Qi的目标函数的最大值小于或者等于f*，则说明Pi中没有比x*更好的可行解，因此可将Pi从P的分解表上删去；如果Qi的最优解是Pi的可行解，则已求得Pi的最优解，故无须进一步考虑Pi，可从表上删去，若Pi的最优解比x*好，则以Pi的最优解代替x*如果分解表上各个Qi的目标函数值均不大于x*，则x*便是P的一个最优解求解整数规划的步骤首先按照某种方式确定P的松弛问题Q，若Q无可行解则P也无可行解，若Q的最优解为P的可行解，则也是P的最优解。若Q的最优解不是P的可行解，则要么以一种更好的方式确定松弛问题Q，继续探测P，要么将P分解成为几个子问题之和，然后逐个探测，当某个子

15、问题已被探明时，就从表中删除，否则继续对子问题进行分解第13页/共82页求解整数规划的分枝定界法 分枝定界法的思想根据理论基础，若整数规划问题P除去整数约束的松弛问题Q为线性规划，则有如下几个推论若Q无可行解，则P也一定无可行解若Q的一个最优解是整数解，则这个解也是整数规划P的最优解若Q的最优解不是整数解，则P的最优目标函数值不会好于Q的最优值。因此，Q的最优目标函数值是P的最优目标函数值的一个界，在最大化目标函数值时为上界，在最小化目标函数值是下界如果在求解过程中已经找到一个整数解，则最优整数解一定不会劣于该整数解，因此，它也是最优目标函数值的一个界，在最大化目标函数值时为下界，在最小化目标

16、函数值是上界 如果用f表示Q的最优值，用fi表示已经找到的最佳整数解的最优值，f*为P的最优值，lb表示下界，ub表示上界，则对于最大化目标函数的问题，一定存在关系 ，而对于最小化目标函数的问题，则为 ，分枝定界法的思想就是不断降低上界，提高下界，最后使得下界接近或者等于上界，通过这个方法来缩小搜索的范围，进而找到问题的最优整数解。第14页/共82页求解整数规划的分枝定界法分枝定界法的求解步骤 求解其松弛线性规划，如果得到整数解，该解即为整数规划的最优解。否则，所得线性规划的解可作为该问题最优整数解的初始上界，初始下界一般设为-。建立分枝树：在任何一个（子）问题中，从不满足整数要求的变量中选出

17、一个进行处理，通过加入一对互斥的约束将一个（子）问题分枝成为两个受到进一步约束的子问题，并强迫不为整数的变量进一步逼近整数值，一次去掉两个整数之间的非整数域，缩小搜索的区域，由此，子问题若不满足整数要求则继续向下进行分枝，可以形成一个分枝树。定界与剪枝：通过不断的分枝和求解各个子问题，分枝定界法将不断修正上下界。上界通常由子问题的最大目标函数值确定，而下界则由已经得到的最优的整数解来确定。求解任何一个（子）问题都有可能出现以下结果：无可行解，此时无需继续向下分枝；得到一个整数解，则不必继续向下分枝，如果该整数解是目前得到的最好的整数解，则被记录下来，并用它的值作为新的下界；得到一个非整数解，如

18、果目标函数值大于剪枝界，则继续向下分枝，否则该子问题被剪枝按照上述步骤搜索迭代，在每次搜索的过程中，每当下界被修改以后，都应检查所有的还没有求解过的子问题并剪去那些目标函数值小于新的下界的子问题，此时如果没有找到任何整数解，则该问题没有整数解；否则。搜索过程中已经得到的最优的整数解就是该问题的最优解。第15页/共82页求解整数规划的分枝定界法说明对于上述求解步骤中的第(4)步，特别说明如下：如果在计算过程中已得到某一个分枝的整数最优解，其最优值为f0。而此时在其他分枝过程中，如果求得某一线性规划所得的目标函数值小于f0，即可停止该枝的计算。因为进一步求解的结果的最优值也只可能比f0更差，这也就

19、是如何检查下界对分枝树进行剪枝的原则。第16页/共82页求解整数规划的分枝定界法如何选择分枝的节点 深度优先搜索 先选择最后的还没有求解过的子问题并剪去那些目标函数值小于新下界的子问题。在搜索的过程中，如果某子节点的上界小于当前原问题的某一可行解的值，则将该子节点删去不再进行分枝。该方法可以较早的实现剪枝的过程，很快的搜索到分枝树的较底层找到一个整数解，且存储空间小，缺点就是未顾及其他分枝，找到的整数解的质量未必高。广度优先搜索 始终选择由最大目标函数值的子问题继续向下分枝，在搜索的过程中，如果某子节点的上界小于当前原问题的某一可行解的值，则将该子节点删去不再进行分枝。因为它每次都以最大上界的

20、子问题进行处理，故用该搜索方法找到整数解的质量较高，缺点是该方法要在整个分枝树上搜索，故存储空间比深度优先搜索大，求解时间也较长。预估法 利用一些先验知识和相关技巧预先估计还未求解过的子问题的最好可能整数解，并选择最好预估值的子问题向下分枝，该方法是上述两种方法的折中选择。第17页/共82页求解整数规划的分枝定界法如何选择分枝变量 按照目标函数系数选择 选择目标函数中对应系数绝对值最大的设计变量进行分枝按非整数变量选择 选择与整数值相差最大的非整数变量首先进行分枝按人为给定的顺序选择 例如选择者按整数变量在问题中的相对重要性排序第18页/共82页求解整数规划的分枝定界法算法描述Step1求P的

21、松弛线性规划问题Q，若Q无可行解，则P也无可行解，算法结束；若其最优解符合整数条件，则找到最优解，算法结束，若不满足转(2)Step2按照分枝节点和分枝变量的原则选择不符合整数约束条件的设计变量xi=bi，令bi为bi的整数部分（向下取整），构造两个互斥的约束条件xibi和xibi+1，形成两个整数规划子问题P1和P2，转Step3Step3求解P1和P2的松弛线性规划问题Q1和Q2，则根据如下情况进一步求解：(1)Q1无可行解，Q2无可行解，则整数规划P无可行解，算法结束；(2)Q1无可行解，Q2有整数解，则该解为P的最优解，算法按结束；(3)Q1无可行解，Q2有非整数解，则对Q2进行分枝转

22、Step2(4)Q1有整数解，Q2有整数解，则较优的一个为P的最优解，算法结束；(5)Q1有整数解且目标函数值优于Q2，Q2有非整数解，则Q1的整数解为P的最优解(6)Q1有整数解，Q2有非整数解且目标函数值优于Q1，则Q1停止分枝，其整数解为新的界，对Q2转Step2(7)Q1无整数解，Q2也无整数解，可以按照设定的规则选取一枝先进行分枝计算，其中一枝若计算得到的最优解为整数解，且最优值优于另一枝，则所得的整数解就是P的最优解，无须对另一枝进行分枝；若得到的最优值劣于另一枝，则对另一枝进行分枝转Step2第19页/共82页求解整数规划的分枝定界法求解整数规划问题P 首先求解P的松弛线性规划问

23、题Q，可知其最优解为：，在最优解处取得的函数最大值为：fQ=4，此时上界为上界为4，由于xQ的两个分量均不为整数，故需要对问题P进行分枝，在此，人为取x1进行分枝，对xP1=1.5向下取整得1，故加上互斥的约束条件x11和x12，那么加入该组互斥条件的作用在于：排除了区间(1,2)之内的非整数解，缩小了搜索的范围；形成了整数规划P的两个子问题P1和P2第20页/共82页求解整数规划的分枝定界法 由于现在已经存在两个子节点P1和P2，下一步选取哪个节点进行分枝需要采用合适的策略，在此我们采用广度优先搜索的方法，由于Q2的目标函数值较大，故对问题P2进行分枝，加入互斥的约束x21和x22，形成P2

24、的两个子问题P3和P4。当加入新的约束之后，有可能出现三种情况：(1)新加入的条件和原问题的条件独立，即互不影响，此时直接将约束加入到问题中；(2)新加入的条件和原问题的条件相矛盾，此时新的问题无可行解；(3)新加入的约束和原约束存在交集，则此时选择其交集作为作为新问题的约束条件。第21页/共82页求解整数规划的分枝定界法 由于Q3的目标函数值fQ3大于Q1的目标函数值fQ1，故下一步对P3进行分枝，加入互斥的约束x12和x13，形成P3的两个子问题P5和P6。现在我们已经在P2的分枝上找到了一组整数解，现在比较fQ5和fQ1，由于现在已有整数解的目标函数值fQ5大于fQ1，而P1的最优目标函

25、数值不会大于fQ1，故该分枝的解不会对目标函数值有任何的改善，所以对P1进行剪枝，即停止对P1的向下分枝，我们已经搜索到了的最优解。这里需要注意注意的，如果我们发现已经求得整数解的最优值fQ5要小于fQ1，则P的上界还并未确定，于是问题还需要继续分解下去。第22页/共82页求解整数规划的分枝定界法上述求解过程示意图第23页/共82页求解0-1规划的隐枚举法 隐枚举法的提出由E Balas在1965年提出的，该方法只检查一部分变量组合，在这过程中根据已有信息自动舍弃许多不可能成为最优解的组合以求得最优解，从而大大减少了工作量，隐枚举法只需比较目标函数在一小部分组合点上的取值大小就能求得最优解和最

26、优值。隐枚举法的思想隐枚举法可以看作是分枝定界法的特殊情况，在求解的过程中，它不需要求解其松弛线性规划问题，利用变量只能取0或1对问题进行分枝。其思路是先将0-1规划问题转化为既定的标准型，该标准型一般是要最小化目标函数的值，在此前提下，首先令全部变量取0值（当求最大值时，令全部变量取1值），检验解是否满足约束条件，若均满足，已得最优解；若不全满足，则令一个变量分枝取值为0或1，该分枝变量称为固定变量，将模型分成两个子模型，其余未被指定取值的变量称为自由变量，通过这种方法，依次指定一些变量为1，直至得到一个可行解，并将它作为目前最好的可行解并记录下来。此后，经过几次检验后，或者停止分枝，或者将

27、另一个自由变量转为固定变量，令其值为0或l，如此继续进行，依次试探变量等于0或l的某些组合，使目前最好的可行解不断逼近最优值，直至没有自由变量或全部子问题停止分枝为止，就求出了0-1规划的最优解，第24页/共82页求解0-1规划的隐枚举法取试探解的理由为什么从全0作出初始的试探解，这是因为0-1规划的标准型要求对目标函数求最小值，而对于最小化目标函数的问题，由于在后面我们会提到0-1规划标准型中cj0，故因此自由变量为0与固定变量组成的子模型能够使得目标函数值最小。同理，如果不用标准型求解，例如对目标函数求最大值的问题，则是将全1作为初始的试探解进行分枝计算隐枚举法和穷举法的不同隐枚举法和穷举

28、法不同，穷举法需要将所有可行的变量组合逐个列举，而隐枚举法通过试探、分析和判断，排除了许多变量组合作为最优解的可能性。也就是说，它们被隐含枚举了，这也是称其为隐枚举法的原因隐枚举法的实质从算法描述可以看出，隐枚举法的实质也是分枝定界法，隐枚举法在求解过程中与一般的分枝定界法不同之处只在于在分枝产生子问题时变量被固定为0或1，而不是两个范围之值的形式。第25页/共82页求解0-1规划的隐枚举法隐枚举法的0-1规划标准型 非标准型的标准化若原问题为求max f，则可令f=-f 将问题转化为min f。或者不改变求最值的属性，将全1作为0-1规划的初始试探解当某个系数cjfP1，故停止向下分枝。按照

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

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

31、件。第34页/共82页求解分派问题的匈牙利算法非标准型的标准化目标函数中设计变量xmn对应的系数为负数Emn0 可令 ，此时有 ，取 可 知 ,于是原目标函数变为：经过上述转换实现了将目标函数中所有设计变量的系数变成正数目标函数求最大 令 ,其中M是足够大的常数，一般方法是令M为效率矩阵元素Eij中的最大值，即 ，由于对于任意的i,j(i=1,2,n;j=1,2,n)均可满足max(Eij)-Eij0，故可以保证Fij0，这时，系数矩阵变为：F=(Fij)，且满足Fij0，对应效率矩阵F的分派问题的目标函数满足：显然可以表达成为 ，因为nM为一常数，故当f 取得最小值时，可以取到最大值，即通过

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

33、阵E进行变换，来获得这一组位于不同行且不同列的零元素。第36页/共82页求解分派问题的匈牙利算法匈牙利算法的理论基础引理1：如果将效率矩阵E的第i行每个元素减去一个常数ui，将第j列中每个元 素减去一个常数vj，得到新的效率矩阵F，其第i行第j列的元素为Fij=aij-ui-vj，则分别对应于E和F的两个分派问题的最优解等价，其最优值相差推论1：如果将效率矩阵E的每一行（或每一列）各元素分别减去该行（或该列）的最小元素，由此得到的新的效率矩阵F，则分别对应于E和F的两个分派问题的最优解等价引理2：若矩阵E的元素可以分成“0”元素和“非0”元素两部分，则覆盖所有“0”元素的最少直线（将直线上的元

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

35、列已经有零元素，则不必再减 对例题中的E，操作如下：第38页/共82页求解分派问题的匈牙利算法第二步，最优性检验，进行试指派，即找出不同行不同列的0元素(I)给只有一个0元素的行中的0打上括号，记作(0)，并划去与其同列的其余0元素，记作；(II)给只有一个0元素的列中的0打上括号，记作(0)，并划去与其同行的其余0元素，记作；(III)反复进行(I)和(II)，直至所有的0都被标记为止；(IV)若仍有没有被标记的0元素，则可从剩余的0元素最少的行（列）开始，选择0元素少的那列（行）的0元素加括号（表示选择性多的要礼让选择性少的）。然后，划去同行同列的其它0元素，反复进行，直到所有0元素都已被

36、标记为止。(V)若(0)元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已经找到，若mn，转下一步第39页/共82页求解分派问题的匈牙利算法第三步，矩阵变换作能覆盖所有0元素的最少直线(a)对没有(0)的行标记“*”；(b)对标记“*”行上含有0元素的列标记“*”；(c)对标记“*”列上有(0)的行标记“*”(d)重复(b)(c)直到无法标记“*”为止(e)对标记“*”的列画纵线，未标记“*”的行画横线，这就是能覆盖所有0元素的最少直线移动0元素在未被划去的元素中找出最小元素s，将其作为矩阵变换的调整量；将标记“*”行的所有元素都减去s将标记“*”列的所有元素都加上s 结果将得到一个新的效

37、率矩阵，转第二步。第40页/共82页求解分派问题的匈牙利算法 对于本例的示例矩阵，未被划去的元素中最小者为2，故首先将第1行和第3行减去2，然后将第2列加上2，获得新的效率矩阵：返回第二步，即尝试在上述矩阵中找到不同行且不同列的n个0元素第41页/共82页求解分派问题的匈牙利算法由以上求解结果，可以知道有两种最优的指派方式，相应的分派方案1号成员完成2号任务，2号完成3号任务，3号完成1号任务，4号完成4号任务；1号完成1号任务，2号完成3号任务，3号完成2号任务，4号完成4号任务最优方案耗时M1：f=21+12+29+23=85M2：f=20+13+29+23=85 第42页/共82页一般整

38、数规划问题的MATLAB求解 求解方法由于MATLAB优化工具箱中并未提供求解纯整数规划和混合整数规划的函数，因而需要自行根据需要和设定相关的算法来实现。现在有许多用户发布的工具箱可以解决该类问题，例如比较著名的YALMIP，读者可以自行到网上下载相关的工具包并进行学习。这里我们给出开罗大学的Sherif和Tawfik在MATLAB Central上发布的一个用于求解一般混合整数规划的程序，在此命名为intprog，笔者在原程序的基础上做了简单的修改，将其选择分枝变量的算法由自然序改造成分枝变量选择原则中的一种，即：选择与整数值相差最大的非整数变量首先进行分枝调用格式 x,fval,exitf

39、lag=intprog(c,A,b,Aeq,beq,lb,ub,M,TolXInteger)第43页/共82页一般整数规划问题的MATLAB求解标准形式假设x为n维设计变量，且问题具有不等式约束m1个，等式约束m2个，那么：c、x均为n维列向量，b为m1维列向量，beq为m2维列向量，A为m1n维矩阵，Aeq为m2n维矩阵。输入参数有c,A,b,Aeq,beq,lb,ub,M和TolXInteger。其中c为目标函数所对应设计变量的系数，A为不等式约束条件方程组构成的系数矩阵，b为不等式约束条件方程组右边的值构成的向量。Aeq为等式约束方程组构成的系数矩阵，beq为等式约束条件方程组右边的值构

40、成的向量。lb和ub为设计变量对应的上界和下界。M为具有整数约束条件限制的设计变量的序号，例如问题中设计变量为x1,x2,x6，要求x2,x3和x6为整数，则M=2;3;6；若要求全为整数，则M=1:6，或者M=1;2;3;4;5;6。TolXInteger为判定整数的误差限，即若某数x和最邻近整数相差小于该误差限，则认为x即为该整数。输出参数有x,fval和exitflag。其中x为整数规划问题的最优解向量，fval为整数规划问题的目标函数在最优解向量x处的函数值，exitflag为函数计算终止时的状态指示变量。第44页/共82页一般整数规划问题的MATLAB求解算法实现intprog.m%

41、整数规划的整数规划的MATLAB实现实现%Originally Designed By Sherif A.Tawfik,Revised By LiMing,2009-12-29%函数调用形式函数调用形式x,fval,exitflag=intprog(f,A,b,Aeq,beq,lb,ub,M,TolXInteger)%函数求解如下形式的整数规划问题函数求解如下形式的整数规划问题%min f*x%subject to%A*x=b%Aeq*x=beq%lb=x=ub%M存储有整数约束的变量编号的向量存储有整数约束的变量编号的向量%TolXInteger是判定整数的误差限是判定整数的误差限%函数返回

42、变量函数返回变量%x:整数规划的最优解整数规划的最优解%fval:目标函数在最优解处的函数值目标函数在最优解处的函数值%exitflag=1 收敛到解收敛到解x%0 达到线性规划的最大迭代次数达到线性规划的最大迭代次数%-1 无解无解%function x,fval,exitflag=intprog(f,A,b,Aeq,beq,lb,ub,M,TolXInteger)%设置不显示求解线性规划过程中的提示信息设置不显示求解线性规划过程中的提示信息options=optimset(display,off);%上界的初始值上界的初始值bound=inf;%求解原问题求解原问题P0的松弛线性规划的松弛

43、线性规划Q0，首先获得问题的初始解，首先获得问题的初始解x0,fval0=linprog(f,A,b,Aeq,beq,lb,ub,options);%利用递归法进行二叉树的遍历，实现分枝定界法对整数规划的求解利用递归法进行二叉树的遍历，实现分枝定界法对整数规划的求解x,fval,exitflag,b=rec_BranchBound(f,A,b,Aeq,beq,lb,ub,x0,fval0,M,TolXInteger,bound);第45页/共82页一般整数规划问题的MATLAB求解%分枝定界法的递归算法分枝定界法的递归算法,x为问题的初始解，为问题的初始解，v是目标函数在是目标函数在x处的取值

44、处的取值function xx,fval,exitflag,bb=rec_BranchBound(f,A,b,Aeq,beq,lb,ub,x,v,M,TolXInteger,bound)options=optimset(display,off);%求解不考虑整数约束的松弛线性规划求解不考虑整数约束的松弛线性规划x0,fval0,exitflag0=linprog(f,A,b,Aeq,beq,lb,ub,options);%如果算法结束状态指示变量为负值，即表示无可行解，返回初始输入如果算法结束状态指示变量为负值，即表示无可行解，返回初始输入%或者所目标函数值大于已经获得的上界，返回初始输入或者

45、所目标函数值大于已经获得的上界，返回初始输入if exitflag0bound xx=x;fval=v;exitflag=exitflag0;bb=bound;return;end%确定所有变量是否均为整数，如是，则返回确定所有变量是否均为整数，如是，则返回ind=find(abs(x0(M)-round(x0(M)TolXInteger);%该条件表示该条件表示x0(M)不是整数不是整数%如果都是整数如果都是整数if isempty(ind)exitflag=1;%如果当前的解优于已知的最优解，则将当前解作为最优解如果当前的解优于已知的最优解，则将当前解作为最优解 if fval0flag

46、br_var=tempbr_var;br_value=tempbr_value;flag=temp_flag;endendif isempty(A)r c=size(Aeq);else r c=size(A);end第47页/共82页一般整数规划问题的MATLAB求解%第第1个子问题的设置个子问题的设置,添加约束条件添加约束条件Xi=ceil(Xi)，i即为上面找到的最接近整数的非整数设计变量的序号即为上面找到的最接近整数的非整数设计变量的序号 A2=A;zeros(1,c);A2(end,br_var)=-1;b2=b;-ceil(br_value);%分枝后的第一个子问题的递归求解分枝后的

47、第一个子问题的递归求解x1,fval1,exitflag1,bound1=rec_BranchBound(f,A1,b1,Aeq,beq,lb,ub,x0,fval0,M,TolXInteger,bound);exitflag=exitflag1;if exitflag10&bound10&bound2bound exitflag=exitflag2;xx=x2;fval=fval2;bb=bound2;end第48页/共82页一般整数规划问题的MATLAB求解求解整数规划问题 上例中x和fval为整数规划问题对应松弛线性规划的最优解和最优值，x1和fval1为整数规划的最优解和最优值，可见本

48、例中无论如何对x进行取整操作都无法得到整数规划问题的最优解。c=-5;-8;A=1 1;5 9;b=6;45;lb=0;0;M=1;2;%x1,x2均要求为整数变量均要求为整数变量Tol=1e-8;%判断是否整数的误差限判断是否整数的误差限x,fval=linprog(c,A,b,lb,)%松弛问题的解松弛问题的解x1,fval1=intprog(c,A,b,lb,M,Tol)%整数规划的解整数规划的解Optimization terminated.x=2.2500 3.7500fval=-41.2500 x1=0 5fval1=-40.0000第49页/共82页一般整数规划问题的MATLAB

49、求解求解整数规划问题c=-1;-1;A=-4 2;4 2;0-2;b=-1;11;-1;lb=0;0;M=1;2;%均要求为整数变量均要求为整数变量Tol=1e-8;%判断是否整数的误差限判断是否整数的误差限x,fval=linprog(c,A,b,lb,)%求解原问题松弛线性规划求解原问题松弛线性规划x1,fval1=intprog(c,A,b,lb,M,Tol)%求最优解整数解求最优解整数解x=%松弛线性规划问题的最优解松弛线性规划问题的最优解 1.5000 2.5000fval=-4.0000 x1=%整数规划的最优解整数规划的最优解 2 1fval2=-3.0000第50页/共82页0

50、-1规划的MATLAB求解0-1规划问题的MATLAB标准型在上述模型中，目标函数f 需要极小化，不等式约束形式为“”。假设x为n维设计变量，且线性规划问题具有不等式约束m1个，等式约束m2个，那么：c、x均为n维列向量，b为m1维列向量，beq为m2维列向量，A为m1n维矩阵，Aeq为m2n维矩阵。如果不满足标准型的要求，则需要对原问题进行转化，化为标准型之后才能使用相关函数，标准化的方法和线性规划中的类似0-1规划问题的MATLAB求解函数 MATLAB优化工具箱中求解0-1规划问题的命令为bintprog 第51页/共82页0-1规划的MATLAB求解bintprog的调用格式 x=bi