运筹学目标规划与整数规划1课件.ppt

3 0-1型整数规划 等价于 取整数 一 引例 例：某公司拟在东、西、南三区建立门市部，有7个位置Ai (i=1,2,…,7)可供选择。 在东区，由A1 、 A2 、 A3 三个点中至多选两个； 在西区由A4 、 A5 两个点中至少选一个； 在南区由A6 、 A 7两个点中至少选一个。 如选用点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大？ 解：引入0-1变量 当Ai点被采用 当Ai点没被采用 东区，由A1 、 A2 、 A3 三个点中至多选两个； 东区，由A1 、 A2 、 A3 三个点中至多选两个； 东区，由A1 、 A2 、 A3 三个点中至多选两个； 在西区由A4 、 A5 两个点中至少选一个； 分枝定界法步骤 一般求解对应的松驰问题，可能会出现下面几种情况： 若所得的最优解的各分量恰好是整数，则这个解也是原整数规划的最优解，计算结束。 若松驰问题无可行解，则原整数规划问题也无可行解，计算结束。 若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数规划的最优解，转下一步。 从不满足整数条件的基变量中任选 一个xl进行分枝，它必须满足xl ?[xl ] 或xl ?[xl ] +1中的一个，把这两个约束条件加进原问题中，形成两个互不相容的子问题（两分法）。 定界：把满足整数条件各分枝的最优目标函数值作为上（下）界，用它来判断分枝是保留还是剪枝。 剪枝：把那些子问题的最优值与界值比较，凡不优或不能更优的分枝全剪掉，直到每个分枝都查清为止。 例5-6 用分枝定界法求解： Max Z=4x1+3x2 s.t. 3x1+4x2 ? 12 4x1+2x2 ? 9 x1,x2 ? 0 整数 用单纯形法可解得相应的松驰问题的最优解（6/5，21/10）Z=111/10为各分枝的上界。 0 1 2 3 4 4 3 2 1 x1 x2 分枝：X1 ? 1,x1 ? 2 P1 P2 Max Z=4x1+3x2 s.t. 3x1+4x2 ? 12 4x1+2x2 ? 9 x1,x2 ? 0 整数 最优解（6/5，21/10） 3x1+4x2 ? 12 4x1+2x2 ? 9 两个子问题： （P1）Max Z=4x1+3x2 s.t. 3x1+4x2 ? 12 4x1+2x2 ? 9 x1,x2 ? 0 ， x1 ? 1 ，整数 用单纯形法可解得相应的（P1）的最优解（1，9/4） Z=10(3/4) （P2）Max Z=4x1+3x2 s.t. 3x1+4x2 ? 12 4x1+2x2 ? 9 x1,x2 ? 0 ， x1 ? 2 ，整数 用单纯形法可解得相应的（P2）的最优解（2，1/2） Z=9(1/2) 0 1 2 3 4 4 3 2 1 x1 x2 再对（P1）分枝：X1 ? 1 （P3） x2 ? 2 （P4） x2 ? 3 P1 P2 P3 P4 （P1）两个子问题： （P3）Max Z=4x1+3x2 s.t. 3x1+4x2 ? 12 4x1+2x2 ? 9 x1,x2 ? 0 ,x1 ? 1, x2 ? 2整数 用单纯形法可解得相应的（P3）的最优解（1，2） Z=10 X1 ? 2 X2 ? 2 X1 ? 1 X2 ? 3 P1:(1,9/4) Z=10(3/4) P4: (0,3) Z=9 P2:(2,1/2) Z=9(1/2) P3: (1,2) Z=10 P:(6/5,21/10) Z=111/10 原问题的最优解（1，2） Z=10 例5-7 用分枝定界法求解： Min Z= x1+4x2 s.t. 2x1+ x2 ? 8 x1+2x2 ? 6 x1,x2 ? 0 整数 用单纯形法可解得相应的松驰问题的最优解（10/3，4/3）Z=26/3为各分枝的下界。 0 1 2 3