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

1、五邑大学 试 卷学期： 2014 至 2015 学年度第 1 学期 课程：高级运筹学任课教师（命题人）： 使用班级： 经管研2014 姓名： 学号： 题号一二三四五六七八总分得分一、构建下述问题的线性规划数学模型并用系统软件求解（10分）生产需要2.9米、2.1米和1.5米的元钢各100根，已知原材料的长度是7.4米，问应如何下料，才能使所消耗的原材料最省。说明利用的是什么软件，求解的结果和重要的截图。解：分析可得，每一根原材料的下料方案有如下几种：123456782.9211100002.1021032101.510130234余料0.10.30.901.10.20.81.4经分析可得，这是

2、一个线性规划问题，设按上述八种方案下料的原材料的根数分别为根，所需要的原材料的总根数为z根.数学模型如下：目标函数为： 且为整数这是一个线性规划问题，我用的软件lingo来解这道题，以下就是我用软件解这道题的重要步骤：1、打开lingo软件2、输入上述线性规划模型3、运行软件，结果如下由软件的运行结果可知，最优解如下，耗费原材料90根，其中按方案一下料的原材料为40根，按方案二下料的原材料为20根，按方案六下料的原材料为30根。二、用图解法求解下述线性规划问题（5分）解：由题意可得，以为坐标轴建立直角坐标系（1）根据约束条件画出与约束条件相应方程的直线，由这些直线共同确定出一个 区域，即可行解

3、的区域可行区域如下图所示：其中， Y2： Y3：其中阴影部分的每一个点都是这个线性规划问题的解。（2）再分析目标函数，在这个坐标平面上，它表示以z为参数、-5/3为斜率的一组平行线：，当z值由大变小时，直线沿其法线方向向上平移，如图所示：所以最后的最优解为三、用单纯形法求解下述线性规划问题（15分）解：（1）先将此线性规划问题化为标准形。引入松弛变量后将其化为标准形： 在该标准形中，约束条件的系数矩阵中不含有单位矩阵，加入人工变量，使得上式变为： （2）列出初始单纯性表，如下表所示：241000-M06 1111000604 11-201004 -M81-2100-1182+M4-2M1+M

4、0 0-M0此时得到的基本可行解为X=（0,0,0,6,4,0,8)（3） 继续进行迭代。如下表所示：241000-M02 0031-1002/324 11-20100_ -M40-330-1-114/3 0 2-3M5+3M 0 -2-M-M0(4)进行下一迭代。如下表所示：241000-M12/3 0011/3-1/300216/3 1102/31/300 -M20-30-10-11 0 2-3M 0-5/3-M -1/3-M0根据最优性解的条件，这个解是最优的，但在最优解中包括了一个人工变量,这说该问题没有可行解。所以此题无可行解。 四、已知如下产销量及运价表，求解此运输问题（15分）产

5、销量及运价表（元）销地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的了，即（

6、产地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

7、=-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

8、*90+16*110=9030（元）五、用隐枚举法求解下述0-1型整数规划问题（10分）解：（1）将模型转化为极小的问题 (2) 令，带入极小问题模型中得 (3)目标函数中变量按系数大小排列，约束条件中变量排列顺序也相应调整，得 (4) 按目标函数值由小到大的顺序排列可能的解，并予以可行性检验。计算表格如下：序号变量组合Z值是否满足约束条件是否可行条件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是停止最优解为（5）原问题的最优解为，Z=-1六、用动态规划求解下述非线性问题（10分）解：这个问题是将一个数9分

9、成三部分，使目标函数Z达到最大。取阶段变量k=1,2,3共分三个阶段。决策变量表示滴k个阶段分配的数量，状态变量表示从第k个阶段至第3个阶段可供分配的总数量，则状态转移方程为即 =9允许决策集合：，允许状态集合：，。递推方程为 当k=3时，有当k=2时，有令，则：再由，又由直接验证可知。 这时，当k=1时，有令，则，再令此时因为, 目标函数的最优解为七、用标号法求下图中点到其他各点的最短路（5分）解：如下图所示：下划线部分为永久标号，未画下划线的为临时标号。(1)（，13）（，12）(M，)(M，)(M，)(M，)（0,0）（，30）（，12）(2)（，39）(，30）(，24）(,24)（M

10、,)（，12）（，13）（0,0）（，30）（，12）(3)（，46）(，30）(，24）(,24)（，12）（，13）（0,0）所以，的最短路径为，最短路径长为12， 的最短路径为，最短路径长为12 的最短路径为，最短路径长为13 的最短路径为，最短路径长为30 的最短路径为，最短路径长为24 的最短路径为或，最短路径长为30 最短路径为,最短路径长为468、 写一篇不少于1200字的课程论文（30分） 对运筹学的认识与体会在学习了近一个学期的运筹学后，我对运筹学有了一个最基本的认识。何谓“运筹学”？它的英文名称是Operations Research,直译为“作业研究”，就是研究在经营管理

11、活动中如何行动，如何以尽可能小的代价，获取尽可能好的结果，即所谓“最优化”问题。汉语是世界上最丰富的语言，中国学者把这门学科意译为“运筹学”，就是取自古语“运筹于帷幄之中，决胜于千里之外”，其意为运算筹划，出谋献策，以最佳策略取胜。这就极为恰当地概括了这门学科的精髓。经过这一个学期的学习，我们应该熟练地掌握、运用运筹学的精髓，用运筹学的思维思考问题，即：应用分析、试验、量化的方法，对实际生活中的人力、财力、物力等有限资源进行合理的统筹安排。我大致归纳了一下本学期所学运筹学的基本内容，也算是对这个学期课程的一个总结吧。首先，运筹学主要可以分为一下几个部分。1、 线性规划线性规划解决的是：在资源有

12、限的条件下，为达到预期目标最优，而寻找资源消耗最少的方案。而线性规划问题指的是在一组线性等式或不等式的约束下，求解一个线性函数的最大或最小值的问题。其数学模型有目标函数和约束条件组成。解线性规划问题时，如果决策变量只有两个，那么我们通过用图解法就可以求出结果，但是当决策变量多于两个的时候，就不那么容易了，于是就引入了单纯形法这一解题方法，然后又衍生出来单纯形表这一简易方法。2、 运输问题 人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的生产量和需要量及各地之间的运输费用，如何制定一个运输方案，使总的运输费

13、用最小。这样的问题称为运输问题。运筹学问题也可以用单纯形法来求解，但是由于运输问题数学模型具有特殊的结构，存在一种比单纯形法更简单的计算方法表上作业法。运输问题中又分为产销平衡与产销不平衡两种情况，对于这两种情况本质上是一样的，产销不平衡也可以转化为产销平衡来求解。具体问题具体分析。 三、整数规划 整数规划是解决决策变量只能取整数的规划问题，一个规划问题中要求部分或全部决策变量是整数，则这个规划称为整数规划；当要求全部变量取整数值的，称为纯整数规划；只要求一部分变量取整数值的，称为混合整数规划。很多实际规划问题都属于整数规划问题。例如1.变量是人数、机器设备台数或产品件数等都要求是整数。2.人

14、员的合理安排问题。整数规划的解法有分支界定发和割平面法。另外在整数规划的特殊情况0-1规划问题中会用到的解决办法是完全枚举法和隐枚举法，当决策变量比较多时，我们往往会用隐枚举法解题。隐枚举法是李老师重点给我们讲述过的。 四、动态规划 动态规划是求解多阶段决策过程最优化的数学方法。1915年，美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段过程转化成一系列单阶段问题，逐个求解，创立了这类过程优化问题的新方法-动态规划。动态规划所研究的对象是多阶段决策问题。 五、网络模型 图论是交通系统分析中的重要工具，在交通系统规划、管理中作用巨大，也是对实

15、际交通网络进行抽象分析的重要手段。在网络模型这一章中我们主要学习了图论有关知识，学习了如何利用图来解决最小数问题、最短有向路问题、最大流问题与最小费用流问题。以上就是我对运筹学的一个大概的认识。对于运筹学很遗憾的我只看过两本书而已，一本是 老师编写的那本，还有一本是李成标编写的在清华大学出版社出版的运筹学，其余的我还没来得及看，想 老师推荐的英文原版文献我更是还没有看过，这一点觉得有点愧对老师。在这两本书中，印象最深刻的就是 老师的0-1规划中的隐枚举法，在清华大学的那本书中所举的例子，根本就不是隐枚举法，而是完全枚举法，这种类似的错误在很多参考书中均有出现。现在来谈一谈我对运筹学的最大收获。我所学的专业是系统工程，对于系统工程学是一门新兴的学科，我最大的收获就是知道运筹学竟然可以被运用到系统工程学中去，或者说运筹学也是系统工程的理论基础之一。系统工程学是的理论基础有着众多的理论基础，而运筹学是那其中不能割舍的一部分。在系统工程中，通常我们会先建立一个复杂的系统工程，然后通过分析这个复杂系统中各个要素的组成关系，来建立我们所需要的模型，最后对这个模型进行优化分析。这个模型可以是运筹学基本模型中的任何一个模型，如果我们不能很好的理解运筹学，那么可能建立这个模型就会有一定的困难。比如说运