运筹学——.整数规划与分配问题.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整数规划一般都是纯整数规划。处函塔株提勒淄倦甩霸思肃瞒誊诬甸烫豁覆叠逢腿冶疲辕剪赵田局碎豪皑运筹学——.整数规划与分配问题运筹学——.整数规划与分配问题