运筹学2020最新试卷带答案

1、运筹学样卷参考答案（48课时）一、判断题（对的记，错的记X,共10分，每小题2分）1.线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大；（）*2 .已知y为线性规划的对偶问题的最优解，若yi0说明在最优生产计划中第i种资源已完全耗尽；（）3 .运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有惟一最优解、有无穷多最优解、无界解和无可行解；（）4 .求解整数规划是可以先不考虑变量的整数约束，而是先求解相应的线性规划问题，然后对求解结果中的非整数的变量凑整即得最优解。（）5 .11个公司之间可能只有4个公司与偶数个公司有业务

2、联系；（）答案：1.T;2.T;3.F;4.F;5.F二、选择题（共15分，每小题3分）1 .在利用图解法求解最大利润问题中中，通过各极点作与目标函数直线斜率相同的平行线，这些平行线称之为。（）A.可行解B.可行域C.等利润线D.等成本线2 .用单纯形法求解线性规划问题时引入的松弛变量在目标函数中的系数为。（）A.0B.很大的正数C.很大的负数D.13 .以下关系中，不是线性规划与其对偶问题的对应关系的是。（）A.约束条件组的系数矩阵互为转置矩阵B.一个约束条件组的常数列为另一个目标函数的系数行向量C.两个约束条件组中的方程个数相等D.约束条件组的不等式反向4 .需求量大于供应量的运输问题需要

3、做的是。（）A.虚设一个需求点B.删去一个供应点C.虚设一个供应点，取虚设供应量为恰当值D.令供应点到虚设的需求点的单位运费为05 .对一个求目标函数最大的混合整数规划问题，以下命题中不正确的是。（）A.其线性规划松弛问题的最优解可能是该整数规划问题的最优解。B.该问题可行解的个数一定是有限的；C.任一可行解的目标函数值不可能大于其线性规划松弛问题的目标函数值；D.该问题可行解中可能存在不取整数值的变量。答案：6.C7.A8.C9.C10.B三、简答题（每题5分，共15分）1 .线性规划问题的三个要素是什么？线性规划模型有哪些特征？答案：线性规划问题的三个要素是决策变量、目标函数和约束条件。线

4、性规划模型的特征有：（1）目标函数是决策变量的线性函数；（2）约束条件是决策变量的线性（不）等式；（3）决策变量连续变化。2 .利用0-1变量表示下列约束条件（要求说明0-1变量的意义）x取值0,2,4,6,8中的一个答案：设yj=1为取第j个数，否则，yj=0.则x0yi2y24y36y48y5yiy2y3y,y5iyj0or1,j1,2,|,53 .写出求极大值的运输问题的产销平衡表B1B2B3B4A17891030A21716151420A3534615销量15101520答案：令新表中单位运价为Cij17Cij,总产量=65>60=总销量，增加一个虚拟的销地，销量为5.B1B2B

5、3B4B5A110987030A20123020A312141311015销量151015205（10分=5分+5分）某产品有三个产地、四个销地，各产地的产量、各销地的销量以及产地到销地之间的单位运价见下表，用表上作业法求该运输问题的最优调运方案。肖地产地、BiB2B3B4产量A141241116A22103910A38511622销量8141214答案：为了简便，表中口中的数为运行方案，（）中的数为检验数。最小元素法：，理地产地、BiB2B3B4产量Ai4(1)12(2)41011616A228一10(1)32_一9(-1)10A38(10)51411(12)6822销量814121448检

6、验数2410,当前方案不是最优，调整如下:Ai4(0)12(2)41211416A22810(2)39210A38(9)51411(12)6822销量814121448所有检验数非负，当前方案为最优方案.有非基变量检验数为0,有无穷多最优解。(4)用图解法求下列目标规划的满意解：minzP1dl+P2(d2d2)P3d32x1x211(a)x1x2d1d10(b)x12x2d2d210(c)8x110x2d3d356(d)x1，x2，di,di0(i1,2,3)图略，满意解是线段GD上任意点，其中G点(2,4),D点(10/3,10/3),因为GD上任意点对应的d30(5)设图中各弧上数为距离

7、，求该网络(看作无向图)的最小生成树。13.解：(1)破圈法或加边法，过程略如上图，为该网络(看作无向图)的最小生成树，总的权重为18二、解答题(共50分)1. (10分)某企业生产甲、乙两种产品，从工艺资料知道：每生产一吨产品甲需用资源A3个单位，资源B5个单位，每生产一吨产品乙需用资源A4个单位，资源B2个单位。若一吨产品的甲和乙的经济价值分别为10千元和6千元，每天原料供应的能力分别为10,12单位，企业应该如何安排生产计划，使得一天的总利润最大？解：设每天生产甲、乙各x1,x2吨，则maxz10x16x23x14x210s.t5x12x212x1,x20图解法求解：略最优解为：X=(2

8、,1),最优目标值为z=26.答：每天生产甲、乙各2吨和1吨，使得一天的总利润最大2.下面三题选一：(1)已知线性规划问题(P)maxz2x13x23x3x1x2x33s.tx14x27x39xj0,j1,2,3的一个单纯形表如下。Cj23300CBXbbX1X2X3X4X52X1110-14/3-1/33X22012-1/31/3j00-1-5/3-1/3(a)写出(P)此时的基本可行解，并判断该解是否为最优解;(b)写出(P)的对偶模型及其最优解。答案：(1)基变量为X1,X2,故当前基本可行解为(1,2,0,0,0),因为所有检验数非正，故为最优解。(2) (P)的对偶模型为minw3y

9、l9y2V iV22V i4y23%7y23V 1,V205/3,1/3)其最优解为原问题最优单纯表中检验数的相反数，即(maxz2x14x2x3x4(2)已知线性规划问题:x13x22x1x2x2xix2xj0(jx3x3x48669的最优解为X*=(2,2,4,0),根据对偶理论求出对偶问题最优解。minw8yl6y26y39y4解：对偶模型为Vi2y2y423y1y2y3y43y3y41yiy41y1,y2,y3,y40设对偶问题最优解为Y*(y1,y2,V3,V4)。因为原问题最优解为%2y2y423y1y2y3y43V3V41又因为xs4922410,故y40,从而y31,y1问题的

10、最优解为(2/5,4/5,1,0)3.下面三题选一：(1)用分枝定界法求解整数规划问题:解：该问题的松弛问题(L)为用图解法(略)得松弛问题(L)的最优解为X(L)分别增加条件x2和x23,1，l|h4)X*=(2,2,4,0),故2/5,y24/5,所以对偶maxz3x12x22x,3x214x10.5x24.5x1,x20且x2为整数maxz3x12x22为3x214x10.5x24.5x1,x20(3.25,2.5),最优目标值为14.75.得两个子问题(L1)和(L2),用图解法(略)得子问题(L1)的最优解为(3.5,2),最优目标值为14.5,子问题(L2)的最优解为(2.5,3)

11、,最优目标值为13.5.因为解(3.5,2)满足X2为整数条件，并且目标函数值是两个子问题中最大，故原问题的最优解为(3.5,2).(2)从甲，乙，丙，丁，戊五人中挑选四人去完成四项工作，已知每人完成各项工作的时间如下表所示。规定每项工作只能由一个人去单独完成，每个人最多承担一项工作，假定甲必须1051520M、831012M:5079M-3、210515008070-0T1_0T0-3151413011395011139501527M01302M-801302M-8094158072100071!10-0-M18.解:8M-3、0913608110此时，费用最小，其中，丙做第一事,4(M-9

12、0Z3)15甲做第二事,21乙做第三事,戌做第四事保证分配到工作，丁因某种原因不同意承担第四项工作。在满足上述条件下，如何分配工作,使完成四项工作总的花费时间最少。(20分)人工作一一三四甲1051520乙210515丙3151413丁15276戊94158(3)求解0-1规划问题:maxz3x12x25x3x12x2x3x14x2x3s.tx1x24x2x36x1,x2,x30或1解：易看出(xi,x2,x3)(0,0,0)满足约束条件，故为一个可行解，且相应的目标函数值为0。因为是求极大值问题，应增加一个约束条件(目标值下界)：3xi2x25x30,求解过程可由下表来表示:(Xi,X2,X

13、3)z值过滤条件约束条件修正过滤条件abcdea(0,0,0)0一VVVVz0(0,0,1)5VVVVVz5(0,1,0)-2x(0,1,1)3x(1,0,0)3x(1,0,1)8VV7V7V7V7V7z8(1,1,0)1x(1,1,1)6X从而得最优解x(1,0,1)T,最优值z8。Vi到V9的最短距离与最短路径。(2)设图中各弧上数为容量，求必到丫9的最大流量。4.(10分)(二选一)(1)设图中各弧上数为距离，求(1)标号过程：略；最短路为：V1一V2V6一V9,最短距离为8.5(2)标号过程：略；最大流量为6,最小割集为：(S,T)=(V1,V2),(V4,V7),其中S=v1,V4,

14、T=v2,V3,V5,V6,V7,V8,V9割量为：C(S,T)=3+3=6.最大流量方案(答案不唯一"):f3=3,f14=3,f23=3,f39=3,f47=3,f78=1,f79=2,f89=1,其余为零。卜面二题选一：卜表为一机械加工工序，试画出PER刖络图，并计算时间参数和确定关键路线。作业代码作业名称紧前作业作业时间(天)A项目设计一4B外购包装材料A8C清理场地A7D外购零配件A6E机加工2人员培训1A9F木模、铸件C15G机加工1D12H机加工2JD、E8I工装制造G10J装配、调试B、F、H、I4关键工序：A,C,F,J关键路线：12378工程完工期限：38某农场要

15、决定一块地中选择什么作物，条件如下，如何决策?一_利信、旱正常多雨0.20.70.1歌菜100040007000小麦F20001r500030001棉花30006。2000(1)分别用乐观法、悲观法、等可能法与最小后悔值法对生产方案作出决策。(2)根据往年天气资料，旱、正常和多雨三种天气的概率分别为0.2、0.7和0.1,求利润期望最大和后悔期望最小的策略。答：利润表如下表所示。旱正常多雨Maxmin等可能法利润期望值0.20.70.1蔬菜1000400070007000100040003700小麦2000500030005000200033334200棉花300060002000600020

16、0036676800乐观法（大中取大）：最佳方案为：蔬菜悲观法（小中取大）：最佳方案为：小麦或棉花等可能法：最佳方案为：蔬菜最大利润期望值法：最佳方案为：棉花后悔值如下表所示。旱正常多雨Max损失期望值0.20.70.1蔬菜20002000020001800小麦10001000400040001300棉花0050005000500最小后悔值法：最佳方案为：蔬菜最小损失期望值法：最佳方案为：棉花四、建立下面问题的数学模型（9分）1,某造船厂根据合同从当年起连续三年末各提供四条规格相同的大型客货轮。已知该厂这答案：设第i年正常生产Xi艘，加班生产yi艘，交付后储贮zi艘X广销存平衡：ZoVZiZi4,i1,2.32,Z31加工能力限制:0x3,0yi30X25,0V220X32,0V33目标函数:w500x1600x2500x3560yl660y2560y330(z0z1z2)已知一个工厂生产A、B两类产品，每件产品生产需消耗三种资源，现已知单位产品获利、单位产品消耗资源和当前资源限制如下表：三年内生产大型客货轮的能力及每艘客货轮成本如下表所示:年度正常生产时间内可完成的客货轮数加班生广时间内引元成的客货轮数正常生产时每艘成本（万元）133500252600323500已知加班生产时，每艘客货轮成本比较正常时高出60万元；又知造出来的客货轮若当年不交货，每