第六章♂整数规划 本章要求 癱理解整数规划的含义 掌握分枝定界法的思想和方法 掌握0-1变量的含义和用法 掌握指派问题的算法 微机求解 OR3
OR3 1 第六章 整数规划 本章要求 理解整数规划的含义 掌握分枝定界法的思想和方法 掌握0-1变量的含义和用法 掌握指派问题的算法 微机求解
6.1整数规划问题的提出 癱决策问题中经常有整薮要求,如人数 件数、机器台数、货物箱数...如何解 决?四舍五入不行,枚举法太慢 问题分类:纯整数规划、混合整数规划 0-1整数规划 专门方法:分枝定界法、割平面法、隐 枚举法、匈牙利法 OR3
OR3 2 6.1 整数规划问题的提出 决策问题中经常有整数要求，如人数、 件数、机器台数、货物箱数……如何解 决？四舍五入不行，枚举法太慢 问题分类：纯整数规划、混合整数规划、 0-1整数规划 专门方法：分枝定界法、割平面法、隐 枚举法、匈牙利法
问题举例 某集装箱运输公司,箱型标准体积24m,重量 13T,现有两种货物可以装运,甲货物体积5m3 重量2T、每件利润2000元;乙货物体积4m3 重量5T、每件利润1000元,如何装运获利最 多 豢maxz=2000X1+1000x2 5X1+4X2≤24 2x1+5X2≤13 x1,x2≥0且为整数 解此LP问题,得:X1=4.8,Ⅹ2=0 显然不是可行解 OR3
OR3 3 问题举例 某集装箱运输公司，箱型标准体积24m3，重量 13T,现有两种货物可以装运，甲货物体积5m3 、 重量2T、每件利润2000元；乙货物体积4m3 、 重量5T、每件利润1000元，如何装运获利最 多？ maxZ=2000x1+1000x2 5x1+4x2≤24 2x1+5x2 ≤13 x1.x2 ≥0且为整数 解此LP问题，得：X1=4.8，X2=0 显然不是可行解
整数规划图解法 X2 B 23467X1 OR3
OR3 4 整数规划图解法 x2 x1 1 2 3 4 5 6 7 2 3 1 B A
图解法的启示 A(4.8,0)点是LP问题的可行解,不 是|P问题的可行解,B(4,1)才是P的 最优解 纯整数规划的可行解就是可行域中的整 数点 非整数点不是可行解,对于求解没有意 义,故切割掉可行域中的非可行解,不 妨碍整数规划问题的优化 P问题的最优解不优于LP问题的最优解 OR3
OR3 5 图解法的启示 A（4.8，0）点是LP问题的可行解，不 是IP问题的可行解，B（4，1）才是IP的 最优解 纯整数规划的可行解就是可行域中的整 数点 非整数点不是可行解，对于求解没有意 义，故切割掉可行域中的非可行解，不 妨碍整数规划问题的优化 IP问题的最优解不优于LP问题的最优解
62分枝定界法 思路:切割可行域,去掉非整数点。一次分枝 变成两个可行域,分别求最优解 例1.maxz=2000X1+1000X2 5X1+4X2≤24 21+5x≤13 X1,x2≥0且为整数 解:先不考虑整数要求,解相应的LP问题,得: X1=48x=0Z=9600不是可行解 z=9600是|P问题的上界,记为:Z=9600 OR3
OR3 6 6.2 分枝定界法 思路：切割可行域，去掉非整数点。一次分枝 变成两个可行域，分别求最优解 例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
分枝定界法(续) X1=4.8不符合要求,切掉45之间的可行域, 可行域变成两块,即原有约束条件再分别附加 约束条件x1≤4和x1≥5 原问题分解为两个 maxz=2000X1+1000X2 maxz=2000X1+1000X2 5X1+4X2≤24 5X1+4x2≤24 2x1+5X2s13(|P1)2×1+5X≤13(P2) X1≤4 X1≥5 X1,x2≥0且为整数 X1,x2≥0且为整数 OR3
OR3 7 分枝定界法（续） 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且为整数
分枝定界法(续) 癱不考虑整数要求,解相应LP问题。 解!P1得:X1=4,x2=1z=9000 解|P得:无可行解 此时可以断定|问题的下界为9000,记 为z=9000 米 由于目前的分枝末梢最大值是9000,故 P问题的上界便是9000。由于Z=Z,此 时已得|P问题的最优解,即 X1=4,X2=1.Z=9000 OR3
OR3 8 分枝定界法（续） 不考虑整数要求，解相应LP问题。 解IP1得：x1=4 ,x2=1 z=9000 解IP2得：无可行解 此时可以断定IP问题的下界为9000，记 为Z=9000 ٭由于目前的分枝末梢最大值是9000，故 IP问题的上界便是9000。由于Z=Z，此 时已得IP问题的最优解，即 x1=4,x2=1,Z=9000
分枝定界法的解题步骤 1、不考虑整数约束,解相应LP问题 癱2、检査是否符合整数要求,是,则得最 优解,完毕。否则,转下步 3、任取一个非整数变量x=b,构造两个 新的约束条件:Xs[b],X≥[b]+1,分别 加入到上一个LP问题,形成两个新的分 枝问题 癱4、不考虑整数要求,解分枝问题。若整 数解的Z值>所有分枝末梢的Z值,则得最 优解。否则,取Z值最大的非整数解, 继续分解,Goto3 (例题2讲解 OR3
OR3 9 分枝定界法的解题步骤 1、不考虑整数约束，解相应LP问题 2、检查是否符合整数要求，是，则得最 优解，完毕。否则，转下步 3、任取一个非整数变量xi=bi，构造两个 新的约束条件：xi ≤[bi] ,xi ≥ [bi]+1,分别 加入到上一个LP问题，形成两个新的分 枝问题。 4、不考虑整数要求，解分枝问题。若整 数解的Z值>所有分枝末梢的Z值，则得最 优解。否则， 取Z值最大的非整数解， 继续分解，Go to 3 （例题2讲解）
6301规划问题 癱某些特殊问题,只做是非选择,故变量设置简 化为0或1,1代表选择,0代表不选择 例4.600万元投资5个项目,求利润最大的方案? 项目投资额项目收益|约束条件 ①210160 ①②③中选1项 ②300210 ③④之中选1项 ③15060 选⑤必先选① o 13080 ⑤260180 OR3 10
OR3 10 6.3 0—1规划问题 某些特殊问题，只做是非选择，故变量设置简 化为0或1，1代表选择，0代表不选择。 例4. 600万元投资5个项目，求利润最大的方案？ 项目 投资额 项目收益 约束条件 210 160 中选1项 300 210 之中选1项 150 60 选必先选 130 80 260 180