运筹学习题2014

1、运筹学习题运筹学习题 2014 习题一习题一线性规划线性规划 l下面给出某线形规划的单纯形初表（表1）与 某一中间表（表2）（Min型） l填完初表1，并确定表中的出基变量为 _，进基变量为_。 l填完表2，该表是否是终表?_。 若是，最优值 _， 其最优基B-1=_ 。 l此线形规划对偶问题的最优解 _。 习题一习题一 l某市共分某市共分6个区，每个区都可设消防站，市政府希望设置消防个区，每个区都可设消防站，市政府希望设置消防 站最少以便节省费用，但必须保证在城市任何地方发生火警时，站最少以便节省费用，但必须保证在城市任何地方发生火警时， 消防车能在消防车能在15分钟内赶到现场，依据实地测定

2、，各区之间消防分钟内赶到现场，依据实地测定，各区之间消防 车行驶时间如下表，试建立该问题的规划模型。并用合适的方车行驶时间如下表，试建立该问题的规划模型。并用合适的方 法求出最优解。法求出最优解。 一区一区二区二区三区三区四区四区五区五区六区六区 一区一区 0 010101616282827272020 二区二区 0 02424323217171010 三区三区 0 0121227272121 四区四区 0 015152525 五区五区 0 01414 习题二习题二 l已知某运输问题的产销平衡表与单位运价表如 下表所示，试确定最优调运方案。 若若A2工厂某条生产线检修，使得生产量减少了工厂某条

3、生产线检修，使得生产量减少了30，但，但 是是B2地区的市场需求必须满足，应如何调运为最优？地区的市场需求必须满足，应如何调运为最优？ B1B1B2B2B3B3产量产量 A1A11010151517173030 A2A2232320202424100100 A3A33030171720207070 需求量需求量40401101105050 习题三习题三指派问题指派问题 l从甲乙丙丁戊五人中挑选四人去完成四项工作，已知每人完成各从甲乙丙丁戊五人中挑选四人去完成四项工作，已知每人完成各 项工作的时间如下表所示，规定每项工作只能由一个人去单独完项工作的时间如下表所示，规定每项工作只能由一个人去单独完

4、 成，每人最多承担一项工作，如何分配工作使完成四项工作总的成，每人最多承担一项工作，如何分配工作使完成四项工作总的 花费时间最少。花费时间最少。 甲甲乙乙丙丙丁丁戊戊 一一10129167 二二810151114 三三1321141715 四四121513108 若假定乙必须分配工作，戊因某种原因不同意承担第一项工作，若假定乙必须分配工作，戊因某种原因不同意承担第一项工作， 在满足上述条件下，应做何分派为最优？在满足上述条件下，应做何分派为最优？ 习题四习题四图论图论 l某县各村分布图如下，现有一医疗小分队被派某县各村分布图如下，现有一医疗小分队被派 往该县为每个村做义诊，且不在村里留宿，应往

5、该县为每个村做义诊，且不在村里留宿，应 如何有效的好安排此次行程？如何有效的好安排此次行程？ 一村一村二村二村三村三村四村四村五村五村六村六村 县城县城 3232-40402525- 一村一村 0 02020-2626- 二村二村 0 02222-2323 三村三村 0 01919-1818 四村四村 0 030302121 五村五村 0 01414 六村六村 0 0 若可留宿当地，有应如何安排行程？若可留宿当地，有应如何安排行程？ 习题五习题五最大流最大流 l某地区有3个城镇，各城镇每天产生的垃圾要 运往该地区的4个垃圾处理厂处理，假设各城 镇每日产生的垃圾量、各处理厂的日处理能力 及因道路

6、情况所能接受各区可供运垃圾的容量 （其中容量为0者表示无此直接道路），数据 如下表所示，试用网络流方法分析目前的道路 状况能否使所有垃圾都运到处理厂得到处理， 如果不能，应首先拓宽哪条道路，请画出相应 的网络图，并说明分析的过程。（可不具体求 解） 1234垃圾量垃圾量 1 2 3 30 0 10 0 0 0 20 40 50 40 20 50 50 70 80 处理量处理量60409030 习题六习题六最大流最大流 l下图网络弧上的数字为容量，括弧内的数字为 该弧的流量。 l在括号内填上适当的数字，使构成一个可行流。 l在下表中填出截集与截量。 l用标号法解此网络最大流，并指出最小截集。 、 1V 1V 11,VV11,VVC 习题七习题七关键路径与完工期关键路径与完工期 依据下列工程活动清单，绘制工程网络图，确定依据下列工程活动清单，绘制工程网络图，确定 期望工程与关键路径。并给出期望工程与关键路径。并给出DE两个工序的最早两个工序的