运筹学完整版

《运筹学》习题答案

一、单选题

1.用动态规划求解工程线路问题时，什么样的网络问题可以转化为定步数问题求解（ ）B

A.任意网络 B.无回路有向网络 C.混合网络 D.容量网络

2.通过什么方法或者技巧可以把工程线路问题转化为动态规划问题？（ ）B

A.非线性问题的线性化技巧 B.静态问题的动态处理

C.引入虚拟产地或者销地 D.引入人工变量

3.静态问题的动态处理最常用的方法是？B

A.非线性问题的线性化技巧 B.人为的引入时段

C.引入虚拟产地或者销地 D.网络建模

4.串联系统可靠性问题动态规划模型的特点是（ ）D

A.状态变量的选取 B.决策变量的选取

C.有虚拟产地或者销地 D.目标函数取乘积形式

5.在网络计划技术中，进行时间与成本优化时，一般地说，随着施工周期的缩短，直接费用是( )。C

A.降低的 B.不增不减的 C.增加的 D.难以估计的

6.最小枝权树算法是从已接接点出发，把( )的接点连接上C

A.最远 B.较远 C.最近 D.较近

7.在箭线式网络固中，( )的说法是错误的。D

A.结点不占用时间也不消耗资源

B.结点表示前接活动的完成和后续活动的开始

C.箭线代表活动

D.结点的最早出现时间和最迟出现时间是同一个时间

8.如图所示，在锅炉房与各车间之间铺设暖气管最小的管道总长度是( )。C

A.1200 B.1400 C.1300 D.1700

9.在求最短路线问题中，已知起点到A，B，C三相邻结点的距离分别为15km，20km,25km，则（ ）。D

A.最短路线—定通过A点 B.最短路线一定通过B点

C.最短路线一定通过C点 D.不能判断最短路线通过哪一点

10.在一棵树中，如果在某两点间加上条边，则图一定( )A

A.存在一个圈 B.存在两个圈 C.存在三个圈 D.不含圈

一、问题描述

胖子冒菜处于商学院弘毅一楼下。因课程原因，平时到此吃饭的同学不多，而在每个星期六就会猛增。该点主要为同学们提供川味冒菜。该快餐店雇佣了两名正式职工，正式职工每天工作8小时。另外的工作由兼职的临时工来担任，临时工每班工作4小时。星期六，胖子冒菜从上午10点开始营业到晚上9点关门。根据调查，星期六每个营业小时所需职工数（包括正式工和临时工）如表10所示。

表10 星期六每个营业小时所需职工数

时间 所需职工数

10：00-11：00 4

11：00-12：00 4

12：00-13：00 4

13：00-14：00 4

14：00-15：00 2

15：00-16：00 2

16：00-17：00 2

17：00-18：00 5

18：00-19：00 5

19：00-20：00 5

20：00-21：00 3

同时已知一名正式职工10点开始上班，干4小时，休息1小时后再干4小时；另一名正式职工12点开始上班干4小时，休息1小时后再干4小时。又知道临时工每小时的工资为5元。在满足对职工需求的条件下如何安排临时工的班次，使得使用临时工的成本为最小？

二、问题分析

这个问题的目标是求临时工的用工成本最小，成本最小就关系到要请多少个临时工，如何安排排班的问题，实际上是人力分配问题。本来我们想采取图与网络来解决，但由于临时工人数不确定，就无法安排。因此我们考虑采取线性规划的方法建立模型进行解决，以下是过程。

(1)决策变量和目标函数

这个问题的影响因素是临时工的总的上班时间，开始的时候我们令每个时间短的临时工的人数为决策变量，但最后所列出的约束条件每条式子只有一个变量，感觉有点奇怪。于是设 Xi 表示第i时间段要开始工作的临时工的人数，如10：00-11：00时段的临时工人数为X1，那这一部分的人数在下一阶段就不能算进去，因为他们在这个阶段是正在工作了，不是开始工作。由于临时工开始工作后每班工作4小时，每小时的工资为5元，一个临时工的排班一次的成本为20元，由此可构建目标函数。

实验报告

课程名称：运筹学/Operations Research

实验总学时数：16

适用专业： 工程管理

承担实验室：15- 109、15-110

开课学院、系或教研室： 管理学院

一、实验教学目的和要求

目的：充分发挥WinQSB软件的强大功能和先进的计算机工具，改变传统的教学手段和教学方法，将软件的应用引入到课堂教学，理论与应用相结合。丰富教学内容，提高学习兴趣。使学生能基本掌握WinQSB软件常用命令和功能。

要求：熟悉WinQSB软件子菜单。能用WinQSB软件求解运筹学中常见的数学模型。

二、单项实验的要求（包括实验分组人数要求）和内容

分组要求：6-7人一组，每组做一份实验报告。

实验一：线性规划

（一）实验目的：安装WinQSB软件，了解WinQSB软件在Windows环境下的文件管理操作，熟悉软件界面内容，掌握操作命令。用WinQSB软件求解线性规划。

（二）内容和要求：安装与启动软件，建立新问题，输入模型，求解模型，结果的简单分析。

（三）操作步骤：

1.将WinQSB文件复制到本地硬盘；在WinQSB文件夹中双击setup.exe。

2.指定安装WinQSB软件的目标目录（默认为C:\ WinQSB）。

3. 安装过程需输入用户名和单位名称（任意输入），安装完毕之后，WinQSB菜单自动生成在系统程序中。

4.熟悉WinQSB软件子菜单内容及其功能，掌握操作命令。

5．求解线性规划。启动程序 开始→程序→WinQSB→Linear and Integer Programming 。

6．观赏例题 点击File→Load Problem→lp.lpp, 点击菜单栏Solve and Analyze或点击工具栏中的图标用单纯形法求解，观赏一下软件用单纯形法迭代步骤。用图解法求解，显示可行域，点击菜单栏Option →Change XY Ranges and Colors，改变X1、X2的取值区域（坐标轴的比例），单击颜色区域改变背景、可行域等8种颜色，满足你的个性选择。

《运筹学》综合复习资料

一、判断

1. 对偶问题的对偶问题一定是原问题。

2. 分枝定界求解整数规划时,分枝问题的最优解不会优于原(上一级)问题的最优解。

3. 整数规划中，割平面的构造应满足能割掉松弛问题的最优解，但不割掉原问题的可行解。

二、计算题

1.某LP模型为∶

0,,,35.021841023..19508943214343214321xxxxxxxxxxtsxxxxzMax

单纯形表已解至如下表:

9

x1 8

x2 50

x3 19

x4 0

s1 0

s2

b

x4 2 4/3 0 1 2/3 -10/3 2

x3 -1/2 -1/3 1 0 -1/6 4/3 1

Zj

Cj - Zj

(1)填上表中尚缺数据并回答该问题的最优解,最优目标函数值

(2)当模型中第一个约束条件右端常数由18 改为19 时,最优基是否发生变化？(要计算过程)

(3)写出该问题的对偶规划并回答对偶问题的最优解。

(4)回答是否要购入第一、第二种资源，如购入可接受的最高市场价格是多少？

2.某商业公司计划开办4家新商店，决定由4家建筑公司承建，已知各建筑公司对各家商店的建造费用报价如下表（单位：万元），试问商业公司应怎样决定，才能使总建造费用最省？

商店1 商店2 商店3 商店4

建筑公司1 4 8 7 15

建筑公司2 7 9 17

14

建筑公司3 6 9 12 8

建筑公司4 6 7 14

6

3.计算v1到v8的最短路。

v1 v2

v3 v4

v5 v6

v7 v8 4

6 5

7 6 9

5 4

1 4

4 7

5 4.某公司计划制造Ⅰ、Ⅱ两种家电产品，已知各制造一件时分别占用的设备A、B的台时、调试时间及每天可用的设备能力和单件产品的获利情况如下表：

Ⅰ Ⅱ 每天可用能力

设备A（小时） 0 5 15