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

论文摘要

本文从一个新的视角来研究一类二维装箱问题—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算法求解了几个算例。

论文目录

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