运筹学：整数规划习题与答案

练习4.9 连续投资问题某公司现有资金10万元,拟在今后五年内考虑用于下列项目的投资:项目A:从第一年到第四年每年年初需要投资,并于次年收回本利115%,但要求第一年投资最低金额为4万元,第二.三.四年不限.项目B:第三年初需要投资,到第五年末能收回本利128%,但规定最低投资金额为3万元,最高金额为5万元.项目C:第二年初需要投资,到第五年末能收回本利140%,但规定其投资金额或为2万元,或为4万元,或为6万元,或为8万元.项目D:五年内每年年初都可购买公债,于当年末归还,并获利6%,此项目投资金额不限. 试问该公司应图和确定这些项目的每年投资金额,使到第五年末拥有最大的资金收益.(1) x 为项目各年月初投入向量。

(2) ij x 为 i 种项目j 年的月初的投入。

(3) 向量c 中的元素ijc 为i 年末j 种项目收回本例的百分比。

(4) 矩阵A 中元素ija 为约束条件中每个变量ijx 的系数。

(5) Z 为第5年末能拥有的资金本利最大总额。

因此目标函数为4325max 1.15 1.28 1.40 1.06A B C D Z x x x x =+++束条件应是每年年初的投资额应等于该投资者年初所拥有的资金.第1年年初该投资者拥有10万元资金,故有11100000A D x x +=.第2年年初该投资者手中拥有资金只有()116%D x +,故有22211.06A C D D x x x x ++=.第3年年初该投资者拥有资金为从D 项目收回的本金: 21.06D x ,及从项目A 中第1年投资收回的本金: 11.15A x ,故有333121.15 1.06A B D A D x x x x x ++=+同理第4年、第5年有约束为44231.15 1.06A D A D x x x x +=+,5341.15 1.06DA Dx x x =+max =1.15*x4a+1.28*x3b+1.4*x2c+1.06*x5d; x1a+x1d=100000;-1.06*x1d+x2a+x2c+x2d=0;-1.15*x1a-1.06*x2d+x3a+x3b+x3d=0; -1.15*x2a-1.06*x3d+x4a+x4d=0; -1.15*x3a-1.06*x4d+x5d=0; x2c=40000 ; x2c=60000; x2c=80000; x2c=20000; x3b>=30000; x3b<=50000;x1a>=0;x2a>=0;x3a>=0;x4a>=0;x5a>=0; x1b>=0;x2b>=0;x3b>=0;x4b>=0;x5b>=0; x1c>=0;x2c>=0;x3c>=0;x4c>=0;x5c>=0; x1d>=0;x2d>=0;x3d>=0;x4d>=0;x5d>=0;Variable Value Reduced Cost X4A 22900.00 0.000000 X3B 50000.00 0.000000 X2C 40000.00 0.000000 X5D 0.000000 0.000000 X1A 62264.15 0.000000 X1D 37735.85 0.000000 X2A 0.000000 0.000000 X2D 0.000000 0.3036000E-01 X3A 0.000000 0.000000 X3D 21603.77 0.000000 X4D 0.000000 0.2640000E-01 X5A 0.000000 0.000000 X1B 0.000000 0.000000 X2B 0.000000 0.000000 X4B 0.000000 0.000000 X5B 0.000000 0.000000 X1C 0.000000 0.000000 X3C 0.000000 0.000000 X4C 0.000000 0.000000 X5C 0.000000 0.000000Row Slack or Surplus Dual Price 1 80000.00 1.0000002 0.000000 1.4018503 0.000000 1.3225004 0.000000 1.2190005 0.000000 1.1500006 0.000000 1.0600007 0.000000 -0.8388608E+188 -20000.00 -0.1280000E+109 -40000.00 -0.1280000E+1010 -20000.00 0.1280000E+1011 20000.00 0.00000012 0.000000 0.6100000E-0113 62264.15 0.00000014 0.000000 0.00000015 0.000000 0.00000016 22900.00 0.00000017 0.000000 0.00000018 0.000000 0.00000019 0.000000 0.00000020 50000.00 0.00000021 0.000000 0.00000022 0.000000 0.00000023 0.000000 0.00000024 40000.00 0.00000025 0.000000 0.00000026 0.000000 0.00000027 0.000000 0.00000028 37735.85 0.00000029 0.000000 0.00000030 21603.77 0.00000031 0.000000 0.00000032 0.000000 0.0000004.10某城市的消防总站将全市划分为11个防火区，现有4个消防站，图4-11给出的是该城市各防火区域和防火站的示意图，其中1,2,3,4，表示消防站1，2，…11表示防火区域，根据历史资料证实，各消防站可在事先规定允许的时间内对所负责的区域内的火灾予以扑灭，图中没有虚线连接的就表示不负责，现在总部提出：能否减少消防站的数目，仍能保证负责各地区的防火任务？如果可以的话，应该关闭哪个？练习4.10某城市的消防站总部将全市划分为11个防火区，现有四的。

运筹学教程（胡运权主编，清华第4版）部分习题答案（第五章）5.1设长度为a j的毛坯截取x j根，则min z = L - ∑j=1,2,...,n a j x js.t. ∑j=1,2,...,n a j x j≤ Lx j ≥ 0, integer, j = 1, 2, …, n即max z’ = ∑j=1,2,...,n a j x js.t. ∑j=1,2,...,n a j x j≤ Lx j ≥ 0, integer, j = 1, 2, …, n5.2设x j = 1, 当第j队员上场；x j = 0, 当第j队员不上场，则max z = 1.92x1 + 1.90x2 + 1.88x3 + 1.86x4 + 1.85x5 + 1.83x6 + 1.80x7 + 1.78x8s.t. x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8= 5x1 + x2 = 1x6 + x7 + x8 ≥ 1x6 ≤ 2 – (x1 + x4)x2 + x8 ≤ 1x j ={0 or 1}, j = 1, 2, …, 85.3max z = ∑i=1,2,...,m c i x is.t. ∑i=1,2,...,m a i x i≤ a∑i=1,2,...,m b i x i≤ bx i = 0 or 1, i = 1, 2, …, m5.4(1) x* = (3, 1); z* = 7(2) x* = (0, 9); z* = 95.5(1) 无可行解(2) x* = (1, 0, 0); z* = 25.6设x j = 1, 当消防站j不关闭；x j = 0, 当消防站j关闭min w = x1 + x2 + x3 + x4s.t. x1 + x2≥ 1 （区域1有消防站负责）x1 + x2≥ 1 （区域2有消防站负责）x1 ≥ 1 （区域3有消防站负责）x1 + x3≥ 1 （区域4有消防站负责）x3≥ 1 （区域5有消防站负责）x1 + x3 + x4≥ 1 （区域6有消防站负责）x1 + x4≥ 1 （区域7有消防站负责）x1 + x2 + x4≥ 1 （区域8有消防站负责）x2 + x4≥ 1 （区域9有消防站负责）x4≥ 1 （区域10有消防站负责）x3 + x4≥ 1 （区域11有消防站负责）x1, x2, x3, x4 = 0 或1最优解：x* = (1, 0, 1, 1); z* = 35.7设y i = 0，当条件i被选；y i = 1，当条件i不选∑j=1,2,…n a ij x j ≥ b i - My i, ( i = 1, 2, …, p)∑i=1,2,...,p y i = p - q5.11(1) 令x = 0x0 +1x1 + 4x2 + 6x3; x j = 0 or 1; x0 + x1 + x2 +x3 = 1(2) 令x = 0x0 +1x1 + 4x2 + 6x3; x j = 0 or 1; x0 + x1 + x2 +x3 = 1。

第五章整数规划习题5.1考虑以下数学模型min z = fi(Xi) + f2 (x2)且满意约束条件(1) 或 ,或X2 河0：(2) 以下各不等式至少有一个成立：2x〔+ x2 *5+ X2 >15x〔+2x2 215(3) Xi -X2 =0或 5 或10(4) 为No , X2 2 0其中20 + 5xi,如>0fi(xO= 10 ，如=°12 + 6x2,如>0f2(X2)= .0 ，如=0将此问题归结为混合整数规划的模型；minz = 1°y〔* 5xi 十12y2 -6x2（0）xi V yi ,M; x2 y2• M（1）% >10- y3 <MX2 己10 —（1 — y3）• M（2）X1 +xA5- y4M2Xi +X2 2 15- y5MX1 + 2x2 2 15 - yeM第 +y5 + y6 < 2（3）x1 _X2 =0y7 -5y8+5y9 -10y w+ 11yn工y8 + y9 + Yw + y” = 1（4）xi >0，x2 - 0; yi = 0或5.2试将下述非线性的0-1规划问题转换成线性的0-1规划问题_ 2 + 3max z - % x2 x3 - x3一 2xi + 3x2 + X3 <3Xj = 0或 1,= 1,2,3)，当=Xs = 1X 22 3又X 〔，Xi 分别与X 、X3等价，因此题中模型可转换为max z = % + y - X3—2xi + 3x2 X3 — 3 y WX2"X3X2 * X3 V y F一Xi ，X2，X3，y 均为 一1 变5.3某科学试验卫星拟从以下仪器装置中选如干件装上；有关数据资料见表5-1表5-1要求：(1)装入卫星的仪器装置总体积不超过 V,总质量不超过 W (2) A 与A 中最多安装一件；(3)氏与4中至少安装一件；(4) As 同玲或者都安上，或者都 担心；总的目的是装上取的仪器装置使该科学卫星发挥最大的试验价值； 试建立 这个问题的数学模型； 解： 6max z = Z CjXj j ='6三 VjXj -V jT解：令y = 故有 x 2x3 =y,I 6£ Wj Xj - w jTXi + x3 -1 X2十X4 Z 1X5 = X61 ，安装Aj仪器X・=< J 0，否就5.4 某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探 费用最小；如10个井位的代号为Si , S2, S10,相应的钻探费用为C1 , C2, ,C 10, 并且井位选择上要满意以下限制条件：(1) 或选择S1和S7,或选择钻探S8；(2) 选择了 S3或S4就不能选择S5,或反过来也一样；(3) 在S5,S6,S7,S8,中最多只能选两个；试建立这个问题的整数规划模型； 解： 10min z = £ CjXj j=3'10E Xj = 5 jmX1 + X8 = 1 X3 + Xs < 1 X7 〜彘=1 X4 + X5 三 1 X5 + X6 + X7 + X8 M 2，选择钻探第Sj 井‘0 ,否就5.5用割平面法求解以下整数规划问题(a) maxz = 7x 〔 一 9x 2 —q 3x2 — 6 7Xi +x 2 V 35 x 1s x 2, - 0且为整(b) minz =数4对 5x2% +2X2 V Xi -4x2 - 5 3xi + X2 -2 XlJ x 2 20且为整、 I ' £4xi — 4X 2 J 5 -Xi 〜6X2 — 5一 Xi + X2 + X3 -5*,X2，X3,20 且为整 (d) max z = "Xi +4x2(c)max z 一 4xi 6x 2 + 2x3-x〔+2x2 £14 5x1+ 2X2 <16 2xi - X2 三 4KM*。

第四章 整数规划与分配问题一、建立下列问题的数学模型1、P143, 4.1 利用0－1变量对下列各题分别表示成一般线性约束条件 (a) 221≤+x x 或53221≥+x x ； (b) x 取值0,3,5,7中的一个； (c) 变量x 或等于0，或50≥； (d) 若21≤x ，则12≥x ，否则42≤x ； (e) 以下四个约束条件中至少满足两个：6225433121≥+≥≤≤+x x x x x x ，，，。

解：(a) 设⎩⎨⎧=否则。

，个条件起作用；第1i ,0y i （i=1,2）,M 为任意大正数。

则有 ⎪⎩⎪⎨⎧=+≥++≤+1y y My -5x 3x 2My 2x x 21221121(b) 设⎩⎨⎧=≠=ix i x y i ,1,0，7,5,3,0=i ，则原条件可表示为⎩⎨⎧=++++++=1753075307530y y y y y y y y x(c) 设⎩⎨⎧≥==50,10,0x x y ，则原条件可表示为⎪⎩⎪⎨⎧≥--≥≤0)1(50x M y x yM x(d)⎩⎨⎧=否则。

，组条件起作用；第1i ,0y i （i=1,2）,M 为任意大正数。

则有⎪⎪⎪⎩⎪⎪⎪⎨⎧=++≤->-≥+≤.1,4,2,1,22122211211y y My x My x My x My x (e)设⎩⎨⎧=个条件不成立第个条件成立第i ,1i ,0y i ，4,3,2,1i =，则原条件可表示为：⎪⎪⎪⎩⎪⎪⎪⎨⎧≤+++-≥+-≥+≤+≤+2y y y y My 6x x My 2x M y 2x M y 5x x 43214433321121 2、P143, 4.2 某钻井队要从以下10个可供选择的井位确定5个钻井探油，目的是使得总的钻探费用最小。

若10个井位代号为101S ,...,S ，相应的钻探费用为101C ,...,C ，并且井位的选择要满足下列条件：（1）或选择1S 和7S ，或选择8S ；（2）选择了3S 或4S 就不能选择5S ，反过来也一样； （3）在10962S ,S ,S ,S 中最多只能选两个。

第四章 整数规划４.1 某工厂生产甲、乙两种设备,已知生产这两种设备需要消耗材料A 、材料B,有关数据如下,问这两种设备各生产多少使工厂利润最大？(只建模不求解）解:设生产甲、乙这两种设备的数量分别为x １、x 2,由于是设备台数,则其变量都要求为整数,建立模型如下:2123max x x z +=⎪⎪⎩⎪⎪⎨⎧≥≤+≤+为整数21212121,0,5.45.01432x x x x x x x x４．2 2197max x x z +=⎪⎩⎪⎨⎧≥≤+≤+-且为整数0,35763.212121x x x x x x t s 割平面法求解。

(下表为最优表）线性规划的最优解为：63max ,0,2/7,2/94321=====z x x x x由最终表中得:27221227432=++x x x ﻩ④ 将系数和常数项分解成整数和非负真分式之和，上式化为；2132********+=++x x x移项后得:①②③④①②③即：21221227212212274343-≤--→≥+x x x x 只要把增加的约束条件加到B 问题的最优单纯形表中。

表4-4由ｘ1行得:7327171541=-+x x x 将系数和常数项分解成整数和非负真分数之和:74476715541+=+-+x x x x得到新的约束条件： 74767154-≤--x x747671654-=+--x x x 在的最优单纯形表中加上此约束，用对偶单纯形法求解：则最优解为3,421==x x ，最优目标函数值为z *=55。

4．3 m ａx z =４ｘ1+３x 2+2x ３⎪⎪⎩⎪⎪⎨⎧=≥+≥++≤+-10,,13344352.32132321321或x x x x x x x x x x x t s 隐枚举法解：(１）先用试探的方法找出一个初始可行解,如x 1=ｘ２＝０,x 3＝1。

满足约束条件，选其作为初始可行解，目标函数z 0=2。

一、判断题1、正偏差变量大于等于零，负偏差变量小于等于零。

（）正确答案：×2、系统约束中最多含有一个正或负的偏差变量。

（）正确答案：×3、目标约束一定是等式约束。

（）正确答案：√4、一对正负偏差变量至少一个大于零。

（）正确答案：×5、一对正负偏差变量至少一个等于零。

（）正确答案：√6、要求不超过目标值的目标函数是minZ= d+。

（）正确答案：√7、超出目标的差值称为正偏差。

（）正确答案：√8、未到达目标的差值称为负偏差。

（）正确答案：√二、填空题1. 用分枝定界法求极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的（）。

正确答案：下界2.在分枝定界法中，若选Xr=4／3进行分支，则构造的约束条件应为（）。

正确答案：X1<=1，X1>=23. 已知整数规划问题P0，其相应的松驰问题记为P0’，若问题P0’无可行解，则问题P0（）。

正确答案：无可行解4.在0 - 1整数规划中变量的取值可能是（）。

正确答案：0或15. 对于一个有n项任务需要有n个人去完成的分配问题，其解中取值为1的变量数为（）个。

正确答案：n三、选择题1. 整数规划问题中，变量的取值可能是（）。

A.整数B.0或1C.大于零的非整数D.以上三种都可能正确答案：D2.在下列整数规划问题中，分枝定界法和割平面法都可以采用的是（）。

A.纯整数规划B.混合整数规划C.0—1规划D.线性规划正确答案：A3.下列方法中用于求解分配问题的是（）。

A.单纯形表B.分枝定界法C.表上作业法D.匈牙利法正确答案：D。

练习 4.9 连续投资问题某公司现有资金10万元, 拟在今后五年考虑用于下列项目的投资: 项目A:从第一年到第四年每年年初需要投资, 并于次年收回本利115%,但要求第一年投资最低金额为4 万元, 第二. 三. 四年不限.项目B:第三年初需要投资, 到第五年末能收回本利128%,但规定最低投资金额为3万元,最高金额为 5 万元.项目C:第二年初需要投资, 到第五年末能收回本利140%,但规定其投资金额或为2万元,或为 4 万元, 或为 6 万元, 或为8 万元.项目D:五年每年年初都可购买公债,于当年末归还, 并获利6%,此项目投资金额不限. 试问该公司应图和确定这些项目的每年投资金额, 使到第五年末拥有最大的资金收益.(1)x 为项目各年月初投入向量。

(2)x ij 为i 种项目j 年的月初的投入(3)向量c中的元素cij为i 年末j种项目收回本例的百分比(4)矩阵A中元素aij为约束条件中每个变量xij的系数。

(5)Z为第5年末能拥有的资金本利最大总额。

因此目标函数为max Z 1.15 x4 A 1.28 x3B 1.40x2C 1.06 x5 D束条件应是每年年初的投资额应等于该投资者年初所拥有的资金第 1 年年初该投资者拥有10 万元资金, 故有x1A x1D 100000 .第 2 年年初该投资者手中拥有资金只有 1 6% x1D , 故有x2A x2C x2D 1.06 x1D .第3 年年初该投资者拥有资金为从D 项目收回的本金: 1.06x2D , 及从项目 A 中第1 年投资收回的本金: 1.15x1A , 故有max=1.15*x4a+1.28*x3b+1.4*x2c+1.06*x5d; x1a+x1d=100000;-1.06*x1d+x2a+x2c+x2d=0;-1.15*x1a-1.06*x2d+x3a+x3b+x3d=0; -1.15*x2a-1.06*x3d+x4a+x4d=0; -1.15*x3a-1.06*x4d+x5d=0; x2c=40000 ; x2c=60000; x2c=80000; x2c=20000; x3b>=30000; x3b<=50000;x1a>=0;x2a>=0;x3a>=0;x4a>=0;x5a>=0; x1b>=0;x2b>=0;x3b>=0;x4b>=0;x5b>=0; x1c>=0;x2c>=0;x3c>=0;x4c>=0;x5c>=0; x1d>=0;x2d>=0;x3d>=0;x4d>=0;x5d>=0;x 3A x 3B x 3D 1.15 x 1A 1.06 x 2 D同理第 4年、第 5 年有约束为 x 4A x 4D 1.15 x 2 A 1.06 x 3 D ,x5D1.15 x 3 A 1.06x 4DVariable Value Reduced Cost X4A 22900.00 0.000000X3B 50000.00 0.000000X2C 40000.00 0.000000X5D 0.000000 0.000000X1A 62264.15 0.000000X1D 37735.85 0.000000X2A 0.000000 0.000000X2D 0.000000 0.3036000E-01 X3A 0.000000 0.000000X3D 21603.77 0.000000X4D 0.000000 0.2640000E-01 X5A 0.000000 0.000000X1B 0.000000 0.000000X2B 0.000000 0.000000X4B 0.000000 0.000000X5B 0.000000 0.000000X1C 0.000000 0.000000X3C 0.000000 0.000000X4C 0.000000 0.000000X5C 0.000000 0.000000Row Slack or Surplus Dual Price1 80000.00 1.0000002 0.000000 1.4018503 0.000000 1.3225004 0.000000 1.2190005 0.000000 1.1500006 0.000000 1.0600007 0.000000 -0.8388608E+188 -20000.00 -0.1280000E+109 -40000.00 -0.1280000E+1010 -20000.00 0.1280000E+1011 20000.00 0.00000012 0.000000 0.6100000E-0113 62264.15 0.00000014 0.000000 0.00000015 0.000000 0.00000016 22900.00 0.00000017 0.000000 0.00000018 0.000000 0.00000019 0.000000 0.00000020 50000.00 0.00000021 0.000000 0.00000022 0.000000 0.00000023 0.000000 0.00000024 40000.00 0.00000025 0.000000 0.00000026 0.000000 0.00000027 0.000000 0.00000028 37735.85 0.00000029 0.000000 0.00000030 21603.77 0.00000031 0.000000 0.00000032 0.000000 0.0000004.10 某城市的消防总站将全市划分为11个防火区，现有4个消防站，图4-11 给出的是该城市各防火区域和防火站的示意图，其中1,2,3,4 ，表示消防站1，2，⋯11 表示防火区域，根据历史资料证实，各消防站可在事先规定允许的时间对所负责的区域的火灾予以扑灭，图中没有虚线连接的就表示不负责，现在总部提出：能否减少消防站的数目，仍能保证负责各地区的防火任务？如果可以的话，应该关闭哪个？练习 4.10某城市的消防站总部将全市划分为11 个防火区，现有四的。

若某钻井队要从以下10个可供选择的井位中确定5个钻井探油。

使总的钻探费用为最小。

若10个井位的代号为S 1,S 2．…，S 10相应的钻探费用为C 1 ,C 2 ,… C 10，并且井位选择要满足下列限制条件： (1)在s 1，s 2，S 4中至多只能选择两个；（2）在S 5，s 6中至少选择一个；（3）在s 3，s 6，S 7，S 8中至少选择两个。

试建立这个问题的整数规划模型解：设x j （j=1,…,10）为钻井队在第i 个井位探油 minZ=j j j x c ∑=101背包问题：一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。

每种物品的重量合重要性系数如表所示。

设登山队员可携带的最大重量为25kg,试选择该队员所应携带的物品。

序号 1 2 3 4 5 6 7物品 食品 氧气 冰镐 绳索 帐篷 照相器材 通信设备 重量/Kg 5 5 2 6 12 2 4 重要性系数 201518148410解：引入0—1变量x i , x i =1表示应携带物品i ，,x i =0表示不应携带物品I⎩⎨⎧==≤++++++++++++=7,...,2,1,10254212625510481418152076543217654321i x x x x x x x x x x x x x x x naxz i 或集合覆盖和布点问题某市消防队布点问题。

该市共有6个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15min 内赶到现场。

据实地测定，各区之间消防车行驶的时间见表，请制定一个布点最少的计划。

解：引入0—1变量x i , x i =1表示在该区设消防站，,x i =0表示不设⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=≥++≥++≥++≥+≥++≥++++++=01111111min 6526545434362121654321或i x x x x x x x x x x x x x x x x x x x x x x x z解得： X*=(0,1,0,1,0,0)’ Z*=2某公司现有5个项目被列入投资计划，各项目的投资额和期望的投资收益如下表所示：该公司只有600万元资金可用于投资，由于技术上的原因，投资受到以下条件的约束：（1）在项目1、2和3中必须有一项被选中，（2）项目3和项目4只能选中一项，（3）项目5被选中的前提是项目1必须被选中。