整数规划习题

1、第五章整数规划习题5.1考虑下列数学模型min z 二 fi(xjf2 (x2)且满足约束条件(1) 或 X1 -10，或 X2 -10 ；(2) 下列各不等式至少有一个成立:2x1 x2 - 15“ +x2 H15x1 +2x2 215(3)% x2或5或10(4)x0x2 0其中20+ 5%,如 a 0 f1 (x1) = 0,如花=012 + 6x2,如 x2 a0 f 2 ( X2 ) = 0,如 x2 = 0将此问题归结为混合整数规划的模型解：min z =10力 5x112y2 6x2(0)X1 W y1 M ； X2 兰 y2 M(1) X1 =10 - y3 *MX2 兰 10

2、_(1 _y3)M(2) x1 + x2 王 15 - y4MX1 + X2 K15 - ysM x1 +2x2 王15 - y6My4 + y5 + y6 兰 2(3) X1 -X2 = 0y7 -5y8 +5yg T0y1o + 11yn y7 + y8 + y9 + ye + yn =1(4) x1 -0, X2 -0;yi -0或 1(if *,11)5.2试将下述非线性的0-1规划问题转换成线性的0-1规划问题max z = x； + x2x3 -x；一 2X! +3x2 十 x3 兰 3j =0或 1,( j =123)1 ，当 x2 =x3 =1解：令y = P ，否则23故有X

3、2X3二y，又xi , xi分别与Xi, X3等价，因此题中模型可转换为max = x1 y - x3一 2xi + 3x2 + x3 兰 3y兰X2* y 兰 X3x2 + x3 兰 y 十1 x1,x2, x3, y均为 0 -1 变量5.3某科学实验卫星拟从下列仪器装置中选若干件装上。有关数据资料见表5-1 表5-1仪器装置代号体积重量实验中的价值AV1wC1AV2wC2AV3W3C3AV4wC4AV5wC5AV6wC6要求：（1）装入卫星的仪器装置总体积不超过 V,总质量不超过 W（ 2）A与A 中最多安装一件；（3）A与A中至少安装一件；（4）A同A或者都安上，或者都 不安。总的目的

4、是装上取的仪器装置使该科学卫星发挥最大的实验价值。 试建立 这个问题的数学模型。解：6max z 八 cj xjj仝$ 6Z VjXj 兰Vjm6Z WjXj EWu為+ x3兰1x2 + x4 畠 1X5 = X61 ，安装Aj仪器Xi =、0，否则5.4 某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探 费用最小。若10个井位的代号为S1 , S2,S10,相应的钻探费用为C1 , C2,C10, 并且井位选择上要满足下列限制条件：(1)(2)(3)或选择S1和S7,或选择钻探S8； 选择了 S3或S4就不能选择S5,或反过来也一样； 在S5,S 6,S 7,S 8,中最

5、多只能选两个；试建立这个问题的整数规划模型。解:10min z _ 7 cj xjj =10二Xj =5j 4X1X8=1x7x8=1X5X6X7X3 X5 -1X4 X5 _ 1X8乞21,选择钻探第Sj井位0 ，否则5.5用割平面法求解下列整数规划问题(a) max z= 7x1 9x2-x3x2 - 6 7Xj + x2 兰 35 x1 ,x20且为整数minz = 4x1 5x23xj +2x2 兰7Xj +4x2 王53X1 X2 _2 xx2 _ 0且为整数max z = 4为 6x2 2x3(b)(c)(d)4x! -4x2 兰 5-Xi 6x2 - 5一為 x2 X3乞5x2,

6、x3, -0且为整数max z = 11捲 4x2x, +2x2 互斥性约束i =1,2; j =1,2,3;6 =0或 1,Xj 05.11 某电子系统由三种元件组成，为使系统正常运转，每个元件都必须工作良 好。如一个或多个元件安装几个备用件将提高系统的可靠性。 已知系统运转可靠 性为各元件可靠性的乘积，而每一元件的可靠性则是备用件数量的函数， 具体数 值见表5-5 o表5-5备用件数元件可靠性12300.50.60.710.60.750.920.70.951.030.81.01.040.91.01.051.01.01.0又三种元件分别的价格和重量如表 5-6所示。已知全部备用件的费用预算限

7、制为 150元，重量限制为20千克，问每个元件各安装多少备用件（每个元件备用件 不得超过5个），是系统可靠性为最大。试列出这个问题的整数规划模型。表5-6元件每件价格（元）重量（千克/件）120223043406解：用x,x,x分别表示1, 2, 3三个元件安装的备用件数量。根据题中条件及费 用、重量的限制，元件1的备件最多安装5个，元件2备件最多5个，元件3 的备件最多安装3个。故问题的数学模型可表示为：maxz 二(0.5y10.6y20.7y30.8y40.9y5y6)(0.6y70.75y80.95y9%。)(0.7yn0.9%2yj20捲 + 30x2 +40x3 M1502x1 +

8、 4x2 十 6x3 兰 206Z yi =1710正yi =1i=Z13送yi =1i 41Xj X0(j =1,2,3)y =0或1(i =1,.,13)5.12用你认为合适的方法求解下述问题：max z = x2x2 5x3+10x2 3x3 152捲 +x2 +x3 兰 10兀必必A0解：将问题改写为max z = x2x2 5x3乂 一10x2 +3x3 兰15 + My厂为 +10x2 3x3 兰15 + (1 y)M2论 + x2 + x3 兰 10、Xj 兰 0( j =1,2,3), y =0或 1求解得 X1=0,X2=0,x 3=10,y=1,z=505.13下述线性规划

9、问题max z= 20x-i 10x210x32x120x2 4x3 三156x120x2 4x3 = 20x1,x2,x0,且取整数值说明能否用先求解相应的线性规划问题然后凑整的办法来求得该整数规划的一 个可行解。解：当不考虑整数约束，求解相应线性规划得最优解为 X1=10/3,x 2=X3=0。用凑整 法时令X1=3,X2=X3=0,其中第2个约束无法满足，故不可行。5.14 某市为方便学生上学，拟在新建的居民小区增设若干所小学。 已知备选校 址代号及其能覆盖的居民小区编号如表 5-7所示，问为覆盖所有小区至少应建多 少所小学，要求建模并求解。表5-7备选校址代号覆盖的居民小区编号A1,5

10、,7B1,2,5C1,3,5D2,4,5E3,6F4,61 ,在第i备选校址建校x =解:令 0 ，否则min z = xa xb xc xd xe xf Xa +Xb +XcXa+Xb +Xc +XdXb +Xd 1Xc Xe -1 Xe Xf - 1Xd Xf -1 Xa -1答案为在A, D, E三个备选校址建校。5.15已知下列五名运动员各种姿势的游泳成绩（各为50米）如表5-8所示，试问如何从中选拔一个参加200米混合泳的接力队，使语气比赛成绩为最好。表5-8单位：秒赵钱张王周仰泳37.732.933.837.035.4蛙泳43.433.142.234.741.8蝶泳33.328.5

11、38.930.433.6自由泳29.226.429.628.531.1解：由下列运动员组成混合接力队：张游仰泳，王游蛙泳，钱游蝶泳，赵游自由 泳，预期总成绩为126.2秒。5-16 用匈牙利法求解下述指派问题，已知效率矩阵分别如下:(a)（b）解：（a）最优指派方案为（b）最优指派方案为5-17从甲、乙、丙、丁、7910121312161715161415111215163821087296427842391069375510X13=X22=X34=X41=1,最优值为 48；X15=X23=X32=X44=X51=1 ；最优值为 21 戊五人中挑选四人去完成四项工作。已知每人完成各 每个人最

12、项工作的时间如表5-9所示。规定每项工作只能由一个人去单独完成, 多承担一项任务。又假定对甲必须保证分配一项任务，丁因某种原因决定不同意承担第4项任务。在满足上述条件下，如何分配工作，使完成四项工作总的花费 时间为最少。表5-9X作人甲乙丙丁戊1102315925101524315514715420151368解：先增加一种假想工作5,再据题中给的条件列出表5A-9表 5A-8工作人甲乙丙丁戊11023159251015243155147154201513OO85OO0000对表5A-9用匈牙利法求解得最优分配方案为：甲-2，乙-3，丙-1，戊-4，对丁 不分配工作。5-18设有m个某种物资的生产点，其中第i个点（i=1，m的产量为a。 该种物资销往n个需求点，其中第j个需求点所需量为bj （j=1，n）。已知7 aibji j。已知。又知从各生产点往需求点发运时，均需经过p个中间编组站之一转运，若启用第k个中间编组站，不管转运量多少，均发生固定费用f，而第k个中间编组站转运最大容量限制为 qk （k=1，p）。用Cik和c分别表 示从i到k和从k到j的单位物资的运输费用，试确定