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

第四章整数规划与分配问题?对于线性规划问题,最优解可能是分数或小数。但是对于某些问题,会要求解答必须是整数(称为整数解)。?对于所求解是机器的台数、完成工作的人数、装货的车数、集装箱数量等;?对于一些决策变量必须取Boolean值时,如要不要在某地建工厂,可选用一个逻辑变量x,令x=0表示不在该地建厂,x=1表示在该地建厂。?这时,分数或小数的解就不合要求,我们称这样的问题为整数规划。例:某厂拟用集装箱托运甲乙两种货物,每箱的体积、重量、可获利润以及托运所受限制如下表:货物体积米3/箱重量百斤/箱利润百元/箱甲乙54 252010托运限制2413问两种货物各托运多少箱,可使获得的利润为最大?????????????,且为整数,013522445:102021212121xxxxxxSTxxMaxZ能否先不考虑对变量的整数约束,作为一般线性规划来求解,当解为非整数的时候可以用“四舍五入”或“凑整”方法寻找最优解???对于变量取值很大时,用上述方法得到的解对于变量取值很大时,用上述方法得到的解与最优解差别不大;但当变量取值较小时,得与最优解差别不大;但当变量取值较小时,得到的解就可能与实际整数最优解差别很大。到的解就可能与实际整数最优解差别很大。??当问题规模较大(决策变量较多)时,用当问题规模较大(决策变量较多)时,用““凑整凑整””方法来算工作量很大。方法来算工作量很大。例:某线性规划问题最优解为(x1, x2) = (, ),用凑整法需要比较与上述数据最接近的几种组合:(4, 5), (4, 6), (5, 5), (5, 6),共四种组合。若问题中有10个整数变量,则解组合达到210 = 1024个整数组合。且最优解未必在这些组合中。例:求整数规划问题的最优解????????????且均取整数值,0,:用图解法得最优解为( , )如果不考虑整数约束(称为整数规划问题的松弛问题)最优解为(4 , 1),z*= 14。凑整法求解:比较四个点(4 , 3),(4 , 2),(3 , 3),(3 , 2),前三个都不是可行解,第四个虽然是可行解,但z=13 不是最优解。(4,1)主要内容一、整数规划的特点及作用一、整数规划的特点及作用二、分配问题与匈牙利法二、分配问题与匈牙利法三、分枝定界法三、分枝定界法四、应用举例四、应用举例第一节第一节整数规划的特点及作用整数规划的特点及作用第四章整数规划及分配问题一、整数规划的特点及作用一、?整数规划(Integer Programming) :决策变量要求取整数的线性规划。?如果所有的决策变量、技术系数和右端项都是非负整数,就称为纯整数规划。?如果所有的决策变量都是非负整数,技术系数和右端项为有理数,称为全整数规划。?如果仅一部分决策变量为整数,则称为混合整数规划。?如果变量取值仅限于0或1,称为0-1整数规划。一、整数规划的特点及作用一、-10-1整数规划整数规划?某公司拟在市东、西、南三区建立门市部。拟议中有7个位置(点)Ai供选择。规定?在东区,由A1,A2,A3三个点中至多选两个;?在西区,由A4,A5两个点中至少选一个;?在南区,由A6,A7两个点中至少选一个。?如选用Ai点,设备投资估计为bi元,每年可获利润估计为ci元,但投资总额不能超过B元。?问:应如何选址,可使年利润为最大?一、整数规划的特点及作用一、-10-1整数规划整数规划??????iijAAx不选选解:设010-1整数规划的一般形式:??????????????????????????)7,,1(,01112:7654321772211772211???jxxxxxxxxBxbxbxbSTxcxcxcMaxZj或???????),,1(,01:njxbAxSTXCMaxZjT?或0-1整数规划一般都是纯整数规划。