运筹与优化整数规划.pptVIP

第四章 整数规划 整数规划的含义 分枝定界法 割平面法 0-1整数规划的解法 指派问题的算法 第一节 整数规划问题的提出 决策问题中经常有整数要求，如人数、件数、机器台数、货物箱数……如何解决？四舍五入不行，枚举法太慢. 问题分类： 纯整数规划 (变量全为非负整数) 、混合整数规划(部分变量为整数)、0-1整数规划 (变量取为0或1). 专门方法：分枝定界法、割平面法、隐枚举法、匈牙利法. 问题举例 某集装箱运输公司，箱型标准体积24m3，重量13T,现有两种货物可以装运，甲货物体积5m3、重量2T、每件利润2000元；乙货物体积4m3、重量5T、每件利润1000元，如何装运获利最多？ 数模: maxZ=2000x1+1000x2 5x1+4x2≤24 2x1+5x2 ≤13 x1、x2 ≥0且为整数 解此IP问题,得: x1=4.8，x2=0 显然不是可行解. 整数规划图解法 x2 A(4.8，0)点是LP问题的可行解,不是IP问题的可行解，B(4，1)才是IP的最优解. 图解法的启示 纯整数规划的可行解就是可行域中的整数点. 非整数点不是(IP)的可行解，对于求解没有意义,故切割掉可行域中(IP)的非可行解，不妨碍整数规划问题的优化. (IP)的最优解不会更优于相应的(LP)的最优解. (IP)的最优解不能按相应(LP)的最优解取整而得. 注1: (LP)有最优解,其相应的(IP)可能无可行解. 注2: (LP)的最优解全为整数时,即得(IP)的最优解. 注1: (LP)无可行解,其相应的(IP)也无可行解. 第二节 分枝定界法 思路：切割可行域，去掉非整数点。一次分枝变成两个可行域，分别求最优解 例1. maxZ=2000x1+1000x2 5x1+4x2≤24 2x1+5x2 ≤13 x1、x2 ≥0 且为整数 解：先不考虑整数要求，解相应的(LP)问题，得： x1=4.8 x2=0 Z=9600 不是可行解 Z=9600是IP问题的上界，记为：Z=9600 例1 （续） X1=4.8不符合要求，切掉4—5之间的可行域，可行域变成两块，即原有约束条件再分别附 加约束条件x1 ≤4和x1 ≥5 原问题分解为两个 maxZ=2000x1+1000x2 maxZ=2000x1+1000x2 5x1+4x2≤24 5x1+4x2≤24 2x1+5x2 ≤13 ( IP1 ) 2x1+5x2 ≤13 (IP2) x1 ≤4 x1 ≥5 x1、x2 ≥0且为整数 x1、x2 ≥0且为整数 例1 （续） 不考虑整数要求，解相应(LP)问题。 解 (LP)1 得：x1=4 ,x2=1 z=9000 解 (LP)2 得：无可行解 此时可以断定IP问题的下界为9000，记为Z=9000 ?由于目前的分枝末梢最大值是9000，故IP问题的上界便是9000。由于Z=Z，此时已得IP问题的最优解，即 x1=4, x2=1, Z=9000 分枝定界法的解题步骤 问题（A） Max z = CX s.t. AX= b, X ≥ 0 且为整数 将问题（A）去掉整数约束的问题记为（B） 在分枝定界法过程中求解问题(B)，应有以下情况之一： ① (B)无可行解，则 (A) 亦无可行解，停止计算； ② (B)有最优解，并满足整数约束，即为(A)的最优解， 那么z* 同时是当前问题(A)最优目标值的上界和下界。停 止计算； ③ (B)有最优解 x 及最优值 z 但不符合整数条件。这时 得到当前问题(A)最优目标值的一个上界 z ＝z ,于是通过 以下判断可对此问题进一步计算。 分枝定界法的解题步骤（1） 分枝定界法的计算过程： 1、对原问题(A)，求