试题三 试题代码:453试题名称:运筹学 考生注意 本试题共七题,共3页,请考生认真检查 2.请务必将答案写在答卷纸上,写在试卷上的答案无效。 题号一 四 总分 得分 、用单纯形法求解下述线性规划问题(20分) maxz=4x,+x2 x1+x2≤2 x1-4x2≤4 2x2≤8 x1,x,≥0 、设一线性规划问题为(25分) max2=2x1-7x2+x3 + ntx x1+2 <4 ≥0 其最优单纯形表为 7 Bb x x X 0 x 在下述每一种情况下,进行灵敏度分析并求出最优解。 日标函数变为maXz=2x1+3 x3 3约束条件右端项由(6,4)变为(3,5) 4增加一个约束条件 x1+2x3≥2 某种产品今后四周的需求量分别为300,700,900,600件,必须得到满足。已知每件 产品的成本在起初两周是10元,以后两周是15元。工厂每周能生产这种产品700件,且在 第二、三周能加班生产。加班后,每周可增产200件产品,但成本每件增加5元。产品如不 能在本周交货,则每件每周存贮费是3元。问如何安排生产计划,使总成本最小,要求建立 运输问题数学模型求解。(25分)
试题三 试题代码：453 试题名称：运筹学 考生注意∶ １．本试题共 七 题，共 3 页，请考生认真检查； ２．请务必将答案写在答卷纸上，写在试卷上的答案无效。 题号 一 二 三 四 五 六 七 总分 得分 签字 一、用单纯形法求解下述线性规划问题（20 分） , 0 2 8 4 4 2 max 4 1 2 1 2 1 2 1 2 1 2 − − − + = + x x x x x x x x z x x 二、设一线性规划问题为（25 分） max , , z x x x x x x x x x j j = − + + + − + = 2 7 6 2 4 0 1 3 1 2 3 1 2 1 2 3 其最优单纯形表为 c j 2 -7 1 0 0 CB XB x1 x2 x3 x4 x5 B -1b 2 x1 1 1 1 1 0 6 0 x5 0 3 1 1 1 10 c z j − j 0 -9 -1 -2 0 在下述每一种情况下，进行灵敏度分析并求出最优解。 2 目标函数变为 maxz = 2x + 3x + x 1 2 3 ； 3 约束条件右端项由(6,4)T 变为(3,5)T； 4 增加一个约束条件 −x1 + 2x3 2 三、某种产品今后四周的需求量分别为 300，700，900，600 件，必须得到满足。已知每件 产品的成本在起初两周是 10 元，以后两周是 15 元。工厂每周能生产这种产品 700 件，且在 第二、三周能加班生产。加班后，每周可增产 200 件产品，但成本每件增加 5 元。产品如不 能在本周交货，则每件每周存贮费是 3 元。问如何安排生产计划，使总成本最小，要求建立 运输问题数学模型求解。（25 分）
四、某校蓝球队准备从以下6名预备队员中选拔3名为正式队员,并使平均身高尽可能高 这6名预备队员情况如下表所示,试建立数学模型。(20分) 队员的挑选要满足下列条件: 2少补充一名后卫队员 3大李或小田中间只能入选一名; 4最多补充一名中锋 5如果大李或小赵入选,小周就不能入选 预备队员 匚身高(厘米) 位置 193 中锋 大李 中锋 小王 456789 187 前锋 小赵 186 前锋 小田 后卫 小周 185 后卫 五、某高校拟开设文学、艺术、音乐、美术四个学术讲座。每个讲座每周下午举行一次。经 调查知,每周星期一至星期五不能出席某一讲座的学生数如下表:(20分) 星期 五 讲座 文学50406030 艺术 音乐40 30 30 20 美术 问:应如何安排一周的讲座日程,使不能出席讲座的学生总数最少,并计算不能出席讲座的 学生总数 六、某飞行队有5名正驾驶员和5名副驾驶员。由于种种原因,某些正、副驾驶员不能同机 飞行,某些则可以,如下表所示。每架飞机出航时需正,副驾驶员各一人。问最多能有几架 飞机同时出航?应如何安排正,副驾驶员?用图论方法求解。(20分) B B2 B B4 B 七、填空:(20分) 1.某工程公司拟从四个项目中选择若干项目,若令 x-|0个项未速中(1234
四、某校蓝球队准备从以下 6 名预备队员中选拔 3 名为正式队员，并使平均身高尽可能高， 这 6 名预备队员情况如下表所示，试建立数学模型。（20 分） 队员的挑选要满足下列条件： 2 少补充一名后卫队员； 3 大李或小田中间只能入选一名； 4 最多补充一名中锋； 5 如果大李或小赵入选，小周就不能入选。 预备队员 号码 身高（厘米） 位置 大张 大李 小王 小赵 小田 小周 4 5 6 7 8 9 193 191 187 186 180 185 中锋 中锋 前锋 前锋 后卫 后卫 五、某高校拟开设文学、艺术、音乐、美术四个学术讲座。每个讲座每周下午举行一次。经 调查知，每周星期一至星期五不能出席某一讲座的学生数如下表：（20 分） 星期 讲座 一 二 三 四 五 文学 50 40 60 30 10 艺术 40 30 20 30 20 音乐 40 30 30 20 10 美术 20 30 20 30 30 问：应如何安排一周的讲座日程，使不能出席讲座的学生总数最少，并计算不能出席讲座的 学生总数。 六、某飞行队有 5 名正驾驶员和 5 名副驾驶员。由于种种原因，某些正、副驾驶员不能同机 飞行，某些则可以，如下表所示。每架飞机出航时需正，副驾驶员各一人。问最多能有几架 飞机同时出航？应如何安排正，副驾驶员?用图论方法求解。（20 分） 正 副 B1 B2 B3 B4 B5 A1 * * A2 * * A3 * * A4 * * A5 * 七、填空：（20 分） 1．某工程公司拟从四个项目中选择若干项目，若令 1 1, 2, 3, 4 0 i i i i x ìï ïï = = í ï ï ïî ，第 个项目被选中； ，第 个项目未被选中；
用x的线性表达式表示下列要求 (1)从1,2,3项目中至少选2个 (2)只有项目2被选中,项目4才能被选中 2.用表上作业法求解某运输问题,若已计算出某空格的检验数为-2,则其经 济意义是 若从 该空格出发进行调整,设调整量为2,则调后可使总运费下降 动态规划中的 Bellman最优性原理是 试题三答案 解:将原问题化为标准形得 maxZ=4x,+x2 x1+x2,+x3=2 x x1-2x2+x5 8 x2≥0,i=1,2,…5 00 b 000 0 31 1 06 040r xI -4 1/23/2|12 4x1 0 l/21/22 09/2-1 由于个而对应的4<0 此线性规划问题无界 (1)k2的价值系数由7变为3
用 i x 的线性表达式表示下列要求： （1）从 1，2，3 项目中至少选 2 个： ； （2）只有项目 2 被选中，项目 4 才能被选中： ； 2．用表上作业法求解某运输问题，若已计算出某空格的检验数为-2，则其经 济意义是 ，若从 该空格出发进行调整，设调整量为 2，则调后可使总运费下降 ； 3. 动态规划中的 Bellman 最优性原理是 。 试题三答案 一、解：将原问题化为标准形得 0, 1,2, 5 2 8 4 4 2 max 4 1 2 5 1 2 4 1 2 3 1 2 = − + = − + = − + + = = + x i x x x x x x x x x Z x x i 4 1 0 0 0 i b bi aik / 1 x 2 x 3 x 4 x 5 x 0 3 x -1 1 1 0 0 2 - 0 4 x 1 -4 0 1 0 4 4 0 5 x 1 -2 0 0 1 8 8 j r 4 1 0 0 0 0 3 x 0 -3 1 1 0 6 - 4 1 x 1 -4 0 1 0 4 - 0 5 x 0 2 0 -1 1 4 2 j r 0 17 0 -4 0 0 3 x 0 0 1 -1/2 3/2 12 4 1 x 1 0 0 -1 2 12 1 2 x 0 1 0 -1/2 1/2 2 j r 0 0 0 9/2 -17/2 由于 40 r 而对应的 ai4 0 此线性规划问题无界 二、解 （1）X2 的价值系数由-7 变为 3
1>0 ∴最优解发生变化,继续迭代 00 x3 2 0 0/3 0 2 d 2/32/3-1/3|8/3 1/31/31/310/3 00 4/3-2 -1/3-46/3 此时最优解为 33 b=b-b 此时不影响解的最优性,只改变解的值及目标函数值 (x12x3)=(38) (3)最优解不满足新增加的约束条件 x3≥2 最优解要发生改变 将约束条件改写为 x1-2x3 加入最优表中继续迭代。 xI x, x5 6
( ) 1 0 3 1 2 3 2 0 = r = − 最优解发生变化，继续迭代。 2 3 1 0 0 1 x 2 x 3 x 4 x 5 x bi bi aik / 2 1 x 0 5 x 1 1 1 1 0 0 3 1 1 1 6 10 6 10/3 j r 0 1 -1 -2 0 2 1 x 3 2 x 1 0 2/3 2/3 -1/3 0 1 1/3 1/3 1/3 8/3 10/3 j r 0 0 -4/3 -2 -1/3 -46/3 此时最优解为 3 46 ) 3 10 , 3 8 ( , ) ( * 1 2 * = = = Z X x x T T （2） = − 1 1 1 0 1 B 0 8 3 5 3 1 1 1 0 ' 1 = = = − b B b 此时不影响解的最优性，只改变解的值及目标函数值 * 6 * ( , ) (3,8) 1 5 = = = Z X x x T T （3） 最优解不满足新增加的约束条件 − x1 + 2x3 2 最优解要发生改变 将约束条件改写为 x1 − 2x3 + x6 = −2 加入最优表中继续迭代。 2 -7 1 0 0 0 1 x 2 x 3 x 4 x 5 x 6 x bi 2 1 x 0 5 x 1 1 1 1 0 0 0 3 1 1 1 0 6 10
0 0 X 0 2 0 2/3 10/3 8/3 0 1/3 0 l/3 8/3 0-26/30 l/3 (19,3) 8 ZE 新的最优解为 三、解:建立运输问题模型并给出初始方案得: 2 3 10 16 700 0 17 200 0 18 200 18 21 200 17 0 200 3 700 200 700 200 200 300 600 1100 3600 10 检验数有负,重复调整,得如下解:
0 6 x 0 -1 -3 -1 0 1 -8 j r 0 -9 -1 -2 0 0 j aik r / - 9 1/3 2 - - 2 1 x 0 5 x 1 3 x 1 2/3 0 2/3 0 1/3 0 8/3 0 2/3 1 4/3 0 1/3 1 1/3 0 -1/3 10/3 22/3 8/3 j r 0 -26/3 0 -5/3 0 -1/3 -28/3 新的最优解为 3 28 * * ( 1, 3) ( , ) 3 8 3 10 = = = Z X x x T T 三、解：建立运输问题模型并给出初始方案得： 销 产 1 2 3 4 5 产 i u 1 10 300 13 17 16 200 19 200 0 4 700 0 1’ 15 1 18 18 21 1 24 1 0 200 200 4 2 M 10 700 13 -7 16 -7 0 0 700 4 2’ M 15 17 18 0 21 200 0 2 200 2 3 M M 15 700 18 0 0 5 700 -1 3’ M M 20 0 23 200 0 0 200 4 4 M M M 15 -8 0 700 700 4 4’ M M M 20 -3 0 200 200 4 销 300 700 900 600 1100 3600 j v 10 -4 16 19 -4 检验数有负，重复调整，得如下解：
销 2 4 0 15 200 200 10 13 16 2 700 0 200 0 200 N 15 700 20 23 200 4 0 00 M 4 200 0 5 销 300 900 600 1100 3600 此时检验数全 0 ,为最优解 Z*=300×10+700×10+200×16+700×15+600×15=32700(元) 分配计划如下:第一个月正常生产500件,分别给1月300件,3月200件 第二个月正常生产700件,供给第二个月 第三个月正常生产700件,供给第三个月 第四个月正常生产600件,供给第六个月 ∫0,第号码的人不入选 y 四、解:设 l,第i号码的人入选 「mxz=(193y4+191y5+187y+186y+180y+185y) V4+ys+ys+y7+y8+yg=3 ys+y8< y4 ys ys t yg V, t yo V t yo 五、解:利用匈牙利法求解,增加一行元素
销 产 1 2 3 4 5 产 i u 1 10 300 13 0 16 200 19 4 0 200 700 0 1’ 15 5 18 5 21 5 24 9 0 200 200 0 2 M 10 700 13 0 16 4 0 3 700 -3 2’ M 15 2 18 2 21 6 0 200 200 0 3 M M 15 700 18 4 0 1 700 -1 3’ M M 20 4 23 8 0 200 200 0 4 M M M 15 600 0 100 700 0 4’ M M M 20 5 0 200 200 0 销 300 700 900 600 1100 3600 j v 10 13 16 15 0 此时检验数全 0 i j r ，为最优解 Z* = 30010 + 70010 + 20016 + 70015+ 60015 = 32700(元) 分配计划如下：第一个月正常生产 500 件，分别给 1 月 300 件，3 月 200 件。 第二个月正常生产 700 件，供给第二个月 第三个月正常生产 700 件，供给第三个月 第四个月正常生产 600 件，供给第六个月 四、解：设 = ，第 号码的人入选 ，第 号码的人不入选 i i yi 1 0 = + = + + + + + + + + + = = + + + + + 0 1 1 1 1 1 1 3 max (193 191 187 186 180 185 ) 8 9 7 9 5 9 4 5 5 8 4 5 5 7 8 9 3 4 5 6 7 8 9 1 yi 或 y y y y y y y y y y y y y y y y Z y y y y y y 五、解：利用匈牙利法求解，增加一行元素
5040603010(493050200(402050100 403020302020100100200000 4030302010 2010030102000 2030203030b1001010000010 00000 此时方案最优,最少人数Z*=20+20+20+10=70人 方案为周一上美术课,周三上艺术课,周四上音乐课,周五上文学课。 B3 B 4 如图所示,最多只能有四架飞机出航:A1-B1,A2-Bs,A3-B3,A4-B2 (2)x2+x4=2或x2+x4=0 2、运费还可以减少,此方案不是最优方案 3、在多阶段决策过程中,最优决策序列具有这种性质,即不管该序列上某状态以前的 状态和决策如何,余下的决策序列必构成该状态的最优决策序列
0 0 0 0 0 20 30 20 30 30 40 30 30 20 10 40 30 20 30 20 50 40 60 30 10 ~ 0 0 0 0 10 0 10 10 30 20 20 10 20 10 10 0 40 30 50 20 0 0 0 0 0 ~ 10 10 0 10 0 0 0 10 30 10 20 0 20 0 0 0 40 20 50 10 0 0 0 0 0 此时方案最优，最少人数 Z* = 20 + 20 + 20 +10 = 70人 方案为周一上美术课，周三上艺术课，周四上音乐课，周五上文学课。 六、解 S A1 A2 A3 A4 B1 B2 B3 B4 t A5 B5 1,1 1,1 1,1 1,1 1,0 1,1 1,1 1,1 1,1 1,0 1,1 1,1 1,1 1,1 1,0 如图所示，最多只能有四架飞机出航：A1—B1，A2—B5，A3—B3，A4—B2 七、解： 1、（1） x1 + x2 + x3 2 （2） x2 + x4 = 2或x2 + x4 = 0 2、运费还可以减少，此方案不是最优方案 3、在多阶段决策过程中，最优决策序列具有这种性质，即不管该序列上某状态以前的 状态和决策如何，余下的决策序列必构成该状态的最优决策序列