学位论文 > 优秀研究生学位论文题录展示

二维装箱问题的非线性优化方法

作　者: 于洪霞
导　师: 张立卫
学　校: 大连理工大学
专　业: 运筹学与控制论
关键词: 二维装箱问题一阶最优性条件凸集分离定理非线性Lagrange算法条件数增广Lagrange算法
分类号: O224
类　型: 博士论文
年　份: 2006年
下　载: 616次
引　用: 3次
阅　读: 论文下载

内容摘要

本文从一个新的视角来研究一类二维装箱问题—2SP(two-dimensional strip packingproblem),旨在给出各种2SP问题的非线性优化模型并设计求解方法。本文的最优化模型的最优性条件依据拟可微分析和变分分析建立,计算方法采用非线性Lagrange方法。主要结果可概括如下: 1.第2章,对d(d是正整数)维空间的装箱问题进行了讨论。首先给出了d维空间一般形状物品装箱问题的数学模型,然后具体到d—维的矩形体和球体的特殊情形。给出了矩形体图元装箱问题的一个不可微优化模型,该模型是一拟可微优化模型,用拟可微优化的理论建立了该模型的一阶最优性条件。然后将其转化为一个光滑的优化模型,用变分分析中的最优性理论建立了该光滑模型的最优性必要条件。对球体图元的装箱问题直接给出光滑的优化模型,依据变分分析的最优性理论建立了最优性必要条件。 2.第3章,主要研究各种二维装箱问题(2SP)的非线性优化模型。首先用两种不同的方式为图元为矩形的2SP问题建立了数学模型。前一种方式基于两个矩形位置关系的数学表述,给出了一个光滑优化模型,依据非线性规划的最优性理论建立了该优化问题的最优性必要条件。后一种方式直接从两个矩形不相交的条件出发给出了一个不可微模型并用拟可微理论建立了最优性条件。然后,将不可微模型转化为一个非线性规划模型,用变分分析的最优性理论建立了最优性必要条件。将光滑模型与非线性规划模型进行了比较,后者优于前者。此外,还分别对圆形、三角形、多边形这些特殊形状图元的装箱问题进行了研究。以凸集分离定理为基础,依据多边形的几何特性给出了三角形和多边形图元装箱问题的不可微模型,并用拟可微理论为这些模型建立了一阶最优性条件。 3.第4章,考虑的是求解二维装箱问题的非线性优化模型的数值算法。首先针对只含有不等式约束的非线性规划问题提出了一个修正Lagrange函数,分析了该函数具有很好的性质。基于该修正Lagrange函数给出了一个对偶算法,即非线性Lagrange算法。对这一算法给出了精细的收敛性结果,证明了存在罚参数的一个阈值,当罚参数小于这个阈值时,算法收敛。此外,对修正Lagrange函数的Hesse阵的条件数进行了估计,结果表明在实际计算时,罚参数不能取的太小。最后,将所提出的非线性Lagrange算法和经典的增广Lagrange算法分别用于求解圆形图元和矩形图元的二维装箱问题并就几个例题给出计算结果。 4.第5章,将二维装箱问题的研究结果应用于集装箱码头关于货船的泊位分配问题。将泊位分配问题描述为一个带约束的二维装箱问题,应用增广Lagrange算法求解了几个算例。

全文目录

中文摘要  4-5
Abstract  5-9
1 绪论  9-21
  1.1 装箱问题的应用背景  9-10
  1.2 研究现状  10-17
    1.2.1 有的数学模型  10-12
    1.2.2 已有的算法  12-17
  1.3 装箱问题与最优化  17-18
  1.4 本文的主要工作  18-21
2 d维装箱问题的数学模型  21-37
  2.1 预备知识  21-26
  2.2 矩形体图元装箱问题  26-33
    2.2.1 不可微模型及最优性条件  26-30
    2.2.2 光滑模型及最优性条件  30-33
  2.3 球体图元装箱问题的NLP模型及最优性条件  33-37
3 二维装箱问题  37-63
  3.1 矩形图元装箱问题  37-49
  3.2 圆形图元装箱问题  49-52
  3.3 三角形图元装箱问题  52-57
  3.4 多边形图元装箱问题  57-63
4 算法  63-93
  4.1 非线性Lagrange算法  63-84
    4.1.1 引言  63-64
    4.1.2 预备知识  64-66
    4.1.3 F_σ(x，λ)的性质与对偶算法的收敛性  66-78
    4.1.4 ▽_x~2F_σ(x，λ)的条件数  78-82
    4.1.5 数值例子  82-84
  4.2 增广Lagrange算法及其数值结果  84-93
5 二维装箱问题的一个应用  93-98
  5.1 泊位分配问题的数学模型  93-94
  5.2 例子  94-98
结论  98-99
参考文献  99-105
创新点摘要  105-106
附录A 符号说明  106-107
攻读博士学位期间发表学术论文情况  107-108
致谢  108-109
大连理工大学学位论文版权使用说明书  109

相似论文

非线性二层规划的过滤信赖域算法与乘子法,O221.2
MIMO系统信道测试及预编码技术研究,TN919.3
凸集的条件数及其相关性质,O174.13
基于块Broyden方法的并行预处理技术的研究,O241.7
一类反对称特征值问题的向后误差和条件数,O241.6
WSN节点定位中不适定问题的研究,TN929.5
PP扁丝成型传热分析及其微结构和拉伸性能研究,TQ325.14
预测控制器设定值柔化因子的在线调整,TP13
广义特征值和奇异值问题的统计条件数估计,O241
基于特征点的图像配准方法及其应用,TP391.41
半定规划问题的两种数值解法,O221
两类晶格材料模型的快速算法研究,O241.82
无约束优化的最优性条件与组合二次极大化问题的研究,O224
利用混合单亲遗传算法求解二维装箱问题,O224
扰动离散Lyapunov矩阵方程,O151.21
盲信号分离算法及其应用研究,TN911.7
不精确高斯牛顿法的局部收敛性质,O224
求解大型离散方程预处理方法的研究,O241.6
基于B样条的有限元法及有限体积法,O241.5
基于PageRank排序算法改进的若干研究,TP393.092
标度整体最小二乘问题及对称代数Riccati方程的扰动分析及条件数,O241.6