2013参考数学建模常用方法：整数规划解读.ppt

第二章 整 数 规 划 1．整数规划的基本概念 2．分枝定界法解整数规划 3．０－１规划 4. 指派问题的解法 第一节 概 述 人们探讨某些线性规划问题，有时必须把全部或部分决策变量限制为整数。这样的线性规划问题，通常称为整数规划。作为线性规划的特殊情况，整数规划也有最小化和最大化之别。此外，整数规划还可以分成纯整数规划和混整数规划。二者的区别在于：前者的决策变量必定全部取整数。而后者的决策变量只是部分取整数。 例1 某医药公司现有两个制药厂A1和A2，三个销售店B1、B2 和 B3。公司打算由两个拟建的制药厂A3 和 A4 中选择一个，来兴建新厂。各销售店每周药品需求量见表2-1。各制药厂每周药品产量和每箱药品运费见表2-2。新厂投产后，估计每周的操作费（含折旧费）：A3 是100元，A4 是120元。在两个拟建的制药厂中，应当选择哪个呢？ 设：制药厂Ai 每周运到销售店Bj 的药品为xij 箱（i =1,2，3，4； j =1，2，3）； 两个老厂A1 和 A2 及一个新厂A3 和 A4 每周的 总费用为 y 元。新厂厂址的选择应该确保 y 达到 最小值。于是，y 是目标函数，xij、u 和 v 都是 决策变量。它们之间的关系可以表述为： y = 3x11 + 2x12 + 3x13（A1每周的运费） + 10 x21 + 5x22 + 8x23（A2每周的运费） + x31 + 3x32 +10x33（A3每周的运费） + 4x41 + 5x42 + 3x43（A4每周的运费） + 100 u（A3每周的操作费） + 120 v（A4每周的操作费） (1) u 和 v 全是 0－1 变量： 例1的数学模型为： 例2 某医疗器械厂生产A1和A2两种产品。出 厂前，每种产品均须经过两道工序：先用机器B1 制造，后由机器B2包装。每台产品的利润和加工 时间见表2-3。在下周内，机器B1和B2分别可以 使用45小时和6小时。问怎样安排下周的生产任 务，才能使所获利润最大？ 其中：“ xk′为整数 ” ,称为整数条件。 例2是最大化纯整数规划，其相应线性规划为： 整数规划常用的解法是分枝定界法和割平面法。一旦遇到仅含两个决策变量的情况，可以采用图解法，其计算方法与线性规划图解法大同小异，就不再赘述。 第二节 分 枝 定 界 法 分枝定界法可以用来求解纯整数规划和混整数规划，它是整数规划的常用解法。 第一步 第二步 主要特征是分枝。从相应线性规划的最优解中，任意选择一个不满足原整数规划整数条件的决策变量xj=bj。以使相应线性规划增加一个约束条件；xj小于bj的最大整数（或xj大于bj的最小整数），因而得到两个新的线性规划，称为分枝。其中每个新的线性规划，统称为枝。 第三步 主要特征就是定界，由各枝的最优值中选最大值，称为定界。而该最大值，称为界。最优值称为界的枝，称为界枝。 解：它是例2的数学模型，并且属于最大化纯整数规划。为便于叙述，我们将其记作A。现在利用分枝定界法求解之。 采取图解法或单纯形法，求得B的 最优解（x1 , x2）=（ 2.25 , 3.75 ） 最优值 ymax = 41.25。 分枝：由B的最优解中，选择决策变量x2=3.75，按照既定的原则写出B的两枝： 定界：由图可知。界为max { 39，41 } = 41。于是界枝是B2。但是，B2的最优解不满足A的整数条件，从而它不是A的最优解。因此，应当再次分枝。 第二次分枝：由B2的最优解中，选择决策变量 x1= 1.8，写出B2的两枝： 第三次分枝： 现在，已完成的求解过程和所得到的计算结果见下图： 第三次定界：由上图可知，界为max { 39, 37, 40 } = 40. 所以，界枝是B212。由于B212的最优解满足A的整数条件，它一定也是A的最优解。于是，原整数规划的最优解为： （x1，x2）=（0，5），最优值 ymax= 40。 例3是一个利用分枝定解法求解纯整数规划问题，其基本步骤也适用于混整数规划问题。 设按照方式 Aj下料的原料有 xj 根（j =1， 2，…，8）；所用原料为 y 根。于是，本下料问题的数学模型是： 采取单