整数规划问题PPT课件

1、第四章第四章 整数规划与分配问题整数规划与分配问题数学模型割平面法分枝定界法0-1整数规划分配问题整数规划整数规划integer linear programminginteger linear programming简述简述lp虽然用途广泛，但经常地，客观上要求 l.p.最优解中不能含有非整数值（如股票的购买之解答），整数规划就是专门用来求解这类问题的有效工具重点掌握重点掌握：0-1 规划灵活应用、分枝定界法。提出问题提出问题 某厂生产a1，a2两种品牌电视，用b1，b2两种原料，具体数据如下，求如何安排生产使利润最大a1a2供应量b130（g/台） 2080gb27040150g利润200

2、（元/g）100整数规划整数规划数学模型数学模型njxxmibxatsxczjjnjijijnjjj, 2 , 10, 2 , 1,),(. .max(min)11部分或全部为整数若所有若所有 xj 的解为整数，称为纯整数规划的解为整数，称为纯整数规划pure integer linear programming若部分若部分 xj 的解为整数，称为混合整数规划的解为整数，称为混合整数规划mixed integer linear programming若若xj 只取只取0或或1，成为，成为0-1整数规划整数规划zero-one integer linear programming松弛问题松弛问题

3、整数规划整数规划整数规划的最优解不会优于其松弛问题的最优解整数规划的最优解不会优于其松弛问题的最优解注 释 最优解不一定在顶点上达到最优解不一定在顶点上达到 最优解不一定是松弛问题最优解的邻近整最优解不一定是松弛问题最优解的邻近整数解数解 整数可行解远多于顶点，枚举法不可取整数可行解远多于顶点，枚举法不可取整数规划问题的求解方法整数规划问题的求解方法分枝定界法分枝定界法branch and bound method 分枝定界法是一种隐枚举方法（分枝定界法是一种隐枚举方法（implicit enumeration）或部分或部分枚举方法，是枚举方法基础上的改进，几乎所有的计算机计算都用枚举方法，是

4、枚举方法基础上的改进，几乎所有的计算机计算都用此算法。其关键是分支和定界。此算法。其关键是分支和定界。例例 max z = x1 + x2 14x1 + 9x2 51 - 6x1 + 3x2 1 x1 ， x2 0 x1 ， x2 取整数取整数s.t.6分支定界法分支定界法思路与解题步骤思路与解题步骤 只解松弛问题只解松弛问题1、在全部可行域上解松弛问题、在全部可行域上解松弛问题 若松弛问题最优解为整数解，则其也是整数规划的最若松弛问题最优解为整数解，则其也是整数规划的最优解优解2、分枝过程、分枝过程 若松弛问题最优解中某个若松弛问题最优解中某个 xk=bk 不是整数，令不是整数，令 bk 为

5、为 bk 的整数部分的整数部分 构造两个新的约束条件构造两个新的约束条件 xk bk 和和 xk bk +1，分别分别加于原松弛问题，形成两个新的整数规划加于原松弛问题，形成两个新的整数规划3、求解分枝的松弛问题、求解分枝的松弛问题 定界过程定界过程 设两个分枝的松弛问题分别为问题设两个分枝的松弛问题分别为问题 1 和问题和问题 2 ，它们，它们的最优解有如下情况的最优解有如下情况 整数规划整数规划分支问题解可能出现的情况分支问题解可能出现的情况情况情况 2, 4, 5 找到最优解找到最优解情况情况 3 在缩减的域上继续分枝定界法在缩减的域上继续分枝定界法情况情况 6 问题问题 1 的整数解作

6、为的整数解作为界界被保留，用于以后与问题被保留，用于以后与问题 2 的后续分枝所得到的解进行比较，结论如情况的后续分枝所得到的解进行比较，结论如情况 4或或5整数规划整数规划分支定界法图解整数规划分支定界法图解整数规划 松弛问题松弛问题 max z = x1 + x2 14x1 + 9x2 51 - 6x1 + 3x2 1 x1 ， x2 0该整数规划松弛问题的解为：该整数规划松弛问题的解为：（x1 ，x2 ）=（3/2 ,10/3）z1 = 29/614x1 + 9x2 51- 6x1 + 3x2 151/141/39整数规划 integer programming（ip）分支定界法图解整数

7、规划分支定界法图解整数规划松弛问题松弛问题 max z = x1 + x2 14x1 + 9x2 51 - 6x1 + 3x2 1 x1 ， x2 0（3/2 ，10/3）z1 = 29/6b1 max z = x1 + x2 14x1 + 9x2 51 - 6x1 + 3x2 1 x1 2 x1 ， x2 0b2 max z = x1 + x2 14x1 + 9x2 51 - 6x1 + 3x2 1 x1 1 x1 ， x2 0b2：解解（1,7/3 ）z21 = 17/3b1：解解（2,23/9 ）z11 = 41/912b1b210整数规划 integer programming（ip）

8、整数规划问题的求解方法整数规划问题的求解方法分支定界法图解整数规划分支定界法图解整数规划（3/2 ,10/3）z1 = 29/6b1 max z = x1 + x2 14x1 + 9x2 51 - 6x1 + 3x2 1 x1 2 x1 ， x2 0b2：解解（1,7/3 ）z21 = 17/3b1：解解（2,23/9 ）z11 = 41/9b11 max z = x1 + x2 14x1 + 9x2 51 - 6x1 + 3x2 1 x1 2 x2 3 x1 ， x2 0b12 max z = x1 + x2 14x1 + 9x2 51 - 6x1 + 3x2 1 x1 2 x2 2 x1

9、， x2 0b12：解解（33/14,2 ）z12 = 61/141 2x=2x=311整数规划 integer programming（ip）整数规划问题的求解方法整数规划问题的求解方法分支定界法图解整数规划分支定界法图解整数规划（3/2 ，10/3）z1 = 29/6b2：解解（1,7/3 ）z21 = 17/3b12 max z = x1 + x2 14x1 + 9x2 51 - 6x1 + 3x2 1 x1 2 x2 2 x1 ， x2 0b12：解解（33/14,2 ）z12 = 61/14b121 max z = x1 + x2 14x1 + 9x2 51 - 6x1 + 3x2

10、1 x1 3 x2 2 x1 ， x2 0b122 max z = x1 + x2 14x1 + 9x2 51 - 6x1 + 3x2 1 x1 2 x2 2 x1 ， x2 0b121：解解（3，1 ）z121 = 4b122：解解（2，2 ）z122 = 4b1：解解（2，23/9 ）z11 = 41/9 1 2 312割平面法割平面法cutting plane approach割平面法求解整数规划问题时，若其松驰问题的最优解割平面法求解整数规划问题时，若其松驰问题的最优解 x* 不满足不满足整数要求时，则从整数要求时，则从 x* 的非整分量中选取一个，用以构造一个线性的非整分量中选取一个

11、，用以构造一个线性约束条件（约束条件（gomory 割平面），将其加入原松驰问题中，形成一个割平面），将其加入原松驰问题中，形成一个新的线性规划，然后求解之。其关键在于新增加的这个线性约束条新的线性规划，然后求解之。其关键在于新增加的这个线性约束条件将切割掉部分非整数解，至少将当前松驰问题的非整数最优解切件将切割掉部分非整数解，至少将当前松驰问题的非整数最优解切割掉了，而割掉了，而不会切割掉问题的任何整数解不会切割掉问题的任何整数解。13整数规划 integer programming（ip）整数规划问题的求解方法整数规划问题的求解方法割平面法割平面法cutting plane approac

12、h 构造切割方程的步骤：构造切割方程的步骤：1、令、令 xi 是相应松驰问题的最优解中为非整数值的一个基变量，由是相应松驰问题的最优解中为非整数值的一个基变量，由单纯形表最终表得：单纯形表最终表得： xi + aik xk = bi （1 式）式）其中其中 i q （q 指基变量下标集）指基变量下标集） k k （k 指非基变量下标集）指非基变量下标集）14整数规划 integer programming（ip）整数规划问题的求解方法整数规划问题的求解方法割平面法割平面法cutting plane approach 构造切割方程的步骤：构造切割方程的步骤：2、将、将 bi 和和 aik 都分解

13、成整数部分都分解成整数部分 n （不超过不超过 b 的最大整数）与非的最大整数）与非负真分数部分负真分数部分 f 之和，即：之和，即： bi = ni + fi ， 其中其中 0 fi 1 （2 式）式） aik = nik + fik ，其中其中 0 fik 1例如：若例如：若 b = 2.35 ，则则 n = 2 ，f = 0.35； 若若 b = -1.45 ，则则 n = -2 ，f = 0.5515整数规划 integer programming（ip）割平面法割平面法cutting plane approach 构造切割方程的步骤：构造切割方程的步骤：2、将（、将（2 式）代入（式

14、）代入（1 式）得：式）得： xi + nik xk - ni = fi - fik xk （3 式）式）3、提出变量为整（当然含非负）的条件：、提出变量为整（当然含非负）的条件：由于（由于（3 式）中等式左边需整，而式）中等式左边需整，而 0 fi 1 ，故有故有 fi - fik xk 0 （4 式）式）此即为所需切割方程。此即为所需切割方程。16整数规划 integer programming（ip）割平面法割平面法cutting plane approach 构造切割方程的步骤：构造切割方程的步骤：（1）切割方程）切割方程 fi - fik xk 0 真正进行了切割，至少把非整数最优真

15、正进行了切割，至少把非整数最优解这一点切割掉了。解这一点切割掉了。证明：（反证法）假设松驰问题的最优解证明：（反证法）假设松驰问题的最优解 x* 未被切割掉，则由未被切割掉，则由 fi - fik x*k 0， 又因为又因为 x*k = 0，（，（因因 x*k 为非基变量）为非基变量） 有有 fi 0 ，这与这与 fi 0 矛盾。矛盾。（2）不会切割掉任何整数解，因为切割方程是由变量为整的条件）不会切割掉任何整数解，因为切割方程是由变量为整的条件提出的。提出的。17整数规划 integer programming（ip）割平面法割平面法cutting plane approach例例求解求解i

16、p max z = x1 + x2 - x1 + x2 1 3x1 + x2 4 x1 ，x2 0 x1 ，x2 整数整数lp max z = x1 + x2 - x1 + x2 1 3x1 + x2 4 x1 ，x2 0181、求解、求解 lp 得到非整数最优解：得到非整数最优解： x =（3/4，7/4，0，0），），max z = 5/2cj1100i 表表cbxbb 1 bx1x2x3x40x31- 11100x443101 j01100b 表表1x13/410-1/41/41x27/4013/41/4 j- 5/200- 1/2- 1/2求解步骤：求解步骤：19整数规划 intege

17、r programming（ip）求解步骤求解步骤：2、构造切割方程：、构造切割方程： 由由 b 表表中的第中的第 2 个方程个方程 x2 + 3/4 x3 + 1/4 x4 = 7/4 有有 b2 = 7/4 = 1 + 3/4 a23 = 3/4 = 0 + 3/4 ， a24 = 1/4 = 0 + 1/4 因此，切割方程为因此，切割方程为 3/4 3/4 x3 1/4 x4 0 增加松弛变量增加松弛变量 x5 ，并将如下方程的约束条件添加到并将如下方程的约束条件添加到 b 表中。表中。 - 3 x3 - 1 x4 + x5 = - 3 x5 020整数规划 integer progra

18、mming（ip）求解步骤：求解步骤：3、求解新的松弛问题、求解新的松弛问题 cj11000b 表表cbxbb 1 bx1x2x3x4x51x13/410-1/41/401x27/4013/41/400x5- 300- 3- 11 j- 5/200- 1/2- 1/20新新 b 表表1x111001/3- 1/121x2101001/40x310011/3- 1/3 j- 2000- 1/3- 1/6210-1整数规划问题整数规划问题0-1 变量及其应用变量及其应用 0-1变量作为逻辑变量（变量作为逻辑变量（logical variable），），常常被引用来表示常常被引用来表示系统是否处于某

19、个特定的状态，或者决策变量是否取某个特定的方系统是否处于某个特定的状态，或者决策变量是否取某个特定的方案。案。xj = 1 当决策取方案当决策取方案 p j 时时0 当决策不取方案当决策不取方案 pj 时时220-1整数规划整数规划一、项目选定一、项目选定(选址）问题选址）问题整数规划整数规划 在在经济全球化经济全球化的时代，许多公司为在全球的时代，许多公司为在全球范围内范围内最优地配置资源最优地配置资源（如获取廉价劳动（如获取廉价劳动力或原料等），要在不同地方建厂或仓库力或原料等），要在不同地方建厂或仓库及其他服务设施，这些都要进行项目或地及其他服务设施，这些都要进行项目或地址的选择。在选址

20、之前，许多侯选地点要址的选择。在选址之前，许多侯选地点要进行分析和比较，而每个决策都涉及到一进行分析和比较，而每个决策都涉及到一个个选选还是还是不选不选的问题。的问题。案例一案例一 某销售公司打算通过在武汉或长春设立分公司（也许两个城某销售公司打算通过在武汉或长春设立分公司（也许两个城市都设）增加市场份额，管理层同时也计划在新设分公司的市都设）增加市场份额，管理层同时也计划在新设分公司的城市最多建一个配送中心，当然也可以不建配送中心。经过城市最多建一个配送中心，当然也可以不建配送中心。经过计算，每种选择对公司收益的净现值、所需费用列在下表中，计算，每种选择对公司收益的净现值、所需费用列在下表中

21、，总预算投资费用不得超过总预算投资费用不得超过20万。如何决策使总净现值最大万。如何决策使总净现值最大决策编号决策编号问题问题净现值（万元）净现值（万元）所需资金（万）所需资金（万）1长春建厂否？长春建厂否？18122武汉建厂否？武汉建厂否？1063长春建配送中心否？长春建配送中心否？12104武汉建配送中心否？武汉建配送中心否？84设 xj=10- 决策j问题的答案是“是” - 决策j问题的答案是“否” max z = 18x1 + 10 x2 + 12x3+8x4 12x1 +6 x2 +10 x3+ 4x4 20 x3+ x4 1 （建建1个配送中心）个配送中心） x3 x1 x4 x2

22、 xj = 0或或1(j=1,2,3,4)最优解最优解 x1 =1，x2=1案例练习案例练习 例1：某油田在10个有油气构造处要选择若干个钻探采油，设第j个构造开采时需投资aj元，投产后预计年收净益为cj元，若该油田投资的总限额为b元，问：应选择哪几个构造开采最为有利？设 xj=10- 选择开采第j个构造 -不选择开采第j个构造max z=cjxjj=110ajxj bxj0或1 (j=1,2,-,10)j=110-年总收益-投资额限制1、表示选择性决策若在开采时还需满足下述条件： （a）若开采8号，则必须同时开采6号； （b）若开采5号，则不许开采3号； （c） 2 号和4号至少开采一个；

23、（d） 8 号与7号必须同时开采； （e）1号、4号、6号、9号开采时不能超过两个，试表示上述约束条件。设 xj=10- 选择开采第j个构造 -不选择开采第j个构造max z=cjxjj=110ajxj bxj0或1 (j=1,2,-,10)j=110-年总收益-投资额限制（a）当当x8=1x6=1，x60当当x8=0 x6=1，x6=0 x8 x6（b）当当x5 =1x3=0， x3 1当当x5 =0 x3=0， x3 =1 x5 + x3 1（c） x2 + x4 1（d） x8 = x7（e） x1 + x4 + x6 + x9 2 在生产或经营过程中，某一个业务活动在生产或经营过程中，

24、某一个业务活动开展通常伴随着固定成本的发生，比如开展通常伴随着固定成本的发生，比如添置或起用设备，新采购材料时产生的添置或起用设备，新采购材料时产生的差旅费，对工人必要培训的费用等，这差旅费，对工人必要培训的费用等，这些构成产品的固定成本。这时，业务活些构成产品的固定成本。这时，业务活动的总成本就包括与活动数量大小相关动的总成本就包括与活动数量大小相关的的变动成本变动成本和起动活动的和起动活动的固定成本固定成本。二二 固定费用（成本）问题固定费用（成本）问题案例案例某工厂近期接到一批订单，要安排生产甲、乙、丙、丁四种产品，每件产品分别需要原料某工厂近期接到一批订单，要安排生产甲、乙、丙、丁四种

25、产品，每件产品分别需要原料a、b、c中的一种或几种中的若干单位，合同规定要在中的一种或几种中的若干单位，合同规定要在15天内完成，但数量不限。由于四种产品都在同天内完成，但数量不限。由于四种产品都在同一种设备上生产，且一台设备同一时间只能加工一件产品。目前，工厂只有一台正使用中的这种一种设备上生产，且一台设备同一时间只能加工一件产品。目前，工厂只有一台正使用中的这种设备（设备设备（设备1），合同期内可挤出），合同期内可挤出3天来生产订单，但会产生天来生产订单，但会产生150元的机会成本损失；还有一台长元的机会成本损失；还有一台长期未用的设备（设备期未用的设备（设备2）可以启用，启用时要做必要的

26、检查和修理，费用）可以启用，启用时要做必要的检查和修理，费用1000元；公司还考虑向元；公司还考虑向邻厂租用邻厂租用2台（设备台（设备3，4），由于对方也在统筹使用，租期分别只能），由于对方也在统筹使用，租期分别只能7和和12天，租金分别天，租金分别2000和和3100，工厂可以决定租一台或两台，也可以一台不租。另外，每种产品如果生产会有固定成本和，工厂可以决定租一台或两台，也可以一台不租。另外，每种产品如果生产会有固定成本和变动成本，具体如下表，假设每天工作变动成本，具体如下表，假设每天工作8小时，工厂最多使用小时，工厂最多使用3台设备，问：工厂如何生产和利用台设备，问：工厂如何生产和利用设

27、备，利润最大设备，利润最大产品产品资源限制资源限制甲甲乙乙丙丙丁丁原料原料 设备设备1234原料原料a469015694183b2041c3805设备台时设备台时（小时）（小时）5738固定成固定成本（元）本（元）350400180 310变动成变动成本（元）本（元）12141611单位产品单位产品价格（元）价格（元）120160135 95 241205696 150100020003100:1,1,2,3,4;1,2,3,400max120 1 160 2 135 3 95 4(12 1 14 2 16 3 11 4350 1 400 2180 3 310 4)(150 1 1000 22

28、000 3 3100 4)jxizjzxxxxxxxxzzzzyyyyij生产j第产品的数量j=1,2,3,41,若设备i的使用台时0若产品j的实际生产量0y，否则，否则4x1+6x2+99424 1 120 256 3 96 4123431122334400101jyyyyyyyyxmzxmzxmzxmzxzijx31562x1+4x3+x43x1+8x2+5x41835x1+7x2+3x3+8x4，y或 ；或例例 应用应用 0-1 变量解决含互斥约束条件问题变量解决含互斥约束条件问题设：工序设：工序 b 有两种方式完成有两种方式完成 方式（方式（1 ）的工时约束为）的工时约束为 0.3x1

29、 + 0.5x2 150 方式（方式（2 ）的工时约束为）的工时约束为 0.2x1 + 0.4x2 120 问题是完成工序问题是完成工序 b 只能从两种方式中任选一种，如何将这两个只能从两种方式中任选一种，如何将这两个互斥的约束条件统一在一个线性规划模型中呢？互斥的约束条件统一在一个线性规划模型中呢？三三 互相排斥问题互相排斥问题32例例 7 应用应用 0-1 变量解决含互斥约束条件问题变量解决含互斥约束条件问题引入引入 0-1 变量变量y1 =0 若工序若工序 b 采用方式（采用方式（1 ）完成）完成1 若工序若工序 b 不采用方式（不采用方式（1 ）完成）完成y2 =0 若工序若工序 b

30、采用方式（采用方式（2 ）完成）完成1 若工序若工序 b 不采用方式（不采用方式（2 ）完成）完成三三 互相排斥问题互相排斥问题33例例 7 应用应用 0-1 变量解决含互斥约束条件问题变量解决含互斥约束条件问题于是前面两个互斥的约束条件可以统一为如下三个约束于是前面两个互斥的约束条件可以统一为如下三个约束条件：条件： 0.3x1 + 0.5x2 150 + m1y1 0.2x1 + 0.4x2 120 + m2y2 y1 + y2 = 1 其中其中 m1 ，m2 都是足够大的正数。都是足够大的正数。三三 互相排斥问题互相排斥问题34案例案例因为资金和管理水平的限制，某公司想以相同的价格和不同

31、的租期（工时）租因为资金和管理水平的限制，某公司想以相同的价格和不同的租期（工时）租赁另一公司甲、乙、丙、丁四个车间中的赁另一公司甲、乙、丙、丁四个车间中的两个两个，来生产五种新开发的产品（，来生产五种新开发的产品（a、b、c、d、e）中的最多中的最多三种三种。由于车间的机床和工人的经验不同，生产不同。由于车间的机床和工人的经验不同，生产不同产品的效率也不同，导致不同产品（任一阶段）在不同的车间生产所用的工时产品的效率也不同，导致不同产品（任一阶段）在不同的车间生产所用的工时数不同（根据生产部的初步实验和经验判断估计出的数据见下表）另外，根据数不同（根据生产部的初步实验和经验判断估计出的数据见

32、下表）另外，根据公司市场部的预测，每种产品的单位利润和在租期内最大的销售量以及各车间公司市场部的预测，每种产品的单位利润和在租期内最大的销售量以及各车间在租期内的总工时数等也见表）在租期内的总工时数等也见表）单位产品（阶段）的生产工时（小时）单位产品（阶段）的生产工时（小时）租期内总租期内总工时数工时数（小时）（小时）产品产品abcde车间车间甲甲58497180乙乙7113107230丙丙49386170丁丁37595165单位利润（百元）单位利润（百元）11148159最大销售量（件）最大销售量（件）2125231518取取m=1000，得得x1=20，x3=23，x4=2，z=434:1

33、,1,1,2,3,4;1,2,3,4,500max11 114 28 315 49 5)23)jxizjzxxxxxij12生产j第产品的数量（件）j=1,2,3,4,5租i车间实际生产j产品y，否则，否则5x1+8x2+4x3+9x4+7x5180+m(1-y7x1+11x2+3x3+10 x4+7x50+m(1-y4x1+9x2+3x3+8x4+6x5170+m(1)12342121 1225 2323 3415 4518 512345300101jyyyyxzxzxzxzxzzzzzzxz34ij-y3x1+7x2+5x3+9x4+5x5165+m(1-y且取整，y或 ；或0-1整数规划

34、的解法整数规划的解法 枚举法 隐枚举法整数规划整数规划指派指派(分配）问题分配）问题例：有一份中文产品说明书需译成英、日、德、俄四种语言，现有甲、乙、丙、丁四人都可以胜任，他们译成不同语言所需时间不同，如下表。求如何分配使所需总时间最少（每人只译一种） 语言人员ejgr甲215134乙1041415丙9141613丁78119整数规划整数规划指派问题的标准形式及其数学模型指派问题的标准形式及其数学模型指派问题的标准形式（以人和事为例）是：指派问题的标准形式（以人和事为例）是： 有有 n 个人和个人和 n 件事，已知第件事，已知第 i 人做第人做第 j 事的费用为事的费用为 cij（i，j =

35、1，2，n），），要求确定人和事之间的一一对应的指派方案，使完成这件要求确定人和事之间的一一对应的指派方案，使完成这件事的总费用最少。如事的总费用最少。如指派问题（指派问题（assignment problem）例：有一份中文产品说明书需译成英、日、德、俄四种语言，现有甲、乙、丙、丁四人例：有一份中文产品说明书需译成英、日、德、俄四种语言，现有甲、乙、丙、丁四人都可以胜任，他们译成不同语言所需时间不同，如下表。求如何分配使所需总时间最都可以胜任，他们译成不同语言所需时间不同，如下表。求如何分配使所需总时间最少（每人只译一种）少（每人只译一种） 语言语言人员人员ejgr甲甲215134乙乙104

36、1415丙丙9141613丁丁7811939建立模型：建立模型：设 xij=10译英文：x11+ x12 + x13 + x14 =1译日文：x21+ x22 + x23 + x24 =1译德文：x31+ x32 + x33 + x34 =1译俄文：x41+ x42 + x43 + x44 =1甲：x11+ x21 + x31 + x41 =1乙：x12+ x22 + x32 + x42 =1丙：x13+ x23 + x33 + x43 =1丁：x14+ x24 + x34 + x44 =1xij =0或1 (i=1,2,3,4; j=1,2,3,4)min z= aijxij(aij-效率)

37、i=1j=14 4若第i项工作交与第j个人完成若第i项工作不交与第j个人完成一般模型一般模型指派问题的标准形式，令指派问题的标准形式，令 1 当指派第当指派第 i 人完成第人完成第 j 项任务项任务 0 当不指派第当不指派第 i 人完成第人完成第 j 项任务项任务xij =min z = cijxij xij = 1， j = 1，2，n xij = 1， i = 1，2，n xij = 1 或或 041匈牙利解法匈牙利解法 标准的指派问题是一类特殊的标准的指派问题是一类特殊的 0-1 整数规划问题，整数规划问题，可以用多种相应的解法来求解。但是，这些方法都没可以用多种相应的解法来求解。但是，

38、这些方法都没有充分利用指派问题的特殊性质来有效减少计算量。有充分利用指派问题的特殊性质来有效减少计算量。1955年，库恩（年，库恩（w.w.kuhn）利用匈牙利数学家康尼利用匈牙利数学家康尼格（格（d.knig）的关于矩阵中独立零元素的定理，提的关于矩阵中独立零元素的定理，提出了指派问题的一种解法，由此，习惯上称之为匈牙出了指派问题的一种解法，由此，习惯上称之为匈牙利解法。利解法。42 匈牙利解法的关键是利用了指派问题最优解的如匈牙利解法的关键是利用了指派问题最优解的如下下性质：性质： 若从指派问题的系数矩阵若从指派问题的系数矩阵 c = （ cij ）nn 的某的某行（或某列）各元素分别行（

39、或某列）各元素分别减去一个常数减去一个常数 k ，得到一个得到一个新的系数矩阵新的系数矩阵c = （ cij ）则以则以 c 和和 c 为系数矩阵为系数矩阵的两个指派问题有的两个指派问题有相同的最优解相同的最优解。匈牙利解法匈牙利解法43步骤一：步骤一： 变换系数矩阵。使其每行及每列至少变换系数矩阵。使其每行及每列至少有一个零元素，同时不出现负元素。有一个零元素，同时不出现负元素。步骤二：步骤二： 进行试指派，即确定独立零元素。进行试指派，即确定独立零元素。步骤三：步骤三： 继续变换系数矩阵，然后返回步骤二。继续变换系数矩阵，然后返回步骤二。匈牙利解法的一般步骤匈牙利解法的一般步骤44以上例说

40、明步骤以上例说明步骤 2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9 0 13 11 2 6 0 10 11 0 5 7 4 0 1 4 22497min（ cij ）=匈牙利解法的一般步骤匈牙利解法的一般步骤45指派问题（指派问题（assignment problem）匈牙利解法的一般步骤匈牙利解法的一般步骤以上例说明步骤以上例说明步骤 0 13 11 2 6 0 10 11 0 4 7 4 0 1 4 2 0 0 4 2min 0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0= （ cij ）指派问题（指派问题（assignment pro

41、blem）46以上例说明步骤以上例说明步骤 0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0此时加圈此时加圈 0 元素的个数元素的个数 m = n = 4，所以得到最优解所以得到最优解指派问题（指派问题（assignment problem）47匈牙利解法的一般步骤匈牙利解法的一般步骤以上例说明步骤以上例说明步骤 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0（ xij ）=指派问题（指派问题（assignment problem）48匈牙利解法的一般步骤匈牙利解法的一般步骤例例任务任务人员人员abcde甲甲乙乙丙丙丁丁戊戊1287154791714109612

42、677614610969109指派问题（指派问题（assignment problem）49匈牙利解法的一般步骤匈牙利解法的一般步骤 12 7 9 7 9 8 9 6 6 6 7 17 12 14 9 15 14 6 6 10 4 10 7 10 976764 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5指派问题（指派问题（assignment problem）50匈牙利解法的一般步骤匈牙利解法的一般步骤 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5 此时加圈此时加圈 0 元素的个数

43、元素的个数 m = 4， 而而n = 5，所以解题没所以解题没有完成。独立零元素（加圈零有完成。独立零元素（加圈零元素）少于元素）少于 n 个，表示还不能个，表示还不能确定最优确定最优指派方案。此时需确定指派方案。此时需确定能覆盖所有能覆盖所有零元素的最少直线数零元素的最少直线数目的直线集合。方法如下：目的直线集合。方法如下：指派问题（指派问题（assignment problem）51匈牙利解法的一般步骤匈牙利解法的一般步骤1)对没有加圈零元素的行打对没有加圈零元素的行打号；号；2)对所有打对所有打号行的所有含零元素的列打号行的所有含零元素的列打号；号；3)再对已打再对已打号的列中含零元素的

44、行打号的列中含零元素的行打号；号；4)重复重复2）和）和3），直到再也不能找到可以打），直到再也不能找到可以打号行号行或列为止；或列为止；5)对没有打对没有打号的行画一横线，对打号的行画一横线，对打号的列画一竖号的列画一竖线，这样就得到线，这样就得到能覆盖所有能覆盖所有零元素的最少直线数零元素的最少直线数目的直线集合。目的直线集合。指派问题（指派问题（assignment problem）52匈牙利解法的一般步骤匈牙利解法的一般步骤 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5指派问题（指派问题（assignment problem）53

45、匈牙利解法的一般步骤匈牙利解法的一般步骤 继续变换系数矩阵。其方法是在未被直线覆盖的继续变换系数矩阵。其方法是在未被直线覆盖的元素中找出一个最小元素。然后在打元素中找出一个最小元素。然后在打号号行行各元素都各元素都减减去这一最小元素，而在打去这一最小元素，而在打号号列列的各元素都的各元素都加加上这上这一最小元素，以保证原来的一最小元素，以保证原来的 0 元素不变。这样得到新元素不变。这样得到新系数矩阵（其最优解和原问题相同）。若得到系数矩阵（其最优解和原问题相同）。若得到 n 个独个独立的立的 0 元素，则已得最优解，否则重复该步骤继续变元素，则已得最优解，否则重复该步骤继续变换系数矩阵。换系

46、数矩阵。指派问题（指派问题（assignment problem）54匈牙利解法的一般步骤匈牙利解法的一般步骤 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5最小元素最小元素= 2 7 0 2 0 2 4 3 0 0 0 0 8 3 5 0 11 8 0 0 4 0 4 1 4 3指派问题（指派问题（assignment problem）55匈牙利解法的一般步骤匈牙利解法的一般步骤 7 0 2 0 2 4 3 0 0 0 0 8 3 5 0 11 8 0 0 4 0 4 1 4 3 此时加圈此时加圈 0 元素的个数元素的个数 m = 5，

47、而而n = 5，独立零元素独立零元素（加圈零元素）等于（加圈零元素）等于 n 个，个，此此时已得到最优解，其解矩阵为时已得到最优解，其解矩阵为指派问题（指派问题（assignment problem）56匈牙利解法的一般步骤匈牙利解法的一般步骤（ xij ）= 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 最优指派：最优指派：甲甲 b乙乙 c丙丙 e丁丁 d戊戊 a指派问题（指派问题（assignment problem）57 在实际应用中，常会遇到各种非标准形式的制派问题。一般的在实际应用中，常会遇到各种非标准形式的制派问题。一般的处理方

48、法是先将其转化为标准形式，然后再用匈牙利法求解。处理方法是先将其转化为标准形式，然后再用匈牙利法求解。1.最大化指派问题最大化指派问题设最大化指派问题系数矩阵设最大化指派问题系数矩阵 c = （ cij ） ，其中最大元素为其中最大元素为 m 。令矩阵令矩阵 b = （ bij ）= （ m - cij ），），则以则以 b 为系数矩阵的最小化指派问题和以为系数矩阵的最小化指派问题和以 c 为系数矩阵的最大化指为系数矩阵的最大化指派问题有相同最优解。派问题有相同最优解。2.人数和事数不等的指派问题人数和事数不等的指派问题若若人少事多人少事多，则添加一些虚拟，则添加一些虚拟的的“人人”，其费用系

49、数取，其费用系数取 0 ，若，若人多事少人多事少，则添加一些虚拟的，则添加一些虚拟的“事事”，其费用系数取，其费用系数取 0 。 非标准形式的指派问题非标准形式的指派问题58非标准形式的指派问题非标准形式的指派问题3.一个人可做几件事的指派问题一个人可做几件事的指派问题若某个人可以做几件事，则若某个人可以做几件事，则将该人化作几个将该人化作几个“人人”来接受指派。这几个来接受指派。这几个“人人”做同一件事做同一件事的费用系数当然都一样。的费用系数当然都一样。4.某事一定不能由某人做的指派问题某事一定不能由某人做的指派问题若某事一定不能由某人若某事一定不能由某人做，则可将相应的费用系数取为足够大

50、的数做，则可将相应的费用系数取为足够大的数 m 。非标准形式的指派问题非标准形式的指派问题59非标准指派问题非标准指派问题 例：分派甲、乙、丙、丁四人完成五项任务，每人完成任务的时间如下表，请就以下要求分别求解分配情况。 任务人员abcde甲甲2529314237乙乙3938262033丙丙3427284032丁丁24423623451）要求每人只完成一项2）甲完成两项，其他人每人完成一项3）丁因某种原因不能承担a工作，其他每人一项，e必须承担任务整数规划整数规划1）要求每人只完成一项 任务人员abcde甲甲2529314237乙乙3938262033丙丙3427284032丁丁2442362345戊戊000002）甲完成两项，其他人每人完成一项 任务人员abcde甲甲2529314237乙乙3938262033丙丙3427284032丁丁2