运筹学教材编写组《运筹学》课后习题-启发式方法(圣才出品)
- 格式：pdf
- 大小：1.89 MB
- 文档页数：13
3 / 13
圣才电子书 十万种考研考证电子书、题库视频学习平台
图 18-1
（2）修改后的迭代算法即神经网络算法。
①建立结合矩阵：将车辆经过的点包括源点看成神经网络的结点，即神经元，令神经元
数目为 N； i 神经元和 j 神经元的结合权值为ij ， j 神经元的输出为 rj 。
2 / 13
圣才电子书十万种考研考证电子书、题库视频学习平台
至旅行线路中包含所有的点。 18.6 说明本书所述货运车辆优化调度算法的原理和求解步骤，并绘出求解过程框图。
请简要回答以下问题。 （1）若有两种车型的车可用，书中提出的模型应怎样修改?在书中所提算法的启发下，
而施工工艺又由不同的施工工序组成，每道施工工序都要消耗一定的人工费用，机械台班和 材料费用，并且某些施工工序之间有一定的先后约束关系，如支起模板后才能浇注混凝土， 而此问题关注不同施工工序如何搭接排序组成一定施工工艺，使整个施工按照最短施工时间 保持一定施工节拍进行流水作业，同时消耗人、机、材等资源也合理。
圣才电子书
十万种考研考证电子书、题库视频学习平台
第 18 章 启发式方法
18.1 什么是启发式方法?说明用启发式方法解决实际问题的过程和步骤。 答：（1）对于结构不良问题，为得到近似可用的解，分析人员必须运用自己的感知和洞 察力，从与其有关而较基本的模型与算法中寻求其间的联系，从中得到启发，去发现适于解 决该问题的思路和途径，这种方法称为启发式方法。 （2）用启发式方法解决实际问题的过程和步骤：①系统观察和分析实际问题；②抽象 并明确提出问题；③建立启发式数学模型；④选择启发式策略，设计启发式方法，按照一定 的搜索规则反复迭代逼近模型最优可行解，直到得到满意解；⑤检验和修正模型及其满意解。
( ) 系统必趋向一个比较好的稳定状态，再把此稳定状态时 ri t 形成换位阵中元素为 l 的结点
连接起来，形成所求的最满意车辆调度线路。
4 / 13
圣才电子书 十万种考研考证电子书、题库视频学习平台
④根据所形成的最满意线路来选择车辆调度方案。 （3）推广到多目标情形：车辆优化的目标函数可以有很多个，如总运费最小，司机总 的驾驶时间最短，车辆满载行驶的时间最长等；而约束条件，如路径的最大输入输出流、车 载量、发车和收车约束等。也可以加入惩罚算子将约束条件转化为惩罚函数，利用多目标方 法进行求解。
18.2 在解决实际问题时应如何运用启发式策略?除本书上列出的几个启发式策略之外， 你认为还有什么样的策略可以使用?
答：在解决实际问题时，可根据实际问题的性质和要求来选用某一启发式策略；为得到 理想效果，也可将几个策略联合起来使用。除本书上列出的几个启发式策略之外，还有计算 机仿真、模拟策略、类比策略、近似策略等可以使用。
18.4 试说明 C-W 节约算法的基本思想，你认为还可用它解决哪些方面的问题?举例加 以说明。
答：（1）C-W 节约算法的基本思想（以旅行商问题为例）：优先考虑将节约值最大的弧 插入到旅行线路中，这样在满足访问若干城市各一次且仅一次的条件下，最大限度地缩短了 路程。
（2）举例。运用 C-W 节约算法：设 n 个不同用户为 n 个点，维修点为基点，n 个用户 点中从点 i 到点 j 的长度为工人骑摩托车的交通时间加上点 i 与点 j 维修时间总和的一半。
试拟定出一套求解的迭代步骤。 （2）你认为应如何将书中提出的模型和算法推广到多目标的情形。 答：（1）货运车辆优化调度算法的原理：最小费用最大流原理。求解步骤为：①仅考虑
重载点，运用表上作业法求出最优解作为原问题的可行解；②进行解的扩展和解的收缩，直 至得到可接受的可行解；③以该可接受的可行解为依据确定初始行车线路；④根据具体约束 条件进行调整，直至得到最优行车路线。求解过程框图如图 18-1 所示：
18.3 对在多台设备上加工多个工件的工件排序问题来说，应如何衡量不同排序方案的 优劣？你认为应有哪些准则?这些准则的适用条件是什么?请举出两个实例加以详细说明。
答：（1）应根据工期最短、成本最低、质量最优等优劣标准来衡量不同排序方案的优劣。 （2）设备充分利用、总加工时间最短等某一或某几种目标函数最优。
②将车辆调度的各种约束条件转化为约束能量函数为 E约 。
③神经网络计算：令时刻 t 神经元 i 的输出为 ri (t ) ，且 ri (t ) 只能取 0 或 1，令神经元
( ) i
的阈值为
Q i
，则输出能量为
E输
=
f
ri
(t
)
,
Q i
,
ij
，因此总的能量函数为 E总=E输 E约 。
如果 r (t + t ) = r (t ) ，其中 t 0 ，则该网络相对处于稳定状态。由于 E 0 ，且 E 有界，
18.7 表 18-1 给出了 12 种工件在设备 A 和 B 上的加工时间，试求： （1）若所有工件都先在设备 A 上加工，再在设备 B 上加工，试确定使总加工时间最短 的工件加工顺序，并计算总加工时间； （2）若工件 8～12 先在设备 B 上加工，再在设备 A 上加工，其他条件同上，试设计 一启发式算法，以计算最小总加工时间和安排相应的工件最优加工顺序。（提示：可考虑将 工件 1~7（要求先在设备 A 上加工，再在设备 B 上加工）和工件 8~12（要求先在设备 B 上加工，然后再在设备 A 上加工）这两组工件分别排序，再将二者按总加工时间尽量短的 要求组合起来。）
优先考虑将节约值最大的长度加入工作线路中去进行迭代。
18.5 试将 Norback 和 Love 提出的几何法与 C-W 节约算法进行比较。 答：（1）几何法：首先找出凸包，然后考查以不在旅行线路上的点为角顶，以线路上的 点的连线为对边的角的大小，选出最大者所对应的角顶，插入到旅行线路中，反复进行直至 形成哈密尔顿回路。 （2）C-W 节约算法：首先以某一点为基点，确定初始解，然后考查基点之外的其它点 的连线所构成的弧的节约值的大小，选出节约值最大者所对应的弧，插入到旅行线路中，直
（3）每个工件在 m 台设备加工都有一定的先后顺序，工件在不同设备的加工顺序不同
1 / 13
圣才电子书 十万种考研考证电子书、题库视频学习平台
的情况不作考虑以及信息掌握情况和资源约束等适用条件。 （4）举例。建筑施工流水作业问题：在不同的施工段上按一定的施工工艺进行施工，
圣才电子书 十万种考研考证电子书、题库视频学习平台
图 18-1
（2）修改后的迭代算法即神经网络算法。
①建立结合矩阵：将车辆经过的点包括源点看成神经网络的结点，即神经元，令神经元
数目为 N； i 神经元和 j 神经元的结合权值为ij ， j 神经元的输出为 rj 。
2 / 13
圣才电子书十万种考研考证电子书、题库视频学习平台
至旅行线路中包含所有的点。 18.6 说明本书所述货运车辆优化调度算法的原理和求解步骤，并绘出求解过程框图。
请简要回答以下问题。 （1）若有两种车型的车可用，书中提出的模型应怎样修改?在书中所提算法的启发下，
而施工工艺又由不同的施工工序组成，每道施工工序都要消耗一定的人工费用，机械台班和 材料费用，并且某些施工工序之间有一定的先后约束关系，如支起模板后才能浇注混凝土， 而此问题关注不同施工工序如何搭接排序组成一定施工工艺，使整个施工按照最短施工时间 保持一定施工节拍进行流水作业，同时消耗人、机、材等资源也合理。
圣才电子书
十万种考研考证电子书、题库视频学习平台
第 18 章 启发式方法
18.1 什么是启发式方法?说明用启发式方法解决实际问题的过程和步骤。 答：（1）对于结构不良问题，为得到近似可用的解，分析人员必须运用自己的感知和洞 察力，从与其有关而较基本的模型与算法中寻求其间的联系，从中得到启发，去发现适于解 决该问题的思路和途径，这种方法称为启发式方法。 （2）用启发式方法解决实际问题的过程和步骤：①系统观察和分析实际问题；②抽象 并明确提出问题；③建立启发式数学模型；④选择启发式策略，设计启发式方法，按照一定 的搜索规则反复迭代逼近模型最优可行解，直到得到满意解；⑤检验和修正模型及其满意解。
( ) 系统必趋向一个比较好的稳定状态，再把此稳定状态时 ri t 形成换位阵中元素为 l 的结点
连接起来，形成所求的最满意车辆调度线路。
4 / 13
圣才电子书 十万种考研考证电子书、题库视频学习平台
④根据所形成的最满意线路来选择车辆调度方案。 （3）推广到多目标情形：车辆优化的目标函数可以有很多个，如总运费最小，司机总 的驾驶时间最短，车辆满载行驶的时间最长等；而约束条件，如路径的最大输入输出流、车 载量、发车和收车约束等。也可以加入惩罚算子将约束条件转化为惩罚函数，利用多目标方 法进行求解。
18.2 在解决实际问题时应如何运用启发式策略?除本书上列出的几个启发式策略之外， 你认为还有什么样的策略可以使用?
答：在解决实际问题时，可根据实际问题的性质和要求来选用某一启发式策略；为得到 理想效果，也可将几个策略联合起来使用。除本书上列出的几个启发式策略之外，还有计算 机仿真、模拟策略、类比策略、近似策略等可以使用。
18.4 试说明 C-W 节约算法的基本思想，你认为还可用它解决哪些方面的问题?举例加 以说明。
答：（1）C-W 节约算法的基本思想（以旅行商问题为例）：优先考虑将节约值最大的弧 插入到旅行线路中，这样在满足访问若干城市各一次且仅一次的条件下，最大限度地缩短了 路程。
（2）举例。运用 C-W 节约算法：设 n 个不同用户为 n 个点，维修点为基点，n 个用户 点中从点 i 到点 j 的长度为工人骑摩托车的交通时间加上点 i 与点 j 维修时间总和的一半。
试拟定出一套求解的迭代步骤。 （2）你认为应如何将书中提出的模型和算法推广到多目标的情形。 答：（1）货运车辆优化调度算法的原理：最小费用最大流原理。求解步骤为：①仅考虑
重载点，运用表上作业法求出最优解作为原问题的可行解；②进行解的扩展和解的收缩，直 至得到可接受的可行解；③以该可接受的可行解为依据确定初始行车线路；④根据具体约束 条件进行调整，直至得到最优行车路线。求解过程框图如图 18-1 所示：
18.3 对在多台设备上加工多个工件的工件排序问题来说，应如何衡量不同排序方案的 优劣？你认为应有哪些准则?这些准则的适用条件是什么?请举出两个实例加以详细说明。
答：（1）应根据工期最短、成本最低、质量最优等优劣标准来衡量不同排序方案的优劣。 （2）设备充分利用、总加工时间最短等某一或某几种目标函数最优。
②将车辆调度的各种约束条件转化为约束能量函数为 E约 。
③神经网络计算：令时刻 t 神经元 i 的输出为 ri (t ) ，且 ri (t ) 只能取 0 或 1，令神经元
( ) i
的阈值为
Q i
，则输出能量为
E输
=
f
ri
(t
)
,
Q i
,
ij
，因此总的能量函数为 E总=E输 E约 。
如果 r (t + t ) = r (t ) ，其中 t 0 ，则该网络相对处于稳定状态。由于 E 0 ，且 E 有界，
18.7 表 18-1 给出了 12 种工件在设备 A 和 B 上的加工时间，试求： （1）若所有工件都先在设备 A 上加工，再在设备 B 上加工，试确定使总加工时间最短 的工件加工顺序，并计算总加工时间； （2）若工件 8～12 先在设备 B 上加工，再在设备 A 上加工，其他条件同上，试设计 一启发式算法，以计算最小总加工时间和安排相应的工件最优加工顺序。（提示：可考虑将 工件 1~7（要求先在设备 A 上加工，再在设备 B 上加工）和工件 8~12（要求先在设备 B 上加工，然后再在设备 A 上加工）这两组工件分别排序，再将二者按总加工时间尽量短的 要求组合起来。）
优先考虑将节约值最大的长度加入工作线路中去进行迭代。
18.5 试将 Norback 和 Love 提出的几何法与 C-W 节约算法进行比较。 答：（1）几何法：首先找出凸包，然后考查以不在旅行线路上的点为角顶，以线路上的 点的连线为对边的角的大小，选出最大者所对应的角顶，插入到旅行线路中，反复进行直至 形成哈密尔顿回路。 （2）C-W 节约算法：首先以某一点为基点，确定初始解，然后考查基点之外的其它点 的连线所构成的弧的节约值的大小，选出节约值最大者所对应的弧，插入到旅行线路中，直
（3）每个工件在 m 台设备加工都有一定的先后顺序，工件在不同设备的加工顺序不同
1 / 13
圣才电子书 十万种考研考证电子书、题库视频学习平台
的情况不作考虑以及信息掌握情况和资源约束等适用条件。 （4）举例。建筑施工流水作业问题：在不同的施工段上按一定的施工工艺进行施工，
