下载文档原格式
第五章 整数规划习题5.1 考虑下列数学模型)()(m in 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 如如将此问题归结为混合整数规划的模型。
解：2211612510m in 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 等价，因此题中模型可转换为31m ax 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或者都安上，或者都不安。
运筹学教程（胡运权主编，清华第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 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或者都安上，或者都不安。
第五章 整数规划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 一枝而言，继续分解已无意义，可舍去。
运筹学第五章课后习题答案运筹学第五章课后习题答案运筹学是一门研究如何进行有效决策和优化问题的学科。
在运筹学的学习过程中，课后习题是非常重要的一部分，通过解答习题可以帮助我们巩固所学的知识，并且加深对运筹学理论的理解。
本文将给出运筹学第五章的课后习题答案，希望对大家的学习有所帮助。
1. 线性规划问题是运筹学中最基本的问题之一。
以下是一道线性规划问题的习题：Maximize 2x + 3ySubject to:x + y ≤ 102x + y ≤ 15x, y ≥ 0解答：首先，我们需要将目标函数和约束条件转化为标准形式。
将目标函数改写为最小化形式，即 Minimize -2x - 3y。
然后，我们引入松弛变量，将不等式约束转化为等式约束，得到以下形式的线性规划问题：Minimize -2x - 3ySubject to:x + y + s1 = 102x + y + s2 = 15x, y, s1, s2 ≥ 0接下来，我们可以使用单纯形法或者图解法来求解这个线性规划问题。
通过计算或者画图，我们可以得到最优解为 x = 5, y = 5，目标函数的最大值为 25。
2. 整数规划是线性规划的一种扩展形式，其中变量的取值限制为整数。
以下是一道整数规划问题的习题：Maximize 3x + 2ySubject to:x + y ≤ 5x, y ≥ 0x, y 是整数解答：这是一个整数规划问题，我们需要找到满足约束条件的整数解，并求解出目标函数的最大值。
通过穷举法，我们可以得到以下整数解：当 x = 2, y = 3 时，目标函数的值为 13；当 x = 3, y = 2 时，目标函数的值为 12；当 x = 4, y = 1 时，目标函数的值为 11；当 x = 5, y = 0 时，目标函数的值为 10。
综上所述，目标函数的最大值为 13，对应的整数解为 x = 2, y = 3。
3. 0-1整数规划是整数规划的一种特殊形式，其中变量的取值限制为0或1。
第五章整数规划练习题
一. 判断下列说法是否正确
1.用分枝定界法求解一个极大化的整数规划问题时，任何一个可行整数解的目标函数值是该问题目标函数值的下界。
( )
2.用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。
( )
3.用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值。
( )
4.指派问题数学模型的形式与运输问题十分相似，故也可以用表上作业法求解。
( )
二. 设有五项工作要分派给五个工人，每人的作业产值如下表所示，为了使总产值最大，问
应如何分配这五项工作，并求得最大产值。
三. 对整数规划
12
121212MaxZ 8x 5x 2x 3x 12
x x 6
x ,x 0,=++≤⎧⎪-≤⎨⎪≥⎩整数
解得其松弛问题最优表如下：。
第五章整数规划练习题答案(总2页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--第五章 整数规划练习题答案一. 判断下列说法是否正确1. 用分枝定界法求解一个极大化的整数规划问题时，任何一个可行整数解的目标函数值是该问题目标函数值的下界。
()2. 用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。
()3. 用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值。
()4. 指派问题数学模型的形式与运输问题十分相似，故也可以用表上作业法求解。
() 二. 设有五项工作要分派给五个工人，每人的作业产值如下表所示，为了使总产值最大，问应如何分配这五项工作，并求得最大产值。
工作 工人A B C D E 甲 94 6 85 乙 8 5 9 106 丙 97 3 58 丁 4 8 69 5 戊105363答案：设原矩阵为A ，因求极大问题，令B=[M-a ij ]，其中M=Max {a ij }=10，则：1642510531404213251042510424003B 13752102641015406241515130450203057470574704646111-⎛⎫⎛⎫⎛⎫⎪⎪ ⎪⎪ ⎪ ⎪ ⎪ ⎪ ⎪=→→- ⎪⎪ ⎪- ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭---m 4n 5l m 44213421324324315415452352346464646=<===⎛⎫⎛⎫ ⎪⎪∅∅ ⎪ ⎪ ⎪ ⎪→→−−−−→∅∅ ⎪⎪∅∅ ⎪ ⎪ ⎪ ⎪∅∅⎝⎭⎝⎭0310234003115406020303535⎛⎫ ⎪⎪ ⎪⎪⎪ ⎪⎝⎭31234311546233535∅⎛⎫ ⎪∅ ⎪ ⎪→ ⎪∅ ⎪ ⎪⎝⎭ m=5=n ，得最优解。
解矩阵*0001000100X 000010100010000⎛⎫⎪⎪ ⎪= ⎪⎪ ⎪⎝⎭。
第五章 整数规划第四节 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年由库恩提出，此解法用到了匈牙利数学家康尼格的关于矩阵中独立零元素的定理。
第五章整数规划练习
题答案
第五章 整数规划练习题答案
一. 判断下列说法是否正确
1. 用分枝定界法求解一个极大化的整数规划问题时，任何一个可行整数解的目标函数值是
该问题目标函数值的下界。
( )
2. 用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。
( )
3. 用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值。
( )
4. 指派问题数学模型的形式与运输问题十分相似，故也可以用表上作业法求解。
( ) 二. 设有五项工作要分派给五个工人，每人的作业产值如下表所示，为了使总产值最大，问
应如何分配这五项工作，并求得最大产值。
答案：
设原矩阵为A ，因求极大问题，令B=[M-a ij ]，其中M=Max {a ij }=10，则：
16425105
3140
42
13251042510424003B 1
3752102
6410
154062415151
3045
020305
7470574704646111-⎛⎫⎛⎫
⎛
⎫
⎪
⎪ ⎪
⎪ ⎪ ⎪ ⎪ ⎪ ⎪
=→→- ⎪
⎪ ⎪- ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭
---
m 4n 5l m 4
4
21342132432431541545235234
6
4
64
6
4
6=<===⎛
⎫⎛⎫ ⎪ ⎪∅∅ ⎪ ⎪ ⎪ ⎪→→−−−−→∅∅ ⎪ ⎪∅∅ ⎪ ⎪ ⎪ ⎪∅∅⎝
⎭
⎝
⎭
031023
4003115406020303535⎛⎫ ⎪
⎪ ⎪
⎪
⎪ ⎪⎝
⎭
31234311546233
5
3
5∅
⎛⎫ ⎪∅ ⎪ ⎪→ ⎪∅ ⎪ ⎪⎝
⎭ m=5=n ，得最优解。
解矩阵*0001000100X 0000101
00010000⎛⎫
⎪
⎪ ⎪= ⎪
⎪ ⎪⎝⎭。
即，甲→D ，乙→C ，丙→E ，丁→B ，戊→A ，最大产值=10+8+9+8+8=43。
三. 对整数规划
12
121212
MaxZ 8x 5x 2x 3x 12
x x 6x ,x 0,=++≤⎧⎪
-≤⎨⎪≥⎩整数 解得其松弛问题最优表如下：
答案：
(1) 产生高莫雷约束：
根据Max {f i }，应选取x 1所在行为源行：134133
x x x 3884
+
+=，即，134133x 0x 0x 3884⎛⎫⎛⎫
++++=+ ⎪ ⎪⎝⎭⎝⎭
产生高莫雷约束为：34313
x x 0488
--≤。
(2) 将高莫雷约束加入松弛变量x 5，写入原表最后一行形成下表并用对偶单纯形法求解：
b j。
