基于改进PSRS的并行0-1规划算法研究及其应用

摘要

并行计算技术的发展与成熟为最优化问题的快速求解带来了新的机遇和挑战。随着并行计算机与并行算法理论的发展，近年来，并行0-1整数规划求解算法的研究与应用引起极大关注，并取得了大量研究成果。
　　 本文对0-1整数规划问题的模型和现有的求解方法进行了研究与分析，详细讨论了该问题的有效求解方法:目标排序法。分析了该方法的核心计算所在，并讨论了该算法进行任务划分的可能性。再对PSRS方法进行了改进，将该方法引入0-1整数规划的求解中，并针对其特殊性对PSRS的排序步骤和结果进行了修改，完成了0-1整数规划问题求解任务的均衡划分。用改进的PSRS和目标排序法设计了一个求解0-1整数规划问题的并行算法。为验证算法有效性，通过建立物流配送中心选址问题的0-1规划模型，并采用所提算法求解该模型，数值试验结果表明，所提算法能有效求解大规模0-1规划问题，且具有较好的加速比和可扩展性。
　　 综上，本文阐述了基于目标排序和改进PSRS设计0-1整数规划并行求解算法的思想和步骤，并基于MPI给出了算法的具体实现，同时应用于求解电子商务中的物流配送中心选址问题。为整数规划的并行算法设计与实现提供了新的思路。

目录

声明

摘要

第一章 绪论

1．1 课题研究意义

1．2 国内外研究现状

1．2．1 并行计算的发展情况

1．2．2 并行计算的优点

1．2．3 0-1整数规划

1．3 本文主要工作

1．4 论文的组织结构

第二章 相关知识简介

2．1 0-1规划概述

2．1．1 线性规划的介绍

2．1．2 0-1整数规划问题

2．1．3 0-1整数规划的通常解法

2．2 MPI并行程序简介和并行计算的优势

2．2．1 MPI(Messages passing interface)简介

2．2．2 MPI的产生及发展

2．2．3 并行计算的优势

第三章 基于改进PSRS算法的0-1规划并行算法实现

3．1 0-1规划的解法分析

3．1．1 0-1规划问题的提出

3．1．2 根据问题建立0-1规划模型

3．1．3 0-1规划求解方案

3．1．4 0-1规划求解流程图

3．2 0-1规划解法的算法的具体实现

3．2．1 主要变量的定义

3．2．2 主要的功能实现

3．3 0-1规划解法的串行算法的弊端

3．3．1 算法上的弊端

3．3．2 资源利用上的弊端

3．4．解0-1规划的并行算法的分析

3．4．1 改进的PSRS算法介绍

3．4．2 基于改进的PSRS算法的并行0-1规划求解方案

3．4．3 并行程序流程图

3．5 PSRS算法的0-1规划并行算法的具体实现(MPI实现)

3．5．1 MPI并行运算环境

3．5．2 Windows下安装MPICH2和配置运行环境

3．5．3 MPI的具体实现

第四章 并行0-1规划算法在电子商务配送中心选址问题的应用

4．1 电子商务模型介绍

4．1．1 电子商务问题的提出

4．1．2 建立模型

4．2 串行运算的实现及结果

4．2．1 实现和结果

4．2．2 串行运算结论说明

4．3 MPI并行计算的实现及结果

4．3．1 实现以及结果

4．3．2 并行运算结论说明

4．4 中大规模数值实验结果

第五章 总结与展望

5．1 结论

5．2 展望

参考文献

致谢

攻读硕士学位期间发表的学术论文