五邑大学《高级运筹学》考试试卷

五邑大学试卷学期：2014至2015学年度第1学期课程：高级运筹学任课教师（命题人）：使用班级：经管研2014姓名：学号：2111401002题号一二三四五六七八总分得分一、构建下述问题的线性规划数学模型并用系统软件求解（10分）生产需要2.9米、2.1米和1.5米的元钢各100根，已知原材料的长度是7.4米，问应如何下料，才能使所消耗的原材料最省。说明利用的是什么软件，求解的结果和重要的截图。解：分析可得，每一根原材料的下料方案有如下几种：123456782.9211100002.1021032101.510130234余料0.10.30.901.10.20.81.4经分析可得，这是一个线性规划问题，设按上述八种方案下料的原材料的根数分别为87654321xxxxxxxx、、、、、、、根，所需要的原材料的总根数为z根.数学模型如下：目标函数为：87654321minxxxxxxxxZ10024321xxxx10023276532xxxxx1004323876431xxxxxx087654321xxxxxxxx、、、、、、、且为整数这是一个线性规划问题，我用的软件lingo来解这道题，以下就是我用软件解这道题的重要步骤：1、打开lingo软件2、输入上述线性规划模型3、运行软件，结果如下由软件的运行结果可知，最优解如下，耗费原材料90根，其中按方案一下料的原材料为40根，按方案二下料的原材料为20根，按方案六下料的原材料为30根。二、用图解法求解下述线性规划问题（5分）2153maxxxZ123221xx204521xx321xx0,021xx解：由题意可得，以21xx、为坐标轴建立直角坐标系（1）根据约束条件画出与约束条件相应方程的直线，由这些直线共同确定出一个区域，即可行解的区域可行区域如下图所示：为纵轴为横轴，21xx其中，01232:121xxYY2：0204521xxY3：0321xx其中阴影部分的每一个点都是这个线性规划问题的解。（2）再分析目标函数2153maxxxZ，在这个坐标平面上，它表示以z为参数、-5/3为斜率的一组平行线：zxx515312，当z值由大变小时，直线沿其法线方向向上平移，如图所示：所以最后的最优解为20,4,021zxx三、用单纯形法求解下述线性规划问题（15分）32142maxxxxZ6321xxx42321xxx82321xxx0,0,0321xxx解：（1）先将此线性规划问题化为标准形。引入松弛变量654xxx、、后将其化为标准形：65432100042maxxxxxxxZ64321xxxx425321xxxx826321xxxx)6,5,4,3,2,1(0ixi在该标准形中，约束条件的系数矩阵中不含有单位矩阵，加入人工变量7x，使得上式变为：765432100042maxMxxxxxxxZ64321xxxx425321xxxx8276321xxxxx)7,6,5,4,3,2,1(0ixi（2）列出初始单纯性表，如下表所示：jc241000-MiBCBXb1x2x3x4x5x6x7x04x61111000605x4[1]1-201004-M7x81-2100-118jjzc2+M4-2M1+M00-M0此时得到的基本可行解为X=（0,0,0,6,4,0,8)（3）继续进行迭代。如下表所示：jc241000-MiBCBXb1x2x3x4x5x6x7x04x200[3]1-1002/321x411-20100_-M7x40-330-1-114/3jjzc02-3M5+3M0-2-M-M0(4)进行下一迭代。如下表所示：jc241000-MiBCBXb1x2x3x4x5x6x7x13x2/30011/3-1/30021x16/31102/31/300-M7x20-30-10-11jjzc02-3M0-5/3-M-1/3-M0根据最优性解的条件，这个解是最优的，但在最优解中包括了一个人工变量7x,这说该问题没有可行解。所以此题无可行解。四、已知如下产销量及运价表，求解此运输问题（15分）产销量及运价表（元）销地1销地2销地3产量（吨）产地110018012035产地215013020020产地39011016025销量（吨）263618解：这是一个产销平衡问题。用表上作业法求解，如下：(1)首先，在表格中找到最小运价90，即（产地3，销地1），由于产地3只有25吨，故优先供应销地25吨，划去产地3的那一行。在找到余下的最低运价100，即（产地1，销地1），供应1吨，划去销地1的那一列。再找到余下的最低运价120，即（产地1，销地3），供应18吨，划去销地3的那一列。再找到余下的最低运价130，即（产地2，销地2），供应20吨，划去产地2的那一行，最后只剩下运价为180的了，即（产地1，销地2），经计算可得，供应16吨。调运量销地1销地2销地3产量（吨）产地11161835产地22020产地32525销量（吨）263618至此，得到了初始最优方案。根据初始调运方案可得总运费Z=100*1+16*180+18*120+20*130+25*90=9990(2)对该初始最优方案进行检验，计算空格的检验数，当所有的检验数都大于0时，就得到了最优方案。采用闭合回路法。空格的检验数如下所示：（产地2，销地1）的检验数=150-100+180-130=100（产地2，销地3）的检验数=200-120+180-130=130（产地3，销地2）的检验数=110-180+100-90=-60（产地3，销地3）的检验数=160-120+100-90=50销地1销地2销地3产地1产地2100130产地3-6050故这个方案不是最优的。（3）以（产地3，销地2)为调整格，将其作为入基变量，找到此格原闭合回路的各个顶点，并依次进行编号，根据闭合回路的原理，可知（产地1，销地2）为换出变量。则调整方案为：销地1销地2销地3产量（吨）产地1171835产地22020产地391625销量（吨）263618该调整方案的检验数为：销地1销地2销地3产地160产地24070产地350所有的检验数都大于0了，所有此方案为最优方案，此时的总运费为：Z=17*100+18*120+20*130+9*90+16*110=9030（元）五、用隐枚举法求解下述0-1型整数规划问题（10分）4321342maxxxxxZ4324321xxxx3234321xxxx104321orxxxx，，，解：（1）将模型转化为极小的问题4321342minxxxxZ4324321xxxx3234321xxxx104321orxxxx，，，(2)令33111',1'xxxx，带入极小问题模型中得33'4'2min4321xxxxZ13''24321xxxx2'2'24321xxxx10',',,,,314321或xxxxxx(3)目标函数中变量按系数大小排列，约束条件中变量排列顺序也相应调整，得3''234min3142xxxxZ1''233142xxxx2''223142xxxx10',',,,,314321或xxxxxx(4)按目标函数值由小到大的顺序排列可能的解，并予以可行性检验。计算表格如下：序号变量组合)',',,(3142xxxxZ值是否满足约束条件是否可行条件1条件21（0,0,0,0）-3√××否2（0,0,0,1）-2××否3（0,0,1,0）-1××否4（0,1,0,0）0√×否5（1,0,0,0)1√√是停止最优解为0',0',0,13142xxxx（5）原问题的最优解为0,1,1,14321xxxx，Z=-1六、用动态规划求解下述非线性问题（10分）123maxzxxx1231239,,0xxxxxx解：这个问题是将一个数9分成三部分，使目标函数Z达到最大。取阶段变量k=1,2,3共分三个阶段。决策变量kx表示滴k个阶段分配的数量，状态变量ks表示从第k个阶段至第3个阶段可供分配的总数量，则状态转移方程为kkkxss1即11222333,,sxssxsxs=9允许决策集合：}0{)(kkkkksxxsD，允许状态集合：}90{kkkssS，91S。递推方程为)}(max{)(11kkkkksfxsf1)(44sf当k=3时，有333333,}max{)(sxsxsf当k=2时，有)}({max)}({max)(22203320223232xsxsfxsfsxsx令)()(22222xsxx，则：22222)('xsx再由2222210)('sxx得，又由直接验证可知的极大值点（为故)21,02)(''222222xsxx。这时，222241)(sxf，2221sx当k=1时，有})(41{max)}({max)(211102210112121xsxsfxsfsxsx令211111)(41)(xsxx，则)3)((41)('111111xsxsx，再令的极大值点。（为故由或得)31,0)31('',31,0)('111111111111xsxssxsxx此时2111111181)31(121)(sssssf因为3,3,3,93211xxxs所以最优解为,目标函数的最优解为27333Z七、用标号法求下图中SV点到其他各点的最短路（5分）解：如下图所示：下划线部分为永久标号，未画下划线的为临时标号。(1)(2)(3)（0,0）(M，)(M，)(M，)（sv，13）（sv，12）(M，)（0,0）（sv，12）（sv，13）（sv，12）(5v，24）(3v,24)（5v，39）(4v，30）（3v，30）（M,)（0,0）（sv，12）（sv，13）（sv，12）（3v，30）(5v，24）(3v,24)(4v，30）（2v，46）所以，1vvs的最短路径为1vvs，最短路径长为12，3vvs的最短路径为3vvs，最短路径长为125vvs的最短路径为5vvs，最短路径长为132vvs的最短路径为23vvvs，最短路径长为304vvs的最短路径为4543vvvvvvss或，最短路径长为246vvs的最短路径为643vvvvs或645vvvvs，最短路径长为30Fsvv最短路径为Fsvvvv23,最短路径长为46八、写一篇不少于1200字的课程论文（30分）对运筹学的认识与体会在学习了近一个学期的运筹学后，我对运筹学有了一个最基本的认识。何谓“运筹学”？它的英文名称是OperationsResearch,直译为“作业研究”，就是研究在经营管理活动中如何行动，如何以尽可能小的代价，获取尽可能好的结果，即所谓“最优化”问题。汉语是世界上最丰富的语言，中国学者把这门学科意译为“运筹学”，就是取自古语“运筹于帷幄之中，决胜于千里之外”，其意为运算筹划，出谋献策，以最佳策略取胜。这就极为恰当地概括了这门学科的精髓。经过这一个学期的学习，我们应该熟练地掌握、运用运筹学的精髓，用运筹学的思维思考问题，即：应用分析、试验、量化的方法，对实际生活中的人力、财力、物力等有限资源进行合理的统筹安排。我大致归纳了一下本学期所学运筹学的基本内容，也算是对这个学期课程的一个总结吧。首先，运筹学主要可以分为一下几个部分。一、线性规划线性规划解决的是：在资源有限的条件下，为达到预期目标最优，而寻找资源消耗最少的方案。而线性规划问题指的是在一组线性等式