《运筹学》期末考试试题

一、模型题（每小题10分，共30分）

1．写出下列问题的对偶问题（10分）

第1页，共8页

(1).minzx13x23x34x11x2x330x14x22x320s.t.x12x2x34x10,x20

(2).maxzx14x22x3x42x12x23x3x45x12x24x3x412s.t.2x1x23x34x10,x20,x40

2. 建立下列问题的线性规划模型。(10分)

某公司有三项工作需分别招收技工和力工来完成。第一项工作可由一个技工

………第2页，共…8页

…答单独完成，或由一个技工和两个力工组成的小组来完成。第二项工作可由一个技工或一个力工单独去完成。第三项工作可由五个力工组成的小组完成，或由一个技工领着三个力工来完成。已知技工和力工每周工资分别为100元和80元，他们每周都工作48小时，但他们每人实际的有效工作小时数分别为42和36。为完成这三项工作任务，该公司需要每周总有效工作小时数为：第一项工作10000小时，第二项工作20000小时，第三项工作30000小时。又能招收到的工人数为技工不超过400人，力工不超过800人。试建立数学模型，确定招收技工和力工各多少人，使总的工资支出为最少(建立数学模型，不求解)。

3. 建立下列问题的整数规划模型。(10分)

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

第3页，共8页

①或选择s1和s7，或选择钻探s8； ②不能同时选择s3和s4；

③如果选择了s2，就必须同时选择s9； ④在s5、s6、s7、s8中最多只能选三个； （第1题10分，第2题40分，共50分）1．用匈牙利求解下列系数矩阵的最小化指派问题（

15192619182317212122262324181917 第4页，共8页

10分）

二、计算题

2. 某厂生产I、II、III三种产品，分别经过A、B、C三种设备加工。已知生产单位各种

产品所需的设备台时、设备的现有加工能力及每件产品的预期利润见下表。（共40分）

（1）求获利最大的产品生产计划；（15分）

（2）产品III每件的利润增加到多大时才值得安排生产？（3分） （3）产品I的利润在多大范围内变化时，原最优计划保持不变；（4分） （4）设备A的能力如为100＋10θ，确定保持最优基不变的θ的变化范围；（4分）

（5）如有一种新产品，加工一件需设备A、B、C的台时各为1、4、3小时，预

第5页，共8页

期每件的利润为8元，问是否值得安排生产？（4分）

（6）如合同规定该厂至少生产10件产品III，试确定最优计划的变化。（10分） A B C 利润（元）

第6页，共8页

I 1 10 2 II 1 4 2 III 1 5 6 4 设备能力（台时） 100 600 300 10 6 三、图表题（每小题10分，共20分）

1. 用动态规划逆序解法（标号法）求从A 到E的最短路线及其长度。 (10分) （注：直接做在下面的图中）

5 6 B11 C11

4 6 3 5 9 6 D11 4 5 6 A 6 7 4 4 4 B2 1 6 C 21 3 E 8 9 D21

B31 C31 2. 运输问题。求出下列运输问题的初始解（用最小元素法）及初始解的检验数填在下表中。（10分）（注：直接做在下面的表中）

第7页，共8页

销地

产地

B1 B2 B3 产量

A1

4

6

3

9

12

A2

7

4 6

15

6

5 3

10

15

A3

20

销量 A4

5

18

2

16

第8页，共8页