0910运筹学(清考)

浙江工业大学09/10学年 第一学期期终试卷清考卷 （考试类型：闭卷） 课程 （管理）运 筹 学 姓名 班级 学号 序 一 二 三 四 五 六 七 总评 计分 一、判断题（对者打√，错者打×，每小题2分，共10分） 1. 用单纯形法求解极大化标准形的线性规划问题时，与 对应的变量都可以被选作入基变量。 （ ） 2. 如果线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。 （ ） 3. 在运输问题中，每次迭代时，如果有某非基变量的检验数等于零，则该运输问题无最优解。 （ ） 4. 在目标规划中，正偏差变量应取正值，负偏差变量应取负值。 （ ） 5. 任何求最小目标函数值的纯整数规划的最小目标函数值小于或者等于相应的线性规划的最小目标函数值。 （ ） 二、选择题（每小题2分，共10分） 1. 在产销平衡的运输问题中，设产地为m个，销地为n个，那么最优解中非零变量的个数为： （ ） A．不能大于(m+n-1)； B．不能小于(m+n-1)； C．等于(m+n-1)； D．不确定。  2. 求极大值的线性规划问题中，下列结论是正确的是： （ ） A．可行解就是基本解； B．基变量的值为非负时的基本解为基本可行解； C．有可行解必有最优解； D．基变量的检验数可能为零，也可能不为零。 3. 在目标规划中，求解的基本原则是首先满足高级别的目标，但当高级别目标不能满足时： （ ） A．其后的所有低级别目标一定不能被满足； B．其后的所有低级别目标一定能被满足； C．其后的某些低级别目标一定不能被满足； D．其后的某些低级别目标有可能被满足。 4. 在图与网络中，下列结论不正确的是： （ ） A．在任一图G中当点集v确定后，树图是G中边数最少的联通图； B．最大流问题是一种特殊的线性规划问题； C．若无向图G有k个顶点，k-1条边，则G一定是树图； D．求最短路问题可以归结为求整数规划问题。 5. 某人要从上海乘飞机到奥地利首都维也纳，他希望选择一条航线，经过转机，使他在空中飞行的时间尽可能短。该问题可转化为： （　 　） A．最短路线问题求解 B．最大流量问题求解 C．最小生成树问题求解 D．统筹问题求解 三、已知某项工程的各道工序顺序及用时如图所示（单位：天），其中弧的上方 为各工序的代号，下方为完成此工序所需的时间。（共10分） （1）试求下列工序的最早开始时间，最迟开始时间，最早完成时间及最迟完成时间，并求出该工序的时差，填入下表。 工序 最早开始时间(ES) 最迟开始时间(LS) 最早完成时间(EF) 最迟完成时间(LF) 时差 c e h i （2）试求完成此工程所需的最少时间，并列出该项工程的关键工序。 四、已知线性规划问题: （共15分）   (1)将上述线性规划问题变换为标准型；  (2)用单纯形求解该线性规划问题，填满下表。    基 CB b 比值 cj-zj 1 0 [3] 0 1 0 1 0 0 0 1/2 -1 0 0 1 4 6 6 4 － 2 cj-zj 3 0 0 -5/2 0 0 0 1/3 -1/3 2 0 1 1/2 0 6 1 0 cj-zj 0 0   (3) 写出该线性规划的最优解和最优目标函数值。  五、某城市建设了一个从湖中（V1）抽水到城市的蓄水池（V8）的管道系统， 如图所示。试求由湖到蓄水池的最大流量。（共10分） (提示：无需图上标注，但要写出每次找到的可增广链及可调整值) 六、某防疫站每年需用某种疫苗1500支，每次订购费50元，每月补充速度 为2500支，每支每月的保管费为1.25元，每支每月缺货费为2元。 （1）该防疫站为把成本降到最低，每次的生产量和间隔时间为多少； （2）其他条件不变，如不允许缺货，每次的生产量和间隔时间为多少； （3）试比较上述两种情况下，防疫站的最低月总成本何时更低？ 并理由。（共10分） 七、已知运输问题的供需关系表与单位运价。（共20分） (1) 以最小元素法确定初始基本可行解,并以闭回路法判别； 销地 产地 B1 B2 B3 B4 产量 A1 5 7 3 12 35 A2 12 8 25 20 30 A3 15 18 11 10 35 销量 10 15 45 30 (2) 求该运输问题的最优解,并以闭回路法判别； 销地 产地 B1 B2 B3 B4 产量 A1 5 7 3 12 35 A2 12 8 25 20 30 A3 15 18 11 10 35 销量 10 15 45 30 (3) 由于市场变化，经研究制定新的运输时要考虑以下目标。 第一优先级：总运费不超过1300元。 第二优先级：第B3销地为重要市场，必须满足其需要； 第三优先级：供应B4销地的产品中，工厂A1的产品控制在20个单位； 第四优先级：为兼顾一般，至少满足B1和B2销地需求率的80%； 第五优先级：工厂A3的不得超负荷生产； 试建立该目标规划问题的数学模型（不需要求解）。 提示：设xij表示从产地Ai运输到销地Bj的运输量（i=1,2,3;j=1,2,3,4）， 如x12表示从A1运输到B2的物品数量。 八、某公司职员因工作需要购买了一台摩托车，4年内他可以连续使用或于任一 年末卖掉旧车，购买新的。已知于j年初购置一台新摩托车的价格和不同役 龄摩托车的处理价格如表所示。又新摩托车第一年运行及维修费为0.2万 元，使用1－3年后机器每年的运行及维修费用分别为0.6，0.9，1.1万元。 试据此确定该人最优的更新策略，使4年内用于摩托车的更换、购买及运行 维修的总费用为最省。（共15分） 单位：万元 J 第一年 第二年 第三年 第四年 年初购置价 1.5 1.6 1.9 2.3 使用j年后的处理价 1.1 0.8 0.6 0.4 （1）将该摩托车更新问题转化为最短路问题，填写权数表： 单位：万元 v1 V2 v3 v4 v5 v1 － v2 － － v3 － － － v4 － － － － （2）画出最短路问题的图示，以Dijkstra法求最短路，并确定最优的更新策略。 （提示：注意Dijkstra法的计算步骤） f 20 25 10 d 15 20 g i 30 7 j 10 h c e 40 b 20 a 5 8 6 4 3 2 1 15 V8 (9,6) V1 V2 V4 V7 V3 V5 V6 (4,3) (10,5) (3,3) (9,9) (11,3) (12,8) (10,8) (6,4) (9,4) (6,1) (4,2) (4,0) _1230317026.unknown _1230297374.unknown