运筹学期末复习题

1、运筹学期末复习题一、判断题：1、任何线性规划一定有最优解。（）2、若线性规划有最优解，则一定有基本最优解。（）3、线性规划可行域无界，则具有无界解。（）4、基本解对应的基是可行基。（）5、在基本可行解中非基变量一定为零。（）6、变量取 0或 1的规划是整数规划。（）7、运输问题中应用位势法求得的检验数不唯一。（）8、产地数为 3，销地数为 4 的平衡运输中，变量组 X11，X13，X22，X33，X34可作 为一组基变量。（）9、不平衡运输问题不一定有最优解。（）10、m+n-1 个变量构成基变量组的充要条件是它们不包含闭回路。（）11、含有孤立点的变量组不包含有闭回路。（）12、不包含任何闭

2、回路的变量组必有孤立点。（）13、产地个数为 m 销地个数为 n 的平衡运输问题的系数距阵为 A，则有 r（A） m+n-1 （）14、用一个常数 k加到运价矩阵C的某列的所有元素上,则最优解不变。 （）15、匈牙利法是求解最小值分配问题的一种方法。（）16、连通图 G的部分树是取图 G的点和 G的所有边组成的树。（）17、求最小树可用破圈法。（）18、Dijkstra 算法要求边的长度非负。（）19、Floyd 算法要求边的长度非负。（）20、在最短路问题中，发点到收点的最短路长是唯一的。（）21、连通图一定有支撑树。（）22、网络计划中的总工期等于各工序时间之和。（）23、网络计划中，总时

3、差为 0 的工序称为关键工序。（）24、在网络图中，关键路线一定存在。（）25、紧前工序是前道工序。26、后续工序是紧后工序。27、虚工序是虚设的 ,不需要时间 ,费用和资源 ,并不表示任何关系的工序28、动态规划是求解多阶段决策问题的一种思路，同时是一种算法。29、30、求最短路径的结果是唯一的。在不确定型决策中，最小机会损失准则比等可能性则保守性更强。31、决策树比决策矩阵更适于描述序列决策过程。32、额相等，在股票市场中，有的股东赚钱，有的股东赔钱，则赚钱的总金额与赔钱的总金 因此称这一现象为零和现象。33、34、若矩阵对策 A 的某一行元素均大于 0，则对应值大于 0。(矩阵对策中，如

4、果最优解要求一个局中人采取纯策略，则另一局中人也必须采取纯策略。35、多阶段决策问题的最优解是唯一的。36、网络图中相邻的两个结点之间可以有两条弧。37、网络图中可以有缺口和回路、选择题1、线性规划的约束条件为： x1+x2+x3=3 2x1+2x2+x4=4 x1, x2, x3, x4 0 则可行解为：A、(3，0，4，0)B、(1，1，1，0)C、(3，4，0，0)D、(3，0，0，-2)2、有 3 个产地 4 个销地的平衡运输问题模型具有特征：A、有 7 个变量B、有 12 个约束C、有 6 个约束D、有 6 个基变量3、当线性规划的可行解集合非空时一定：A 、包含原点 X=(0,0,

5、 0)B、有界C 、无界D、是凸集4、线性规划的条件为： x1+x2+x3=3 2x1+2x2+x4=4 x1, x2, x3, x4 0则基本可行解是：A 、(0,0,4,3) B、(0,0,3,4) C、(2,0,1,0) D、(3,4,0,0) E、 (3,0,0,-2)5、线性规划具有无界解是指A 、可行解集合无界B、有相同的最小比值C、存在某个检验数 k0 且ik0(i=1,2,m)D、最优表中所有非基变理的检验数非零6、线性规划可行域的顶点是：A 、可行解B、非基本解 C、基本可行解D、最优解E、基本解7、minZ=x1-2x2-x1+2x2 5, 2x1+x2 8, x1, x2

6、0，则A 、有惟一最优解B、有多重最优解C、有无界解D、无可行解E、存在最优解8、下列变量组是一个闭回路的有：A 、x 21, x11, x12, x32, x33, x23B、x 11, x12, x23, x34, x41, x13C、x 21, x13, x34, x41, x12D、x 12, x32, x33, x23, x21, x11E、x 12, x22, x32, x33, x23, x219、具有 m个产地 n个销地的平衡运输问题模型具有特征：A 、有 mn 个变量 m+n 个约束B、有 m+n 个变量 mn 个约束C、有 mn 个变量 m+n-1 个约束 D 、有 m+n

7、-1 个基变量 mn-m-n+1 个非基变量E、系数矩阵的秩等于 m+n-110、下列结论正确的有：A 、任意一个运输问题不一定存在最优解B、任何运输问题都存在可行解C、产量和销量均为整数的运输问题必存在整数最优解D 、m+n-1 个变量组构成基变量的充要条件是它不包括任何闭回路E 运输单纯形法(表上作业法)的条件是产量等于销量的平衡问题11、下列说法错误的是：A 、若变量组 B 包含有闭回路，则 B 中的变量对应的列向量线性无关B、平衡运输问题的对偶问题的变量非负C、运输问题的对偶问题的约束条件为大于等于约束D、运输问题的对偶问题的约束条件为大于等于约束E、第 i 行的位势 ui 是第 i

8、个对偶变量12、有 6 个产地 7 个销地的平衡运输问题模型的对偶模型具有特征A、有 42 个变量B、有 42 个约束C、有 13 个约束D、是线性规划模型E、有 13 个变量13、运输问题的数学模型属于A、线性规划模型B、整数规划模型C、0-1 整数规划模型D、网络模型14、匈牙利法的条件是：E、不属于以上任何一种模型A、问题求最小值B、效率矩阵的元素非负C、人数与工作数相等D、问题求最大值15、下列说法正确的是E、效率矩阵的元素非正A、将指派（分配）问题的效率矩阵每行分别乘以一个非零数后最优解不变B、将指派问题的效率矩阵每行分别加上一个数后最优解不变C、将指派问题的效率矩阵每个元素同时乘以

9、一个非零数后最优解不变D、指派问题的数学模型是整数规划模型E、指派问题的数学模型属于网络模型16、连通 G 有 n 个点，其部分树是 T，则有：A、T 有 n个 n条边B、T 的长度等于 G 的每条边的长度之和C、T 有 n个点 n-1条边D、T 有 n-1 个点 n 条边17、求最短路的计算方法有：A、Dijkstra 算法B、Floyd 算法C、加边法D、破圈法E、Ford-Fulkerson算法18、下列错误的结论是：A、给定某一阶段的状态，则在这一阶段以后过程的发展不受这一阶段以前各个 阶段状态的影响，而只与当前状态有关，与过程过去的历史无关B、动态规划是求解多阶段决策问题的一种算法策

10、略，当然也是一种算法C、动态规划是一种将问题分解为更小的、相似的子问题，并存储子问题的解而 避免计算重复的子问题，以解决最优化问题的算法策略D、动态规划数学模型由阶段、状态、决策与策略、状态转移议程及指标函数个要素组成19、下列正确的结论是：A、顺推法与逆推法计算的最优解可能不一样B、顺推法与逆推法计算的最优解相同C、各阶段所有决策组成的集合称为决策集D、各阶段所有决策组成的集合称为允许决策集合E、状态 SK 的决策就是下一阶段的状态20、对于不确定型的决策，由决策者的主观态度不同基本可分为以下几种准则A 、乐观主义准则B、悲观主义准则C、最大期望收益准则D、等可能性准则E、最小机会损失准则2

11、1、对于不确定型的决策，某人采用乐观主义准则进行决策，则应在收益表中A 、大中取大B、大中取小C、小中取大D、小中取小22、对于矩阵对策 G=S1, S2, A来说，局中人 I有把握的至少得益为 V1，局中人 II有把握的至多损失为 V2，则有A 、V1V2B、V1V2三、求解下列各题：1、用图解法求解下列线性规划问题， 界解还是无可行解。（1）minZ=x1+1.5x2 x1+3x23 x1x22 x1，x20（ 3）MaxZ=x 1+3x2 5x1+10x250 x1+x21 x24 x1，x20C、V1=V2D、V1V2E、C 或D并指出问题是具有唯一最优解，无穷多解，无（ 2） Max

12、Z=x 1+x2x1x220.5x11.5x1+2x210x1，x20（4）minZ=100x1+800x2x110.8x1+x21.6x22x1 ，x 2 05)minX=x 1+2x2x1x22x13x26x1，x202、如下图所示，（1）求 A 到 F 的最短路线及最短距离46D1410E133DA1F927E1D53872C1B135C2B276C3B363C42）求 A 到 E 的最短路线及最短距离6B1C123D135475C24E144D45B2 3B3C33、某公司有资金 400 万元，向 A、B、C 三个项目追加投资，三个项目可以有不同的投资额度，相应的效益如下表所示，问如何

13、分配资金，才可使效益值最大。投资额 效益值 项目01234A15132530B36152532C0243042424、某公司将某种设备 4 台，分配给所属的甲、乙、丙三个工厂，各工厂获得此设备后，预测可创造的利润如下表所示，问如何安排，所获得利润最大设备台数盈利工厂甲厂乙厂丙厂0000123421075312111341312135、有 5 个零件，先在车床上削，再在磨床上加工，时间如下表，问如何按排加工顺序，使 5 个零件的总工加工时间为最少。 （注：不计算时间长度）零件车床磨床11.50.2521.02.532.00.540.751.2551.251.756、请根据项目工序明细表（下表）（

14、1）画出网络图（2）计算各项时间参数（3）确定关键路线1）工序abcdefg紧前工序a,ba,bbcd,e时间24543242）工序abcdefg紧前工序aab, ced,ed,e时间9612196783)工序abcdefghijklmnopq紧前期序aaaaab,ce,ffd,ghj,kj,ki,lhmo,p工序时间601420302110712601025105152758、在一台机床上要加工 10 个零件，下面列出它们的加工时间，请确定加工顺序，以便各零件在车间里停留的平均时间最短零件12345678910时间1171583127.51.5161）求 min5 83 610 129 24

15、 714 5805040参)9、求解下列运输问题30 60 40 402）求 min31733）求 max29681131079284410596565891071054121494）求 min211023172315302120251922300400500200 200 250 55010、求解下列指派问题（ min ）1）126915C=201218263518102561015202）5869180260C=755015023065701702508255200280（3）85907390C=82877891838279888690808511、求解下列指派问题（max)109617C

16、=1514102018131319168122612、如图，求任意两个城市间的最短路13、在下两图中，求 V1 到 V6 的最短路线及最短路长14、用破圈法求下图的最小树6V23677558815、求解矩阵对策G=S1，S2，A ，其中：1)-7-8A=16-1-3-32)-61-83249-1-10-30616、已知面对四种自然状态的三种备选行动方案的公司收益如下表所示自然状态方案N1N2N3N4S11580-6S241483S3141012假定不知道各种自然状态出现的概率请分别用以下五种方法最优行动方案：A 、最大最小准则。B、最大最大准则。C、等可能性准则。D、乐观系数准则。（取=0.6

17、）E、后悔值准则。17、根据以往的资料，一家面包店所需要的面包数（即面包当天的需求量）可能为 下面各个数量中的一个：120 ， 180， 240， 300， 360 但不知其分布概率。如果一个面包当天没销售掉，则在当天结束时以0.10 元处理给饲养场，新面包的售价为每个 1.20 元，每个面包的成本为 0.50元，假设进货量限定为需 求量中的某一个，求：A、作出面包进货问题的收益矩阵 B、分别用最大最小准则、最大最大准则，后悔值法以及乐观系数法（=0.7），进行决策。18、设有参加对策的局中人 A 和 B，A 的损益矩阵如下，求最优纯策略和对策值。1231-500-100700210002003500-200-70019、A 、 B 两家公司各控制市场的 50%，最近两家公司都改进了各自的产品，准备 发动新的广告宣传。如果这两家公司都不做广告，那么平分市场的局面将保持不变，但 如果一家公司发动强大广告宣传，那么另一家公司将按比例失去其一定数量的顾客，市场调查表明，潜在顾客的 50%，可以通过电视广告争取到， 30%通过报纸，其余的 20% 可通过无线电广播争取到。现每一家公司的目标是选择最有利的广告手段。a、把这个问题表达成一个矩阵的对策，求出局中人A 的损益矩阵。b、这个决策有鞍点吗？ A、B 两公司的