第四章 整数规划

1、数学建模基础数学建模基础青岛科技大学数理学院王天顺整整 数数 规规 划划 讲讲 义义2012年04月 1 1 整数规划问题的提出整数规划问题的提出一、整数规划问题的特征：一、整数规划问题的特征： 规划中的变量（部分或全部）限制为整数，若在规划中的变量（部分或全部）限制为整数，若在线性规划模型中，变量限制为整数，则称为整数线线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。效地求解一切整数规划。 二、整数规

2、划问题的求解方法分类：二、整数规划问题的求解方法分类： 1 1、（、（i i）分枝定界法）分枝定界法可求纯或混合整数线性规划。可求纯或混合整数线性规划。（iiii）割平面法）割平面法可求纯或混合整数线性规划。可求纯或混合整数线性规划。（iiiiii）隐枚举法）隐枚举法求解求解“0-1”0-1”整数规划：整数规划： 过滤隐枚举法；过滤隐枚举法； 分枝隐枚举法。分枝隐枚举法。（iviv）匈牙利法）匈牙利法解决指派问题（解决指派问题（“0-1”0-1”规划特殊情规划特殊情形）。形）。（v v）蒙特卡洛法）蒙特卡洛法求解各种类型规划。求解各种类型规划。2 2整数规划的分枝定界法整数规划的分枝定界法 对

3、有约束条件的最优化问题（其可行解为有限数）的所有可解空对有约束条件的最优化问题（其可行解为有限数）的所有可解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考

4、虑，这称剪枝。子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。这就是分枝定界法的主要思路。分枝定界法可用于解纯整数或混合的整数规划问题。由于这方法分枝定界法可用于解纯整数或混合的整数规划问题。由于这方法灵活且便于用计算机求解，所以现在它已是解整数规划的重要方灵活且便于用计算机求解，所以现在它已是解整数规划的重要方法。目前已成功地应用于求解生产进度问题、旅行推销员问题、法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。工厂选址问题、背包问题及分配问题等。设有最大化的整数规划问题设有最大化的整数规划问题A，与它相应的线性

5、规划为问题，与它相应的线性规划为问题B，从，从解问题解问题B开始，若其最优解不符合开始，若其最优解不符合A的整数条件，那么的整数条件，那么B的最优目的最优目标函数必是标函数必是A的最优目标函数的上界；而的最优目标函数的上界；而A的任意可行解的目标函的任意可行解的目标函数值将是它的最优目标函数的一个下界。数值将是它的最优目标函数的一个下界。分枝定界法就是将分枝定界法就是将B的可行域分成子区域的方法。逐步减小上界的可行域分成子区域的方法。逐步减小上界和增大下界，最终求到最优目标函数值和增大下界，最终求到最优目标函数值 。 LPXbAXtsXCfBnjxXbAXtsXCfATjT标准问题为整数，设线

6、性整数规划问题：0.max)(,2,10.max)(fffffnjxAAfBiiiAxiiABiBj时有的最优目标函数值，这表示问题以，值，记为试探，求得其目标函数一般可取的一个整数可行解，用观察法找最优值的的上界，转为记为的整数条件但不符合有最优解若的解。则停（剪枝），得到的整数条件且符合有最优解若无可行解；），说明无可行解，则停（剪枝若：可能得到以下情况之一求解骤）分枝定界法：（一般步A, 1, 0)(22)(,A,)()(,A,)()()(),(1B进行迭代两个后继问题。不考虑整数条件求解这中得到两个子问题分别加入把，构造两个约束条件：，其值为任选一最优）分枝：（分枝与定界：以下进行分枝

7、和定界：),(),()()(),()(1)(变量个不符合整数条件的解中的B 在1.1212121BBBcccbxcbxbxstepiiiiii（2）定界，以每个后继问题为一分枝标明求解的结）定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界值最大者作为新的上界 ，从已符合整数条件的各，从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界分支中，找出目标函数值为最大者作为新的下界若无作用若无作用 不变。不变。第二步：比较与剪枝，各分枝的最优目标函数中若有第二步：比较与剪枝，各分枝的最优目标

8、函数中若有小于小于 者，则剪掉这枝，即以后不再考虑了。若大者，则剪掉这枝，即以后不再考虑了。若大于于 ，且不符合整数条件，则重复第一步骤。一，且不符合整数条件，则重复第一步骤。一直到最后得到直到最后得到 为止。得最优整数解。为止。得最优整数解。 fffffff例 求解下述整数规划，且为整数02, 17022017562719.290140maxxxxxxxTSxxf3 3 0-1型整数规划10 xj3.1 引入引入0-1变量的实际问题变量的实际问题 3.1.1 投资场所的选定投资场所的选定相互排斥的计划相互排斥的计划 例例4 某公司拟在市东、西、南三区建立门市部。拟议中有某公司拟在市东、西、南

9、三区建立门市部。拟议中有7个个位置（点）位置（点）Ai(i=1,27)可供选择。规定可供选择。规定 在东区。由在东区。由A1,A2,A3三个点中至多选两个；三个点中至多选两个； 在西区。由在西区。由A4,A5两个点中至少选一个；两个点中至少选一个；在南区，由在南区，由A6,A7两个点中至少选一个。两个点中至少选一个。 如选用如选用Ai点，设备投资估计为点，设备投资估计为bi元，每年可获利润估计为元，每年可获利润估计为ci元，元，但投资总额不能超过但投资总额不能超过B元。问应选择哪几个点可使年利润为最元。问应选择哪几个点可使年利润为最大？大？先引入先引入0-1变量令变量令于是问题可列写成：于是问

10、题可列写成： 72 , 1Ai0Ai1ixi点没被选中当点被选中当101761542321. .71或xixxxxxxxBbixitsi71maxicixiz3.1.2 相互排斥的约束条件相互排斥的约束条件有两个相互排斥的约束条件有两个相互排斥的约束条件5x1+4x224 或或7x1+3x2 45 。为了统一在一个问题中，引入为了统一在一个问题中，引入0-1变量变量y，则上述约束条件可改，则上述约束条件可改写写为：为： 5x1+4x224+yM,7x1+3x2 45+(1-y)M,y=0或或1 其中其中M是充分大的数。是充分大的数。约束条件约束条件x1=0 或或500 x1 800可改写为可改

11、写为500 yx1 800y, y=0或或1 如果有如果有m个互相排斥的约束条件：个互相排斥的约束条件： ai1x1+ainxn bi, i=1,2,m为了保证这个约束条件只有一个起作用，我们引入为了保证这个约束条件只有一个起作用，我们引入m个个0-1变量变量和一个充分大的常数和一个充分大的常数M而下面这一组而下面这一组m+1个约束条件个约束条件ai1x1+ainxn bi+yiM, i=1,2,m （1）y1+ym=m-1 （2）就合于上述的要求。这是因为，由于（就合于上述的要求。这是因为，由于（2），），m个个yi中只有一个中只有一个能取能取0值，设值，设yi*=0，代入（，代入（1），就

12、只有），就只有i=i*的约束条件起作的约束条件起作用，而别的式子都是多余的用，而别的式子都是多余的 3.2 0-1型整数规划解法之一（过滤隐枚举法）型整数规划解法之一（过滤隐枚举法）解解0-1型整数规划最容易想到的方法，和一般整数规划的情形一型整数规划最容易想到的方法，和一般整数规划的情形一样，就是穷举法，即检查变量取值为样，就是穷举法，即检查变量取值为0或或1的每一种组合，比较目的每一种组合，比较目标函数值以求得最优解，这就需要检查变量取值的标函数值以求得最优解，这就需要检查变量取值的2n个组合。对个组合。对于变量个数于变量个数n较大较大,这几乎是不可能的。因此常设计一些方法，只这几乎是不可

13、能的。因此常设计一些方法，只检查变量取值的组合的一部分，就能求到问题的最优解。这样的检查变量取值的组合的一部分，就能求到问题的最优解。这样的方法称为隐枚举法（方法称为隐枚举法（Implicit Enumeration），分枝定界法也是），分枝定界法也是一种隐枚举法。当然，对有些问题隐枚举法并不适用，所以有时一种隐枚举法。当然，对有些问题隐枚举法并不适用，所以有时穷举法还是必要的。穷举法还是必要的。例例321523Maxxxxz10,64344223213221321321或xxxxxxxxxxxxx 求解思路及改进措施：求解思路及改进措施：（i） 先试探性求一个可行解，易看出先试探性求一个可行

14、解，易看出(x1,x2,x3)=(1,0,0)满足约束条件，故为一个可行解，且满足约束条件，故为一个可行解，且z=3。（ii） 因为是求极大值问题，故求最优解时，凡是因为是求极大值问题，故求最优解时，凡是目标值目标值z3的解不必检验是否满足约束条件即可删的解不必检验是否满足约束条件即可删除，因它肯定不是最优解，于是应增加一个约束除，因它肯定不是最优解，于是应增加一个约束条件（目标值下界）：（条件（目标值下界）：（iii） 改进过滤条件。改进过滤条件。（iv） 由于对每个组合首先计算目标值以验证过由于对每个组合首先计算目标值以验证过滤条件，故应优先计算目标值大的组合，这样可滤条件，故应优先计算目

15、标值大的组合，这样可提前抬高过滤门槛，以减少计算量。提前抬高过滤门槛，以减少计算量。 4 4分派问题及解法分派问题及解法艘艘船船去去航航行行等等。条条航航线线有有项项任任务务；台台机机床床加加工工类类似似有有：率率最最高高。决决定定如如何何指指派派可可使使总总效效同同任任务务的的效效率率不不同同，去去完完成成，各各人人对对完完成成不不个个人人（每每人人一一项项）项项任任务务要要分分配配给给题题）：一一、分分派派问问题题（指指派派问问nnnnproblemAssignmentnn 10, 1, 1, 1, 1.min)(01:0.11111或或每每人人一一项项任任务务每每项项任任务务一一人人模模

16、型型：否否则则项项任任务务个个人人完完成成第第第第引引入入（时时间间成成本本等等）项项任任务务的的效效率率个个人人完完成成第第第第设设一一般般模模型型：ijnjijniijninjijijijijxnixnjxtsxcfPjixjic称为指派问题的系数矩阵称为指派问题的系数矩阵二、求解方法二、求解方法1 1、直接利用直接利用Matlab的函数的函数binprog。整数规划问题的求解可以使用整数规划问题的求解可以使用Lingo等专用软件。对于一般的整数等专用软件。对于一般的整数规划规划问题，无法直接利用规划规划问题，无法直接利用Matlab的函数，必须利用的函数，必须利用Matlab编编程实现分

17、枝定界解法和割平面解法。但对于指派问题等特殊的整程实现分枝定界解法和割平面解法。但对于指派问题等特殊的整数规划问题，有时可以直接利用数规划问题，有时可以直接利用Matlab的函数的函数binprog。 nnnnnncccccccccC212222111211阵阵上上：数数据据集集中中在在下下列列系系数数矩矩kiackicbakCproofBbBaCkjijijnmij那么，行各元素加上的第设从与原问题有相同的解。为系数矩阵的分派问题以那么得到矩阵加上同一个实数素中的一行（或一列）各元若从矩阵,.,)(2、匈牙利算法由于指派问题的特殊性，又存在着由匈牙利数学家Konig提出的更为简便的解法匈牙利

18、算法。算法主要依据以下事实： 响最优解。目标函数的常数项不影目标函数：afxaxcxbfnkiinjkjnjijijninjijij11111条条直直线线覆覆盖盖所所有有零零至至少少个个独独立立零零元元素素至至少少有有直直线线数数。覆覆盖盖所所有有零零元元素素的的最最少少的的最最多多个个数数等等于于系系数数矩矩阵阵中中独独立立零零元元素素匈匈牙牙利利关关于于独独立立元元素素的的定定理理336072395006024310.).(. 3 ExnigoKD nmmn 有有）（覆盖零的直线数（覆盖零的直线数直线数直线数找最少的覆盖全部零的找最少的覆盖全部零的）数为数为（独立零个（独立零个找最多的独立

19、零个数找最多的独立零个数对偶”关系对偶”关系注：这里提供的一种“注：这里提供的一种“”；标为“列的其他零元素划去，同时把该元素所在”则给它加圈，标为“中只有一个零元素，对每行检查，若当前行：试派，即找独立零元素每列均有零元素；，反复进行，至每行、（列）各元素的最小值列）分别减去该行对矩阵的每一行（每一各元素步骤：设求匈牙利法求解分派问题0,)0(1. 2. 10min,stepstep。中单个零元素均被处理，直到所有行、列，反复执行”；“去，标为在的行的其它零元素划同时把该元素所加圈，标为不算），给它划去的零个零元素中只有一对每列检查，若当前列210),0(0(2. 3, 0, 1.3210,

20、)0(13stepnmxxnmmijij时时，转转当当即即为为最最优优解解。其其余余应应的的时时，停停止止，所所加加圈圈零零对对当当记记加加圈圈零零的的个个数数为为处处理理。，直直至至所所有有的的零零元元素素被被，反反复复进进行行”；与与列列的的其其它它零零元元划划去去“同同时时把把该该元元素素所所在在的的行行”“元元素素加加圈圈或或列列，把把其其中中任任一一个个零零选选零零元元素素个个数数较较少少的的行行个个，类类似似上上述述办办法法：均均多多于于若若同同行行（列列）中中零零元元素素 ”的的行行，列列为为止止。直直到到得得不不出出新新记记“，重重复复”；行行，记记“”元元素素所所在在”列列中

21、中，加加圈圈零零“再再对对有有“”；记记“”元元素素所所在在列列，”行行中中，划划去去零零“对对有有“；记记号号，无无妨妨记记“对对无无加加圈圈零零元元素素的的行行作作最最小小直直线线数数。确确定定覆覆盖盖全全部部零零元元素素的的 32)0(3021. 3step)(2. 4.4成功，重新试派成功，重新试派说明试探不说明试探不时，转时，转当当时，转时，转当当总线数总线数”的列画一纵线，记”的列画一纵线，记对所有有“对所有有“”的行画一横线；”的行画一横线；对所有无“对所有无“stepnlstepnll . 2. 4stepstep转转。”的的列列中中各各元元素素加加上上所所有有记记“，”的的行行中中各各元元素素减减去去所所有有记记“，对对最最小小元元素素为为设设无无直直线线覆覆盖盖部部分分中中的的不不得得出出现现负负元元。素素的的个个数数，但但变变换换矩矩阵阵，以以增增加加零零元元 减减各各行行最最小小元元，例例467679107104106614159141217766698979712. 1