北京交通大学942真题2010

北京交通大学942管理运筹学2010年真题

一.(24分)判断（正确的打“√”错误的打“×”）

（1）线性规划问题的每一个基解对应可行域的一个顶点；（2）若x1，x2分别是某一线性规划问题的最优解，则x=λ1x1+λ2x2也是该线性规划问题的最优解，其中λ1，λ2为正的实数；

（3）已知y1?为线性规划的对偶问题的最优解，若y1?>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分）某厂生产Ⅰ，Ⅱ，Ⅲ三种产品，其所需劳动力，原材料等有关数据如下：每件产品Ⅰ分别需要劳动力和原材料为6小时和3公斤，每件产品Ⅱ分别需要劳动力和原材料为3小时和4公斤，每件产品Ⅲ分别需要劳动力和原材料为5小时和5公斤；拥有的劳动力和原材料总数分别为45小时和30公斤；又已知Ⅰ，Ⅱ，Ⅲ三种产品的单件利润分别为3,1,4元。

要求：

（1）写出该厂获利最大的生产计划问题的线性规划模型并求出最优解；

（2）写出该线性规划问题的对偶问题，并求对偶问题的最优解；

（3）产品Ⅰ的利润在什么范围内变化时，上述最优计划不

变；

（4）如果设一种新产品Ⅳ，单件产品消耗劳动力8小时，原材料2公斤，每件可获利3元，问该产品是否值得

生产；

（5）如果劳动力数量不变，原材料可以从市场购买，每公斤0.4元，问该厂是否购买原材料来扩大生产，购买

多少为宜？

四（16分）某公司有甲，乙，丙三个工厂和A，B，C三个客户，这三个工厂在下一时期将分别生产某种产品300,500和400件，公司计划卖给客户A，B，C的产品数量分别是400,300,100件客户D想尽可能多地购买剩下的产品。各工厂卖给各客户单位产品利润如下表。问如何安排生产供应使该公司总利润最大？

五．（20分）用动态规划方法求解下列整数规划问题：Max Z=4x1+7x2+8x3

2x1+3x2+4x3≤8

x1，x2，x3≥0且为整数

（要求写出动态规划模型的基本要素并求解）

六（14分）.某理发店只有一个理发员，来理发的顾客到达

过程为poisson流，平均5人/小时；理发时间服从负指数分布，平均需要10分钟；店内有5把椅子供顾客等候，多余顾客将到其他理发店理发。

（1）该理发店忙的概率

（2）该店内恰有2个顾客的概率

（3）在店内的平均顾客数

（4）每位顾客在该店内的平均逗留时间

（5）等待服务的平均顾客数

（6）每位顾客的平均等待时间

（7）顾客损失的概率

七．（16分）下图中A，F分别表示陆地，而B，C，D，E

分别表示河中的四个岛屿；1,2,3……13分别为顺序编号的十三座桥。

假设河两岸分别为相互敌对的两只部队占领，则至少要切断几座桥才能达到阻止对方部队从桥上过河的目的。要求用图论的方法进行分析，具体指出需要切断哪几座桥。