2016年哈尔滨工业大学威海校区850运筹学考研必备复习题库及答案
● 摘要
一、简答题
1． 在解决实际问题时应如何运用启发式策略? 除本书上列出的几个启发式策略之外，你认为还有什么样的策略可以使用?
【答案】在解决实际问题时，可根据实际问题的性质和要求来选用某一启发式策略; 为得到理想效果，也可将几个策略联合起来使用。除本书上列出的几个启发式策略之外，还有计算机仿真、模拟策略、类比策略、近似策略等可以使用。
2． 对在多台设备上加工多个工件的工件排序问题来说，应如何衡量不同排序方案的优劣? 你认为应有哪 些准则? 这些准则的适用条件是什么? 请举出两个实例加以详细说明。
【答案】（l ）应根据工期最短、成本最低、质量最优等优劣标准来衡量不同排序方案的优劣。 （2）设备充分利用、总加工时间最短等某一或某几种目标函数最优。
（3）每个工件在m 台设备加工都有一定的先后顺序，工件在不同设备的加工顺序不同的情况不作考虑以及 信息掌握情况和资源约束等适用条件。
（4）举例。建筑施工流水作业问题:在不同的施工段上按一定的施工工艺进行施工，而施工工艺又由不同 的施工工序组成，每道施工工序都要消耗一定的人工费用，机械台班和材料费用，并且某些施工工序之间有一定的先后约束关系，如支起模板后才能浇注混凝土，而此问题关注不同施
使整个施工按照最短施工时间保持一定施工节拍进行流工工序如何搭接排序组成一定施工工艺，
水作业，同时消耗人、机、材等资源也合理。
3． 简述对偶问题的“互补松弛性”。
【答案】互补松弛性:若仅当为最优解。 分别是原问题和对偶问题的可行解。那么，当且4． 简述求解整数规划分枝定界法的基本思想。
【答案】设有最大化的整数规划问题A ，与它对应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z*的上界，记作; 而A 的任意可行解的目标函数值将是z*的一个下界
域（称为分支）的方法，逐步减小和增大; 。分支定界法就是将B 的可行域分成子区:， 最终求到z*。
二、计算题
5． 某公司考虑生产一种新产品，决策者对市场销售状态进行预测的结果有三种情况:销路好、一般、差，其概率及各种情况下增加的利润额（单位:万元）如表所示（其中S 为销路，P 为利润增长额，A 为方案）。 为了得到更加可靠的信息，公司可以花费0.6万元请咨询公司代为进行市场调查，以确定市场的实际需求。
请回答下列问题:
（l ）采用贝叶斯决策准则，最优方案是什么?
（2）画出贝叶斯决策过程的决策树。
（3）计算全情报价值EVPI ，并确定是否需要请咨询公司进行市场调查?
表 销路和利润增长额预测情况。
【答案】（l ）设两种选择的期望收益分别为E 1、E 2，则
会选择第一种方案，期望值EMV=l .35万元。
（2）贝叶斯决策过程的决策树如图所示。
图
（3）当完全情报告诉决策者自然状态是S 1时，决策者一定采用方案a 1; 当完全情报告诉决策者自然状态是 S 2时，决策者一定采用方案a l ; 当完全情报告诉决策者自然状态是S 3时，决策者一定采用方案a 2。
所以
咨询公司的咨询要价小于2.7，所以，需要请咨询公司进行调查。
6． 某厂有100台设备，可用于加工甲、乙两种产品。根据以往经验这些设备都用于加工甲产品时，每季度 末损坏1/3台; 而都用于加工乙产品时，每季度末损坏1/10台，损坏的设备当年不能修复。每台机器一季度用于 加工甲产品可获利10百元; 加工乙产品可获利7百元。问如何安排各季度加工甲、乙产品的设备台数，才能使 全年获得最大? （用动态规划方法求解）
【答案】该问题可以分为4个阶段。k 表示季度，状态变量s k 表示k 年初拥有的可投入最大机器
数量，决策变量 x k 表示第k 季度的分配在用产品的设备数量，则s k -u k 为分在乙产品的设备数量。
状态转移方程:
K 阶段允许决策集合为：
指数
为第k 季度初从s k 出发到第4季度结束最大产值 当k=4时，
即在第4年全部要八乙
7． 己知图表示7个城市间拟建一条连接各个城市的通信线路，各边的权数表示两个城市之间的修建 费用，求连接各城市通信线路最小修建费用方案。
图
【答案】最优万案为: