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

第四章整数规划与分配问题整数规划的特点及作用分配问题与匈牙利法分枝定界法割平面法应用举例1ppt课件1整数规划的特点及应用在实际问题中,全部或部分变量取值必须是整数。比如人或机器是不可分割的,选择地点可以设置逻辑变量等。在一个线性规划问题中要求全部变量取整数值的,称纯整数线性规划或简称纯整数规划;只要求一部分变量取整数值的,称为混合整数规划。2ppt课件对整数规划问题求解,有人认为可以不考虑对变量的整数约束,作为一般线性规划问题求解,当解为非整数时,用四舍五入或凑整方法寻找最优解。当变量取值较小时,得到的解可能与实际整数最优解差别很大。若问题中整数变量的数目很大,则凑整方法的组合数目很多。:如果不考虑整数约束(松弛问题)用图解法得考虑到整数约束,用凑整法求解时,比较四个点(4,3),(4,2),(3,3),(3,2),前三个都不是可行解,第四个虽然是可行解,但z=13不是最优。实际问题的最优解为(4,1)这时z*=14。最优解为(,)。4ppt课件逻辑(0-1):定义逻辑变量又设M为任意大的正数,则约束条件可以改写为:5ppt课件定义逻辑变量:此时约束条件可以改写为:≤4,则x2≥1(第一组条件);否则当x1>4时,x2≤3(第二组条件).定义逻辑变量:又设M为任意大正数,则问题可表达为:需注意,当约束为大于时,右端项中用减号。,其生产费用函数表示为其中Kj是同产量无关的生产准备费用,问题的目标是使所有产品的总生产费用为最小,即8ppt课件定义逻辑变量(表示是否生产产品j)又设M为任意大正数,为了表示上述定义,引入约束:显然,当xj>0时,yj=1。9ppt课件将目标函数与约束条件合起来考虑有:由此看出,当xj=0时,为使z极小化,应有yj=010ppt课件