河 北 工 业 大 学 期 末 考 试 试 卷
2010 年 春 季学期
课程名称 学院名称 题号 分数 阅卷人 一 运筹学 管理学院 二 三 四 适用专业 班级 五 六 七 八 管理学院各专业 A/ B 卷 姓名 九 十 十一 A 开/闭卷 学号 十二 总分 闭卷
一、填空题（每小题 3 分，共 15 分） 1. 用单纯形法求解线性规划问题时，单纯形表中的每个解对应的是线性规划问题的一个 法中其 题的解总是 一一对应。 。
，与图解
2. 在对偶单纯形法中，确定换入变量时采用的是最小比值规则（θ规则） ，采用该规则的主要目的是保证对偶问 3. 用表上作业法（运输单纯形法）解运输规划模型时，作业表应满足的两个基本条件是 4. 在动态规划模型中， 状态变量表示每个阶段 特性。 5. 若解整数规划的单纯形表的最终表中有约束行为： x 1 方程为 。
5、 用标号法寻找网络最大流时，发生标号中断（没有增广链） ，这时若用 V 表示已标号的节点的集合，用 V 表示 未标号的节点集合，则在网络中所有 V → V 方向上的弧有 A、 f c B、 f c C、 f c D、 f 0 。 （f 为当前流，c 为弧的容量）
第 1页，共 4页
max z 3 x1 2 x2 2 x1 3 x2 14 2 x1 x2 9 x 0, x 0 2 1
（1）求 c1 的变化范围以使最优解保持不变。 （2）现在市场上原材料 B 的价格为 1 元，问是否需要买入原材料 B，为什么？ （3）如果需要买入原材料 B，最多买入多少？
1 2 8 x 3 x 4 ，其中 x1 为基变量，则其对应的割平面 4 5 3
。 的
时所处的自然状况或客观条件， 它要满足
二、单项选择题（每题 3 分，共 15 分） 1、 下面哪一个表达式可以作为目标规划的目标函数 A、 min d 1 d 1 C、 min d 1 d 1
工序 A B C E
紧前 工序 — A A B,C
作业 时间 3 4 5 9
工序 F G I J
紧前 工序 C C G E,F,I
作业 时间 8 4 3 2
第 4页，共 4页
（1） 写出其对偶问题。 （2） 其原问题的最优解为 x1 5, x2 0, x3 1 ，根据对偶性质直接求解对偶问题的最优解。
四、 （共 20 分，其中第 1、3 问各 7 分，第 2 问 6 分） 某厂用两种原材料生产两种产品，已知数据见表 1，根据该 表列出的数学模型如下，加松弛变量，并用单纯形法求解得最终单纯形表见表 2 表 1： 产品 I 产品 II 原材料 A（kg/件） 原材料 B（kg/件） 收入（元 / 件） 2 2 3 3 1 2 资源限制 14 9 表 2： CB 2 3 XB x2 x1 cj – zj b 5/2 13/4 x1 0 1 0 x2 1 0 0 x3 1/2 -1/4 -1/4 x4 -1/2 3/4 -5/4



B、 max d 1 d 1 D、 max d 1 d 1


。 D、基本解


2、 线性规划问题可行域的每一个顶点，对应的是一个 A、基本可行解 B、非可行解 C、最优解
3、 在整数规划割平面方法最终单纯形表中得到的一个各变量之间关系式为 x1 方程为 。 1 1 3 A、 x 2 x3 5 4 5
第 3页，共 4页
河 北 工 业 大 学 期 末 考 试 试 卷
2010 年 春 季学期
学院名称： 管理学院 班级名称： 姓名： 学号：
六、 （20 分） 已知下列工程项目资料 要求： （1）绘制网络图； （2）计算事项时间参数 （3）确定关键路线 （第 1、2 问各 7 分，第 3 问 6 分）
4 1 8 x 2 x3 ， 则其确定的割平面 5 4 5
1 3 3 B、 x 2 x3 5 4 5
1 1 3 C、 x 2 x3 3 5 4 5
。
4、 已知某个含 10 个节点的树，其中 9 个节点的次为 1，1，3，1，1，1，3，1，3，另一个节点的次为 A、1 B、4 C、3 D、2
河 北 工 业 大 学 期 末 考 试 试 卷
2010 年 春 季学期
学院名称： 管理学院 班级名称： 姓名： 学号：
三、已知线性规划问题（第一问 8 分，第二问 7 分，共 15 分）
min z 2 x1 x 2 2 x 3 x1 x 2 x 3 4 x1 x 2 x 3 6 x 0, x 0, x 无约束 2 3 1
第 2页，共 4页
河 北 工 业 大 学 期 末 考 试 试 卷
2010 年 春 季学期
学院名称： 管理学院 班级名称： 姓名： 学号：
五、某公司打算在甲乙丙三个地区共建立四个分销点，根据销售部门预测，在不同地区设置不同数量的销售点， 每 月可获得利润如下表，问应如何在各地区配置销售点以使每月总收入最大（要求用动态规划求解） 。 （共 15 分， 其中模型表达、过程推演和求解结果各占 5 分） 销售点数 收益 （万元） 甲 乙 丙 0 0 0 0 1 16 12 10 2 25 17 14 3 30 20 16 4 32 22 17