混合整数双层线性规划的性质与算法研究

论文摘要

本文讨论的主要内容是双层规划中的混合整数双层线性规划。通过分析混合整数双层线性规划的数学模型、可行集的性质和最优性条件,对于不同类型的混合整数双层线性规划,给出了寻找最优解的算法。主要工作如下:论文首先介绍了双层规划产生的背景、定义、主要特点、复杂性、应用和研究现状;给出了双层线性规划的数学模型、基本定义和最优性条件,并详细讨论了混合整数双层线性规划的模型特点、解的存在性情况、基本理论以及应用。对上层变量为0-1型变量和下层变量为连续型变量的混合整数双层线性规划问题,给出了它的基本模型,定义以及基本性质,并利用辅助规划的对偶理论和组合最优化思想设计了一种判别准则,从而提出了求解全局最优解的枚举法;此外,将上层目标函数转化为参数约束,结合下层规划构造了一个混合整数线性规划,利用分支定界思想,通过处理一系列混合整数线性规划设计了另一种不同思想的枚举法,并通过对两种不同枚举法的对比,分析了其各自的优点和缺点。对于上、下层变量都是0-1型变量的混合整数双层线性规划,在给出其基本模型、定义和性质的基础上,利用问题模型的特殊性构造了一个便于求解的定界函数,并结合深度优先的分支准则提出了一个分支定界算法。对于上层变量为0-1型变量,下层变量为一般整数变量的混合整数双层线性规划给出了界的设计,利用相同的分支准则也设计了一个分支定界算法。本文的另一个主要内容是对上、下层变量都是0-1型变量的多下层混合整数双层线性规划问题进行了探讨。在给出其模型、定义、性质和基本理论的基础上,对定界函数进行了设计,并结合其下层之间的相互关系设计了一种分支准则,由此提出了一个求解此类问题的分支定界算法。最后,对论文所做的工作进行了总结,并对以后的工作进行了展望。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 引言
• 1.2 双层规划
• 1.3 混合整数双层线性规划问题的研究概述
• 1.4 本文的主要工作
• 2 离散/连续型混合整数双层线性规划
• 2.1 问题的基本模型与定义
• 2.2 枚举法一的理论与步骤
• 2.3 枚举法二的理论与步骤
• 2.4 小结
• 3 离散/离散型混合整数双层线性规划
• 3.1 上、下层变量都是0-1型变量的混合整数双层线性规划
• 3.2 上层变量都是0-1型变量,下层变量都是离散型变量的混合整数双层线性规划
• 3.3 小结
• 4 多下层混合整数双层线性规划
• 4.1 问题的表述
• 4.2 界的设定与分支准则的选择
• 4.3 算法与算例
• 4.4 小结
• 5 总结
• 致谢
• 攻读硕士期间发表的论文
• 参考文献