第五章 整数规划练习题答案

运筹学思考练习题答案第⼀章 L.P 及单纯形法练习题答案⼀、判断下列说法是否正确1. 线性规划模型中增加⼀个约束条件，可⾏域的范围⼀般将缩⼩，减少⼀个约束条件，可⾏域的范围⼀般将扩⼤。

(?)2. 线性规划问题的每⼀个基解对应可⾏域的⼀个顶点。

(?)3. 如线性规划问题存在某个最优解，则该最优解⼀定对应可⾏域边界上的⼀个点。

(?)4. 单纯形法计算中，如不按最⼩⽐值原则选取换出变量，则在下⼀个基可⾏解中⾄少有⼀个基变量的值为负。

(?)5. ⼀旦⼀个⼈⼯变量在迭代中变为⾮基变量后，该变量及相应列的数字可以从单纯形表中删除，⽽不影响计算结果。

(?)6. 若1X 、2X 分别是某⼀线性规划问题的最优解，则1212X X X λλ=+也是该线性规划问题的最优解，其中1λ、2λ为正的实数。

(?)7. 线性规划⽤两阶段法求解时，第⼀阶段的⽬标函数通常写为ai iMinZ x =∑(x ai 为⼈⼯变量)，但也可写为i ai iMinZ k x =∑，只要所有k i 均为⼤于零的常数。

(?)8. 对⼀个有n 个变量、m 个约束的标准型的线性规划问题，其可⾏域的顶点恰好为m n C 个。

(?)9. 线性规划问题的可⾏解如为最优解，则该可⾏解⼀定是基可⾏解。

(?)10. 若线性规划问题具有可⾏解，且其可⾏域有界，则该线性规划问题最多具有有限个数的最优解。

(?)⼆、求得L.P 问题121231425j MaxZ 2x 3x x 2x x 84x x 164x x 12x 0;j 1,2,,5=+++=??+=??+=?≥=的解如下： X ⑴=(0,3,2,16,0)T ;X ⑵=(4,3,-2,0,0)T ;X ⑶=(3.5,2,0.5,2,4)T ;X ⑷=(8,0,0,-16,12)T ; =(4.5,2,-0.5,-2,4)T ; X ⑹=(3,2,1,4,4)T ;X ⑺=(4,2,0,0,4)T 。

要求：分别指出其中的基解、可⾏解、基可⾏解、⾮基可⾏解。

运筹学教程（胡运权主编，清华第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。

第五章整数规划1．整数规划的特点(1)整数规划:决策变量要求取整数的线性规划。

（2）整数规划可分为纯整数规划和混合整数规划。

(3)整数规划的可行域为离散点集。

2．整数规划的建模步骤整数规划模型的建立几乎与线性规划模型的建立完全一致，只是变量的部分或全体必须限制为整数。

3．求解整数规划的常用方法1）分支定界法没有最大化的整数规划问题A，与它相应的线性规划问题为问题B，从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z＊的上界，记作，而A的任意可行解的目标函数值将是z＊的一个下界 ,分支定界法就是将B的可行域分成子区域的方法,逐步减小和增大，最终求得z＊。

将要求解的整数规划问题称为问题A，将与它相应的线性规划问题称为问题B。

(1）解与整数规划问题A相应的线性规划问题B,可能得到以下几种情况之一:①B没有可行解，A也没有可行解,停止计算。

②B有最优解，并符合问题A的整数条件，则此最优解即为A的最优解，停止计算。

③B有最优解,但不符合A的整数条件，记它的目标函数值为。

(2)用观察法找问题A的一个整数可行解，求得其目标函数值,并记作。

以z*表示问题A的最优目标数值，则≤z*≤。

下面进行迭代.分支，在B的最优解中任选一个不符合整数条件的变量xi ，其值为bi。

构造两个约束条件xj ≤［bj］①和xj ≥[bj］+1 ②其中［bj ］为不超过bj的最大整数。

将这两个约束条件分别加入问题B，求两个后继规划问题B1和B2。

不考虑整数约束条件求解这两个后继问题。

定界，以每个后继问题为一分支标明求解的结果。

第一步：先不考虑整数约束，变成一般的线性规划问题，用图解法或单纯形法求其最优解，记为 ) ；第二步:若求得的最优解，刚好就是整数解，则该整数就是原整数规划的最优解,否则转下步;第三步：对原问题进行分支寻求整数最优解。

第四步:对上面两个子问题按照线性规划方法求最优解。

若某个子问题的解是整数解,则停止该子问题的分支，并且把它的目标值与上一步求出的最优整数解相比较以决定取舍;否则，对该子问题继续进行分支。

第五章 整数规划习题5.1 考虑下列数学模型)()(min 2211x f x f z += 且满足约束条件（1）或101≥x ，或102≥x ； （2）下列各不等式至少有一个成立：⎪⎩⎪⎨⎧≥+≥+≥+15215152212121x x x x x x（3）021=-x x 或5或10 （4）01≥x ，02≥x 其中)(11x f =⎩⎨⎧=>+0,00,520111x x x 如如 =)(22x f ⎩⎨⎧=>+0,00,612222x x x 如如将此问题归结为混合整数规划的模型。

解：2211612510min x y x y z +++=⎪⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎪⎨⎧∙∙∙=≥≥=+++++-+-=-≤++-≥+-≥+-≥+∙--≥∙-≥∙≤∙≤），，＝（或，）（）（）（；）（11.110;00)4(111105503215215152)1(10101021111098711109872165462152142132312211i y x x y y y y y y y y y y x x y y y M y x x M y x x M y x x M y x M y x M y x M y x i5.2 试将下述非线性的0-1规划问题转换成线性的0-1规划问题333221max x x x x z -+=⎩⎨⎧==≤++-），（或3,2,110332321j x x x x j解：令=y ⎩⎨⎧==否则，当,01132x x故有y x x =32，又21x ，31x 分别与1x ，3x 等价，因此题中模型可转换为31max x y x z -+=⎪⎪⎪⎩⎪⎪⎪⎨⎧-+≤+≤≤≤++-变量均为10,,,13323213232321y x x x y x x x y x y x x x5.3 某科学实验卫星拟从下列仪器装置中选若干件装上。

有关数据资料见表5-1要求：（1）装入卫星的仪器装置总体积不超过V ，总质量不超过W ；（2）A 1与A 3中最多安装一件；（3）A 2与A 4中至少安装一件；（4）A 5同A 6或者都安上，或者都不安。

第五章 整数规划主要内容：1、分枝定界法； 2、割平面法； 3、0－1型整数规划； 4、指派问题。

重点与难点：分枝定界法和割平面法的原理、求解方法，0－1型规划模型的建立及求解步骤，用匈牙利法求解指派问题的方法和技巧。

要 求：理解本章内容，熟练掌握求解整数规划的方法和步骤，能够运用这些方法解决实际问题。

§1 问题的提出要求变量取为整数的线性规划问题，称为整数规则问题（简称IP ）。

如果所有的变量都要求为（非负）整数，称之为纯整数规划或全整数规划；如果仅一部分变量要求为整数，称为混合整数规划。

例1 求解下列整数规划问题211020max x x z += ⎪⎪⎩⎪⎪⎨⎧≥≤+≤+为整数21212121,0,13522445x x x x x x x x 如果不考虑整数约束，就是一个线性规划问题（称这样的问题为原问题相应的线性规划问题），很容易求得最优解为：96max ,0,8.421===z x x 。

50用图解法将结果表示于图中画“+”号的点都是可行的整数解，为满足要求，将等值线向原点方向移动，当第一次遇到“+”号点（1,421==x x ）时得最优解为1,421==x x ，最优值为z=90。

由上例可看出，用枚举法是容易想到的，但常常得到最优解比较困难，尤其是遇到变量的取值更多时，就更困难了。

下面介绍几种常用解法。

§2 分枝定界法分枝定界法可用于解纯整数或混合的整数规划问题。

基本思路：设有最大化的整数规划问题A ，与之相应的线性规划问题B ，从解B 开始，若其最优解不符合A 的整数条件，那么B 的最优值必是A 的最优值*z的上界，记为z；而A 的任意可行解的目标函数值是*z的一个下界z，采取将B 的可行域分枝的方法，逐步减少z 和增大z ，最终求得*z 。

现举例说明： 例2 求解A219040max x x z +=⎪⎪⎩⎪⎪⎨⎧≥≤+≤+为整数21212121,0,702075679x x x x x x x x 解：先不考虑条件⑤，即解相应的线性规划B （①--④），得最优解=1x 4.81, =2x 1.82, =0z 356（见下图）。

第五章 整数规划5.1(1)在原线性规划问题约束条件中添加松弛变量43,x x ，化为标准型，可得⎪⎪⎩⎪⎪⎨⎧≥=++=+++=为整数21432142132121,0,,,5.1645.143223max x x x x x x x x x x x x x x z不考虑整数条件，用单纯形法求解，计算结果如下表所示。

因而最优解为.231252273,)0,0,25,27(*=⨯+⨯=z T 当凑整为TX )0,0,3,4('=时，显然为非可行解；同样，当凑整为TX )0,0,2,4("=或T X )0,0,3,3("=也不是可行解。

当凑整为T X )0,0,2,3("'=为可行解，相应的z=13.用分枝定界法求解该整数规划问题。

记231=z ，因为0,021==x x 为可行解，故有2310*≤≤z 分解为两个子问题：⎪⎪⎩⎪⎪⎨⎧≥≤≤≤+≤++=0305.1645.1432)(23max 212121121x x x x x x B x x z 得最优解344,)0,35,0,617,3(1=z T 。

⎪⎪⎩⎪⎪⎨⎧≥≥≤+≤++=045.1645.1432)(3max 212121221x x x x x x B x x z 得最优解13,)0,0,5,21,4(2=z T。

综合知3440*≤≤z 并再分解1B 为两枝3B 和4B ：⎪⎪⎩⎪⎪⎨⎧≤≤≤≤≤+≤++=20305.1645.1432)(23max 212121321x x x x x x B x x z 得最优解.13,)0,0,25,25,2,3(3=z T⎪⎪⎩⎪⎪⎨⎧≥≤≤≤+≤++=3305.1645.1432)(23max 212121421x x x x x x B x x z 得最优解.457,)0,0,41,25,0,3,411(4=z T3B 已是整数解，可取.133==z z 对2B 一枝而言，继续分解已无意义，可舍去。

整数规划习题4-1某厂拟在A 、B 、C 、D 、E 五个城市中建立若干个配送中心，各处设配送中心都需要资金、人力、设备等，而这样的需求量及能提供的利润各处不同，有些点可能亏本，但却能得到贷款和人力等资源。

设数据已知，由下表所示。

厂方应作出4-2用分支定界法求解下列整数规划问题⎪⎩⎪⎨⎧≥≥+≤+⎪⎩⎪⎨⎧≥≥+≤+-+=+=且为整数且为整数）（）（0,5427230,5021010m 2min 12121212121212121x x x x x x x x x x x x x x z ax x x z4-3用割平面法求解下列整数规划问题⎪⎩⎪⎨⎧≥≤+≤+⎪⎩⎪⎨⎧≥≥+≥++=+=且为整数且为整数）（）（0,102920,1029232m 232min 12121212121212121x x x x x x x x x x x x x x z ax x x z 4-4用隐枚举法求解下列0-1规划问题⎪⎪⎪⎩⎪⎪⎪⎨⎧=≤+≤+≤++≤-++-=1,0,,162444233max 3212232321321321x x x x x x x x x x x x x x x x z4-5安排4个人做4项不同的工作，每个人完成工作所需要的时间如下表所示，（1）应如何指派，可使总的时间最少？（2）如果表中的数据为创造的效益，应如何指派，使总效益最大？（3）如果在表中增加一个人（一行），完成A、B、C、D工作的时间分别为16、17、20、21天，这时应如何指派，使总时间最少？4-6对每题结论进行判断，如果结论错误请改正。

（1）整数规划的最优解是先求相应的线性规划的最优解然后取整得到。

（2）求最大值整数规划问题的目标函数值是各分支函数值的上界。

（3）求最小值整数规划问题的目标函数值是各分支函数值的上界。

（4）整数规划的可行解集合是离散型集合。

（5）0一1规划的变量有n个，则有2n个可行解。

（6）割平面约束是将可行域中一部分非整数解切割掉。

第五章整数规划练习题
一. 判断下列说法是否正确
1.用分枝定界法求解一个极大化的整数规划问题时，任何一个可行整数解的目标函数值是该问题目标函数值的下界。

( )
2.用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。

( )
3.用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值。

( )
4.指派问题数学模型的形式与运输问题十分相似，故也可以用表上作业法求解。

( )
二. 设有五项工作要分派给五个工人，每人的作业产值如下表所示，为了使总产值最大，问
应如何分配这五项工作，并求得最大产值。

三. 对整数规划
12
121212MaxZ 8x 5x 2x 3x 12
x x 6
x ,x 0,=++≤⎧⎪-≤⎨⎪≥⎩整数
解得其松弛问题最优表如下：。

本文部分内容来自网络整理，本司不为其真实性负责，如有异议或侵权请及时联系，本司将立即删除！== 本文为word格式，下载后可方便编辑和修改！ ==整数规划试题篇一：试题--整数规划第3章整数规划一、选择题（在下列各题中，从备选答案中选出1个或多个正确答案） 1. maxZ?3x1?2x2,2x1?3x2?14,x1?0.5x2?4.5,x1,x2?0且为整数，对应线性规划的最优解是（3.25，2.5），它的整数规划的最优解是( )A.(4，1) B.(4，3)C.(3，2) D.(2，4)2. 下列说法正确的是 ( )A.整数规划问题最优值优于其相应的线性规划问题的最优值B.用分枝定界法求解一个极大化的整数规划时，当得到多于一个可行解时，通常可任取其中一个作为下界，再进行比较剪枝C.分枝定界法在处理整数规划问题时，借用线性规划单纯形法的基本思想，在求相应的线性模型解的同时，逐步加入对各变量的整数要求限制，从而把原整数规划问题通过分枝迭代求出最优解。

D.以上说法都不对3. 分枝定界法中( )A. 最大值问题的目标值是各分枝的下界B. 最大值问题的目标值是各分枝的上界C. 最小值问题的目标值是各分枝的上界D. 以上结论都不对Z?3x1?x2,4x1?3x2?7,x1?2x2?4,x1,x2?0或1，最优解是( ) 4. maxA.(0,0）B.(0,1）C.(1,0）D.(1,1)二、填空题4x1?x2?18，5x1?x2?30至少一个满足，用0－1变量表示的一般1．x1?2x2?5，线性约束条件是（）2．求解纯整数规划的两种方法是（）3. 已知基变量x1=3.25，x1要求取整数，则添加分枝约束（）和（）。

三、判断题1. 整数规划的最优解是先求相应的线性规划的最优解然后取整得到；2. 部分变量要求是整数的规划问题称为纯整数规划；3. 求最大值问题的目标函数值是各分枝函数值的上界；4. 求最小值问题的目标函数值是各分枝函数值的下界；5. 变量取0或1的规划是整数规划；6. 整数规划的可行解集合是离散型集合；7. 将指派问题的效率矩阵每行分别加上一个数后最优解不变；8. 匈牙利法求解指派问题的条件是效率矩阵的元素非负；9. 匈牙利法可直接求解极大化的指派问题；参考答案：一、选择题 1. A ， 2. D ， 3. B ， 4 . D二、填空题 1.2. （分枝定界法和割平面法）3.（x1≤3），（x1≥4）三、判断题1.× 取整后不一定是原问题的最优解 2.× 称为混和整数规划3.√4.√5.√6.√7.√8.√9.× 是求解极小化的指派问题篇二：整数规划习题第五章整数规划习题5.1 考虑下列数学模型 min且满足约束条件z?f1(x1)?f2(x2)（1）或x1?10，或x2?10；（2）下列各不等式至少有一个成立：?2x1?x2?15??x1?x2?15?x?2x?152?1（3）x1?x2?0或5或10?0（4）x1其中?0，x2?20?5x1,如x1?0?,如x1?0f1(x1)?0=将此问题归结为混合整数规划的模型。

第五章 整数规划第四节 0－1型整数规划例题：求解0－1整数规划1231231231223123m ax Z=3x -2x +5x x +2x -x 2x +4x +x 4s.t.x +x 34x + x 6x ,x ,x =01≤⎧⎪≤⎪⎪≤⎨⎪≤⎪⎪⎩或 解法：穷举法（枚举法）、隐枚举法。

（＝8） 解题要点：对于求max ，变量摆放顺序按其在目标函数中值由小到大排列； 对于求min ，则相反。

练习：123451234512345i m axZ=2x -x +5x -3x +4x 3x -2x +7x -5x +4x 6s.t.x -x +2x -4x +2x 0x =01(i=1,2,,5)≤⎧⎪≤⎨⎪⎩或 ...，（＝6） 1234123412341241234m in Z=3x +7x -x +x 2x -x +x -x 1x -x +6x +4x 8s.t.5x +3x +x 5x x ,x ,x =01≥⎧⎪≥⎪⎨≥⎪⎪⎩，或，（＝3）第五节 指派问题例题：某商业公司计划开为5家新商店。

为了尽早建成营业，商业公司决定由5家建筑公司分别承建。

已知建筑公司A i （i ＝1，2，…，5）对新商店B j （j ＝1，2，…，5）的建造费用的报价（万元）为c ij （i ，j ＝1，2，…，5），见下表。

商业公司应当对5家建筑公司怎样分配建造任务，才能使总的建造费用最少？12345A 4871512A 79171410C =A 691287A 6714610A 6912106⎛⎫ ⎪ ⎪⎪ ⎪ ⎪ ⎪⎝⎭，答案：34万元 解题要点：在每行每列都减去该行和列的最小数，使得每行、每列都有0； 找√方法：无圈行→0列→圈行； 画线方法：无√行、有√列。

练习：求最小化指派问题。

12797989666C 71712149151466104107109⎛⎫ ⎪ ⎪⎪ ⎪ ⎪ ⎪⎝⎭＝，答案：32 791012131216171516141511121516⎛⎫ ⎪ ⎪ ⎪ ⎪⎝⎭，＝48，3821038729764275842359106910⎛⎫⎪ ⎪⎪ ⎪ ⎪ ⎪⎝⎭，＝21 上述解法叫匈牙利解法，1955年由库恩提出，此解法用到了匈牙利数学家康尼格的关于矩阵中独立零元素的定理。

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

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

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

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

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

因此目标函数为束条件应是每年年初的投资额应等于该投资者年初所拥有的资金.第1年年初该投资者拥有10万元资金,故有.第2年年初该投资者手中拥有资金只有,故有.第3年年初该投资者拥有资金为从项目收回的本金:,及从项目中第1年投资收回的本金:,故有同理第4年、第5年有约束为,ma某=1.15某某4a+1.28某某3b+1.4某某2c+1.06某某5d;某1a+某1d=100000;-1.06某某1d+某2a+某2c+某2d=0;-1.15某某1a-1.06某某2d+某3a+某3b+某3d=0;-1.15某某2a-1.06某某3d+某4a+某4d=0;-1.15某某3a-1.06某某4d+某5d=0;某2c=40000;某2c=60000;某2c=80000;某2c=20000;某3b>=30000;某3b<=50000;某1a>=0;某2a>=0;某3a>=0;某4a>=0;某5a>=0;某1b>=0;某2b>=0;某3b>=0;某4b>=0;某5b>=0;某1c>=0;某2c>=0;某3c>=0;某4c>=0;某5c>=0;某1d>=0;某2d>=0;某3d>=0;某4d>=0;某5d>=0;VariableValueReducedCot某4A22900.000.000000某3B50000.000.000000某2C40000.000.000000某5D0.0000000.000000某1A62264.150.000000某1D37735.850.000000某2A0.0000000.000000某2D0.0000000.3036000E-01某3A0.0000000.000000某3D21603.770.000000某4D0.0000000.2640000E-01某5A0.0000000.000000某1B0.0000000.000000某2B0.0000000.000000某4B0.0000000.000000某5B0.0000000.000000某1C0.0000000.000000某3C0.0000000.000000某4C0.0000000.000000某5C0.0000000.000000RowSlackorSurpluDualPrice180000.001.00000020.0000001.40185030.0000001.32250040.0000001.21900050.0000001.15000060.0000001.06000070.000000-0.8388608E+188-20000.00-0.1280000E+109-40000.00-0.1280000E+1010-20000.000.1280000E+10 1120000.000.000000 120.0000000.6100000E-01 1362264.150.000000140.0000000.000000150.0000000.0000001622900.000.000000170.0000000.000000180.0000000.000000190.0000000.0000002050000.000.000000210.0000000.000000220.0000000.000000230.0000000.0000002440000.000.000000250.0000000.000000260.0000000.000000270.0000000.0000002837735.850.000000290.0000000.0000003021603.770.000000310.0000000.000000320.0000000.0000004.10练习4.10某城市的消防站总部将全市划分为11个防火区，现有四的。