试题四 试题代码:453试题名称:运筹学 考生注意 1.本试题共七题,共3页,请考生认真检查 2.请务必将答案写在答卷纸上,写在试卷上的谷案无效 题得签 号分字 总分 对约束条件(20分) +xs+ -17 x3 2 +x6+3x 7 x≥0j=1,…,7 说明解Ⅹ=(1,2,1,0.0,0,0)ˉ是不是基可行解,假定不是,试找出一个基可行解 、已知线性规划问题(20分) minz=2x1-x2+ 2x3 x3=4 x1+x2-kx2≤6 XI 其最优解为x1=-5,x2=0,x3=-1 1.求k的值 2.求出对偶问题的最优解 三、已知某运输问题的产销平衡表与单位运价表如下表所示(25分) B B B 10 B50 20 20 50 销量 l15 1.求最优调拨方案; 2.如产地A3的产量变为130,又B2地区需要的115单位必须满足,试重新确定最优调 拨方案 四、塞尔默公司的营销经理将要主持召开一年一度的由营销区域经理以及销售人员参加的销 售协商会议。为了更好地安排这次会议,他雇佣了四个临时工(安、伊恩、琼、肖恩),每 个人负责完成下面的一项任务:1.书面陈述的文字处理:2制作口头和书面陈述的电脑图 3会议材料的准备,包括书面材料的抄写和组织;4处理与会者的提前和当场注册报名。虽 然这四个临时工都有完成这四项任务所需的基本能力,但是在他们完成每一项任务时所表现 出来的有效程度是有很大差异的。表1显示了每一个人完成每一项任务所用的时间(单位 小时)。试问营销经理应该将哪一项任务指派给哪一个人,才能使总时间最小?(20分) 表1塞尔默公司问题中的有关数据 文字处理制作电脑 材料准
试题四 试题代码：453 试题名称：运筹学 考生注意∶ １．本试题共 七 题，共 3 页，请考生认真检查； ２．请务必将答案写在答卷纸上，写在试卷上的答案无效。 题号 一 二 三 四 五 六 七 总分 得分 签字 一、对约束条件（20 分） − − − + + = − − − + + = − − − − + = − = x x x x x x x x x x x x x x j j 1 2 3 5 6 3 4 6 7 1 2 4 7 4 8 17 2 2 3 2 4 10 2 9 0 1,,7 说明解 X=（1,2,1,0,0,0,0）T是不是基可行解，假定不是，试找出一个基可行解。 二、已知线性规划问题（20 分） 0, 0 6 4 m 2 2 1 2 1 2 3 1 2 3 1 2 3 − + − − + + = = − + x x x x kx x x x inz x x x 其最优解为 x x x 1 = −5 , 2 = 0 , 3 = −1 1．求 k 的值； 2．求出对偶问题的最优解 三、已知某运输问题的产销平衡表与单位运价表如下表所示（25 分） Ai Bj B1 B2 B3 B4 B5 产量 A1 10 15 20 20 40 50 A2 20 40 15 30 30 100 A3 30 35 40 55 25 150 销量 25 115 60 30 70 1．求最优调拨方案； 2．如产地 A3 的产量变为 130，又 B2 地区需要的 115 单位必须满足，试重新确定最优调 拨方案 四、塞尔默公司的营销经理将要主持召开一年一度的由营销区域经理以及销售人员参加的销 售协商会议。为了更好地安排这次会议，他雇佣了四个临时工（安、伊恩、琼、肖恩），每 一个人负责完成下面的一项任务：1.书面陈述的文字处理；2.制作口头和书面陈述的电脑图； 3.会议材料的准备，包括书面材料的抄写和组织；4.处理与会者的提前和当场注册报名。虽 然这四个临时工都有完成这四项任务所需的基本能力，但是在他们完成每一项任务时所表现 出来的有效程度是有很大差异的。表 1 显示了每一个人完成每一项任务所用的时间（单位： 小时）。试问营销经理应该将哪一项任务指派给哪一个人，才能使总时间最小？（20 分） 表 1 塞尔默公司问题中的有关数据 文字处理 制作电脑图 材料准备 记录
安 35 41 伊恩 肖恩 51 6 五、用动态规划方法求解下列问题(25分) maxz=3x1+4x5+x ≥9 0j=1,2,3 六、求解下图的中国邮路问题(20分) 七、选择(20分) 1.标准形式的线性规划问题,其可行解()是基可行解,最优解()是可行解,最优 解()在可行域的某一顶点 (a)一定 (b)不一定 (c)一定不 2.影子价格是(),其经济意义为() (a)对偶最优解(b)Bb(c)约束资源的供应限制 (d)约束条件所付的代价 3.运用表上作业法求解运输问题时,计算检验数可用() (a)闭回路法(b)西北角法(c)位势法(d)最小元素法 4.动态规划的研究对象是(),其求解的一般方法是() (a)最优化原理b)静态决策 (c)逆序求解 (d)函数迭代法(e)多阶段决策过程 试题四答案 解 (1)首先将解代入约束条件,满足,说明是可行解 A=00-2 1-40 线性相关,此解不是基可行解 (2)选取x,x3,x4作为基变量
安 35 41 27 40 伊恩 47 45 32 51 琼 39 56 36 43 肖恩 32 51 25 46 五、用动态规划方法求解下列问题（25 分） max , , z x x x x x x x j j = + + = 3 4 9 0 1 2 3 1 2 2 2 3 2 1 2 3 六、求解下图的中国邮路问题（20 分） 七、选择（20 分） 1．标准形式的线性规划问题，其可行解（ ）是基可行解，最优解（ ）是可行解，最优 解（ ）在可行域的某一顶点。 （a）一定 （b）不一定 （c）一定不 2．影子价格是（ ），其经济意义为（ ） （a）对偶最优解 （b） B b −1 （c）约束资源的供应限制 （d）约束条件所付的代价 3．运用表上作业法求解运输问题时，计算检验数可用（ ） （a）闭回路法 （b）西北角法 (c) 位势法 (d) 最小元素法 4．动态规划的研究对象是（ ），其求解的一般方法是（ ） （a）最优化原理 （b）静态决策 （c）逆序求解 （d）函数迭代法 （e）多阶段决策过程 试题四答案 一、解： （1） 首先将解代入约束条件，满足，说明是可行解 − − − − − − = 1 4 0 0 0 2 1 4 8 A A = 0 线性相关，此解不是基可行解 （2） 选取 1 3 4 x , x , x 作为基变量， 6 2 3 4 2 5 1 2 2 1 6
A=0-2-2 4 线性无关。 令 x6=x7=0 解出x1=9>0,x3=1>0,x4=0 得出一个基可行解 X=(90,1,000.0) 解:写出原问题的对偶问题得 z=4y1 y1+y2≤-1 y,-ky2 y无约束,y2≥0 由互补松弛定理:×y1=0得yn1=0,∴y1+y,=-2 y3=0 得 0,∴y1-ky2=-2 ①②联立得 1+k 而2*=-12=Z*将y*,y2*代入回 4y1*+6y2*=-12则k=-3,y*=-6y2*=2 综上,k=-3,对偶问题最优解为Y*=(y1,y2)=(-62) 三、解:(1)表上作业法求解得: B B B B B 15 A L 0 15 0 35 A210 A 150 15 销 l15 60 3070 300 15 15 检验数”20,此方案最优z*=200+450+750+2275+900+900+1750=7225 (2)增加虚拟产地A4 销 B B B3 Bs
− − − − − − = 1 0 10 0 2 2 1 8 0 A A = −36 0 线性无关。 令 x2 = x5 = x6 = x7 = 0 ，解出 x1 = 9 0, x3 =1 0, x4 = 0 得出一个基可行解 即 X = (9,0,1,0,0,0,0)。 二、解：写出原问题的对偶问题得 − = + − + − = + 0 2 1 2 max 4 6 1 2 1 2 1 2 1 2 1 2 ' y y y ky y y y y Z y y 无约束， 由互补松弛定理： x1 ys1 = 0 得 ys1 = 0, y1 + y2 = −2 ① x3 ys3 = 0 得 ys3 = 0, y1 − ky2 = −2 ② ①②联立得 k y k k y + − = + − = 1 4 , * 1 6 2 1 * 2 而 Z* = −12 = Z'*,将y1*, y2 * 代入③ 4y1 *+6y2 * = −12 ③ 则 k = −3, y1 * = −6, y2 * = 2 综上， k = −3 ，对偶问题最优解为 T T Y* (y , y ) ( 6,2) = 1 2 = − 三、解：（1）表上作业法求解得： 销 产 B1 B2 B3 B4 B5 产 i u A1 10 0 15 50 20 15 20 0 40 35 50 -10 A2 20 10 40 15 15 60 30 30 30 15 100 0 A3 30 15 35 65 40 25 55 15 25 70 150 10 销 25 115 60 30 70 300 j v 20 25 15 30 15 检验数 0 i j r ，此方案最优 Z* = 200+ 450+ 750+ 2275+900+900+1750 = 7225 （2）增加虚拟产地 A4 销 产 B1 B2 B3 B4 B5 产 i u
15 15 0 35 40 55 130 30 30 0 0 A 4 20 20 l15 300 15 检验数≥0 此方案最优Z*=500+750+2275+900+450+1625=6500 四、解:用匈牙利法求解 35412740)(30 0)(3 000 4745325115471111 90 3956364371511341821260 32512546(01006 01208 最优方案为:肖恩 文字处理,伊恩 刂作电脑图 材料准备,琼 记录 最小时间2*=32+45+27+43=147(小时) 五、解:按变量划分为三个阶段 s可以提供第k到第阶段的资源数,i=12,3 +1 第三阶段:s)=mxx2)=s 0 其中 2(s2)=mx4x2+s3}=mx4x2+(2) 第二阶段: 0<x,≤ <x2≤S2 其中 第三阶段: f1(s1)=mx{3x12+4s2}=max13x2+}=3·61+6 <x1≤ 0<x1≤9 其中x*=V6
A1 10 15 15 50 20 30 20 15 40 35 50 -25 A2 20 25 40 0 15 60 30 15 30 0 100 0 A3 30 15 35 65 40 30 55 30 25 65 130 -5 A4 0 10 M 0 15 0 15 0 5 20 -20 销 25 115 60 30 70 300 j v 20 40 15 30 30 检验数 0 i j r ，此方案最优 Z* = 500+ 750+ 2275+900+ 450+1625 = 6500 四、解：用匈牙利法求解 32 51 25 46 39 56 36 43 47 45 32 51 35 41 27 40 ~ 0 10 0 6 7 15 11 3 15 4 7 11 3 0 2 0 ~ 10 0 6 4 12 8 11 3 7 3 0 2 0 0 0 0 ~ 0 12 0 8 2 12 6 0 9 0 1 7 1 0 0 0 最优方案为：肖恩 文字处理，伊恩 制作电脑图 安 材料准备， 琼 记录 最小时间 Z* = 32 + 45+ 27 + 43 =147(小时） 五、解：按变量划分为三个阶段 i s 可以提供第 k 到第 阶段的资源数， i =1,2,3 i i i s = s • x +1 第三阶段： 2 3 2 3 3 max 3 f (s ) = x = s 0 3 3 x s 其中 3 * 3 x = s 第二阶段： 2 2 2 2 2 2 2 3 2 2 ( 2 ) max 4 2 max 4 ( ) 4s x s f s x s x = = + = + 0 2 2 x s 0 2 2 x s 其中 2 * 2 2 s x = 第三阶段： 3 5 3 2 3 6 6 36 ( ) max 3 4 max 3 1 2 2 1 2 1 1 1 = • + = + = + x f s x s x 0 x1 9 0 x1 9 其中 3 x1 * = 6
之*=3·6+6,其中x*=6,x2*=号√2·6 *=3√2·6 六、解:将奇数点变为偶数点得 经检验,重复边权小于等于非重复边权,此时为最优解 Z*=6+3+2+2+6+2+2+2+1+1+4+5+5=41 l、ba,a 234
2 5 3 2 Z* = 3 • 6 + 6 ，其中 3 x1 * = 6 ， 6 1 * 2 6 2 3 2 − x = • 6 1 3 * 3 2 6 − x = • 六、解：将奇数点变为偶数点得 6 3 2 6 1 2 2 1 2 5 4 经检验，重复边权小于等于非重复边权，此时为最优解 Z* = 6+3+ 2+ 2+ 6+ 2+ 2+ 2+1+1+ 4+5+5 = 41 七、解 1、 b,a,a 2、 a,c 3、 ac 4、 ec
