运筹学试卷

开/闭卷 命题人(签字) 审题人(签字) 年 月 日 题号 得分 评卷人 学院 专业 姓名 学号 闭 卷

课程名称

运筹学

A/B卷 A 学分 3

课程编号 22040103、22040605

一 二 三 四 五 六 七 八 九 十 基本题总分 附加题 基本题（100分） 一、判断题：（每小题2分，本题共20分）

（1）基本可行解中的非零变量的个数小于约束条件数时，该问题可求得退化解（ ） （2）若xj是一个非基变量，则xj的检验数必定不是0。（ ） （3）如果运输问题单位运价表中的某一行（或某一列）元素分别乘上一个常数k，最

优调运方案将不会发生变化。（ ）

（4）求图的最小支撑树以及图中一点到另一点的最短路问题，都可以归结为求解整数

规划问题。（ ）

（5）用分枝定界法求解一个极大化的整数规划问题，当得到多于一个可行解时，通常

可任取其中一个作为下界，再进行比较剪枝。（ ） （6）在报童问题中,报童每天总的损失期望值为报纸售剩而遭到的损失期望值与因失去

销售机会而少赚钱的损失期望值之和（ ） （7）指派问题数学模型的形式与运输问题十分相似，故也可以用表上作业法求解。（ ） （8）若图T是树，则T中任意两点有唯一连相连。（ ）

（9）在其它费用不变的条件下，随着单位存贮费用的增加，最优订货批量也相应增大。

（ ）

（10）在大M法的目标函数中，人工变量的系数为任意大的正数M。（ ） 二、填空题（每空2分，本题共20分）

（1）下表给出运输问题的产销平衡表及运价： 销 地 运价（元/吨） 产地 _____________ ________ B1 B2 B3 产量（吨） A1 A2 销量（吨） 15 18 22 21 25 16 4 5 6 8 7 求使运费最小的方案可用 方法求解。首先用伏格尔法求初始调运方案，数字格为 ，此时，空格处的检验数为 ，再用 方法调整得最优方案为 ，最小运费为 。 《 运筹学 》试卷 A 卷 第 1 页 共 5 页

（2）指派问题属于 问题，可以用 方法求解，当任务数比人数少时，可以采取 方法处理。

（3）在图中找一条经过每边的最短路问题是 。 三、（25分）某车间生产甲、乙、丙三种产品，每件所消耗劳动力、原料及可供使用资源

量如下表： 单位产品消耗资源量 产品甲 产品乙 产品乙 现有资源量 6 3 5 劳动力 45（单位） 3 4 5 原料 30（单位） 3 1 5 单位产品利润（元） （1） 用单纯形法确定使总利润达到最大的生产计划。 （2） 分别求出劳动力和原材料的影子价格。

（3） 若产品乙的单位利润变为2元，其它条件不变，原最优计划是否发生改变？ （4） 若原材料不够，可到市场上购买，市场价格为0.8元/单位,问是否要购进,最多

购进多少?

《 运筹学 》试卷 A 卷 第 2 页 共 5 页

四、（20分）最大流问题如下图所示，图中弧旁数字为容量，求下图网络中vs到vt的最大流量。要求：

（1）建立该问题的数学模型； （2）用标号法求解上述问题。（写出每条增广链及其调整流量、最小截集和总流量）

3 v2 14 v4 3vs 25 vt 1 25v1

v3

《 运筹学 》试卷 A 卷 第 3 页 共 5 页

五、（10分）给定目标规划问题：

minz2P1(d1d1)P2(d2d2)2x1x2d1d122x13x2d2d26st.x16x,x0,d,d0,(i1,2)ii12

用图解法找出该目标规划问题的满意解。

六、证明题（5分）

线性规划问题maxzCX,AXb,X0，设X0为问题的最优解。若目标函数中用C*代

替C后，问题的最优解变为X*，求证：

**0 (CC)(XX)0

《 运筹学 》试卷 A 卷 第 4 页 共 5 页

附加题（30分）

分析用位势法求检验数的问题： （1）、（10分）表述一般的运输问题，写出该运输问题的数学模型及其对偶问题的模型； （2）、（10分）证明对偶变量法（也称位势法）求检验数的合理性； （3）、（10分）结合本试题中基本题二（1）的运输问题，用位势法求初始表格中空格处

的检验数。

《 运筹学》试卷 A 卷第 5 页 共 5 页