发布时间 : 星期四 文章《运筹学》期末考试试卷更新完毕开始阅读
《运筹学》期末考试试卷(A)
学院 班级 姓名 学号
题号 得分 一 二 三 四 五 六 七 八 九 总分 一、不定项选择题(每小题2分，共6分) 1．线性规划的标准型有特点（ ）。
A、右端项非零； B、目标求最大； C、有等式或不等式约束； D、变量均非负。
2．一个线性规划问题（P）与它的对偶问题（D）有关系（ ）。
A、（P）无可行解则（D）一定无可行解； B、（P）、（D）均有可行解则都有最优解；
C、（P）的约束均为等式，则（D）的所有变量均无非负限制； D、若（D）是（P）的对偶问题，则（P）是（D）的对偶问题。 3．关于动态规划问题的下列命题中（ ）是错误的。
A、动态规划阶段的顺序与求解过程无关；B、状态是由决策确定的； C、用逆序法求解动态规划问题的重要基础之一是最优性原理； D、列表法是求解某些离散变量动态规划问题的有效方法。 二、判断题（每小题1分，共5分）
1．若某种资源的影子价格等于k，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k个单位。 （ ）
2．如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化。 （ ）
3．运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有唯一
试卷A 共（4）页 第（1）页
最优解，有无穷多最优解，无界解，无可行解。 （ ）
4．用割平面法求解纯整数规划问题时，要求包括松弛变量在内的全部变量必须取整数值。 （ ）
5．如图中某点vi有若干个相邻点，与其距离最远的相邻点为vj，则边[i,j]必不包含在最小支撑树内。 （ ） 三(20分)、考虑下列线性规划：
maxz?3x1?5x2?x3?4x1?2x2?x3?14 ?? x1? x2?x3?4?x?0,j?1,2,3?j其最优单纯形表为：
CB 0 5 XB b? 6 4 -20 x1 2 1 -2 x2 0 1 0 x3 -1 1 -4 x4 1 0 0 x5 -2 1 -5 x4 x2 -Z 1(10分)、写出此线性规划的最优解、最优值； 2(2分)、求线性规划的对偶问题的最优解；
3(4分)、试求c2在什么范围内，此线性规划的最优解不变； 4(4分)、若b1?14变为9，最优解及最优值是什么？ 四（10分）、下述线性规划问题 ：
maxz?10x1?24x2?20x3?20x4?25x5?x1?x2?2x3?3x4?5x5?19??2x1?4x2?3x3?2x4?x5?57?x?0,j?1,2,?,5?j以y1,y2为对偶变量写出其对偶问题。
五(14分)、某公司下属的2个分厂A1、A2生产质量相同的工艺品，要运输到B1、B2、B3，3个销售点，分厂产量、销售点销量、单位物品的运费数据如下表：
试卷A 共（4）页 第（2）页
A1 A2 销量 B1 23 18 20 B2 11 16 10 B3 20 17 20 产量 25 25 用伏格尔法给出近似最优解。 六（10分）、已知目标规划模型为：
??minz?p1d1??p2(d2?d2)?p3d3??10?2x1?x2????x1?x2?d1?d1?0????x1?2x2?d2?d2?12????x?x?d?d?81233??x1,x2,di?,di??0,i?1,2,3?试用图解法求满意解。
七(15分)、有甲、乙、丙、丁四个人，要分别指派他们完成A、B、C、D不同的工作，每人做各项工作所消耗的时间如下表所示：
甲 乙 丙 丁 A 7 13 15 11 B 9 12 16 12 C 10 15 14 15 D 12 17 15 16 问：应该如何指派，才能使总的消耗时间为最少？
八（10分）、某公司生产三种产品，各产品的重量和利润关系如下：
产品 重量（t） 利润（元） Ⅰ 4 8 Ⅱ 5 11 Ⅲ 6 13 现将三种产品运往市场出售，运输能力为总重量不超过10t，如何安排运输使总利润最大。试建立此问题的动态规划模型（只建模，不求解）。
试卷A 共（4）页 第（3）页
九(10分)、下图为一网络，网络中每条弧上的数字为该条弧的（容量，流量）。
v 2 (9,5) (6,3) v 5 (7,5) (3,3) (5,2) (4,1) (3,2) (3,2) v 1 v 4 v 7 (1,1) (5,1) (7,3) v 3 (4,0) v 6
1(6分)、求该网络的最大流和最大流量；
2(4分)、若想增加网络的最大流量，首先应改善哪些瓶颈弧的容量？
试卷A 共（4）页 第（4）页