下载文档原格式
管理运筹学试题（B）一．单项选择（将唯一正确答案前面的字母填入题后的括号里。
正确得1分，选错、多选或不选得0分。
共15分）1．线性规划标准型中bi（i=1，2，……m）必须是（）A．正数B．非负数C．无约束D．非零的正确答案：A: B: C: D:2．线性规划问题的基本可行解X对应于可行域D的（）A．外点B．所有点C．内点D．极点正确答案：A: B: C: D:3．基本可行解中的非零变量的个数小于约束条件数时，该问题可求得 ( ）A．基本解B．退化解C．多重解D．无解正确答案：A: B: C: D:4．原问题的第i个约束方程是“=”型，则对偶问题的变量qi是（）A．多余变量B．自由变量C．松弛变量D．非负变量正确答案：A: B: C: D:5．若原问题是求目标最小，则对偶问题的最优解值就等于原问题最优表中多余变量的（）A．机会费用B．个数C．值D．机会费用的相反数正确答案：A: B: C: D:6．求解指派问题的匈牙利方法要求系数矩阵中每个元素都是（）A．非负的B．大于零C．无约束D．非零常数正确答案：A: B: C: D:7．设V是一个有n个顶点的非空集合，V={v1，v2，……，vn}，E是一个有m条边的集合，E={e1，e2，……em}，E中任意一条边e是V的一个有序元素对[u，v]，（u≠v），则称V和E这两个集合组成了一个（）A．无向图B．有向图C．完备图D．树正确答案：A: B: C: D:8．若一个闭链C除了第一个顶点和最后一个顶点相同外，没有相同的顶点和相同的边，则该闭链C称为（）A．初等链B．圈C．回路D．饱和链正确答案：A: B: C: D:9．若有向图G有根u，且基本图是一棵树，则称G 为以u为根的（）A．有向树B．完备图C．简单图D．分离图正确答案：A: B: C: D:10．若Q为f增流链，则Q中所有前向边都为f （）A．对边B．饱和边C．邻边D．不饱和边正确答案：A: B: C: D:11．若G中不存在流f增流链，则f为G的（）A．最小流B．最大流C．最小费用流D．无法确定正确答案：A: B: C: D:12．若f 是G的一个流，K为G的一个割，且Valf=CapK，则K一定是（）A．最小割B．最大割C．最小流D．最大流正确答案：A: B: C: D:13．若树T有n个顶点，那么它的边数一定是（）A．n2 B．n C．n+1 D．n-1正确答案：A: B: C: D:14．对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验但不完全满足（）A．等式约束B．“≤”型约束C．“≥”约束D．非负约束正确答案：A: B: C: D:15．用割平面法求解整数规划时，构造的割平面只能切去（）A．整数可行解B．整数解最优解C．非整数解D．无法确定正确答案：A: B: C: D:二．多项选择题（每题至少有一个答案是正确的。
2015年管理运筹学一真题解析一、选择题（16分，共8小题）（答在试卷上的内容无效） 1.在线性规划模型中，满足约束条件和非负条件的解称为（B ）。
A.基本解 B.可行解 C.基本可行解 D.最优解解析：取一组包含m 个线性无关的系数向量组成的基，令其余非基变量等于0的解就是基本解；可行解是指满足约束条件和非负约束的解；基本可行解是指在同时满足约束条件方程和非负约束的基本解；最优解是指使目标函数达最优的解。
因此选B 。
2.在统筹图中，某一关键工序的总时差一定（C ）该工序的单时差。
A.不大于 D.不小于 C.等于 D.不确定解析：这是关键工序的性质之一即关键工序总时差一定为0，单时差也一定为0，因此总时差等于单时差，故选C 。
3.若定义1,,1,20,ii i A x i A ⎧⎪==⎨⎪⎩投资项目不投资项目，一下那个约束条件准确表达“投资A 1的前提是必须投资A 2”。
（D ） A. 121x x +≤B. 120x x +≥C. 120x x -=D. 120x x -≤解析：这是对0-1规划的约束条件的考查。
要表示“投资A 1的前提是必须投资A 2”，则有x 1≤x 2，即x 1-x 2≤0.当左端为1时，右端必为1，这就清楚表达了“投资A 1的前提是必须投资A 2”。
因此选D 。
4.将一个指派问题的费用矩阵的某行各元素都加上常数k 得到一个新的矩阵，这一新矩阵对应着一个新的指派问题，则（A ）。
A.新问题与原问题有相同的最优解；B.新问题最优目标值大于原问题最优目标函数值；C.新问题最优解等于原问题最优解加上k ;D.新问题最优解小于原问题最优解。
解析：这是对指派问题解法的考查。
在元素上都加常数k ，这样做以后其目标函数值与原目标函数值仅仅相差一个k,而最优解是相同的。
（详见寇伟华版运筹学154-155页）5.将连接六个城市的部分道路改造为高速公路，使各个城市均能通达，又要使高速公路的总长度最小，该问题属于（A ）。
《管理运筹学》第二版习题答案(韩伯棠教授)高等教育出版社第 2 章 线性规划的图解法11a.可行域为 OABC 。
b.等值线为图中虚线所示。
12c.由图可知，最优解为 B 点，最优解： x 1 = 769 。
7 2、解：15 x 2 =7， 最优目标函数值：a x 210.60.1O1有唯一解x 1 = 0.2函数值为 3.6x 2 = 0.6b 无可行解c 无界解d 无可行解e 无穷多解1 2 2 1 2f 有唯一解20 x 1 =3 8函数值为 92 33、解：a 标准形式：b 标准形式：c 标准形式：x 2 = 3max fmax f= 3x 1 + 2 x 2 + 0s 1 + 0s 2 + 0s 3 9 x 1 + 2x 2 + s 1 = 303x 1 + 2 x 2 + s 2 = 13 2 x 1 + 2x 2 + s 3 = 9 x 1 , x 2 , s 1 , s 2 , s 3 ≥= −4 x 1 − 6x 3 − 0s 1 − 0s 23x 1 − x 2 − s 1 =6x 1 + 2x 2 + s 2 = 10 7 x 1 − 6 x 2 = 4x 1 , x 2 , s 1 , s 2 ≥max f = −x ' + 2x ' − 2 x ''− 0s − 0s'''− 3x 1 + 5x 2 − 5x 2 + s 1 = 70 2 x ' − 5x ' + 5x '' = 50122' ' ''3x 1 + 2 x 2 − 2x 2 − s 2 = 30'' ''4 、解：x 1 , x 2, x 2, s 1 , s 2 ≥ 0标准形式： max z = 10 x 1 + 5x 2 + 0s 1 + 0s 23x 1 + 4 x 2 + s 1 = 9 5x 1 + 2 x 2 + s 2 = 8 x 1 , x 2 , s 1 , s 2 ≥ 0s 1 = 2, s 2 = 0标准形式： min f = 11x 1 + 8x 2 + 0s 1 + 0s 2 + 0s 310 x 1 + 2x 2 − s 1 = 203x 1 + 3x 2 − s 2 = 18 4 x 1 + 9x 2 − s 3 = 36 x 1 , x 2 , s 1 , s 2 , s 3 ≥ 0s 1 = 0, s 2 = 0, s 3 = 136 、解：b 1 ≤c 1 ≤ 3c 2 ≤ c 2 ≤ 6d x 1 = 6 x 2 = 4e x 1 ∈ [4,8]x 2 = 16 − 2x 1f 变化。
2015年管理运筹学二真题解析一、问答题（70分，共10小题，每小题7分）（答在试卷上的内容无效）1.应用单纯型法求解线性规划问题时，出现不可行解的特征是什么？ 答：当b 的值出现负数时即表明出现不可行解。
2.简述建立对偶模型的规则。
答：规则如下：（1）在原问题（P ）中，目标函数为求1min nj j j f c x ==∑，其约束条件统一成“≥”或“=”。
（2）在对偶问题（D ）中，目标函数为求1min mi i i z b u ==∑。
（3）在原问题（P ）中与b i 相应的一个约束条件，对应着对偶问题（D ）的一个变量u i ：如果该约束条件为不等式，则u i ≥0；若该约束条件为等式，则u i 为自由变量。
（4）在原问题（P ）的每个变量x j 对应对偶问题（D ）的每一个约束条件：若（P ）中x j ≥0，则（D ）中为1mii i j i a u c =≤∑；若x j 为自由变量，则1mii i j i a u c ==∑。
3.针对增加约束条件方程时，应如何应用对偶单纯型法进行求解？ 答：其步骤如下：（1）检验原来的最优解是否满足新增的约束条件，若满足原最优解就是新的最优解，否则转第二步；（2）将新增的约束条件方程加上松弛变量或减去多余变量使其化为等式，再把这个等式方程的系数补加到原模型的最有单纯型表中；（3）令原来的基变量和新增的松弛或多余变量作为新的基变量；（4）对新的单纯型表进行初等变换，使新基的系数矩阵变为单位矩阵，此时可以得到一个满足最优检验但不一定满足非负约束条件的可行解；（5）利用对偶单纯型法进行迭代求解。
4.对b i 的灵敏度分析的目的是什么？答：其目的是在cj 和aj 不变的前提下并在保证不改变原来最优解基变量但基变量取值可以变动的情况下，求出bi 值允许变化的范围。
并且是在求出最优解以后不必将参数从头算起，就知道最优解及其目标函数值会发生什么变化，使决策者只花很少的费用就可以得到比一组最优解更多的信息。
第2章 线性规划的图解法1．解：x`A 1 (1) 可行域为OABC(2) 等值线为图中虚线部分(3) 由图可知，最优解为B 点， 最优解：1x =712，7152=x 。
最优目标函数值：7692．解： x 2 10 1(1) 由图解法可得有唯一解 6.02.021==x x ，函数值为3.6。
(2) 无可行解 (3) 无界解 (4) 无可行解 (5)无穷多解(6) 有唯一解 3832021==x x ，函数值为392。
3．解：(1). 标准形式：3212100023m ax s s s x x f ++++=,,,,9221323302932121321221121≥=++=++=++s s s x x s x x s x x s x x(2). 标准形式：21210064m in s s x x f +++=,,,46710263212121221121≥=-=++=--s s x x x x s x x s x x(3). 标准形式：21''2'2'10022m in s s x x x f +++-=,,,,30223505527055321''2'2'12''2'2'1''2'2'11''2'21≥=--+=+-=+-+-s s x x x s x x x x x x s x x x4．解：标准形式：212100510m ax s s x x z +++=,,,8259432121221121≥=++=++s s x x s x x s x x松弛变量（0，0） 最优解为 1x =1，x 2=3/2.标准形式：32121000811m in s s s x x f ++++=,,,,369418332021032121321221121≥=-+=-+=-+s s s x x s x x s x x s x x剩余变量（0.0.13） 最优解为 x 1=1，x 2=5.6．解：(1) 最优解为 x 1=3，x 2=7. (2) 311<<c (3) 622<<c (4)4621==x x(5) 最优解为 x 1=8，x 2=0. (6) 不变化。
运筹学（第2版）习题答案2第1章 线性规划 P36~40第2章 线性规划的对偶理论 P68~69 第3章 整数规划 P82~84 第4章 目标规划 P98~100 第5章 运输与指派问题 P134~136 第6章 网络模型 P164~165 第7章 网络计划 P185~187 第8章 动态规划 P208~210 第9章 排队论 P239~240 第10章 存储论 P269~270 第11章 决策论 Pp297－298 第12章 博弈论 P325~326 全书360页由于大小限制，此文档只显示第6章到第12章，第1章至第5章见《运筹学课后答案1》习题六6.1如图6－42所示，建立求最小部分树的0－1整数规划数学模型。
【解】边[i ，j ]的长度记为c ij ，设⎩⎨⎧=否则包含在最小部分树内边0],[1j i x ij数学模型为：,12132323243434364635365612132434343546562324463612132446362335244656121324354656m in 52,22,233344,510ij ijij i j ij Z c x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x ==++≤++≤++≤++≤+++≤+++≤+++≤++++≤++++≤+++++≤=∑或,[,]i j ⎧⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎩所有边6.2如图6－43所示，建立求v 1到v 6的最短路问题的0－1整数规划数学模型。
图6－42【解】弧(i ，j )的长度记为c ij ，设⎩⎨⎧=否则包含在最短路径中弧0),(1j i x ij数学模型为：,1213122324251323343524344546253545564656m in 100,00110,(,)ijiji jij Z cx x x x x x x x x x x x x x x x x x x x x x i j =⎧+=⎪---=⎪⎪+--=⎪⎪+--=⎨⎪++-=⎪⎪+=⎪=⎪⎩∑或所有弧 6.3如图6－43所示，建立求v 1到v 6的最大流问题的线性规划数学模型。
运筹学（第2版）习题答案2第1章 线性规划 P36~40第2章 线性规划的对偶理论 P68~69 第3章 整数规划 P82~84 第4章 目标规划 P98~100 第5章 运输与指派问题 P134~136 第6章 网络模型 P164~165 第7章 网络计划 P185~187 第8章 动态规划 P208~210 第9章 排队论 P239~240 第10章 存储论 P269~270 第11章 决策论 Pp297－298 第12章 博弈论 P325~326 全书360页由于大小限制，此文档只显示第6章到第12章，第1章至第5章见《运筹学课后答案1》习题六6.1如图6－42所示，建立求最小部分树的0－1整数规划数学模型。
【解】边[i ，j ]的长度记为c ij ，设⎩⎨⎧=否则包含在最小部分树内边0],[1j i x ij数学模型为：,12132323243434364635365612132434343546562324463612132446362335244656121324354656m in 52,22,233344,510ij ijij i j ij Z c x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x ==++≤++≤++≤++≤+++≤+++≤+++≤++++≤++++≤+++++≤=∑或,[,]i j ⎧⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎩所有边6.2如图6－43所示，建立求v 1到v 6的最短路问题的0－1整数规划数学模型。
图6－42【解】弧(i ，j )的长度记为c ij ，设⎩⎨⎧=否则包含在最短路径中弧0),(1j i x ij数学模型为：,1213122324251323343524344546253545564656m in 100,00110,(,)ijiji jij Z cx x x x x x x x x x x x x x x x x x x x x x i j =⎧+=⎪---=⎪⎪+--=⎪⎪+--=⎨⎪++-=⎪⎪+=⎪=⎪⎩∑或所有弧 6.3如图6－43所示，建立求v 1到v 6的最大流问题的线性规划数学模型。
17春西南交《管理运筹学基础》在线作业二答案一、单项选择题（共37 道试题，共74 分。
）1. 不属于线性规划数学模型三要素：（）A. 决策变量B. 规划模型C. 目旳函数D. 约束条件对旳答案：2. 对偶问题旳变量qi是自由变量，则原问题中第i个约束条件是（）A. ≤型B. ≥型C. =型D. 以上三者都不对对旳答案：3. 不合用在不确定条件下进行决策旳措施是( )A. 最大最小决策原则B. 现实主义旳决策原则C. 最小期望损失值原则D. 乐观主义决策原则对旳答案：4. 若原问题是一原则型，则对偶问题旳最优解值就等于原问题最优表中松弛变量旳（）A. 值B. 个数C. 机会费用D. 检查数对旳答案：5. 线性规划问题旳基可行解与可行域顶点旳关系是（）A. 顶点与基可行解无关B. 顶点少于基可行解C. 顶点与基可行解无关D. 顶点多于基可行解对旳答案：6. 从教材列举旳实例中可以归纳出求最短路线问题应从（）开始推算。
A. 终点B. 起点C. 中间点D. 终点和起点对旳答案：7. 敏捷度分析研究旳是线性规划模型中两个数据之间旳变化和影响，这两个数据是原始数据和（）A. 决策变量B. 松弛变量C. 基本解D. 最优解对旳答案：8. 一般讲，对于某一问题旳线性规划与该问题旳整数规划可行域旳关系存在（）A. 前者不小于后者B. 后者不小于前者C. 两者相等D. 两者无关对旳答案：9. 运筹学研究功能之间关系是应用（）A. 系统观点B. 整体观点C. 联络观点D. 部分观点对旳答案：10. 求解需求量不不小于供应量旳运送问题不需要做旳是（）A. 虚设一种需求点B. 令供应点到虚设旳需求点旳单位运费为0C. 取虚设旳需求点旳需求量为恰当值D. 删去一种供应点对旳答案：11. 用运筹学分析与处理问题旳过程是一种（）A. 预测过程B. 科学决策过程C. 计划过程D. 控制过程对旳答案：12. 对偶问题旳对偶是（）A. 基本问题B. 无法确定C. 其他问题D. 原问题对旳答案：13. 线性规划问题有可行解，则（）A. 必有基可行解B. 必有唯一最优解C. 无基可行解D. 无唯一最优解对旳答案：14. 线性规划敏捷度分析应在( )旳基础上，分析系数旳变化对最优解产生旳影响。
15秋西南交大《管理运筹学A》在线作业二答案西南交《管理运筹学》在线作业二一、单选题（共 35 道试题，共 70 分。
）1. 求解0—1整数规划的方法是（）. 割平面法. 分枝定界法. 隐枚举法. 匈牙利法正确答案：2. 图解法适用于求解有关线性规划问题，但该问题中只能含有（）. 一个变量. 两个变量. 三个变量. 四个变量正确答案：3. 若原问题是一标准型，则对偶问题的最优解值就等于原问题最优表中松弛变量的（）. 值. 个数. 机会费用. 检验数正确答案：4. 在求最大流量的问题中，已知与起点相邻的三节点单位时间的流量分别为10，12，15，则终点单位时间输出的最大流量应（）. 等于27. 大于或等于37. 小于37. 小于或等于37正确答案：5. 不适用在不确定条件下进行决策的方法是( ). 最大最小决策标准. 现实主义的决策标准. 最小期望损失值标准. 乐观主义决策标准正确答案：6. 运筹学研究功能之间关系是应用（）. 系统观点. 整体观点. 联系观点. 部分观点正确答案：7. 在图论中，图是一种工具，它反映研究对象之间的（）. 线性相关关系. 非线性相关关系. 一般关系. 特定关系正确答案：8. 线性规划问题的基可行解与可行域顶点的关系是（）. 顶点与基可行解无关. 顶点少于基可行解. 顶点与基可行解无关. 顶点多于基可行解正确答案：9. 从趋势上看，运筹学的进一步发展依赖于一些外部条件及手段，其中最主要的是（）. 数理统计. 概率论. 计算机. 管理科学正确答案：10. 运筹学作为一门现代的新兴科学，起源于第二次世界大战的（）. 工业活动. 军事活动. 政治活动. 商业活动正确答案：11. 下面几种情形中，不可能是线性规划数学模型的约束条件形式的是( ). =. ＜. ≥. ≤正确答案：12. 数学模型中，“s·t”表示（）. 目标函数. 约束. 目标函数系数. 约束条件系数正确答案：13. 用分枝定界法求极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的（）. 原解. 上界. 下界. 最优解正确答案：14. 在用图解法求解线性规划问题时，如果取得极值的等值线与可行域的一段边界重合，则该问题有（）. 无界解. 唯一最优解. 无可行解. 无穷多最优解正确答案：15. 求解需求量小于供应量的运输问题不需要做的是（）. 虚设一个需求点. 令供应点到虚设的需求点的单位运费为0. 取虚设的需求点的需求量为恰当值. 删去一个供应点正确答案：16. 灵敏度分析研究的是线性规划模型中两个数据之间的变化和影响，这两个数据是原始数据和（）. 决策变量. 松弛变量. 基本解. 最优解正确答案：17. 对偶问题的对偶是（）. 基本问题. 无法确定. 其它问题. 原问题正确答案：18. 约束条件为X=，X≥0的线性规划问题的可行解集是（）. 补集. 凸集. 交集. 凹集正确答案：19. 下面几种情形中，不可能是线性规划数学模型的约束条件形式的是. =. ＜. ≥. ≤正确答案：20. 用运筹学解决问题时，要对问题进行（）. 分析与考察. 分析和定义. 分析和判断. 分析和实验正确答案：21. 对于运筹学模型，（）。
机密★启用前西南交通大学2018年硕士研究生招生入学考试试卷试题代码：961 试题名称：管理运筹学二考试时间：2017年12月考生注意：1.本试题共三大题，共3页，满分150分，请认真检查；2.答题时，请直接将答题内容写在考场提供的答题纸上，答在试卷上的内容无效；3.请在答题纸上按要求填写试题代码和试题名称；4.试卷不得拆开，否则遗失后果自负。
一、 问答题（70分，共10小题，每小题7分）（答在试卷上的内容无效） 1、利用数学表达式凸集与凹集的区别。
解析：设K 是n 维欧式空间的一个点集，若任意两点(1)(2)X K X K ∈∈、的连线上一切点(1)(2)+-X X K ααα∈≤≤（1）（01），则称K 为凸集；相反，不满足上述条件的称为凹集。
2、 以max 为例，如何运用检验数j j c z -判断基本可行解是否为最优解？解析：当可行解全部检验数0j j c z -≤时达到最优解。
3、 如果原问题模型存在约束方程是“=”形式，那么转换对偶模型应该怎么处理？解析：有两种处理方式：①将“=”形式的约束条件方程变为“≥”和“≤”两个不等式方程；②可以不进行变动，对偶问题中对应的变量i y 就作为自由变量。
4、 若新增加了约束条件方程，简述运用对偶单纯形法扩展应用的求解思路。
解析：第一步：检验原来的最优解是否满足新增加的约束条件方程，如果满足，原来的最优解就是新模型的最优解，否则转到第二步；第二步：将新增加的约束条件方程加上松弛变量或减去多余变量使其化为等式，再把这个等式方程的系数补加到原模型的最优单纯形表中；第三步：另原来的基变量和新增加的松弛变量或多余变量作为新的基变量； 第四步：对新的单纯形表进行初等变换，使新基变量的系数矩阵变为单位矩阵，此时可以得到一个满足最优检验但不一定满足非负约束的可行解； 第五步：利用对偶单纯形法继续迭代求解。
5、 设有一闭回路如下所示，'',,,i j i j u u v v 是图中基变量对应的位势。
2015年961管理运筹学二解析(西南交通大学)2015年管理运筹学二真题解析一、问答题（70分，共10小题，每小题7分）（答在试卷上的内容无效）1.应用单纯型法求解线性规划问题时，出现不可行解的特征是什么？答：当b 的值出现负数时即表明出现不可行解。
2.简述建立对偶模型的规则。
答：规则如下：（1）在原问题（P ）中，目标函数为求1min nj jj f c x ==∑，其约束条件统一成“≥”或“=”。
（2）在对偶问题（D ）中，目标函数为求1min mi ii z b u ==∑。
（3）在原问题（P ）中与b i 相应的一个约束条件，对应着对偶问题（D ）的一个变量u i ：如果该约束条件为不等式，则u i ≥0；若该约束条件为等式，则u i 为自由变量。
（4）在原问题（P ）的每个变量x j 对应对偶问题（D ）的每一个约束条件：若（P ）中x j ≥0，则（D ）中为1mii iji a u c =≤∑；若x j 为自由变量，则1mii iji a uc ==∑。
3.针对增加约束条件方程时，应如何应用对偶单纯型法进行求解？答：其步骤如下：（1）检验原来的最优解是否满足新增的约束条件，若满足原最优解就是新的最优解，否则转第二步；（2）将新增的约束条件方程加上松弛变量或减去多余变量使其化为等式，再把这个等式方程的系数补加到原模型的最有单纯型表中；（3）令原来的基变量和新增的松弛或多余变量作为新的基变量；（4）对新的单纯型表进行初等变换，使新基的系数矩阵变为单位矩阵，此时可以得到一个满足最优检验但不一定满足非负约束条件的可行解；（5）利用对偶单纯型法进行迭代求解。
4.对b i的灵敏度分析的目的是什么？答：其目的是在cj和aj不变的前提下并在保证不改变原来最优解基变量但基变量取值可以变动的情况下，求出bi值允许变化的范围。
并且是在求出最优解以后不必将参数从头算起，就知道最优解及其目标函数值会发生什么变化，使决策者只花很少的费用就可以得到比一组最优解更多的信息。
5.简述表上作业法的主要求解步骤。
答：步骤如下：（1）利用差值法或最小值法求出一组初始可行解：（2）用闭回路法或位势法求检验数，若无负检验数即得最优解，若有，则转第（3）步；（3）利用闭回路法进行调整；（4）重复第（2）步，直到得到最优解。
6.分支定界法在满足什么情况下停止分支？答：当发生下列三种情况之一，就不再分支：（1）该分支子问题无可行解，再分也无可行解；（2）已求得一个不违反任一整数约束的解，此时再分也不可能得到更优的解；（3）此子问题的解不优于任一不违反整数约束的另一子问题的目标函数值。
7.简述寻找最小生成树的避圈法的思路。
答：思路如下：（1）在连通的无向图G中，从所有边中选出一条权最小的边，并把它纳入树中；（2）在G中剩余的边中再选择一条权最小且与选进树中的边不构成回路的边，同样将其纳入树中；（3）如此反复，直到找不出这样的边为止。
8.简述平行作业法在缩短工期时的思路。
答：在工程项目任务十分紧迫、工作面允许以及资源保证供应的条件下，可以组织几个相同的施工队，在同一时间、不同的工区上进行施工，称为平行施工组织方式。
可以充分利用工作面，争取时间、缩短施工工期。
9.简述时间参数法确定关键路线的思路。
答：思路如下：（1）正确绘制统筹图并计算出时间参数即最早时间和最迟时间；（2）计算出总时差，此时总时差为0的工序就是关键工序；（3）由关键工序组成的一条路线就是关键路线。
10.针对网络流f,如何鉴别其为最小费用流？答：构造图G的伴随网络图G f，检查其中是否存在负费用增流圈，若不存在，则是最小费用最大流，否则，就不是。
二、计算题（60分，共4小题，每小题15分）（答在试卷上的内容无效）1.某运输网络G如下图，各条边数字依次为容量、流量、费用。
请完成（1）判断图G 是否为可行流。
（3分） （2）判断图G 是否为流值为10 的最小费用流，若不是，将当前网络调整为最小费用流。
要求计算出总费用。
（6分）（3）求图G 的最小费用最大流。
要求计算出总费用。
（6分）解析：本题是求最小费用最大流，应当熟知什么是可行流，掌握求最大流和最小费用最大流的算法。
解：（1）由于每条边的流值均满足容量限制，每个节点的流量也满足流量守恒，故此流是可行流。
（2）构造伴随网络G f 如下：8,6,110,4,26,4,44,2,48,8,2tv 2v 1s图中存在负费用增流圈v 1 v 2 t v 1, 所以不是最小费用流。
在增流圈上调整即具有负费用的边减去调整值2，费用为正值的边加上调整值2得：继续构造伴随网络图：此图已不存在负费用增流圈。
则已求得流值为6,-16,22,48,-2tv 2v 1s2,42,-44,-24,-42,16,2,48,8,110,6,28,8,2tv 2v 1s4,2,48,-14,24,48,-2tv 2v 1s2,42,-46,-22,-410的最小费流，费用为： 8×2+2×4+6×2+8×1+2×4=52 （3）用标号算法求最大流：找到增流链sv 1v 2t,调整量为2，调整后得：上图已找不到增流链，故得最大流，流值为12.现构造其伴随网络图：4,2,4sv 1v 2t8,8,210,6,28,8,16,2,4∞)(s,2)2(v 1,2)6,4,48,8,110,4,28,8,2tv 2v 1s4,4,4图中已找不到负费用增流圈，故得到最小费用最大流，其费用为：8×2+4×4+4×4+4×2+8×1=64。
2、某企业经营管理2个加工厂甲和乙，有3个原材料基地以下列数量供应原料： 原材料基地A ：200t ，单价200元/t ； 原材料基地B ：300t ，单价180元/t ； 原材料基地C ：400t ，单价600元/t ； 单位运价表（元/t ）如下： 加工厂原材料基地甲乙A4050 8,-16,22,48,-2tv 2v 1s4,-44,-24,-4B 20 30C 100 60两个加工厂的容量及加工费如下：加工厂甲乙容量450t 500t加工费400元/t 300元/t请完成（1）试建立该运输问题的模型。
（6分）（2）加工厂出售产品的价格是900元/t，问该企业如何组织两个加工厂的生产，使获得的利润最大？利润值是多少？（9分）解析：本题考查的时不平衡运输问题及表上作业法。
需要注意的是，此时的“运费”包括单位运价和加工费，由于供需不平衡，需要虚设一个原材料基地D，其供应量为50t；至于求检验数的方法有闭回路和位势法，一般情况下闭回路法较为简单，不易出错而位势法需要求多个变量的值容易算错。
解：（1）需要虚设一个原材料基地D，其供应量为50t，得供需平衡表如下：甲乙销量加工厂原料A 640 750 200B 600 510 300C 660 520 400D 0 0 50产量450 500用差值法求解（括号中即为运量）：甲乙销量加工厂原料A （200）200B （200）（100）300C （400）400D （50）50产量450 500用闭回路法非基变量检验数(括号中数字)如下:甲乙销量加工厂原料A 200 (200) 200B 200 100 300C (50) 400 400D 50 (90) 50 产量450500所有检验数都大于0,已得最优解为(X 11,X 21,X 22,X 32,X 41)=(200,200,100,400,50) 最大利润900×900-200×640-200×600-100×510-400×520=303000元.3.下图所示的运输网络，边旁数字表示的最大通行能力。
假设该运输网络中某些节点有流量需求，此处已知v 6需要5个流量。
请构造分配最大流的新网络图，并分配最大流。
解析：本题是有节点流量限制的最大流分配问题，一般处理方法是将节点分成两个节点中间相连接的边的权即为该节点所需流量；解：将节点6拆分为v 61和v 62，新网络图如下：1083643342945v 7v 6v 5v 4v 3v 2v 1初始可行流为0，用标号算法求最大流：增流链v 1v 2v 5v 7,调整量2：继续寻找增流链：5v 62v 611083643342945v 7v 5v 4v 3v 2v 1(v 5,2)(v 1,5)(0,+∞)5,0v 62v 6110,08,03,06,04,03,03,04,02,09,04,05,0v 7v 5v 4v 3v 2v 1v 1v 2v 3v 4v 5v 75,24,09,02,24,03,03,04,06,03,08,210,0v 61v 625,0增流链为v 1v 3v 61v 62v 7,调整量4：继续寻找增流链：增流链为v 1v 4v 5v 7，调整量为4：(v 62,4)613(v 1,9)(0,+∞)v 1v 2v 3v 4v 5v 75,24,09,02,24,03,03,04,06,03,08,210,0v 61v 625,0v 1v 2v 3v 4v 5v 75,24,09,42,24,43,03,04,06,03,08,210,4v 61v 625,4(v 5,4)(v 1,4)(0,+∞)v 1v 2v 3v 4v 5v 75,24,09,42,24,43,03,04,06,03,08,210,4v 61v 625,4继续寻找增流链：增流链为v 1v 3v 4v 61v 62v 7，调整量为1：此时标号已无法进行，得到最大流，流值为11.4.下图为统筹网络图，边旁数字表示工序名称和v 1v 2v 3v 4v 5v 75,24,49,42,24,43,03,04,46,03,08,610,4v 61v 625,4(v 62 ,1)(v 61 ,1)(v 43)(v 3 ,3)(v 1,5)(0,+∞)v 1v 2v 3v 4v 5v 75,24,49,42,24,43,03,04,46,03,08,610,4v 61v 625,4v 1v 2v 3v 4v 5v 75,24,49,52,24,43,03,14,46,13,08,610,5v 61v 625,5工序时间（天）。
问题如下：（1）利用时间参数法计算总工期并确定关键路线及关键工序。
（6分）（2）通过改进措施，使工序c 的工序时间减少1天，是否对工程总工期有影响？为什么？ （3）因为意外原因，使工序b 的工序时间延长了2天，是否对工程总工期有影响？为什么？（3分）（4）因为意外原因，使工序b 的工序时间延长了2天，工序d 的工序时间延长了3天，是否对工程总工期有影响？为什么？（3分） 解析：本题是绘制统筹图相关的问题。
