【作者】 王锡禄；

【导师】 夏尊铨；

【作者基本信息】 大连理工大学 ， 运筹学与控制论， 2000， 博士

【摘要】 具有拓扑结构的双层规划是生产与决策管理中经常遇到的问题。如路网设计、化工换热网络综合的优化，桁架结构设计与优化、工厂或车间与流水线的布局、卫星舱布局优化等都属于此类问题。由于此类问题属于NP-困难问题，缺乏最优性理论，因此目前已有的算法多为启发式、人机交互类算法。本文应用图论、群论、凸分析、不可微优化等学科的基本理论研究了具有拓扑结构的双层规划。取得的主要成果有： 1 依点到集的映射、集值映射、二元映射和分离定理等理论首次建立了 具有拓扑结构双层规划的数学模型 （BP） min F(x,y) s.t.x∈X y∈Arg min｛F(x,y)|y∈Ω(x)｝ 其上层规划为关于离散变量x的拓扑结构优化，下层规划是关于连续 变量的约束规划。 2 首次把图、置换群对图的作用、等价类、轨道等用于拓扑结构优化中， 把其可行域分解成有限多个子域，从而克服了长期困扰拓扑优化的时 断时续性质（on-off nature），为获得该类规划的全局最优解奠定了理 论基础。 3 依据上述理论研制了改进的遗传算法与LCABS算法，用于（BP）问 题的求解。 4 应用凸集分离定理、置换群对图集的作用、不动点集、轨道等理论首 次把卫星舱布局中的隐式约束（不干涉性与相容性）转化成等价的显 式表示的线形约束，首次建立了卫星舱布局优化的具有拓扑结构的双 层规划模型及全局优化算法。 5 首次建立了化工换热网络优化的具有拓扑结构的双层规划，并把它分 解为有限个子规划，给出了算法。在一定条件下论述了该算法收敛到 全局最优解。 6 首次建立车间作业调度问题的具有拓扑结构：的双层规划模型。新模 型将此类问题的三个主要因素：调度、批量与加工时间的优化归结在 一个模型内。更多还原

【Abstract】 The bilevel programming characted by topological struture optimiza- tion is ofen encountered in the process of production and management. For example, road net designment, heat exchange net design and optimization, truss structure design, the layout of workshops, assembly line design and the layout occured in satellite cables all belong to this type problems. since the problems are NP-hard, there lacks optimality theory , so the current so- lution procedures often turn to heuristic methods. The paper applies graph theory, group theroy, convex analysis, non-smooth optimization to study the problems and obtained the following results: 1 A bilelel programming model is constructed on the basis of point-valued mapping, set-valued mapping, and seperation theorem for the first time (BP) mm F(ai~,y) s.t. xEX ~ Arg min{F(x,y)Iy E ~2(a~)} where the upper level is about topological structure optimization(a~ is a topological structure varable), and the lower level is a constrained programming about continuous variable y. 2 Apply graph, the action of permutation group on a graph, equiva- lent class, orbit etc. for the first time to study topological structure optimization. Divide the domain into finite number of sub-domain, such overcome the on-off nature disturbing topological structure opti- niization, which also founds the theory basis for acheving the global optiniization solution for the problems. 3 Develop an improve generic algorithm and LCABS algorithm according to the above theories, by which an algorithm for (BP) is constructed. 4 Apply convex scperation theorem, the action of pcrmutaion group on a graph. stability set, orbit ~o study the layout of satellite cables, and 111 obtain an equivalent explicit form for the non-overlap and capacity constraints for the first time, and construct a bilevl programming for the problem. 5 Construct a bilevel programming charactered by topological structure for heat exchange net for the first time, and some conditions for global. solutions are also studied. 6 Construct for the first time a bilevel programming charactered by topo- logical structure fOr job-shop scheduling problems and the new model integrates the main three factors occured in the problem: scheduling, lot and start-time.更多还原