第八章-整数规划.pptVIP

整数规划 8.1概述 在整数规划中，如果所有的变量都为非负整数，则称之为纯整数规划问题，如果只有一部分变量为非负整数，则称之为混合整数规划问题。在整数规划中，如果变量的取值只限于0和1，这样的变量称为0-1变量。在纯整数规划和混合整数规划问题中，常会有一些变量是0、1变量，如果所有的变量都是0、1变量，则称为0-1规划。 例1. 某医药公司现有两个制药厂A1和A2，三个销售店B1，B2，B3公司打算由两个拟建的制药厂A3和A4中选择一个，来兴建新厂，各销售店每周药品需求量见表1，各制药厂每周药品产量和每箱药品运费见表2，新厂投产后，估计每周的操作费（含折旧费）A3是100元，A4是120元，在两个拟建的制药厂中应当选择哪个呢？ 8.2 整数规划的图解法 例：某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量，可获利润以及托运所受限制如下表所示。甲种货物至多托运4件，问两种货物各托运多少件，可获利润最大。 性质： 任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。 8.3 分枝定界法 分枝定界法可以划分为三步： 第一步：主要特征是放宽就指删去整数条件 实现放宽之后，就能够得到三个结论：原整数规划的可行域真包含于相应线性规划的可行域。就最大化问题而言，原整数规划的最优值不大于相应线性规划的最优值。若相应线性规划的最优解满足原整数规划的整数条件，则它也是原整数规划的最优解。具体做法： ①删去整数条件，把原整数规划化成线性规划 ②求解相应线性规划 ③若相应线性规划最优解也是原整数规划最优解，则结束，否则转入第二步。 第二步： 主要特征是分枝。从相应线性规划的最优解中，任意选择一个不满足原整数规划整数条件的决策变量xj=bj以使相应线性规划增加一个约束条件；xj小于bj的最大整数或xj大于bj的最小整数，因而得到两个新的线性规划，称为分枝。其中每个新的线性规划统称为枝。 经过分枝之后，就有如下结论：原整数规划的可行域真包含于两枝可行域的并集。整数规划的最优解不大于两枝最优值的最大值。 具体作法：先列出两枝各自的数学模型，后计算每枝的最优解和最优值。 第三步： 主要特征是定界，由各枝的最优值中选最大值，称为定界。而该最大值，称为界，最优值称为界的枝，称为界枝。 可得结论：若界枝的最优解满足原整数规划的最优条件，则它也是原整数规划的最优解。 具体作法：进行定界，找出界枝。若界枝的最优解就是原整数规划的最优解，则计算过程便告结束；否则回到第二步。 例：在暑假期间，某同学准备徒步回家探亲，他把要带的物品放进包后，觉得还能多放5个单位重量的东西。为此，他列出拟放物品的清单，见下表，他认为：应使所增加的物品的总价值最大。基于以上考虑，他到底还要带哪些东西呢？ 隐枚举法 8.5 指派问题 例1.某医院的四名化验员（甲、乙、丙、丁）完成四项化验工作（A、B、C、D）所消耗的时间见表，哪个化验员担当哪项工作，可使它们总耗时最短。 建立该题的数学模型 求解最小化指派问题： 定理.若效率矩阵[bij]第i行最小值为bi，则效率矩阵分别为[bij]和[bij-bi]的最小化指派问题具有相同的最优解，把“第i行”换成“第j列”，“bi”换成“bj”依然成立。 求解步骤： ⑴在效率矩阵[bij]中，让每行（列）元素减去该行（列）元素的最小值，从而得到矩阵[cij] ⑵在矩阵[cij]中，首先找到含0最少的行，并且把其中的一个0括起来，即（0）；然后划掉与（0）同行或同列的0，即? ，不得在括?的前提下，相继完成其它各行 ⑶在矩阵[cij]中，若不能得到m个（0）则进行第四步；若能得到m个（0），则令与（0）=[cij]相对应的的xij=1，的决策变量等于0。这时，[xij]便是最优解。将最优解带入目标函数y的表达式，即得最优值。 ⑷遵循下列程序，在[cij]中画出直线：①在没有（0）的行，标上“√”；②在标上“√”的行中?所在的列，标上“√”；③在标上“√”的列中（0）所在的行标上“√”；④在没有标上“√”的行或已经标上“√”的列，都画上一条直线；⑤去掉“√”，而且将（0）和?重新写成0。 ⑸从未画上直线的元素中找出最小值。让画上直线的列中元素都加上该最小值，未画上直线的行中元素都减去最小值，随即去掉各行各列上的直线，并转入第2步。 当指派问题的系数矩阵，经过变换得到同行和同列中都有两个或两个以上0元素时，这时可以任选一行（列）中某一个0元素，再划去同行（列）的其它0元素，这时会出现多重解。 例1的求解过程： 最大化指派问题 例2.某卫生防疫站准备选