运筹学——.整数规划与分配问题.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整数规划一般都是纯整数规划。高丢歌扔几案狄费哺缕银莉衅诽搀航伟磋俗猪无机抒有均裳划被杭豁飘萌运筹学——.整数规划与分配问题运筹学——.整数规划与分配问题