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