(完整版)北京交通大学942真题2010.doc

北京交通大学 942 管理运筹学 2010 年真题一.(24分)判断(正确的打“a错误的打 次”(1) 线性规划问题的每一个基解对应可行域的一个顶点；(2) 若x(1), ??2)分别是某一线性规划问题的 最优解，则 x=??1 ??(1)+?2???(2)也是该线性规划问题的最优解，其中 ?1?， ??2 为正的实数；( 3)已知 ?1?为线性规划的对偶问题的最优解， 若 ?1?>0，则说 明在最优生产计划中第 i 种资源已完全耗尽；( 4)整数规划问题最优解的目标函数值一定优于其相应的 线性规划问题最优解的目标函数值；( 5)指派问题效率矩阵的每个元素乘以同一大于 0 的常数k，将不影响最优指派方案；( 6)如果图 T 是树， 则 T 中一定存在两个顶点， 它们之间存 在两条不同的链；(7)任一图G=(V,E)都存在支撑子图和支撑树；( 8)网络图中任何一个结点都表示前一工序的结果和后一 工序的开始；( 9)结点最早时间同最迟时间相等的点连接的线路就是关键线路；( 10)假如到达排队系统的顾客为普阿松流，则依次到达的 两名顾客之间的时间间隔时间服从负指数分布；( 11)运输问题是一种特殊的线性规划模型，因而其求解结果也可能出现下列四种情况：唯一最优解，无穷多最优解， 无界解，无可行解；（12）单纯形法计算中，选取最大正检验数对应的变量作为 换入变量，将使目标函数得到最快的增长。

二．简答 （1）试简述求解整数规划模型的分支定界法剪枝的几种情 况；（ 6 分）（2）试写出标准指派问题的线性规划模型； （4 分）（3）试写出求解最短路径的 Dijkstra 算法的步骤； （ 6 分）（4）试写出 M/M/1 排队系统的 Little 公式4 分） 三（40分）某厂生产I，“，皿三种产品，其所需劳动力，原材料等 有关数据如下：每件产品I分别需要劳动力和原材料为 6小时和3公 斤，每件产品H分别需要劳动力和原材料为 3小时和4公斤，每件产 品皿分别需要劳动力和原材料为 5小时和5公斤；拥有的劳动力和 原材料总数分别为45小时和30公斤；又已知I, II,皿三种产品的 单件利润分别为 3,1,4 元要求：（1）写出该厂获利最大的生产计划问题的线性规划模型并求出最优解；（2）写出该线性规划问题的对偶问题,优解；并求对偶问题的最（3）产品I的利润在什么范围内变化时，上述最优计划不变;（4） 如果设一种新产品W,单件产品消耗劳动力 8小时， 原材料2公斤，每件可获利3元，问该产品是否值得 生产；（5） 如果劳动力数量不变，原材料可以从市场购买， 每公斤0.4元，问该厂是否购买原材料来扩大生产， 购买多少为宜？四（16分）某公司有甲，乙，丙三个工厂和 A, B，C三个客户，这 三个工厂在下一时期将分别生产某种产品 300,500和400件，公司计 划卖给客户A，B, C的产品数量分别是400,300,100件客户D想尽可 能多地购买剩下的产品。

各工厂卖给各客户单位产品利润如下表问 如何安排生产供应使该公司总利润最大？客户工厂ABCD甲15131214乙18171512丙1310910五.（20分）用动态规划方法求解下列整数规划问题:Max Z=4x〔 +7x2+&32?? + 3?? + 4?? < 8{??, ??, ?? > 0且为整数（要求写出动态规划模型的基本要素并求解）六（14分）.某理发店只有一个理发员，来理发的顾客到达 过程为 poisson 流，平均 5 人/ 小时；理发时间服从负指数 分布，平均需要 10分钟；店内有 5 把椅子供顾客等候， 多余 顾客将到其他理发店理发1)该理发店忙的概率2)该店内恰有 2 个顾客的概率3)在店内的平均顾客数4)每位顾客在该店内的平均逗留时间5)等待服务的平均顾客数6)每位顾客的平均等待时间7)顾客损失的概率七.(16分)下图中A, F分别表示陆地，而B, C, D, E分别表示河中的四个岛屿；1,2,3 分3别为顺序编号的十三座桥 假设河两岸分别为相互敌对的两只部队占领， 则至少要切断几座桥才 能达到阻止对方部队从桥上过河的目的 要求用图论的方法进行分析, 具体指出需要切断哪几座桥。