第七章整数规划模型精选文档.ppt

《第七章整数规划模型精选文档.ppt》由会员分享，可在线阅读，更多相关《第七章整数规划模型精选文档.ppt（68页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章整数规划模型本讲稿第一页，共六十八页第七章 整数规划模型 整数规划模型在实践中有广泛的应用背景，例如著名的指派模型、背包模型、旅行售货员模型、排序模型以及地理六章中的截料模型等都是整数规划模型。整数规划模型（Integer Programming，简记IP）是一类要求变量为整数的规划模型。自从高莫瑞（R.E.Gomory）在1958年提出割平面法以后，整数规划才逐步成为一个独立的理论分支。将目标函数为线性函数，约束条件均为线性等式或不等式的整数规划模型称为整数线性规划模型（ILP），否则称为整数非线性规划模型（INLP）两类。若要求全部变量都去整数值，则称为纯整数规划模型（Pure IP

2、）或全整数规划模型（All IP）；若只要求一部分变量取整数值，则称为混合整数规划模型（Mixed IP）；若要求全部或部分变量只取0或1值。则称为0-1规划。由于整数非线性规划尚无一般解法，因此本文仅考虑整数线性规划模型及其解法，下文所提及的整数规划专指整数线性规划。本讲稿第二页，共六十八页1 整数规划模型及穷举法 一、整数规划模型 建立整数规划模型的过程也与建立线性规划模型一样，有“设立决策变量”、“明确决策目标函数”和“寻找限制条件”三个过程。例一（投资模型）某工厂有资金13万元，用于购置新机器，可在A、B两种机器中任意选购。已知机器A、B的购置费每台分别为2万元和4万元。该厂维修能力只

3、能修7台机器B；若维修机器A，1台折算B为2台。已知1台机器A可增加产值6万元，1台B可增加产值4万元，问应购置机器A和B各多少台，才能使产值增加最多？解 设购买机器A和B的台数分别为 台，则模型为：本讲稿第三页，共六十八页用LINDO软件解的程序为：本讲稿第四页，共六十八页 答案为：最优决策变量 目标函数最优值为22。（跳跃式成本模型）设两种产品A和B每公斤价格为10元和7元，每公斤需要的加工工时为6小时和4小时，成本和工时的关系如图7.1所示，要求建立一整数规划模型，是利润最大。解 设两种产品的产量分别为 公斤，设工时在2000以内为第一范围，2000到3000小时为第二范围，3000到5

4、000小时为第三范围。再设当工时在第j范围内时，（j=1，2，3）。则模型为：本讲稿第五页，共六十八页图7.1本讲稿第六页，共六十八页用LINDO软件解的程序为：本讲稿第七页，共六十八页二、穷举法 穷举法尽管往往不是有效的和常用的方法，但却是最自然想到和直观的方法，而对有些模型却是无可奈何的方法。有时通过对穷举法的研究，往往能够得到启发而产生新的方法。满足整数规划模型所有约束条件的可行解的集合，很多情况下是有限集合，这为穷举法的应用提供了可能。下面用穷举法求一个只有两个变量的整数规划模型的最优解。本讲稿第八页，共六十八页 例3 用穷举法求例1中的整数规划模型的最优解：max Z=s.t.为整数

5、 解 图7.2给出了可行解的集合，共有十二个整数点（即对应到可行解），得整数规划的最优解 最优值 。即A，B两种机器分别购买3台和1台，产值最多增加22万元。本讲稿第九页，共六十八页11 0 2 2 3 3 4 5 （2.5，2）图7.2 整数规划模型与线性规划模型不同之处只在于增加了整数约束。不考虑整数约束得到的线性规划称为整数规划的线性松弛。第六章讲述了用图解法球线性规划模型的解，能否用它的线性松弛模型的最优解痉过去整或四舍五入本讲稿第十页，共六十八页 得到整数规划模型的最优解呢？在上例中整数规划模型的最优解 ，线性松弛模型的最优解为 ，四舍五入得 ，不是不是可行解，自然也不是最优解；若将

6、 取整得 ，虽然是可行解，但它不是最优解。由此可见，刚刚的设想是行不通的，事实上整数规划模型的求解是难题，至今还没有有效的算法（即多项式算法）。割平面法和分支定界法一、割平面法 整数规划模型的割平面法由高莫瑞首创，称为高莫瑞割平面法（Gomory Cutting Plane Algorithm），以区别于后来其他割平面法。在整数规划模型中，去掉了本讲稿第十一页，共六十八页 变量为整数的约束条件之后的模型称为原整数规划得像性松弛模型。高莫瑞割平面法的基本思想是在整数规划的线性松弛模型中逐次增加一个新约束（即割平面），它能割去圆松弛可行域中一块不含整数解的区域。逐次切割下去，直到切割最终得到松弛可

7、行域的一个最优顶点即整数解为止。我们用例4结合图形来说明高莫瑞割平面法的思想及过程：例4 用割平面法求下面的整数规划模型的最优解：为整数本讲稿第十二页，共六十八页 解 图7.3作出了整数规划的线性松弛模型（记为）的可行解，其最优解为 ，增加新的约束条件：得新模型 ，图7.4给出了 的最优解为 。本讲稿第十三页，共六十八页0 1 1 2 2 3 3 4 5 0 1 1 2 2 3 3 4 5 图7.3 图7.4本讲稿第十四页，共六十八页 此时 ，已经满足整数要求，但 还不是整数，还需要增加新的约束条件：得新模型（），图7.5给出了 的最优解为 ，已得原整数规划模型的最优解 ，易计算出最优值为55

8、。本讲稿第十五页，共六十八页1 1 2 2 3 3 4 5 图7.50 新增加的约束条件必须满足下列两个条件：（1）不能割去满足条件的整数点（即整数可行解）。新的割平面的加入，使得可行解区域逐渐减小，割去的区域不能有整数可行解。（2）必须将前一次的最优解割去。将原整数规划模型的本讲稿第十六页，共六十八页 最优解逐步暴露在可行解区域的顶点上。割平面构造原理涉及到对偶单纯形法，在此不多加介绍。割平面法有很重要的理论意义，但在实际计算中没有分支定界效率高，且涉及到对分数的处理，因此几乎没有给予割平面法的软件。二、分支定界法 分支定界法的基本思想是根据某种规则将原整数规划模型的可行域分解为越来越小的子

9、区域，并检查某各子区域内整数解的情况，直到找到最优的整数解或证明整数解不存在。根据整数规划模型性质的不同，存在许多的分支界定法以及分支界定的技巧，在此只对分支界定的一般原理作一简单的介绍。在介绍具体算法之前，以下几个重要的实事是容易理解的：本讲稿第十七页，共六十八页 （1）如果求解一个整数规划的线性松弛模型时得到一个整数解，这个解一定也是整数规划模型的最优解。然而，求解实际模型时这种概率很小。（2）如果得到的解不是一个整数解，则最优整数解的目标值一定不会好于得到的线性松弛模型的最优解。因此线性松弛模型的最优解是整数规划模型最优值的一个界（对最大化模型为上界，对最小化模型为下界）。（3）如果在求

10、解过程中已经找到一个整数解，则最优整数解一定不会劣于该整数解。因此它也是最优整数解的一个界（对最大化模型为下界，对最小化模型为上界）。如果用 表示线性松弛模型的最优值，用 表示已找到的最好整数解的目标值，为原整数规划本讲稿第十八页，共六十八页 模型的最优值，表示下界，表示上界，则最优值一定满足以下关系 ：（对最大化模型 ）(对最小化模型)分支 定界法定界法思想就是不断降低上界，提高下界最后使得下界等于上界，就可以搜索到最优整数解。分支定界法从求解线性松弛模型开始，将线性松弛模型的可行分成许多小的子区域，这一过程称为分支；通过分支和找到更好的整数解来不断修改模型的上下界，这一过程称为定界，这就是

11、分支定界法的由来。以下对分支定界法的基本步骤进行简单的讨论（假定模型求极大值）。1.对给定的整数规划模型，放松整数约束，求解它的线性松弛模型的最优解，如果得到解释整数解，该解即为整数规划模型的最优解。否则，所得到的最优值可作为该本讲稿第十九页，共六十八页 模型最优值的初始上界。最初下界一般认为负无穷。2.从任何一个模型或子模型中不满足整数要求的变量中选出一个进行分支处理。分支通过假如一对互斥的约束将一个（子）模型分解为两个受到更多约束的子模型，并强迫不为整数的变量进一步逼近整数值。例如，如果选中的变量 =q，q的整数部分为k，则在一个子模型中增加约束为 ，在另一个子模型中增加的约束为 。分支过

12、程砍掉了在 和 之间的非整数区域，缩小了搜索的区域。每个子模型都是一个线性规划模型，如果它的最优解不满足整数要求，对该模型还必须继续向下进行分支，所有分支可以形成一个树形图。树形图上面为线性松弛模型，它有两个分支，每个分支又会有两个分支，焚之可以继续进行下去，直到找到一个有整数本讲稿第二十页，共六十八页 最优解的分支或该分支不可行时为止。3.通过不断的分支和求解各个子模型的最最优解，不断修正最优值的上下界。上界通常由各分支最优值的最小值决定，下届则由已经能够找到的最好的整数解的目标值决定。求解任何一个子模型都有以下四种可能的结果：（1）子模型无可行解，此时无续向下继续分支。（2）子模型的最优解

13、满足原整数规划模型变量整数约束，则不必向下继续分支。如果该整数解是目前得到的最好的整数解，则被记录下来，并用它的值作为新的下届。（3）子模型的最优值介于目前所得到的上下界之外，则无需继续向下进行分支。（4）最优解不满足原整数规划模型变量整数约束，最优值介于所得到的上下界之间，则该模型才有本讲稿第二十一页，共六十八页 继续向下搜索的必要。4.直到每一个子模型均无需继续向下分支时，整数规划模型的最优解才找到。下面以例5用分支定界法求整数规划模型最优解的过程。例5 用分支定界法求下列整数规划模型：为整数本讲稿第二十二页，共六十八页 解 求解该模型的线性松弛模型（记为 ），得到最优值 =5.545，最

14、优解为 =1.477，=4.068（该模型可用线性规划的图解法，若多于两个变量，可用LINDO或MATLAB求解）。因为该模型失球最大化模型，整数规划模型的最优值不可能大于 ，也不可能小于负无穷，所以可令上界 =5.545，下届 。本讲稿第二十三页，共六十八页 由于两个变量都不是整数，我们可以从中选择一个变量进行分支，假定选 ，要求 变为整数，因此希望 或者小于等于1，或者大于等于2。分支后形成两个子模型，子模型1增加约束 ，子模型2增加约束 。（子模型1）本讲稿第二十四页，共六十八页(子模型2)子模型1的最优值为 =5.333，最优解为 =1，=4.333。该解还不是整数解，还应继续分支。由

15、于子模型1中只有 取值不是整数，应对 进行分支。分支后又形成两个子模型3和4。子模型3是由子模型1架上约束 形成的，子模型4页是由子模型1加上约束 构成的。本讲稿第二十五页，共六十八页(子模型3)(子模型4)本讲稿第二十六页，共六十八页 子模型3的最优值为 =5，最优解为 =1，=4，该解已经是整数解。所以子模型3无需向下继续分支，且新的下届可以计算如下：子模型4无可行解，所以子模型4也无需继续向下分支。子模型2的最优值为 =4.5，最优解为 =2，=2.5。此时最优值已小于下届5，故也无需继续向下分支。整数规划模型的最优解已经找到，=1，=4，最优值为5。为了清晰的描述求解的全过程，我们作出

16、个子模型关系的树形图（图7.6）本讲稿第二十七页，共六十八页松弛模型 子模型1 子模型2 子模型3 子模型4无可行解 本讲稿第二十八页，共六十八页 三、两辆铁路平板车的装货问题 这是1988年美国数模竞赛的B题，问题如下：有七种规格的包装箱 要装到两辆平板车上去。包装箱的宽和高是一样的，但厚度t（以厘米计）及重量w(以千克计）是不同的。下表给出了每种包装箱的厚度，重量以及数量。每辆平板车有10.2米长的地方可用来装包装箱（像面包片一样），载重为40吨。由于地区货运的限制，对 类包装箱的总数有一个特别的限制：这三类箱子所占的总空间（厚度）不能超过302.7厘米。包装箱类型t（厘米）48.752.

17、061.372.048.752.064.0w（千克）200030001000500400020001000件数8796648 本讲稿第二十九页，共六十八页 问题要求：设计一种装车方案，使剩余的空间最小。下面介绍一种解法。1.问题的假设。包装箱不能能分割成较小的部分。10.2m图7.7本讲稿第三十页，共六十八页 所有的数据均是精确值，无任何测量误差。给出的解，均可进行实际操作（装卸）。2.模型的建立 以 表示装到第j（j=1，2）辆铁路平板车上的 类包装箱的个数（1i 7）；表示类型为 的包装箱的总件数；表示类型为 的包装箱每件重量；表示类型为 的包装箱每件厚度；S表示剩余的空间。我们的目的是使

18、装车剩下的空间最小。为此我们的模型为 本讲稿第三十一页，共六十八页st(平板车1的长度限制)(平板车2的长度限制)(平板车1的载重量限制)(平板车2的载重量限制 )(类包装箱的件数限制)（对 、三种型号包装箱长度的特别限制）为整数 本讲稿第三十二页，共六十八页 对上述整数线性规划问题，用分支定界法可以求得30个不同的解如下（没有利用的空间为0.6cm）箱子类型12345671234 56743533004443 03042912004505 13042533104543 02041912104605 12041533204643 01040912204705 11040533304743 00

19、0平板车1平板车2本讲稿第三十三页，共六十八页箱子类型1 2 3 4 5 6 71 2 3 4 5 6 73 7 4 3 1 0 05 0 5 3 2 3 03 7 0 5 2 1 05 0 9 1 1 2 03 6 4 3 1 1 05 1 5 3 2 2 03 6 0 5 2 2 05 1 9 1 1 1 03 5 4 3 1 2 05 2 5 3 2 1 03 5 0 5 2 3 05 2 9 1 1 0 03 4 4 3 1 3 05 3 5 3 2 0 03 2 9 1 3 0 05 5 0 5 0 3 03 1 9 1 3 1 05 6 0 5 0 2 03 0 9 1 3 2 0

20、5 7 0 5 0 1 0平板车1平板车2本讲稿第三十四页，共六十八页平板车1平板车2箱子类型1234567123456727432006053130264321061531202543220625311025053306291000244323063531001643310715302015433207253010144333073530000790020800631007640008032330069003081063000664010813232005640208232310本讲稿第三十五页，共六十八页 3.模型的分析 现在，我们分析求得的解是否是最优解？考虑 、三种类型的箱子，它们有如

21、下特别限制：、类箱子的件数限制为 （），记 ，并把已知的 与 （）代入，我们有 为整数 本讲稿第三十六页，共六十八页 这个问题的解共有315个，其中使的最小值介于292.2，302.7的解有6个，列表如下：330302.1cm420298.8cm023296.0cm510295.5cm113292.7cm600292.2cm本讲稿第三十七页，共六十八页 可以看出对类型为 、三种类型的包装箱，在所占空间（厚度）不能超过320.7cm的限制下，两辆平板车只能装运302.1cm宽度的包装箱。此时 类型和 类型的包装箱各装3只，不装 类型的包装箱。由 两辆平板车装运 、四种类型的包装箱的空间厚度为17

22、37.3cm。从而总的装运空间的厚度最多为 302.1+1737.3=2039.4（cm）因此，装运的剩余空间至少为 2040-2039.4=0.6（cm）因此，我们求得的30个解均为最优解。如果我们进一步要求这两辆车装运包装箱后，使得剩余空间相同，此时的解即为如下两个解：本讲稿第三十八页，共六十八页 注意到，最优解不装运 类箱子。现在，如果我们进一步要求每一种类型的包装箱都必须装运一部分，从表中可以看出此时两辆平板车装运的 类型包装箱的只数分别为8、7、9、6、1、1、3。此时装完两辆平板车后，剩余的空间至少为 2024-（292.7+1737.3）=10（cm）。平板车厚度重量第一辆101

23、19.7340000790020第二辆10119.7330008006310第一辆10119.7330000690030第二辆10119.7340008106300本讲稿第三十九页，共六十八页 我们现在的目标函数是使平板车上没有利用的空间最少，当然也可以把目标函数定义为两辆平板车装运的包装箱的总重量最大，此时得到的解也将不同。3 0-1规划及隐枚举法 只取0或1值的变量称为0-1变量。在实际生活中许多情况下的状态仅有两种，比如“开、关”，“上、下”，“投资该项目与不投资该项目”等等，通常要用到这种形式的变量来表示。将含有0-1变量的线性规划称为0-1规划。首先建立两个0-1规划模型。例6（装箱

24、模型）某运输公司打算用一个在重30吨重的货物集装箱装运一批货物。这些货物的有关数据由下表给出。试问硬装哪几件货物，才能使获利最多？本讲稿第四十页，共六十八页 解 当集装箱不装第i件货物时，令 =0，否则令 =1（i=1、2、3、4、5）。于是该模型为：货物编号12345重量（吨）20181654利润（百元）303520105s.t.=0或1（j=1、2、3、4、5）本讲稿第四十一页，共六十八页 例7 (投资模型)某公司拟在市东、西、南三区建立市部。拟议中7个位置 （i=17）可供选择：在东区，由 ，三个点中至多选两个；在西区，由 ，两个点中之少选一个；在南区，由 ，两个点中之少选一个；如果选用

25、 点，设备投资估计为 元，每年可获利润为 元，但投资总额不能超过B元。问应该选哪几个点可使年利润为最大？解 当选 点时，令 ，否则令 （i=17）。则模型为：本讲稿第四十二页，共六十八页 0-1规划是整数规划的特殊情况，可用前面介绍的方法求解，但有其变量取值的特性，它另有一种特殊的分值定界法隐枚举法，它也是通过求解线性松弛模型来获得原整数规划模型的最优解的，不过这里恰好跟一般分值定界相反，是由放弃所有线性约束、只保留变量0-1约束而得到的。下面具体说明这种方法。隐枚举法要求0-1规划为下述标准形式：或本讲稿第四十三页，共六十八页 其中，约束条件必须为“”。当某一 时，令 ，则 再令 ，原目标函

26、数变为 从而使目标函数中个变量的系数变为非负数。或本讲稿第四十四页，共六十八页 隐枚举的解法思路与分值定界法有相似之处。利用变量只能取0或1进行分支。首先令全部变量取0值（当求最大值时，令全部变量取1值），检验解是否满足约束条件。若均满足，已得最优解；若不全满足，则令一个变量取值为0或1（此变量称为固定变量），将模型分成两个子模型，其余未被指定取值的变量称为自由变量。由于 ，因此自由变量为0与固定变量组成的子模型的解使目标值最小。经过几次检验后，或停止分支，或者将另一个自由变量转为固定变量，令其值为0或1，继续分支。如此继续进行，直至没有自由变量或全部子模型停止分支为止，就求出最优解。具体算法

27、过程：第一步，将模型化为标准形式。第二步，令全部 都是自由变量，且均取0值，本讲稿第四十五页，共六十八页 检验解是否为可行解（即满足所有约束条件）。若是可行解，则一定为最优解；若不可行，进行第三步。第三步，将某一变量转为固定变量，令其取值为0或1，使该模型（子模型）分成两个子模型。其它变量均为自由变量，仍取0值。第四步，检查已有的子模型，若子模型满足下列条件之一，该子模型停止向下分支，继续检查其它子模型，直到所有子模型均检查完毕，转第五步；若有某一个子模型不满足下列四个条件，则转第三步。1.将自由变量均取0值与固定变量的值一起代入约束方程中，满足所有约束条件，则为可行解，该模型停止向下分支。本

28、讲稿第四十六页，共六十八页 2.若自由变量取任意值时，都不满足某一约束条件，则该子模型无可行解，也停止向下分支。即将子模型固定变量的值代入约束条件方程中，令不等式左端的自由变量当系数为负时取值为1，系数为正时取值为0，得到左端所能取得的最小值，若此最小值大于右端值，说明此子模型无可行解。3.将自由变量均取0值与固定变量的值一起代入目标函数，得到的目标值大于已求得的可行解的目标值，则该子模型一定无更好的可行解，也停止向下分支。4.所有变量均为固定变量，则该子模型停止向下分支。第五步，在所有可行解中目标值最小的解，即为最优解。本讲稿第四十七页，共六十八页 例8求下列0-1规划最优解 解 将原模型记

29、为 ，目标值 ，自由变量全取0值，显然不是可行解。不妨取 作为固定变量，在 中增加约束条件 记为 ，增加 记为 。模型 中 ，其它为自由变量，均取0值，此时 为可行解，停止分支。目标或本讲稿第四十八页，共六十八页 值 ，因此，原模型的最优值的上界为8。模型 不满足算法中停止的条件，需继续分支。将 变为固定变量，于是模型 分为两个分支 和 ，继续考虑 和 。为了清晰的表达求解的过程，我们类似分值定界法，作出树形图（图7.8），图中黑体数字表示该变量为固定变量。最优解为 ，最优值为 。本讲稿第四十九页，共六十八页可行解，停止分支不可行，停止分支图7.8本讲稿第五十页，共六十八页可行解，停止分支不可

30、行，停止分支目标值大于上界6，停止分支图7.8本讲稿第五十一页，共六十八页4 指派模型及匈牙利法 一、指派模型 许多管理部门可能经常面临这样的问题：有若干项任务需要完成，又有若干对象能够完成其中的每项任务。由于每个对象的特点与能力不同，完成各项任务的效益也各不相同。又因任务性质的要求和管理上的要求等，应如何分配人员去完成所有任务，能使完成各项任务的总效益最佳或费用最小？这类问题就称之为指派问题或分配问题。在指派问题中，作如下假设：1.被指派的人数与任务的数目相等，为n。2.每个被指派的人员只完成一个任务，而且每一个任务必有一个人去完成。本讲稿第五十二页，共六十八页 3.第i个被指派的人去完成第

31、j项任务的费用为 。指派问题的模型为 C=（）为n阶方阵，称为指派模型（P）的效益矩阵；若 为（P）的最优解，则n阶方阵 称为（P）的最优解方阵。事实上方阵X为一置换方阵，即该矩阵中的每一行、每一列只有一个“1”。本讲稿第五十三页，共六十八页 二、匈牙利法 解决指派模型的方法是匈牙利数学家考尼格提出的。因此得名匈牙利法。1.匈牙利法基本原理。匈牙利法基于下面两个基本性质：性质1 设一个指派模型的效益矩阵为（）。若（）的第i行元素减去一个常数 （i=1，2，n），第j列元素均减去一个常数 （j=1，2，n），得到一个新的效益矩阵（），其中每一元素 ，则以（）为效益矩阵的最优解也是以（）为效益矩阵

32、的指派模型的最优解。如果取 （i=1，2，n）为第i行元素的最小值，（j=1，2，n）为第j列元素的最小值，则 本讲稿第五十四页，共六十八页 得到一个新的效益矩阵（）为非负矩阵（即所有元素均为非负数）。性质1说明可以通过求以（）为效益矩阵的指派模型的最优解得到原指派模型的最优解。直观地讲，求指派模型的最优解方阵就是在效益矩阵中找到n个元素，要求在不同行、不同列上，使这些元素之和最小。江、将这n个元素所在位置赋值为“1”，其它元素均为“0”，就得到最优解方阵。效益矩阵（）中最小元素为“0”，因此邱指派模型（P）的最优解又转化为在矩阵（）中找出n个在不同行、不同列上的“0”元素，就很容易的、构造出

33、最优解矩阵。性质2 若一方阵中的一部分元素为0，一部分元素为非0，则覆盖方阵内所有0元素的最少直线恰好等于那些位于不同行、不同列上的0元素的最多个数。本讲稿第五十五页，共六十八页 此时存在两个问题：第一，当效益矩阵阶数n较大时，如何得知不存在n个位于不同行、不同列上的0元素，即如何得知覆盖方阵内所有0元素的最少直线数需要几条？第二，赋予实际背景的指派模型，总存在最优解。事实上任意一个指派模型均有最优解。当确切得知不存在n个位于不同行、不同列上的0元素时，如何进一步按性质1构造出新的效益矩阵，其中位于不同行、不同列上的0元素不断增加，直至达到几个？要解决第一个问题，我们需要引入两个定义和一些性质

34、：定义1 矩阵 的积和式perA定义为：本讲稿第五十六页，共六十八页 其中（）取遍（1、2、n）的所有排列。积和式是矩阵的一个重要参数，在组合理论中经常将积和式与其他参数建立联系，它类似于矩阵的行列式，但又有很大的区别。行列式的计算方法有许多，但积和式的计算主要用拉普拉斯展开法，按某行（列）展开，直至到2阶。例如计算下列3阶矩阵的积和式时，按第一行展开，则转化为计算三个2阶矩阵的积和式。本讲稿第五十七页，共六十八页 定义2 称D为C的补矩阵。若 ，满足 性质3 设C为指派模型（P）的效益矩阵，D为C的补矩阵，覆盖C中0元素所需要最小直线数为n的充要条件为 。由性质3得知，当指派模型（P）的效益

35、矩阵或由性质1所得效益矩阵对应的补矩阵D的积和式 时，覆盖效益矩阵内0元素的最小直线数需要n条。因此性质3也可以称为效益矩阵迭代的终止条件。特别要指出的是当迭代终止时，且 性质4 指派模型（P）最优解的个数等于perD。本讲稿第五十八页，共六十八页 对于第二个问题，我们可以按如下的方法处理。当确切得知效益矩阵中不存在n个位于不同行、不同列上的0元素时，一定可以用少于n条直线将所有“0”元素覆盖。在未被直线覆盖的所有元素中，找出最小元素，记为；所有未被直线覆盖的元素都减去；覆盖线十字交叉处元素即同时被两条直线覆盖的元素都加上，其余元素不变。这一过程相当于将效益矩阵的每一行的所有元素均减去，同时将

36、被直线覆盖的行（或列）上的所有元素均加上。由性质1保证最优解矩阵不发生改变，同时在新的效益矩阵中位于不同行、不同列上的0元素个数得到增加。2.匈牙利方法步骤 第一步，从下效益矩阵C的每行减去该行的最小元素，从所得矩阵的每列减去该列的最小元素，得新的效益矩阵B。本讲稿第五十九页，共六十八页 第二步，构造效益矩阵B的补矩阵D，计算perD。第三步，判断perD是否等于0。是则转入下面第五步。第四步，检查 的每行、每列，从中找出“0”元素最少的一排（即行或列），从该排圈出一个“0”元素，若该排有多个“0”元素，则任圈一个，用表示，把刚得到的元素所在行、列划去。在剩下的矩阵中重复上述过程，直至找到n个

37、。将n个所在位置赋值“1”，其它元素赋值为“0”，得到矩阵就是原指派模型的最优解矩阵。第五步，一定可用少于n条直线将效益矩阵B中所有“0”元素覆盖。在未被直线覆盖的所有元素中，找出最小元素；所有未被直线覆盖的元素都减去；覆盖线十字交叉处元素即同时被两条直线覆盖的元素都加上，其余元素不变。得到的效益矩阵仍记为B，回到第二步。本讲稿第六十页，共六十八页 下面我们以例9来说明匈牙利方法。例9 现有5辆货车装货待卸，调度员分配五个装卸组卸货，由于各班技术专长不同，各班组所需时间如下表所示，调度员应如何分配，使所花的总时间最少？装卸组 待卸车4573613584265723563693434本讲稿第六十

38、一页，共六十八页 解 效益矩阵第一步：将C每行元素减去该行的最小元素，得矩阵 将所得矩阵 各列元素减去该列的最小元素，得效益矩阵本讲稿第六十二页，共六十八页 第二步:构造效益矩阵 的补矩阵 ，计算 。（按第一行展开）本讲稿第六十三页，共六十八页 第三步：由于perD等于0，则转第五步。第五步：用四条直线（少于五条）就可以讲效益矩阵 中所有的“0”元素覆盖：4条直线分别覆盖 第三行、第五行、第一行和第四列。在未被直线覆盖的所有元素中，找出最小元素 =2 ；所有未被直线覆盖的元素都减去 ；覆盖线十字交叉处元素都加上 ，其余元素不变。得到的效益矩阵记为 ，回到第二步。本讲稿第六十四页，共六十八页 第

39、二步:构造效益矩阵 的补矩阵 ，计算 。（按第三行展开）（按第一行展开）本讲稿第六十五页，共六十八页 第三步：由于perD不等于0，则转第四步。第四步，检查 的每行、每列，第三行“0”元素最少，只有一个，只能选它，换成表示，在 中把第三行和第五列划去。在剩下的矩阵中重复上述过程，很容易找到5个不同行、不同列中的。将5个所在位置赋值“1”，其它元素赋值为“0”，得到矩阵就是原指派模型的最优解矩阵 。由性质4知该指派模型由四组最优解。另三个最优解矩阵分别为：本讲稿第六十六页，共六十八页 最优解矩阵 对应分配方案：卸 ，卸 ，卸 ，卸 ，卸 。目标值本讲稿第六十七页，共六十八页 Z=5+1+2+3+4=15。通过简单计算，不同的最优解所对应的最优值都为15。本讲稿第六十八页，共六十八页