发布时间 : 星期日 文章2012级运筹学A卷更新完毕开始阅读9639d6fe87c24028905fc384
2012级《运筹学》课程试题（A卷）
题号 分数 一 二 三 四 五 六 七 总分 合分人： 复查人：
一、填空题：（共21分）
分数 评卷人 1、（4分）线性规划问题的解的类型有：唯一最优解、 、 和无可行解四种类型。运输问题是特殊的线性规划问题，它的解的类型有 。
2、（2分）若原问题无可行解，则对偶问题解的类型为 。 3、（3分）m个产地、n个销地的产销平衡的运输问题的变量个数为 个。求解运输问题初始基可行解的常用表上作业法主要包括西北角法、 、 和 三种。 4、（4分）如下目标规划问题：
minz=P1d1++P2d2_+P3d3+
用图解法进行求解，得到图形如下：
共 7 页 第 1 页
O x2 D ?d? +d3 l3 l2 B d?? E F l1 A C x1
该模型在 点取得满意解，该满意解满足了第 级目标，没有满足第 级目标。
5、（2分）对于求极大化的整数规划问题，若其松弛问题的最优单纯形表中有一行数据为：
XB x2 b 13/7 x1 0 x2 1 x3 11/7 x4 -20/7 则对应的割平面约束（或方程）为 。
6、（2分）用分支定界法求解极小化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的 。 7、（2分）用动态规划求解某生产计划问题。已知第一期期初库存为0，第五期期末库存也必须是0，每期的生产数量不大于5，决策变量xk表示第k期生产量，状态变量sk表示第k期初库存量，则状态变量s4的取值范围是 。（已知第1~5期市场对产品的需求量分别为2，4，3，4，4。）
8、（1分）Dijkstra算法和Floyd法都是求解最短路问题的算法。其中， 法适宜于求解图中任意两点之间的最短路。
9、（1分）一个有n个顶点的树图的边数为 。
二、建模题（共16分）
分数 评卷人 1、（7分）某省外贸局拟从下列应试者中招聘四名工作人员，希望所招四人平均业务能力评分最高，且满足下述要求：①专业不得相同；②女性最多不超过二人；③至少有一名精通日语者；④精通英语者最多入选一人。
编号 性别 专业 精通语种 业务能力评分 1 2 3 4 5 6 男 女 男 女 男 女 纺织 机械 化工 电子 机械 食品 英 英 德 法 日 日 95 93 87 87 83 73 试建立该问题的0-1规划模型（不求解）。
共 7 页 第 2 页
2、（9分）企业计划生产甲、乙两种产品， 这些产品需要使用两种材料， 要在两种不同设备上加工。工艺资料如下表所示。 产品 资源 材料Ⅰ 材料Ⅱ 设备A 设备B 产品利润（元） 产品甲 3 0 2 5 20 产品乙 0 4 2 3 40 现有资源 12（kg） 14（kg） 12（h） 15(h) 企业在安排生产计划时， 依次尽可能满足下列目标： P1：力求使利润指标不低于80元；
P2：考虑到市场需求， 甲、乙两种产品的生产量需相等； P3：设备A既要求充分利用，又尽可能不加班； P4：设备B加班时间尽可能少；
另外，考虑到材料购买困难，一定不能超用。 建立该生产计划问题的目标规划模型（不求解）。
三、计算题（共63分）
共 7 页 第 3 页
分数 评卷人 1、（共22分）
已知某生产计划问题（两种资源、三种产品）的线性规划模型如下：
maxz=4x1+x2+5x3
6x1+3x2+5x3≤452x1+4x2+5x3≤30 x1≥0,x2≥0引入松弛变量x4和x5，用单纯形法求得其最优单纯形表如下：
cj 4 1 5 0 0 CB 4 5 xB b 15/4 9/2 x1 1 0 0 x2 -1/4 9/10 -5/2 x3 0 1 0 x4 1/4 -1/10 -1/2 x5 -1/4 3/10 -1/2 x1 x3 cj?zj
(1)写出该线性规划的对偶问题,并写出对偶问题的最优解。
(2)目前单位产品一的利润为4，在其他条件不变的前提下，该利润在什么范围之内变化时，最优解不变？
(3)若有一种新产品丁，其原料消耗定额为：A为4单位，B为2单位，单位产品利润为2.5，问该种产品是否值得生产，并求出新的最优生产计划。
(4)若原材料A市场紧缺，除拥有量外一时无法购进，而原材料B若数量不足可从市场购买，单价为0.25，问：该厂是否购买该种资源？并说明理由。若购买，以购买多少为宜？
共 7 页 第 4 页