第9章整数规划与分配问题.pdf

第四章 整数规划与分配问题 Integer Linear Programming 数学模型 分枝定界法 0-1整数规划 分配问题 整数规划 简述 LP虽然用途广泛，但经常地，客观上要求 L.P.最优解中不能含有非整数值（如股票的 购买之解答），整数规划就是专门用来求 解这类问题的有效工具 •重点掌握：0-1 规划灵活应用、分枝定界 法。 提出问题 • 某厂生产A1 ，A2两种品牌电视，用B1 ，B2两种原 料，具体数据如下，求如何安排生产使利润最大 A1 A2 供应量 B1 30 （g/台） 20 80g B2 70 40 150g 利润 200 （元/g ）100 整数规划 数学模型 n max(min)z c x ∑ j j j 1 ⎧ n a x b ( , i ) , m1,2, , L =≤ =≥∑ ⎪ ij j i ⎪⎪ j 1 s .t . ⎨ 松弛问题 ⎪ xj ≥0 j 1,2n, , L ⎪ ⎪⎩ xj 部分或全部为整数 • 若所有 x 的解为整数，称为纯整数规划pure integer linear programming j • 若部分 xj 的解为整数，称为混合整数规划mixed integer linear programming • 若xj 只取0或1，成为0-1整数规划zero-one integer linear programming 整数规划的最优解不会优于其松弛问题的最优解 整数规划 注 释 • 最优解不一定在顶点上达到 • 最优解不一定是松弛问题最优解的邻近整 数解 • 整数可行解远多于顶点，枚举法不可取 整数规划问题的求解方法 整数规划问题的求解方法 分枝定界法branch and bound m