生产调度混合整数线性规划模型的可行解域分析

论文摘要

无论是在科学研究还是在工程实际中,最优化问题都有着重要的研究价值。因此,学者们对于最优化问题非常重视。回顾以往,上世纪中叶起,最优化理论与方法的研究和应用有了突飞猛进的发展。到如今,凭借先进的硬件与软件保证,人们可以有效求解最优化问题,数值计算不再是瓶颈。简单地说,最优化问题就是在问题的可行解域中寻找其最佳解。不同的算法有着不同的可行解域寻优方法。然而在最优化问题的建模过程中,由于问题的复杂性、信息的不完整性以及不可避免的人为疏忽错误,我们往往难以全面准确地描述问题。优化模型有可能因为矛盾约束、违背约束等原因而不存在可行解域。如果不存在可行解域,任何高效的寻优算法都无能为力。于是,模型的可行解域分析,日益引发众多学者的关注。虽然当前有关模型可行解域的方法和结论相继出现,但是大多是针对线性规划的,而且相关的数学方法无法照搬于实际应用。实际上,数学思想与工程实际,二者相得益彰。运用数学分析,可以科学地解决实际问题；结合工程实际,数学方法可以得到合理实践。本文正是以0-1混合整数线性规划（MILP）的炼油厂生产调度模型为研究背景,在系统工程思想指导下,进行MILP的可行解域分析。模型的可行解域分析包含两方面问题。第一方面问题是可行性分析,即通过判断模型是否存在可行解域来确定模型的可行性状态,如果存在可行解域则模型是可行的,如果不存在可行解域则模型是不可行的：第二方面问题是不可行性分析,找到造成模型不可行的症结所在,并采取措施修正模型使其出现可行解域。在这两方面问题的基础上,本文主要进行了以下的研究工作：首先,介绍基于事件逻辑的优化调度模型,并建立一个具体的实例模型,然后进行模型的参数分析、约束分析以及结构分析,并归纳调度规则,为后续章节的可行解域分析做准备。其次,进行模型的可行性分析。首先给出诊断模型可行性的流程与方法。然后针对0-1MILP模型,结合生产调度特点,给出一种基于规则分支的分支定界算法,旨在进行模型可行性测试。应用本算法进行测试,可以减少需要搜索的分支,从而缩小搜索域。在模型存在可行解域时,得到一个可行解作为以后执行模型寻优算法的初始解。最后通过实例分析,验证本测试算法的有效性。最后,进行不可行模型的不可行性分析。首先在前人有关最小矛盾约束集合（IIS）的工作基础上,利用调度模型特点,给出基于约束分组的两阶段IIS方法,用于寻找不可行模型的一个IIS。相比一般寻找IIS的方法,本方法更适合实际情况而且更有效。然后,在Amaral等人的一般模型修正方法的基础上,考虑参数限定因素,给出参数限定的模型修正方法,使得数学方法可以应用于实际模型约束中有参数限制的情况。最后,针对0-1MILP模型,给出基于IIS的不可行模型的分析诊断方法。通过本方法的分析,可以找到造成模型不存在可行解域的问题所在,再进行参数调整使其出现可行解域,并通过实例分析验证分析方法的效用。文章最后对研究工作进行了总结,明确了进一步工作的任务,为下一步的研究提供参考。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题背景和意义
• 1.2 优化模型可行解域分析的研究现状
• 1.2.1 寻找模型的可行解
• 1.2.2 不可行性分析方法
• 1.2.3 不可行模型修正方法
• 1.3 存在的问题
• 1.4 本文的主要工作
• 第二章 0-1变量混合整数线性规划形式的生产调度模型
• 2.1 引言
• 2.2 生产调度
• 2.2.1 生产调度概述
• 2.2.2 生产调度分类
• 2.3 0-1MILP生产调度优化模型
• 2.3.1 模型形式
• 2.3.2 实例模型
• 2.3.3 模型约束分析和参数分析
• 2.3.4 模型结构分析
• 2.4 连续生产过程的调度规则
• 2.5 本章小结
• 第三章 模型的可行性分析
• 3.1 引言
• 3.2 可行性诊断方法
• 3.2.1 可行性诊断流程
• 3.2.2 可行性诊断方法
• 3.3 可行性测试算法
• 3.3.1 分支定界算法
• 3.3.2 可行性测试的分支定界算法
• 3.3.3 数值例子
• 3.3.4 生产调度模型实例实验
• 3.4 本章小结
• 第四章 不可行模型的不可行性分析
• 4.1 引言
• 4.2 常见错误
• 4.2.1 模型错误
• 4.2.2 数据错误
• 4.3 不可行模型的IIS分析方法
• 4.3.1 IIS方法
• 4.3.2 基于约束分组的两阶段IIS方法
• 4.4 不可行模型的约束修正研究
• 4.4.1 模型约束修正研究的必要性
• 4.4.2 一般修正方法
• 4.4.3 参数限定的模型约束修正方法
• 4.5 基于IIS的模型不可行性分析诊断方法
• 4.5.1 诊断方法思想
• 4.5.2 诊断方法描述
• 4.5.3 数值例子
• 4.5.4 生产调度模型实例实验
• 4.6 本章小结
• 第五章 结论与展望
• 5.1 本文主要工作总结
• 5.2 进一步的工作
• 参考文献
• 致谢
• 攻读硕士学位期间参与的项目
• 学位论文评阅及答辩情况表