运筹学习题2014课件.pptVIP

运筹学习题 2014 习题一——线性规划 下面给出某线形规划的单纯形初表（表1）与某一中间表（表2）（Min型） 填完初表1，并确定表中的出基变量为__________，进基变量为_________。 填完表2，该表是否是终表?_________。 若是，最优值 ________， 其最优基B-1=_________ 。 此线形规划对偶问题的最优解 _______。 习题一 某市共分6个区，每个区都可设消防站，市政府希望设置消防站最少以便节省费用，但必须保证在城市任何地方发生火警时，消防车能在15分钟内赶到现场，依据实地测定，各区之间消防车行驶时间如下表，试建立该问题的规划模型。并用合适的方法求出最优解。 一区 二区 三区 四区 五区 六区 一区 0 10 16 28 27 20 二区 0 24 32 17 10 三区 0 12 27 21 四区 0 15 25 五区 0 14 习题二 已知某运输问题的产销平衡表与单位运价表如下表所示，试确定最优调运方案。 若A2工厂某条生产线检修，使得生产量减少了30，但是B2地区的市场需求必须满足，应如何调运为最优？ B1 B2 B3 产量 A1 10 15 17 30 A2 23 20 24 100 A3 30 17 20 70 需求量 40 110 50 习题三——指派问题 从甲乙丙丁戊五人中挑选四人去完成四项工作，已知每人完成各项工作的时间如下表所示，规定每项工作只能由一个人去单独完成，每人最多承担一项工作，如何分配工作使完成四项工作总的花费时间最少。 甲 乙 丙 丁 戊 一 10 12 9 16 7 二 8 10 15 11 14 三 13 21 14 17 15 四 12 15 13 10 8 若假定乙必须分配工作，戊因某种原因不同意承担第一项工作，在满足上述条件下，应做何分派为最优？ 习题四——图论 某县各村分布图如下，现有一医疗小分队被派往该县为每个村做义诊，且不在村里留宿，应如何有效的好安排此次行程？ 一村 二村 三村 四村 五村 六村 县城 32 -- 40 25 -- -- 一村 0 20 -- -- 26 -- 二村 0 22 -- -- 23 三村 0 19 -- 18 四村 0 30 21 五村 0 14 六村 0 若可留宿当地，有应如何安排行程？ 习题五——最大流 某地区有3个城镇，各城镇每天产生的垃圾要运往该地区的4个垃圾处理厂处理，假设各城镇每日产生的垃圾量、各处理厂的日处理能力及因道路情况所能接受各区可供运垃圾的容量（其中容量为0者表示无此直接道路），数据如下表所示，试用网络流方法分析目前的道路状况能否使所有垃圾都运到处理厂得到处理，如果不能，应首先拓宽哪条道路，请画出相应的网络图，并说明分析的过程。（可不具体求解） ? 1 2 3 4 垃圾量 1 2 3 30 0 10 0 0 0 20 40 50 40 20 50 50 70 80 处理量 60 40 90 30 ? 习题六——最大流 下图网络弧上的数字为容量，括弧内的数字为该弧的流量。 在括号内填上适当的数字，使构成一个可行流。 在下表中填出截集与截量。 用标号法解此网络最大流，并指出最小截集。 ①、②、③ ④、⑤、⑥ ? ? 习题七——关键路径与完工期 依据下列工程活动清单，绘制工程网络图，确定期望工程与关键路径。并给出DE两个工序的最早开始时间ES与最迟完成时间LF，以及总时差TF。 工序 紧前工序 活动时间 A --- 2 B --- 5 C A 4 D B 7 E B 6 F CD 8 G D 5 H DE 4