长方体装箱问题的非线性规划模型.doc

长方体装箱问题的非线性规划模型 现有一批立方体形状货物，要求装入一个集装箱中，装箱达到的要求为满足一定约束条件下体积的利用率最大化。为便于研究作如下假定：货物的几何中心即为其重心，货物的摆放必须与坐标轴平行（即在装箱过程中，要求立方体形状货物的宽、高、深均分别与集装箱的宽、高、深平行），不能斜放，也不能悬浮放置。装载约束条件为货物理论上可以放在容器的任意位置，但不能超出容器的容纳范围，也不能与其他货物交叠放置。 1 一般数学模型 给定个长方体物品的集合，每一个成方体物品的宽度、高度、深度分别是、、，。给定一个大的长方体箱子，它的宽度是，深度是，高度无限，要求将这个长方体的小物品装入箱子中，使小长方体物品的宽度方向、高度方向、深度方向分别与大的长方体箱子的宽度方向、高度方向、深度方向分别平行，并使得所用的大长方体箱子的高度最小。 采用的坐标系为三维笛卡尔坐标系，设坐标系以容器的宽度方向为轴，高度方向为轴，深度方向为轴，容器的左后下角为坐标原点。 令是决策变量，它的第个分量表示第个小的长方体物品的左后下角的坐标。定义集合的映射图如下： 其中的定义域是 。 令，则中元素的个数为。任意两个长方体的物品装箱时不重叠的充分必要条件是 显然，三维带形装箱问题能转化成以下的优化模型： Model General minimize subject to , , 这个数学模型是一个非光滑模型，因为它的约束条件是非正常函数。 3.2.2 光滑最优化描述 长方体物品相交即在装箱过程中能够重叠当且仅当他们在三个坐标轴上的投影都能够相交。我们分别用、和表示集合在轴、轴和轴上的投影，则 ， ， 。 容易验证 ， ， 。 由以上等价条件可将Model General等价的转化为以下形式： Model Absolute minimize subject to Model Absolute是一非凸非光滑优化模型，因为其可行集是非凸的。 由于，我们可以通过引进新的变量把Model Absolute转化为一个光滑的优化模型。引进变量，令，，定义函数， 如下所示： ， ， 其中 ，， ， 。 令，其中， ， 其中。则Model Absolute能转化为以下的光滑优化模型： Model NLP minimize subject to 为了得到Model NLP的一阶最优性条件我们引进以下记号 ， 其中 , ， ， 。 则能表示为如下的形式： ， ， 的Jacobian阵的转置为，为了计算在点的法锥，我们首先给出和的计算公式。令 ， ， ， ，，， 则 ， 其中 在的法锥是 ， 其中 ， 引理1（在点的法锥） 满足，，且，则在点的法锥能表示成如下形式 。 证明 根据Rockafellar和Wets(1998)的定理6.14，只需证明下式成立 (1) 令，则能写成或矩阵形式 ， 即 ， ， ， , (2) 。 (3) 由于，我们知，又有(3)及，即，所以得到。 由于，得到，由(2)得到，因为非奇异，我们得到（假设奇异，则至少一，这导致，或者，或者，这与已知条件矛盾）。 我们证明了(1)式的正确性，再由Rockafellar和Wets(1998)的定理6.14，我们得到 。 定理1（Model NLP 的一阶最优性条件） 是Model NLP的局部最优点，满足，，且，则存在向量满足。 证明 由Rockafellar和Wets(1998)的定理6.12知，由引理1得到结论。 3.2.3 数值试验结果 在Model NLP中，约束条件是一简单的箱式约束，它能表达成一般的不等式约束，所以我们可以将Model NLP表达成如下形式： minimize subject to 我们用增广拉格朗日（ALM）方法解决这一约束优化问题，它是解一系列含有参数和拉格朗日乘子的无约束优化问题： minimize ALM算法： 步1：给定，和；； 步2：解