运筹学教材编写组《运筹学》期末考试试卷(B)

《运筹学》期末考试试卷(B)

学院 班级 姓名 学号

考生注意∶

１．本试题共 七 题，共 3 页，请考生认真检查；

２．请务必将答案写在答卷纸上，写在试卷上的答案无效。 题号 一 二 三 四 五 得分 签字 六 七 总分

一、用单纯形法求解下述线性规划问题（20分）

二、设一线性规划问题为（25分）

???????maxz?4x1?x2?x1?x2?2x1?4x2?4x1?2x2?8x1,x2?0?maxz?2x1?7x2?x3?x1?x2?x3?6??x1?2x2?4?x?0j?1,?,3j ?

其最优单纯形表为 cj2 -7 1 0 0 B-1b 6 10 CB XB 2 0 x1 1 0 0 x2 1 3 -9 x3 1 1 -1 x4 1 1 -2 x5 0 1 0 x1 x5 cj?zj在下述每一种情况下，进行灵敏度分析并求出最优解。 122 目标函数变为

TT

3 约束条件右端项由(6,4)变为(3,5)；

maxz?2x?3x?x3；

134 增加一个约束条件

三、某种产品今后四周的需求量分别为300，700，900，600件，必须得到满足。已知每件产品的成本在起初两周是10元，以后两周是15元。工厂每周能生产这种产品700件，且在第二、三周能加班生产。加班后，每周可增产200件产品，但成本每件增加5元。产品如不

?x?2x?2能在本周交货，则每件每周存贮费是3元。问如何安排生产计划，使总成本最小，要求建立运输问题数学模型求解。（25分）

四、某校蓝球队准备从以下6名预备队员中选拔3名为正式队员，并使平均身高尽可能高，这6名预备队员情况如下表所示，试建立数学模型。（20分）

队员的挑选要满足下列条件： 2 3 4 5

少补充一名后卫队员；

大李或小田中间只能入选一名； 最多补充一名中锋；

如果大李或小赵入选，小周就不能入选。

预备队员 大张 大李 小王 小赵 小田 小周

五、某高校拟开设文学、艺术、音乐、美术四个学术讲座。每个讲座每周下午举行一次。经调查知，每周星期一至星期五不能出席某一讲座的学生数如下表：（20分）

星期 讲座 文学 艺术 音乐 一 50 40 40 二 40 30 30 三 60 20 30 四 30 30 20 五 10 20 10 号码 4 5 6 7 8 9 身高（厘米） 193 191 187 186 180 185 位置 中锋 中锋 前锋 前锋 后卫 后卫 20 30 20 30 30 美术 问：应如何安排一周的讲座日程，使不能出席讲座的学生总数最少，并计算不能出席讲座的学生总数。

六、某飞行队有5名正驾驶员和5名副驾驶员。由于种种原因，某些正、副驾驶员不能同机飞行，某些则可以，如下表所示。每架飞机出航时需正，副驾驶员各一人。问最多能有几架飞机同时出航？应如何安排正，副驾驶员?用图论方法求解。（20分）

副正 B B B B B 12345A1 A2 A3 A4 A5 * * * * * * * * *

七、填空：（20分）

1．某工程公司拟从四个项目中选择若干项目，若令

xi用xi的线性表达式表示下列要求：

（1）从1，2，3项目中至少选2个： ；

（2）只有项目2被选中，项目4才能被选中： ；

2．用表上作业法求解某运输问题，若已计算出某空格的检验数为-2，则其经

济意义是 ，若从

该空格出发进行调整，设调整量为2，则调后可使总运费下降 ；

3. 动态规划中的Bellman最优性原理是

。

ì??1，第i个项目被选中；=íi=1,2,3,4?0，第i个项目未被选中；???

期末考试试卷(B)参考答案

一、解：将原问题化为标准形得

maxZ?4x1?x2?x1?x2?x3?2x1?4x2?x4?4x1?2x2?x5?8 xi?0,i?1,2,?5

4 1 0 0 0 bi bi/aik x1 x2 x3 x4 x5 0 x3 -1 1 1 0 0 2 - 0 x4 1 -4 0 1 0 4 4 0 x5 1 -2 0 0 1 8 8

rj 4 1 0 0 0

0 x3 0 -3 1 1 0 6 - 4 x1 1 -4 0 1 0 4 - 0 x5 0 2 0 -1 1 4 2

rj 0 17 0 -4 0

0 x3 0 0 1 -1/2 3/2 12 4 x1 1 0 0 -1 2 12 1 x2 0 1 0 -1/2 1/2 2

rj 0 0 0 9/2 -17/2

由于r4?0而对应的ai4?0 ? 此线性规划问题无界

二、解

（1）X2的价值系数由-7变为3。

?1?r2?3??20???3???1?0??

?最优解发生变化，继续迭代。 2 3 1 0 0 x1 x2 x3 x4 x5 2 x1 0 x5 1 1 1 1 0 0 3 1 1 1 0 1 -1 -2 0 1 0 2/3 2/3 -1/3 0 1 1/3 1/3 1/3 0 0 -4/3 -2 -1/3 bi bi/aik 6 10 6 10/3 rj 2 x1 3 x2 8/3 10/3 -46/3 rj 此时最优解为 810?X*?(x1,x2)T?(,)T3346Z*?3

?10??1B???11???? （2）

?10??3??3?b'?B?1b???11????5?????8???0??????

?X*?(x1,x5)T?(3,8)TZ*?6

此时不影响解的最优性，只改变解的值及目标函数值

（3） 最优解不满足新增加的约束条件?x1?2x3?2

?最优解要发生改变 将约束条件改写为 x1?2x3?x6??2 加入最优表中继续迭代。