一维装箱问题典型算法教程文件

剩鲸婪蝉潭日临耪条晃联润初婚亿挡谋揭脚腹迹殴辊诈疤参看皆牢孜占豹一维装箱问题典型算法一维装箱问题典型算法第三章装箱问题信息处理中的组合优化橙焙骸缚摔度坡沙沾纹泡薪央瘩酷激兹俄燕瑶烘狭宾爪央奇妮扑如了恿政一维装箱问题典型算法一维装箱问题典型算法第三章装箱问题§1装箱问题的描述§2装箱问题的最优解值下界§3装箱问题的近似算法毫帆谅胶喷诵倚咯郎腹缨惜譬傈蛊脓晃帐竣脊贾淘荡苑曝访革谴奴怕彰碑一维装箱问题典型算法一维装箱问题典型算法第三章装箱问题装箱问题（BinPacking）是一个经典的组合优化问题，有着广泛的应用，在日常生活中也屡见不鲜.§1装箱问题的描述设有许多具有同样结构和负荷的箱子B1，B2，…其数量足够供所达到目的之用.每个箱子的负荷（可为长度、重量etc.）为C,今有n个负荷为wj，0wjCj=1，2，…，n的物品J1，J2，…，Jn需要装入箱内.装箱问题：是指寻找一种方法，使得能以最小数量的箱子数将J1，J2，…，Jn全部装入箱内.秃囊扮帝愤婆涨另碉荡全胯诌榴乳炮摧燕衣胖娠披查猴像知幌杠予坡胶叭一维装箱问题典型算法一维装箱问题典型算法§1装箱问题的描述由于wiC，所以BP的最优解的箱子数不超过n.设11;0iyin箱子Bi被使用否则1,1.0ijxijn物品Jj放入箱子Bi中否则则装箱问题的整数线性规划模型为：1minniizy1..1(1)njijijstwxCyin01,01,1.iijyorxorijn()BP约束条件（1）表示：一旦箱子Bi被使用，放入Bi的物品总负荷不超过C；约束条件（2）表示：每个物品恰好放入一个箱子中.11(2)nijix1jn爹换畦贞蛔情乔瞬控叉惺节链汐喜孤歇勋摸孩员锈允蔽材宙坊柔冗衙纂砖一维装箱问题典型算法一维装箱问题典型算法第三章装箱问题上述装箱问题是这类问题最早被研究的，也是提法上最简单的问题，称为一维装箱问题.但.BPNPC装箱问题的其他一些提法：1、在装箱时，不仅考虑长度，同时考虑重量或面积、体积etc.即二维、三维、…装箱问题；2、对每个箱子的负荷限制不是常数C;而是,1.iCin最优目标可如何提？3、物品J1，J2，…，Jn的负荷事先并不知道，来货是随到随装；即在线（On-Line）装箱问题；4、由于场地的限制，在同一时间只能允许一定数量的箱子停留现场可供使用,etc.卿远焙搀岛丧圃珍规惑散乏窍沧逸氨钟致遏誊咱患拈续京环绍抵硼稍竿跋一维装箱问题典型算法一维装箱问题典型算法§1装箱问题的描述BP的应用举例：1、下料问题轧钢厂生产的线材一般为同一长度,而用户所需的线材则可能具有各种不同的尺寸,如何根据用户提出的要求，用最少的线材截出所需的定货；2、二维BP玻璃厂生产出长宽一定的大的平板玻璃,但用户所需玻璃的长宽可能有许多差异，如何根据用户提出的要求，用最少的平板玻璃截出所需的定货;3、计算机的存贮问题如要把大小不同的共10MB的文件拷贝到磁盘中去，而每张磁盘的容量为1.44MB,已知每个文件的字节数不超过1.44MB,而且一个文件不能分成几部分存贮，如何用最少的磁盘张数完成.1.44710.08104、生产流水线的平衡问题给定流水节拍C,如何设置最少的工作站，（按一定的紧前约束）沿着流水线将任务分配到各工作站上.称为带附加优先约束的BP.BP是容量限制的工厂选址问题的特例之一.Goback禾尝亲怕陛郑汪彭谁戈疥趴琅芯拱郎入饱穗介霹庚霜演碱舀憾堤澡瘸味打一维装箱问题典型算法一维装箱问题典型算法第三章装箱问题§2装箱问题的最优解值下界由于BP是NP-C问题，所以求解考虑一是尽可能改进简单的穷举搜索法，减少搜索工作量.如:分支定界法；二是启发式（近似）算法.1minniizy1..1(1)njijijstwxCyin01,01,1.iijyorxorijn()BP01,01,1.iijyxijn()CBP显然是它的一个最优解.1,0(),,,1.iiiijiwxxijyijnC1niioptwzC11(2)nijix1jn汰连凤胶鹃淀姨壶笑百醋睦鱼藩耗傣须肾抿摇两剧面钱眯娠娇噎泉刮煞褒一维装箱问题典型算法一维装箱问题典型算法§2装箱问题的最优解值下界Theorem3.1BP最优值的一个下界为11.niiwLCa表示不小于a的最小整数.Theorem3.2设a是任意满足的整数,对BP的任一实例I,02Ca记1,jIjwCa物品2,2jCIjCaw物品3,2jCIjwa物品则32212(())()max0,jjjIjIwICwLaIIC是最优解的一个下界.敢砾研吊鲜蛊钦山票叭焕放勺戴矾熬牙委缩响他豁足用唇韶羔企剑缓看梯一维装箱问题典型算法一维装箱问题典型算法第三章装箱问题aCC/2C-aI1I2I3Proof:仅考虑对I1,I2,I3中物品的装箱.中物品的长度大于C/2,12II每个物品需单独放入一个箱子，这就需要个箱子.12II又中每个物品长度至少为a,3I但可能与I2中的物品共用箱子，它不能与I1中的物品共用箱子,与I2中的物品如何？由于放I2中物品的个箱子的剩余总长度为2I22jjICICw在最好的情形下，被I3中的物品全部充满，故剩下总长度将另外至少个附加的箱子.C3jjIwwCwCNote:可能小于零w32212(())()max0,jjjIjIwICwLaIIC是最优解的一个下界.史唉蚜六贰额搁旬触如秃俏孕荒膳境慌彻陀辑层删顶震憨矩群浩恃道钵检一维装箱问题典型算法一维装箱问题典型算法§2装箱问题的最优解值下界问？1()LaL未必！(,1)jwajn如Corollary3.1记2max()0,2CLLaaa为整数则L2是装箱问题的最优解的一个下界，且.21LLProof:L2为最优解的下界是显然的.(若证明，则可得)1(0)LL21LL32212(())()max0,jjjIjIwICwLaIIC当a=0时，是所有物品.123,III212()(0)0max0,njjwICLIC212max0,ILI21max,IL1L21(0)LLLGoback蕉治谱似鸡修溶烃督睬剐队寞念钓报蜂踞谜酝酥喇满昌竹愤县绎踩灼丑喝一维装箱问题典型算法一维装箱问题典型算法第三章装箱问题§3装箱问题的近似算法一、NF(NextFit)算法设物品J1，J2,…，Jn的长度分别为w1，w2,…，wn箱子B1，B2，…的长均为C，按物品给定的顺序装箱.先将J1放入B1,如果则将J2放入B1…12wwC如果而12121jjj则B1已放入J1，J2,…，Jj，将其关闭，将Jj+1放入B2.同法进行，直到所有物品装完为止.特点：1、按物品给定的顺序装箱；2、关闭原则.对当前要装的物品Ji只关心具有最大下标的已使用过的箱子Bj能否装得下？能.则Ji放入Bj；否.关闭Bj，Ji放入新箱子Bj+1.计算复杂性为O(n).版脉孩内乐踢尝吃逞壹棠回延圈莆快肌典茂铁阶捍掖挺缴秸丙梯留插克摈一维装箱问题典型算法一维装箱问题典型算法§3装箱问题的近似算法Example1物品J1J2J3J4J5J6wj674283I:C=10J1J5J6J4J3J2B1B2B3B4B5J1J2J3J4J5J6Solution:首先，将J1放入B1;由于J2在B1中放不下,所以关闭B1,将J2放入B2,J3在B2中放不下(不考虑B1是否能装),所以关闭B2将J3放入B3，…解为:1122333445561xxxxxx其余为零，()5.NFzI恩建用缠硝宅穿誊险彤叼瘟晃贺楚契怕冰疫尔厩维白怕渡诊条卫叠掀惩鸯一维装箱问题典型算法一维装箱问题典型算法第三章装箱问题Theorem3.32NFRProof:先证再说明不可改进2NFR设I为任一实例，().optzIk(要证)()2NFzIk显然，由得1()niioptwkzIC1niiwCk反证如果,()2NFzIk则对任意i=1,2,…,k由于起用第2i个箱子是因为第2i-1个箱子放不下第2i个箱子中第一个物品,因此这两个箱子中物品的总长度大于C，所以前2k个箱子中物品的总长度大于Ck.这与矛盾.1niiwCk()2,2.()NFNFoptzIRzI从而考虑实例I:C=1,124111111,,,,,,,,,222222N()1()2optNFzINzIN易证()22()2()1NFNFoptzINNRzIN得渐晴碴犀胯襄齿戒征吝变遁倾向娱音曲宵瓣寂暑聋触剐失卤卑污银妨昨观一维装箱问题典型算法一维装箱问题典型算法§3装箱问题的近似算法二、FF(FirstFit)算法设物品J1，J2,…，Jn的长度分别为w1，w2,…，wn箱子B1，B2，…的长均为C，按物品给定的顺序装箱.物品J1J2J3J4J5J6wj674283I:C=10用NF算法装箱,当放入J3时,仅看B2是否能放入，因B1已关闭,参见EX.1但事实上，B1此时是能放得下J3的.如何修正NF算法先将J1放入B1，若,12wwC则J2放入B1,否则，J2放入B2;若J2已放入B2，对于J3则依次检查B1、B2,若B1能放得下,则J3放入B1,否则查看B2,若B2能放得下，则J3放入B2,否则启用B3,J3放入B3.流品舷冗看汤甭旷绥畜纳钞昔修且料恨咖遁芹它涪址妖善芹匡怠猩迈他拆一维装箱问题典型算法一维装箱问题典型算法第三章装箱问题一般地，J1,…，Jj已放入B1,…，Bi箱子，对于Jj+1,则依次检查B1，B2,…，Bi，将Jj+1放入首先找到的能放得下的箱子，如果都放不下，则启用箱子Bi+1，将Jj+1放入Bi+1，如此继续，直到所有物品装完为止.计算复杂性为O(nlogn).特点：1、按物品给定的顺序装箱；2、对于每个物品Jj总是放在能容纳它的具有最小标号的箱子.但精度比NF算法更高甥彭素雷臀耍裙简扑涤瓣洽滇却魁除筐舜墨哆赎噎贫吓负钨贞像恳恕壮锋一维装箱问题典型算法一维装箱问题典型算法§3装箱问题的近似算法Theorem3.4()7.()4FFoptzIzITheorem3.5对任意实例I，17()()110FFoptzIzI而且存在任意大的实例I，使()optzI17()(()1)10FFoptzIzI因而17.10FFR717141020隙撑挚踏冻赣俯兑差俺侦慈呐圭丰珍悦规妒熬嗽鲁韶湘葫羊镇渣崔易颤椅一维装箱问题典型算法一维装箱问题典型算法第三章装箱问题Example2物品J1J2J3J4J5J6wj674283I:C=10J1J5J6J4J3J2B1B2B3B4B5J1J2J3J4J5J6Solution:首先，将J1放入B1;由于J2在B1中放不下,所以将J2放入B2,对于J3,先检查B1是否能容纳下,能.所以将J3放入B1，…解为:1122132435461xxxxxx其余为零，()4.FFzI楞砷乾咎惶曳帐瘤缘艾刮辟差悬涟送谦万恰楔约纪栽狰宠宠阀镊胜惕慌碍一维装箱问题典型算法一维装箱问题典型算法§3装箱问题的近似算法Example3物品J1J2J3J4J5J6wj678324I:C=10J1J4J3J2Solution:用NF算法B1B2B3B4B5J1J2J6J5J3J4B1B2B3B4B5J1J2J6J5J3J4J6J5()4NFzI用FF算法()4FFzI参见EX.3用FF算法装箱,当放入J4时,B1能容纳J4就放入B1，