二次分配问题及其线性化技术

内容概要

张惠珍，女，1979年生于山西省五台县，现上海理工大学管理学院讲师。山西财经大学经济学院毕业（经济学学士），成都理工大学信息工程学院毕业（工学硕士），上海理工大学管理学院毕业（管理学博士）。葡萄牙里斯本大学理学院访问学者，西班牙胡安卡洛斯大学统计与运筹系博士后。在《COMPUTERS AND OPERATIONS RESEARCH》、《ANNALSOF OPERATIONS RESEARCH》、《系统工程理论与实践》等国内外学术期刊上发表论文20余篇。主要研究方向为组合优化、智能优化等。马良，男，1964年生于上海，现上海理工大学管理学院教授、博士生导师、系主任。复旦大学数学系毕业（理学学士），（原）上海机械学院系统工程系毕业（工学硕士），上海交通大学管理学院毕业（管理学博士）。先后主持完成包括两项国家自然科学基金在内的各类科研项目20多项，发表论文200多篇，出版《蚁群优化算法》专著1部，主编出版“十一五”规划本科教材《基础运筹学教程》以及研究生教材《高级运筹学》各1部，白行开发研制运筹学／管理科学专业软件包1套。曾获上海市高校优秀青年教师、中国机械工业青年科技专家、宝钢优秀教师奖、上海市曙光学者、上海市育才奖等10多项荣誉称号和奖励。主要研究方向为系统工程、智能优化等。

书籍目录

前言第一章 预备知识  1.1 最优化问题及其分类  1.2 组合优化问题  1.3 算法及其分类  1.4 计算复杂性与NP完全问题第二章 二次分配问题  2.1 QAP简述  2.2 QAP模型    2.2.1 二次整数规划模型    2.2.2 迹模型    2.2.3 Kronecker内积模型    2.2.4 凹二次规划模型  2.3 QAP的目标函数均值  2.4 QAP的计算复杂性    2.4.1 QAP全局最优和近似最优的计算复杂性    2.4.2 QAP局部搜索的计算复杂性  2.5 QAP的渐进行为  2.6 扩展QAP问题    2.6.1 双二次分配问题    2.6.2 瓶颈二次分配问题    2.6.3 二次半分配问题    2.6.4 一般二次分配问题    2.6.5 多目标二次分配问题    2.6.6 二次三维分配问题    2.6.7 黑白二次分配问题  2.7 几种可转化为QAP的组合优化问题    2.7.1 旅行商问题    2.7.2 图的分割问题    2.7.3 最大团问题    2.7.4 图的同构    2.7.5 图的包装  2.8 二次分配问题的应用第三章 二次分配问题的求解方法  3.1 经典求解方法    3.1.1 分支定界法    3.1.2 割平面法    3.1.3 求解QAP的其他经典方法  3.2 启发式求解算法    3.2.1 模拟退火算法    3.2.2 遗传算法    3.2.3 蚁群算法    3.2.4 粒子群算法    3.2.5 禁忌搜索算法    3.2.6 贪婪随机自适应搜索过程    3.2.7 大洪水算法第四章 二次分配问题的线性化及其多面体描述  4.1 QAP线性化模型    4.1.1 Lawler QAP线性化模型    4.1.2 Kaufman-Broeckx类QAP线性化模型    4.1.3 Flow-Based QAP线性化模型    4.1.4 Frieze-Yadegar QAP线性化模型    4.1.5 Adams-Johnson 类 QAP线性化模型    4.1.6 QAP高阶模型  4.2 QAP的多面体描述第五章 二次分配问题的下界计算方法  5.1 Gilmore-Lawler类下界    5.1.1 二次分配问题线性化模型的结构特征    5.1.2 Gilmore-Lawler下界    5.1.3 基于缩减技术的QAP下界计算方法    5.1.4 基于再建模技术的QAP下界计算方法    5.1.5 基于匈牙利算法的QAP下界对偶上升求解方法  5.2 QAP线性化模型的线性松驰    5.2.1 Frieze-Yadegar模型和Adams-Johnson模型的线性松驰    5.2.2 Kaufman-Broeckx类模型的线性松驰  5.3 方差缩减下界计算方法  5.4 基于正交松驰的QAP下界计算方法  5.5 基于凸二次松驰的QAP下界计算方法  5.6 基于正定规划的QAP下界计算方法第六章 几种特殊二次分配问题及其求解  6.1 稀疏二次分配问题    6.1.1 稀疏二次分配问题的线性化    6.1.2 算例分析  6.2 对称二次分配问题    6.2.1 对称二次分配问题及其线性化模型    6.2.2 对称二次分配问题的多面体描述    6.2.3 非对称二次分配问题的对称化    6.2.4 算例分析参考文献

编辑推荐

张惠珍、马良编著的《二次分配问题及其线性化技术》以二次分配问题的线性化技术为基础，对所提出的二次分配问题求解方法不仅给出了相关数学证明，从理论的角度说明了各种方法的正确性，而且选用了二次分配基准问题库（QAPLIB）中的部分实例进行了解算，将计算结果与原有方法进行了比较，从实验的角度说明了本书提出的方法对二次分配问题的求解具有较好的性能。

作者简介

二次分配问题是一种易于描述却难于求解的典型组合优化问题，已被归人所谓的NP—难题。该问题不仅以不同的形式存在于工厂布局、作业车间调度、挡板布线等实际生活领域，而且综合了一大类组合优化问题的典型特征，是一个既有广泛的实际应用背景，又有重要理论研究价值的优化问题。

    二次分配问题目标函数中的二次项在一定程度上增加了问题的求解复杂度，通过一定方法将其二次项线性化，得到与原问题等价的（混合）整数规划模型，不仅会使问题的求解复杂度得到一定降低，能够应用既有的（混合）整数规划求解方法进行求解，而且当问题规模增大而难于求解时，可通过求解该（混合）整数规划模型的线性松弛，求得原问题最优解的下界值。

    《二次分配问题及其线性化技术》是作者张惠珍、马良近年来在对二次分配问题研究的基础上编写而成，着重介绍了以线性化技术为基础的二次分配问题的求解方法。书中从几种不同的角度探索了多种二次分配问题的求解新方法，并分别从理论和实验两方面讨论了各种方法的性能，为二次分配问题的求解提供了有效的基本解决方案和手段。

    本书内容充实，包含了大量较为新颖的材料，其中部分内容展现了作者近年来在二次分配问题研究上的最新成果。

    《二次分配问题及其线性化技术》可作为运筹学、计算数学、应用数学、计算机科学与工程、管理科学与工程等专业的高年级本科生、研究生和教师的参考书，对于从事最优化理论和方法的研究人员或科研人员，也有相应的参考价值。

图书封面

---

 二次分配问题及其线性化技术下载

---