第六章♂整数规划 本章要求 癱理解整数规划的含义 掌握分枝定界法的思想和方法 掌握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问题的最优解