第４８卷第２期
大连理工大学学报
Ｖ０１．４８，Ｎｏ．２Ｚ００
８年３月ＪｏｕｒｎａｌｏｆＤａｌｉａｎＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ
Ｍａｒ．２
０
０
８
文章编号：１０００－８６０８（２００８）０２—０３０８－０５
二维装箱问题非线性规划模型和算法
于洪霞１’２，
张绍武３，张立卫¨
（１．大连理工大学应用数学系。辽宁大连
１１６０２４，
２．上海电力学院数理系．上海
２０００９０；
３．大连理工大学电子与信息工程学院，辽宁大连１１６０２４）
摘要：二维装箱问题是具有广泛应用背景的一类组合优化问题，这类问题是ＮＰ难问题，很难得到精确解．将二维装箱问题表示为一个非线性规划模型，用变分分析中切锥的概念建立了这一优化问题的一阶最优性条件．给出了求解这一优化问题的增广Ｌａｇｒａｎｇｅ方法．并求解了具体问题．数值实验表明增广Ｌａｇｒａｎｇｅ方法适合求解该问题．对于不超过１０个物品的装
箱问题可以求得精确解．
关键词：二维装箱问题；一阶最优性条件；增广Ｌａｇｒａｎｇｅ方法中图分类号：０２２１．２
文献标志码：Ａ
０
引
言
点，每个小矩形物品左下角坐标用（ｚ，，Ｙｉ）表示，二维装箱问题可以分为两类：一类是给定数则每个小矩形的内部可以表示为
量不限大小固定的容器，目标是使用最少数量的Ｓｆ（ｚｆ，Ｙｆ）＝｛（比，，．，）∈Ｒ２”ｌ
容器装完所有的物品；另一类是给定一个宽度为ｚｆ＜乱ｆ＜ｚｆ＋ｌｆ，有限数值的矩形容器，它的高度不限，要求将所有Ｙｆ＜训ｉ＜Ｙｆ十ｈｆ）
物品放入该容器中，并取得最小的放置高度，使容令Ｈ一｛（ｉ，Ｊ）Ｉｉ∈．厂，＿『∈．厂，ｉ＜Ｊ），则ＩＨｌ＝器利用率最高．本文只考虑第二类装箱问题．
ｎ（ｎ一１）／２，任何两个矩形物品不重合可以表示为
在计算机科学和工业领域中，装箱问题有着ｓｆ（ｚｉ，Ｙ；）ｎＳｊ（毛，Ｙｓ）一０，（ｉ，歹）∈Ｈ
广泛的应用背景，包括多处理器任务调度、资源分从而二维装箱问题可以用下面的数学模型来表示：
配、运输计划等，因此对其求解的研究具有广泛的广义模型
应用价值．从计算复杂性理论来讲，装箱问题是ｍｉｎ
口
ＮＰ难问题，很难精确求解，已有的大部分成果都Ｓ．ｔ．
Ｓｉ（墨，Ｙｉ）ｎＳ（乃，＂）一⑦，
（ｉ，Ｊ）∈Ｈ，
是针对近似算法的研究．目前的近似算法有下次０≤五≤Ｌ—ｌｆ，０≤Ｙｉ≤＂一ｈｆ，ｉ∈Ｊ
适应（ｎｅｘｔ－ｆｉｔｄｅｃｒｅａｓｉｎｇｈｅｉｇｈｔ，ＮＦＤＨ）、首次适应（ｆｉｒｓｔ－ｆｉｔ由于约束Ｓ。（ｚ；，Ｙ，）ｎｄｅｃｒｅａｓｉｎｇｈｅｉｇｈｔ，ＦＦＤＨ）、最佳适Ｓ（乃，ｙｓ）一ｇ，（ｆ，歹）∈应（ｂｅｓｔ—ｆｉｔ
ｄｅｃｒｅａｓｉｎｇ
ｈｅｉｇｈｔ，ＢＦＤＨ）等［１］．本文
Ｈ不是通常的由函数表示的约束，这个模型是一建立二维装箱问题的数学模型，将其转化为一个个非光滑数学规划问题，下面研究如何将其转化非线性规划问题，给出数值算法并对不超过ｌｏ个为一个光滑的数学规划问题．
物品的装箱问题进行求解．
令Ｐｘ（Ｓ）和Ｐｙ（Ｓ）分别表示矩形Ｓ在ｚ轴１
数学模型
和Ｙ轴上的投影，则
Ｐ“（Ｓｆ（ｚｆ，ｙｆ））＝（ｚｆ，ｚｆ＋Ｚｆ），
给定宽度为Ｌ，高度不限的矩形容器；矩形物
Ｐ７（Ｓ。（ｚｆ，ｙｆ））一（ｙｊ，Ｙｆ＋ｈｉ）
品集合．，一｛ｌ，…，７１），每个矩形物品的宽度为容易知道两个矩形物品重合当且仅当它们到Ｘ轴ｚｉ，高度为ｈ；．以矩形容器左下角的位置为坐标原
和Ｙ轴的投影都相交，经过简单的计算能得到
收稿日期：２００５—１２—２０ｌ修回日期：２００７—１２—１７．基金项目；周家自然科学基金资助项目（１０７７１０２６）．
作者简介：于洪霞（１９７８一），女，博士；张立卫。（１９６６・）．男．教授，博士生导师
第２期
于洪霞等：二维装箱问题非线性规划模型和算法
３０９
Ｐ４（Ｓｉ（五，ｙｉ））ｎＰ“（Ｓ（‘，奶））≠∞铮
卜而＋孚｜＿半＜ｏ，
（ｙ，。一弘＋字）２一叫２，．。）Ｔ，
Ｐｙ（Ｓ；（五，Ｙ；））ｎＰｙ（Ｓ，（‘，ＹＪ））≠⑦∞
Ｆ３（ｚ）＝（（毗。一训ｔ：＋红｛生）×
ｙ，１＋孚Ｊ＿学＜ｏ
（以。一试：＋学）…
从而，广义模型可以等价地表示为
绝对值模型
（砟ｍ一雌ｍ＋纽笋）×
ｒａｉｎ
臼
ｓ．ｔ．ｍａｘ∽一乃＋孚卜字，
（砟ｍ一如Ｈ纽芦））Ｔ，
Ｆ４（ｚ）＝（ｕ—ｙ１一ｈｌ…硼一Ｙ。一ｈ。）Ｔ
ｙｒ一弘＋学｜＿半净。，
令Ｑ＝｛ｚ∈ｚ１Ｆ（ｚ）∈Ｄ），其中Ｄ一｛０＾ｆ）ｘ
ｆ０．，ｌ＿）（“ｌ。，｝＞＜Ｒ！．
（ｉ，歹）∈Ｈ，
０。≤ｚ≤Ｌｅｒ。］一ｌ
０≤ｚｉ≤Ｌ—Ｚｆ，０≤Ｙｆ≤口一ｈｆ，ｉ∈Ｊ
Ｚ＝
ｚ∈Ｒ２井３卅１
Ｙ≥０。由于其中包含反凸约束，可行集是非凸的，进而知矿≥０Ｍ
道绝对值模型是非凸非光滑的优化问题．通过引’．，ｘ∈ＲＭ，ｗｙ∈ＲＭ，ｖ∈Ｒ
入人工变量∥、∥、’．，Ａ，可以把绝对值模型转化为ｅ【司一（１…１）Ｔ∈Ⅳ，这样绝对值模型就可以一个光滑的优化问题．令ｚ一（工Ｙ’‘，ｘ∥
等价地表示为一个光滑优化问题．
＇．一
ｕ），Ｍ＝ｎ（ｎ一１）／ｚ，定义函数，０：Ｒ”×Ｒ”×
非线性规划模型
ｍｉｎ
Ｙｏ（ｚ）
ＲＭ×Ｒ＿ＲＭ×Ｒ＾ｆ×ＲＭ×Ｒ”如下：
ＲＭ×ＲＭ×ＲＭ—Ｒ和Ｆ：Ｒ”×Ｒ”×ＲＭ×ＲＭ×ｓ．ｔ．
Ｆ（ｚ）∈Ｄ，０（ｚ）＝口，
ｚ∈Ｚ
Ｆ（ｚ）一（矸（ｚ）巧（ｚ）碍（ｚ）ＦＴ（ｚ））Ｔ
为了得到非线性规划模型的一阶最优性条件，引其中
入下列标记：
Ｆ心）一（（ｚ。一ｚ：＋孚）２一训酝…
Ｗｘ—ｄｉａｇ（ｆｔ雎Ｈ（训荔）（珀～＋孕）２一硝。。）Ｔ，
ＷＹ—ｄｉａｇ（１．脏Ｈ（叫【，）
Ａ＝ｄｉａｇ（ｆ。，）∈Ｈ（ａｆ．ｊ）Ｂ—ｄｉａｇ（ｆ，』）∈Ｈ（届．Ｊ）
Ｆｚ（ｚ）一（（ｙ。一ｙ：＋红≠）２一础终…
Ｃ＝ｄｉａｇ＿（ｆ，』）∈Ｈ（７ｉ．，）
ｄ１．２（工）ｄ１。３（ｘ）
ｄｌ。。（工）
ＯＯ
Ｏ一ｄ１．２（ｘ）
Ｏ
Ｏｄ２．３（工）ｄ２．。（ｘ）
Ｏ
Ｏ
—ｄｌ。３（工）
Ｏ一ｄ２．３（ｚ）
Ｏ
０
Ｄｌ—
ＯＯ
Ｏ
Ｏ
Ｏ
Ｏ
Ｏ０ＯＯ
０
ｄｒｌ，。（ｘ）
０
Ｏ
—ｄ１．。（ｚ）
Ｏ
一ｄ２．。（工）
一ｄ。一１．。（ｘ）
ｆｆｌ。２（ｘ）ｃ１．３（ｚ）
ｃ１。。（ｚ）
Ｏ００１
Ｉ一气。（ｘ）
Ｏ
Ｏｃ２．３（工）
ｃ２。。（工）
００
—Ｃ１．３（ｘ）
Ｏ一ｆ２。３（ｚ）
ＯｏＤ２一０
Ｏ
Ｏ
Ｏ
Ｏ
０
；
Ｉ
ｏＯＯＯＯ
Ｃｒｒ－Ｉ，ｎ（ｚ）Ｊ
；Ｉ
１
０
Ｏ
—Ｃ１．。（ｘ）Ｏ
—ｃ２．。（ｚ）
—ｃ，ｒ。，。（工）Ｊ
３１０
大连理工大学学报
第４８卷
其中ｄ¨（工）一２（ｘｆ一乃）＋ｌｆ—ｌ，，ｆ幻（ｙ）一２（ｙｆ
—Ｙｉ）＋ｈｆ—ｈ，，口叫一一（以』一畦』＋（＾ｆ＋屯）／２），屈。』＝一（础』一铷毛＋（ｚｒ＋／ｊ）／２），托，ｊ一２以』一砌幻Ｘ＋（ｚｔ＋ｌ，）／ｚ一碱』＋（＾ｆ＋以）／ｚ．这
样ＶＦＴ（ｚ）（ｉ＝１，…，４）可以表示为
Ｄｌ０。×Ａｆ
０。×＾ｆ
Ｄ２一２Ｗｘ
，Ｖ巧（ｚ）＝
ＯＭ×Ｍ
ＶＦ｝（ｚ）＝
０Ｍ×＾ｆ一２ｗｙ
Ｏ朋＇（盯Ｏ脓Ｍ
０ｌｘＭ０ｌ×Ｍ０。×Ｍ’０棋。
０＂ｘＭ
一Ｉ。×。
Ｖ砑（ｚ）一
Ａ
０』Ⅵ×。Ｂ，Ｖ砑（ｚ）一
０Ｍ×。
Ｃ０脓。
０１×Ｍ．
１１×。
函数Ｆ的Ｊａｃｏｂｉ转置矩阵为
ＶＰ（ｚ）一（Ｖ矸（ｚ）Ｖ砰（ｚ）
ＶＦＴ（ｚ）ＶＦ手（ｚ））
为求得％（力，ｚ∈ｎ，给出Ⅳｚ（【）和ⅣＤ（Ｆ（‘））的
计算公式．
令
互一（ｚ∈Ｒ”ｌ０。≤工≤ｋ［，ｚ］一ｆ），
互一｛．），∈Ｒ”ＩＹ≥０。一）
其中厄＝［ｏ，Ｌ—ｌｉ］，刁＝Ｅｏ，ｏ。）．则
Ｎｚ（ｒ）＝心（ｚ）×心（罗）×Ｎ∥（刀ｘ）×
ＮＲＭ（矿）×ＮＲ，（矿）×ＮＲ（雷）
其中
Ｎ乙（ｚ）２
Ｎ４（五）×…×心（磊）
ｒＩＬ；
五一Ｏ
Ｎ乏（五）一｛｛０）；０＜ｚ；＜Ｌ一厶
ｌｌ～；
五一Ｌ—Ｚｉ
心（ｙ）２
Ｎ弓（Ｙ１）×…×Ｎ弓（见）
ｗ勋一氍量三吕
ＮａＭ（缈ｘ）＝Ｎ∥（矿）＝｛０Ｍ）
ＮＲ＃（矿）＝ＮＲ＋（毗２）×…×ＮＲ＋（硼－－，ｒＡ
１．。）
ＮＲ＋（跏＝慌鼍至：
—‰（可）一｛０）
Ｄ在Ｆ（ｚ）处的法锥ＮＤ（Ｆ（ｒ））为
ＮＤ（Ｆ（乏））一Ｎ｛ｏＭ｝（ＦＩ（ｒ））×Ｎ｛ｏ＾，Ｊ（Ｆｚ（【））×
ＮｉｏＭ｝（Ｆ３（‘））×＾『Ｒ：（Ｆ４（ｒ））
其中
ｊｖ｛ｏ｝（Ｆｌ（‘））一Ｎ｛ｏ｝（Ｆｚ（ｚ））＝Ｍ’
Ｍ’
Ｎ｛ｏ，（Ｆ３（‘））一ＲＭＭ’
ＮＲ；（Ｆ４（ｚ））＝ＮＲ＋（Ｆ：（互））×…×
ＮＲ＋（日（‘））
Ｋ㈣＠”一１｛ｏ）’；磊：丢＞ｏ
ｆＲ－；霸（‘）一０
引理１（Ｑ在【的法锥）
设ｒ∈Ｑ满足面毛≠
０，磷』≠０，仞乙一（ｚ；＋易）／ｚ≠武，一（＾；＋％）／ｚ，
（ｆ，．『）∈Ｈ，矿＞０，则Ｑ在ｚ的法锥可以表示为
‰（石）＝｛Ｖ矿（石）ｐ＋口Ｉ
Ｐ∈ＮＤ（Ｆ（乏）），ｑ∈
Ｎｚ（‘）｝．
证明根据文献［５］的定理６．１４，只需证明下面的约束规范成立：
一ＶＦ。（【）Ｐ∈Ｎｚ（‘），
Ｐ∈Ｎ０（Ｆ（‘））辛ｐ＝０
（１）
令ｐ＝
（ｐ１Ｔ
…Ｐ４Ｔ）Ｔ∈ＮＤ（Ｆ（【）），贝Ⅱ
一Ｖ，（ｚ）ｐ∈Ｎｚ（ｚ）可以写成ＶＦ丁（ｚ）（一ｐ１）＋
…＋ＶＦＴ（【）（一ｐ４），或者写成矩阵的形式：
Ｄ１０。×Ｍ０。×Ｍ
０”×。
０积Ｍ
Ｄｚ０”×Ｍ—Ｉ。×。
一Ｐ１
一２Ｗｘ
ＯＭ×＾ｆ
Ａ０揪。
一ｐ２
ＯＭ×＾ｆ一２∥
∈Ⅳｚ（暑）
ＢＯＭｘ。
一ｆｐ３０Ｍ×Ｍ
ＯＭ×ＭＣ０脓。
一ｐ４
０ｌ×＾ｆ
０ｌ×Ｍ
０１×＾ｆ
１
ｌ×＂
即
一Ｄｌｐｌ
∈№。（置）
一Ｄ２Ｐ２＋Ｐ４
∈Ｎｚ（ｙ）
２ＷＸｐｌ一Ａｐ
３
∈Ｎ∥（矿）
（２）２∥ｐ２一Ｂｐ
３
∈Ｎ．Ｍ（矿）
（３）
一Ｃｐ
３
∈Ｍ．”（矿）
∑（一ｐ；）
∈ＮＲ（口）
由ｐ４∈Ｎ贮（Ｆ４（ｒ））知ｐ４≤０。，此外由Ｎ。（弓）一
ｎ
（ｏ）知∑（一ｐ；）＝ｏ，从而可得出Ｐ４＝０。．因为
ｉ；ｌ
３＝０Ｍ．其
２＝０Ｍ（因为ＮＲＭ（谛ｘ）＝ＮＲＭ（形ｙ）一
印＾＞０，可知ＮＲ！（矿）一｛０Ｍ），从而ｃｐ中Ｃ非奇异（否则，至少有一个托．ｊ＝０，这意味着仞：』一（ｚｚ＋‘）／ｚ＝面！ｊ一（丘ｚ＋ｈ，）／ｚ，与假设矛盾），因此得到Ｐ３—０Ｍ．由式（２）和（３）得到Ｗｘｐ－
＝０＾ｆ，ＷＹｐ
第２蠲
予漤黢等：二维装箱阕题霉线缝规划模型孝舞法
Ｒ４肿ｈ，其中Ａ；”＞Ｏ（ｉ＝３Ｍ＋１，．．・，４Ｍ＋４ｎ）；≤”＞０，ｉ—ｌ，…，４斑－４－４耐；ｓ≥０，ｋ；＝王．
步２
｛０Ｍ））．又因为∥和ｗｙ是非奇异的，得出Ｐ１一
Ｐ２—０辫．至此证明了式（１），从蕊计算％（零＞的公
式可以从文献Ｅｓ］得到．
定理１（非线性规划模型的一阶最优性条件）设￡∈Ｑ是嚣线性规划模型懿一个局部最优解，
求解ｍｉｎＰ（ｚ，Ａ“’，盯娃’）得弼珀．１；
０Ｃ卜’（ｚ件Ｉ）０。。≤￡（其中Ｑ卜’（４）一ｍｉｎ｛Ｏ，Ｃｆ（ｚＤ｝），剥箨止。
步３
对ｉ—ｌ，…，４Ｍ十４咒，令
ｈ，＿≈川
满足面毛≠０，武ｊ≠０，碗一（玉＋ｌｊ）／Ｚ雾成Ｊ一
（＾。＋ｈｉ）ｌＳ，（ｉ，Ｊ）∈Ｈ，矿＞０，则存在一个向量
Ｐ∈％（Ｆ＜黟），使季鏊一［Ｖ五（嚣）÷Ｖ矿＜彩ｐ二∈心（ｒ）．
证明
毋（蚌”＝｛隘辽≤？，炉，；ｌ西＿‘镰ｐＩ喜：４
步４
计算
ｉ一３Ｍ＋１，…，４Ｍ＋４ｎ，ｋ：一ｋ＋１；转步２．
由文献［５］的定理６．１２知一Ｖ＾（ｚ）
ｇ％（Ｄ，羁壹雩ｌ理ｌ得证．
２
Ａ：胂１’一Ａｆ“’一蠢Ｄｆｆ（孙１），ｉ一１，…，３Ｍ爻；转１’＝ｍａｘ｛２；聍一ｏ＇ｉ㈨Ｑ（珏１），０｝，
数值算法
在菲线性规慈摸蘩孛，终束ｚ∈ｚ胃以震篱单的
大爨豹数值实验表明，对于中小援模阕题，可以求得精确解．本文选出３个例子说明，图ｌ（ａ）～（ｃ）给出了对应予求得解的矩形排列。
在图１（ａ）中，嚣一８，
ｆ一（３ｈ一（２０
３
５１０
６６
８４
４６
５５
７），５
不等式来表示，进而非线性规划模型可以表述为
ｒａｉｎ＾（嚣）
ｓ．ｔ．
Ｃｉ（ｚ）＝０，ｉ—ｉ，…，３掰，嘶（聋）≥０，
ｉ＝３Ｍ＋１，…，４Ｍ＋４ｎ
。
对于这个约束优化闻题可以应用增广Ｌａｇｒａｎｇｅ方法通过求勰一淳襄无约束优讫闯题得戮解决，
ｒａｉｎ
Ｐ（嚣，Ａ，盯）一
３Ｍ
４），Ｌ＝１２。
解掣＝２５．
在图１（ｂ）中，札一９，
ｌ一（３ｈ一（１０解
５６６４８６４５５５８４７３
＾（ｚ＞＋∑［一左芦ｆ（：）＋ｏ。ｓ蟊ｅ；（鬈）】÷
甭
４肿４Ｍ
３）。
２０），￡＝１２．
ｆ—ＡｌｃＩ（ｚ）＋ｏ・５ａｉｃｌ２（ｚ）；
Ｑ（互）＜；ｂ／ａｌ
＂＝２８．
∑ｌ净澎Ｈｌ
算法ＡＬＭ：步１
在躁ｌ（ｃ）中，摊＝１０，
ｌ一（４
ｈ一（２１
５１０４８９８４２８７７６８５９４８），
一０．５走２旭；否刚
其中口＞０是参数，Ａ是Ｌａｇｒａｎｇｅ乘子．
给定初始值ｚｌ∈Ｒｚ井３擗１，Ａｎ’∈
３）．Ｌ＝１３．
解”一４０．
●
垂
‘
１
６
●
１０
’
２
●
｜
７
５
９
３
８
（ｃ）ｎ＝ｌＯ
匿１
Ｆｉｇ．１
三种情况解酶毽零
ｏｆｓｏｌｕｔｉｏｎｓｆｏｒｔｈｒｅｅ
ｃａｓｅｓ
Ｉｌｌｕｓｔｒａｔｉｏｎｓ
３１２
大连瑷王大
与经典的启发式算法如下次适应、首次适应
学学摄
第４８卷
例子各个算法的计算结果和增广Ｌａｇｒａｎｇｅ算法懿计算辩闭．
稔最佳适应籀毙，增广Ｌａｇｒａｎｇｅ算法在计算的糖确度方面有很大提高，表１给出了针对上面３个
袭１
Ｔａｂ．１
与经典翡启发式方法的数值毙较
Ｎｕｍｅｒｉｃａｌｃｏｍｐａｒｉｓｏｎｓｗｉｔｈｃｌａｓｓｉｃａｌｈｅｕｒｉｓｔｉｃｍｅｔｈｏｄｓ
＾耐ｎ
ｔＡＬＭ／ｍｉｎ
ＮＦＤＨ筹法
８９
ｌＯ
ＦＦＤＨ箕法
３５
ＢＦＤＨ算法
３７４１
ＡＬＭ箕法
２５
３Ｓ３８
５４
３
９
３８
５４
２８
４０
５３３５
注；，｜为褥子数量＃矗辩｛。秀最，ｌ、爨霾；ｔＡＬＭ秀ＡＬＭ算法诤冀辩惩
３
结语
ｏｎ
ｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌ
Ａｐｐｌｉｅｄ
ｂｉｎ
ｐａｃｋｉｎｇｐｒｏｂｌｅｍｓ［Ｊ］．
２００２。
Ｄｉｓｃｒｅｔｅ
Ｍａｔｈｅｍａｔｉｃｓ，１２３／１２４：
本文绘出二维装箱问题戆嚣线性规燃模型，以变分分析为工具建立了这一非线性规划问题的最优性条件，并用增广Ｌａｇｒａｎｇｅ方法对它求解．数值结采表曙，对不超过ｌｏ个物晶的装禳闻题，用该方法可以求得精确解，从计算时间上稽，对这样规模的阅题，该方法比经典的启发式方法要优越．如俺把毒蓦线性规划方法用予有效求解大规模二维装箱问题是以后值得研究的课题．
［２３
３７３—３９０Ｌ（）ＤＩ
Ａ。ＭＡＲＴＥＬＬＯＳ。ＶＩＧＯＤ。Ａｐｐｒｏｘｉｍａｔｉｏｎ
ｆｏｒ
ｔｈｅ
ｏｒｉｅｎｔｅｄ
ａｌｇｏｒｉｔｈｍｓｐａｃｋｉｎｇ
ｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌｂｉｎ
ｐｒｏｂｌｅｍ秘］。ＥｕｒｏｐｅａｎＪｏｕｒｎａｌｏｆＯｐｅｒａｔｉｏｎａｌ
Ｒｅｓｅａｒｃｈ．１９９９，１１２：１５８－１６６
［３］武晓今．朱仲英．嚣维装箱问题的一种寅现方法［Ｊ］．
缴型电脑应翅，２００３，１９（４）：２０—２３
［４］ＭＡＲＴＥＬＬＯＳ，Ｍ（）ＮＡｅｌＭ，ＶＩＧＯ
ａｐｐｒｏａｃｈ
ｔｏ
Ｄ．Ａｎｅｘａｃｔ
ｔｈｅ
ｏｎ
ｓｔｒｉｐ—ｐａｃｋｉｎｇ
ｐｒｏｂｌｅｍ
［Ｊ］．
ＩＮＦＯＲＭＳＪｏｕｒｎａｌ
参考文献：
［１］ＬＯＤＩＡ．ＭＡＲＴＥＬＬＯＳ，ＶＩＧＯ
Ｄ．Ｒｅｃｅｎｔａｄｖａｎｃｅｓ
Ｃｏｍｐｕｔｉｎｇ，２００３，ＩＳ：３１０。３１９
Ｉｓ］ＲＯＣＫＡＦＥＬＬＡＲ
Ｒ
Ｔ，ＷＥＴＳＲｊ玫Ｖａｒｉａｔｉｏｎａｌ
Ｙｏｒｋ；Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，１９９８
Ａｎａｌｙｓｉｓ［Ｍ］．Ｎｅｗ
Ａｎｏｎｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇｍｏｄｅｌｆｏｒｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌｓｔｒｉｐ－ｐａｃｋｉｎｇ
ｐｒｏｂｌｅｍａｎｄ
ＹＵ
ｉｔｓ
ｎｕｍｅｒｉｃａｌｍｅｔｈｏｄ
Ｓｈａｏ．ｗｕ３，ＺＨＡＮＧ
Ｌｉ－ｗｅｉ’１
Ｈｏｎｇ—ｘｉａｌｔ２，ＺＨＡＮＧ
（｛，ＤｅｐａｒｔｍｅｎｔｏｆＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓ・ＤａｌｉａｎＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ。Ｄａｌｉａｎ１１６０２４．Ｃｈｉｎａ；
２．ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓａｎｄＰｈｙｓｉｃｓ・ＳｈａｎｇｈａｉＵｎｉｖｅｒｓｉｔｙｏｆＥｌｅｃｔｒｉｃＰｏｗｅｒ，Ｓｈａｎｇｈａｉ
２０００９０．Ｃｈｉｎａ；
３．ＳｃｈｏｏｌｏｆＥｌｅｃｔｒｏｎｉｃａｎｄＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，ＤａｌｉａｎＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｄａｌｉａｎ１１６０２４。Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ａｓａ＋ｃｌａｓｓｏｆｃｏｍｂｉｎａｔｏｒｉａｌｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓｗｉｔｈｍａｎｙｉｍｐｏｒｔａｎｔａｐｐｌｉｃａｔｉｏｎｓ，ｔｗｏ—ｄｉｍｅｎｓｉｏｎａｌｓｔｒｉｐ—ｐａｃｋｉｎｇｐｒｏｂｌｅｍｓ
ａｒｅ
ｑｕｉｔｅｄｉｆｆｉｃｕｌｔ
ａｓ
ｔｏａ
ｂｅｓｏｌｖｅｄａｃｃｕｒａｔｅｌｙ
ａｓ
ｔｈｅｙ
ａｒｅ
ＮＰｈａｒｄ．
Ａｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌｓｔｒｉｐ—ｐａｃｋｉｎｇｐｒｏｂｌｅｍｉｓｆｏｒｍｕｌａｔｅｄｔｈｅｎｏｔｉｏｎｏｆｔａｎｇｅｎｔ
ｃｏｎｅｓ
ｎｏｎｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇ（ＮＬＰ）ｍｏｄｅｌａｎｄ
ｔｏ
ｉｎｖａｒｉａｔｉｏｎａｌａｎａｌｙｓｉｓｉｓｅｍｐｌｏｙｅｄｅｓｔａｂｌｉｓｈｔｈｅｆｉｒｓｔ—ｏｒｄｅｒｏｐｔｉｍａｌｉｔｙ
ｔｏ
ｃｏｎｄｉｔｉｏｎｓｆｏｒｔｈｅＮＬＰｐｒｏｂｌｅｍ．ＴｈｅａｕｇｍｅｎｔｅｄＬａｇｒａｎｇｅｍｅｔｈｏｄｉｓｐｒｅｓｅｎｔｅｄ
ｓｏｌｖｅｔｈｉｓＮＬＰ
ｐｒｏｂｌｅｍａｎｄｓｐｅｃｉｆｉｃｐｒｏｂｌｅｍｓ
ａｒｅ
ｓｏｌｖｅｄｂｙｉｔ．ＮｕｍｅｒｉｃａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅａｕｇｍｅｎｔｅｄＬａｇｒａｎｇｅ
ｔｏ
ｍｅｔｈｏｄｉｓｓｕｉｔａｂｌｅｆｏｒｓｏｌｖｉｎｇｔｈｉｓＮＬＰｐｒｏｂｌｅｍａｎｄｉｔｉｓａｂｌｅ
ｐｒｏｂｌｅｍｓｉｎｖｏｌｖｉｎｇｕｐＫｅｙ
ｔｏ
ｆｉｎｄ
ｅｘａｃｔ
ｓｏｌｕｔｉｏｎｓ
ｔｏ
ｓｔｒｉｐ—ｐａｃｋｉｎｇ
１０ｉｔｅｒｎｓ．
ｓｔｒｉｐ—ｐａｃｋｉｎｇ
ｗｏｒｄｓ：ｔｗｏ—ｄｉｍｅｎｓｉｏｎａｌ
Ｌａｇｒａｎｇｅｍｅｔｈｏｄ
ｐｒｏｂｌｅｍ；ｆｉｒｓｔ—ｏｒｄｅｒｏｐｔｉｍａｌｉｔｙｃｏｎｄｉｔｉｏｎｓ；ａｕｇｍｅｎｔｅｄ
二维装箱问题非线性规划模型和算法
作者：作者单位：
于洪霞， 张绍武， 张立卫， YU Hong-xia， ZHANG Shao-wu， ZHANG Li-wei
于洪霞,YU Hong-xia(大连理工大学,应用数学系,辽宁,大连,116024;上海电力学院,数理系,上海,200090)， 张绍武,ZHANG Shao-wu(大连理工大学,电子与信息工程学院,辽宁,大连,116024)， 张立卫,ZHANG Li-wei(大连理工大学,应用数学系,辽宁,大连,116024)大连理工大学学报
JOURNAL OF DALIAN UNIVERSITY OF TECHNOLOGY2008,48(2)1次
刊名：英文刊名：年，卷(期)：被引用次数：
参考文献(5条)
1.ROCKAFELLAR R T;WETS R J B Variational Analysis 1998
2.MARTELLO S;MONACI M;VIGO D An exact approach to the strip-packing problem 20033.武晓今;朱仲英 二维装箱问题的一种实现方法[期刊论文]-微型电脑应用 2003(04)
4.LODI A;MARTELLO S;VIGO D Approximation algorithms for the oriented two-dimensional bin packingproblem[外文期刊] 1999(1)
5.LODI A;MARTELLO S;VIGO D Recent advances on two-dimensional bin packing problems[外文期刊]2002(1/3)
引证文献(1条)
1.王石 一种解决矩形布局问题的启发式快速算法[期刊论文]-计算机技术与发展 2011(3)
本文链接：http://d.g.wanfangdata.com.cn/Periodical_dllgdxxb200802028.aspx
第４８卷第２期
大连理工大学学报
Ｖ０１．４８，Ｎｏ．２Ｚ００
８年３月ＪｏｕｒｎａｌｏｆＤａｌｉａｎＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ
Ｍａｒ．２
０
０
８
文章编号：１０００－８６０８（２００８）０２—０３０８－０５
二维装箱问题非线性规划模型和算法
于洪霞１’２，
张绍武３，张立卫¨
（１．大连理工大学应用数学系。辽宁大连
１１６０２４，
２．上海电力学院数理系．上海
２０００９０；
３．大连理工大学电子与信息工程学院，辽宁大连１１６０２４）
摘要：二维装箱问题是具有广泛应用背景的一类组合优化问题，这类问题是ＮＰ难问题，很难得到精确解．将二维装箱问题表示为一个非线性规划模型，用变分分析中切锥的概念建立了这一优化问题的一阶最优性条件．给出了求解这一优化问题的增广Ｌａｇｒａｎｇｅ方法．并求解了具体问题．数值实验表明增广Ｌａｇｒａｎｇｅ方法适合求解该问题．对于不超过１０个物品的装
箱问题可以求得精确解．
关键词：二维装箱问题；一阶最优性条件；增广Ｌａｇｒａｎｇｅ方法中图分类号：０２２１．２
文献标志码：Ａ
０
引
言
点，每个小矩形物品左下角坐标用（ｚ，，Ｙｉ）表示，二维装箱问题可以分为两类：一类是给定数则每个小矩形的内部可以表示为
量不限大小固定的容器，目标是使用最少数量的Ｓｆ（ｚｆ，Ｙｆ）＝｛（比，，．，）∈Ｒ２”ｌ
容器装完所有的物品；另一类是给定一个宽度为ｚｆ＜乱ｆ＜ｚｆ＋ｌｆ，有限数值的矩形容器，它的高度不限，要求将所有Ｙｆ＜训ｉ＜Ｙｆ十ｈｆ）
物品放入该容器中，并取得最小的放置高度，使容令Ｈ一｛（ｉ，Ｊ）Ｉｉ∈．厂，＿『∈．厂，ｉ＜Ｊ），则ＩＨｌ＝器利用率最高．本文只考虑第二类装箱问题．
ｎ（ｎ一１）／２，任何两个矩形物品不重合可以表示为
在计算机科学和工业领域中，装箱问题有着ｓｆ（ｚｉ，Ｙ；）ｎＳｊ（毛，Ｙｓ）一０，（ｉ，歹）∈Ｈ
广泛的应用背景，包括多处理器任务调度、资源分从而二维装箱问题可以用下面的数学模型来表示：
配、运输计划等，因此对其求解的研究具有广泛的广义模型
应用价值．从计算复杂性理论来讲，装箱问题是ｍｉｎ
口
ＮＰ难问题，很难精确求解，已有的大部分成果都Ｓ．ｔ．
Ｓｉ（墨，Ｙｉ）ｎＳ（乃，＂）一⑦，
（ｉ，Ｊ）∈Ｈ，
是针对近似算法的研究．目前的近似算法有下次０≤五≤Ｌ—ｌｆ，０≤Ｙｉ≤＂一ｈｆ，ｉ∈Ｊ
适应（ｎｅｘｔ－ｆｉｔｄｅｃｒｅａｓｉｎｇｈｅｉｇｈｔ，ＮＦＤＨ）、首次适应（ｆｉｒｓｔ－ｆｉｔ由于约束Ｓ。（ｚ；，Ｙ，）ｎｄｅｃｒｅａｓｉｎｇｈｅｉｇｈｔ，ＦＦＤＨ）、最佳适Ｓ（乃，ｙｓ）一ｇ，（ｆ，歹）∈应（ｂｅｓｔ—ｆｉｔ
ｄｅｃｒｅａｓｉｎｇ
ｈｅｉｇｈｔ，ＢＦＤＨ）等［１］．本文
Ｈ不是通常的由函数表示的约束，这个模型是一建立二维装箱问题的数学模型，将其转化为一个个非光滑数学规划问题，下面研究如何将其转化非线性规划问题，给出数值算法并对不超过ｌｏ个为一个光滑的数学规划问题．
物品的装箱问题进行求解．
令Ｐｘ（Ｓ）和Ｐｙ（Ｓ）分别表示矩形Ｓ在ｚ轴１
数学模型
和Ｙ轴上的投影，则
Ｐ“（Ｓｆ（ｚｆ，ｙｆ））＝（ｚｆ，ｚｆ＋Ｚｆ），
给定宽度为Ｌ，高度不限的矩形容器；矩形物
Ｐ７（Ｓ。（ｚｆ，ｙｆ））一（ｙｊ，Ｙｆ＋ｈｉ）
品集合．，一｛ｌ，…，７１），每个矩形物品的宽度为容易知道两个矩形物品重合当且仅当它们到Ｘ轴ｚｉ，高度为ｈ；．以矩形容器左下角的位置为坐标原
和Ｙ轴的投影都相交，经过简单的计算能得到
收稿日期：２００５—１２—２０ｌ修回日期：２００７—１２—１７．基金项目；周家自然科学基金资助项目（１０７７１０２６）．
作者简介：于洪霞（１９７８一），女，博士；张立卫。（１９６６・）．男．教授，博士生导师
第２期
于洪霞等：二维装箱问题非线性规划模型和算法
３０９
Ｐ４（Ｓｉ（五，ｙｉ））ｎＰ“（Ｓ（‘，奶））≠∞铮
卜而＋孚｜＿半＜ｏ，
（ｙ，。一弘＋字）２一叫２，．。）Ｔ，
Ｐｙ（Ｓ；（五，Ｙ；））ｎＰｙ（Ｓ，（‘，ＹＪ））≠⑦∞
Ｆ３（ｚ）＝（（毗。一训ｔ：＋红｛生）×
ｙ，１＋孚Ｊ＿学＜ｏ
（以。一试：＋学）…
从而，广义模型可以等价地表示为
绝对值模型
（砟ｍ一雌ｍ＋纽笋）×
ｒａｉｎ
臼
ｓ．ｔ．ｍａｘ∽一乃＋孚卜字，
（砟ｍ一如Ｈ纽芦））Ｔ，
Ｆ４（ｚ）＝（ｕ—ｙ１一ｈｌ…硼一Ｙ。一ｈ。）Ｔ
ｙｒ一弘＋学｜＿半净。，
令Ｑ＝｛ｚ∈ｚ１Ｆ（ｚ）∈Ｄ），其中Ｄ一｛０＾ｆ）ｘ
ｆ０．，ｌ＿）（“ｌ。，｝＞＜Ｒ！．
（ｉ，歹）∈Ｈ，
０。≤ｚ≤Ｌｅｒ。］一ｌ
０≤ｚｉ≤Ｌ—Ｚｆ，０≤Ｙｆ≤口一ｈｆ，ｉ∈Ｊ
Ｚ＝
ｚ∈Ｒ２井３卅１
Ｙ≥０。由于其中包含反凸约束，可行集是非凸的，进而知矿≥０Ｍ
道绝对值模型是非凸非光滑的优化问题．通过引’．，ｘ∈ＲＭ，ｗｙ∈ＲＭ，ｖ∈Ｒ
入人工变量∥、∥、’．，Ａ，可以把绝对值模型转化为ｅ【司一（１…１）Ｔ∈Ⅳ，这样绝对值模型就可以一个光滑的优化问题．令ｚ一（工Ｙ’‘，ｘ∥
等价地表示为一个光滑优化问题．
＇．一
ｕ），Ｍ＝ｎ（ｎ一１）／ｚ，定义函数，０：Ｒ”×Ｒ”×
非线性规划模型
ｍｉｎ
Ｙｏ（ｚ）
ＲＭ×Ｒ＿ＲＭ×Ｒ＾ｆ×ＲＭ×Ｒ”如下：
ＲＭ×ＲＭ×ＲＭ—Ｒ和Ｆ：Ｒ”×Ｒ”×ＲＭ×ＲＭ×ｓ．ｔ．
Ｆ（ｚ）∈Ｄ，０（ｚ）＝口，
ｚ∈Ｚ
Ｆ（ｚ）一（矸（ｚ）巧（ｚ）碍（ｚ）ＦＴ（ｚ））Ｔ
为了得到非线性规划模型的一阶最优性条件，引其中
入下列标记：
Ｆ心）一（（ｚ。一ｚ：＋孚）２一训酝…
Ｗｘ—ｄｉａｇ（ｆｔ雎Ｈ（训荔）（珀～＋孕）２一硝。。）Ｔ，
ＷＹ—ｄｉａｇ（１．脏Ｈ（叫【，）
Ａ＝ｄｉａｇ（ｆ。，）∈Ｈ（ａｆ．ｊ）Ｂ—ｄｉａｇ（ｆ，』）∈Ｈ（届．Ｊ）
Ｆｚ（ｚ）一（（ｙ。一ｙ：＋红≠）２一础终…
Ｃ＝ｄｉａｇ＿（ｆ，』）∈Ｈ（７ｉ．，）
ｄ１．２（工）ｄ１。３（ｘ）
ｄｌ。。（工）
ＯＯ
Ｏ一ｄ１．２（ｘ）
Ｏ
Ｏｄ２．３（工）ｄ２．。（ｘ）
Ｏ
Ｏ
—ｄｌ。３（工）
Ｏ一ｄ２．３（ｚ）
Ｏ
０
Ｄｌ—
ＯＯ
Ｏ
Ｏ
Ｏ
Ｏ
Ｏ０ＯＯ
０
ｄｒｌ，。（ｘ）
０
Ｏ
—ｄ１．。（ｚ）
Ｏ
一ｄ２．。（工）
一ｄ。一１．。（ｘ）
ｆｆｌ。２（ｘ）ｃ１．３（ｚ）
ｃ１。。（ｚ）
Ｏ００１
Ｉ一气。（ｘ）
Ｏ
Ｏｃ２．３（工）
ｃ２。。（工）
００
—Ｃ１．３（ｘ）
Ｏ一ｆ２。３（ｚ）
ＯｏＤ２一０
Ｏ
Ｏ
Ｏ
Ｏ
０
；
Ｉ
ｏＯＯＯＯ
Ｃｒｒ－Ｉ，ｎ（ｚ）Ｊ
；Ｉ
１
０
Ｏ
—Ｃ１．。（ｘ）Ｏ
—ｃ２．。（ｚ）
—ｃ，ｒ。，。（工）Ｊ
３１０
大连理工大学学报
第４８卷
其中ｄ¨（工）一２（ｘｆ一乃）＋ｌｆ—ｌ，，ｆ幻（ｙ）一２（ｙｆ
—Ｙｉ）＋ｈｆ—ｈ，，口叫一一（以』一畦』＋（＾ｆ＋屯）／２），屈。』＝一（础』一铷毛＋（ｚｒ＋／ｊ）／２），托，ｊ一２以』一砌幻Ｘ＋（ｚｔ＋ｌ，）／ｚ一碱』＋（＾ｆ＋以）／ｚ．这
样ＶＦＴ（ｚ）（ｉ＝１，…，４）可以表示为
Ｄｌ０。×Ａｆ
０。×＾ｆ
Ｄ２一２Ｗｘ
，Ｖ巧（ｚ）＝
ＯＭ×Ｍ
ＶＦ｝（ｚ）＝
０Ｍ×＾ｆ一２ｗｙ
Ｏ朋＇（盯Ｏ脓Ｍ
０ｌｘＭ０ｌ×Ｍ０。×Ｍ’０棋。
０＂ｘＭ
一Ｉ。×。
Ｖ砑（ｚ）一
Ａ
０』Ⅵ×。Ｂ，Ｖ砑（ｚ）一
０Ｍ×。
Ｃ０脓。
０１×Ｍ．
１１×。
函数Ｆ的Ｊａｃｏｂｉ转置矩阵为
ＶＰ（ｚ）一（Ｖ矸（ｚ）Ｖ砰（ｚ）
ＶＦＴ（ｚ）ＶＦ手（ｚ））
为求得％（力，ｚ∈ｎ，给出Ⅳｚ（【）和ⅣＤ（Ｆ（‘））的
计算公式．
令
互一（ｚ∈Ｒ”ｌ０。≤工≤ｋ［，ｚ］一ｆ），
互一｛．），∈Ｒ”ＩＹ≥０。一）
其中厄＝［ｏ，Ｌ—ｌｉ］，刁＝Ｅｏ，ｏ。）．则
Ｎｚ（ｒ）＝心（ｚ）×心（罗）×Ｎ∥（刀ｘ）×
ＮＲＭ（矿）×ＮＲ，（矿）×ＮＲ（雷）
其中
Ｎ乙（ｚ）２
Ｎ４（五）×…×心（磊）
ｒＩＬ；
五一Ｏ
Ｎ乏（五）一｛｛０）；０＜ｚ；＜Ｌ一厶
ｌｌ～；
五一Ｌ—Ｚｉ
心（ｙ）２
Ｎ弓（Ｙ１）×…×Ｎ弓（见）
ｗ勋一氍量三吕
ＮａＭ（缈ｘ）＝Ｎ∥（矿）＝｛０Ｍ）
ＮＲ＃（矿）＝ＮＲ＋（毗２）×…×ＮＲ＋（硼－－，ｒＡ
１．。）
ＮＲ＋（跏＝慌鼍至：
—‰（可）一｛０）
Ｄ在Ｆ（ｚ）处的法锥ＮＤ（Ｆ（ｒ））为
ＮＤ（Ｆ（乏））一Ｎ｛ｏＭ｝（ＦＩ（ｒ））×Ｎ｛ｏ＾，Ｊ（Ｆｚ（【））×
ＮｉｏＭ｝（Ｆ３（‘））×＾『Ｒ：（Ｆ４（ｒ））
其中
ｊｖ｛ｏ｝（Ｆｌ（‘））一Ｎ｛ｏ｝（Ｆｚ（ｚ））＝Ｍ’
Ｍ’
Ｎ｛ｏ，（Ｆ３（‘））一ＲＭＭ’
ＮＲ；（Ｆ４（ｚ））＝ＮＲ＋（Ｆ：（互））×…×
ＮＲ＋（日（‘））
Ｋ㈣＠”一１｛ｏ）’；磊：丢＞ｏ
ｆＲ－；霸（‘）一０
引理１（Ｑ在【的法锥）
设ｒ∈Ｑ满足面毛≠
０，磷』≠０，仞乙一（ｚ；＋易）／ｚ≠武，一（＾；＋％）／ｚ，
（ｆ，．『）∈Ｈ，矿＞０，则Ｑ在ｚ的法锥可以表示为
‰（石）＝｛Ｖ矿（石）ｐ＋口Ｉ
Ｐ∈ＮＤ（Ｆ（乏）），ｑ∈
Ｎｚ（‘）｝．
证明根据文献［５］的定理６．１４，只需证明下面的约束规范成立：
一ＶＦ。（【）Ｐ∈Ｎｚ（‘），
Ｐ∈Ｎ０（Ｆ（‘））辛ｐ＝０
（１）
令ｐ＝
（ｐ１Ｔ
…Ｐ４Ｔ）Ｔ∈ＮＤ（Ｆ（【）），贝Ⅱ
一Ｖ，（ｚ）ｐ∈Ｎｚ（ｚ）可以写成ＶＦ丁（ｚ）（一ｐ１）＋
…＋ＶＦＴ（【）（一ｐ４），或者写成矩阵的形式：
Ｄ１０。×Ｍ０。×Ｍ
０”×。
０积Ｍ
Ｄｚ０”×Ｍ—Ｉ。×。
一Ｐ１
一２Ｗｘ
ＯＭ×＾ｆ
Ａ０揪。
一ｐ２
ＯＭ×＾ｆ一２∥
∈Ⅳｚ（暑）
ＢＯＭｘ。
一ｆｐ３０Ｍ×Ｍ
ＯＭ×ＭＣ０脓。
一ｐ４
０ｌ×＾ｆ
０ｌ×Ｍ
０１×＾ｆ
１
ｌ×＂
即
一Ｄｌｐｌ
∈№。（置）
一Ｄ２Ｐ２＋Ｐ４
∈Ｎｚ（ｙ）
２ＷＸｐｌ一Ａｐ
３
∈Ｎ∥（矿）
（２）２∥ｐ２一Ｂｐ
３
∈Ｎ．Ｍ（矿）
（３）
一Ｃｐ
３
∈Ｍ．”（矿）
∑（一ｐ；）
∈ＮＲ（口）
由ｐ４∈Ｎ贮（Ｆ４（ｒ））知ｐ４≤０。，此外由Ｎ。（弓）一
ｎ
（ｏ）知∑（一ｐ；）＝ｏ，从而可得出Ｐ４＝０。．因为
ｉ；ｌ
３＝０Ｍ．其
２＝０Ｍ（因为ＮＲＭ（谛ｘ）＝ＮＲＭ（形ｙ）一
印＾＞０，可知ＮＲ！（矿）一｛０Ｍ），从而ｃｐ中Ｃ非奇异（否则，至少有一个托．ｊ＝０，这意味着仞：』一（ｚｚ＋‘）／ｚ＝面！ｊ一（丘ｚ＋ｈ，）／ｚ，与假设矛盾），因此得到Ｐ３—０Ｍ．由式（２）和（３）得到Ｗｘｐ－
＝０＾ｆ，ＷＹｐ
第２蠲
予漤黢等：二维装箱阕题霉线缝规划模型孝舞法
Ｒ４肿ｈ，其中Ａ；”＞Ｏ（ｉ＝３Ｍ＋１，．．・，４Ｍ＋４ｎ）；≤”＞０，ｉ—ｌ，…，４斑－４－４耐；ｓ≥０，ｋ；＝王．
步２
｛０Ｍ））．又因为∥和ｗｙ是非奇异的，得出Ｐ１一
Ｐ２—０辫．至此证明了式（１），从蕊计算％（零＞的公
式可以从文献Ｅｓ］得到．
定理１（非线性规划模型的一阶最优性条件）设￡∈Ｑ是嚣线性规划模型懿一个局部最优解，
求解ｍｉｎＰ（ｚ，Ａ“’，盯娃’）得弼珀．１；
０Ｃ卜’（ｚ件Ｉ）０。。≤￡（其中Ｑ卜’（４）一ｍｉｎ｛Ｏ，Ｃｆ（ｚＤ｝），剥箨止。
步３
对ｉ—ｌ，…，４Ｍ十４咒，令
ｈ，＿≈川
满足面毛≠０，武ｊ≠０，碗一（玉＋ｌｊ）／Ｚ雾成Ｊ一
（＾。＋ｈｉ）ｌＳ，（ｉ，Ｊ）∈Ｈ，矿＞０，则存在一个向量
Ｐ∈％（Ｆ＜黟），使季鏊一［Ｖ五（嚣）÷Ｖ矿＜彩ｐ二∈心（ｒ）．
证明
毋（蚌”＝｛隘辽≤？，炉，；ｌ西＿‘镰ｐＩ喜：４
步４
计算
ｉ一３Ｍ＋１，…，４Ｍ＋４ｎ，ｋ：一ｋ＋１；转步２．
由文献［５］的定理６．１２知一Ｖ＾（ｚ）
ｇ％（Ｄ，羁壹雩ｌ理ｌ得证．
２
Ａ：胂１’一Ａｆ“’一蠢Ｄｆｆ（孙１），ｉ一１，…，３Ｍ爻；转１’＝ｍａｘ｛２；聍一ｏ＇ｉ㈨Ｑ（珏１），０｝，
数值算法
在菲线性规慈摸蘩孛，终束ｚ∈ｚ胃以震篱单的
大爨豹数值实验表明，对于中小援模阕题，可以求得精确解．本文选出３个例子说明，图ｌ（ａ）～（ｃ）给出了对应予求得解的矩形排列。
在图１（ａ）中，嚣一８，
ｆ一（３ｈ一（２０
３
５１０
６６
８４
４６
５５
７），５
不等式来表示，进而非线性规划模型可以表述为
ｒａｉｎ＾（嚣）
ｓ．ｔ．
Ｃｉ（ｚ）＝０，ｉ—ｉ，…，３掰，嘶（聋）≥０，
ｉ＝３Ｍ＋１，…，４Ｍ＋４ｎ
。
对于这个约束优化闻题可以应用增广Ｌａｇｒａｎｇｅ方法通过求勰一淳襄无约束优讫闯题得戮解决，
ｒａｉｎ
Ｐ（嚣，Ａ，盯）一
３Ｍ
４），Ｌ＝１２。
解掣＝２５．
在图１（ｂ）中，札一９，
ｌ一（３ｈ一（１０解
５６６４８６４５５５８４７３
＾（ｚ＞＋∑［一左芦ｆ（：）＋ｏ。ｓ蟊ｅ；（鬈）】÷
甭
４肿４Ｍ
３）。
２０），￡＝１２．
ｆ—ＡｌｃＩ（ｚ）＋ｏ・５ａｉｃｌ２（ｚ）；
Ｑ（互）＜；ｂ／ａｌ
＂＝２８．
∑ｌ净澎Ｈｌ
算法ＡＬＭ：步１
在躁ｌ（ｃ）中，摊＝１０，
ｌ一（４
ｈ一（２１
５１０４８９８４２８７７６８５９４８），
一０．５走２旭；否刚
其中口＞０是参数，Ａ是Ｌａｇｒａｎｇｅ乘子．
给定初始值ｚｌ∈Ｒｚ井３擗１，Ａｎ’∈
３）．Ｌ＝１３．
解”一４０．
●
垂
‘
１
６
●
１０
’
２
●
｜
７
５
９
３
８
（ｃ）ｎ＝ｌＯ
匿１
Ｆｉｇ．１
三种情况解酶毽零
ｏｆｓｏｌｕｔｉｏｎｓｆｏｒｔｈｒｅｅ
ｃａｓｅｓ
Ｉｌｌｕｓｔｒａｔｉｏｎｓ
３１２
大连瑷王大
与经典的启发式算法如下次适应、首次适应
学学摄
第４８卷
例子各个算法的计算结果和增广Ｌａｇｒａｎｇｅ算法懿计算辩闭．
稔最佳适应籀毙，增广Ｌａｇｒａｎｇｅ算法在计算的糖确度方面有很大提高，表１给出了针对上面３个
袭１
Ｔａｂ．１
与经典翡启发式方法的数值毙较
Ｎｕｍｅｒｉｃａｌｃｏｍｐａｒｉｓｏｎｓｗｉｔｈｃｌａｓｓｉｃａｌｈｅｕｒｉｓｔｉｃｍｅｔｈｏｄｓ
＾耐ｎ
ｔＡＬＭ／ｍｉｎ
ＮＦＤＨ筹法
８９
ｌＯ
ＦＦＤＨ箕法
３５
ＢＦＤＨ算法
３７４１
ＡＬＭ箕法
２５
３Ｓ３８
５４
３
９
３８
５４
２８
４０
５３３５
注；，｜为褥子数量＃矗辩｛。秀最，ｌ、爨霾；ｔＡＬＭ秀ＡＬＭ算法诤冀辩惩
３
结语
ｏｎ
ｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌ
Ａｐｐｌｉｅｄ
ｂｉｎ
ｐａｃｋｉｎｇｐｒｏｂｌｅｍｓ［Ｊ］．
２００２。
Ｄｉｓｃｒｅｔｅ
Ｍａｔｈｅｍａｔｉｃｓ，１２３／１２４：
本文绘出二维装箱问题戆嚣线性规燃模型，以变分分析为工具建立了这一非线性规划问题的最优性条件，并用增广Ｌａｇｒａｎｇｅ方法对它求解．数值结采表曙，对不超过ｌｏ个物晶的装禳闻题，用该方法可以求得精确解，从计算时间上稽，对这样规模的阅题，该方法比经典的启发式方法要优越．如俺把毒蓦线性规划方法用予有效求解大规模二维装箱问题是以后值得研究的课题．
［２３
３７３—３９０Ｌ（）ＤＩ
Ａ。ＭＡＲＴＥＬＬＯＳ。ＶＩＧＯＤ。Ａｐｐｒｏｘｉｍａｔｉｏｎ
ｆｏｒ
ｔｈｅ
ｏｒｉｅｎｔｅｄ
ａｌｇｏｒｉｔｈｍｓｐａｃｋｉｎｇ
ｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌｂｉｎ
ｐｒｏｂｌｅｍ秘］。ＥｕｒｏｐｅａｎＪｏｕｒｎａｌｏｆＯｐｅｒａｔｉｏｎａｌ
Ｒｅｓｅａｒｃｈ．１９９９，１１２：１５８－１６６
［３］武晓今．朱仲英．嚣维装箱问题的一种寅现方法［Ｊ］．
缴型电脑应翅，２００３，１９（４）：２０—２３
［４］ＭＡＲＴＥＬＬＯＳ，Ｍ（）ＮＡｅｌＭ，ＶＩＧＯ
ａｐｐｒｏａｃｈ
ｔｏ
Ｄ．Ａｎｅｘａｃｔ
ｔｈｅ
ｏｎ
ｓｔｒｉｐ—ｐａｃｋｉｎｇ
ｐｒｏｂｌｅｍ
［Ｊ］．
ＩＮＦＯＲＭＳＪｏｕｒｎａｌ
参考文献：
［１］ＬＯＤＩＡ．ＭＡＲＴＥＬＬＯＳ，ＶＩＧＯ
Ｄ．Ｒｅｃｅｎｔａｄｖａｎｃｅｓ
Ｃｏｍｐｕｔｉｎｇ，２００３，ＩＳ：３１０。３１９
Ｉｓ］ＲＯＣＫＡＦＥＬＬＡＲ
Ｒ
Ｔ，ＷＥＴＳＲｊ玫Ｖａｒｉａｔｉｏｎａｌ
Ｙｏｒｋ；Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，１９９８
Ａｎａｌｙｓｉｓ［Ｍ］．Ｎｅｗ
Ａｎｏｎｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇｍｏｄｅｌｆｏｒｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌｓｔｒｉｐ－ｐａｃｋｉｎｇ
ｐｒｏｂｌｅｍａｎｄ
ＹＵ
ｉｔｓ
ｎｕｍｅｒｉｃａｌｍｅｔｈｏｄ
Ｓｈａｏ．ｗｕ３，ＺＨＡＮＧ
Ｌｉ－ｗｅｉ’１
Ｈｏｎｇ—ｘｉａｌｔ２，ＺＨＡＮＧ
（｛，ＤｅｐａｒｔｍｅｎｔｏｆＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓ・ＤａｌｉａｎＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ。Ｄａｌｉａｎ１１６０２４．Ｃｈｉｎａ；
２．ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓａｎｄＰｈｙｓｉｃｓ・ＳｈａｎｇｈａｉＵｎｉｖｅｒｓｉｔｙｏｆＥｌｅｃｔｒｉｃＰｏｗｅｒ，Ｓｈａｎｇｈａｉ
２０００９０．Ｃｈｉｎａ；
３．ＳｃｈｏｏｌｏｆＥｌｅｃｔｒｏｎｉｃａｎｄＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，ＤａｌｉａｎＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｄａｌｉａｎ１１６０２４。Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ａｓａ＋ｃｌａｓｓｏｆｃｏｍｂｉｎａｔｏｒｉａｌｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓｗｉｔｈｍａｎｙｉｍｐｏｒｔａｎｔａｐｐｌｉｃａｔｉｏｎｓ，ｔｗｏ—ｄｉｍｅｎｓｉｏｎａｌｓｔｒｉｐ—ｐａｃｋｉｎｇｐｒｏｂｌｅｍｓ
ａｒｅ
ｑｕｉｔｅｄｉｆｆｉｃｕｌｔ
ａｓ
ｔｏａ
ｂｅｓｏｌｖｅｄａｃｃｕｒａｔｅｌｙ
ａｓ
ｔｈｅｙ
ａｒｅ
ＮＰｈａｒｄ．
Ａｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌｓｔｒｉｐ—ｐａｃｋｉｎｇｐｒｏｂｌｅｍｉｓｆｏｒｍｕｌａｔｅｄｔｈｅｎｏｔｉｏｎｏｆｔａｎｇｅｎｔ
ｃｏｎｅｓ
ｎｏｎｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇ（ＮＬＰ）ｍｏｄｅｌａｎｄ
ｔｏ
ｉｎｖａｒｉａｔｉｏｎａｌａｎａｌｙｓｉｓｉｓｅｍｐｌｏｙｅｄｅｓｔａｂｌｉｓｈｔｈｅｆｉｒｓｔ—ｏｒｄｅｒｏｐｔｉｍａｌｉｔｙ
ｔｏ
ｃｏｎｄｉｔｉｏｎｓｆｏｒｔｈｅＮＬＰｐｒｏｂｌｅｍ．ＴｈｅａｕｇｍｅｎｔｅｄＬａｇｒａｎｇｅｍｅｔｈｏｄｉｓｐｒｅｓｅｎｔｅｄ
ｓｏｌｖｅｔｈｉｓＮＬＰ
ｐｒｏｂｌｅｍａｎｄｓｐｅｃｉｆｉｃｐｒｏｂｌｅｍｓ
ａｒｅ
ｓｏｌｖｅｄｂｙｉｔ．ＮｕｍｅｒｉｃａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅａｕｇｍｅｎｔｅｄＬａｇｒａｎｇｅ
ｔｏ
ｍｅｔｈｏｄｉｓｓｕｉｔａｂｌｅｆｏｒｓｏｌｖｉｎｇｔｈｉｓＮＬＰｐｒｏｂｌｅｍａｎｄｉｔｉｓａｂｌｅ
ｐｒｏｂｌｅｍｓｉｎｖｏｌｖｉｎｇｕｐＫｅｙ
ｔｏ
ｆｉｎｄ
ｅｘａｃｔ
ｓｏｌｕｔｉｏｎｓ
ｔｏ
ｓｔｒｉｐ—ｐａｃｋｉｎｇ
１０ｉｔｅｒｎｓ．
ｓｔｒｉｐ—ｐａｃｋｉｎｇ
ｗｏｒｄｓ：ｔｗｏ—ｄｉｍｅｎｓｉｏｎａｌ
Ｌａｇｒａｎｇｅｍｅｔｈｏｄ
ｐｒｏｂｌｅｍ；ｆｉｒｓｔ—ｏｒｄｅｒｏｐｔｉｍａｌｉｔｙｃｏｎｄｉｔｉｏｎｓ；ａｕｇｍｅｎｔｅｄ
二维装箱问题非线性规划模型和算法
作者：作者单位：
于洪霞， 张绍武， 张立卫， YU Hong-xia， ZHANG Shao-wu， ZHANG Li-wei
于洪霞,YU Hong-xia(大连理工大学,应用数学系,辽宁,大连,116024;上海电力学院,数理系,上海,200090)， 张绍武,ZHANG Shao-wu(大连理工大学,电子与信息工程学院,辽宁,大连,116024)， 张立卫,ZHANG Li-wei(大连理工大学,应用数学系,辽宁,大连,116024)大连理工大学学报
JOURNAL OF DALIAN UNIVERSITY OF TECHNOLOGY2008,48(2)1次
刊名：英文刊名：年，卷(期)：被引用次数：
参考文献(5条)
1.ROCKAFELLAR R T;WETS R J B Variational Analysis 1998
2.MARTELLO S;MONACI M;VIGO D An exact approach to the strip-packing problem 20033.武晓今;朱仲英 二维装箱问题的一种实现方法[期刊论文]-微型电脑应用 2003(04)
4.LODI A;MARTELLO S;VIGO D Approximation algorithms for the oriented two-dimensional bin packingproblem[外文期刊] 1999(1)
5.LODI A;MARTELLO S;VIGO D Recent advances on two-dimensional bin packing problems[外文期刊]2002(1/3)
引证文献(1条)
1.王石 一种解决矩形布局问题的启发式快速算法[期刊论文]-计算机技术与发展 2011(3)
本文链接：http://d.g.wanfangdata.com.cn/Periodical_dllgdxxb200802028.aspx