2017运筹学课外练习题题库.doc

2017运筹学课外练习题题库1、 判断题1若线性规划可行域无界则无最优解。( )2在二元线性规划问题中，如问题有可行解，且可行域有界，则一定有最优解。( )3已知在线性规划的对偶问题的最优解中，对偶变量，说明在最优生产计划中,第i种资源已经完全用尽。( )4线性规划具有唯一最优解是指最优表中非基变量检验数全部非零。( )5运输问题不一定存在最优解。( )6互为对偶的两个线性规划, 对任意可行解X 和Y，存在关系ZW。( )7要求不低于目标值的目标函数是。( )8若原问题具有m个约束，则它的对偶问题具有m个变量。( ) 9有5个产地3个销地的平衡运输问题模型具有15个变量。( )10如果运输问题的单位运价表的某一行（或某一列）元素再乘上那个一个常数 ，最优调运方案将不会发生变化。 （ ） 11求极小值的目标值是各分枝的下界。 ( )12若 分别是某一线性规划问题的最优解，则也是该线性规划问题的最优解，其中的实数。( )13原问题不可行，则对偶问题具有无界解。( ) 14. 线性规划标准型的变量一定要非负。( )16整数规划的最优解是先求相应的线性规划的最优解然后取整得到。( )17运输问题的所有结构约束条件都是等式约束。( )18运输问题m+n1个变量构成基变量组的充要条件是它们不包含闭回路。( )19. 用单纯形法求解一般线性规划时，当目标函数求最小值时，若所有的检验数Cj-Zj0，则问题达到最优。( )20. 对偶问题的目标函数总是与原问题目标函数相等。( )21. 工程计划网络中的关键路线上事项的最早时间和最迟时间往往不相等。( )22. 指派问题的解中基变量的个数为mn。( )23. 运输问题的基本可行解不含闭回路。( )24. 目标规划中，正偏差变量大于等于零，负偏差变量小于等于零。( )25如果运输问题的单位运价表的某一行（或某一列）元素再乘上那个一个常数 ，最优调运方案将不会发生变化。 （ ） 26运输问题解的情况有四种：无可行解；无界解；唯一最优解；无穷多最优解。( )27. 互为对偶问题，或者同时都有最优解，或者同时都无最优解。( ) 28在线性规划的图解法中，基可行解一定可以在顶点得到。( )29运输问题不一定存在最优解。( )30匈牙利法是对指派问题求最小值的一种求解方法。( )31无孤立点的图一定是连通图。( ) 32可行流的流量等于发点流出的合流。( )33割集中弧的容量之和称为割量。( )二、填空题1如果某一整数规划问题，决策变量X1,X20且均为整数，所对应的线性规划（松弛问题）的最优解为X1=19/4，X2=22/5，Max Z=45，我们现在要对X1进行分枝，应该分为X1 4 和X1 5 。2线性规划的最优解是(0，6),它的第1、2个约束中松驰变量（S1,S2）= （0，2） 。3运输问题中m+n1个变量构成基变量的充要条件是 不包含任何闭回路 。4. 在求运费最少的调度运输问题中，如果某一非基变量的检验数为6，则说明 如果在该空格中增加一个运量运费将 增加6 （填如何变化及变化值）。5. 如果某一整数规划问题，决策变量X1,X20且均为整数，所对应的线性规划（松弛问题）的最优解为X1=11/4，X2=14/3，MaxZ=9/29，我们现在要对X1进行分枝，应该分为X12和 X13 。6. 有5个产地4个销地的平衡运输问题，有 8 个基变量。7. 如果决策者要求结果一定不能有正或负的偏差，这种约束称为 系统 约束。8. 运输规划中，寻找求初始基本可行解两种方法是 最小元素 、 元素差额法 与 左上角（或西北角）法。9. 原问题的第1个约束方程是“=”型，则对偶问题相应的变量是_ 无约束 _ 变量。10.如果某一整数规划问题，决策变量X1,X20且均为整数，所对应的线性规划（松弛问题）的最优解为X1=16/3，X2=11/2，MaxZ=19/7，我们现在要对X1进行分枝，应该分为X1 5 和X1 6 。11. 在求运费最少的调度运输问题中，如果某一非基变量的检验数为5，则说明如果在该空格中增加一个运量，运费将 增加5 （填写变化方向及化量）。12. 有5个产地5个销地的平衡运输问题，则它的基变量有 9 个。1.有7个产地8个销地的平衡运输问题，则它的基变量有 14 个。13.如果X是问题的可行解, Y是问题的可行解, 则 = (填写比较大小的符号) 。14. 在求运费最少的调度运输问题中，如果某一非基变量的检验数为5，则说明如果在该空格中增加一个运量，运费将 增加5 （填写变化方向及化量）。15. 如果某一整数规划问题，决策变量X1,X20且均为整数，所对应的线性规划（松弛问题）的最优解为X1=11/3，X2=17/2，MaxZ=19/29，我们现在要对X1进行分枝，应该分为X1 3 和X1 4 。16.和分别是问题和问题的最优解的充要条件是 CX=Yb 。17. 图G中，若任意两点之间都有路可到达，则称G是 连通图 。一个无圈的连通图称为树，在一个树中，边数和顶点数的关系为 边数=顶点数-1 。18如果某一整数规划问题，决策变量X1,X20且均为整数，所对应的线性规划（松弛问题）的最优解为X1=17/2，X2=19/3，MaxZ=16/29，我们现在要对X1进行分枝，应该分为X1 8 和X1 9 。19.如果X是问题的可行解, Y是问题的可行解, 则 = (填写比较大小的符号) 。20. x和w分别是问题和问题的最优解的充要条件是 CX=Yb 。3、 选择题1线性规划的约束条件为 ，则基本解为 ： ( B ) 。 A(0, 2, 2, 4) B(2, 2, 0, 0) C(0, 0, 12, 8) D(2, 0, 6, 8)2线性规划可行域的顶点一定是 ( A ) 。 A基本可行解 B非基本解 C非可行解 D最优解3线性规划具有多重最优解是指 (C ) 。 A最优表中存在常数项为零 B最优表中非基变量检验数全部非零 C最优表中存在非基变量的检验数为零 D可行解集合有界4在求解运输问题的过程中运用到下列哪些方法（ D ）。A 西北角法 B 位势法 C 闭回路法 D 以上都是5对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中 （ ）。 Ab列元素不小于零 B检验数都大于零 C检验数都不小于零 D检验数都不大于零 6线性规划问题的标准型最本质的特点是 （ C ）。 A目标要求是极小化 B变量可以取任意值 C变量和右端常数要求非负，约束条件一定是等式形式 D 以上均不对7关于运输问题，下列说法不正确的是 （ A ）。 A在其数学模型中，有m+n1个变量 B用元素差额法求得的初始解比用西北角法得到的初始解在一般情况下更靠近最优解 C对任何一个运输问题，一定存在最优解 D对于产销不平衡的运输问题。同样也可以用表上作业法求解8. 最早运用运筹学理论的是（ A ）。 A二次世界大战期间，英国军事部门将运筹学运用到军事战略部署 B美国最早将运筹学运用到农业和人口规划问题上 C 二次世界大战期间，英国政府将运筹学运用到政府制定计划 D50年代，运筹学运用到研究人口，能源，粮食，第三世界经济发展等问题上9线性规划的约束条件为 ，则基本解为 ：( B ) 。 A(0, 2, 4, 2) B(2, 2, 0, 0) C(0, 0, 12, 8) D(2, 0, 6, 8)10线性规划具有唯一最优解是指 ( A ) 。 A最优表中非基变量检验数全部非零 B最优表中存在常数项为零 C可行解集合有界 D最优表中存在非基变量的检验数为零11有m个产地n个销地的平衡运输问题模型具有特征 ( A ) 。 A有mn个变量，m+n个约束，m+n-1个基变量 B有m+n个变量，mn个约束 C有mn个变量，m+n1约束 D有m+n1个基变量，mnmn1个非基变量12在线性规划的图解法中，全部可行解所分布的区域称之为( B ) 。A阴影区 B可行解区C最优解区D基础可行解区13.线性规划具有无界解是指 （ C ）。A.可行解集合无界 B.有相同的最小比值 C.存在某个检验数 D.最优表中所有非基变量的检验数非零14.线性规划具有无界解是指 （ C ）A.可行解集合无界 B.有相同的最小比值 C.存在某个检验数 D.最优表中所有非基变量的检验数非零15. 下列线性规划与目标规划之间错误的关系是（ B ）A.线性规划的目标函数由决策变量构成，目标规划的目标函数由偏差变量构成 B.线性规划模型不包含目标约束，目标规划模型不包含系统约束 C.线性规划求最优解，目标规划求满意解 D.线性规划模型只有系统约束，目标规划模型可以有系统约束和目标约束16.互为对偶的两个线性规划问题的解存在关系 （ B ）A.原问题有可行解，对偶问题也有可行解 B.一个有最优解，另一个也有最优解C.一个无最优解，另一个可能有最优解 D.一个问题无可行解，则另一个问题具有无界解17.分枝定界法中，正确的是A、B、C、D的哪个？ （ D ）a.最大值问题的目标值是各分枝的下界 b.最大值问题的目标值是各分枝的上界c.最小值问题的目标值是各分枝的上界 d.最小值问题的目标值是各分枝的下界 e.以上结论都不对A. a,b B. e C. c,d D. b,d 18. 线性规划可行域的顶点一定是（ A ）A.可行解 B.非基本解 C.非可行 D.是最优解19.X是线性规划的可行解，则错误的结论是 （ D ）A.X可能是基本解B. X可能是基本可行解C.X满足所有约束条件 D. X是基本可行解20.互为对偶的两个线性规划问题的解存在关系 （ B ）A.原问题有可行解，对偶问题也有可行解 B.一个有最优解，另一个也有最优解C.一个无最优解，另一个可能有最优解 D.一个问题无可行解，则另一个问题具有无界解21. 求最大流的计算方法有（ D ）A. Dijkstra算法 B. Floyd算法 C. 加边法 D. Ford-Fulkerson算法22则 ( A ) A无可行解 B有唯一最优解 C有多重最优解 D有无界解23对于供求不平衡的运输问题，若需求量大于供应量，为了转化成供求平衡的运输问题，我们往往虚设一个( A )A供应点 B需求点C仓库 D运输渠道24在线性规划的图解法中，全部可行解所分布的区域称之为( B)A阴影区 B可行解区C最优解区D基础可行解区25下面哪些不是线性规划问题的标准形式所具备的（ C ）A 所有的变量必须是非负的 B 所有的约束条件（变量的非负约束除外）必须是等式C 添加新变量时，可以不考虑变量的正负性 D 目标函数求最大值26. 下列线性规划与目标规划之间错误的关系是（ B ）A.线性规划的目标函数由决策变量构成，目标规划的目标函数由偏差变量构成 B.线性规划模型不包含目标约束，目标规划模型不包含系统约束 C.线性规划求最优解，目标规划求满意解 D.线性规划模型只有系统约束，目标规划模型可以有系统约束和目标约束27在网络计划技术中，总时差等于0的活动，称之为( C)A关键线路B关键结点（事项）C关键工序D关键时差28.下列变量组是一个闭回路（ C ）A. x11,x12,x23,x34,x41,x13 B. x21,x13,x34,x41,x12C. x12,x32,x33,x23,x21,x11 D.x12,x22,x32,x33,x23,x2129网络图三点估计法中，正常条件下完成一项活动正常时间，称为( D )A作业时间B最乐观时间C最保守时间 D最可能时间30. 下列线性规划与目标规划之间错误的关系是（ B ）A.线性规划的目标函数由决策变量构成，目标规划的目标函数由偏差变量构成 B.线性规划模型不包含目标约束，目标规划模型不包含系统约束 C.线性规划求最优解，目标规划求满意解 D.线性规划模型只有系统约束，目标规划模型可以有系统约束和目标约束31.下列变量组是一个闭回路（ C ）A. x11,x12,x23,x34,x41,x13 B. x21,x13,x34,x41,x12C. x12,x32,x33,x23,x21,x11 D.x12,x22,x32,x33,x23,x2132.求含负权图最短路的计算方法有（ B ）A. Dijkstra算法 B. Floyd算法C. 加边法 D. Ford-Fulkerson算法4、 简答题1. 将线性规划问题化为标准形式。 标准形式: 。2. 已知下表是制订生产计划问题的一张LP最优单纯形表（极大化问题，约束条件均为“”型不等式）其中X3,X4,X5为松驰变量。（3）XBX1X2X3X4X5bX400-1/2133X110-7/201/32X20110-17Cj-Zj00-1-4-5问：（1）对偶问题的最优解：Y (1,4,5,0,0) 。(2)原问题的最优解：X (2,7,0,3,0) 。3. 将线性规划问题化为标准形式。 标准形式: 。4. 已知下表是制订生产计划问题的一张LP最优单纯形表（极大化问题，约束条件均为“”型不等式）其中X3,X4,X5为松驰变量。（3）XBX1X2X3X4X5bX400-1/2127/3X110-4/3012/51X20120-16Cj-Zj00-2-4-3问：（1）对偶问题的最优解：Y (2,4,3,0,0) 。(2)原问题的最优解：X (1,6,0,7/3,0) 。5. 已知下表是制订生产计划问题的一张LP最优单纯形表（极大化问题，约束条件均为“”型不等式）其中X3,X4,X5为松驰变量。（3）XBX1X2X3X4X5bX400-1132X110-1/301/35/3X20110-11Cj-Zj00-3-2-7问：（1）写出B-1=(2)对偶问题的最优解：Y(3)原问题的最优解：X（1）B-1= （2分）(2)对偶问题的最优解：Y（3，2，7，0，0）T （2分） (3)原问题的最优解：X（5/3，1，0，2，0）T （2分）6. 已知下表是制订生产计划问题的一张LP最优单纯形表（极大化问题，约束条件均为“”型不等式）其中X4,X5,X6为松驰变量。（4）XBX1X2X3X4X5X6bX11103011/2X30011042/3X50-201161Cj-Zj000-30-8问：（1）写出B-1= （2分） （2）对偶问题的最优解：Y （2分） (3)原问题的最优解：X （1分）（1）写出B-1= （2分）（2）对偶问题的最优解：Y (3,0,8,0,0,0) T （2分） (3)原问题的最优解：X （1/2，0，2 /3，0，1，0）T （1分）7. 将线性规划问题化为标准形式。8. 已知下表是制订生产计划问题的一张LP最优单纯形表（极大化问题，约束条件均为“”型不等式）其中X3,X4,X5为松驰变量。（3）XBX1X2X3X4X5bX400-1133X110-1/301/35/2X20110-12Cj-Zj00-4-2-5求：（1）对偶问题的最优解：Y(4,2,5,0,0)(2)原问题的最优解：X(5/2,2,0,3,0)9. 将线性规划问题化为标准形式。 10. 已知下表是制订生产计划问题的一张LP最优单纯形表（极大化问题，约束条件均为“”型不等式）其中X3,X4,X5为松驰变量。（3）XBX1X2X3X4X5bX400-1/2125X110-7/301/53X20110-17Cj-Zj00-2-3-7问：（1）对偶问题的最优解：Y(2,3,7,0,0)(2)原问题的最优解：X(3,7,0,5,0)11. 求线性规划问题的标准形式。 12. 已知下表是制订生产计划问题的一张LP最优单纯形表（极大化问题，约束条件均为“”型不等式）其中X3,X4,X5为松驰变量。（3）XBX1X2X3X4X5bX400-1133X110-1/301/35/2X20110-12Cj-Zj00-4-2-5问：(1)对偶问题的最优解：Y(5,2,4,0,0)(2)原问题的最优解：X(5/2,2,0,3)五、计算题1（本小题共15分）已知某工厂计划生产A1，A2，A3三种产品，各产品需要在甲、乙、丙设备上加工。有关数据如下表。产品设备A1 A2 A3工时限制/月甲乙2 3 11 2 2 1000 3000单位产品利润/千元3 4 1试问：如何合理安排生产，以充分发挥设备能力，使工厂获利最大？2、（本小题共16分）已知运输问题的调运和运价表如下，求最优调运方案和最小总费用。销地产地B1B2B3产量A185440A214181390A39210110销量80100602403（本小题共15分）已知某工厂计划生产A1，A2，A3三种产品，各产品需要在甲、乙、丙设备上加工。有关数据如下表。产品设备A1 A2 A3工时限制/月甲乙4 6 22 4 4 2000 6000单位产品利润/千元6 8 2试问：如何合理安排生产，以充分发挥设备能力，使工厂获利最大？4、（本小题共16分）已知运输问题的调运和运价表如下，求最优调运方案和最小总费用。销地产地B1B2B3产量A159215A231711A362820销量1812165已知某工厂计划生产A1，A2，A3三种产品，各产品需要在甲、乙、丙设备上加工。有关数据如下表。产品设备A1 A2 A3工时限制/月甲乙丙8 12 1010 5 6 2 8 10 320 400 420单位产品利润/千元3 2 4试问：如何合理安排生产，以充分发挥设备能力，使工厂获利最大？（本小题共15分）本题要求：（1） 建立线性规划数学模型（3分）（2） 将模型化为标准型（3分）（3） 用单纯形表求解（7分）（4） 求出工厂的最大利润值（2分）生产A1产品38单位，可使工厂获利最大为：4千元32=128千元6某公司下属的3个分厂A1、A2、A3生产质量相同的工艺品，要运输到B1、B2、B3、B4 ，4个销售点，分厂产量、销售点销量、单位物品的运费数据如下：B1B2B3B4产量ai21519221834A32724101529销量bj23163526求最优调运方案和最小总费用。（本小题共10分）本题要求：（1）用最小元素法确定初始解（3分）（2）计算初始解的检验数（4分）（3）看是否需要调整运量，直至达到最优，并求出最优调运方案和最小总费用。（3分）（只要得出一种最优调运方案即可）最小总费用为： f* = 11*16+23*6+19*15+15*23+18*11+10*29=1432 11=30-19+18-15=1422=19-18+19-11=923=22-18+19-23=031=27-10+23-19+18-15=2432=24-10+23-11=26最小总费用为： f* = 11*16+23*6+19*15+15*23+18*11+10*29=1432 （3）由于所有的检验数都大于等于0，所以得到最优解最优调运方案为： x12 = 16, x13 = 6, x14 = 15, x21 = 23, x24 = 11, x33 = 29, 其它xij = 0 （1.5分） 最小总费用为： f* = 11*16+23*6+19*15+15*23+18*11+10*29=1432 7根据下面工程明细表（本小题共15分）（1）计算各工序时间期望值（取2位小数）。（6分）（2）绘制PERT网络图。（9分）作业代号紧前工序作业时间ambABCDEFGHIJKL_ACCA,BA,BE,FD,HID,H,GG561021210810712152169135161210128172025812158181512139202228解：（1）计算各工序时间期望值。A工序时间期望值： （0.5分）B工序时间期望值： （0.5分）C工序时间期望值： （0.5分）D工序时间期望值： （0.5分）E工序时间期望值： （0.5分）F工序时间期望值： （0.5分）G工序时间期望值： （0.5分）H工序时间期望值： （0.5分）I工序时间期望值： （0.5分）J工序时间期望值： （0.5分）K工序时间期望值： （0.5分）L工序时间期望值： （0.5分）（2） PERT网络图，各事项的时间参数及各作业总时差和单时差为下图所示8（本小题共15分）已知某工厂计划生产A1，A2，A3三种产品，各产品需要在甲、乙、丙设备上加工。有关数据如下表。产品设备A1 A2 A3工时限制/月甲乙丙8 12 1010 5 6 2 8 10 320 400 420单位产品利润/千元3 2 4试问：如何合理安排生产，以充分发挥设备能力，使工厂获利最大？本题要求：（5） 建立线性规划数学模型（3分）（6） 将模型化为标准型（3分）（7） 用单纯形表求解（7分）（8） 求出工厂的最大利润值（2分）10（本小题共10分）已知运输问题的调运和运价表如下： 。销地产地B1B2B3产量A159215A231711A362820销量181216本题要求：（1）用最小元素法确定初始解（2分）（2）计算初始解的检验数（4分）（3）调整运量得到新的基可行解，求检验数，直至达到最优，并求最优调运方案和最小总费用。（4分）1）初始解为 （2分）B1B2B3产量/tA11515A21111A3181120销量/t181216（2）计算检验数 （4分）B1B2B3产量/tA1513015A220011A300020销量/t181216（3）由于存在非基变量的检验数小于0，所以不是最优解，需调整调整为： （4分）B1B2B3产量/tA11515A21111A3712120销量/t181216重新计算检验数： B1B2B3产量/tA1513015A202211A300020销量/t181216所有的检验数都大于等于0，所以得到最优解最优调运方案为：x13 = 15, x21 = 11, x31 = 7, x32 = 12, x33 = 1,其它xij = 0最小总费用为：f* = 2*15+3*11+6*7+2*12+8*1=13711已知某工厂计划生产A1，A2，A3三种产品，各产品需要在甲、乙、丙设备上加工。有关数据如下表。产品设备A1 A2 A3工时限制/月甲乙丙3 4 52 4 3 2 8 4 300 450 500单位产品利润/千元2 5 5试问：如何合理安排生产，以充分发挥设备能力，使工厂获利最大？假设允许产品件数为非整数，如计算过程中出现非整数，要求用分数表达，本题要求：（9） 建立线性规划数学模型（2分）（10） 将模型化为标准型（2分）（11） 用单纯形表求解，并给出最优解（8分）（12） 求出工厂的最大利润值（3分）(1) （2分）(2) （2 分）(3)CBxB2 5 5 0 0 0bx1 x2 x3 x4 x5 x6000x4x5x63 4 5 1 0 02 4 3 0 1 02 8 4 0 0 130045050075225/2125/22 5 5 0 0 0005X4x5x22 0 3 1 0 -1/21 0 1 0 1 -1/21/4 1 1/2 0 0 1/850200125/216.6672001253/4 0 2.5 0 0 -5/8505X3x5x22/3 0 1 1/3 0 -1/61/3 0 0 -1/3 1 -1/3-1/12 1 0 -1/6 0 5/2450/3或16.67550/3或183.3325/6或54.17-11/12 0 0 -1/12 0 -5/24最优解为：X=（0，325/6, 50/3）T（8分）(4)所以，生产A1产品0单位，生产A2产品325/6单位，生产A3产品50/3单位，可使工厂获利最大为：2千元0+5325/6+5*50/3=2125/6=354.1667千元。 （3分）12、已知运输问题的调运和运价表如下，求最优调运方案和最小总费用。（共16分）。销地产地B1B2B3产量A159215A231711A362820销量181216解：初始解为(3分)B1B2B3产量/tA11515A21111A3181120销量/t181216计算检验数(5分)B1B2B3产量/tA1513015A220011A300020销量/t181216由于存在非基变量的检验数小于0，所以不是最优解，需调整调整为：(2分)B1B2B3产量/tA11515A21111A3712120销量/t181216重新计算检验数(3分)B1B2B3产量/tA1513015A202211A300020销量/t181216所有的检验数都大于等于0，所以得到最优解最优调运方案为：x13 = 15, x21 = 11, x31 = 7, x32 = 12, x33 =