整数规划的数学模型及解的特点

《整数规划的数学模型及解的特点》由会员分享，可在线阅读，更多相关《整数规划的数学模型及解的特点（16页珍藏版）》请在装配图网上搜索。

1、整数规划的数学模型及解的特点整数规划IP (integer programming) :在许多规划问题中，如果要求一部分或全部决策变量必须取整数。例如，所求的解是机器的台数、人数、车辆船只数等，这样的规划问题称为整数规划，简记 IP。松弛问题(slack problem):不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若松弛问题是一个线性规化问题，则该整数规划为整数线性规划(integerlinear programming) 。一、整数线性规划数学模型的一般形式nmax(或 min)Z = " cjxjj =1nst工 aj Xj -（-,二

2、）bij 1Xj 0i =1,2,., n j =1,2,mX, x2，xn中部分或全部取整数整数线性规划问题可以分为以下几种类型1、纯整数线性规划(pure integer linear programming):指全部决策变量都必须取整数值的整数线性规划。有时，也称为全整数规划。:指决策变量中有2、混合整数线性规划(mixed integer liner programming)一部分必须取整数值，另一部分可以不取整数值的整数线性规划3、01 型整数线性规划(zero -one integer liner programming) :指决策变量只能取值0或1的整数线性规划。1解整数规划问题

3、max z = 3x1 x2'3xi -2x2£35x1 +4x2 之 102x1 x2 £ 5x1,x2 > 0且为整数max z = x1 x29: 51x1x2 一1414c1- 2x1x2三 3.Xi，X2i0且为整数0- 1型整数规划0-1型整数规划是整数规划中的特殊情形，它的变量仅可取值0或1,这时的变量xi称为01变量，或称为二进制变量。01型整数规划中01变量作为逻辑变量(logical variable) ,常被用来表示系统是否处于某一特定状态，或者决策时是否取某个方案。1如果决策i为是或有x 二i 10如果决策i为否或无一、0-1型整数规划

4、的典型应用问题例1：背包问题：一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量和重要性系数如表所示。设登山队员可携带的最大重量为 25kg,试选择该队员所应携带的物品。序号1234567物品食品氧气冰镐绳索帐篷照相器材通信设备重量/Kg55261224重要性系数201518148410解：引入01变量xi, xi=1表示应携带物品i , ,xi=0表示不应携带物品i naxz = 20x1 15x2 18x3 14x4 8x5 4x6 10x75x1 + 5x2 + 2x3 + 6x4 + 12x5 + 2x6 + 4x7 w 25 -xi

5、= 0或 1,i =1,2,7上述问题就是一个标准的0-1 整数规划问题，解得：X*=(1,1,1,1,0,1,1)Z*=81例2:集合覆盖和布点问题某市消防队布点问题。该市共有 6个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发生火警时， 消防车要在15min 内赶到现场。据实地测定，各区之间消防车行驶的时间见表，请制定一个布点 最少的计划。地区1地区2地区3地区4地区5地区6地区101016282720地区210024321710地区316240122721地区428321201525地区527172715014地区620102125140解：引入01变量

6、xi, xi=1表示在该区设消防站，xi=0表示不设min z = x1 x2 x3 x4 x5 x6x1x21XiX2X6- 1X3X4- 1X3X4X51X4X5X6- 1X2X5X6- 1,Xi = 1或 0解得:X*=(0,1,0,1,0,0)'Z*=2二、特殊约束的处理1 .矛盾约束：建模时，有时会遇到相互矛盾的约束，而模型只能两者取一或,例如下面两个约束f(x) - 3f(x) 三0(2)先不等式同向处理，原式可化为:3- f (x) M 0 (3)f (x)三 0 (4)再引入一个01变量y,及一个很大的正数 M3 - f (x) 三 My (5)f(x) 'M(

7、Jy) (6)y=0时,(5)与(1)相同,(6)自然满足，实际上不起作用y=l时,(6)与(2)相同,(5)自然满足，实际上起作用f(x) - a(a > 0)对于形似' ''',可以用以下一对约束代替f(x) - af(x) - - a约束同向处理，改为-f (x) - -a- f (x) - - a Myf(x)v-a 引入 01 受重后，f (x) = - a + M (1 - y)2 .多中选一的约束模型希望在下列几个约束中，只能有一个约束有效：fi(x) £ 0 (i = 1,2,n) (1)引入n个0 1整数变量yi, i=1,2,

8、0.fi(x)v M(1-y) (i = 1,2,.,n) (2)yi Y2 . Vn 1 1(3)则上式可改写为：yi=0时，(2)自然满足，此时约束不起作用yi=1时，约束起作用。而和式保证了在01整数变量中有一个且也只有一个取值1,其余取0值。若希望有k个约束有效，只需将(3)改为V1y2yn = k3、某市为方便学生，拟在新建的7个居民小区增设若干所学校。已知各备选校址代号及其能覆盖的居民小区编号如表1所示，问要覆盖所有居民小区至少应建多少所学校？对应的校址代号是哪些？表1备选校址ABCDEF小区编号1, 5, 71, 2, 51, 3, 52, 4, 53, 64, 6解：对每一个学

9、校定义一个变量xj广1,当某居民小区可由第j个学校负责Xj ,当某居民小区不可由第j个学校负责则对于第1个小区：x1 + x2 + x3 -1对于第2个小区：X2+X4力对于第3个小区：x3 +X5 -1对于第4个小区：。+徐)对于第5个小区：X#X2+X3+X4)对于第6个小区：% +对于第7个小区：X1=16XjMin z ="T解得：X = 1，0，0,1,1，0Z*=3例2 有两个相互排斥的约束条件5x1 +4x2 <24 或 7X1 +3x2 <45o为了统一在一个问题中，引入。-1变量y,则上述约束条件可改写为:5x1 + 4x2 £24 + yM*

10、7X1 +3X2 <45 +(1 y)MJ =0或1其中M是充分大的数。500y M X1 三 800y例3约束条件x1 = 0或500 'x1' 800可改写为y = 0或 13.1.3 关于固定费用的问题(Fixed Cost Problem ) 在讨论线性规划时，有些问题是要求使成本为最小。那时总设固定成本为常数，并在线性规划的模型中不必明显列出。但有些固定费用（固定成本）的问题不 能用一般线性规划来描述，但可改变为混合整数规划来解决，见下例。例5某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定的生 产方式投资高（选购自动化程度高的设备），由于产量大，因

11、而分配到每件产品 的变动成本就降低；反之，如选定的生产方式投资低，将来分配到每件产品的 变动成本可能增加。所以必须全面考虑。今设有三种方式可供选择，令xj表示采用第j种方式时的产量；cj表示采用第j种方式时每件产品的变动成本；kj表示采用第j种方式时的固定成本。为了说明成本的特点，暂不考虑其它约束条件。采用各种生产方式的总成本分别为K +5 3 >0Pj =j I0,当Xj=0 j =1,2,3.在构成目标函数时，为了统一在一个问题中讨论，现引入0-1变量yj,令1,当采用第j种生产方式，即xj > 0时，y i 二j0,当不采用第j种生产方式，即xj = 001于是目标函数min

12、 z= （kiyi+qx。+（k2y2+C2X2）+（k3y3 +C3X3）（3）式这个规定可表为下述3个线性约束条件：yj 名 WXj WyjM, j =1,2,3（4）其中s是一个充分小的正常数，M是个充分大的正常数。（4）式说明，当xj >0时4）式完全可以代替（3）yj必须为1;当xj =0时只有yj为0时才有意义，所以（ 式。3 8 28 7 26 4 28 4 29 10 6例8求解下列指派问题，已知指派矩阵为10 39775359 10-，求最小指派问题数学模型为：Min z=3*x11+8*x12+2*x13+10*x14+3*x1555' ' aij *

13、 xij+8*x21+7*x22+9*x51 + 10*x52+6*x53+9*x54+10*x55X11+x12+x13+x14+x15=15; xj =1 i =1.5jmX51+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=3 8 2 10 38 7 2 9 76 4 2 7 58 4 2 3 59 10 6 9 10;enddatamin = sum

14、(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)|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号上场，贝U 6号不出场

15、；y=x1+x4 ,if y=2 x6=0X1 <= x62号和6号至少保留一个不出场。X2+x6 <=1应当选择哪5名队员上场，才能使出场队员平均身高最高？公司生产A B C三种产品，售价分别为12元、7元和6元。生产每单位A需要1小时技术服务、10小时直接劳动、3千克材料；生产每单位 B需要2小时技术服务、4小时直接劳动、2千克材料；生产每单位C需要1小时技术服务、5小时直接劳动、1千克材料；现在最多能提供100小时技术服务、700小时直接劳动、400千克材料；生产成本是生产量的非线性函数，如下所示:产品A产品B产品C心且 ）上单位成本（元）心且 ）上单位成本（元）040100

16、506401009510041001508100以上3150以上7心且 ）上单位成本（元）01005100以上4要求建立一个总利润最大的生产计划数学模型。设产品A的产量为不，且%1*01,其他0 M x1 三 40%2=,°1,其他40 二 x <1000 y13 = 1,其他100 x1 <150%4 二1°'其他x1 150设产品B的产量为x2,且:0 y21 = 1,其他0 三 x2 M 500 y22 = 1,其他50 ：二 x2 三 100ro,其他y23 :1, x2 100设产品C产量为七,且:0y31 二1，其他0 < x3 <

17、;100Q 其他y32 :1,x3 100设总利润为：yMax y = 12-(10yn9y128y137y14)lx11.7 -(6y214y223y23)h16-(5y314y32)屋x1 +x2 +x3 <100,10x1 +42x2 +5x3 <700,3x1 +2x2 +x3 <400y11 + y12 +y13 + y14 =1,y21 + y22 + y23 = 1, y31 + y32 =10 Ex1yli <40,40 :二 x1y12 £100,100 < x1y13 <150St </ / "x1yl4 >

18、;150,0 < x2 y21 <50,50 < x2 y22 <100,x3y23 >100,0 Ex3y31 <100,x3y32 >100, xj 之0(j =1,2,3)=0或1(j =1,2,3), y2j =0或1(j =1,2,3), y3j =0或1(j =1,2)2某钻井队要从以下10个可供选择的井位中确定5个钻井采油，目的是使总 的钻井费用最小。若10个钻井位代号为 s,S2JM,S1。，相应的钻控费用为Gd,，并且井位的选择要满足下列条件：若选择G和a ,或选择钻探S8:选择了 S3或S4,就不能选择S5,反过来也是一样。在ss&

19、amp;s。中最多只能选择两个。试建立这个问题的整数规划模型。设Xj=0或1,其中Xj =0代表Sj点未入选，Xj*代表Sj点入选；于是可构造如下数学模型:10maxz - '、： Cjxjj 1x Xi +% =1X7 +X8 =1X3 +X5 <1X4 +X5 <1X X5 X6 X7 X3 -210Z Xj =5j % =0oU(j =1,2|”,10)考虑下列数学模型min Z = f(%) g(X2)其中f(X1)10 + 6X1，若 X1 > 00,若 X1 =0g(X2)=，15 十 10x2,若x2 > 00,若 X2=0满足约束条件(1) x1 A8或 x2>6(3) x1+2x2A20、2x1+x2A20及x1+x2A20三个约束中至少一个满足将此问题归结为混合整数规划的数学模型。