运筹学教材编写组《运筹学》课后习题-整数规划(圣才出品)

一、单选题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、由图可得：最优解为2、用图解法求解线性规划： Min z=2x 1+x 2⎪⎪⎩⎪⎪⎨⎧≥≤≤≥+≤+-01058244212121x x x x x x解：由图可得：最优解x=1.6,y=6.4Max z=5x 1+6x 2⎪⎩⎪⎨⎧≥≤+-≥-0,23222212121x x x x x x解：由图可得：最优解Max z=5x 1+6x 2, Max z= +∞Maxz = 2x 1 +x 2⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤0,5242261552121211x x x x x x x由图可得：最大值⎪⎩⎪⎨⎧==+35121x x x ， 所以⎪⎩⎪⎨⎧==2321x xmax Z = 8.1212125.max 23284164120,1,2maxZ .jZ x x x x x x x j =+⎧+≤⎪≤⎪⎨≤⎪⎪≥=⎩如图所示，在（4，2）这一点达到最大值为26将线性规划模型化成标准形式：Min z=x 1-2x 2+3x 3⎪⎪⎩⎪⎪⎨⎧≥≥-=++-≥+-≤++无约束321321321321,0,052327x x x x x x x x x x x x解：令Z ’=-Z,引进松弛变量x 4≥0，引入剩余变量x 5≥0，并令x 3=x 3’-x 3’’,其中x 3’≥0,x 3’’≥0Max z ’=-x 1+2x 2-3x 3’+3x 3’’⎪⎪⎩⎪⎪⎨⎧≥≥≥≥≥≥-=++-=--+-=+-++0,0,0'',0',0,05232'''7'''5433213215332143321x x x x x x x x x x x x x x x x x x x7将线性规划模型化为标准形式Min Z =x 1+2x 2+3x 3⎪⎪⎩⎪⎪⎨⎧≥≤-=--≥++-≤++无约束，321321321321,00632442392-x x x x x x x x x x x x解：令Z ’ = -z ，引进松弛变量x 4≥0,引进剩余变量x 5≥0,得到一下等价的标准形式。

第11章网络计划11.1 已知下列资料(表11-1)。

表11-1要求：（1）绘制网络图；（2）用图上计算法计算各项时间参数(除外)；（3）确定关键路线。

解：（1）由题意绘制网络图如图11-1所示。

（2）事项最早时间见图11-1中“□”中的数字，事项最迟时间见图11-1中“△”中的数字。

图11-1（3）总时差为零的工序为关键工序，所以关键路线为①→③→④→⑤→⑥→⑦→⑩→⑪，对应的工序为。

11.2 已知下列资料，如表11-2所示。

rH B G A F K→→→→→要求：（1）绘制网络图；（2）计算各项时间参数；（3）确定关键路线。

表11-2解：（1）由题意绘制网络图如图11-2所示。

（2）事项最早时间见图11-2“□”中的数字，事项最迟时间见图11-2中“△”中的数字。

图11-2（3）总时差为零的工序为关键工序，所以关键路线为，如图11-2所示。

11.3 已知下列资料，如表11-3所示：表11-3求出这项工程的最低成本日程。

解：由表11-3中的已知条件和数据，绘制如图11-3所示的网络图。

图11-3各事项的最早时间为：各事项最迟时间为：()()()()()()(){} 6max44,6,33,6,55,6E E E ET T T T T T T=+++{}max84,45,11012=+++=()()()()(){}{} 7max22,7,66,7max86,12315 E E ET T T T T=++=++=将各事项的最早时间与最迟时间分别记入该事项右下角的“□”和“△”内，如图11-4所示。

图11-4总时差为零的工序为关键工序，从图11-4可以看出关键路线为又已知工程项目每天的间接费用为500元，按图11-4及表11-3中的已知资料，若按图11-4安排，易知工程总工期为l5天，工程的直接费用(各工序直接费用之和)为（20+30+15+5+18+40+10+15）×100=15300元 工程间接费用15×500=7500元 工程总费用为15300+7500=22800元如果要缩短工期，应该首先缩短关键线路上赶一天进度所需费用最小的工序的作业时间。

第14章存储论14.1设某工厂每年需用某种原料1800吨，不需每日供应，但不得缺货。

设每吨每月的保管费为60元，每次订购费为200元，试求最佳订购量。

解：由题意知，该模型为“不允许缺货，生产时间很短”，按E.O.Q计算Q*得所以最佳订购量为32吨。

14.2某公司采用无安全存量的存储策略。

每年使用某种零件100000件，每件每年的保管费为30元，每次订购费为600元。

试求：（1）经济定购批量；（2）订购次数。

解：（1）按E.O.Q模型计算，得所以经济订购批量为2000件。

（2）订购次数为：＝50（次）所以每年的订购次数为50次。

*32()Q==≈吨*Q*2000()Q===件14.3某工厂生产某种零件，每年需要量为18000个，该厂每月可生产3000个，每次生产后的装配费为5000元，每个零件的存储费为1.5元，求每次生产的最佳批量。

解：由题意知，该题模型为“不允许缺货，生产需一定时间”，已知，，。

最佳批量是所以，每次生产的最佳批量为4472个。

14.4某产品每月用量为4件，装配费为50元，存储费每月每件为8元，求产品每次最佳生产量及最小费用。

若生产速度为每月可生产10件，求每次生产量及最小费用。

解：（1）用“不允许缺货，生产时间很短”的模型求解。

已知。

则最佳批量为以月为单位的平均费用为（2）用“不允许缺货，生产需一段时间”的模型求解。

已知，，则最佳批量为最小费用为3C5000=1C 1.5=P3000R180********==÷=，*Q4472==≈（个）31C50R4C8===，，*7()Q==≈件**1374()85056.6()227Q RC Q CCQ=+=⨯+⨯≈元31C50C8P10===，，R4=所以，如果生产时间足够短，那么最佳生产量为7件，最小费用为56.6元；如果生产速度为每月可生产10件，那么最佳生产量为9件，最小费用为43.8元。

14.5每月需要某种机械零件2000件，每件成本l50元，每年的存储费用为成本的16％，每次订购费100元，求E.O.Q 及最小费用。

整数、运输、目标三、整数规划（每小题20分，共100分）1.对应线性规划的最优解是（3.25，2.5），它的整数规划的最优解是A. (4，1)B.(4，3)C.(3，2)D.(2，4)2.下列说法正确的是A.整数规划问题最优值优于其相应的线性规划问题的最优值B.用割平面法求解整数规划问题，构造的割平面有可能切去一些不属于最优解的整数解C.用分枝定界法求解一个极大化的整数规划时，当得到多于一个可行解时，通常可任取其中一个作为下界，再进行比较剪枝D.分枝定界法在处理整数规划问题时，借用线性规划单纯形法的基本思想，在求相应的线性模型解的同时，逐步加入对各变量的整数要求限制，从而把原整数规划问题通过分枝迭代求出最优解。

3. x 1要求是非负整数，它的来源行是A. B. C. D. 4.，最优解是A.（0, 0）B.（0，1）C.（1，0）D.（1，1）5 分枝定界法中a .最大值问题的目标值是各分枝的下界b .最大值问题的目标值是各分枝的上界c .最小值问题的目标值是各分枝的上界d .最小值问题的目标值是各分枝的下界 12121212max 32,2314,0.5 4.5,,0Z x x x x x x x x =++≤+≤≥且为整数145578333x x x -+=32313154-≤-x x －254-≤-x x －254＝＋S x x +254＝－＋s x x 12121212max 3,437,24,,01Z x x x x x x x x =++≤+≤=或e .以上结论都不对A. a,bB. b,dC. c,dD. e四、目标规划（每小题20分，共100分）1.要求不超过第一目标值、恰好完成第二目标值，目标函数是A.B.C.D.2.下列正确的目标规划的目标函数是 "A. max Z ＝d －+d +B. max Z ＝d －－d +C. min Z ＝d －+d +D. min Z ＝d －－d +3. 目标函数的含义是A. 首先第一和第二目标同时不低于目标值，然后第三目标不低于目标值B.第一、第二和第三目标同时不超过目标值C.第一和第二目标恰好达到目标值，第三目标不超过目标值D.首先第一和第二目标同时不超过目标值，然后第三目标不超过目标值4.目标规划)(m in 22211+--++=d d p d p Z )(m in 22211+-+++=d d p d p Z 11222min ()Z p d p d d +-+=+-11222min ()Z p d p d d --+=+-11223min ()Z p d d p d ---=++⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥=-+=-+=-++=-+++++=+-+-+-+-+---+)4,,1(0,,,20506040)(min 21442331222111214332211 i d d x x d d x d d x d d x x d d x x d P d P d d p z i i －的满意解是A.（50，20）B.（40，0）C.（0，60）D.（50，10）5 下列线性规划与目标规划之间错误的关系是A.线性规划的目标函数由决策变量构成，目标规划的目标函数由偏差变量构成B.线性规划模型不包含目标约束，目标规划模型不包含系统约束C.线性规划求最优解，目标规划求满意解D.线性规划模型只有系统约束，目标规划模型可以有系统约束和目标约束E.线性规划求最大值或最小值，目标规划只求最小值五、运输问题（每小题10分，共100分）1.有6个产地7个销地的平衡运输问题模型的对偶模型具有特征A 有12个变量B 有42个约束 C. 有13个约束D．有13个基变量2.有5个产地4个销地的平衡运输问题A.有9个变量B.有9个基变量C. 有20个约束D．有8个基变量3.下列变量组是一个闭回路A.{x11,x12,x23,x34,x41,x13}B.{x21,x13,x34,x41,x12}C.{x12,x32,x33,x23,x21,x11}D.{x12,x22,x32,x33,x23,x21}4. m+n－1个变量构成一组基变量的充要条件是A.m+n－1个变量恰好构成一个闭回路B.m+n－1个变量不包含任何闭回路C.m+n－1个变量中部分变量构成一个闭回路D.m+n－1个变量对应的系数列向量线性相关5.运输问题A.是线性规划问题B.不是线性规划问题C.可能存在无可行解D.可能无最优解6.下列结论正确的有A 运输问题的运价表第r行的每个c ij同时加上一个非零常数k，其最优调运方案不变B 运输问题的运价表第p列的每个c ij同时乘以一个非零常数k，其最优调运方案不变C.运输问题的运价表的所有c ij同时乘以一个非零常数k, 其最优调运方案变化D．不平衡运输问题不一定存在最优解7.下列说法正确的是A.若变量组B包含有闭回路，则B中的变量对应的列向量线性无关B.运输问题的对偶问题不一定存在最优解C. 平衡运输问题的对偶问题的变量非负D．第i行的位势u i是第i个对偶变量8. 运输问题的数学模型属于A.0-1规划模型B.整数规划模型C. 网络模型D.以上模型都是9.不满足匈牙利法的条件是A.问题求最小值B.效率矩阵的元素非负C.人数与工作数相等D.问题求最大值10.下列错误的结论是A.将指派（分配）问题的效率矩阵每行分别乘以一个非零数后最优解不变B.将指派问题的效率矩阵每行分别加上一个数后最优解不变C.将指派问题的效率矩阵每个元素同时乘以一个非零数后最优解不变D.指派问题的数学模型是整数规划模型PPT习题。

第3章 运输问题3.1 复习笔记1．运输问题的数学模型运输问题：已知有m 个生产地点,1,2,,i A i m =…，可供应某种物资，其供应量（产量）分别为i a ，1,2,,i m =…，有n 个销地j B ，1,2,,j n =…，其需要量分别为j b ，1,2,,j n =…，从i A 到j B 运输单位物资的运价（单价）为ij c 。

如何安排运输，能使得总运输成本最小？（1）产销平衡运输问题的数学模型1111min ,1,2,,..,1,2,,0m nij iji j mij j i nij i j ijz c x x b j n s t x a i mx =====⎧==⎪⎪⎪==⎨⎪⎪≥⎪⎩∑∑∑∑ 模型特点：①该模型包含m n ⨯个变量，()m n +个约束方程；②该系数矩阵中对应于变量ij x 的系数向量ij P ，其分量中除第i 个和第m j +个为1外，其余的都为零。

即(01010)T ij i m j P e e +==+…………③对于产销平衡的运输问题，有以下关系式存在：111111n m n n m m j ij ij i j i j j i i b x x a ======⎛⎫⎛⎫=== ⎪ ⎪⎝⎭⎝⎭∑∑∑∑∑∑ 所以模型最多只有m+n-1个独立约束方程。

即系数矩阵的秩≤m+n -1。

注意：运输问题的基变量一定是m+n-1个，m+n-1个变量构成基变量的充要条件是它们不构成闭回路。

闭回路的特点：在运输产销平衡表中，每一条边都是水平或垂直的；每一行或每一列至多只有两个闭回路的顶点。

（2）产销不平衡运输问题的数学模型当产大于销，即11m n i j i j a b ==>∑∑时，运输问题的数学模型可写成：1111min ,1,2,,..,1,2,,0m n ij iji j mij j i nij i j ijz c x x b j n s t x a i mx =====⎧==⎪⎪⎪≤=⎨⎪⎪≥⎪⎩∑∑∑∑ 当产小于销，即11m n i j i j a b ==<∑∑时，运输问题的数学模型可写成：11min m n ij ij i j z c x ===∑∑11, (1,2,,), (1,2,,)0nij i j mij j i ij x a i m x b j n x ==⎧==⎪⎪⎪≤=⎨⎪⎪≥⎪⎩∑∑……2．表上作业法表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法。

第四章 整数规划４.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。

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