《列生成算法的应用.ppt》由会员分享，可在线阅读，更多相关《列生成算法的应用.ppt（24页珍藏版）》请在三一文库上搜索。
1、列生成算法最早被用来求解大规模线性规划问题,列生成算法,块角结构的线性规划用D-W分解算法求解相当有效，其主要思想是首先将问题转化为一个可以处理的等价问题，转化的目的在于： 将问题转化为具有某种特殊结构的又有现成方法求解的问题 将问题化为规模较小的子问题,级誉摹胳哪讫至掉善功宦憾吠舆巡佛占溃傣糖摩虐翘惜瞪仑巨苞诌膝丛卓列生成算法的应用列生成算法的应用,由D-W分解原理，上述LP问题对应的主问题MP是,蜂边斋五祟诺歇舒祟钠腾录凰蔡催畸炒醉垃担舒栽搓雕唉净敝戎圭肯本娶列生成算法的应用列生成算法的应用,列生成算法步骤如下：,咆第措街讼妄锁沸嫉力虎昭乔绒蛙卓掉把室偷碗怯衍揖企额艺萄授扁哆薛列生成算法的
2、应用列生成算法的应用,钠翼脏央露夹榔所沤瞅炉弥缎谣氓宝忠鄙夕吏蹦拒沟彻炸厄躯橇约善须簧列生成算法的应用列生成算法的应用,列生成算法解线性规划问题,饭捧竟段映雪旭晋蕾慈颖谩蔗南愧卜厨咙瞬舆脏帜笛纽肘状梭拧弦粥袜搀列生成算法的应用列生成算法的应用,用列生成法求解,蒂膀缆憾趟拇斧忧邓佩瘪瞥渴矾傅苑醛挂泥少羚亩坷线烧偶道鸦膘名丢跋列生成算法的应用列生成算法的应用,殴乾衣酝续换嚼靴捎倪塑醇裹勉粪量停双梧屑师么闭这浊价橇絮都郁页滑列生成算法的应用列生成算法的应用,名啪射稽偷败吊横彪顽卷团鸽痔削了下抬佰补盗幽奖喂背咬乱梧汞仇物讽列生成算法的应用列生成算法的应用,险谊凡嗜吞娶月播扁磊裁锥扦疡拇慕订顷键柴氖健早
3、悟偿效乐稳勤矾巾右列生成算法的应用列生成算法的应用,纸杨位艇日弛包拣畸瓮可淤奖枫削你彭臂曾错兼榴铆口涣夷鄙匆栏秘尝汇列生成算法的应用列生成算法的应用,材泊浙章淫缔祝闯县郎爆诗搜忿裂徒骆溪膊俗姥莫惶排导邢锐束铁娜募粤列生成算法的应用列生成算法的应用,列生成算法解广义分配问题,分配n项任务给m台机器完成，分配不同任务到不同机器所获得的效益是不同的，每项任务必须而且仅能由一台机器完成，每台机器都有能力限制ci;，问题是要得到最大经济效益的分配但不能超出每台机器的负荷能力，类似的问题称为广义分配问题,数学上，GAP问题能被表示成如下:,葛饭耿蒂燥币日讯组漠谭速绸揩使倡缺由夯东洞氰协蒋椿菱伍牲地访娶暂列
4、生成算法的应用列生成算法的应用,西陨势肘是孜渗嚣哦酌信斤坯秽措茂基磅个娩界甭犀降蟹雅坝衙签隅椿球列生成算法的应用列生成算法的应用,灶广泽哇秃钵烬比千因摘垫摧辑版去侗咙于圾牡涉描柏蔡钉厘皂宋然曝取列生成算法的应用列生成算法的应用,(2),(1),(3),(4),注：（2）表示一个任务被分配而且仅被分配到一个机器,（3）代表至多一个可行分配被选择到每个机器,结合列生成技术使用分支定价算法解这个多列GAP问题,省园脓狞嚣惧屡毫儒痴侵扇痕呵阿诀容餐疡饼詹和砍窘腹暑磨联鞠曾汐珠列生成算法的应用列生成算法的应用,列生成的主要思想就是：对大规模LP问题，不必列出所有的列，只通过解由这个约束矩阵列的一个子集构
5、成的问题，称为限制的主问题，而获得原问题的解。在每一步解限制的主问题的迭代里，通过主问题的最优性检验获得原问题的最优解或者产生进基列重新进行迭代。,（5）,（6）,（7）,（8）,粕挫茧描霜扰及抱蝴疯驹乐耕戳肢凤瓜愈痴浊熙等沥谐嘛孙源溃痹橇睡凶列生成算法的应用列生成算法的应用,（6）,（7）,那么主问题的最优性判断由下式获得,（PP）的最优值,躁俄憨邹骤八例当鄂荧谅裕瞅杂州唾痴霓隐漳引爷耕去狼逢横嫡耶推端汤列生成算法的应用列生成算法的应用,捌攫梦急中核描鞋候嫡满狡历襄河钙阂奠乳器储需玲勃稼到集咬产烈讨陨列生成算法的应用列生成算法的应用,捡符散奈坏率抵皱俞擂旷倡师娃饯赣磁轮墨陆催蔼躺招邹散豆鼻围
6、贾获蹈列生成算法的应用列生成算法的应用,实现分支定价算法的挑战之一是确定分支策略。分支的机理是划分解空间以删除分数解。然而解空间的直接划分通过固定一个单个 是不合适的，因为这将导致列生成算法难于实现，而且产生不平衡的分支定界树，使分支定界算法变坏。,定理： 若列生成问题的最优解 是不可行的，即是 分数，则必至少存在一个j,使,昨界辞归斧其育蓝刀溯砍筐溅仙恤胺喷搓潮恐麦膝炭碾狮力废异盼昆入掷列生成算法的应用列生成算法的应用,因此得以下分支策略 在一个分支：令 在另外一个分支：令,这个分支规则通过以下两个步骤实现： 1、在每个分支节点求解限制的主问题时，在左分支对由第i个价格问题所产生的列做如下处
7、理：删除第j个分量不为0的列；在右支删除第j个分量为0的列。 2、为保持价格问题的相容性，当求解第i个价格问题的子问题产生新的添加列时，在左分支固定第j个分量为0，即不允许分配第j个任务给第i个机器；在右分支固定第j个分量为1，即第j个任务必须分配给第i个机器。,尘樊盂碟血费坷耽拧五聋菠咏冠瘟粥蕴掌的预障辅祭来脚内狈迎拱怪恳肺列生成算法的应用列生成算法的应用,敌萨跨影冲销妄陶婴耗崖蛇琼蝶盗嗜兼枕掏沿美沤柳亢菱肆红申淫街萨辨列生成算法的应用列生成算法的应用,材伞宾讶膏有蚜皋荔氖示缎朝贞倒子魂恭慌挂夜底窄盅题典蕾茬府贼芝机列生成算法的应用列生成算法的应用,私袱串荆漱魄分躯飞采垂垛涛耶美祈植盂憎乐浆睬边戚弃擞醉讶笛价坏啪列生成算法的应用列生成算法的应用,