运筹学模拟试题及参考答案

1、运筹学模拟试题及参考答案、判断题（在下列各题中，你认为题中描述的内容为正确者，在题尾括号内写，错误者写“X”。） TOC o 1-5 h z 1.图解法提供了求解线性规划问题的通用方法。（）2,用单纯形法求解一般线性规划时，当目标函数求最小值时，若所有的检验数Cj-Zj0,则问题达到最优。（）.在单纯形表中，基变量对应的系数矩阵往往为单位矩阵。（）.满足线性规划问题所有约束条件的解称为基本可行解。（）.在线性规划问题的求解过程中，基变量和非基变量的个数是固定的。（）.对偶问题的目标函数总是与原问题目标函数相等。（）7,原问题与对偶问题是对应的。（）.运输问题的可行解中基变量的个数一定遵循m+n

2、1的规则。（）.指派问题的解中基变量的个数为 m+n。（）.网络最短路径是指从网络起点至终点的一条权和最小的路线。（）.网络最大流量是网络起点至终点的一条增流链上的最大流量。（）.工程计划网络中的关键路线上事项的最早时间和最迟时间往往不相等。（）.在确定性存贮模型中不许缺货的条件下，当费用项目相同时，生产模型的间隔时间比订购模型的间隔时间长。（）.单目标决策时，用不同方法确定的最佳方案往往是一致的。（）15.动态规划中运用图解法的顺推方法和网络最短路径的标号法上是一致的。（）二、简述题1,用图解法说明线性规划问题单纯形法的解题思想。.运输问题是特殊的线性规划问题，但为什么不用单纯形法求解。.建

3、立动态规划模型时，应定义状态变量，请说明状态变量的特点。三、填空题.图的组成要素; 。. 求最小树的方法有 、。.线性规划解的情形有 、.求解指派问题的方法是 。.按决策环境分类，将决策问题分为 、. 树连通，但不存在 。四、下列表是线性规划单纯形表（求 Zmax）,请根据单纯形法原理和算法.计算该规划的检验数Cj一32000Cixbbxi x2 x3x4x53xi3110-1022x340111/20Z j33.52-20C j-Z j.计算对偶问题的目标函数值.确定上表中输入，输出变量五、已知一个线性规划原问题如下，请写出对应的对偶模型Smax 6x1 x2 TOC o 1-5 h z x

4、1 x272xi 3x216x1, x20六、下图为动态规划的一个图示模型，边上的数字为两点间的距离，请用逆推 法求出S至F点的最短路径及最短路长。BiB3七、自己选用适当的方法，对下图求最小（生成）树。八、用标号法求下列网络 V1-V7的最短路径及路长九、下图是某一工程施工网络图（统筹图），图中边上的数字为工序时间（天）, 请求出各事项的最早时间和最迟时间，求出关键路线，确定计划工期。十、某企业生产三种产品 Ai、A2、A3。每种产品在销售时可能出现销路十一、已知运输问题的运价表和发量和收量如表 2所示，请用最小元素法求出 运输问题的一组可解释。BiB2B3B4Ai291279A213524

5、A31042653546俵2）2, 3,4）、Bj 为工作项目（j=1,2,AiA2A3A43, 4）,请作工作安排，使总的工作时间最小。B1B2B3B441742235643324卜列表3是一个指派问题的效率表（工作时间表），其中A参考答案一、判断题 X(2)V(3)V(4)X(5)V(6)X (7)V (8)V (9) X (10) V(11)X(12) X(13)，(14) X(15) X二、简述题1、在可行域内先确定一个基本可行解，然后通过迭代计算，逐步使目标函数增大 (求Zmax),求出新解，计算出方案机会成本后，得出相应检验数，当所有的Cj- ZjW0时即得最优解。2、运输问题可以

6、用单纯形求解，但由于虚设的变量多，运算复杂，十分不合算，所以不用 单纯形法求解，而用简单的表上作业法求解。3、由于动态规划的求解过程是一个多段决定过程，其状态变量必须满足无后效性和可知性 的特征要求。三、填空题.树.破圈法和避圈法.可行解、退化解、无界解、多重解.匈牙利法.确定性决策，不确定性决策，风险性决策。6.圈。四.1.Cj320000Ci X0bXiX2X3X4X5X6(3) Xi3101/2101/21-1(2) X240111/2-10Zj327/2-2-23/2Cj z00(-7/2)(2)2-3/2Smin = 15X4输入，Xi输出。五、Zmax=-7y 1 +16y 2y1

7、 2 y2 6y1 3 y21y1，y2 0六、C110)17112F(0)(18)14C2A210(26)9(27)10137(13)SA1 Bi Ci F32七、V2V45V6ViV53V3最小树为图中双线所示，最小树长1433(v6, 10)V6(V3, 9) (V5, 7)(Vi, 4)V2(Vi, 0 Vi(Vi, 6)V5(Vi, i3) V7(vi, 3)(V? 5)SiS2S3Ai30i0-6A220i29A3i5i3i2max3020i5十二、选方案AiAiA2A 3bj牛耳2早3 早4212 63 3归io , d) 曷 b 43746Bi B2 B3 B4Bi B2 B3

8、 B4Ai4743 , I1 (Q) 1I I, 6I I- 3 IA2235 0 ,- 3As564.I2 I I 3 ,I II A463&=I4 I II I。I- 2（表3）运筹学试题参考答案 一、填空题（每空2分，共10分）1、在线性规划问题中，若存在两个最优解时，必有相邻的顶点是 最优解。2、树图中，任意两个顶点间有且仅有一条链_。3、线性规划的图解法适用于决策变量为两个 线性规划模型。4、在线性规划问题中，将约束条件不等式变为等式所引入的变量被称为松弛变县M。5、求解不平衡的运输问题的基本思想是设立虚供地或虚需求点，化为供求平衡的标准形式。6、运输问题中求初始基本可行解的方法通常

9、有最小费用法 与 西北角法 两种方法。7、称无圈的连通图为树，若图的顶点数为 p,则其边数为 p1 。二、（每小题5分，共10分）用图解法求解下列线性规划问题：1） max z = 6xi+4x2 TOC o 1-5 h z 2xi X210 x1 x28x27x1，x20、2) min z =2xi+x2解:x1 4x2 24 x1 x2 85 x110 x2 0、从上图分析，可行解域为abcde,最优解为e点由方程组x1 x2 8x15.X = (5, 3) Tx2min z =Z*= 2 5+3=13解出 x1=5, x2=3三、（15分）一家工厂制造甲、乙、丙三种产品，需要三种资源一一

10、技术服务、劳动力和行政管理。每种产品的资源消耗量、单位产品销售后所能获得的利润值以及这三种资源的储备量如下表所示：技术服务劳动力行政管理单位利润甲110210乙1426丙1564资源储备量1006003001）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5分）2）用单纯形法求该问题的最优解。（10分）解：1）建立线性规划数学模型：设甲、乙、丙三种产品的生产数量应为 XI、X2、X3,则Xi、X2、X30,设z 是产品售后的总利润，则maX z =10Xi+6X2+4X3s.t.X1 x2 x3 100 10X1 4X2 5X3 6002X1 2X2 6X3 300X1, X2，X30

11、2）用单纯形法求最优解：加入松弛变量X4, X5, X6,得到等效的标准模型：max z =10 x1+6x2+4x3+0 X4+0 X5+0 X6100600 x6 300s.t.X1 X2 X3 X410X1 4x2 5x3x52x1 2x2 6x3 Xj 0, j 1,2,.,6列表计算如下:1064000CbXbbe lX1X2X3X4X5X60X41001111001000X5600(10)45010600X630022600115000000010T640000X4400(3/5)1/21-1/100200/310X16012/51/201/1001500X618006/550-1

12、/51150104501002T10-106X2200/3015/65/3-1/6010X1100/3101/62/31/600X6100004-201220010620/310/32/30300-8/3-10/32/30.100200.X*=(，i 3，3- ，0, 0, 0, 100) 1100200 2200max z =10 x+6 x =333四、（10分）用大M法或对偶单纯形法求解如下线性规划模型:min z =540 xi + 450X2+ 720X33x1 5x2 9x3 70 TOC o 1-5 h z 9x1 5x2 3x330Xi, X2,X30解：用大M法，先化为等效的

13、标准模型:max z/ = 540 xi 450 x2 720 x3s.t.3x1 5x2 9x3 x4709x1 5x2 3x3x5 30yj 0, j 1,2,.,5增加人工变量乂6、乂7,得到:max z/ =- 540 x1 450 x2 720 x3 Mx 6 Mx 73x15x2 9x3 x49x1 5x2 3x3x5x7 30 xj 0,j 1,2，,5大M法单纯形表求解过程如下: 540 450-72000MMCbXbbXiX2X3X4X5X6X7e l-MX670359101070/3MX730(9)53010130/9=10/3-12M-10M-12MMM-M-M12M 5

14、40 T10M -45012M -720-M-M00MX660010/3(8)11/31 1/3 540Xi10/315/91/30-1/901/910/3/1/3=10-300+10/3 M-8M - 180-MM/3+6 0-MM/3 600-150+10/3 M8M -540 fMM/3 600M/3+6 0 720X315/205/121-1/81/241/8-1/2415/2/5/12=18 540Xi5/61(5/12)01/24-1/81/241/85/6/5/12=2 540 572-720135/2475/12135/2-75/20125T0135/2-475/12135/2

15、 M75/2 M 720X320/3-1011/61/61/6-1/6 450X2212/5101/10 3/101/103/10 360-450-7207515-75-15 5700-1800075-1575-M15 -M.该对偶问题的最优解是x*= (0, 2,203，0, 0) T最优目标函数值 min z = ( 5700) =5700B1B2B3B4SiA12011865A25910210A31874115dj331212五、（12分）给定下列运输问题:（表中数据为产地Ai到销地Bj的单位运费）1）用最小费用法求初始运输方案，并写出相应的总运费；（4分）2）用1）得到的基本可行解，继

16、续迭代求该问题的最优解。（10分）解：用“表上作业法”求解。 TOC o 1-5 h z 3B1|1/ B210 1/ 12B2A1、A2B4A3B3B4Z=20X 3+11 x 2+2 x 10+7 x 1+4 x 12+1 x 2=159选X21作为入基变量迭代调整用表上闭回路法进行迭代调整：再选X13作为入基变量迭代调整最小运费 Z=11X3+8X2+5X3+2X7+4X 10+1 X5=123六、（8分）一个公司经理要分派4个推销员去4个地区推销某种商品。4个推销员各有不同的 经验和能力，因而他们在每一地区能获得的利润不同，其估计值如下表所示：D1D2D3D4甲35272837乙283

17、42940丙35243233丁24322528问：公司经理应怎样分派4个推销员才使总利润最大? 解：用求极大值的“匈牙利法”求解。35272837M Cij5131232834294012611035243233M =4051687243225281681512效率矩阵表示为:行约简1021208106110911370024列约简标号未得到最优解,12(0)8需要继续变换矩阵11(0)（求能覆盖所有001008841104604标号(0)10*0811（0）1000000100100100(0)*0所画（）0元素少于n（n = 4）,0元素的最少数直线集合）：2,(0)4在直线交叉处加上2。

18、*0(0)使总利润为最大的分配任务方案为:甲D1,乙D4,丙D3, 丁 D2此时总利润 W=35+40+32+32=139七、（6分）计算下图所示的网络从 A点到M点的最短路线及其长度。,可用逆向追踪“图上标号法”解决如下:最佳策略为：ACFGf M解：此为动态规划之“最短路问题”此时的最短距离为8+8+5+5=26V5八、（8分）用P-T标号法求下图从至的最短路。（需写出最短路线）V2V8解决如下:解：此为网络分析之“最短路问题”，可用顺向追踪“ TP标号法”最短距离 2+1+1+7+9=20。V1 到 v7 的最短路线是： v1f v2v5-v9-v8-V11,九、（10分）用我增广链的方

19、法求如下网络的最大流。（需写出相应的增广链）（弧旁的数字为该弧容量）解：此为网络分析之“寻求网络最大流问题”，可用“寻求网络最大流的标号法（福特富克尔逊算法）”解决如下:标号过程：1、给 vs标上（0, ）;2、检查vs,在弧（vs, v1）上,fsi=0, Csi=4, fsiCsi,给 vi 标号(s, B(v 其中(m) min(vs),(Csifsi)min 4 04,(s, 4)v4vi(0, 00(s, i0)同理，给V2标号(s,B(V2),其中(V2)min(Vs), (Cs2fs2) min,100 10 , TOC o 1-5 h z 3、检查 v1,在弧(v1, v3)上

20、，f13=0, C13=3, f13VC13,给 v3标号(1, B(v3),其 中(“)min (vJ(C13%) min 4 3 03,(s, 4)(3, 3)v1v4检查v3,同理，给 v4标号(3, B(v4),其中 M) min 3)834 34) min 3,403,检查v2,同理，给 v5标号(2, B (v5),其中(vs) min(v2),(C2525)min 10,404,4、检查v4，在弧(v4，v。上，f4t=0,C4t=7,f4tC4t,给vt标号(4, B(v。)，其中(vt) min(v4),(C4tfQ min 3,7 03, vt 得到标号，标号过程结束。(s

21、, 4)(3, 3)一 厂I、， Lv1v4调整过程：从vt开始逆向追踪，找到 增广链(s, 4)(3, 3)V4Vi(4, 3)(0, 00W (Vs，Vi , V3, V4, Vt), =3,在p上进行流量=3的调整，得可行流f如图所示:V4(1, 0)(3, 3)(7, 3)(4, 3)(3, 0)(2, 0)Vs *VtV3(10, 0)(8, 0)(4, 0)V5V2去掉各点标号，从Vs开始，重新标号3V30533V305Vt又得到标号，标号过程结束再次从vt开始逆向追踪，找到 增广链(s, 10)叱(vs, v2, v3, v4, vt),=1,在 w上进行流量=1的调整，得可行流

22、f如图所(s, 1)(3, 1)v1(1,0)v4(7, 3)v2(s, 10)(2, 4)(s, 1)(3, 1)v1(4, 1)v5v4(1, 0)(4, 3)(7, 3)v2(4, 3)(0, 00) vs(10, 0)(0, 00) vs(10, 0)v5(4, 1)(2, 4)ViV4(1,0)(3, 3)(7, 4)(4, 3)(3, 0)VsVtV3(10, 1)(8, 0)(470)V5V2去掉各点标号，从Vs开始，重新标号。(s, 1)(1,1)V4V1(1, 0)(3, 3)(7, 4)(4, 3)(3, 0)(2, 0)Vt(8, 0)(4, 0)V2V3(2, 2)(0

23、, 00) Vs (10, 1)，9V5(4, 1)Vt又得到标号，标号过程结束再次从Vt开始逆向追踪，找到 增广链(s, 1)(1,1)V4Vi(1,0)(3, 3)(7, 4)(4, 3)(3, 0)(2, 0)5, 0)(10, 1)(8, 0)(4, 0)V5V3(2, 2)Vt(4, 1)(0, 00) VsV2(s, 9)(2, 4)s，V1，V4, Vj, =1,在H上进行流量=1的调整，得可行流f如图所示:V4V1(1,1)(3, 3)(7, 5)(4, 4)(3, 0)(2, 0)VsVtV3(10, 1)(8, 0)(4, 0)V5V2去掉各点标号，从Vs开始，重新标号。3

24、153215V32、V32、Vt又得到标号，标号过程结束再次从vt开始逆向追踪，找到 增广链1 (vs, v2, v5, v4, vt),=2,在 w上进行流量=2的调整，得可行流f 如图所(5, 2)(5, 2)(2, 4)vi(10, 1)v2(s, 9)v5v1(10, 1)(s, 9)(4, 4)(0, 00) vsv4(1 , 1)(7, 5)(4, 2)(4, 4)(0, 00) vsv2v4(1 , 1)(7, 5)v5(4, 2)(2, 4)3V3153V315s去掉各点标号，从Vs开始，重新标号V1(1,1)V4(-t, 3)(4, 4)(7, 7)V2V5(-3, 3)V1

25、(10, 3)V2(s, 7)V5Vs(4, 4)(0, 00) Vs(1 , 1)V4(7, 7)(5, 3)(10, 3)(3, 3)Vt又得到标号，标号过程结束再次从vt开始逆向追踪，找到 增广链3V315sV3151 (vs, v3, v5, vt),=3,在 w上进行流量=3的调整，得可行流f 如图所示去掉各点标号，从(-t, 3)v4v2v5(-3, 3)(0, 8)vs(10, 3)v2(s, 7)vi(1 , 1)(4, 4)(7, 7)(4, 4)v4(1 , 1)(7, 7)(5, 3)v5vs(10, 3)(3, 3)vs开始，重新标号(-3, 1)(-t, 1)(1,1)(3, 3)(4, 4)(3, 3)(10, 3)(4, 2)V3(2, 1)(0, 00) vsV4(7, 7)(2, 2)(8, 3)V5Vt