管理运筹学03整数规划

1、3.1 3.1 整数规划问题及其建模整数规划问题及其建模3.2 3.2 分支定界法分支定界法3.3 3.3 割平面法割平面法3.4 0-13.4 0-1型整数线性规划的解法型整数线性规划的解法3.5 3.5 指派问题指派问题3.6 3.6 整数规划应用整数规划应用第3章 整数规划2整数规划整数规划：变量取整数的线性规划；纯整数规划纯整数规划：所有变量都取整数的线性规划；混合整数规划：混合整数规划：部分变量取整数的线性规划；0-10-1规划：规划：所有变量都取0、1两个值的规划；0-10-1混合规划：混合规划：部分变量取0、1两个值的规划。例3-1背包问题 4线性规划最优解为: x1=0，x2=

2、0，x3=2.5而整数规划的最优解是 x1=1，x2=0，x3=2maxmaxs.t.s.t.z=z=17x17x1 110 x10 x1 1x x1 1, ,x x1 1, ,+72x+72x2 2+42x+42x2 2x x2 2, ,x x2 2, ,+35x+35x3 3+20 x+20 x3 3x x3 3x x3 3为整数为整数505000例3-2厂址选择问题在n个地点中选r个（nr）建厂，在第i个地点建厂（i=1，2，n）所需投资为ii万元，占地li亩，建成以后的生产能力为pi万吨。现在有总投资i万元，土地l亩，应如何选择厂址，使建成后总生产能力最大。设 5整数规划模型为:地建厂

3、表示在地不建厂表示在i1i0 xi1,0 xrxlxlixi. t .sxpzmaxin1iin1iiin1iiin1iii0-10-1规划规划例3-3 考虑固定成本的最小生产费用问题 在最小成本问题中，设第j种设备的固定成本为 ，运行的变动成本为 ，则生产成本与设备运行时间的关系为：6000)(jjjjjjjxxcdxxf当当jdjcibija1 , 0, 0, 2 , 1, 2 , 1. .)(min11jjjjnjijijnjjjjjyxnjmyxmibxatsxcydz混合混合0-10-1规划规划设第j种设备运行每小时可以生产第i种产品 件，而第i种产品定货为 件。要满足定货同时使设备

4、运行的总成本最小的问题为：7且为整数0,521964214. .4max21214121xxxxxxtsxxz0,521964214. .4max21214121xxxxxxtsxxz线性规划整数规划x*=（13/5，19/5）z*=89/5=17.8x*=（5，3）z*=17基本思想分支（branch）定界（bound）第3章 整数规划80xbaxcxzmin0xixbaxcxzminrr01xixbaxcxzminrrx xr riir rx xr r ir+1分支（branch）这两个子问题的可行域都是原线性规划问题可行域的子集，这两个子问题的最优解的目标函数值都不会比原线性规划问题的最

5、优解的目标函数值更小。如果这两个问题的最优解仍不是整数解，则继续选择一个非整数的变量，继续将这个子问题分解为两个更下一级的子问题。这个过程称为“分枝（branch）”。定界（bound）如果某一个子问题的最优解是整数解，则它的目标函数值可作为整数规划最优目标函数值的上界。如果某一个子问题的解还不是整数解，但这个非整数解的目标函数值已经超过这个上界，那么这个子问题不必再进行分枝。如果在分枝过程中得到新的整数解且该整数解的目标函数值小于已记录的上界，则用较小的整数解的目标函数值代替原来的上界。上界的值越小，就可以避免更多不必要的分枝。确定整数解目标函数值上界并不断更新上界，并且不断“剪除”目标函数

6、值超过上界的分枝的过程，称为定界（bound）。第3章 整数规划9例例3-43-4 用分枝定界法求解以下整数规划先求得相应的线性规划的最优解，为第3章 整数规划1012121212min235735. . 4936,0zxxxxs txxx x 且为整数17814,1762,1712321zxx11sub-6无可行解原问题原问题121 231 7621 781 41 7xxz sub-2121231731132xxz subxxsub-314142421zzxxsub-47214731,521zxxsub-55114153521zxxsub-714131521zzzx

7、xsub-914140721zzzxxsub-8731475621zxxsub-10无可行解x22x23x15x15x21x22x14x16x20 x21图3-3. 探索过程示意图14zz 1第3章 整数规划12首先放弃变量的整数要求，求得线性规划的最优解。首先放弃变量的整数要求，求得线性规划的最优解。如果最优解恰是一个整数解，则线性规划的最优解就是相如果最优解恰是一个整数解，则线性规划的最优解就是相应的整数规划的最优解。应的整数规划的最优解。如果线性规划的最优解不是整数解，则要构造一个新的约如果线性规划的最优解不是整数解，则要构造一个新的约束，对线性规划问题的可行域进行切割，切除已经得到的束

8、，对线性规划问题的可行域进行切割，切除已经得到的线性规划的最优解，但保留原可行域中所有的整数解，求线性规划的最优解，但保留原可行域中所有的整数解，求解新的线性规划问题解新的线性规划问题如果最优解仍不是整数解，再增加附加的约束将其切除，如果最优解仍不是整数解，再增加附加的约束将其切除，但仍保持最初可行域中所有的整数解，如此一直进行，直但仍保持最初可行域中所有的整数解，如此一直进行，直至得到一个整数的最优解为止。至得到一个整数的最优解为止。第3章 整数规划13设放弃变量整数要求得到的线性规划的最优单纯形表如下：设放弃变量整数要求得到的线性规划的最优单纯形表如下：设其中基变量设其中基变量xr的值的值

9、br不是整数，以不是整数，以i表示整数，以表示整数，以 f表表示正的真分数，令示正的真分数，令yrj = irj + frj (0 frj 1) r= i + f (0 f 1)将上面两式代入将上面两式代入约束约束r中，得中，得第6章 整数规划14改写成改写成因此对于整数可行解，约束（因此对于整数可行解，约束（3-2）可以写成更严格的不等式）可以写成更严格的不等式这就是源于第这就是源于第 行的行的。 线性规划的任何整数可行解都满足这个约束；线性规划的任何整数可行解都满足这个约束；未切割掉未切割掉任何一个整数解。任何一个整数解。 线性规划的非整数最优解不满足这个约束。线性规划的非整数最优解不满足

10、这个约束。切割掉了非切割掉了非整的整的lp解解x；rrnmjjrjrjrfixfix1)(nmjjrjrrnmjjrjrxffixix11011nmjjrjrrnmjjrjrxffixix第3章 整数规划15 2 若若xk的分量全为整数的分量全为整数，则，则xk即为原问题的最优解，停止计算即为原问题的最优解，停止计算； 否则根据否则根据xk的一个非整分量所在单纯形表的那一行，譬如第的一个非整分量所在单纯形表的那一行，譬如第 r 行，行， 构造源于第构造源于第 i行行的的给它引入一个弛变量给它引入一个弛变量 n+k+1， 得得 frj j + n+k+1 =-f-fj =m+1 - - 3 把这

11、个新约束添到最优单纯形表中，并增加一列把这个新约束添到最优单纯形表中，并增加一列( 即即 n+k+1列列 )，用对偶单纯形法继续迭代，求得一个新解，用对偶单纯形法继续迭代，求得一个新解xk+1， 令令k: = k+1，返，返2。 1 用单纯形法求解用单纯形法求解ip的伴随的伴随lp问题问题，得到其解得到其解x0，令，令k=0；n第6章 整数规划16 min z = 3x1+4x23x1+x24x1+2x24 x1, , x20 x1, , x2 为整数s.t.例例3-53-5 试用割平面法求解以下整数规划：试用割平面法求解以下整数规划：解解 求解线性规划得最优单纯形表求解线性规划得最优单纯形表

12、选择一个非整数的基变量，例如选择一个非整数的基变量，例如 x x2 2=8/5=8/5，构造约束条件，构造约束条件(3-4(3-4） b2=8/5=1+3/5，i2=1，f2=3/5 y23=1/5=0+1/5，i23=0，f23=1/5 y24=-3/5=-1+2/5，i24=-1，f24=2/5附加的约束条件 为 3/5-（1/5x3+2/5x4）0即1/5x3+2/5x43/5将这个约束加到线性规划的最优单纯形表中，并增加一个松弛变量x5, ,得下表得下表第3章 整数规划17第3章 整数规划18用对偶单纯形法，用对偶单纯形法，x5x5离基，离基，x3x3进基进基已获得整数的最优解：已获得

13、整数的最优解： x*=（2，1） z*=10为了得到切割约束1/5x3+2/5x43/5在（x1, x2）平面中的表达式，将其中的松弛变量x3，x4用x1，x2表示 x3=3x1+x2-4，x4=x1+2x2-4代入切割约束，得到 x1+x23这个切割过程的图解如下图第3章 整数规划19整数规划最优解0123451234切割直线线性规划最优解隐枚举法（implicit eumeration）例例3-6 3-6 用隐枚举法求解下列问题 可行解：x=(1，0，0)，z=3 增加过滤条件（filtering constraint） 第3章 整数规划201231231231213123max32522

14、44. .346,01zxxxxxxxxxstxxxxx x x或1233253xxx第3章 整数规划21按价值系数从小到大排列max z=-2x2+3x1+5x3 -2x2+3x1+5x33 2x2+x1-x32 4x2+x1+x34 x2+x1 3 4x1+x36 第3章 整数规划22点条件满足条件？是（t）否（f）z（0 0 0）0f（0 0 1）5-1101t5第3章 整数规划23点条件满足条件？是（t）否（f）z（0 1 0）3f（0 1 1）80215t8点条件满足条件？是（t）否（f）z（1 0 0）-2f（1 0 1）3f（1 1 0）1f（1 1 1）6f指派问题或分派问题（

15、指派问题或分派问题（assignment problemassignment problem）：）：需完成n项任务，恰好有n个人可承担这些任务。各人完成任务的效率(或所费时间) 不同。应指派哪个人去完成哪项任务，使完成n项任务的总效率最高(或所需总时间最小)。例例3-5 3-5 甲、乙、丙、丁四人配送a,b,c,d四种货物, 所需时间如下表所示。若一种货物只交一人送货，则应指派何人配送何种货物, 能使总的时间最少？第3章 整数规划24工件工件工人工人abcd甲149415乙117910丙132105丁1791513效率矩阵设xij=1表示第 i人送j货，否则xij=0 上述问题的模型为：第3章

16、 整数规划251 , 04 , 2 , 114 , 2 , 11. .min41414141ijiijjijijijijxjxixtsxcz1 , 0, 0, 2 , 11, 2 , 11. .min1111ijijniijnjijninjijijxxnjxnixtsxcz一般指派问题的模型指派问题的求解方法指派问题的求解方法匈牙利法匈牙利法性质性质3-13-1. 若从系数矩阵(cij)的一行(列)各元素中分别减去该行(列)的最小元素，得到新矩阵(bij)，那么以(bij)为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同 。性质性质3-23-2. 若一个方阵的一部分元素为0，另一部分元素不

17、为0，则覆盖方阵内所有0元素的最少直线数恰好等于独立0元素（位于不同行，不同列的0元素）的最多个数。第3章 整数规划26例3-7：匈牙利法的步骤一、系数矩阵经变换，在各行各列中都出现一、系数矩阵经变换，在各行各列中都出现0 0元素。元素。二、寻找独立二、寻找独立0 0元素元素最优值为：z* =11+9+4+5=29第3章 整数规划273004160408070200805646083801132041105109274131591751021310971115491416040807020080560010100000010100)(ijx甲甲cc，乙乙aa，丙丙dd，丁丁bb例3-5：先减列

18、元素独立0元素的个数为3，小于矩阵的阶数。第3章 整数规划28542112510060255501007360008117606025550100731315917510213109711154914三、找出找出能覆盖非最优阵中所有能覆盖非最优阵中所有0 0元的元的最少直线集合最少直线集合第6章 整数规划29(1) 对没有对没有 元的行打元的行打号；号；0 (2) 对打对打号的行上所有号的行上所有 元所在的列打元所在的列打号；号；0 (3) 对打对打号的列上所有号的列上所有 元所在的行打元所在的行打号；号；0 (4) 重复重复(2)、(3)步骤，直到找不出新的打步骤，直到找不出新的打 号的行、

19、列为止；号的行、列为止； (5) 对没有打对没有打号的行画横线，对所有打号的行画横线，对所有打号号 的列画竖线，这就是能覆盖所有的列画竖线，这就是能覆盖所有0元的最少元的最少 直线的集合。直线的集合。三、用最少的直线数覆盖矩阵中的所有三、用最少的直线数覆盖矩阵中的所有0 0元素元素第3章 整数规划3025100602555010073四、增加矩阵中的四、增加矩阵中的0 0元素元素 在没有被直线覆盖的部分中找出最小元素。然后在打行各元素中都减去这最小元素，而在打列的各元素都加上这最小元素。 若得到n个独立的0元素，则已得最优解，否则回到第三步重复进行。14000603444010074第3章 整

20、数规划3125100602555010073最优解可令可令 b bijij=m-c=m-cijij 。其中。其中m m是足够大的常数是足够大的常数( (如选（如选（c cijij）中）中最大元素为最大元素为m m即可即可) )，这时系数矩阵可变换为，这时系数矩阵可变换为b=(bb=(bijij) )第3章 整数规划32ijijijxczmaxijijijijijijijijijijijijijijxcnmxcmxxcmxb)(目标函数经变换后，即解目标函数经变换后，即解ijijijxbzmin所得所得(b(bijij) )最小解即为原问题最小解即为原问题(c(cijij) )的最大解。的最大解。 例例3-83-8某航空公司是一家经营小型飞机、短途航线的运输企业。管理层准备拓展经营领域，面临的问题是：是采购更多的小型飞机来开辟一些新的短途航，还是开始通过为一些跨地区航线购买大型飞机来进军全国市场，或者两种方法同时进行，已知采购成本、年利润、最多购买的数量限制如下表。并且可用资金为1亿元，如何进行决策，能使年利