五章整数规划.pptVIP

第五章 整数规划 一、整数规划数学模型及解的特点 二、解纯整数规划的割平面法 三、分支定界法 四、0－1型整数规划 五、指派问题 一、数学模型及解的特点 一、数学模型及解的特点 一、数学模型及解的特点 四、0—1规划 四、0—1规划 四、0—1规划 2.固定费用问题： 四、0—1规划 设Xj是第j种产品的产量。Yj是0－1变量，表示是（Yj=1）否（Yj=0）生产第j种产品。 四、0—1规划 五、指派问题 五、指派问题 五、指派问题 五、指派问题 五、指派问题 是一类特殊的运输问题和0－1整数规划问题。 匈牙利法： 库恩W.W.Kuhn 利用匈牙利数学家康尼格关于独立零元素的定理 1955 理论依据： 系数矩阵中独立0元素的最多个数=能覆盖所有0元素的最少直线数。 最优解性质：从系数矩阵cij的一行（或列）减去该行（或列）的最小元素，得到的新矩阵bij 。它们的最优解相同。 五、指派问题 五、指派问题 五、指派问题 五、指派问题 五、指派问题 五、指派问题 五、指派问题 解：1、化系数矩阵 五、指派问题 2、确定独立零元素 五、指派问题 3、变换矩阵 五、指派问题 计算步骤： 1 . 化系数矩阵。 2 4 1 0 丁 4 7 5 0 丙 11 3 0 6 乙 2 11 13 0 甲 R G J E 0 1 1 0 丁 2 5 5 0 丙 9 0 0 6 乙 0 8 13 0 甲 R G J E 9 11 8 7 丁 13 16 14 9 丙 15 7 4 10 乙 4 13 15 2 甲 R G J E 2 . 进行试指派，以寻求最优解。（确定独立零元素） 在只有一个零元素的行（或列）的零元素加圈。把位于同列（或同行）的其它零元素划去。如此反复，直至所有零元素都被圈去或划去为止。如有多个零元素，任选。如有n个独立零元素，得解。否则，转3。 0 1 1 0 丁 2 5 5 0 丙 9 0 0 6 乙 0 8 13 0 甲 R G J E 3. 作最少直线覆盖所有0元素。 方法： 对没有划圈零元素的行打“√”； 在已打“√”的行中，对划去零元素所在列打“√”； 在已打“√”的列中，对划圈零元素所在行打“√”； 重复(2)相(3)，直到再也不能找到打“√”的行或列为止； 对没有打“√”的行画一横线，对打“√”的列画一垂线，这样就得到了覆盖所有零元素的最少直线数目的直线集合。 4.进行矩阵变换增加0元素。找出没被直线覆盖的最小元素，打“√”的行减去该元素，打“√”的列加上该元素，若得到n个独立0元素，得解。否则转入第三步。 0 1 1 0 丁 2 5 5 0 丙 9 0 0 6 乙 0 8 13 0 甲 R G J E √ √ √ √ √ 0 0 0 0 丁 2 4 4 0 丙 10 0 0 7 乙 0 7 12 0 甲 R G J E √ √ √ √ √ 0 0 0 0 丁 2 4 4 0 丙 10 0 0 7 乙 0 7 12 0 甲 R G J E 例 ：拟派甲.乙.丙.丁四人去完成四项工作。已知甲.乙.丙.丁完成各项工作的时间如表： 10 11 8 5 丁 6 2 2 11 丙 3 8 6 1 乙 3 3 3 5 甲 D C B A ？如何指派，使总的消耗时间最少。 10 11 8 5 6 2 2 11 3 8 6 1 3 3 3 5 5 6 3 0 4 0 0 9 2 7 5 0 0 0 0 5 三、 分枝定界法 三、 分枝定界法 三、 分枝定界法 分支定界法的优点： (1)、任何模型均可用； (2)、思路简单、灵活； (3)、速度快； (4)、适合上机。 三、 分枝定界法 一、0－1变量及其应用 0－1变量常被用来表示系统是否处于某个特定状态，或者决策时是否取某个特定方案。 当问题有多项要素，每项要素皆有两种选择时，可用一组0－1变量来描述。 在应用中，有时会遇到变量可以取多个整数值的问题。如果用0－1变量来表示，也可以用一组0－1变量来取代。 如x取0－9之间的任意整数时。 x=20x0+ 21x1 + 22x2 + 23x3 ? 9 1. 含有相互排斥的约束条件的问题： （1）两个约束中，只有一个起作用。 例：a11x1+a12x2B1 a21x1+a22x2B2 a11x1+a12x2B1+M1Y1 a21x1+a22x2B2+M2Y2 Y1+Y2=1 实际问题