学位论文 > 优秀研究生学位论文题录展示

二次分配问题算法研究

作　者: 张惠珍
导　师: 马良
学　校: 上海理工大学
专　业: 管理科学与工程
关键词: 二次分配问题线性化下界匈牙利算法半拉格朗日松弛
分类号: TP301.6
类　型: 博士论文
年　份: 2009年
下　载: 213次
引　用: 0次
阅　读: 论文下载

内容摘要

二次分配问题是一种易于描述却难于求解的典型组合优化问题，已被归入NP-hard问题。二次分配问题不仅以不同的形式存在于工厂布局，作业车间调度，挡板布线等实际生活领域，而且综合了一大类组合优化问题的典型特征，它是一个既有广泛的实际应用背景，又有重要的理论研究价值的优化问题。随着二次分配问题实例规模的增长，其解空间呈现组合爆炸特征，因而通常在多项式时间内无法求得其最优解。过去几十年，由于二次分配问题的高度求解复杂性，已激发了人们对优化技术的研究。因此，研究二次分配问题的求解方法对优化技术和二次分配问题自身的发展有着重要意义。本文着重研究了以线性化技术为基础的二次分配问题的求解方法，具体包括：(1)详细讨论了基于匈牙利算法的二次分配问题的最优目标函数值的下界求解技术；(2)对原有二次分配问题的下界求解方法和二次分配问题线性化模型进行深入研究的基础上，提出三种基于线性化技术的二次分配问题求解新方法；(3)对输入矩阵(流矩阵和距离矩阵)中存在零元素的二次分配问题的求解进行了探讨，为该类特殊二次分配问题的求解提供了新的解决手段；(4)提出使用半拉格朗日算法求解二次分配问题的方法，这为有效求解二次分配问题提供了一种新的解决方案。本文对所提出的二次分配问题求解方法不仅给出了其数学证明，从理论的角度说明了各种方法的正确性，而且选用了二次分配基准问题库(QAPLIB)中的部分实例进行了计算，将计算结果与原有方法进行比较，从实验的角度说明了本文提出的方法对二次分配问题的求解具有较优的性能。

全文目录

摘要  5-6
ABSTRACT  6-9
第一章绪论  9-13
  §1.1 研究背景  9
  §1.2 本文主要研究内容  9-13
第二章二次分配问题  13-47
  §2.1 组合优化问题  13-14
  §2.2 算法及其分类  14-15
  §2.3 计算复杂性与 NP 完全问题  15-18
  §2.4 二次分配问题  18-46
    §2.4.1 QAP 模型  18-21
    §2.4.2 QAP 的计算复杂性  21-25
    §2.4.3 QAP 的线性化  25-30
    §2.4.4 QAP 的多面体描述(QAP Polytopes)  30-32
    §2.4.5 QAP 的下界计算方法  32-36
    §2.4.6 扩展 QAP 问题  36-39
    §2.4.7 QAP 的求解方法  39-45
    §2.4.8 QAP 的渐进特性(The Asymptotic Behavior of The QAP)  45-46
  §2.5 小结  46-47
第三章基于匈牙利算法的 QAP 对偶上升求解法  47-67
  §3.1 概述  47
  §3.2 二次分配问题线性化模型的结构特征  47-51
  §3.3 基于匈牙利算法的 QAP 下界对偶上升求解方法  51-61
    §3.3.1 匈牙利算法  51-52
    §3.3.2 几种基于匈牙利算法的 QAP 对偶上升求解法  52-61
  §3.4 算例分析  61-66
  §3.5 小结  66-67
第四章几种求解二次分配问题的新方法  67-91
  §4.1 概述  67
  §4.2 基于 Gilmore-Lawler 下界的 QAP 线性化模型  67-75
    §4.2.1 Gilmore-Lawler 下界的等价形式  67-69
    §4.2.2 QAP 问题的 Gilmore-Lawler 线性化模型  69-71
    §4.2.3 算例分析  71-75
  §4.3 Adams-Johnson 线性化模型的缩减与改进  75-85
    §4.3.1 Adams-Johnson 线性化模型的有效缩减  75-78
    §4.3.2 算例分析  78-85
  §4.4 一种 QAP 线性化新方法  85-88
    §4.4.1 一种 QAP 线性化新模型  85-88
    §4.4.2 算例分析  88
  §4.5 小结  88-91
第五章稀疏二次分配问题及其求解  91-105
  §5.1 概述  91
  §5.2 稀疏二次分配问题的线性化  91-99
  §5.3 算例分析  99-104
  §5.4 小结  104-105
第六章二次分配问题的半拉格朗日求解法  105-119
  §6.1 概述  105
  §6.2 拉格朗日松弛方法  105-106
  §6.3 半拉格朗日松弛方法(Semi-Lagrangian Relaxation)  106-110
  §6.4 求解 QAP 问题的半拉格朗日算法  110-114
    §6.4.1 QAP 的半拉格朗日松弛及其对偶问题  110-112
    §6.4.2 QAP 的半拉格朗日松弛的核问题  112-114
    §6.4.3 求解 QAP 的半拉格朗日松弛对偶问题的算法  114
  §6.5 算例分析  114-117
  §6.6 小结  117-119
第七章结论与展望  119-121
  §7.1 全文总结  119-120
  §7.2 进一步的工作  120-121
参考文献  121-133
在读期间公开发表的论文和承担科研项目及取得成果  133-135
致谢  135

二次分配问题算法研究

内容摘要

全文目录

相似论文