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

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

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

3、态变量的特点。三、填空题图的组成要素;。求最小树的方法有、。线性规划解的情形有、求解指派问题的方法。按决策环境分类，将决策问题分为树连通，但不存在。四、下列表是线性规划单纯形表（求Zma）,请根据单纯形法原理和算法。计算该规划的检验数Cj32000jCixBbxiX2X3X4x53x13110-10122x340111/20z33.52-20jczjj计算对偶问题的目标函数值确定上表中输入，输出变量五、已知一个线性规划原问题如下，请写出对应的对偶模型S=6x+xmax12x+x7121612x,x012六、下图为动态规划的一个图示模型，边上的数字为两点间的距离，请用逆推法求出S至F点的最短路径

4、及最短路长。V6八、用标号法求下列网络V-V7的最短路径及路长。V7九、下图是某一工程施工网络图（统筹图），图中边上的数字为工序时间（天）请求出各事项的最早时间和最迟时间，求出关键路线，确定计划工期。十、某企业生产三种产品餌、A2、A3。每种产品在销售时可能出现销路好（SJ,销路一般（S2）和销路差（S3）三种状态，每种产品在不同销售状态的获利情况（效益值）如表1所示，请按乐观法则进行决策，选取生产哪种产品最为合适。逆态益值产品S1S2S3A13010-6A220129A3151312（表1）十一、已知运输问题的运价表和发量和收量如表2所示，请用最小元素法求出运输问题的一组可解释。B1B2B3

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

6、Wo时即得最优解。2、运输问题可以用单纯形求解，但由于虚设的变量多，运算复杂，十分不合算，所以不用单纯形法求解，而用简单的表上作业法求解。3、由于动态规划的求解过程是一个多段决定过程，其状态变量必须满足无后效性和可知性的特征要求。三、填空题1.树破圈法和避圈法可行解、退化解、无界解、多重解匈牙利法确定性决策，不确定性决策，风险性决策。TOC o 1-5 h z圈。四.1.c.-320000jX1X2X3X4X5X6-4012-10120111/2-10327/2-2-23/2CiX0b(3)X13(2)X24ZjC.Z.00(-7/2)(2)2-3/22Smin=153.X4输入，Xi输出。五

7、、Z=-7y,+16y2TOC o 1-5 h zmax12一y+2y6丿1丿2一y+3y012六、SA1B1C1F3215七、L=10,13)7最短路径：VV3V5V6v7S1S2S3A130厶10-6A220129A3151312十、max3020选方案A1B143-aiA1/.129V6|A235633A310654-bj3746十二、BBBB1b2b3b412343-6-3A1474A22350-0-1111-3A3564k|21-3-1110A463=8i411丄丨1-2（表3）运筹学试题参考答案一、填空题（每空2分，共10分）1、在线性规划问题中，若存在两个最优解时，必有相邻的顶点

8、是最优解。2、树图中，任意两个顶点间有且仅有一条链3、线性规划的图解法适用于决策变量为两个线性规划模型。4、在线性规划问题中，将约束条件不等式变为等式所引入的变量被称为松弛变量。5、求解不平衡的运输问题的基本思想是设立虚供地或虚需求点，化为供求平衡的标准形式。6、运输问题中求初始基本可行解的方法通常有最小费用法与西北角法两种方法。7、称无圈的连通图为树，若图的顶点数为p,则其边数为p1二、（每小题5分，共10分）用图解法求解下列线性规划问题：1)maxz=6x1+4x22x+x1012x+x812x0、从上图分析，可行解域为abcde，最优解为e点。2)minz=2X+x2一x+4x8彳125

9、x0I2解:由方程组解军出X=5,x2=3x+x=812x=5Jix.X*=1=(5,3)tIx丿minz=Z*=2x5+3=13三、（15分）一家工厂制造甲、乙、丙三种产品，需要三种资源技术服务、劳动力和行政管理。每种产品的资源消耗量、单位产品销售后所能获得的利润值以及这三种资源的储备量如下表所示：技术服务劳动力行政管理单位利润甲110210乙1426丙1564资源储备量1006003001）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5分）2）用单纯形法求该问题的最优解。（10分）解：1）建立线性规划数学模型：设甲、乙、丙三种产品的生产数量应为X、x2、X3,则X、x2、x3$0

10、,设z是产品售后的总利润，则maxz=0 x+6x2+4x3s.t.x+x+x1002310 x+4x+5x600彳1232x+2x+6x01232）用单纯形法求最优解：加入松弛变量X4，X5，X6，得到等效的标准模型:456maXz=10X+6X+4X+0X+0X+0XTOC o 1-5 h z123456s.t.=100+x=6005+x=3006x+x+x+x123410 x+4x+5x1232x+2x+6x123x0,j=1,2,.,6j列表计算如下:10 x1x2x41010X4X4X2x11006003004060180200/3100/3100(10)60150010t10(3/

11、5)2/56/51/21/2-15/61/6-1/101/10-1/5-15/3-1/6-2/31/6200/3150150-2220031020/310/32/3-8/3-10/3-2/30，100)TX*=(,200,0,0,332200maxz=10X竺+6X型333四、（10分）用大M法或对偶单纯形法求解如下线性规划模型:minz=540 x1450 x2720 x33x+5x+9x70123v9x+5x+3x30123x,x,x0123解：用大M法，先化为等效的标准模型maxz/=540 x1450 x2720 x3s.t.3x+5x+9x-x二701234v9x+5x+3x-x二3

12、01235y0,j二1,2,5增加人工变量X6、X7，得到:67maXz/=540X450X720XMXMXTOC o 1-5 h z123673x+5x+9x-x+x二7012346v9x+5x+3xx+x3012357x0,j1,2,.,5j大M法单纯形表求解过程如下：CBXBb540 x1450 x2720 x30 x40 x5Mx6Mx70L-Mx670359101070/3-Mx730(9)53010130/9=10/312M10M12MMMMM12M540t10M45012M720MM00-Mx660010/3(8)11/311/3540 x110/315/91/301/901/9

13、10/3/1/3=10-300+10/3M-8M180MM/3+60MM/3600-150+10/3M8M-540tMM/3600M/3+60720 x315/205/1211/81/241/81/2415/2/5/12=18540 x15/61(5/12)01/241/81/241/85/6/5/12=2540572720135/2475/12135/275/20125t0135/2475/12135/2M75/2m720 x320/31011/61/61/61/6450 x2212/5101/103/101/103/1036045072075157515570018000751575M15

14、M该对偶问题的最优解是x*=(0，2,20c，0，0)T最优目标函数值minz=（5700）=5700五、（12分）给定下列运输问题：（表中数据为产地Ai到销地斗的单位运费）BiB2B3B4SjA12011865A25910210A31874115d.3312121）用最小费用法求初始运输方案，并写出相应的总运费；（4分）2）用1）得到的基本可行解，继续迭代求该问题的最优解。（10分）解：用“表上作业法”求解。1）先用最小费用法（最小元素法）求此问题的初始基本可行解：费销7B1B2B3B4SiA201186532XXA5910210XXX10A1874115X1122dj3312123030初

15、始方案:B110AB24B2Z=20X3+11X2+2X10+7X1+4X12+1X2=1592）用闭回路法，求检验数:费肖产AB1B2B3B4SiA20118061532XXA5129-1105210XXX10A18-274115X1122dj3312123030I。21=12其余。j.选x21作为入基变量迭代调整。用表上闭回路法进行迭代调整：费肖产AB1B2B3B4SiA2011812611523XXA591310152101XX9X123dj3312123030再选x13作为入基变量迭代调整。费销产ABiB2B3B4SiA20-12118615X32XA59-1

16、1052103XX7A18-14704115XX105dj3312123O30调整后，从上表可看出，所有检验数W0,已得最优解。j最优方案为:B2B3BiB45B3B4最小运费Z=llX3+8X2+5X3+2X7+4X10+1X5=123六、（8分）一个公司经理要分派4个推销员去4个地区推销某种商品。4个推销员各有不同的经验和能力，因而他们在每一地区能获得的利润不同，其估计值如下表所示：DiD2D3D4甲35272837乙28342940丙35243233丁24322528问：公司经理应怎样分派4个推销员才使总利润最大？解：用求极大值的“匈牙利法”求解。35272837M-C.r513123、

17、28342940126110352432331lzM=405168724322528丿J681512丿效率矩阵表示为：行约简r2106(0)r21090列约简12680*12611001132标号(0)110*2I8074丿标号8(0)44丿未得到最优解，需要继续变换矩阵所画（）0元素少于n（n=4）.求能覆盖所有0元素的最少数直线集合）：210126(0)11.8(0)0*(0)、0*2未被直线覆盖的最小元素为Cj=2,在未被直线覆盖处减去2,在直线交叉处加上2。厂010088411046040、046丿标号(0)100*8110)(0)4得最优解:(1000000100100100丿0*、

18、0)46丿使总利润为最大的分配任务方案为:甲D，乙_D4，丙_D3，丁_D2此时总利润W=35+40+32+32=139七、（6分）计算下图所示的网络从A点到M点的最短路线及其长度。8此时的最短距离为8+8+5+5=26八、（8分）用P-T标号法求下图从至的最短路。（需写出最短路线）解：此为网络分析之“最短路问题”可用顺向追踪“TP标号法”解决如下:v1到v/勺最短路线是：Vjfv2fv5fv9fv8fv,最短距离2+1+1+7+9=20。171259811九、（10分）用找增广链的方法求如下网络的最大流。（需写出相应的增广链）（弧旁的数字为该弧容量）解：此为网络分析之“寻求网络最大流问题”，

19、可用“寻求网络最大流的标号法（福特富克尔逊算法）”解决如下：标号过程：1、给V标上（0,8）；s2、检查v,在弧（v,v）上，f=0,C=4,fC,给v标号（s,B（vJ），其ss1s1s1s1s111中P（v）=min|3（v）,（C一f）=min仃a,4o=4，1ss1s1冋理，给V标号(sB(V)，其中p(v)=min3(v),(C-f)=ming,10-o=10，TOC o 1-5 h z222ss2s23、检查v,在弧(v,v)上,f=0,C=3,fC，给v标号(1,&(v),其1131313131333中p(v)=min)=min,3-0=3,311313检查V,同理，给V标号(3

20、,&(V),其中卩(v)=minP(v),(C-f)=min,4-0=3，344433434检查V,同理，给V标号(2,&(V),其中卩(v)=min3(v),(C-f)=min0,4-0=4，2555225254、检查v,在弧(V,v)上，f=0,C=7,fC，给v标号(4,B(v),其中44t4t4t4t4ttt调整过程：从V开始逆向追踪，找到增广链。t(s1374432V31084V2V4V5V1Vt(3,3)(s,10)(4,3)(0,8)VsV,V,V,13得可行流f如图所示:v),9=3,在卩上进行流量=3的调整tt41去掉各点标号，从Vs开始，重新标号。(s,1)( ,1)(0,

21、(4,1)t(s,10)vt又得到标号，标号过程结束。再次从v开始逆向追踪，找到增广链tt(s,1)(3,1)(0,(4,1)t(s,10)叮vs，v2,v3,v4,vt），9T，在P上进行流量。=1的调整得可行流f如图所示：t去掉各点标号，从vs开始，重新标号。(s,1)(1,1)(0,(4,1)t(s,9)41vt又得到标号，标号过程结束。再次从v开始逆向追踪，找到增广链tt(-3, )(5,2)(s,1)( ,1)(0,(4,1)t(s,9)41g(v,v,v,v),0=1,在上进行流量。=1的调整，得可行流f如图所示:s14t14去掉各点标号，从vs开始，重新标号。(0,(4,2)t(s,9)vt又得到标号，标号过程结束。再次从V开始逆向