2010级《运筹学》课程试题（A卷）
题号 分数 一 二 三 四 五 六 七 总分 合分人： 复查人：
一、填空题：（共17分）
分数 评卷人 1、（2分）用大M法求解目标函数极大化的线性规划问题，引入的人工变量在目标函数中的系数为 。
2、（2分）若X*是线性规划问题maxzmaxz?C?CX,AX?b,X?0的最优解。则问题
? X,AX??b,X?0（??0且为常数)的最优解为 。3、（3分）用表上作业法求解运输问题时，常用的三种确定初始基可行解的方法为 法、 法和 法。 4、（2分）用分支定界法求解极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的 。
5、（2分）某工程公司拟从四个项目中选择若干项目，若令：
?1, 第i个项目被选中xi?? 第i 个项目未被选中i?1,2,3,4 ?0，用xi的线性表达式表示下列要求：
（1）只有项目2被选中，项目4才能被选中： ；
（2）如果项目1和项目2同时被选中，则项目3不能被选中： 。 6、（2分）无向连通图G是欧拉图的充分必要条件是 。 7、（4分）锅炉房到5座大楼铺设暖气管道，可以选择的铺设路径及路径长度如下图所示（单位：米），使得所有楼都能供上暖的最短管道铺设长度为 米。
共 9 页 第 1 页
二、多项选择题（每题3分，共18分）
1、原问题有可行解，则其对偶问题（ ）。
分数 评卷人 A．可能有唯一最优解 B．可能有无穷多最优解
C．可能为无界解 D．可能为无可行解
2、对于有m个产地n个需求地的产销平衡的运输问题的数学模型，下列说法正确的是（ ）。
A．变量的个数为m×n个
B．约束条件的个数为m×n个
C．一定有有限最优解 D．基可行解中基变量的个数为m+n个
3、对于目标规划问题的数学模型，下列说法正确的是（ ）。
A．正偏差变量和负偏差变量都大于等于零
B．约束条件中必须同时包含绝对约束和目标约束
C．若某满意解不满足P3的目标，则其一定不满足优先级低于P3的所有目标 D．用图解法求解有权系数的目标规划模型时，可能会出现错误 4、关于整数规划问题，下列说法正确的是（ ）。
A．求极大化的整数规划问题最优解的目标函数值一定大于等于其对应的松弛问题最优解的目标函数值
B．用割平面法求解纯整数规划问题时，要求包括松弛变量在内的全部变量必须取整数值
C．分支定界法既可以求解纯整数规划问题，也可以求解混合整数规划问题 D．匈牙利算法是一种求解指派问题的方法 5、关于动态规划问题，下列说法正确的是（ ）。
A．本阶段的状态是由上一阶段的状态和上一阶段的决策确定的
B．用逆序法求解动态规划问题的重要基础之一是最优性原理 C．同一个问题用顺序法和逆序法求解的结果可能不同 D．列表法是求解某些离散变量动态规划问题的有效方法 6、下列方法中哪些是求解网络中两点间最短路的方法（ ）。
A．避圈法 B．Dijkstra法
C．Floyd法 D．逐次逼近法
共 9 页 第 2 页
二、建模题（共7分）
分数 评卷人 某电子公司制造A，B，C三种产品，它们都在同一生产线上进行制造、装配及检验。三种产品每部在生产过程中所消耗的时间分别为5小时，8小时，12小时。生产线每月正常运转时间是170小时。这三种产品每部的利润：A为100（千元），B为144（千元），C为252（千元）。该公司确定的经营目标为：
P1：充分利用生产线的工时；
P2：为满足客户的要求，A，B，C的产量分别不少于5、5、8部，并依产品单位工时的利润比例确定权系数；
P3：生产线的加班时间每月不宜超过16小时。 试建立该问题的目标规划模型。
共 9 页 第 3 页
三、计算题（共58分）
1、（共14分）
已知某生产计划问题的线性规划模型如下：
maxz?6x1?14x2?13x3
?124?x1?2x 2 ? x 3 ? 第一种资源约束
分数 评卷人 ?2? 4 x 60 第二种资源约束 3 ??x1?2x2 ? xj?0,j?1,2,3
引入松弛变量x4，x5后，用单纯形法求得其最优单纯形表如下：
cj 6 14 13 0 0 CB 6 13 xB x1 b 36 6 x1 1 0 0 x2 6 -1 -9 x3 0 1 0 x4 4 -1 -11 x5 -1 1/2 -1/2 x3 cj?zj (1)第一种资源和第二种资源的影子价格分别为多少？ (2)分析下列情况单独发生的情况下，最优解的变化情况。 a.目标函数的系数c1由6变为4； b.约束条件右端项由?
共 9 页 第 4 页
?24??15?变为。 ????60??40?
相关推荐：
loading