2015运筹学复习题

1. 某工厂生产甲、乙两种产品，这两种产品需要经过A、B、C、D四种不同的设备加工。已知各产品所需要的加工台时数、每件产品的产值以及各设备在计划期内的有效台时数见下表。试建立既满足工时要求，又能使产值最大的线性规划模型。若该工厂的决策者考虑不生产产品甲和乙，而考虑将生产设备的有效台时用于接受对外协作加工，工厂只收加工费，试建立四种设 备最低定价的线性规划模型。

甲、乙两种产品生产情况表

设备 A B C D

单位产品产值（元）

产品

甲 2 3 5 0 200

乙 4 6 0 8 400

有效台时数

16 12 20 16

2. 某商场决定：营业员每周连续工作5天后连续休息2天，轮流休息。根据统计，商场每天需要的营业员如下表所示。商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少。（建立该问题的数学模型，不求解） 星 期 一 二 三 四

需要人数 300 300 350 400

星 期 五 六 日

需要人数 480 600 550

3. 某农业生产单位有男劳动力250人，女劳动力200人，安排在一日内完成割麦任务320亩，且除草的亩数最多。在已知男劳力每天能割麦1.5亩，除草2亩；女劳力一天能割麦1.2亩，除草1.4亩，如下表所示。

劳力和任务量 男劳力（人） 女劳力（人） 任务量（亩）

任务

割麦 1.5 1.2 320

除草 2 1.4 越多越好

限制量 250 200

试建立如何安排劳动力，使既能完成割麦任务又能使除草亩数最多的线性规划模型。 4. 将下面的数学模型化为线性规划问题的标准形式。

maxz?2y1?y2

x1?3x2?2x3?3y1?2y2?2x?x?3x?1s..t?123?x,y?0 (i?1,2,3;j?1,2)?ij5. 将下规划问题化为线性规划标准形式。

minZ?y

?x?y?2?s.t.?x?y?0 ??x?36. 求X?(x1,x2,x3,x4)T，满足下列条件（20分）

?x1?x2?2x3?x4?2?2x?x?3x?x?6?1234s.t.? ?x1?x2?x3?x4?7?xj?0,(j?1,?,4)?使函数 minf?2x1?x2?x3?x4

分别求该线性规划问题与其对偶问题的最优解。 7. 已知X?(x1,x2,x3)T，满足下列条件

?x1?x2?1?x?x??1?12s.t.?

x?x?103?1??x1?0,x3?0使函数 maxf?x1?x2?x3

分别求该线性规划问题与其对偶问题的最优解。

8. 某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用为最小。若10个井位的代号为s1,s2,……,s10，相应的钻探费用为c1,c2,……,c10，并且井位选择方面要满足下列限制条件：

① 或选择s1和s7，或选择钻探s8；

② 选择了s3或s4就不能选择s5，反之如选择了s5，就不能选择s3和s4； ③ 在s5, s6, s7, s8中最多只能选两个；

④ 如果s9被选中，s10也必须同时选中。相返，如果s10被选中，则s9可能被选中，也可能不被选中。

试建立这个问题的整数规划模型。

9. 拟打一口深水井向5个村供饮用水，已知第i村的饮用水量为Qi吨（i=1,2,3,4,5），井只能打在5个村中的某个村，且知若井打在第i个村，第j个村的吨水费用为Cij元，试建立使总水费用为最低的选址规划模型。

10. 运用变量代换，将下述非线性0-1型整数规划转换成线性0-1型整数规划。

2maxz?x1?x2x3?x1x2x3

???3x1?4x2?x3?3s..t?

x?0或1 (j?1,2,3)??j11. 有4个工人，要指派他们分别完成4种工作，每人做各种工作所消耗的时间如下表所示，问指派哪个人去完成哪种工作，可使总的消耗时间为最少？

工作

工作人员

A B C

甲 15 18 21

D

24

乙 丙 丁

19 26 19 23 17 21 22 16 23 18 19 17

12. 有一份说明书，要分别译成英、日、俄、德、法五种文字，并分别称为任务A，B，C，D，E。同时，分派给甲、乙、丙、丁、戊五个人去完成，且要求每人只能完成一种任务，因个人专长不同，他们翻译成不同文字所花时间如下表。试求应该如何分派任务，才能使总的花费时间最少？ 任务 人 甲 乙 丙 丁 戊

A 12 8 7 16 4 B 7 11 17 14 10 7 5 4 1 6 5 3 2 4 5 1 5 4 6 1 8 7 6 C 9 7 12 6 7 D 7 8 14 6 10 E 9 6 12 10 6 13. 用动态规划求下列网络节点1到节点7的最短路径

2 14. 现有资金5亿元，可对三个项目进行投资，投资额均为整数（单位：亿元），其中2#项目的投资额不得超过3亿元，1#、3#项目的投资额均不得超过4亿元，3#项目至少要投资1亿元，每个项目投资5年后，预计可获得收益见表1。问如何投资可望获得最大收益。

表1 预计获得收益

项目

投资额

1# 2# 3#

0 0 0 － 1 3 5 4 2 6 10 8 3 10 12 11 4 12 － 15

15. 已知某工程资料如下表，试求出该工程的最低成本日程。

某工程资料情况表

工序代号 工序时间 紧前工序 正常完工进度的直接费赶进度一天所需费用A 4 20 5 用（百元） （百元）－ B 8 30 4 － C 6 B 15 3 D 3 A 5 2 E 5 A 18 4 F 7 A 40 7 G 4 10 3 B，D H 3 15 6 E，F，G 153 合计 工程的间接费用 5（百元/天） 16. 已知某一计划中各道工序的a, m, b值（单位为天），见下表的第2、3、4列，工序衔接

表在下表中也已给出，且?(1.293)?0.9014, ?(1.302)?0.9032, ?(1.289)?0.9003,

?(1.272)?0.8980, ?(1.401)?0.0.9192求：

（1）求每道工序的工序时间t ( i , j )及工序时间方差D ( i , j )； （2）画出网络图，确定关键路线； （3）在72天内完工的概率；

（4）计算工程在第73天时完工的难易系数。

工序

A B C D E F G H I J

a 6 5 11 15 9 18 30 20 14 28

m 7 8 12 17 10 24 35 26 17 34

b 9 10 14 19 12 26 42 30 22 38

紧前工序 － － － A,B,C A C E D F F

紧后工序 E，D D D，F H G I，J — — — —

16. 甲的赢得矩阵如下：

乙

① ② ③ ④ ⑤

①②?10?甲③ ?14④? 8060?041018??6181018?

?812161412??⑤??12016166???61．用优势原理进行化简

2．给出求甲和乙的最优混合策略的线性规划模型。 3. 求出甲和乙的最优混合策略和对策值。

17. 甲的赢得矩阵如下： 乙 ① ② ③ ④ ⑤

甲 ③

1．用优势原理进行化简

2．给出求甲和乙的最优混合策略的线性规划模型。 3．求甲乙的最优混合策略和对策值。

①?3②④⑤ 403?5025??7395??4687??60880?9??9? ?6?3??