管理运筹学模拟试题及答案

1、四 川 大 学 网 络 教 育 学 院 模 拟 试 题（ A ）管理运筹学单选题（每题分，共 20 分。）1 目标函数取极小（ minZ）的线性规划问题可以转化为目标函数取极大的线性规 划问题求解，原问题的目标函数值等于（ C ）。A. maxZB. max（-Z）C. max（-Z）2. 下列说法中正确的是（ B ）。基本解一定是可行解 基本可行解的每个分量一定非负 若 B是基，则 B 一定是可逆非基变量的系数列向量一定是线性相关 的3在线性规划模型中，没有非负约束的变量称为（ D ）多余变量B松弛变量C人工变量D自由变量4. 当满足最优解，且检验数为零的变量的个数大于基变量的个数时，可求得

2、 （ A ）。多重解 无解 正则解退化解5对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验 但不完全满足 （ D ）。A等式约束B“”型约束C“”约束D非负约束6. 原问题的第个约束方程是“”型，则对偶问题的变量yi 是（ B ）。多余变量 自由变量 松弛变量 非负变量7. 在运输方案中出现退化现象，是指数字格的数目（ C）。D.等于 m+n-1回路D无法确定A.等于 m+nB.大于 m+n-1C.小于 m+n-18. 树的任意两个顶点间恰好有一条（ B ）。边 初等链 欧拉圈9若 G中不存在流 f增流链，则 f为 G的 （ B ）。A最小流B最大流C最小费用流10.对偶单

3、纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验“”型约束非负约束但不完全满足（ D ）等式约束 “”型约束、多项选择题（每小题 4 分，共 20分）1化一般规划模型为标准型时，可能引入的变量有（ ）A松弛变量B剩余变量C非负变量D非正变量E自由变量2图解法求解线性规划问题的主要过程有（ ）A画出可行域D选基本解B求出顶点坐标C求最优目标值E选最优解C确定换出变3表上作业法中确定换出变量的过程有（ ）A判断检验数是否都非负B选最大检验数量D选最小检验数E确定换入变量4求解约束条件为“”型的线性规划、构造基本矩阵时，可用的变量有（ ）A人工变量B松弛变量C. 负变量D剩余变量E稳态

4、变量 5线性规划问题的主要特征有（ ）A目标是线性的B约束是线性的C求目标最大值D求目标最小值E非线性三、 计算题（共 60 分）1. 下列线性规划问题化为标准型。 (10 分 )min Zx1+5x2 -2x32.x12x1满足 1x1x1写出下列问题的对偶问题x2 x3 6x23x3x2 100,x2 0, x3符号不限（10 分 ）min Z 4x1 2x2 +3x34x1+5x2 6x3=7满足8x1 9x2 10x3 1112x1 13x2 14x1 0, x2无约束， x3 03. 用最小元素法求下列运输问题的一个初始基本可行解(10 分 )4某公司有资金 10 万元，若投资用于项

5、目9x2,i(i 1,2,3)的投资额为 xi时，其收益分别为 g1(x1) 4x1,g(x2)g(x3) 2x3,问应如何分配投资数额才能使总收益最大(15 分)5 求图中所示网络中的最短路。 (15 分)四川大 学 网 络 教 育 学 院 模 拟 试 题( A )管理运筹学参考答案一、单选题4. A 5. D 6. B 7. C 9. B二、多选题1. ABE 2. ABE 3. ACD 4. AD 5. AB三、计算题1、max(-z)=x15x2 2(x3 x3)2、写出对偶问题maxW=7 y1 11y2 14y34解：状态变量 sk为第 k阶段初拥有的可以分配给第 k到底 3个项目

6、的资金额； 决策变量 xk为决定给第 k 个项目的资金额；状态转移方程为 sk 1 sk xk ；最优 指标函数 fk (sk)表示第 k阶段初始状态为 sk时，从第k到第 3个项目所获得的最大收益， fk(sk) 即为所求的总收益。递推方程为：fk(sk) max gk (xk) fk (sk 1) (k 1,2,3)0 xk skf4(s4) 0当 k=3 时有f3(s3) max 2x30 x3 s32当 x3 s3时，取得极大值 2s3 ，即：f3(s3) max 2x3 2x30 x3 s3当 k=2 时有：max 9x22s320 x2 s2max 9x22(s2x2)0 x2 s

7、2h2 (s2, x2 )9x22(s2 x2 )f3(s3)2令 用经典解析方法求其极值点。2f2(s2 ) max 9x2 0 x2 s2由dh2 9dx22(s2 x2)(x2 s29解得：4而d2h2d x224 f 0x2 所以 29s24 是极小值点。极大值点可能在 0，s2 端点取得：1) 02f2(0) 2s22， f2(s2 )9s2当 f2(0) f2(s2) 时，解得 s2当 s2 f 9 / 29/2时，f2(0) f f2(s2) ，f2(0) p f2(s2) ，此时，x2当 k=1 时，当 f2 (s2)f1(s1) max 4x1f2 (s2)0 x1 s19s

8、2时，f1(s1)max 4x1 9s1 9x1m0 xa1 sx1 9s1 5x19s1但此时s2 s1 x110 0 10 f 9/ 2，与s2 p 9/ 2矛盾，所以舍去。当 f2 (s2)2s22 时， f1(10)m0 xa1 1x0 4x1 2(s1x1)2令h1( s1 , x1) 4 x1 2(s1 x1) 2由dh1 4dx14(s2x2)( 1) 0解得：x2 s11而d2h2d x221 f 0所以 x1s1 1 是极小值点。比较0,10两个端点x10 时， f1(10) 200s2f1 (10) 40x110 时，当 s2 p 9 / 2 时，此时， x2x1 0所以再

9、由状态转移方程顺推：最优投资方案为全部资金用于第200 万元。s2 s1 x110 0因为s2 f 9/2所以*x20 ， s3 s2*x*2 10因此*x3s3 10100 103 个项目，可获得最大收益5. 解：用 Dijkstra 算法的步骤如下，P（ v1） 0T（vj）（j 2， 37）第一步：因为 v1,v2 ，v1,v3 A且v2，v3是T标号，则修改上个点的 T 标号分别为T v2minTv2 ,P v1 w12=min,0 5 5T v3minTv3 ,P v1 w13min,0 2 2所有 T标号中， T（ v3 ）最小，令 P（v3） 2 第二步： v3 是刚得到的 P标

10、号，考察 v3v3,v4 ， v3,v6 A，且 v5，v6是 T标号T v4 min T v4 ,P v3 w34=min ,2 7 9T v6 min ,2 4 6 所有 T标号中， T（ v2）最小，令 P（v2） 5 第三步： v2是刚得到的 P 标号，考察 v2T v4 min T v4 ,P v2 w24=min 9,5 2 7T v5 min T v5 ,P v2 w25 min ,5 7 12 所有 T标号中， T（ v6 ）最小，令 P（v6） 6 第四步： v6是刚得到的 P 标号，考察 v6T v4min T v4 ,P v6 w64min 9,6 2 7T v5min

11、T v5 ,P v6w65 min12,617Tv7minT v7,Pv6w67min,6612所有 T标号中， T（ v4），T（ v5 ）同时标号，令 P（ v4） =P（ v5）7 第五步：同各标号点相邻的未标号只有v7T v7min T v7 ,P v5 w57 min 12,7 3 10至此： 所有的 T标号全部变为 P标号，计算结束。 故v1至v7 的最短路 为 10 。管理运筹学模拟试题 2、单选题（ 每题分 ，共 20 分。）1目标函数取极小（ minZ）的线性规划问题可以转化为目标函数取极大的线性规划问题求解，原问题的目标函数值等于（A. maxZ B. max（-Z）2.

12、下列说法中正确的是（ ）。 基本解一定是可行解若 B 是基，则 B 一定是可逆 的）。C. max（-Z）基本可行解的每个分量一定非负非基变量的系数列向量一定是线性相关3在线性规划模型中，没有非负约束的变量称为（）B松弛变量C人工变量A多余变量4. 当满足最优解， 且检验数为零的变量的个数大于基变量的个数时， 多重解D自由变量 可求得（ ）。无解正则解退化解5对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验但不 完全满足（ ）。A等式约束B “ ”型约束C“ ”约束D非负约束6. 原问题的第个约束方程是 “ ”型，则对偶问题的变量 yi 是（ ）。 多余变量 自由变量 松弛

13、变量 非负变量7. 在运输方案中出现退化现象，是指数字格的数目 （）。A.等于 m+nB.大于 m+n-1C.小于 m+n-1D.等于 m+n-18. 树的任意两个顶点间恰好有一条（ ）。边 初等链 欧拉圈 回路9若 G 中不存在流 f 增流链，则 f 为 G 的（）。A最小流B最大流C最小费用流D无法确定10.对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验但不 完全满足（ ）等式约束 “”型约束 “”型约束 非负约束二、判断题题（每小题 2 分，共 10分）1线性规划问题的一般模型中不能有等式约束。（）2对偶问题的对偶一定是原问题。（）3产地数与销地数相等的运输问题是产

14、销平衡运输问题。（）4对于一个动态规划问题，应用顺推或逆解法可能会得出不同的最优解。（）5在任一图 G中，当点集 V 确定后，树图是 G中边数最少的连通图。 （ ）三、计算题（共 70 分）1、某工厂拥有 A,B,C三种类型的设备，生产甲、乙两种产品，每件产品在生产中需要使用的机时数，每件产品可以获得的利润，以及三种设备可利用的机时数见下表：求：（1）线性规划模型； （5 分）（ 2）利用单纯形法求最优解； （ 15 分）4. 如图所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要 从v1出发，经过这个交通网到达 v8 ，要寻求使总路程最短的线路。 （15 分）5. 某项

15、工程有三个设计方案。 据现有条件， 这些方案不能按期完成的概率分别为 ,即三个方 案均完不成的概率为 =。为使这三个方案中至少完成一个的概率尽可能大，决定追加2万元资金。 当使用追加投资后， 上述方案完不成的概率见下表，问应如何分配追加投资，才 能使其中至少一个方案完成的概率为最大。（15 分 ）追加投资（万元）各方案完不成的概率123012管理运筹学模拟试题 2 参考答案一、单选题4. A .5. D 6. B 7. C 9. B二、多选题1. 2. 3. 4. 5. 三、计算题1. 解：（1） maxz 1500x12500x23x12x265满足2x1x2403x275x1,x2 02）

16、cBxB1x2x3x4x50x365321000x44021010400x5750300125z0150025000000x3153010-2/350x4152001-1/32500x22501001/3z-625001500000-2500/3-1500x15101/30-2/90x4500-2/311/92500x22501001/3z-7000000-5000-500*T最优解 x (5,25,0,5,0) 最优目标值 = 70000元 2. 解：此规划存在可行解 x (0,1) ，其对偶规划 min w 4y1 14y2 3y3满足：y1 3y2 y3 32y

17、1 2y2 y3 2y1,y2,y3 0T对偶规划也存在可行解 y (0,1,0) ，因此原规划存在最优解。3、解：可以作为初始方案。理由如下：(1) 满足产销平衡( 2)有 m+n-1 个数值格(3)不存在以数值格为顶点的避回路4. 解：5.解： 此题目等价于求使各方案均完不成的概率最小的策略。 策过程的第 k 个阶段， k1，2，3。把对第 k 个方案追加投资看着决xk第k个阶段，可给第 k, k+1， 3个方案追加的投资额。ukDkuk对第 k 个方案的投资额 uk 0,1,2且ukxkxk 1xkuk阶段指标函数 C xk ,ukp xk ,uk过程指标函数3 C xk ,uk Vk

18、1,3 ik,这里的 p xk ,uk 是表中已知的概率值。Vk,3f k xkmu iDnC xk,uk k1，2，3k 1 xk, f4 x4 1以上的 用逆序算法求解f3 x3 min C x3,u3u3 D3k 3 时，得表：最优策略： u11，u2=1, u3=0 或 u1 0， u2 =2, u3 =0， 至少有一个方案完成的最大概率为 =四 川 大 学 网 络 教 育 学 院 模 拟 试 题（ C ）管理运筹学二、 多选题（每题 2分，共 20 分） 1求运输问题表上作业法中求初始基本可行解的方法一般有 （）A西北角法B最小元素法C单纯型法D伏格尔法E位势法2建立线性规划问题数学

19、模型的主要过程有（）A 确定决策变量 B 确定目标函数 C确定约束方程D解法E结果3化一般规划模型为标准型时， 可能引入的变量有（）A松弛变量B剩余变量C自由变量D非正变量E非负变8就课本范围内，解有“”型约束方程线性规划问题的方法有（ ）A大 M 法B两阶段法C标号法D统筹法E对偶单纯型法10线性规划问题的主要特征有（ ）A目标是线性的 B约束是线性的 C求目标最大值 D求目标最小值 E非线 性（）（）二、辨析正误（每题 2 分，共 10 分） 1线性规划问题的一般模型中不能有等式约束。 2线性规划问题的每一个基本可行解对应可行域上的一个顶点。 3线性规划问题的基本解就是基本可行解。4同一问

20、题的线性规划模型是唯一。5对偶问题的对偶一定是原问题。6产地数与销地数相等的运输问题是产销平衡运输问题。 7对于一个动态规划问题，应用顺推或逆解法可能会得出不同的最优解。 8在任一图 G中，当点集 V 确定后，树图是 G中边数最少的连通图。 9若在网络图中不存在关于可行流f 的增流链时， f 即为最大流。10无圈且连通简单图 G 是树图。三、计算题（共 70 分）1、某工厂要制作 100 套专用钢架，每套钢架需要用长为 2.9m , 2.1m , 1.5m 的圆 钢各一根。已知原料每根长 7.4m ，现考虑应如何下料，可使所用的材料最省产品甲产品乙设备能力 /h设备 A3265设备 B2140

21、设备 C0375利润 /（元/件）15002500求：（1）写出线性规划模型（ 10 分）（2）将上述模型化为标准型（ 5 分）2、求解下列线性规划问题， 并根据最优单纯形法表中的检验数， 给出其对偶问题的最优解。 （15 分）maxz 4x1 3x2 7x3x1 2x2 2x3 100满足3x1 x2 3x3 100x1,x2,x3 03 断下表中方案是否可作为运输问题的初始方案，为什么（ 10 分）4. 用 Dijkstra 算法计算下列有向图的最短路。 （15 分）5某集团公司拟将 6 千万资金用于改造扩建所属的 A、B、C 三个企业。每个企业的利润增 长额与所分配到的投资额有关，各企业

22、在获得不同的投资额时所能增加的利润如下表所示。 集团公司考虑要给各企业都投资。 问应如何分配这些资金可使公司总的利润增长额最大（ 15分）四 川 大 学 网 络 教 育 学 院 模 拟 试 题（ C ）管理运筹学参考答案三、多选题4. ABE .5. AB二、判断题1. 2. 3 4. 5. 6. 7. 8. 9. 10. 三、计算题1. 解 分析：利用7.4m 长的圆钢截成 2.9m , 2.1 m ,1.5m 的圆钢共有如下表所 示的 8 中下料方案。方案 毛胚 /m方案1方案2方案3方案4方案5方案6方案7方案8211100000210321010130234合计剩余料 头0设 x1 ，

23、 x2， x3 ， x4， x5 ， x6 ， x7 ， x8分别为上面 8 中方案下料的原材料根数 min z x1 x2 x3 x4 x5 x6 x7 x82. 解 ：引入松弛变量 x4, x5将模型化为标准型，经求解后得到其最优单纯型表： 最优单纯型表基变量bix1x2x3x4x5x2253/4103/41/2x3255/4011/41/2i-25010/4001/22*T 由此表可知，原问题的最优解 x* (0, 25, 25)T ，最优值为 250.表中两个 松弛变量的检验数分别为 1/2 , 2 ,由上面的分析可知，对偶问题的 最优解为 ( 1/ 2,2) 。3.解：不能作为初始方

24、案，因为应该有 n+m-1=5+4-1=8有数值的格。4.解： P( v1)0T(vj)(j 2， 37)第一步：因为 v1,v2v1,v3 ，v1,v4 A且v2，v3，v4是 T 标号，则修改上个点的 T 标号分别为Tv2minTv2 ,P v1w12=min,0 2 2Tv3minTv3 ,P v1w13=min,0 5 5Tv4minTv4 ,P v1w14=min,0 3 3所有 T标号中， T( v2 )最小，令 P( v2)2 第二步： v2是刚得到的 P 标号，考察 v2 v2,v3 ， v2,v6A，且 v3，v6是T标号T v3 min T v3 ,P v2 w23=min

25、 5,2 2 4 T v6 min ,2 7 9 所有 T标号中， T（ v4 ）最小，令 P（ v4）3 第三步： v4是刚得到的 P 标号，考察 v4 T v5 min T v5 ,P v4 w45 min ,3 5 8所有 T标号中， T（ v 3 ）最小，令 P（ v3）4 第四步： v3是刚得到的 P 标号，考察 v3 T v5 min T v5 ,P v3 w35 min 8,4 3 7 T v6 min T v6 ,P v3 w36 min 9,4 5 9所有 T标号中， T（ v 5 ）最小，令 P（ v5）7 第五步： v5是刚得到的 P 标号，考察 v5 T v6 min T v6 ,P v5 w56 min 9,7 1 8 T v7 min T v7 ,P v5 w57 min ,7 7 14所有 T标号中， T（ v 6 ）最小，令 P（ v6）8 第 6 步： v6 是刚得到的 P 标号，考察 v6 T v7 min T v7 ,P v6 w67 min 14,8 5 13T（ v7 ） P（ v7 ） 13至此： 所有的 T标号全部变为 P标号，计算结束。 故v1至v7 的最短路 为 13 。5.