2005学年《运筹学》试题A(1)汇总

1、、单项选择题 （102=20分）1 判断下面哪个模型不是线性规划模型（）B. minZ =龙+ 7航- X2+ 4x 0112.下列哪个关于线性规划最优解的描述是正确的（）A.线性规划问题的每一个基本解对应可行域的一个顶点；B.若分别为某一个线性规划问题的最优解，则也是该线性规划问题的最优解，其中为任意实数；C.每个线性规划问题的两条约束直线的交点都对应一个基本解；运筹学试题 A 切x, + 5 x3 b鬲 A0X、max Z = x + 2 x, +圧上.+ 5xys 6A, 0,禺2 0D. max Z- Xj + 2 x, -iX、D.每个线性规划问题的基本解一定是某两个约束直线方程的交

2、点；J、彳巧*吗-2 鬲工山3.已知某线性规划问题的约束为% 2 ,判断下列各点哪个是该线性规划问题的可行域的顶点（）A.X X= （1,10, 22, 14；B.X X= （3, -1, 7, 1；C.X X= （2, 4, 0, 7；D.X X= （3, 5, 1,1；4.若将原来求极小的线性规划问题转化为其对偶问题，下列说法正 确的是（）A.原问题第 i i 个变量，则转化后的第 i i 个约束条件类型为；B.原问题第 i i 个变量为自由变量，则转化后的第 i i 个约束条件类型为；C.原问题第 j j 个约束条件类型为，则转化后的第 j j 个变量为自由变量；D.原问题第 j j 个

3、约束条件类型为，则转化后的第 j j 个变量；5.线性规划问题min Z二3州 +5.V,2A, ；Bz i /f - I；CA i t ；D丄 $ p Z 丨.（16 分）用大 M 方法求解下面的线性规划问题:min Z - 3A, + Sx2齐+禺21斗 4- 2A; 4州 2 0. Jtj 20三、（18 分）某工厂生产 3 种产品 A, B, C,每种产品的单位利润为 4, 1, 5;而生产每件商品所需耗费的劳动力资源分别为 2,1, 3;而所需的原材料分别为 3,2, 5;而在一周内，劳动力资源取多为 性规划模型求得最优表如下表所示：30个单位, 原材料供应最多为60 个；建立线4

4、1 5 0 0b4151 1/2 3/2 1/2 00 1 1 2 E 600根据最优表回答下列问题：1. 要使得生产计划不改变，A 产品的单位利润的允许变动范围是什么？（4 分）2. 若增加一种产品，其利润为 6,所需的单位劳动力和原材料分别为 2 和5,则问是否要调整生产计划，若需调整，求修改方案；（6 分）3. 若每周的劳动力可以多提供 20 个，则是否要修改生产计划？若要修改，求修改方案（8 分）四、（16 分）现要在 5 个工人中确定出 4 个人来分别完成 4 项任务。每项任务只能由一个人来完成，而且每个人只能完成一项任务。每个工人完成每项任务所需的工时数如下表所示任务工人ABCDI

5、9437II4656III5475IVV10674试用运输模型和方法找出一个工作分配方案，使得总工时最少。五、（16 分）设某公司拟将五台设备分配给下属的甲、乙、丙三个工厂。各个 工厂获得设备后，可以为公司带来的盈利如下表所示：工厂设备台数甲乙丙000013542710639111141211125131113问：分配给各个工厂多少台设备，可以为公司带来盈利的总利润的总和最大六、（6 分）求下图的最小生成树:七、（8 分）一个理发店只有一个理发师，有三个空椅供等待理发的人使用。设顾客以泊松 流来到系统，平均每小时 5 人；理发师的理发时间服从负指数分布，平均一个 人需要 10 分钟。求系统各个

6、状态的发生概率以及系统的平均排队等待时间。答案一、单项选择题1. C 2. D 3. A 4. D 5. B 6. D 7. D 8. C 9. A 10. C解：将问题标准化得:.（4分）max ZF= - 3 - A/q显然系数矩阵中没有单位阵，故在第一个约束中增加一个人工变量得新问题（8 分）F 面用表格单纯形法求解该问题:M-3 M-5 -MM 0 00 -2 -3 0 3-Z3M.（14 分）此时人工变量，故有最优解，对应原问题的最优解为；最优值为 3。.（ 16 分）-3 -5 0 01-1 0 11/11 2 0 1 04/1-301 1 -1 0 10 1 1 1 -1斗解:1

7、.设此时 A 的利润变为为，由于为基变量，所以影响所有的检验数计算各个非基变量的检验数得= 5 - 3c, y 2Yd，要使生产计划不变，则要求所有检验数仍然非正，即有2.增加商品 D 后，最优表变为Jb4 1 5 0 0 64151 1/2 3/2 1/2 0 115/10151 1/2 1/2 1/2 115/8一0 1 -1 2 600 2_汕口 4 们 0），从而得咛3；（4分）415/21/2 1/4 5/4 1/4 -1/2 0615/21/2 1/4 1/4 1/4 1/2 10即生产计划调整为 生产 A 为 15/2, D 为 15/2,此时的利润为 75;（6 分）3.此时从

8、 30 变为 50如Tkf25计算-v2门，知需要调整生产计划，利用对偶单纯形方法计算:-3/2251 1/2 3/2 1/2 0151 1/2 1/2 3/2 1100-750 -3/2 -3/2 -5/2 -1 0比值4204/3 2/3 5/3 0 1/3010-2/3 -1/3 -1/3 1 -2/3Z800 -5/3 -5/3 0 -4/3四、解：将该问题转化为运输问题进行求解；将工人看作是产地，每个产地的产量 为 1（只能完成一件事情），将任务看成销地，每个销地的销量为1 （每件事情只能由一个工人来完成），将每个工人完成各种任务的所需的时间数看成各 产地和各销地之间的距离或者单位运

9、输成本，则原问题转化为运输问题。. .（4 分）总产量”为 5，总销量”为 4,所以是产大于销的问题。需虚拟一个销地E，其销量为 1,且 E 与各产地之间的距离为 0. . （6 分）用最小元素法和闭回路法求得的最优表为ABCDE4/3所以计划调整为生产A 为 20,此时的利润为 80（8分）I00100II10III01IV00V00.（6 分）即，应由 I 完成 C, II 完成 A, III 完成 B,完成所有任务的最少时间为 3+4+4+3= 14五、 解：把 5 台设备分配给 3 各工厂可以以次分为三个阶段（k= 1, 2, 3）。设每个阶段初尚未分配出的设备数目为状态变量，记为，显

10、然；设相应工厂分配的设备数为决策变量，记为，显然；（2 分）则有状态转移方程：; . .（2 分）效应函数为：4 也网）见题中表格；伽）诃血（心讣基本方程为：时-；.（2 分）逆序求解最优值集与最优决策集:0 000 000 100 01IV 完成 D，V 不参加；其最优值即.（2 分）（可）=op仏（坷也）| 时，由于 ：，所以，显然此时 为的单调增函数，1:有下列元素：（0） = 0.0,（0）- 0；（1） = 4,叭（1=1；4（2） = 6,冬（2） = 2;如11哲=3;（町=】2,UJ4） = 4;（5）-13,UJ5）- 5;（两）=0忙也J+（电），一时，因此 为A(0) =

11、 max 0 + 0 = 0,0+ A|0+4maxi - max5+如）0+ (2)0 + 6/ (2) = max * 5+ KO)卜=max 5+4 I10+ (0)10 + 0o+o+ W)W)o+lllo+lll5+ A5+6/(3) = max=wax卜io+ A（】）叭4|n+他iiii + +o|o|(0+ z；(4)0+125+5 + 11 (4) = max * H) + /；(2)* = muxm10 + 6H+&111 + 41 1 + /；(o)1(0) = 0;吐M 1；3(2) = 2;2(3) 2;w3(4) = 1,2;二= 10.=1&*=1

12、4,(6 分)顺序求最优路线和最优决策：最优路线为：I 亠 T； L；或者因此，最优的分配方案为 甲厂 0 台，乙厂 2 台，丙厂 3 台；或者，甲厂 2 台，乙厂 2 台，丙厂 1 台。六、哄W)(0 + B 11 15+ 5+12()+ f；(3)110+11-mux J11+ (2)111 + 611+ 4hi + 4】+(0)111*0卜二21、w.(5) - 2;化(5 _ mnx0+ (5)0+213+ (4)3 + 167+百7 + 14 = mux9+ f(2)9 + 1012+ r(i)12 + 513+ Z：(0)1】3 + j(=max2111(5) =0.2; 时,$ （歼 2 2 0 0 卩他（內如+g g） ，