stu1314com运筹学第3章整数规划模型

1、3.1 引言3.2 整数规划问题及其数学模型3.3 分枝定界法3.4 0-1规划的解法3.5 指派问题的解法3.1 引言 在第2章介绍的线性规划模型中, 决策变量取连续型的非负数值,即可以是分数或小数.然而,在许多经济管理的实际问题中,决策变量只能取非负的整数才有实际意义.例如,最优调度的车辆数,设置的销售网点数,指派工作的人数等. 人们对整数规划感兴趣,还因为有些经济管理中的实际问题的解,必须满足逻辑条件和顺序要求等一些特殊的约束条件. 此时,往往需引进逻辑变量(又称0-1变量),以达到表示“是”(用1表示)与“非”(用0表示). 因此,进一步研究变量取非负整数的规划问题是很有必要的.一、基

2、本概念一、基本概念 1. 1.整数规划问题整数规划问题：称所有变量都取非负整数：称所有变量都取非负整数的数学规划问题为的数学规划问题为纯整数规划问题纯整数规划问题. . 2. 2.混合整数规划问题混合整数规划问题：称部分变量取非负整：称部分变量取非负整数的数学规划问题为数的数学规划问题为混合整数规划问题混合整数规划问题. . 3. 3.0-1规划规划:称决策变量均为称决策变量均为0-1变量的整数规变量的整数规划为划为0-1规划规划. 注意注意:整数规划问题是个非线性问题整数规划问题是个非线性问题. 这是因这是因为整数规划的可行解集合是由一些离散的非负整为整数规划的可行解集合是由一些离散的非负整

3、数组所构成数组所构成,而不是一个凸集而不是一个凸集.二、整数线性规划问题的数学模型二、整数线性规划问题的数学模型 本章仅讨论约束条件和目标函数均为线性的本章仅讨论约束条件和目标函数均为线性的整数规划问题整数规划问题, ,即整数线性规划问题即整数线性规划问题( (简称整数规简称整数规划划).).其数学模型的一般形式是其数学模型的一般形式是: :jnjjxcZ1max(min),1,2( 0),2 , 1( . .1njxmibxatsjnjijijxj皆为整数或部分为整数.三、整数规划问题的求解方法 迄今为止, 求解整数规划问题尚无统一的有效算法.一般我们主要采取以下三种方法： (1)舍入取整法

4、；(2)枚举法；(3)隐枚举法. (1)舍入取整法:求解整数规划问题,首先会想到不考虑其整数性约束,而先去求解相应的线性规划问题(称其为松弛问题).然后,将所得的非整数最优解用“舍入取整”的方法得到整数规划的最优解. 但一般来说,用“舍入取整”法得到的解不一定是原问题的最优解,很可能远远偏离最优解,甚至是非可行解.因此,用“舍入取整”法求解整数规划往往不可取. 但由于用整数规划方法 求整数最优解需花费较多的人力和计算机机时, 因此,在处理经济活动中的某些实际问题时,如果允许目标函数值在某一误差范围内,有时也可采用“舍入取整”所得的整数可行解作为原问题整数最优解的近似解. 设 X*是原整数规划问

5、题的最优解, X是其松弛问题的非整数最优解, X 是“舍入取整”得的整数可行解, d为给出目标函数值的允许误差.由于 cX cX*cX ,所以 cX* - cX cX - cX .当cX - cX d 时,则X 可作为X*的近似解. 应该说，此法仅在变量个数很少的情况下才有效，对于变量个数稍多的整数规划问题则不适用. 例如,在3.5节将介绍的指派问题中，当变量数 n =10时，就有10!3106个可行解,当n =20时, 就有20!21018个可行解. 如果一一计算,就是用高速计算机也无法处理,所以,也是不可取的. 为此,有必要对不同的整数规划问题找出有效的特殊解法. 其次，能否考虑将整数规划

6、问题所有可行的整数解完全枚举出来，经过比较其相应的目标函数值,从而得到最优解呢?3.2 整数规划问题及其数学模型(1) 生产计划问题 例1 某工厂生产A1, A2两种产品,产品分别由B1, B2两种部件组装而成.每件产品所用部件数和部件的产量限额以及产品利润由下表给出.应如何安排A1, A2的生产数量,该厂才能获取最大利润?部件产品 B1 B2利润(百元)A1 6 1 15A2 4 3 20部件的最大产量 25 10解 设x1, x2分别表示产品A1和A2的产量,依题意该问题的数学模型是., 0, 010325462015max212121, 21且皆为整数xxxxxxxxZ 这是个纯整数规划

7、问题,又因为约束条件和目标函数的系数全为整数,故亦称全整数规划问题.(2) 投资项目选择问题 例2 某单位有5个拟选择的投资项目,其所需要投资与期望收益如下表所示. 项 目所需投资额(万元)期望收益(万元)A6.010.0B4.08.0C2.07.0 D4.06.0E5.09.0 由于各项目之间有一定联系,A,C,E三项中必须选择而且仅需选择一项;B和D两项中必须选择而且仅需选择一项;又C的实施必须以D的实施为前提条件.该单位共筹集资金15万元,应该选择那些项目投资,使期望收益最大? 解解 考虑到有的项目有可能被选中考虑到有的项目有可能被选中,也有可能也有可能不被选中不被选中,设决策变量设决策

8、变量xj( j =1,2,3,4,5)分别表示项分别表示项目目A,B,C,D,E,且定义且定义10jx( j =1,2,3,4,5)表示项目表示项目 j 不被选中不被选中表示项目表示项目 j 被选中被选中 由于项目由于项目A,C, E三项中必须选择而且仅需三项中必须选择而且仅需选择一项，所以有关系式选择一项，所以有关系式x1+ x3+ x5 = 1. 与此相同，与此相同，B和和D之间也有类似关系式之间也有类似关系式x2+ x4 = 1. 又由于项目C的实施要以项目D的实施为前提,即选中项目C之前必须选中项目D,当然可以只选项目D而不选项目C. 换句话说,若x3= 1,则x4 = 1.而x3=

9、0,则x4 = 0或x4 = 1. 于是有关系式x3 x4 (或记为 x3- x4 0). 所有项目投资总额的限制条件为6x1 + 4x2 + 2x3 + 4x4 + 5x515. 目标函数为期望收益最大,可表示为max Z = 10 x1 + 8x2 + 7x3 + 6x4 + 9x5.归纳起来,该问题的数学模式为jxxxxxxxxxxxxxxxxxxZ1554246011.967810max54321434253154321皆为0或1( j =1,2,3,4,5). 上述模型虽然是一个全整数规划,但与例1不同的是决策变量只限取0或1. 因此,又是0-1规划规划. 显然,利用0-1变量处理一

10、类“选择问题”是非常方便的. 下面再进一步说明各种情况下的“选择”以及相应的数学模型. 假定现有的m种资源对可供选择的 n个项目进行投资的数学模型为求一组变量x1, x2, , xn，使jnjjxcZ1max)., 2 , 1( 10), 2 , 1(1njxmibxajnjijij或满足cj表示投资第表示投资第j项目获得的期项目获得的期望收益望收益aij表示第表示第i种种资源投入第资源投入第j项目的数量项目的数量bi表示第表示第i种资源的限量种资源的限量 如果在可供选择的k(kn )个项目中，必须且只能选择一项，则加入新约束条件11kjjx 如果在可供选择的k(kn )个项目是互相排斥的，或

11、在前k个项目中，至多只能选择一项投资,则加入新约束条件kjjx11 如果在可供选择的k(kn )个项目中，至少应选择一项投资，则加入新约束条件kjjx11 如果项目如果项目j的投资以项目的投资以项目i的投资为前提，则加的投资为前提，则加入新约束条件入新约束条件 如果对第如果对第r种资源与第种资源与第s种资源的投资是互相排种资源的投资是互相排斥的斥的,即只允许对资源即只允许对资源br与与bs中的一种进行投资中的一种进行投资,则则将原约束条件中去掉第将原约束条件中去掉第r个约束条件个约束条件,变成新规划问变成新规划问题题(1);再将原约束条件中去掉第再将原约束条件中去掉第s个约束条件个约束条件,变

12、成变成新规划问题新规划问题(2);然后从两个最优方案中选择一个最然后从两个最优方案中选择一个最佳方案投资佳方案投资.xjxi 如果项目如果项目i与项目与项目j要么同时被选中，要么同时要么同时被选中，要么同时不被选中，则加入新约束条件不被选中，则加入新约束条件xi= =xj(ij) 在生活中经常遇到这样的问题：有n项任务要完成, 恰好有n个人可分别去完成其中的每一项, 但由于各人的专长不同, 各人完成不同任务的效率 (或所花费时间等) 也不同. 于是产生下述问题：应指派哪个人去完成哪项任务, 使完成n项任务的总效率最高 (或花费的总时间最少). 这类问题称为指派指派问题问题(Assignment

13、 Problem). 用cij0 (i, j =1, 2, , n )表示指派第i个人去完成第j项任务时的效率(时间或成本等), (cij )nn称为效率矩阵效率矩阵. 如果设xij = 1表示指派第i个人去完成第j项任务, xij = 0表示指派第i个人不去完成第j项任务, 注意到每项任务只能指派一人去完成, 每人只能完成一项任务, 则指派问题的数学模型为 ninjijijxcZ11min, 2, 1, 1, 2, 1, 1. .11nixnjxtsnjijniijxij0,1. 3.3 分枝定界法一、分枝定界法的基本思想 1.将整数规划问题转化为相应的非整数规划问题考虑. 2.若相应非整数

14、规划问题的最优解满足整数性约束,则它就是原问题的最优解. 否则,就在不满足整数性约束的变量中,任选一个xi=bi,将新的约束条件xibi和xibi+1分别加入到原问题,把原问题分枝为两个子问题(此时不存在遗根问题);再分别去求子问题的最优解. 3.对于最大化问题，其相应非整数规划问题的最优值就是原整数规划问题最优值的上界. 同理对于最小化问题，其相应非整数规划问题的最优值就是原整数规划问题最优值的下界. 以下均对最大化问题进行讨论 1.若子问题的最优解满足整数性约束，则不再分枝，其相应的目标函数值就是原整数规划问题最优值的一个下界. 当该值大于原下界时，则将其定为新的下界. 2. 对不满足整数

15、性约束的子问题,若其最优值大于下界时,则继续分枝;若其最优值不大于下界，则停止计算(不再分枝). 3.若某个子问题无可行解，则相应整数规划问题也无可行解，停止计算(不再分枝). 4.求解子问题的顺序按“后进先出”的原则.分枝定界法的方法步骤求解下列整数规划问题., 0, 010325462015max212121, 21且皆为整数xxxxxxxxZ(1)先不考虑整数性约束，求解相应的非整数规划问题. 0, 010325462015max212121, 21xxxxxxxxZ0所得最优解为x1 = 2.5, x2 = 2.5，最优值为Z = 87.5Z = 87.5就是原整数规划问题最优值的上界

16、.并令其下界 Z = 0. (2)在不满足整数性约束的变量中,任选一个(比如x1 = 2.5). (2)在不满足整数性约束的变量中,任选一个(比如x1 = 2.5),将新的约束条件x12和x13分别加入到原问题,把原问题分枝为两个子问题： . 0, 0210325462015max2112121, 21xxxxxxxxxZ . 0, 0310325462015max2112121, 21xxxxxxxxxZ (3)不妨先求解子问题，而将子问题暂时记录下来，待求解. 子问题的最优解 x1 = 2, x2 = 8/3 = 2.67和 max Z = 250/3 = 83.3. 由于子问题的解中仍有

17、x2不是整数,所以应该对子问题分别增加新的约束条件x22和x23,将子问题再分枝为两个子问题： . 0, 02210325462015max21212121, 21xxxxxxxxxxZ . 0, 03210325462015max21212121, 21xxxxxxxxxxZ (4)将子问题暂时记录下来，待求解.用同样的方法求解子问题，得其最优解x1 = 2, x2 = 2和 max Z = 70. (5)按所记录下来待求解问题的顺序，依“后进先出”的原则，分别进行求解.用同样的方法求解子问题： . 0, 03210325462015max21212121, 21xxxxxxxxxxZ 得其

18、最优解x1 = 1, x2 = 3和 max Z = 75. 得到整数解，不再分枝.同时修改原来的下界为 Z = max 70,75 = 75. (6)再求解子问题： 得其最优解x1 = 3, x2 = 1.75和 max Z = 80. 由于Z = 80Z = 75，因此需对子问题再进行分枝为子问题和子问题. . 0, 0310325462015max2112121, 21xxxxxxxxxZ 对子问题进行分枝为子问题和子问题： . 0, 01310325462015max21212121, 21xxxxxxxxxxZ . 0, 02310325462015max21212121, 21xx

19、xxxxxxxxZ (7)求解子问题，得其最优解x1 = 3.5, x2 = 1和 max Z = 72.5. 虽然不是整数解，但max Z = 72.5Z = 75，不再分枝. (8)求解子问题，无可行解，不再分枝. 求解过程的流程图如下：问题 (0)x1 = 2.5, x2 = 2.5 max Z = 87.5问题 x1 = 1, x2 = 2.67 max Z = 83.3问题 x1 = 3, x2 = 1.75 max Z = 80问题 x1 = 2 x2 = 2 Z = 70问题 x1 = 1x2 = 3Z = 75问题 x1 = 3.5x2 = 1Z = 72.5问题 无可行解 求

20、解0-1规划的方法，常见的有两种，即完全枚举法和隐枚举法.3.4.1 完全枚举法 完全枚举法的基本思想是，首先将全部变量取0或1的所有组合(解)列出，然后，再逐个检查这些组合(解)是否可行的过程中，利用增加并不断修改过滤条件的办法，减少计算量，达到求出最优解之目的. 下面通过例子来说明其方法步骤.用完全枚举法求解0-1规划问题max Z= 17x1+ 10 x2+ 16x3, 4x2+ 2x365x1+ x2+ 2x364x1- 2x2+ 3x375x1+ 2x2+ 3x37xj=0或1( j =1,2,3)解 (1)列出变量所有的解，共有23=8个. (2)增设过滤条件. 设法找出一个可行解

21、，如Z(0,0,0)=0，因问题是最大化，可增设过滤条件17x1+ 10 x2+ 16x3 0(3)寻求最优解A约束条件(0,0,0)(0,0,1)(0,1,0)(0,1,1)(1,0,0)(1,0,1)(1,1,0)(1,1,1)1234Z值 4x2+ 2x365x1+ x2+ 2x364x1- - 2x2+ 3x375x1+ 2x2+ 3x371234 0 0A增设过滤条件17x1+10 x2+16x30 16修改16 26修改26 27修改27 至此，最优解为至此，最优解为(1,1,0)；最优值为；最优值为27.3.4.2 隐枚举法 由于0-1规划问题的特殊性，任何0-1规划均可化为如下

22、标准形式：njjijnjjjxaxcZ11maxbi, (i = 1, 2, , m )xj=0或1 ( j =1,2, , n )(所有cj 0) (2)若某个cj0，令1 xj = yj，其中yj为0 - 1变量，则yj在目标函数中的系数Cj0 ; (1) 若目标函数为最小化，即minZ = CX,只须令Z= -Z，则可化为max Z= -CX ; 以下讨论如何将以下讨论如何将0-1规划问题的一般形式化规划问题的一般形式化为标准型为标准型. (3)若在第i个约束方程中，约束条件为“ ”形式，则可对约束方程两边同时乘以-1，变为“”形式；AX = b 等价于bAXbAX (4)若约束条件含有

23、等式，则有隐枚举法的基本思想 隐枚举法是一种特殊的分枝定界法，其基本思想是:首先令全部变量取0，如果此解可行，则为最优解，计算终止. 否则，有选择地指定某个变量为0或1，将问题分枝为两个子问题,令其余的变量全部为0, 如果此解可行，则取相应的目标函数值为下界. 当某个子问题的目标函数值小于下界或找到其可行解，不再分枝. 对每一个子问题如此进行，直到不再分枝或所有的变量都被指定为止. 参看P83-87.max Z= 17x1 +10 x2 +16x3, 4x2+ 2x3 65x1 + x2+ 2x3 64x1 -2x2+ 3x3 75x1+2x2+ 3x3 7xj=0或1( j =1,2,3)用

24、隐枚举法求解0-1规划问题max Z= 4317y110y216y3, 4y22y305y1 y22y324y1 + 2y23y3 25y12y23y33yj=0或1( j =1,2,3)得标准形令 x1=1-y1, x2=1-y2, x3=1-y3max S= 17y110y216y3, 4y2 2y30 (1)5y1 y2 2y32 (2)4y1 + 2y23y32 (3)5y12y23y33 (4)yj=0或1( j =1,2,3)变形 令(y1,y2,y3)=(0,0,0),不满足约束条件 (2) , (4) 所以(y1,y2,y3)=(0,0,0)为非可行解,但S=0为目标函数的上界

25、,记为S=0令 y1 =1,其余变量为零 得 max S= 17, 0 0 (1) 52 (2) 4 2 (3) 53 (4)4个约束条件均满足,总距离=0max S= 17y110y216y3, 4y2 2y30 (1)5y1 y2 2y32 (2)4y1 + 2y23y32 (3)5y12y23y33 (4)yj=0或1( j =1,2,3)2个约束条件不满足总距离 = 2得 max S= 10, 4 0 (1) 1 2 (2) 2 2 (3) 2 3 (4)令 y2 =1,其余变量为零max S= 17y110y216y3, 4y2 2y30 (1)5y1 y2 2y32 (2)4y1

26、+ 2y23y32 (3)5y12y23y33 (4)yj=0或1( j =1,2,3)令 y3 =1,其余变量为零 得 max S= 16, 2 0 (1) 22 (2) 3 2 (3) 33 (4)4个约束条件均满足,总距离=0max S= 17y110y216y3, 4y2 2y30 (1)5y1 y2 2y32 (2)4y1 + 2y23y32 (3)5y12y23y33 (4)yj=0或1( j =1,2,3)考虑到目标函数的取值,令y3=1,0分枝max S= 17y110y216, 4y2 2 (1)5y1 y2 0 (2)4y1 + 2y2 5 (3)5y12y2 0 (4)y

27、j=0或1( j =1,2,)问题(1),令y3=1,max S= 17y110y2, 4y2 0 (1)5y1 y2 2 (2)4y1 + 2y2 2 (3)5y12y2 3 (4)yj=0或1( j =1,2,)问题(2),令y3=0,指派问题的数学模型为ninjijijxcZ11min, 2, 1, 1, 2, 1, 1. .11nixnjxtsnjijniijxij0,1. C=(cij )nn为效率矩阵效率矩阵. 指派问题是一种特殊的0-1规划问题，有如下性质：若从效率矩阵C的任何一行(列)各元素中分别减去一个常数k后, 其最优解不变，但其最优值比原问题的最优值小k. 求解指派问题的

28、匈牙利算法 变换效率矩阵，使变换后的效率矩阵的每行每列都出现0元素. 依次对效率矩阵的每行每列的各元素分别减去该行该列的最小元素. 求最优指派方案. 从含零元素最少的行中选择一个0元素表示一种指派，然后暂时删除该指派所在的行和列，重复进行直到剩下的矩阵中没有0元素为止. 如果已得到n种指派则计算终止，否则进入第步. 作最少直线数覆盖所有0元素. 对没有被指派的0元素所在的行打号； 对打号的行上所有没有被指派的0元素所在的列打号； 再对打号的列上被指派的0元素所在的行打号； 重复直到没有可打号的行列为止. 然后对所有没有打号的行画横线，对所有打号的列画竖线. 可以证明这些直线覆盖了所有的0元素，且直线数是最少的，它等于已被指派的0元素的个数. 变换新矩阵，使之增加新的0元素. 在没有被直线覆盖的元素