第十四章 运筹学中的启发式方法 第一节 启发式方法的概念 第二节 应用问题举例 第三节运筹学案例介绍 3
3 第十四章 运筹学中的启发式方法 第一节 启发式方法的概念 第二节 应用问题举例 第三节 运筹学案例介绍
第一节启发式方法的概念 一、启发式方法的提出 本课程前面各章讨论了一些常用的优化模型， 研究了相应求解的标准算法。运用这些模型和算 法能有效地解决很多实际问题，得出问题的最优 解。但是，标准模型和算法应用上常常受到很大 局限，标准模型和算法主要适用于解决具有良性 结构的问题 4
4 第一节 启发式方法的概念 一、启发式方法的提出 本课程前面各章讨论了一些常用的优化模型， 研究了相应求解的标准算法。运用这些模型和算 法能有效地解决很多实际问题，得出问题的最优 解。但是，标准模型和算法应用上常常受到很大 局限，标准模型和算法主要适用于解决具有良性 结构的问题
第一节启发式方法的概念 所谓良性结构的问题，是指问题的结构比较 清晰，所含各元素之间的关系明确，边界清楚 容易为人们所认识，能够比较方便地通过建模和 使用一定的算法求出问题的解答。概括地说良性 结构问题具有以下特征： (1)能建立起反映该问题性质的一种“可接 受”模型。与问题有关的主要信息可纳入模型之 中 (2)模型所需要的数据能够得到
5 所谓良性结构的问题，是指问题的结构比较 清晰，所含各元素之间的关系明确，边界清楚， 容易为人们所认识，能够比较方便地通过建模和 使用一定的算法求出问题的解答。概括地说良性 结构问题具有以下特征： (1)能建立起反映该问题性质的一种“可接 受”模型。与问题有关的主要信息可纳入模型之 中。 (2)模型所需要的数据能够得到。 第一节 启发式方法的概念
第一节 启发式方法的概念 (3)有判定解的可行性和最优性（或满意性） 的明确准测 (4)模型可解，能拟定出求解模型的程序性 步骤，而且得出的解一般就是问题的可行方案。 (⑤)求解工作所需的计算量不过大，所需费 用不过多。 很多实际问题不具有良性结构，当套用传统 的运筹学方法去处理时，就难以得到满意的效果。 6
6 (3)有判定解的可行性和最优性(或满意性) 的明确准则。 (4)模型可解，能拟定出求解模型的程序性 步骤，而且得出的解一般就是问题的可行方案。 (5)求解工作所需的计算量不过大，所需费 用不过多。 很多实际问题不具有良性结构，当套用传统 的运筹学方法去处理时，就难以得到满意的效果。 第一节 启发式方法的概念
第一节启发式方法的概念 这时，与其偏离事实，忽略或修正某些重要 的条件，勉强使用某种标准模型而使问题得到简 化以易于求解，还不如保持问题的本来面目，建 立基本符合问题实际情况的非标准模型。前者虽 可用已有的标准算法求解，但由于问题的模型失 真，得到的解通常难以付诸实施；后者由于模型 涉及因素多，结构复杂，而与传统的标准模型相 去甚远，难以套用已有的标准算法 7
7 这时，与其偏离事实，忽略或修正某些重要 的条件，勉强使用某种标准模型而使问题得到简 化以易于求解，还不如保持问题的本来面目，建 立基本符合问题实际情况的非标准模型。前者虽 可用已有的标准算法求解，但由于问题的模型失 真，得到的解通常难以付诸实施；后者由于模型 涉及因素多，结构复杂，而与传统的标准模型相 去甚远，难以套用已有的标准算法。 第一节 启发式方法的概念
第一节启发式方法的概念 在后面这种情况下，为得到可用的近似解， 分析人员必须运用自已的感知和洞察力，从与其 有关而较基本的模型及算法中寻求其中的联系 从中得到启发，去发现可用于解决该问题的思路 和途径，人们称这种方法为启发式方法，用这种 方法建立的算法为启发式算法。 8
8 在后面这种情况下，为得到可用的近似解， 分析人员必须运用自己的感知和洞察力，从与其 有关而较基本的模型及算法中寻求其中的联系， 从中得到启发，去发现可用于解决该问题的思路 和途径，人们称这种方法为启发式方法，用这种 方法建立的算法为启发式算法。 第一节 启发式方法的概念
第一一节 启发式方法的概念 二、启发式方法的特点 由上可知，启发式方法是寻求解决问题的 种方法和策略；当然，它也可以是面向某种具体 问题的一种求解手段。启发式方法建立在经验和 判断的基础上，体现了人的主观能动作用和创造 力 用启发式方法解决问题时强调“满意”，常 常是得到“满意解”，决策者就认为可以了，而 不去苛求最优性和探求最优解 9
9 二、启发式方法的特点 由上可知，启发式方法是寻求解决问题的一 种方法和策略；当然，它也可以是面向某种具体 问题的一种求解手段。启发式方法建立在经验和 判断的基础上，体现了人的主观能动作用和创造 力。 用启发式方法解决问题时强调“满意” ，常 常是得到“满意解” ，决策者就认为可以了，而 不去苛求最优性和探求最优解。 第一节 启发式方法的概念
第一节启发式方法的概念 之所以如此，其原因主要是 (1)有很多问题不存在严格最优解（例如目标 之间相互矛盾的多目标决策问题，一般的多属性 评价问题等)，这时，对目标和属性的满意性常 比“最优性”更能准确地描述人们的意愿和选择 行为。 (2)对有些问题，要得到最优解需花费过大 的代价，不合算。 10
10 之所以如此，其原因主要是： (1)有很多问题不存在严格最优解(例如目标 之间相互矛盾的多目标决策问题，一般的多属性 评价问题等)，这时，对目标和属性的满意性常 比“最优性”更能准确地描述人们的意愿和选择 行为。 (2)对有些问题，要得到最优解需花费过大 的代价，不合算。 第一节 启发式方法的概念
第一节启发式方法的概念 (3)从实际决策的需要出发，有时不必要求 解答具有过高的精度 假定为解决某类问题设计了一个算法，它能 用于求解所有这类问题，而且获得最优解的计算 工作量可表示为这类问题“大小”的多项式函数， 就称这个算法是确定型的多项式算法，简称为多 项式算法或有效算法。 11
11 (3)从实际决策的需要出发，有时不必要求 解答具有过高的精度。 假定为解决某类问题设计了一个算法，它能 用于求解所有这类问题，而且获得最优解的计算 工作量可表示为这类问题“大小”的多项式函数， 就称这个算法是确定型的多项式算法，简称为多 项式算法或有效算法。 第一节 启发式方法的概念
第一节启发式方法的概念 很多“组合优化”问题（如设施定位问题 旅行售货员问题、多个工件在多台设备上的加工 排序问题等)不存在多项式算法，欲求其最优解 需要花费巨大的代价。 用启发式方法求解问题是通过迭代过程实现 的，因而需拟定出一套科学的求解搜索规则。 12
12 很多“组合优化”问题(如设施定位问题、 旅行售货员问题、多个工件在多台设备上的加工 排序问题等)不存在多项式算法，欲求其最优解 需要花费巨大的代价。 用启发式方法求解问题是通过迭代过程实现 的，因而需拟定出一套科学的求解搜索规则。 第一节 启发式方法的概念