《工程运筹学》教学案卷

《《工程运筹学》教学案卷》由会员分享，可在线阅读，更多相关《《工程运筹学》教学案卷（42页珍藏版）》请在金锄头文库上搜索。

1、工程运筹学工程运筹学教学案卷教学案卷 对象：交通运输、农业工程、环境工程对象：交通运输、农业工程、环境工程对象：交通运输、农业工程、环境工程对象：交通运输、农业工程、环境工程 http:/ 整数规划整数规划n n 讲课讲课讲课讲课4 4学时学时学时学时 ，实验，实验，实验，实验2 2学时学时学时学时n n6-1 整数规划数学模型整数规划数学模型n n6-2 分枝定界法分枝定界法n n6-3 “01型型”整数规划的解法整数规划的解法n n6-4 指派问题指派问题为本章重点内容为本章重点内容08级级本本科科适适用用6-1 整数规划数学模型整数规划数学模型n n 前面讨论了线性规划问题，其基变量的最

2、优解可以是整前面讨论了线性规划问题，其基变量的最优解可以是整前面讨论了线性规划问题，其基变量的最优解可以是整前面讨论了线性规划问题，其基变量的最优解可以是整数，也可以是分数或小数。数，也可以是分数或小数。数，也可以是分数或小数。数，也可以是分数或小数。n n实际生产中，很多问题的最优解必须是整数才有实际意义。实际生产中，很多问题的最优解必须是整数才有实际意义。实际生产中，很多问题的最优解必须是整数才有实际意义。实际生产中，很多问题的最优解必须是整数才有实际意义。n n比如，农机配备模型中，农业机械及拖拉机的台数；比如，农机配备模型中，农业机械及拖拉机的台数；比如，农机配备模型中，农业机械及拖拉

3、机的台数；比如，农机配备模型中，农业机械及拖拉机的台数；n n列车、飞机编组中的列数与架数；再如果树栽培的株数、劳列车、飞机编组中的列数与架数；再如果树栽培的株数、劳列车、飞机编组中的列数与架数；再如果树栽培的株数、劳列车、飞机编组中的列数与架数；再如果树栽培的株数、劳动力分派的人数等等。动力分派的人数等等。动力分派的人数等等。动力分派的人数等等。n n 只允许变量取整数最优解的线性规划称为整数规划只允许变量取整数最优解的线性规划称为整数规划只允许变量取整数最优解的线性规划称为整数规划只允许变量取整数最优解的线性规划称为整数规划n n英文英文英文英文 Integer ProgrammingIn

4、teger Programming，简称，简称，简称，简称IPIP为整数规划问题。为整数规划问题。为整数规划问题。为整数规划问题。n n整数规划是近三十年来发展起来的规划论中的一个分支。整数规划是近三十年来发展起来的规划论中的一个分支。整数规划是近三十年来发展起来的规划论中的一个分支。整数规划是近三十年来发展起来的规划论中的一个分支。 08级级本本科科适适用用6-1 整数规划数学模型整数规划数学模型n n 我们我们我们我们能不能把线性规划的非整数规划最能不能把线性规划的非整数规划最优解经过优解经过“舍入化整舍入化整”就行了呢？就行了呢？n n例例1：某农场拟用甲、乙两种拖拉机运输农：某农场拟用

5、甲、乙两种拖拉机运输农产品，每种拖拉机的耗油量和装卸、驾驶等产品，每种拖拉机的耗油量和装卸、驾驶等用工时、油量、工人数限制量及利润见表，用工时、油量、工人数限制量及利润见表，问两种拖拉机各用几台，才可获利最大？问两种拖拉机各用几台，才可获利最大？n n显然这是一个关于拖拉机配备的整数问题显然这是一个关于拖拉机配备的整数问题 08级级本本科科适适用用6-1 整数规划数学模型整数规划数学模型拖拉机用工数（人）耗油量（公斤）利润（百元）甲5220乙4510限制量2413我我们首先首先设 x1 ，x2 分别为使分别为使用甲、乙两种拖拉机的台数，用甲、乙两种拖拉机的台数，则其数学模型为：则其数学模型为：

6、 08级级本本科科适适用用6-1 整数规划数学模型整数规划数学模型最后的约束条件（最后的约束条件（5）这个模型和（这个模型和（LP）模型的区别仅在于？）模型的区别仅在于？现在不考虑（现在不考虑（5），解（），解（1）-（4）显然不是整数，不符合要求。假如我们显然不是整数，不符合要求。假如我们显然不是整数，不符合要求。假如我们显然不是整数，不符合要求。假如我们“ “舍入化整舍入化整舍入化整舍入化整” ”代入方程（代入方程（2），就破坏了人数约数。），就破坏了人数约数。 （以后我们称这样的问题为原问题相应的（以后我们称这样的问题为原问题相应的LP问题）问题）利用单纯形法很容易就可解得：利用单纯形法

7、很容易就可解得：就满足约束条件，因而是可行解就满足约束条件，因而是可行解 但不是最优解但不是最优解 08级级本本科科适适用用6-1 整数规划数学模型整数规划数学模型n n那么如何求解整数规划问题呢？那么如何求解整数规划问题呢？那么如何求解整数规划问题呢？那么如何求解整数规划问题呢？n n 我们首先想到的办法是穷举变量的所有可行的整数组我们首先想到的办法是穷举变量的所有可行的整数组我们首先想到的办法是穷举变量的所有可行的整数组我们首先想到的办法是穷举变量的所有可行的整数组合，再比较各组合的目标函数值，从中定出最优解。合，再比较各组合的目标函数值，从中定出最优解。合，再比较各组合的目标函数值，从中

8、定出最优解。合，再比较各组合的目标函数值，从中定出最优解。n n 对于简单的问题来说，上述对于简单的问题来说，上述对于简单的问题来说，上述对于简单的问题来说，上述 方法是可行的，方法是可行的，方法是可行的，方法是可行的，n n 对于复杂的大问题，显然穷举法是不合适的。对于复杂的大问题，显然穷举法是不合适的。对于复杂的大问题，显然穷举法是不合适的。对于复杂的大问题，显然穷举法是不合适的。n n常用的整数规划解法有分枝定界法、割平面法。常用的整数规划解法有分枝定界法、割平面法。常用的整数规划解法有分枝定界法、割平面法。常用的整数规划解法有分枝定界法、割平面法。n n解解解解0-10-1整数规划还有

9、隐枚举法、指派匈牙利法等。整数规划还有隐枚举法、指派匈牙利法等。整数规划还有隐枚举法、指派匈牙利法等。整数规划还有隐枚举法、指派匈牙利法等。n n下面介绍分枝定界法下面介绍分枝定界法下面介绍分枝定界法下面介绍分枝定界法 08级级本本科科适适用用6-2 6-2 分枝定界法分枝定界法分枝定界法分枝定界法（Branch and Bound MethodBranch and Bound Method）n n 由于整数规划是在相应的线性规划问题的基由于整数规划是在相应的线性规划问题的基由于整数规划是在相应的线性规划问题的基由于整数规划是在相应的线性规划问题的基础上，增加了变量为整数的约束条件。础上，增加

10、了变量为整数的约束条件。础上，增加了变量为整数的约束条件。础上，增加了变量为整数的约束条件。n n所以其可行域就会缩小，其最优解也就不会优越所以其可行域就会缩小，其最优解也就不会优越所以其可行域就会缩小，其最优解也就不会优越所以其可行域就会缩小，其最优解也就不会优越于相应的线性规划问题的最优解。于相应的线性规划问题的最优解。于相应的线性规划问题的最优解。于相应的线性规划问题的最优解。n n对于求极大值问题来说，相应的线性规划目标函对于求极大值问题来说，相应的线性规划目标函对于求极大值问题来说，相应的线性规划目标函对于求极大值问题来说，相应的线性规划目标函数值就成为其整数规划目标函数值得上界。数

11、值就成为其整数规划目标函数值得上界。数值就成为其整数规划目标函数值得上界。数值就成为其整数规划目标函数值得上界。08级级本本科科适适用用6-2 6-2 分枝定界法分枝定界法分枝定界法分枝定界法（Branch and Bound MethodBranch and Bound Method）n n 分枝定界法分枝定界法分枝定界法分枝定界法就是利用该性质来求解的一种方法就是利用该性质来求解的一种方法就是利用该性质来求解的一种方法就是利用该性质来求解的一种方法n n 设最大化的整数规划问题设最大化的整数规划问题设最大化的整数规划问题设最大化的整数规划问题A A，与它相对应的线性，与它相对应的线性，与它

12、相对应的线性，与它相对应的线性规划问题为规划问题为规划问题为规划问题为B B。n n先先先先 解问题解问题解问题解问题B B，若其最优解不符合，若其最优解不符合，若其最优解不符合，若其最优解不符合A A的整数条件，那的整数条件，那的整数条件，那的整数条件，那么么么么B B的最优目标函数必是的最优目标函数必是的最优目标函数必是的最优目标函数必是A A的最优目标函数的最优目标函数的最优目标函数的最优目标函数 Z* Z* n n 的上界，记作的上界，记作的上界，记作的上界，记作 Z ZB B n nA A任意可行解目标函数值将是任意可行解目标函数值将是任意可行解目标函数值将是任意可行解目标函数值将是

13、 Z*Z*的一个下界的一个下界的一个下界的一个下界 Z ZA A 。08级级本本科科适适用用6-2 6-2 分枝定界法分枝定界法分枝定界法分枝定界法（Branch and Bound MethodBranch and Bound Method）n n例：求解下面整数规划问题例：求解下面整数规划问题例：求解下面整数规划问题例：求解下面整数规划问题n n解：（解：（解：（解：（1 1）- -（5 5）为问题）为问题）为问题）为问题A A ，不考虑条件（不考虑条件（不考虑条件（不考虑条件（5 5）的）的）的）的（1 1）（4 4），为），为），为），为B B（即（即（即（即A A相应的相应的相应的相

14、应的LPLP问题）问题）问题）问题）n n解解解解B B得最优解为：得最优解为：得最优解为：得最优解为：n n该该该该最优解不符整数条件，但最优解不符整数条件，但最优解不符整数条件，但最优解不符整数条件，但 是问题是问题是问题是问题 A A 的最优目标函数值的最优目标函数值的最优目标函数值的最优目标函数值 的上界。的上界。的上界。的上界。 08级级本本科科适适用用6-2 6-2 分枝定界法分枝定界法分枝定界法分枝定界法（Branch and Bound Branch and Bound MethodMethod）n n分枝定界法首先注意一个非整数变量，如分枝定界法首先注意一个非整数变量，如分枝

15、定界法首先注意一个非整数变量，如分枝定界法首先注意一个非整数变量，如n n 于是对问题分别增加约束条件于是对问题分别增加约束条件于是对问题分别增加约束条件于是对问题分别增加约束条件n n即将原问题分解为两个子问题即将原问题分解为两个子问题即将原问题分解为两个子问题即将原问题分解为两个子问题 B B1 1 ，B B2 2 即两枝。即两枝。即两枝。即两枝。n n给每一枝增加一个约束条件，如图给每一枝增加一个约束条件，如图给每一枝增加一个约束条件，如图给每一枝增加一个约束条件，如图6-16-1（这并不影响问题（这并不影响问题（这并不影响问题（这并不影响问题A A的可行域）的可行域）的可行域）的可行域

16、）n n不考虑整数条件，解不考虑整数条件，解不考虑整数条件，解不考虑整数条件，解 B B1 1 ，B B2 2 08级级本本科科适适用用6-2 6-2 分枝定界法（分枝定界法（分枝定界法（分枝定界法（Branch and Bound MethodBranch and Bound Method）图图图图6-26-2将将B中的中的X1=4.81分成分成X15或或X1 4不考不考虑整数条件，解整数条件，解B1 ，B2得最优解见表得最优解见表 问问问问 题题题题 B1 问问问问 题题题题 B2解解B1 ，B2，将可行域，将可行域D分成分成为D1，D2将将B1中的中的X2=2.1再分成再分成X23或或X

17、22，即，即1分解分解为B3 ，B4 不考不考虑整数条件，解整数条件，解B3 ，B42308级级本本科科适适用用6-2 6-2 分枝定界法（分枝定界法（分枝定界法（分枝定界法（Branch and Bound MethodBranch and Bound Method）n n解解解解 B B3 3 - - 符合整数条件符合整数条件符合整数条件符合整数条件 n n解解解解 B B4 4 - - 不合整数条件不合整数条件不合整数条件不合整数条件n n那么还有没有必要继续分解那么还有没有必要继续分解那么还有没有必要继续分解那么还有没有必要继续分解 B B4 4 呢？呢？呢？呢？n n没有，因为再分解

18、没有，因为再分解没有，因为再分解没有，因为再分解 B B4 4 ，最后得到的目标函数值不会，最后得到的目标函数值不会，最后得到的目标函数值不会，最后得到的目标函数值不会超过超过超过超过327327，而，而，而，而327327本身就小于本身就小于本身就小于本身就小于340340。08级级本本科科适适用用6-2 6-2 分枝定界法（分枝定界法（分枝定界法（分枝定界法（Branch and Bound MethodBranch and Bound Method）n n但此时还不能认为但此时还不能认为但此时还不能认为但此时还不能认为 B B3 3的解就是整数最优解。的解就是整数最优解。的解就是整数最优

19、解。的解就是整数最优解。n n因为问题因为问题因为问题因为问题 B B2 2的的的的z=341340z=341340，最优解可能在，最优解可能在，最优解可能在，最优解可能在340341340341之间有整数解，之间有整数解，之间有整数解，之间有整数解，n n于是对于是对于是对于是对 B B2 2分解即在分解即在分解即在分解即在 条件下构成问条件下构成问条件下构成问条件下构成问题题题题 B B5 5 ，B B6 6 ，经过计算，经过计算，经过计算，经过计算 B B5 5 ，B B6 6 对应的目标函对应的目标函对应的目标函对应的目标函数值都小于数值都小于数值都小于数值都小于340340。n n为

20、最优整数解，最优值为为最优整数解，最优值为为最优整数解，最优值为为最优整数解，最优值为综上，所以综上，所以综上，所以综上，所以08级级本本科科适适用用6-2 6-2 分枝定界法（分枝定界法（分枝定界法（分枝定界法（Branch and Bound MethodBranch and Bound Method）n n从以上解的过程可以总结出分枝定界法求解整数从以上解的过程可以总结出分枝定界法求解整数从以上解的过程可以总结出分枝定界法求解整数从以上解的过程可以总结出分枝定界法求解整数规划（最大化）问题的步骤如下：规划（最大化）问题的步骤如下：规划（最大化）问题的步骤如下：规划（最大化）问题的步骤如下

21、：n n （1 1）称原问题（整数规划）为问题）称原问题（整数规划）为问题）称原问题（整数规划）为问题）称原问题（整数规划）为问题A A，称其相应，称其相应，称其相应，称其相应不考虑整数条件的线性规划问题为不考虑整数条件的线性规划问题为不考虑整数条件的线性规划问题为不考虑整数条件的线性规划问题为B B，解，解，解，解B B。n n （2 2）如）如）如）如B B没有可行解则止，说明没有可行解则止，说明没有可行解则止，说明没有可行解则止，说明A A也无可行解。也无可行解。也无可行解。也无可行解。n n（3 3） 如如如如B B有最优解，判断是否符合整数条件，有最优解，判断是否符合整数条件，有最优

22、解，判断是否符合整数条件，有最优解，判断是否符合整数条件，n n如符合则它就是如符合则它就是如符合则它就是如符合则它就是A A的最优解，否则进行下一步。的最优解，否则进行下一步。的最优解，否则进行下一步。的最优解，否则进行下一步。08级级本本科科适适用用6-2 6-2 分枝定界法（分枝定界法（分枝定界法（分枝定界法（Branch and Bound MethodBranch and Bound Method）n n（4 4）在问题）在问题）在问题）在问题B B中，任选一个不符合整数条件的变中，任选一个不符合整数条件的变中，任选一个不符合整数条件的变中，任选一个不符合整数条件的变量，如果量，如果

23、量，如果量，如果 X X j j 的值是的值是的值是的值是 b b j j ，进行如下分枝，它，进行如下分枝，它，进行如下分枝，它，进行如下分枝，它们就是对问题们就是对问题们就是对问题们就是对问题B B各个增加一个约束条件：各个增加一个约束条件：各个增加一个约束条件：各个增加一个约束条件：n n 小于小于小于小于 b b j j的最大整数；的最大整数；的最大整数；的最大整数；n n 大于大于大于大于 b b j j的最小整数。的最小整数。的最小整数。的最小整数。n n（5 5）不考虑整数条件，解这两个后续问题。）不考虑整数条件，解这两个后续问题。）不考虑整数条件，解这两个后续问题。）不考虑整数

24、条件，解这两个后续问题。n n 在还没有分解出的后继问题的各可行问题中，在还没有分解出的后继问题的各可行问题中，在还没有分解出的后继问题的各可行问题中，在还没有分解出的后继问题的各可行问题中，n n选目标函数最大的问题，重新称这个问题为选目标函数最大的问题，重新称这个问题为选目标函数最大的问题，重新称这个问题为选目标函数最大的问题，重新称这个问题为B B，n n回到步骤（回到步骤（回到步骤（回到步骤（3 3） 重复进行。重复进行。重复进行。重复进行。08级级本本科科适适用用6-3 “01型型”整数规划的解法整数规划的解法 “01 “01型型型型” ”整数规划是整数规划中的特殊情形，整数规划是整

25、数规划中的特殊情形，整数规划是整数规划中的特殊情形，整数规划是整数规划中的特殊情形，规划中只限定决策变量取规划中只限定决策变量取规划中只限定决策变量取规划中只限定决策变量取0 0或或或或1 1两个数值，两个数值，两个数值，两个数值， 把把把把 X X j j 称为称为称为称为“ “01”01”变量。变量。变量。变量。 “ “01”01”规划多用于选择投资场所，确定新上工规划多用于选择投资场所，确定新上工规划多用于选择投资场所，确定新上工规划多用于选择投资场所，确定新上工程项目，指派工作任务等实际问题。程项目，指派工作任务等实际问题。程项目，指派工作任务等实际问题。程项目，指派工作任务等实际问题

26、。08级级本本科科适适用用6-3 “01型型”整数规划的解整数规划的解法法n n例：某矿泉水公司拟在市东、西、南、北四个区设立例：某矿泉水公司拟在市东、西、南、北四个区设立例：某矿泉水公司拟在市东、西、南、北四个区设立例：某矿泉水公司拟在市东、西、南、北四个区设立门市部，有门市部，有门市部，有门市部，有9 9个位置点个位置点个位置点个位置点 可供选择。同可供选择。同可供选择。同可供选择。同时考虑实际情况规定：时考虑实际情况规定：时考虑实际情况规定：时考虑实际情况规定：n n 东区的点东区的点东区的点东区的点 中至少选两个；中至少选两个；中至少选两个；中至少选两个；n n 西区的点西区的点西区的

27、点西区的点 中至少选一个；中至少选一个；中至少选一个；中至少选一个；n n 南区的点南区的点南区的点南区的点 中至少选一个；中至少选一个；中至少选一个；中至少选一个； 北区北区北区北区 点全选点全选点全选点全选 n n如果如果如果如果 点被选中，设备投资点被选中，设备投资点被选中，设备投资点被选中，设备投资 元，每年获利元，每年获利元，每年获利元，每年获利 n n 元。但所有点投资总额不超过元。但所有点投资总额不超过元。但所有点投资总额不超过元。但所有点投资总额不超过B B元，问应该选择哪些点才元，问应该选择哪些点才元，问应该选择哪些点才元，问应该选择哪些点才可使年利润最大？可使年利润最大？可

28、使年利润最大？可使年利润最大？ 08级级本本科科适适用用6-3 “01型型”整数规划的解整数规划的解法法n n解：先引入解：先引入解：先引入解：先引入“ “01”01”变量变量变量变量 ， 令令令令n n n n 求满足前述约束条件：求满足前述约束条件：求满足前述约束条件：求满足前述约束条件：n n此例即为此例即为此例即为此例即为“ “01”01”型整数规划，型整数规划，型整数规划，型整数规划，那么解决这样问题，最容易想的那么解决这样问题，最容易想的那么解决这样问题，最容易想的那么解决这样问题，最容易想的就是穷举法，即检查变量取值就是穷举法，即检查变量取值就是穷举法，即检查变量取值就是穷举法，

29、即检查变量取值0 0或或或或1 1的每一个组合，并比较目标的每一个组合，并比较目标的每一个组合，并比较目标的每一个组合，并比较目标函数求得最优解。这就需要检查函数求得最优解。这就需要检查函数求得最优解。这就需要检查函数求得最优解。这就需要检查变量取值的变量取值的变量取值的变量取值的 2 2 的的的的 n n次方次方次方次方个组合。个组合。个组合。个组合。 当当当当n n很大时，几乎是不可能的。很大时，几乎是不可能的。很大时，几乎是不可能的。很大时，几乎是不可能的。因此设计一些方法，只检查变因此设计一些方法，只检查变因此设计一些方法，只检查变因此设计一些方法，只检查变量取值的组合的一部分，就能量

30、取值的组合的一部分，就能量取值的组合的一部分，就能量取值的组合的一部分，就能够求得问题的最优解。够求得问题的最优解。够求得问题的最优解。够求得问题的最优解。n n这样的方法称为隐枚举法，这样的方法称为隐枚举法，这样的方法称为隐枚举法，这样的方法称为隐枚举法，分枝定界法实际上也是一种隐分枝定界法实际上也是一种隐分枝定界法实际上也是一种隐分枝定界法实际上也是一种隐枚举法。枚举法。枚举法。枚举法。08级级本本科科适适用用6-3 “01型型”整数规划的解法整数规划的解法下面举例说明一种解下面举例说明一种解0-1型整数规划的隐枚举法型整数规划的隐枚举法08级级本本科科适适用用6-3 “01型型”整数规划

31、的解法整数规划的解法 先通先通过试换的方法找出一个可行解。容易看出的方法找出一个可行解。容易看出得得z=3。由于是求极大。由于是求极大值问题，当然希望，当然希望于是增加一个于是增加一个约束条件（束条件（0）：）： 是符合（是符合（1）（4）条件的可行解）条件的可行解下面举例说明一种解下面举例说明一种解0-1型整数规划的隐枚举法型整数规划的隐枚举法条件（条件（0）称）称为过滤条件（条件（Filtering Constraint）。 这样原原问题的的线性条件就性条件就变成了成了5个个。 原原题如果用全部的枚如果用全部的枚举法，法，3个个变量共有量共有23=8个解，加上个解，加上4个约束条件，共需个

32、约束条件，共需32次运算。次运算。 按照（按照（0）（4）的顺序排好。对每个解，依次代入约束）的顺序排好。对每个解，依次代入约束方程左侧，求出数值，如下表方程左侧，求出数值，如下表1 。看是否符合不等式条件，。看是否符合不等式条件，如果不符合，同行以下各条件就不必检查，因而就减少了如果不符合，同行以下各条件就不必检查，因而就减少了运算次数。运算次数。08级级本本科科适适用用6-3 “01型型”整数规划的解法整数规划的解法约 束束 条条 件件满足条件足条件否否 是是Z值（0）（1）（2）（3）（4） 05-11015-2如此如此检查下去，下去，结果果见下个幻灯片下个幻灯片 08级级本本科科适适用

33、用6-3 “01型型”整数规划的解法整数规划的解法约 束束 条条 件件满足条件足条件否否 是是Z值（0）（1）（2）（3）（4）05-233816-1110215126001 101 538经过24次运算求得最次运算求得最优解：解：，08级级本本科科适适用用6-3 “01型型”整数规划的解法整数规划的解法约 束束 条条 件件满足条件足条件否否 是是Z值（0）（1）（2）（3）（4） 055-2在在计算算过程中，若遇到程中，若遇到z值已超已超过条件（条件（0）右）右边值，应改改变条件（条件（0），使右），使右边为迄今迄今为止的最大者，然后止的最大者，然后继续运算。运算。如当如当检查点（点（0，0

34、，1）时，因，因z=53，改之，改之为新的新的过滤条条件，可减少更多的件，可减少更多的计算量。算量。 338021116268如当如当检查点（点（1，0，1）时，因，因z=85，改之，改之为新的新的过滤条条件，件，还可减少更多的可减少更多的计算量。此算量。此处略。略。 08级级本本科科适适用用6-3 “01型型”整数规划的解法整数规划的解法 为了使最了使最优解比解比较早出早出现，一般重新排列，一般重新排列X j的的顺序，序，使目使目标函数中函数中X j的系数是的系数是递增的。那么本例可改增的。那么本例可改为：约束方程与变量取值均按照顺序：约束方程与变量取值均按照顺序：、按照前面方法求解会更快取

35、得最优解。共计算按照前面方法求解会更快取得最优解。共计算16次。次。08级级本本科科适适用用6-4 指派问题指派问题n n 在实际工作中，常常会碰到这样的问题，要在实际工作中，常常会碰到这样的问题，要在实际工作中，常常会碰到这样的问题，要在实际工作中，常常会碰到这样的问题，要指派几个人去完成几项不同的任务，每个人必须指派几个人去完成几项不同的任务，每个人必须指派几个人去完成几项不同的任务，每个人必须指派几个人去完成几项不同的任务，每个人必须完成其中一项，而且仅仅一项。但由于各个人的完成其中一项，而且仅仅一项。但由于各个人的完成其中一项，而且仅仅一项。但由于各个人的完成其中一项，而且仅仅一项。但

36、由于各个人的专长不同，任务的难易程度也不一样，所以完成专长不同，任务的难易程度也不一样，所以完成专长不同，任务的难易程度也不一样，所以完成专长不同，任务的难易程度也不一样，所以完成不同任务的效率就不同。那么，应该指派哪个人不同任务的效率就不同。那么，应该指派哪个人不同任务的效率就不同。那么，应该指派哪个人不同任务的效率就不同。那么，应该指派哪个人去完成哪项任务才能使总的效率最高（或需要总去完成哪项任务才能使总的效率最高（或需要总去完成哪项任务才能使总的效率最高（或需要总去完成哪项任务才能使总的效率最高（或需要总的时间最少）呢？这就是典型的指派问题。的时间最少）呢？这就是典型的指派问题。的时间最

37、少）呢？这就是典型的指派问题。的时间最少）呢？这就是典型的指派问题。n n例例例例1 1 1 1：今欲指派赵、钱、孙、李四人加工：今欲指派赵、钱、孙、李四人加工：今欲指派赵、钱、孙、李四人加工：今欲指派赵、钱、孙、李四人加工A A A A、B B B B、C C C C、D D D D四种不同的零件，每人加工四种零件所需时间如四种不同的零件，每人加工四种零件所需时间如四种不同的零件，每人加工四种零件所需时间如四种不同的零件，每人加工四种零件所需时间如下表，问应该指派谁加工何种零件可使总的花费下表，问应该指派谁加工何种零件可使总的花费下表，问应该指派谁加工何种零件可使总的花费下表，问应该指派谁加

38、工何种零件可使总的花费时间最少？时间最少？时间最少？时间最少？ 08级级本本科科适适用用6-4 指派问题指派问题ABCD赵4658钱61078孙78119李9384零件零件人员人员ABCD赵4658钱61078孙78119李9384表表6-4-16-4-1： ( (单位：工时单位：工时) ) 在在类似的似的问题中，都必中，都必须给出像表出像表6-4-1的数表称的数表称为效率矩效率矩阵或系数矩或系数矩阵，其元素，其元素 表示指派第表示指派第i人去完成第人去完成第j项任务的效率。项任务的效率。08级级本本科科适适用用6-4 指派问题指派问题n n求解这类问题时，通常引入求解这类问题时，通常引入求解

39、这类问题时，通常引入求解这类问题时，通常引入0101变量，变量，变量，变量，n n对于极小化问题，指派问题数学模型为：对于极小化问题，指派问题数学模型为：对于极小化问题，指派问题数学模型为：对于极小化问题，指派问题数学模型为：约束条件（约束条件（2）说）说明第明第j项任务只能由项任务只能由1人去完成；人去完成；约束条件（约束条件（3）说）说明第明第i人只能去完成一人只能去完成一项任务。项任务。极极小小问问题题08级级本本科科适适用用6-4 指派问题指派问题n n 指派问题是指派问题是指派问题是指派问题是0101规划的特例，也是运输问题规划的特例，也是运输问题规划的特例，也是运输问题规划的特例，

40、也是运输问题的特例。即可以用的特例。即可以用的特例。即可以用的特例。即可以用0101规划又可以用运输问题的规划又可以用运输问题的规划又可以用运输问题的规划又可以用运输问题的求解方法。求解方法。求解方法。求解方法。n n 这样做是不合算的。根据指派问题的特殊结这样做是不合算的。根据指派问题的特殊结这样做是不合算的。根据指派问题的特殊结这样做是不合算的。根据指派问题的特殊结构，我们有更为简便的方法，即匈牙利法（匈牙构，我们有更为简便的方法，即匈牙利法（匈牙构，我们有更为简便的方法，即匈牙利法（匈牙构，我们有更为简便的方法，即匈牙利法（匈牙利人康尼格利人康尼格利人康尼格利人康尼格D.KoningD.

41、Koning发明）。发明）。发明）。发明）。n n指派问题的最优解性质：指派问题的最优解性质：指派问题的最优解性质：指派问题的最优解性质：n n如果将指派问题的效率矩阵如果将指派问题的效率矩阵如果将指派问题的效率矩阵如果将指派问题的效率矩阵 C C ij ij 的每一行（列）的每一行（列）的每一行（列）的每一行（列）的各元素都减去该行（列）的最小元素，得到一的各元素都减去该行（列）的最小元素，得到一的各元素都减去该行（列）的最小元素，得到一的各元素都减去该行（列）的最小元素，得到一个新的矩阵个新的矩阵个新的矩阵个新的矩阵b b ij ij ，n n 那么以（那么以（那么以（那么以（ b b i

42、j ij ）为系数矩阵求得的最优解和）为系数矩阵求得的最优解和）为系数矩阵求得的最优解和）为系数矩阵求得的最优解和原问题相同。原问题相同。原问题相同。原问题相同。08级级本本科科适适用用6-4 指派问题指派问题n n 利用前述性质，可使原系数矩阵变为含有很利用前述性质，可使原系数矩阵变为含有很利用前述性质，可使原系数矩阵变为含有很利用前述性质，可使原系数矩阵变为含有很多个多个多个多个0 0元素的新系数矩阵，而最优解保持不变。元素的新系数矩阵，而最优解保持不变。元素的新系数矩阵，而最优解保持不变。元素的新系数矩阵，而最优解保持不变。n n 如果能在新的效率矩阵中找到如果能在新的效率矩阵中找到如果

43、能在新的效率矩阵中找到如果能在新的效率矩阵中找到n n个不同行的个不同行的个不同行的个不同行的且不同列的零元素；且不同列的零元素；且不同列的零元素；且不同列的零元素；则令解矩阵则令解矩阵则令解矩阵则令解矩阵 X X ij ij 中对应的几中对应的几中对应的几中对应的几个独立的零元素的元素取值为个独立的零元素的元素取值为个独立的零元素的元素取值为个独立的零元素的元素取值为1 1，其它元素为，其它元素为，其它元素为，其它元素为0 0。n n将其代入目标函数得：将其代入目标函数得：将其代入目标函数得：将其代入目标函数得：Z Zb b ，它一定是最小。，它一定是最小。，它一定是最小。，它一定是最小。n

44、 n这就是以这就是以这就是以这就是以 b b ij ij为系数矩阵的指派问题的最优解。也为系数矩阵的指派问题的最优解。也为系数矩阵的指派问题的最优解。也为系数矩阵的指派问题的最优解。也就得到了原问题的最优解。就得到了原问题的最优解。就得到了原问题的最优解。就得到了原问题的最优解。n n下面以书中例题来说明指派问题的解法：下面以书中例题来说明指派问题的解法：下面以书中例题来说明指派问题的解法：下面以书中例题来说明指派问题的解法： 08级级本本科科适适用用6-4 指派问题指派问题n n第一步：变换效率矩阵，使各行各列都出现第一步：变换效率矩阵，使各行各列都出现第一步：变换效率矩阵，使各行各列都出现

45、第一步：变换效率矩阵，使各行各列都出现0 0元素：元素：元素：元素：（1 1）效率矩阵每一行都减该行的最小元素；）效率矩阵每一行都减该行的最小元素；）效率矩阵每一行都减该行的最小元素；）效率矩阵每一行都减该行的最小元素；n n （2 2）效率矩阵每列都减该列最小元素。）效率矩阵每列都减该列最小元素。）效率矩阵每列都减该列最小元素。）效率矩阵每列都减该列最小元素。n n第二步：试指派，即找出不同行且不同列的第二步：试指派，即找出不同行且不同列的第二步：试指派，即找出不同行且不同列的第二步：试指派，即找出不同行且不同列的0 0元素：元素：元素：元素：n n （1 1）给只有一个）给只有一个）给只有

46、一个）给只有一个0 0元素的行中的元素的行中的元素的行中的元素的行中的0 0画上圈，记作画上圈，记作画上圈，记作画上圈，记作0 0，n n并划去与其同列的其余并划去与其同列的其余并划去与其同列的其余并划去与其同列的其余0 0元素（元素（元素（元素（行搜索行搜索行搜索行搜索）记作）记作）记作）记作；n n （2 2）给只有一个）给只有一个）给只有一个）给只有一个0 0元素的列中画元素的列中画元素的列中画元素的列中画0 0，并划去与其同，并划去与其同，并划去与其同，并划去与其同行的其余行的其余行的其余行的其余0 0元素，记作元素，记作元素，记作元素，记作；（；（；（；（列搜索）列搜索）列搜索）列搜

47、索）n n （3 3）反复进行（）反复进行（）反复进行（）反复进行（1 1）、（）、（）、（）、（2 2），直至所有的），直至所有的），直至所有的），直至所有的0 0都被圈都被圈都被圈都被圈出为止；出为止；出为止；出为止； 08级级本本科科适适用用6-4 指派问题指派问题n n （4 4）若仍有没有画圈的）若仍有没有画圈的）若仍有没有画圈的）若仍有没有画圈的0 0元素，且同行（列）的元素，且同行（列）的元素，且同行（列）的元素，且同行（列）的0 0元素至少元素至少元素至少元素至少有两个（表示对这人可以从两项任务中指派其一），这可用有两个（表示对这人可以从两项任务中指派其一），这可用有两个（表示

48、对这人可以从两项任务中指派其一），这可用有两个（表示对这人可以从两项任务中指派其一），这可用不同方案去试探。不同方案去试探。不同方案去试探。不同方案去试探。n n 从剩余的从剩余的从剩余的从剩余的0 0元素最少的行（列）开始，比较这行各元素最少的行（列）开始，比较这行各元素最少的行（列）开始，比较这行各元素最少的行（列）开始，比较这行各0 0元素元素元素元素加圈的数目，选择加圈的数目，选择加圈的数目，选择加圈的数目，选择0 0元素少的那列（行）的这个元素少的那列（行）的这个元素少的那列（行）的这个元素少的那列（行）的这个0 0元素加圈元素加圈元素加圈元素加圈（表示选择性多的要礼让选择性少的）。

49、（表示选择性多的要礼让选择性少的）。（表示选择性多的要礼让选择性少的）。（表示选择性多的要礼让选择性少的）。n n然后，划掉同行同列的其它然后，划掉同行同列的其它然后，划掉同行同列的其它然后，划掉同行同列的其它0 0元素，反复进行，直到所有元素，反复进行，直到所有元素，反复进行，直到所有元素，反复进行，直到所有0 0元元元元素都已被圈出为止。素都已被圈出为止。素都已被圈出为止。素都已被圈出为止。n n （5 5）若）若）若）若0 0元素的数目元素的数目元素的数目元素的数目mm等于矩阵的阶数等于矩阵的阶数等于矩阵的阶数等于矩阵的阶数n n，那么该指派问题，那么该指派问题，那么该指派问题，那么该指

50、派问题的最优解已经找到，若的最优解已经找到，若的最优解已经找到，若的最优解已经找到，若mnmn，转下一步。，转下一步。，转下一步。，转下一步。08级级本本科科适适用用6-4 指派问题指派问题n n第三步：用最少直线覆盖效率矩阵中的第三步：用最少直线覆盖效率矩阵中的第三步：用最少直线覆盖效率矩阵中的第三步：用最少直线覆盖效率矩阵中的0 0元素：元素：元素：元素：n n （1 1）对没有）对没有）对没有）对没有0 0圈的行打圈的行打圈的行打圈的行打“”“”；n n （2 2）对已打）对已打）对已打）对已打“”“”的行中的的行中的的行中的的行中的0 0元素所在列打元素所在列打元素所在列打元素所在列打

51、“”“”；n n （3 3）对打）对打）对打）对打“”“”列中的列中的列中的列中的“ “0”0”所在行打所在行打所在行打所在行打“”“”；n n （4 4）重复、直至打不出新的）重复、直至打不出新的）重复、直至打不出新的）重复、直至打不出新的“”“”；n n （5 5）对没有打）对没有打）对没有打）对没有打“”“”的行画一横线，对打的行画一横线，对打的行画一横线，对打的行画一横线，对打“”“”的列画垂线的列画垂线的列画垂线的列画垂线。n n则效率矩阵中所有则效率矩阵中所有则效率矩阵中所有则效率矩阵中所有0 0元素被这些直线所覆盖。元素被这些直线所覆盖。元素被这些直线所覆盖。元素被这些直线所覆盖

52、。08级级本本科科适适用用6-4 指派问题指派问题n n第四步：调整效率矩阵，使出现新的第四步：调整效率矩阵，使出现新的第四步：调整效率矩阵，使出现新的第四步：调整效率矩阵，使出现新的0 0元素：元素：元素：元素：n n （1 1）找出未被划去的元素中最小元素，以其作）找出未被划去的元素中最小元素，以其作）找出未被划去的元素中最小元素，以其作）找出未被划去的元素中最小元素，以其作为调整量为调整量为调整量为调整量 ；n n （2 2）矩阵中打）矩阵中打）矩阵中打）矩阵中打“”“”的行各元素（不包括的行各元素（不包括的行各元素（不包括的行各元素（不包括0 0和和和和）都减）都减）都减）都减 ，n

53、n打打打打“”“”列元素都加上列元素都加上列元素都加上列元素都加上 。然后，去掉所有标。然后，去掉所有标。然后，去掉所有标。然后，去掉所有标记，记，记，记，转第二步。转第二步。转第二步。转第二步。08级级本本科科适适用用6-4 指派问题指派问题n n例例例例2 2：（见效率矩阵）按上述步骤计算如下：（见效率矩阵）按上述步骤计算如下：（见效率矩阵）按上述步骤计算如下：（见效率矩阵）按上述步骤计算如下： 由于由于m=n=4，所以得最优，所以得最优这表示：安排由甲译俄文、这表示：安排由甲译俄文、乙译日文、丙译英文、丁译乙译日文、丙译英文、丁译德文，所需总时间最少为：德文，所需总时间最少为： 为所求为

54、所求 每行都减去该行最小元素每行都减去该行最小元素每列都减去该列最小元素每列都减去该列最小元素试指派：给只有一个零元素试指派：给只有一个零元素的行的零元素划圈，并给其的行的零元素划圈，并给其同列的零元素划同列的零元素划试指派：给只有一个零元素试指派：给只有一个零元素的列的零元素划圈，并给其的列的零元素划圈，并给其同行的零元素划同行的零元素划划圈的零元素所在位置指派划圈的零元素所在位置指派为为1，其余位置为零，其余位置为零08级级本本科科适适用用6-4 指派问题指派问题n n例例例例3 3：求下表中所示效率矩阵的指派问题的最优解：求下表中所示效率矩阵的指派问题的最优解：求下表中所示效率矩阵的指派

55、问题的最优解：求下表中所示效率矩阵的指派问题的最优解： ABCDE甲甲127979乙乙89666丙丙71712149丁丁15146610戊戊4107109任务任务人员人员08级级本本科科适适用用6-4 指派问题指派问题 ，所以还没有解完，按第三步进行：，所以还没有解完，按第三步进行：1 1）对没有圈对没有圈0 0的行打的行打“”；2 2）对已打）对已打“”的行中的的行中的0 0元素所在列打元素所在列打“”；3 3）对打）对打“”列中的列中的“0 0”所在行打所在行打“”；4 4） 重复直至打不出新的重复直至打不出新的“”；5 5）对没有打）对没有打“”的行画一横线，对打的行画一横线，对打“”的

56、列画垂线。的列画垂线。 每一行都减该行的最小元素；每一行都减该行的最小元素；每一行都减该行的最小元素；每一行都减该行的最小元素；解解每一列都减该列的最小元素；每一列都减该列的最小元素；每一列都减该列的最小元素；每一列都减该列的最小元素；由于每一列都已经有零元素，不用再计算由于每一列都已经有零元素，不用再计算由于每一列都已经有零元素，不用再计算由于每一列都已经有零元素，不用再计算先进行搜索，即对只有一个零元素的行的零元素画圈先进行搜索，即对只有一个零元素的行的零元素画圈先进行搜索，即对只有一个零元素的行的零元素画圈先进行搜索，即对只有一个零元素的行的零元素画圈进行列搜索，即对只有一个零元素的列的

57、零元素画圈进行列搜索，即对只有一个零元素的列的零元素画圈进行列搜索，即对只有一个零元素的列的零元素画圈进行列搜索，即对只有一个零元素的列的零元素画圈08级级本本科科适适用用6-4 指派问题指派问题在没有被直在没有被直线所覆盖的元素中找出最小元素（所覆盖的元素中找出最小元素（2）对没有打没有打“”的各行元素分的各行元素分别减减2 2，（，（“0 0”除外）除外）给打打“”的列各元素分的列各元素分别加上加上2 2，（“0 0”除外）除外）得到新得到新阵（* *）后，并按照前述第二步）后，并按照前述第二步继续：08级级本本科科适适用用6-4 指派问题指派问题m=n=5具有具有n个独立的个独立的0元素

58、，这就得到了最优元素，这就得到了最优解，画出相应解矩阵，由解矩阵得最优指派方案：解，画出相应解矩阵，由解矩阵得最优指派方案：甲甲B、乙、乙C、丙、丙E、丁、丁D、戊、戊A所需所需总时间为： 试指派：行搜索试指派：行搜索试指派：列搜索试指派：列搜索重复行、列搜索重复行、列搜索对剩下的对剩下的对剩下的对剩下的“ “0”0”元素，选择元素，选择元素，选择元素，选择“ “0”0”最少的行或列中的最少的行或列中的最少的行或列中的最少的行或列中的“ “0”0”划圈，表示选择性多的礼让少的。划圈，表示选择性多的礼让少的。划圈，表示选择性多的礼让少的。划圈，表示选择性多的礼让少的。本题有多重解本题有多重解08

59、级级本本科科适适用用6-4 指派问题指派问题n n从以上讨论限于极小化问题，对极大化问题，从以上讨论限于极小化问题，对极大化问题，从以上讨论限于极小化问题，对极大化问题，从以上讨论限于极小化问题，对极大化问题，n n n n（其中（其中（其中（其中MM是足够大的常数，通常选是足够大的常数，通常选是足够大的常数，通常选是足够大的常数，通常选C C ij ij 中最大的元中最大的元中最大的元中最大的元素素素素=M=M即可）。即可）。即可）。即可）。n n这时，系数矩阵变为：这时，系数矩阵变为：这时，系数矩阵变为：这时，系数矩阵变为：n n 即求：即求：即求：即求： 可令：可令：可令：可令：08级级本本科科适适用用6-4 指派问题指派问题n n前述变换后，符合匈牙利法的条件，目标函数经变前述变换后，符合匈牙利法的条件，目标函数经变前述变换后，符合匈牙利法的条件，目标函数经变前述变换后，符合匈牙利法的条件，目标函数经变换后，即解换后，即解换后，即解换后，即解 因为因为n M 为常数，所以当为常数，所以当 取最小值时，取最小值时， 便为最大。便为最大。