Part II 整数规划 Integer Programming 整数规划 问题描述 分枝定界法 割平面法 指派问题 匈牙利算法 例1. 某工厂在计划期内要安排甲、乙两种仪器设备的生产，已知生 产仪器设备需要A、B两种材料的消耗以及资源的限制，如下 表。 问题：工厂应分别生产多少件甲、乙种仪器设备才能使工厂获 利最多？ 甲 乙 资源限制 材料 A 3 2 10 材料 B 0 2 5 单件获利 1 万元 1 万元 1 整数规划的问题描述 解解: 目标函数：目标函数： Max z = x1 + x2 约束条件：约束条件： 3 x1 + 2 x2 10 2 x2 5 x1，x2 0 为整数为整数 不考虑整数约束得到最优解：不考虑整数约束得到最优解： x1 =1.667, x2 = 2.5; z = 4.167 考虑整数约束得到最优解：考虑整数约束得到最优解： x1 = 2， x2 = 2； z = 4 整数规划的最优目标值小于相应线性规划的最优目标值整数规划的最优目标值小于相应线性规划的最优目标值(相当于相当于 附加一个约束附加一个约束) 1 整数规划的问题描述 整数规划问题：目标函数和约束条件仍旧是关于决策变量的 线性函数，只是要求部分或全部决策变量取整数。 )minPrminPrgogramIntegerMixgogramIntegerPure混合整数规划（）纯整数规划（整数规划如何求解整数规划问题？ 枚举法，or穷举法？ 相应线性规划求解后“化整”得到的解？ 将整数规划问题的相应线性规划求解后“化整”得到的解 不一定是原问题的最优解，有时甚至不是可行解。 1 整数规划的问题描述 1 整数规划的问题描述 求解整数规划问题的方法： Classical 分枝定界法（Branch and Bound Method） 割平面法（Cutting Plane Method） Advanced Method 分枝割平面法（Branch and Cut Method） 分枝定价法（Branch and Price Method） 分枝割平面定价法（ Branch Cut and Price Method） . 基本思想： B j=1,2,n，并求得其目标值，得到目标函数值的一个下界。 B&B步骤： 2 分枝定界法 第三步：分枝，定界 分枝： 任取非整数的分量 xj ，构造两个附加约束： 对问题 A 分别加入这两个约束，可得到两个子问题 A1和 A2 ， 显然这两个子问题的可行解集的并包含问题 A 的可行解集； 定界：根据前面分析，对每个当前问题 Ai 可以通过求解松 弛问题Bi ，以及找Ai 的可行解得到当前问题的上、下界 。 比较与剪枝：对当前子问题进行考察，若不需再进行计算， 则称之为剪枝。 一般遇到下列情况就需剪枝： 无可行解； 最优解符合整数约束； 最优值 z 小于当前的下界。 通过比较，若子问题不剪枝则返回 。 2 分枝定界法 jjxx 1jjxxB&B 终止条件： 当所有子问题都剪枝了，即没有需要处理的子问题时，达 到当前上界的可行解即原问题的最优解，算法结束。 2 分枝定界法 例 ：Max z = 40xMax z = 40x1 1+ 90x+ 90x2 2 s.t. 9xs.t. 9x1 1+7x+7x2 2 56 56 7x7x1 1+20x+20x2 2 70 70 x x1 1,x,x2 2 0 0 x x1 1,x,x2 2 取取整数整数 2 分枝定界法 2 分枝定界法 2 分枝定界法 2 分枝定界法 2 分枝定界法 2 分枝定界法 2 分枝定界法 2 分枝定界法 2 分枝定界法 2 分枝定界法 Exercise: Exercise: 用B&B算法求解下列ILP问题 Max Z= 4X1+ 3X2 s.t. 3X1+ 4X2 12 4X1+ 2X2 9 X1,X2 0, Integer 2 分枝定界法 用单纯形法可解得相应的松驰问题的最优解（6/5， 21/10）Z=111/10为各分枝的上界。 0 1 2 3 4 4321x1 x2 分枝：分枝：X1 1, X1 2 P1 P2 2 分枝定界法 x2 P1 P2 P3 P4 x1 再对（再对（P1）分枝：）分枝：X1 1 （P3） X2 2 （P4） X2 3 2 分枝定界法 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 2 分枝定界法 Exercise 2 分枝定界法 integer, 0,205462. .max21212121xxxxxxtsxxz2 分枝定界法 Integerxxxxxxxtsxxz, 0,121124124. .max212212121用分枝定界算法求解下面整数规划问题： 提示：利用人工变量！ 2 分枝定界法 小结: 分枝定界法优于穷举法（枚举法），属于隐式枚举。 与穷举法比较，计算量要小。 思考： （1）在什么情况下，分枝定界法的计算量会很大？ （2）分枝的方向(所选择的分枝变量)不同是否会对计算 量有影响？ 2 分枝定界法 3 割平面法 1958, 由Gomory 提出 Cutting Plane Method 设想：整数规划问题的最优解落在松弛线性规划问题的可行 域的一个顶点上。 基本思想： 首先，求解整数规划问题对应的线性松弛问题； 其次，增加线性约束条件（称为割平面），使得由原 可行域中切割掉一部分，这部分只包含非整数解，而不包 含任何整数可行解。 再求解新的线性规划问题，迭代。 该方法就是想构造一个适当的割平面，使得切割后的得到这 样的可行域：它的一个整点为顶点恰好是问题的最优解。 例例 3 割平面法 3 割平面法 构造割平面 433141 43 43xxxx43 41 41431xxx33041 43 434343xxxx割平面，切割方程 cut 添加cut后的松弛问题的单纯形表，应用对偶单纯形法求解： 3 割平面法 3 割平面法 3 割平面法 小结：小结： 割平面的构造方法很多，如分数割平面法。 割平面算法由于收敛速度较慢，单独应用情况较少，经 常与其他算法联合使用。 3 割平面法 4 指派问题 例：例： 有四个熟练工人，他们都是多面手，有四项任务要他们有四个熟练工人，他们都是多面手，有四项任务要他们 完成。若规定每人必须完成且只完成一项任务，而每人完完成。若规定每人必须完成且只完成一项任务，而每人完 成每项任务的工时耗费如下表所示。成每项任务的工时耗费如下表所示。 问如何分配任务使完成四项任务的总工时耗费最少？问如何分配任务使完成四项任务的总工时耗费最少？ 任务任务工时工时ABCD人员人员 人员人员 甲甲109781 乙乙58771 丙丙54651 丁丁23451 任务任务1111其其中：中：cij 为第为第 i 个工人为完个工人为完 成第成第 j 项任务时的工时消项任务时的工时消 耗；耗； cijm m 称为称为效率矩阵效率矩阵 项任务人去完成第当不指派第项任务人去完成第当指派第ji0ji1ijx01,2, 1, 1,2, 1, 1.min或数学模型：ijjijiijijijijxnixnjxtsxcz4 指派问题 求解算法： 隐枚举法 Implicit Enumeration 匈牙利算法（指派问题） 4 指派问题 定义：定义： 01整数规划是整数规划的特殊情形：它的变量xi 仅取值0 或1，这样的变量称为01变量，或二进制变量。 约束条件为： integer, 10ix定理定理 1 如果从效率矩阵如果从效率矩阵cijm m中每行元素分别减去一个常数中每行元素分别减去一个常数 ui，从，从 每列元素分别减去一个常数每列元素分别减去一个常数 vj ，所得新的效率矩阵所得新的效率矩阵bijm m的的 任务分配问题的最优解任务分配问题的最优解等价于等价于原问题的最优解。原问题的最优解。 定义定义：独立的独立的0元素元素 定理定理 2 ：关于矩阵中关于矩阵中0元素的定理康尼格元素的定理康尼格 若方阵中一部分元素为零，一部分元素非零，则覆盖方阵内所若方阵中一部分元素为零，一部分元素非零，则覆盖方阵内所 有零元素的最少直线数等于位于不同行、不同列的零元素的有零元素的最少直线数等于位于不同行、不同列的零元素的 最多个数。最多个数。 4 指派问题 匈牙利算法的基本思路： 根据定理 1变换效率矩阵，使矩阵中有足够多的 零。若矩阵中存在 m 个独立的零元素，就找到了 最优解 若覆盖变换后的效率矩阵零元素的直线少于m条， 就尚未找到最优解，设法进一步变换矩阵，增加 新的零元素。 4 指派问题 匈牙利算法的步骤：匈牙利算法的步骤： 第一步：变换效率矩阵，使每行每列至少有一个零第一步：变换效率矩阵，使每行每列至少有一个零 行变换：找出每行最小元素，从该行各元素中减去之行变换：找出每行最小元素，从该行各元素中减去之 列变换：找出每列最小元素，从该列各元素中减去之列变换：找出每列最小元素，从该列各元素中减去之 2210020112300023321012012230) 1 (023543)2(56)4(5778)5(8)7(910换变列换变行第二步：检查覆盖所有零元素的直线是否为第二步：检查覆盖所有零元素的直线是否为m条条 划线规则划线规则 1、逐行检查、逐行检查：若该行只有一个未标记的零，对其加：若该行只有一个未标记的零，对其加( )标记，将标记，将 ( ) 标记元素同行同列上其它的零打上标记元素同行同列上其它的零打上*标记。若该行有二个以上未标标记。若该行有二个以上未标 记的零，暂不标记，转下一行检查，直到所有行检查完；记的零，暂不标记，转下一行检查，直到所有行检查完； 2、逐列检查、逐列检查，若该列只有一个未标记的零，对其加，若该列只有一个未标记的零，对其加( )标记，将标记，将( )标标 记元素同行同列上其它的零打上记元素同行同列上其它的零打上*标记。若该列有二个以上未标记的标记。若该列有二个以上未标记的 零，暂不标记，转下一列检查，直到所有列检查完；零，暂不标记，转下一列检查，直到所有列检查完； 221*0*02)0(1123)0(*0)0(23221*00201123)0(0023查检列逐查检行逐3、重复、重复1、2后，可能出现后，可能出现三种情况三种情况； a. 每行都有一个每行都有一个 (0)，显然已找到最优解，令对应，显然已找到最优解，令对应(0)位置的位置的 xij=1； b. 仍有零元素未标记，此时，一定存在某些行和列同时有多个零，仍有零元素未标记，此时，一定存在某些行和列同时有多个零， 称为称为僵局状态僵局状态，因为无法采用，因为无法采用 1. 2 中的方法继续标记。中的方法