运筹学——.整数规划与分配问题.ppt

第四章整数规划与分配问题须锹镀插勋锣遥瑞暇荷央渗发舅坊资铃墩叮趋芽蛰粥架柜钳毖蘑遁动辟耪运筹学——.整数规划与分配问题运筹学——.整数规划与分配问题对于线性规划问题,最优解可能是分数或小数。但是对于某些问题,会要求解答必须是整数(称为整数解)。对于所求解是机器的台数、完成工作的人数、装货的车数、集装箱数量等;对于一些决策变量必须取Boolean值时,如要不要在某地建工厂,可选用一个逻辑变量x,令x=0表示不在该地建厂,x=1表示在该地建厂。这时,分数或小数的解就不合要求,我们称这样的问题为整数规划。谍弓谣髓屠妊引孜替缚田励腐垦讶佣夏柠帘尾俄楞轧恫蔬良康医平凿拾跃运筹学——.整数规划与分配问题运筹学——.整数规划与分配问题例:某厂拟用集装箱托运甲乙两种货物,每箱的体积、重量、可获利润以及托运所受限制如下表:货物体积米3/箱重量百斤/箱利润百元/箱甲乙54252010托运限制2413问两种货物各托运多少箱,可使获得的利润为最大?能否先不考虑对变量的整数约束,作为一般线性规划来求解,当解为非整数的时候可以用“四舍五入”或“凑整”方法寻找最优解?履臀垄灿证遏楞岸壮也渍阎牡慨害拧营河哼梯泅搅阐玉会淌煎今暖址萨忽运筹学——.整数规划与分配问题运筹学——.整数规划与分配问题对于变量取值很大时,用上述方法得到的解与最优解差别不大;但当变量取值较小时,得到的解就可能与实际整数最优解差别很大。当问题规模较大(决策变量较多)时,用“凑整”方法来算工作量很大。例:某线性规划问题最优解为(x1,x2)=(,),用凑整法需要比较与上述数据最接近的几种组合:(4,5),(4,6),(5,5),(5,6),共四种组合。若问题中有10个整数变量,则解组合达到210=1024个整数组合。且最优解未必在这些组合中。陌捉挛挚玫千合恼接邑建税纹转掏稗汕氧种离膛吱倒扦汕冤侧巧嘛钮民娶运筹学——.整数规划与分配问题运筹学——.整数规划与分配问题例:求整数规划问题的最优解解:用图解法得最优解为(,)如果不考虑整数约束(称为整数规划问题的松弛问题)最优解为(4,1),z*=14。凑整法求解:比较四个点(4,3),(4,2),(3,3),(3,2),前三个都不是可行解,第四个虽然是可行解,但z=13不是最优解。(4,1)根琉售情揣***蹿毙喧录气躯哑连奥或矽映焰浚协筑休拣啸褂坷梁就昂吠伍运筹学——.整数规划与分配问题运筹学——.整数规划与分配问题主要内容一、整数规划的特点及作用二、分配问题与匈牙利法三、分枝定界法四、应用举例晓侗惋甩鞘蒙仲党匙键磋蒙馁崖瞳蚜砍割颅袋静柱摇肩筋汾蛾盛逆虱捉酵运筹学——.整数规划与分配问题运筹学——.整数规划与分配问题第一节整数规划的特点及作用第四章整数规划及分配问题拳查靠望吕洒嫌窍哗宾盏焚懦煎慢驻蚁戒衷俊车淀舵更侗仰簧排痔贡剥奈运筹学——.整数规划与分配问题运筹学——.整数规划与分配问题一、整数规划的特点及作用(IntegerProgramming):决策变量要求取整数的线性规划。如果所有的决策变量、技术系数和右端项都是非负整数,就称为纯整数规划。如果所有的决策变量都是非负整数,技术系数和右端项为有理数,称为全整数规划。如果仅一部分决策变量为整数,则称为混合整数规划。如果变量取值仅限于0或1,称为0-1整数规划。局步夫喷蹋袖趁离拙苹掸紊助蜗汲砖剔纶琐霞嫂负阮钾笔粪炼郊熊靖处裂运筹学——.整数规划与分配问题运筹学——.整数规划与分配问题一、整数规划的特点及作用-1整数规划某公司拟在市东、西、南三区建立门市部。拟议中有7个位置(点)Ai供选择。规定在东区,由A1,A2,A3三个点中至多选两个;在西区,由A4,A5两个点中至少选一个;在南区,由A6,A7两个点中至少选一个。如选用Ai点,设备投资估计为bi元,每年可获利润估计为ci元,但投资总额不能超过B元。问:应如何选址,可使年利润为最大?变叭皂揣苹丧椅协砂麦捉饰及膝埔纷梳滚恤硕辑串墙晾训萨侵匿币寸哀模运筹学——.整数规划与分配问题运筹学——.整数规划与分配问题一、整数规划的特点及作用-1整数规划0-1整数规划的一般形式:0-1整数规划一般都是纯整数规划。厂勘滚艰枚乞芬浴吞噶展砖兑壹矽父嫂残愿橱羽旅拜难泉霸爷搭辰颁保籽运筹学——.整数规划与分配问题运筹学——.整数规划与分配问题