(完整word版)整数规划的数学模型及解的特点

1、整数规划的数学模型及解的特点整数规划IP(integerprogramming):在许多规划问题中，如果要求一部分或全部决策变量必须取整数。例如，所求的解是机器的台数、人数、车辆船只数等，这样的规划问题称为整数规划，简记IP。松弛问题(slackproblem):不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若松弛问题是一个线性规化问题，则该整数规划为整数线性规划(integerlinearprogramming)。一、整数线性规划数学模型的一般形式max(或min)Z=fcxjjj=1s.thax,=)bijjij=1x0ji=1,2,.,nj=1,2

2、,.mx,x，x中部分或全部取整数12n整数线性规划问题可以分为以下几种类型1、纯整数线性规划(pureintegerlinearprogramming)：指全部决策变量都必须取整数值的整数线性规划。有时，也称为全整数规划。2、混合整数线性规划(mixedintegerlinerprogramming)：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。3、01型整数线性规划(zerooneintegerlinerprogramming):指决策变量只能取值0或1的整数线性规划。1解整数规划问题maxz=3x+x12TOC o 1-5 h z3x-2x10122x+x0且

3、为整数12129+x142maxz=x+x5110且为整数01型整数规划01型整数规划是整数规划中的特殊情形，它的变量仅可取值0或1，这时的变量xi称为01变量，或称为二进制变量。01型整数规划中01变量作为逻辑变量(logicalvariable),常被用来表示系统是否处于某一特定状态，或者决策时是否取某个方案。1如果决策i为是或有XVio如果决策i为否或无一、01型整数规划的典型应用问题例1：背包问题：一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量和重要性系数如表所示。设登山队员可携带的最大重量为25kg,试选择该队员所应携带的物品。序

4、号1234567物品食品氧气冰镐绳索帐篷照相器材通信设备重量/Kg55261224重要性系数201518148410解：弓I入01变量xi,xi=1表示应携带物品i，,xi=0表示不应携带物品inaxz=20 x+15x+18x+14x+8x+4x+10 x1234567+5x+2x+6x+12x+2x+4xW25234567上述问题就是一个标准的0-1整数规划问题，解得X*=(1,1,1,1,0,1,1)Z*=81例2：集合覆盖和布点问题某市消防队布点问题。该市共有6个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发生火时，消防车要在15min内赶到现场。据实

5、地测定，各区之间消防车行驶的时间见表，请制定一个布点最少的计划。地区1地区2地区3地区4地区5地区6地区101016282720地区210024321710地区316240122721地区428321201525地区527172715014地区620102125140解：弓I入01变量xi,xi=1表示在该区设消防站,xi=0表示不设minz=x+x+x+x+x+x123456112x+x+x1126x+x134Vx+x+x1345x+x+x1456x+x+x1256x=1或0i解得：X*=(0,1,0,1,0,0)Z*=2二、特殊约束的处理矛盾约束：建模时，有时会遇到相互矛盾的约束，而模型只

6、能两者取一或例如下面两个约束f(x)3(1)f(x)0(2)先不等式同向处理，原式可化为：3-f(x)0f(x)0(4)再引入一个0-1变量y,及一个很大的正数M,3-f(x)My(5)f(x)a(a对于形似f(x)af(x)-a约束同向处理，改为-f(x)-af(x)-a0)，可以用以下一对约束代替-f(x)-a+My引入01变量后，f(x)-a+M(1-y)多中选一的约束模型希望在下列几个约束中，只能有一个约束有效f(x)0(i=1,2,n)(1)i引入n个01整数变量yi,i=1,2,n.TOC o 1-5 h zf(x)1123x+x124对于第3个小区：x+x135对于第4个小区：对

7、于第5个小区：x+x+x+x11234对于第6个小区：x+x156对于第7个小区：丈XMinz=j=1j解得：X*=(l,0,0,l,l,0)Tz*=3例2有两个相互排斥的约束条件5x+4x2412或7x+3x45。为了统一在一个问题中，引入o-1变量y，则上述约束条件可改写为:5x+4x24+yM127x+3x45+(1y)M12y=0或1其中M是充分大的数。例3约束条件x二0亠500 x8001或1可改写为500yx1y二0或10P=彳jjjjj0,当x=0l当jj=1,2,3.在构成目标函数时，为了统一在一个问题中讨论，现引入o-1变量y7，令1当采用第/种生产方式，即Xj0时，y=仁j

8、0,当不采用第种生产方式，即Xj=0时j于是目标函数minz=（ky+cx）+（ky+cx）+（ky+cx）TOC o 1-5 h z111122223333（3）（3）式这个规定可表为下述3个线性约束条件：yx0时yj必须为1;当xj二0时只有为0时才有意义，所以式完全可以代替式。例8求解下列指派问题，已知指派矩阵为TOC o 1-5 h z38210387297642754235求最小指派问题。106910数学模型为：ijijj=1i=1Minz=3*x11+8*x12+2*x13+10*x14+3*x15+8*x21+7*x22+9*x51+10*x52+6*x53+9*x54+10*x

9、55X11+x12+x13+x14+x15=1工x=1i=1.5ijj=1X51+x52+x53+x54+x55=1X11+x21+x31+x41+x51=1X15+x25+x35+x45+x55=1Xi,j=0,1Lingo程序为：model:sets:row/1.5/:;col/1.5/:;link(row,col):a,x;endsetsdata:a=382103872976427584235106910;enddatamin=sum(link(i,j):a(i,j)*x(i,j);for(row(i):sum(col(j):x(i,j)=1);for(col(j):sum(row(i)

10、|i#le#2:x(i,j)+sum(row(i)|i#ge#3:x(i,j)=1);end篮球队需要选择5名队员组成出场阵容参加比赛。8名队员的身高和擅长位置见下表：队员身高（米）擅长位置11.92中锋21.90中锋31.88前锋41.86前锋51.85前锋61.83后卫71.80后卫81.78后卫出现阵容应满足以下条件：中锋只能有一个上场；x1+x2=1至少有一名后卫；x6+x7+x8=1如1号和4号上场，则6号不出场；y=x1+x4,ify=2x6=0X1=x62号和6号至少保个不出场。X2+x6=1应当选择哪5名队员上场，才能使出场队员平均身高最高？22公司生产A、B、C三种产品，售价

11、分别为12元、7元和6元。生产每单位A需要1小时技术服务、10小时直接劳动、3千克材料；生产每单位B需要2小时技术服务、4小时直接劳动、2千克材料；生产每单位C需要1小时技术服务、5小时直接劳动、1千克材料；现在最多能提供100小时技术服务、700小时直接劳动、400千克材料；生产成本是生产量的非线性函数，如下所示：设产品A的产量为xi，且Jo,其他人|1,0 x401J0,其他人1,100 x1501设产品B的产量为x2，且=Jo,其他y21|1,0 x5021214o,1,o,1,o,1,其他40 x1501其他50 x1002设产品C产量为X3,且:31o,1,其他0 x1003设总利润

12、为：yTOC o 1-5 h zMaxy=12-(10y+9y+8y+7y)x+【7-(6y+4y+3y)x+【6-(5y+4y)x111213141212223231323x+x+x100,10 x+42x+5x700,3x+2x+x40023123123y+y+y+y=1,y+y+y=1,y+y=112131421222331320 xy40,40 xy100,100 xy150,0 xy50,50 xy100,0 xy100,x0(j=1,2,3)323331332jy=0或1(j=1,2,3),y=0或1(j=1,2,3),y=0或1(j=1,2)1j2j3j2某钻井队要从以下10个可供选择的井位中确定5个钻井采油，目的是使总的钻井费用最小。若10个钻井位代号为S1,S2,S10,相应的钻控费用为分，C10，并且井位的选择要满足下列条件：若选择S1和S7，或选择钻探S8:选择了S3或S4，就不能选择S5，反过来也是一样。在S2,S6,S9,S10中最多只能选择两个。试建立这个问题的整数规划模型。设S=0或1，其中j=0代表j点未