整数规划习题解答

一、单选题1、下列说法正确的是（）。

A.分枝定界法在处理整数规划问题时，借用线性规划单纯形法的基本思想，在求相应的线性模型解的同时，逐步加入对各变量的整数要求限制，从而把原整数规划问题通过分枝迭代求出最优解B.用割平面法求解整数规划问题，构造的割平面有可能切去一些不属于最优解的整数解C.用分枝定界法求解一个极大化的整数规划时，当得到多于一个可行解时，通常可任取其中一个作为下界，再进行比较剪枝D.整数规划问题最优值优于其相应的线性规划问题的最优值正确答案：A2、整数规划的最优解中，决策变量满足（）。

A.决策变量不是整数B.没有要求C.决策变量至少有一个是整数D.决策变量必须都是整数正确答案：D3、下列（）可以求解指派问题。

A.梯度法B.牛顿法C.单纯形法D.匈牙利法4、整数规划中，通过增加线性约束条件将原规划可行域进行切割，切割后的可行域的整数解正好是原规划的最优解的方法是（）。

A.隐枚举法B.0-1规划法C.分支定界法D.割平面法正确答案：D5、标准指派问题（m人，m件事）的规划模型中，有（）个决策变量。

A.都不对B. m*mC. mD.2m正确答案：B二、判断题1、匈牙利法可以直接求解极大化的指派问题。

（）正确答案：×2、整数规划的可行解集合是离散型集合。

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

（）4、用分支定界法求一个极大化的整数规划时，当得到多于一个可行解时，通常可以任取一个作为下界值，在进行比较和剪枝。

（）正确答案：×5、用割平面求纯整数规划时，要求包括松弛变量在内的全部变量都取整数。

（）正确答案：√。

第四章 整数规划与分配问题一、建立下列问题的数学模型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 中最多只能选两个。

若某钻井队要从以下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 重要性系数 20 15 18 14 8 4 10解：引入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 内赶到现场。

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

地区1 地区2 地区3 地区4 地区5 地区6 地区1 地区2 地区3 地区4 地区5 地区6 0 10 16 28 27 20 10 0 24 32 17 10 16 24 0 12 27 21 28 32 12 0 15 25 27 17 27 15 0 14 20 10 21 25 14 0解：引入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必须被选中。

第六章---运筹学-整数规划案例第六章整数规划用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域(在图上用“×”标出)。

1、 max z=3x1+2x2. 2x1+3x2≤122x1+x2≤9x1、x2≥0解：2、 min f=10x1+9x2. 5x1+3x2≥45x1≥8x2≤10x1、x2≥0求解下列整数规划问题1、 min f=4x1+3x2+2x3. 2x1-5x2+3x3≤44x1+x2+3x3≥3x2+x3≥1x1、x2、x3=0或1解：最优解（0，0，1），最优值：22、 min f=2x1+5x2+3x3+4x3. -4x1+x2+x3+x4≥2-2x1+4x2+2x2+4x2≥4x1+x2-x2+x2≥3x1、x2、x3、x3=0或1解：此模型没有可行解。

3、max Z=2x1+3x2+5x3+6x4. 5x1+3x2+3x3+x4≤302x1+5x2-x2+3x2≤20-x1+3x2+5x2+3x2≤403x1-x2+3x2+5x2≤25x1、x2、x3、x3=正整数解：最优解（0，3，4，3），最优值：474、 min z =8x1 +4 x2+3 x3+5 x4+2 x5＋3 x6＋4 x7＋3 x8+4 x9+9 x10+7 x11+5 x12 +10 x13+4 x14+2 x15+175 x16+300 x17+375 x18 +500 x19约束条件x1 + x2+x3≤30x4+ x5＋ x6-10 x16≤0x7+ x8＋ x9-20 x17≤0x10+ x11＋ x12-30 x18≤0x13+ x14＋ x15-40 x19≤0x1 + x4+ x7+x10+ x13＝30x2 + x5+ x8+x11+ x14＝20x3 + x6+ x9+x12+ x15＝20x i为非负数（i=1,2…..8）x i为非负整数（i=9,10…..15）x i为为0－1变量（i=16,17…..19）解：最优解（30，0，0，0，0，0，0，0，0，0，0，0，0，20，20，0，0，0，1），最优值：860一餐饮企业准备在全市范围内扩展业务，将从已拟定的14个点中确定8个点建立分店，由于地理位置、环境条件不同，建每个分店所用的费用将有所不同，现拟定的14个店的费用情况如下表：公司办公会决定选择原则如下：（1）B5、B3和B7只能选择一个。

例1 求解下列整数规划得最优解:()123123max 45634510..01,2,3,j j Z x x x x x x s t x j x =++++⎧⎪⎨=⎪⎩≤≥为整数.解 （1）建立动态规划模型:阶段变量: 将给每一个变量 赋值瞧成一个阶段, 划分为3个阶段, 且阶段变量k=1,2,3. 设状态变量 表示从第 阶段到第3阶段约束右端最大值, 则 设决策变量k x 表示第k 阶段赋给变量k x 得值(1,2,3)k =、 状态转移方程: 阶段指标: 基本方程；()(){}()3113,2,1044()max ,()0.s k k k k k k k k k k x a f s u s x f s f s ++⎡⎤=⎢⎥⎢⎥⎣⎦⎧=+⎪⎨⎪=⎩≤≤ 其中1233,4, 5.a a a === 用逆序法求解: 当3k =时，()(){}{}33333443330055max 6max 6,ssx x f s x f s x ⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦=+=≤≤≤而 表示不超过 得最大整数。

因此, 当 时, ；当 时, 可取0或1；当 时, 可取0, 1, 2,由此确定 现将有关数据列入表4.1中当 时, 有()(){}(){}22222332322220044max 5max 54,ssx x f s xf s xf s x ⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦=+=+-≤≤≤≤而 。

所以当 时, ；当 时, ；当 时 。

由此确定 。

现将有关数据列入表4.2中、当时,有()(){}(){}11111221211110033max 4max 43,ssx x f s x f s x f s x ⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦=+=+-≤≤≤≤例5 用动态规划方法解下列非线性规划问题⎩⎨⎧=≥≤++⋅⋅=3,2,1 0 max 3213221i x c x x x x x x z i 解: 解决这一类静态规划问题, 需要人为地赋予时间概念, 从而将该问题转化为多阶段决策过程。

一、判断题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。

第五章 整数规划第四节 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年由库恩提出，此解法用到了匈牙利数学家康尼格的关于矩阵中独立零元素的定理。

第3章 整数规划3.1某公司今后三年内有五项工程可以考虑投资。

每项工程的期望收入和年度费用(万元)如表3-8所示。

表3-8费 用工 程 第一年 第二年 第三年 收 入1 2 3 4 55 1 8 4 7 2 5 967 5 28 69 30 40 20 15 30 资金拥有量30 25 30每项工程都需要三年完成，应选择哪些项目使总收入最大，建立该问题的数学模型。

【解】设1,1,2,,50j j x j j ⎧==⎨⎩投资项目不投资项目，模型为 12345123451234512345max 30402015305457830795625826293001,1,,5j Z x x x x x x x x x x x x x x x x x x x x x j =++++++++≤⎧⎪++++≤⎪⎨++++≤⎪⎪=⎩＝或最优解X ＝(1,1,1,0,1)T ，Z=120万元，即选择项目1、2、3、5时总收入最大。

3.2选址问题。

以汉江、长江为界将武汉市划分为汉口、汉阳和武昌三镇。

某商业银行计划投资9000万元在武汉市备选的12个点考虑设立支行，如图3-8所示。

每个点的投资额与一年的收益见表3－9。

计划汉口投资2～3个支行，汉阳投资1～2个支行，武昌投资3～4个支行。

如何投资使总收益最大，建立该问题的数学模型，说明是什么模型，可以用什么方法求解。

图3-8表3-9地址i 1 2 3 4 5 6 7 8 9 10 11 12投资额(万元) 900 1200 1000 750 680 800 720 1150 1200 1250 850 1000 收益（万元） 400 500 450 350 300 400 320 460 500 510 380 400 【解】设1,1,2,,120,j j x j j ⎧==⎨⎩ 在第个点设立支行在第个点不设立支行模型为12312123111244771212115588max 40050045040090012001000850100090002,3,1,2,3,4101,,12j j j j j j j j j j j j jZ x x x x x x x x x x x x x x x x j =======++++⎧+++++≤⎪⎪≥≤≥≤≥≤⎨⎪⎪==⎩∑∑∑∑∑∑ 或， 最优解：x 1＝x 5=x 12=0，其余x j =1，总收益Z=3870万元，实际完成投资额8920万元。