07整数规划2(指派问题).ppt

第四节 0-1整数规划
0-1整数规划是线性规划及整数规划的一种特殊形式。
模型结构和形式是线性规划,只是决策变量取0或1。
例1:投资场所的选定——相互排斥的计划
某公司拟在城市的东、西、南三区建立分公司,待选位置有七个记为Ai。规定东区A1,A2,A3中至多选二个; 西区A4,A5中至少选一个; 南区A6,A7中至少选一个, 选用Ai点时估计设备投资为bi元, 每年可获利润估计为ci元, 投资总额不能超过d元, 问应选择哪几个点可使得年利润最大?
例2: 相互排斥的约束条件
某厂拟采用集装箱托运甲乙两种货物,每箱的体积、重量、可获利润以及托运(车运)所受限制如下表, 如采用船运, 其体积托运限制则为45,问两种货物托运多少箱,可使获得利润为最大?
解: 设x1, x2分别表示甲乙两种货物的托运箱数, 则其整数规划数学模型为
当采用船运方式
当采用车运方式
其中
一般情况下, m个约束条件中选择q个约束条件:
ai1x1+ai2x2+…+ainxnbi+yiM, i=1,2,…,m
y1+y2+…+ym=m-q
其中yi是0, 1变量,且只有q个取0。
0-1整数规划问题的解法
若有n个决策变量, 则可以产生2n个可能变量的组合, 故完全枚举是不可能的. 求解0-1整数规划问题的解法均是部分枚举法或称为隐枚举法(Implicit enumeration)
基本思想: 在2n个可能的变量组合中, 往往只有一部分是可行解. 只要发现某个变量组合不满足其中的某一约束条件时, 就不必要检验其它的约束条件是否可行。若发现一个可行解, 则根据它的目标函数值可以产生一个过滤条件(Filtering constraint), 对于目标函数值比它差的变量组合就不必再去检验它的可行性(类似分支定界法中的定界。实际上,隐枚举法是一种特殊的分支定界法)。在以后求解过程中, 每当发现比原来更好的可行解, 则依次替代原来的过滤条件(可减少运算次数, 较快地发现最优解)。
以例子说明上述求解方法
例1: 求解下述0-1整数规划问题
解:求解过程见下表
所以,最优解为(x1,x2,x3)T=(1,0,1)T, 最优值为8.
注: 当决策变量(x1, x2 , x3)按(0,0,0), (0,0,1), (0,1,0), (0,1,1),...方式取值时, 为了减少计算次数, 通常将目标函数中的决策变量的顺序按其系数的大小重新排序, 以使最优解能较早出现。对最大化问题, 按从小到大的顺序排列;对极小化问题, 则相反。
例2:求解下述0-1整数规划问题
解:重新排序为