运筹学第五章整数规划

1、薛威薛威2012015 5年年4 4月月运筹学运筹学第五章整数规划第五章整数规划 Textmasterformate durch Klicken bearbeiten Zweite EbeneDritte Ebene Vierte Ebene Fnfte Ebene【教学目的】【教学目的】 通过本单元的通过本单元的学习，使学习，使学生掌握整数问题的概念，学生掌握整数问题的概念，类型和模型的建立，能够运用分支界定法求解一般整数类型和模型的建立，能够运用分支界定法求解一般整数问题，并掌握问题，并掌握0-10-1整数规划和指派问题的基本求解方法。整数规划和指派问题的基本求解方法。【教学重点教学重点】

2、建立整数规划模型建立整数规划模型掌握分支界定法掌握分支界定法【教学难点教学难点】0-10-1整数规划、指派整数规划、指派问题的求解问题的求解第五章整数规划 整数规划问题介绍 整数规划算法分枝定界法 整数规划算法割平面法 0-1整数规划 指派问题(分派问题)线性规划模型：nnxcxcxcz2211maxmnmnmmnnnnbxaxaxabxaxaxabxaxaxat s22112222212111212111.0,21nxxx实际问题要求xi为整数！如机器的台数，人数等整数规划线性整数规划非线性整数规划简称整数规划整数线性规划问题纯整数规划的数学模型：nnxcxcxcz2211maxmnmnmm

3、nnnnbxaxaxabxaxaxabxaxaxat s22112222212111212111.0,21nxxx取整数nxxx,210-1规划的数学模型：nnxcxcxcz2211maxmnmnmmnnnnbxaxaxabxaxaxabxaxaxat s22112222212111212111.0,21nxxx1 ,0,21nxxx整数规划纯整数规划01规划混合型整数规划例1.胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子售价30元/个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4个小时，油漆工2小时。生产一个椅子需要木工3个小时，油漆工1小时。该厂每月可用木工

4、工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？每月的销售收入生产椅子的数量生产桌子的数量解：设Zxx21,213050maxxxZ求12034.21xxt s50221 xx0,21xx为整数21,xx纯整数规划例2.某服务部门各时段（每2小时为一时段）需要的服务员人数见下表。按规定，服务员连续工作8小时（即4个时段）为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少。 时段12345678服务员最少数目10891113853解 设在第j时段开始时上班的服务员人数是xj。由于第j时段开始时上班的服务员将在第（j+1）时段结束时下班，所以决策变量只

5、需考虑x1，x2 ，x3 ，x4 ，x5。该问题的数学模型是，且均为整数035813119810. .min5, 4, 3, 2, 15545435432432132121154321xxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxz最省？使总建设费和总运输费的需求，又建厂，使得既满足各地。试决定应在哪些地方费为的单位运运往销地。从工厂，其销售量分别为品需要销售这种产，个地点。又有，分别是建设费，生产能力分别是它们生产同一种产品，地点有地点建厂，可供选择的例：某公司计划在几个ijjinnmmmcBAbbbBBBnfffaaaAAA2121212121,解：的运量运往商店表示工厂

6、设jiijBAx则总运费为mi 1nj 1ijijxc个地点建厂不在第个地点建厂在第设iiyi01则总建厂费为miiiyf1混合型整数规划数学模型：111minmnmijijiiijiZc xy f 0ijx1 ,0iymiaxt sinjij,2 , 1.1总结整数规划的可行域包含在其对应的一般线性规划可行域之内；整数规划的最优解可能不是其对应的一般线性规划的顶点；整数规划的最优解不会优于其对应的线性规划的最优解。分支定界法1、基本思路 且为整数且为整数)2 . 1( , 0)2 . 1( )IP(min11mjxmibxaxczjnjijijnjjj考虑纯整数问题：考虑纯整数问题：整数问题

7、的松弛问题： ),2 . 1( , 0),2 . 1( )LP(min11mjxmibxaxczjnjijijnjjj （1）先不考虑整数约束，解( IP )的松弛问题( LP )，可能得到以下情况之一： 若( LP )没有可行解，则( IP )也没有可行解，停止计算。 若( LP )有最优解，并符合( IP )的整数条件，则( LP )的最优解即为( IP )的最优解，停止计算。 若( LP )有最优解，但不符合( IP )的整数条件，转入下一步。 为讨论方便，设( LP )的最优解为： 不不全全为为整整数数其其中中目目标标函函数数最最优优值值为为), 2 , 1(.)0 , 0 ,( )0

8、(21)0(mibzbbbbXiTmr （2）分支： 在在( LP )的最优解的最优解 X(0)中，任选一个不符合整数条件的变量，中，任选一个不符合整数条件的变量，例如例如xr= br （不为整数），以（不为整数），以br表示不超过表示不超过br的最大整数。的最大整数。构造两个约束条件构造两个约束条件 xr br 和和 xr br1 将这两个约束条件分别加入问题将这两个约束条件分别加入问题( IP ) ，形成两个子问题，形成两个子问题( IP1)和和( IP2 ) ，再，再解这两个子问题的松弛问题解这两个子问题的松弛问题( LP1)和和( LP2) 。 （3）定界：记( IP )的目标函数最优

9、值为 ,以 作为 的下界，记为 。令 ，则有)0(zz zzzz *z)0(z*z （4）修改上、下界：按照以下两点规则进行。 在各分枝问题中，找出目标函数值最小者作为新的下界； 从已符合整数条件的分枝中，找出目标函数值最小者作为新的上界。 （5）比较与剪枝 ： 各分枝的目标函数值中，若有大于 者，则剪掉此枝，表明此子问题已经探清，不必再分枝了;否则继续分枝。 如此反复进行，直到得到如此反复进行，直到得到 为止，为止，即得最优解即得最优解 X* 。2、例题 max Z=40X1 + 90X2 9X1+7X2 567X1+20X2 70X1 , X2 0 X1 , X2为为整数整数解：先解该整数

10、规划对应的松弛问题解：先解该整数规划对应的松弛问题X* =4.8091.817Z* =355.890， 上界上界Z* 选选X1分枝分枝问题问题(2)(1)X1 4问题问题(3)(1)X1 5问题问题2解为解为X1 =4X2 =2.1Z=349.0解为解为X1 =5X2 =1.571Z=341.39问题问题3选选(2)继续分枝继续分枝问题问题(4)(2)X2 2问题问题(5)(2)X2 3分支定界过程分支定界过程(1)4.8091.817355.890(2)42.1349.0(3)51.571341.39(4)42340(5)1.4283340327.12(6)5.4441340307.76(7

11、)无解无解X1 4X1 5X2 2X2 1X2 2X2 3:0L讨论松弛问题无最优解，、01L无最优解则)(IP结束002010),*,*(*2zxxxXon最优值，、最优解为整数解0*) 1 ( X的最优解为，则)(*0IPX结束中至少有一个是分数，0*)2(X是分数设01*x：分枝x1x*01x1x*01+1:1L子问题无最优解，、11L剪枝1112111),*,*(*2zxxxXn最优值，、最优解为整数解1*) 1 ( X为下界1,z关闭中至少有一个是分数：1*)2(X继续分枝:2L子问题总结割平面法割平面法的基本思想： 若整数规划IP的松弛规划L0的最优解不是整数解，对L0增加一个约束

12、条件，得线性规划L1，此过程缩小了松弛规划的可行解域，在切去松弛规划的最优解的同时，保留松弛规划的任一整数解，因此整数规划IP的解均在L1中，若L1的最优解为整数解，则得IP的最优解。若L1的最优解不是整数解，重复以上步骤，由于可行解域在不断缩小，且保留IP所有的整数解，总可以在有限次后得到IP的最优解.原最优解要被割去可行域中割去一部分，割去部分不含整数解，割平面法原理：计算步骤：（1）用单纯形法求解( IP )对应的松弛问题( LP )： 若( LP )没有可行解，则( IP )也没有可行解，停止计算。 若( LP )有最优解，并符合( IP )的整数条件，则( LP )的最优解即为( I

13、P )的最优解，停止计算。 若( LP )有最优解，但不符合( IP )的整数条件，转入下一步。 （2）从(LP)的最优解中，任选一个不为整数的分量xr,将最优单纯形表中该行的系数 和 分解为整数部分和小数部分之和，并以该行为源行，按下式作割平面方程： 1rnmjjrjfxf rja 的小数部分的小数部分rjarb 的小数部分的小数部分rb （3）将所得的割平面方程作为一个新的约束条件置于最优单纯形表中（同时增加一个单位列向量），用单纯形法求出新的最优解，返回1。例例：用割平面法求解整数规划问题用割平面法求解整数规划问题 且为整数且为整数0,023623 max2121212xxxxxxxZ解

14、：解：增加松弛变量增加松弛变量x3和和x4 ，得到，得到(LP)的初始单纯形表和最的初始单纯形表和最优单纯形表：优单纯形表：Cj0100CBXBbx1x2x3x40 x3632100 x40-3201Z00100Cj0100CBXBbx1x2x3x40 x11101/6-1/61x23/2011/41/4Z-3/2 00 -1/4 -1/4 此题的最优解为：此题的最优解为：X= (1 , 3/2) Z = 3/2 但不是整数最但不是整数最优解，引入割平面。以优解，引入割平面。以x2 为源行生成割平面。为源行生成割平面。 此题的最优解为：此题的最优解为：X= (1 , 3/2) Z = 3/2

15、但不是整数最但不是整数最优解，引入割平面。以优解，引入割平面。以x2 为源行生成割平面，由于为源行生成割平面，由于 1/4=0+1/4, 3/2=1+1/2, 生成割平面的条件为生成割平面的条件为: Cj0100CBXBbx1x2x3x40 x11101/6-1/61x23/2011/41/4Z-3/2 00 -1/4 -1/421414143 xx0-1整数规划10,64342422.253max3213221321321321或例：求xxxxxxxxxxxxxt sxxxZ枚举法：检验可行解：32次运算计算目标函数值：8次（x1 x2 x3)Z值 约束条件（1）（2）（3）（4）过滤条件（

16、0 0 0）（0 0 1）（0 1 0）（1 0 0）（1 0 1）（1 1 0）（1 1 1）0-2531836 Z0Z5运算次数：21（0 1 1）01 整数规划是一种特殊形式的整数规划，这时的决策变量xi 只取两个值0或1，一般的解法为隐枚举法。是否能对上述方法进行优化，使得运算量进一步减少呢？根据上述算法的特点，可以按目标函数中各变量系数的大小顺序重新排列各变量，以使最优解尽可能早出现。试用改进的算法求解下题：1234123412341241234min3721. .64835,01zxxxxxxxxst xxxxxxxx x x x 或 在实际中经常会遇到这样的问题，有n 项不同的任

17、务，需要n 个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成 n 项任务的总效率最高（或所需时间最少），这类问题称为指派问题或分派问题。指派问题设决策变量设决策变量 1 分配第分配第i 个人去做第个人去做第j 件工作件工作 xij = 0 相反相反 ( i, j=1.2. n )其数学模型为：其数学模型为： ).2.1,1(0).2.1( 1).2.1( 1min1111njixnjxnixxcZijniijnjijninjijij或或指派问题的性质定理：定理：对于指派

18、问题，成本矩阵的任一对于指派问题，成本矩阵的任一行行(或列或列)减去减去(或加上或加上)一个相同的数得到一个相同的数得到的新指派问题与原问题同解的新指派问题与原问题同解解题步骤： 指派问题是0-1 规划的特例，当然可用整数规划，0-1 规划的解法去求解，但运算繁琐。利用指派问题的特点可有更简便的解法，这就是匈牙利法(匈牙利数学家D.Konig提出) ，即系数矩阵中独立 0 元素的最多个数等于能覆盖所有 0 元素的最少直线数。 第一步：变换指派问题的系数(也称效率)矩阵（cij）为(bij)，使在(bij)的各行各列中都出现0元素，即 (1) 从（cij）的每行元素都减去该行的最小元素； (2)

19、 再从所得新系数矩阵的每列元素中减去该列的最小元素。 第二步：进行试指派，以寻求最优解。 在(bij)中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。找独立0元素，常用的步骤为： (1)从只有一个0元素的行(列)开始，给这个0元素加圈，记作 。然后划去 所在列(行)的其它0元素，记作 ；这表示这列所代表的任务已指派完，不必再考虑别人了。 (2)给只有一个0元素的列(行)中的0元素加圈，记作；然后划去 所在行的0元素，记作 (3)反复进行(1)，(2)两步，直到尽可能多的0元素都被圈出和划掉为止。 (4)若仍有没有

20、划圈的0元素，且同行(列)的0元素至少有两个，则从剩有0元素最少的行(列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止。 （5）若 元素的数目m 等于矩阵的阶数n，那么这指派问题的最优解已得到。若m n, 则转入下一步。 第三步：作最少的直线覆盖所有0元素。 (1)对没有的行打号； (2)对已打号的行中所有含元素的列打号； (3)再对打有号的列中含 元素的行打号； (4)重复(2)，(3)直到得不出新的打号的行、列为止； (5)对没有打号的行画横线

21、，有打号的列画纵线，这就得到覆盖所有0元素的最少直线数 l 。l 应等于m，若不相等，说明试指派过程有误，回到第二步(4)，另行试指派；若 lm n，须再变换当前的系数矩阵，以找到n个独立的0元素，为此转第四步。第四步：变换矩阵(bij)以增加0元素。在没有被直线覆盖的所有元素中找出最小元素，然后打各行都减去这最小元素；打各列都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第二步。 例：求费用矩阵为右表的 指派问题的最优解费用工作人甲乙丙丁戊A B C D E12 7 9 7 9 8 9 6 6 6 7 17 12 14 12 15 14 6 6 10

22、4 10 7 10 661071041066141512141217766698979712C第一步：每行减去最小元素，每列减掉最小元素;第二步：对零元素画圈打;第三步: 划线覆盖零元素;61071041066141512141217766698979712C-7-6-7-6-426360400895751000003220205得4个，且不存在没打的0502 0 2230 0 00 10 5 7 5980 0 4063 6 2第四步：在没有被直线复盖的元素中找出最小元素，让打号的列加上这个元素，打号的行减去这个元素。70202430000835311800404140匈牙利法的具体步骤：第一

23、步：变换指派问题的费用矩阵，使其在各行各列都出现0元素；方法：首先每行元素减去该行的最小元素，然后每列减去该列的最小元素第二步：进行试指派（画）方法：从含0元素最少的行或列开始，圈出一个0元素，用 表示，然后划去该所在的行和列中的其余0元素，用表示，依次类推。若矩阵中的的个数等于n，则得最优解若矩阵中的的个数n，则进行第三步第三步：做能复盖所有0元素的最小直线集合：1）对没有的行打号2）对打号的行上所有0元素的列打号3）再对打号的列上所有的行打号4）重复以上步骤直到得不出新的打号为止5）对没有打号的行画横线，所有打号的列画纵线，所得到的直线既是复盖所有0元素的最小直线集合第四步：在没有被直线复

24、盖的元素中找出最小元素，让打号的列加上这个元素，打号的行减去这个元素。取整数求例21332142132121,0,5.1645.1432.2030maxxxxxxxxxxxxxtsxxz混合型0,5.1645.1432.2030max3321421321210 xxxxxxxxxxtsxxzL ；松弛问题:0L155, 00, 5 . 25 . 304321zxxxx，x13x14:1L:2LL0的最优单纯型表：x1x2x3x4常数项检00-5-5Z-155x2012/5-1/55/2x110-1/103/107/20,35.1645.1432.2030max33211421321211xxxxxxxxxxxtsxxzL ；随堂练习:0L155, 00, 5 . 25 . 304321zxxxx，x13x14:1L3440, 0,350,6173154321zxxxxx，:2L