第五章+整数规划.ppt

整数规划 整数规划 整数规划的数学模型及解的特点解纯整数规划的割平面法 分支定界法0 1型整数规划 指派问题 例1某厂拟用集装箱托运甲乙两种货物 每箱的体积 重量 可获利润以及托运所受限制见下表 问每集装箱中两种货物各装多少箱 可使所获利润最大 1整数规划的数学模型 一 问题的提出 解设分别为甲 乙两种货物的托运箱数 则这是一个纯整数规划问题 其数学模型为 在许多线性规划问题中 要求最优解必须取整数 例如所求的解是机器的台数 人数车辆船只数等 如果所得的解中决策变量为分数或小数则不符合实际问题的要求 二 整数规划问题的数学模型 对于一个规划问题 如果要求全部决策变量都取整数 称为纯 或全 整数规划 如果仅要求部分决策变量取整数 称为混合整数规划问题 有的问题要求决策变量仅取0或l两个值 称为0 l规划问题 整数规划简称为IP问题 这里主要讨论的是整数线性规划问题 简称为ILP问题 若不考虑整数条件 由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题 slackproblem 整数线性规划数学模型的一般形式 三 整数规划问题解的特点 对于整数线性规划问题 为了得到整数解 初看起来 似乎只要先不管整数要求 而求线性规划的解 然后将求得的非整数最优解 舍零取整 就可以了 但实际上 这个想法却常常行不通 有时 舍零取整 后的整数解根本就不是可行解 有的虽然为可行解 却不是最优解 例1某厂拟用集装箱托运甲乙两种货物 每箱的体积 重量 可获利润以及托运所受限制见下表 问每集装箱中两种货物各装多少箱 可使所获利润最大 解设分别为甲 乙两种货物的托运箱数 则这是一个纯整数规划问题 其数学模型为 1 若暂且不考虑取整数这一条件 则 1 就变为下列线性规划 2 我们将式 2 称为 1 的松弛问题 解 2 得到最优解 3 但它不满足 1 的整数要求 因此它不是 1 的最优解 若把解 3 舍零取整 如取X1 5 0 T 但它不是式 1 的可行解 因为它不满足 1 中的约束条件 若取X2 4 0 T X2是 1 的可行解 但它却不是 1 的最优解 因为当X2 4 0 T时 Z2 80 但当X3 4 1 T时 Z3 90 Z2 即伴随规划的最优解通过 舍零取整 得到的X1 X2都不是 1 的最优解 因此通过松弛问题最优解的 舍零取整 的办法 一般得不到原整数规划问题的最优解 对上面的问题 我们从几何的角度来观察 若松弛问题 2 的可行域K是有界的 则原整数规划 1 的可行域K0应是K中有限个格点 整数点 的集合 见图1 图中 为整数点 格点 图1中四边形OABC是松弛问题 2 的可行域 它的最优解为C点 4 8 0 而 1 的可行域为k0 0 0 0 1 0 2 1 0 1 l 1 2 2 0 2 1 3 0 3 1 4 0 4 l 将C点 舍零取整 后得到的X1 5 0 0 T不在K0中 而X2 4 0 T在K0中 但不是 1 的最优解 最优解在B点左侧 4 1 当然 我们也会想到能否用 穷举法 来求解整数规划 如 1 问题 将K0中所有整数点的目标函数值都计算出来 然后逐一比较找出最优解 这种方法对变量所能取的整数值个数较少时 勉强可以应用 如本例可取0 1 2 3 4共5个数值 而只能取0 1 2共三个数值 因此其组合最多为15个 其中有不可行的点 但对大型问题 这种组合数的个数可能大得惊人 如在指派问题中 有n项任务指派n个人去完成 不同的指派方案共有n 种 当n 20时 这个数超过2 1018 如果用穷举法每一个方案都计算一遍 就是用每秒百万次的计算机 也要几万年 显然 穷举法 并不是一种普遍有效的方法 因此研究求解整数规划的一般方法是有实际意义的 整数规划解的特点 整数线性规划及其松弛问题 从解的特点上来说 二者之间既有密切的联系 又有本质的区别 松弛问题作为一个线性规划问题 其可行解的集合是一个凸集 任意两个可行解的凸组合仍为可行解 整数规划问题的可行解集合是它的松弛问题可行解集合的一个子集 任意两个可行解凸组合不一定满足整数约束条件 因而不一定仍为可行解 由于整数规划问题的可行解是其松弛问题的可行解的子集 所以 其松弛问题的最优解目标函数值是整数规划问题目标函数值的上界 在一般情况下 松弛问题的最优解不会刚好满足变量的整数约束条件 因而不是整数规划的可行解 自然也不是整数规划的最优解 但松弛问题的最优解恰好满足变量的整数约束条件 那么它必然同时是整数规划问题和其松弛问题的最优解 目前 常用的求解整数规划的方法有 分支定界法和割平面法 对于特别的0 1规划问题采用隐枚举法和匈牙利法 自20世纪60年代以来 已发展了一些常用的解整数规划的算法 如各种类型的割平面法 分枝定界法 解0 1规划的隐枚举法 分解方法 群论方法 动态规划方法等等 近十年来有人发展了一些近似算法及用计算机模拟法 也取得了较好的效果 背景 2解纯整数规划的割平面法 考虑纯整数规划问题 纯整数规划的松弛问题是一个线性规划问题 可用单纯形法求解 在松弛问题的最优单纯形表中 记Q为m个基变量的下标集合 K为n m个非基变量的下标集合 则m个约束方程可示为 5 4式 而对应的最优解X x1 x2 xn 其中 若各皆为整数 则X 满足整数约束 因而就是纯整数规划的最优解 若不全为整数 则X 不满足整数约束 因而就不是纯整数规划的可行解 自然也不是该整数规划的最优解 割平面法的基本思想 用割平面法 cuttingplaneapproach 解整数规划时 若其松弛问题的最优解不满足整数约束 则从X 的非整分量中选取一个 用以构造一个线性约束条件 将其加入原松弛问题中 形成一个新的线性规划 然后求解之 若新的最优解满足整数要求 则它就是整数规划的最优解 否则重复上述步骤 直到获得整数最优解为止 为最终获得整数最优解 每次增加的线性约束条件应当具备两个基本性质 已获得的不符合整数要求的松弛问题最优解不满足该线性约束条件 从而不可能在以后的解中再出现 凡整数可行解均满足该线性约束条件 因而整数最优解始终被保留在每次形成的松弛问题 线性规划 可行域中 我们应该怎样构造新的约束条件 为此 若不是整数 在 5 4 中对应的约束方程为 其中按假设不是整数 可能是整数 也可能不是整数 5 6式 5 7式 5 8式 分解和成两部分 一部分是不超过该数的最大整数 另一部分是余下的小数即 将 5 7 和 5 8 式代入 5 6 式 移项以后得 5 9式 对5 9式分别讨论当前解 非整数解 和可行域中整数解的情况 对于当前解5 9式右端有 对于整数解5 9式左端表明为整数 又因为本身不能 1 故 由此我们以 5 10式 作为标尺来 将当前不满足整数约束的最优解去掉 而完全保留了原整数规划问题的可行解 综上所述 线性约束条件 5 10 式具备上述的两个性质 将其与原整数规划的松弛问题合并 构成一个新的线性规划 记R为原松弛问题可行域 R 为新的线性规划可行域 从几何意义上看 5 10 式实际上对R做了一次 切割 在留下的R 中 保留了整数规划的所有可行解 但不符合整数要求的X 被 切割 掉了 随着 切割 过程的不断继续 整数规划最优解最终有机会成为某个线性规划可行域的顶点 作为该线性规划的最优解而被解得 割平面法在1958年由高莫瑞 R E Gomory 首先提出 故又称Gomory割平面法 在割平面法中 每次增加得用于 切割 的线性约束称为割平面约束或Gomory约束 构造割平面约束的方法很多 但 5 10 式是最常用的一种 它可以从相应线性规划的最终单纯形表中直接产生 实际解题时 经验表明若从最终单纯行表中选择具有最大分数部分的非整分量所在行构造割平面约束 往往可以提高 切割 效果 减少 切割 次数 例 用割平面法求解整数规划问题 解 增加松弛变量x3和x4 得到 LP 的初始单纯形表和最优单纯形表 割平面约束 加入割平面约束后得到的新的线性规划问题为 我们可用使用单纯行法从头开始解这个线性规划问题 但更简便的方法是使用对偶单纯形法 将生成的割平面条件加入松弛变量 然后加到表中 将x3 6 3x1 2x2 x4 3x1 2x2 带入中 得到等价的割平面条件 x2 1见下图 此时 X1 2 3 1 Z 1 仍不是整数解 继续以x1为源行生成割平面 其条件为 将生成的割平面条件加入松弛变量 然后加到表中 至此得到最优表 其最优解为X 1 1 Z 1 这也是原问题的最优解 等价的约束割平面条件为x1 x2 3分枝定界法 在20世纪60年代初LandDoig和Dakin等人提出了分枝定界法 由于该方法灵活且便于用计算机求解 所以目前已成为解整数规划的重要方法之一 适用范围 分枝定界法既可用来解纯整数规划 也可用来解混合整数规划 分枝定界法由来 混合整数规划问题一般有无限多个可行解 即使是纯整数规划问题 随着问题规模的扩大 其可行解的数目也将急剧增加 因此通过枚举全部可行解 并从中筛选出最优解的算法无实际应用价值 分枝定界法 branchandbound 是一种隐枚举或部分枚举法 是在枚举法基础上的改进 分枝定界法的关键是分枝和定界 分枝定界法的基本思想 分枝和定界的思想 若整数规划的松弛问题的最优解不符合整数要求 假设不符合整数要求 是不超过的最大整数 则构造两个约束条件 分别将其并入上述松弛问题中 从而形成两个分枝 即两个后续问题 这就是所谓分枝 两个后续问题的可行域中包含原整数规划问题的所有可行解 而在原松弛问题可行域中 满足的一部分区域在以后的求解过程中被遗弃了 让而它不包含整数规划的任何可行解 根据需要 各后续问题可用类似地产生自己的分枝 即自己的后续问题 分枝 为整数规划最优解的出现创造了条件 什么是定界 所谓 定界 是在分枝过程中 若某个后续问题的最优解恰巧获得整数规划问题的一个可行解 即其解满足整数约束 那么 它的目标函数值就是一个 界限 可作为衡量处理其他分枝的一个依据 因为整数规划问题的可行解集是其松弛问题的可行解集的一个子集 所以其松弛问题的最优解目标函数值是原整数规划问题的上界 所以 对于那些相应松弛问题最优解的目标函数值比上述 界限 值差的后续问题 就可以剔除而不再考虑 当然 如果在以后的分枝过程中出现了更好的 界限 则以它来取代原来的界限 这样可以提高定界的效果 定界 则可用提高搜索的效率 分枝 为整数规划最优解的出现创造了条件 而 定界 则可用提高搜索的效率 下面 通过例子来阐明分枝定界法的基本思想和一般步骤 例求解整数规划问题 解 去掉整数要求 得其相应得线性规划 在分枝定界法中 将此记为B 称其为原整数规划A的松弛问题 用任一种方法解问题B得最优解和最优值为 x1 4 55 x2 2 17 Z 37 97B的可行解集记为R0 如图所示 A 4 55 2 17 上面B的最优解不满足整数要求 即不是整数规划的最优解 为寻求原整数规划的最优解 我们把B划分为两个子问题 分枝 任选一个不满足整数约束的变量 这里我们取x1构造两个约束条件 在B中分别增加上述约束条件 得到B的两个子问题 问题 问题 x1 4 x2 2 33 Z 36 33 x1 5 x2 1 5 Z 35 5 此时 B的可行解被分成了三个部分 即问题 的可行解R1 问题 的可行解R2 以及不含整数可行解的4 x1 5的部分 LP1x1 4 x2 2 33Z 1 36 33 LPx1 4 55 x2 2 17Z 0 37 97 LP2x1 5 x2 1 5Z 2 35 5 x1 4 x1 5 整个求解过程 问题B 问题 问题 由于问题 和问题 的最优解仍不满足整数要求 则把 和 继续进行类似的划分 由于 的最优值较大 则其包含原整数规划最优解的可能形更大些 因此先分解 在 中分别增加约束条件得到 的两个子问题 和 问题 在 中分别增加两个约束 得到 的两个子问题 和 问题 问题 x1 4 x2 2 Z 34 x1 1 71 x2 3 Z 29 57 此时 问题1的可行域被分成三部分 即 的可行集R3 的可行解集R4 以及不含整数可行解的2 x2 3部分 LP1x1 4 x2 2 33Z 1 36 33 LPx1 4 55 x2 2 17Z 0 37 97 LP2x1 5 x2 1 5Z 2 35 5 x1 4 x1 5 整个求解过程 问题B 问题 问题 x2 2 x2 3 LP3x1 4 x2 2Z 3 34 LP4x1 1 71 x2 3Z 4 29 57 问题 问题 由于 的最优解已满足整数要求 它的最优值34可以作为原整数规划问题的界限 下界 作为衡量处理其他分枝的一个依据 LP1x1 4 x2 2 33Z 1 36 33 LPx1 4 55 x2 2 17Z 0 37 97 LP2x1 5 x2 1 5Z 2 35 5 x1 4 x1 5 整个求解过程 问题B 问题 问题 x2 2 x2 3 LP3x1 4 x2 2Z 3 34 LP4x1 1 71 x2 3Z 4 29 57 问题 问题 而 的最优解仍不满足整数要求 但因为它的最优值29 57小于已经得到的原整数规划问题的整数可行解的目标函数值34 即小于下界 则可以肯定 的可行解集中不含有原整数规划的最优解 则 可舍去 称为剪枝 将 舍去后 还不能说问题 的最优解就是原整数规划的最优解 因为问题 的最优解35 5 34 即 的可行解集中还有可能含有原整数规划的最优解 比 的最优解目标函数值大的整数解 因此需要考察问题 分别增加约束条件得到问题 的两个子问题 和 问题 问题 问题 引入约束 x1 5 33 x2 1 Z 33 67 无可行解 问题 的可行域R5 问题 无可行解 此时 问题 的可行域被分成两部分部分 即 的可行集R5 和不含整数可行解的1 x2 2部分 问题 无可行解集 LP1x1 4 x2 2 33Z 1 36 33 LPx1 4 55 x2 2 17Z 0 37 97 LP2x1 5 x2 1 5Z 2 35 5 x1 4 x1 5 问题B 问题 问题 x2 2 x1 3 LP3x1 4 x2 2Z 3 34 LP4x1 1 71 x2 3Z 4 29 57 x2 1 x2 2 LP5x1 5 33 x2 1Z 5 33 67 LP6无可行解 对于问题 由于其最优值小于已得到的整数规划的整数可行解目标函数值 故 可舍去 剪枝 对于问题 无可行解 故也不再考虑 舍去 最后可得原整数规划的最优解为 x1 4 x2 2 Z 34即下图中的D点 D 4 2 分枝定界法的步骤 分枝定界法解整数规划的一般步骤如下 1 不考虑整数约束 解相应LP问题 2 检查是否符合整数要求 是 则得最优解 完毕 否则 转下步 3 任取一个非整数变量 构造两个新的约束条件 分别加入到上一个LP问题 形成两个新的分枝问题 4 不考虑整数要求 解分枝问题 若整数解的Z值 所有分枝末梢的Z值 则得最优解 否则 取Z值最大的非整数解 继续分解 Goto3 x1 4 x1 5 问题 问题 x2 2 x1 3 x2 1 x2 2 练习 例 用分枝定界法求解整数规划问题 可用图解法求解 树形图如下 LP1x1 7 2 x2 2Z 1 29 2 14 5 LPx1 13 4 x2 5 2Z 0 59 4 14 75 LP2x1 5 2 x2 3Z 2 27 2 13 5 LP3x1 3 x2 2Z 3 13 LP4x1 4 x2 1Z 4 14 x2 2 x2 3 x1 3 x1 4 30 1型整数规划 一 0 1变量及其应用 若变量只能取0或1 则称其为0 1变量 0 1变量作为逻辑变量 logicalvariable 常被用来表示系统是否处于某个特定状态 或者决策时是否取某个特定方案 例如 当决策取方案P时 当决策不取方案P时 即取时 若Ej选择Aj 若Ej选择 J 1 2 n 那么 向量 x1 x2 xn 就描述了问题的特定状态或方案即 当问题含有多项要素 而每项要素皆有两种选择时 可用一组0 1变量来描述 一般地 设问题有有限项要素E1 E2 En 其中每项Ej有两种选择Aj和 则可令 投资场所选择问题某城市拟在其东 西 南三个区域设立邮局 各地区都由几个具体的地点可供选择 要求不超过总投资100万元的条件下 建立盈利最大化0 1规划 分析 令xj j1 2 7 为0 1变量 二 0 1整数规划举例 其数学模型为 在应用中 有时会遇到变量可以取多个整数值的问题 这时 利用0 1变量是二进值变量 binaryvariable 的性质 可以用一组0 1变量来取代该变量 例如 变量x可取0 9之间的任意整数时 可令 其中x0 x1 x2 x3皆为0 1变量 0 1变量不仅广泛应用于科学技术问题 在经济管理问题中也有十分重要的应用 1互斥问题2固定费用问题3工件排序问题 含有相互排斥的约束条件的问题假设工序B的每周工时约束条件为现在假设工序B还有一种新的加工方式 相应的每周工时约束变成 如果工序B只能从两种加工方式中选择一种 那么 1 式和 2 式就成为两个相互排斥的约束条件 为了统一在一个问题中 就需要引入0 1变量 工序B采用原加工方式 工序B不采用原加工方式 工序B采用新加工方式 工序B不采用新加工方式 于是 通过引入0 1变量 可以将相互排斥的约束条件 1 和 2 统一起来 其中M1和M2都是充分大的数 由于 5 式决定了y1和y2中必定有一个是1 另一个是0 互斥条件 若y1 1 而y2 0 即采用新的加工方式 此时由于M1是一个充分大的数 则 3 式无效 反之 若y1 0 而y2 1 即采用原加工方式 此时由于M2是一个充分大的数 则 4 式无效 一般地 若需要从p个约束条件 中恰好选择q个约束条件 则可用引入p个0 1向量 若选择第i个约束条件 若不选择第i个约束条件 那么 约束条件组 就可用达到这个目的 因为上述约束条件组保证了在p个0 1变量中有p q个为1 q个为0 凡取0值的yi对应的约束条件即为原约束条件 而取1的yi对应的约束条件无效 固定费用问题 有三种资源被用于生产三种产品 资源量 产品单件费用及售价 资源单耗量及组织三种产品生产的固定费用见下表 要求定制一个生产计划 使总收益最大 建模碰到的困难主要是事先不能确切知道某种产品是否生产 因而不能确定相应的固定费用是否发生 下面借助0 1变量解决这个困难设xj是第j种产品的产量 j 1 2 3 再设 生产第j种产品 即xj 0 不生产第j种产品 即xj 0 则问题的整数规划数学模型是 如果生产第j种产品 则其产量xj 0 此时由约束条件xj Mjyj 知yj 1 因此相应的固定费用在目标函数中将被考虑 如果不生产第j种产品 则其产量xj 0 此时由约束条件xj Mjyj可知 yj可以是0也可以是1 但yj 1不利于目标函数的最大化 因而在问题的最优解中必然是yj 0 从而相应的固定费用将不再被考虑 工件排序问题 用4台机床加工3件产品 各产品的机床加工顺序 以及产品i在机床j上的加工工时aij见下表 由于某种原因 产品2的加工总时间不得超过d 现要求确定各件产品在机床上的加工方案 使在最短的时间内加工完全部产品 解 设xij表示产品i在机床j上开始加工的时间 i 1 2 3 j 1 2 3 4 下面将逐步列出问题的整数规划模型1 同一件产品在不同机床上的加工顺序约束对于同一件产品 在下一台机床上加工的开始时间不得早于在上一台机床上加工的约束时间 故应有 产品3 2 每一台机床对不同产品的加工顺序约束一台机床在工作中 如已开始的加工还没有结束 则不能开始另一件产品的加工 对于机床1 有两种加工顺序 或先加工产品1 后加工产品2 或反之 对于其它3台机床 情况也类似 为了容纳两种相互排斥的约束条件 对于每台机床 分别引入0 1变量 则每台机床上的加工产品的顺序可用下列四组约束条件来保证 各yj的意义是明显的 如当y1 0时 表示机床1先加工产品1 后加工产品2 当y1 1时 表示机床1先加工产品2 后加工产品1 3 产品2的加工时间约束产品2的开始加工时间是x21 结束加工时间是x24 a24 故应有 4 目标函数的建立设全部产品加工完毕的结束时间为W 由于三件产品的加工结束时间分别为x14 a14 x24 a24 x33 a33 故全部产品的实际加工结束时间为 转化为线性表达式 综上所述 例题的整数规划模型为 0 1型整数规划是一种特殊的整数规划 若含有n个变量 则可能产生2n个可能的变量组合 当n较大时 采用完全枚举法解题几乎是不可能的 已有的求解0 1型整数规划的方法一般都属于隐枚举法 三 0 1型整数规划的解法 在2n个可能的变量组合中 往往只有一部分是可行解 只要发现某个变量组合不满足其中一个约束条件时 就不必再去检验其他约束条件 对于可行解 其目标函数值也有优劣之分 若已发现一个可行解 则根据它的目标函数值可以产生一个过滤条件 对于目标函数值比它差的变量组合就不必再去检验它的可行性 在以后的求解过程中 每当发现比原来更好的可行解 则以此替换原来的过滤条件 上述这些做法 都可用减少运算次数 使最优解能较快地被发现 例求解0 1整数规划 解求解过程可以列表表示 a b c d 接上表 所以 最优解 x1 x2 x3 T 1 0 1 T maxZ 8 由于采用上述算法 实际只作了20次运算 例求解0 1整数规划 解 采用上例那样的算法 解此例共需作36次运算 为了进一步减少运算量 常按目标函数中各变量系数的大小顺序重新排列各变量 以便最优解有可能较早出现 对于最大化问题 可按由小到大的顺序排列 对于最小化问题 则相反 本例可写成下列形式 采取这样的形式用上法解此例 只需作30次运算 一般问题的规模越大 这样做的好处就越明显 篮球队需要选择5名队员组成出场阵容参加比赛 8名队员的身高及擅长位置见下表 出场阵容应满足以下条件 只能有一名中锋上场至少有一名后卫如1号和4号均上场 则6号不上场2号和8号至少有一个不出场 问 应当选择哪5名队员上场 才能使出场队员平均身高最高 试建立数学模型 有五项设计任务可供选择 各项设计任务的预期完成时间分别为3 8 5 4 10 周 设计报酬分别为7 17 11 9 21 万元 设计任务只能一项一项地进行 总的期限是20周 选择任务时必须满足下面要求 1至少完成3项设计任务 2若选择任务1 必须同时选择任务2 3任务3和任务4不能同时选择 应当选择那些设计任务 才能使总的设计报酬最大 试建立数学模型 整数规划 整数规划的数学模型及解的特点解纯整数规划的割平面法 分支定界法0 1型整数规划 指派问题 5指派问题 指派问题是整数规划的一类重要问题 也是在实际生活中经常遇到的一种问题 由n项不同的工作或任务 需要n个人去完成 每人只能完成一项工作 由于每人的知识 能力 经验等不同 故各人完成不同任务所需的时间 或其它资源 不同 问应只排哪个人完成何项工作所消耗的总资源最少 一 指派问题的数学模型 引进0 1变量 表示按排第i个人完成第j项工作 表示不安排第i个人完成第j项工作 则决策变量矩阵可表示为 用表示第i个人完成第j项工作所需的资源数 称之为效率系数 或价值系数 表示为 效率矩阵 Coefficientmatrix 则指派问题的数学模型为 或1 注 指派问题是一种特殊的LP问题 是一种特殊的运输问题 下用目前认为最简洁的方法 匈牙利法求解 例1 某商业公司计划开办五家新商店 为了尽早建成营业 商业公司决定由5家建筑公司分别承建 已知建筑公司对新商店的建造报价 万元 为 见表5 9 商业公司应当对5家建筑公司怎样分配建筑任务 才能使总的建筑费用最少 这是一个标准的指派问题 若设0 1变量 当承建时 当不承建时 则问题的数学模型为 或1 若单说让谁建 不让谁建 4 6 7 6 7 从而导出匈牙利解法的思想 匈牙利法是1955年由库恩 W W Kuhn 根据匈牙利数学家狄 考尼格 d konig 关于矩阵中独立零元素的定理发明的 匈牙利法的基本原理 定理1将效率矩阵的某一行 或某一列 的各个元素都减去同一个常数t t可正可负 得到新的矩阵 则以新矩阵为效率矩阵的指派问题与原指派问题的最优解相同 但其最优值比原最优值减少t 解 设效率矩阵C为 二 匈牙利解法 记新指派问题的目标函数为 则有 注意到 所以原式 因此有 而新问题的约束方程同原指派问题 因此其最优解比相同 而最优解差一个常数 推论若将指派问题的效率矩阵每一行及每一列分别减去各行各列的最小元素 则得到的新的指派问题与原指派问题有相同的最优解 证明 结论是显然的 只要反复运用定理1便可得证 注 当将效率矩阵的每一行都减去各行的最小元素 将所得的矩阵的每一列在减去当前列中最小元素 则最后得到新效率矩阵中必然出现一些零元素 设 0 从第i行看 它表示第i人去干第j项工作效率 相对 最好 而从第j列来看 它表示第j项工作让第i人来干效率 相对 最高 问题是 能否找到位于不同行 不同列的n个0元素 定义在效率矩阵C中 有一组处于不同行 不同列的零元素 称为独立零元素组 此时其中每个元素称为独立零元素 例已知 则 是一个独立零元素组 分别称为独立零元素 也是一个独立零元素组 不是一个独立零元素组 根据以上对效率矩阵中零元素的分析 对效率矩阵C中出现的的独立零元素组中零元素所处的位置 在决策变量矩阵中令相应的 1 其余的 0 就可找到指派问题的一个最优解 就上例中 就是一个最优解 同理 也是一个最优解 但是在有的问题中发现效率矩阵C中独立零元素的个数不够n个 这样就无法求出最优指派方案 需作进一步的分析 首先给出下述定理 已知效率矩阵 怎么办 定理效率矩阵C中独立零元素的最多个数等于能覆盖所有零元素的最少直线数 本定理由匈牙利数学家狄 考尼格证明的 证明的内容已超出所需学的范围 下面通过例子说明上述定理的内容 例已知矩阵 至于如何找覆盖零元素的最少直线 通过例子来说明 例1现有一个4 4的指派问题 其效率矩阵为 求解该指派问题 步骤1 变换系数矩阵 使得每行及每列至少产生一个零元素 2 4 9 7 4 2 步骤2 用圈0法确定中的独立0元素 若独立零元素个素有n个 则已得最优解 若独立零元素的个数 n 则转入步骤3 其余全为0 在只有一个0元素的行 或列 加圈 表示此人只能做该事 或此事只能由该人来做 每圈一个 0 同时把位于同列 或同行 的其他零元素划去 表示此时已不能再由他人来做 或此人已不能做其它事 如此反复 直到矩阵中所有零元素都被圈去或划去为至 在遇到所有行和列中 零元素都不止一个时 可任选其中一个加圈 然后划去同行 同列其他未被标记的零元素 例 步骤3 若矩阵已不存在未被标记的零元素 但圈零的个数m n 作最少直线覆盖当前零元素 已知例1 工程承包 中的系数矩阵变为 4 7 6 6 6 1 3 变换系数矩阵 确定独立零元素 作最少直线覆盖当前所有零元素 由于独立零元素个数4 5 对没有圈0的行打 在已打 的行中 对零元素所在的列打 在已打 的列中 对圈0元素所在的行打 重复 和 直到再也找不到可以打 的行或列为止 对没有打 的行画一横线 对已打 的列画一纵线 即得覆盖当前0元素的最少直线数目的集合 继续变换系数矩阵 以增加0元素 在未被直线覆盖的元素中找出一个最小的元素 对未被直 线覆盖的元素所在的行 或列 中各元素都减去这一元素 这样 在未被直线覆盖的元素中势必会出现0元素 但同时却又使已覆盖的元素中出现负元素 为了消除负元素 只要对它们所在的列 或行 中各元素都加上这一最小元素 返回 1 1 1 中已有5个独立0元素 故可确定指派问题的最优方案 其余全为0 中已有5个独立0元素 故可确定指派问题的最优方案 其余全为0 也就是说 最优指派方案是 让承建 承建 承建 承建 这样安排能使总的建