多层规划的理论与算法研究

本文主要研究两层规划的几何性质、最优解的存在性、最优性条件及全局算法设计 等问题。主要工作如下： 第二章讨论多层线性规划的若干理论问题。从不同的角度详细讨论多层规划建模中 的有关问题。证明下层以最优值反应上层的两层线性规划可化归为线性Max-min问题， 进一步证明它与具有线性可分离约束的单层数学规划等价。对下层有多个平行子问题的 两层线性规划首次提出对偶可行解的概念，以凸分析为工具用统一的框架在较弱的假设 下给出该问题可行集和对偶可行集的明确面表示，并证明二者均是闭连通集。分别用反 例说明已有文献中关于线性二级价格控制问题及Naccache关于集合连通性有关的两个 结论不成立，并指出基于这些结论的若干需要重新考虑的问题。第三章讨论多层线性规 划的全局解法。证明几种求解两层线性规划的精确罚函数法是等价的，同时给出罚因子 初始值的确定和自适应增加机制，并基于罚问题约束集相同的特点给出该法的外逼近法 实现。将线性两层规划转化为参数凹极小化问题，基于此利用可行集连通的几何性质设 计出上升可行极点搜索法。充分利用可行集连通的几何性质，给出求解三层线性规划“第 k-最好”算法的一种实现。最后给出相关数值结果和分析。第四章讨论两层线性混合 整数规划问题。刻画了几种特殊问题的可行集，并讨论其最优解的存在性。讨论求解上 层变量是0-1的两层线性规划的分支定界法、多层规划法和遗传算法，并给出不同算法 间的数值结果比较。 第五章讨论两层规划最优解的存在性及最优性条件。给出两层规划不同解之间的关 系及两层规划强、弱最优解存在的充分条件。给出下层以最优值反应上层的两层规划是 凸规划的几个充分条件及基于此的最优性条件。说明直接基于下层最优值函数和下层问 题的KKT最优性条件给出的两层规划的FJ最优性条件是平凡成立的，并借助于部分 calm性讨论两层规划基于其等价单层问题关于特殊约束部分calm性的最优性条件。第 六章讨论非线性两层规划的算法设计。给出了基于下层对偶间隙求解两层规划罚函数法 的性质、收敛定理、全局实现以及与Stackelberg对策决策过程的联系；给出两层规划 的Lagrange型对偶问题与对偶定理。利用差分进化算法求解两层规划，数值结果表明 该法是可行而有效的。第七章讨论多层规划和多目标规划的关系。构造出以任意给定的 向量d1，d2为价格系数的两层规划，其最优解不是相应双目标规划的有效解。给出多层 规划最优解是有效的充分条件及判断其无效的方法。提出在保持递阶结构前提下的递阶 交互决策有效化方法，其适用于下层有多个子问题的两层线性规划问题。