《运筹学2.ppt》由会员分享，可在线阅读，更多相关《运筹学2.ppt（100页珍藏版）》请在三一文库上搜索。
1、对偶单纯形法,对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。,对偶单纯形法原理,对偶单纯形法基本思路：,找出一个对偶问题的可行基，保持对偶问题为可行解的条件下，判断XB是否可行（XB为非负），若否，通过变换基解，直到找到原问题基可行解（即XB为非负），这时原问题与对偶问题同时达到可行解，由定理4可得最优解。,对偶单纯形法,找出一个DP的可行基,LP是否可行 （XB 0）,保持DP为可行解情况下转移到LP的另一个基本解,最优解,是,否,循 环,结束,对偶单纯形法,例2.9 用对偶单纯形法求解：
2、,解:（1）将模型转化为求最大化问题，约束方程化为等式求出一组基本解，因为对偶问题可行，即全部检验数0（求max问题）。,对偶单纯形法,对偶单纯形法,对偶单纯形法,原问题的最优解为：X*=（2 , 2 , 2 , 0 , 0 , 0），Z* =72 其对偶问题的最优解为：Y*= （1/3 , 3 , 7/3），W*= 72,对偶单纯形法,对偶单纯形法应注意的问题：,用对偶单纯形法求解线性规划是一种求解方法，而不是去求对偶问题的最优解,初始表中一定要满足对偶问题可行，也就是说检验数满足最优判别准则,最小比值中 的绝对值是使得比值非负，在极小化问题j0，分母aij0 这时必须取绝对值。在极大化问题
3、中， j0，分母aij0， 总满足非负，这时绝对值符号不起作用，可以去掉。如在本例中将目标函数写成,这里j 0在求k时就可以不带绝对值符号。,对偶单纯形法,对偶单纯形法与普通单纯形法的换基顺序不一样，普通单纯形法是先确定进基变量后确定出基变量，对偶单纯形法是先确定出基变量后确定进基变量；,普通单纯形法的最小比值是 其目的是保证下一个原问题的基本解可行，对偶单纯形法的最小比值是,其目的是保证下一个对偶问题的基本解可行,对偶单纯形法在确定出基变量时，若不遵循 规则，任选一个小于零的bi对应的基变量出基，不影响计算结果，只是迭代次数可能不一样。,本章小结,学习要点： 1. 线性规划解的概念以及3个基
4、本定理 2. 熟练掌握单纯形法的解题思路及求解步骤,Chapter3 运输规划 ( Transportation Problem ),运输规划问题的数学模型 表上作业法 运输问题的应用,本章主要内容：,运输规划问题的数学模型,例3.1 某公司从两个产地A1、A2将物品运往三个销地B1, B2, B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,运输规划问题的数学模型,解：产销平衡问题：总产量 = 总销量500 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表：,Min C = 6x11+ 4x12+ 6x13+ 6x2
5、1+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij 0 ( i = 1、2；j = 1、2、3）,运输规划问题的数学模型,运输问题的一般形式：产销平衡,A1、 A2、 Am 表示某物资的m个产地； B1、B2、Bn 表示某物质的n个销地；ai 表示产地Ai的产量； bj 表示销地Bj 的销量； cij 表示把物资从产地Ai运往销地Bj的单位运价。设 xij 为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型：,
6、运输规划问题的数学模型,变化： 1）有时目标函数求最大。如求利润最大或营业额最大等； 2）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束)； 3）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。,定理: 设有m个产地n个销地且产销平衡的运输问题，则基变量数为m+n-1。,表上作业法,表上作业法是一种求解运输问题的特殊方法，其实质是单纯形法。,表上作业法,例3.2 某运输资料如下表所示：,问：应如何调运可使总运输费用最小？,表上作业法,解：第1步 求初始方案,方法1：最小元素法 基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最
7、后供完为止。,3,11,3,10,1,9,2,7,4,10,5,8,3,4,1,6,3,3,表上作业法,总的运输费(31)+(64) +(43) +(12)+(310)+(35)=86元,元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案。,15,5,10,总运费是z=108+52+151=105,最小元素法：,表上作业法,5,15,10,总运费z=105+152+51=85,后一种方案考虑到C11与C21之间的差额是82=6，如果不先调运x21，到后来就有可能x110，这样会使总运费增加较
8、大，从而先调运x21，再是x22，其次是x12,用元素差额法求得的基本可行解更接近最优解，所以也称为近似方案。,表上作业法,方法2：Vogel法,1）从运价表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。,3,11,3,10,1,9,2,7,4,10,5,8,表上作业法,2）再从差值最大的行或列中找出最小运价确定供需关系和供需数量。当产地或销地中有一方数量供应完毕或得到满足时，划去运价表中对应的行或列。 重复1)和2)，直到找出初始解为至。,3,11,3,10,1,9,2,7,4,10,5,8,5,表上作业法,7,1,1,3,5,2,1,5,表上作业法,7,1
9、,3,5,2,7,5,3,表上作业法,1,1,3,5,1,5,3,6,3,1,2,该方案的总运费: (13)(46)(35)(210)(18)(35)85元,表上作业法,第2步 最优解的判别（检验数的求法）,求出一组基可行解后，判断是否为最优解，仍然是用检验数来判断，记xij的检验数为ij由第一章知，求最小值的运输问题的最优判别准则是：,所有非基变量的检验数都非负，则运输方案最优,求检验数的方法有两种： 闭回路法 位势法（）,表上作业法,闭回路的概念,为一个闭回路 ，集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边。如下表,表上作业法,例下表中闭回路的变量集合是x11,x12,x42
10、,x43,x23,x25,x35, x31共有8个顶点，这8个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。,一条回路中的顶点数一定是偶数，回路遇到顶点必须转90度与另一顶点连接，表33中的变量x 32及x33不是闭回路的顶点，只是连线的交点。,表上作业法,闭回路,例如变量组 不能构成一条闭回路，但A中包含有闭回路,变量组 变量数是奇数，显然不是闭回路，也不含有闭回路；,表上作业法,用位势法对初始方案进行最优性检验：,1）由ij=Cij-（Ui+Vj）计算位势Ui ， Vj ，因对基变量而言有ij=0，即Cij-（Ui+Vj） = 0，令U1=0,2）再由ij=Cij-（Ui+Vj）计算
11、非基变量的检验数ij,3,11,3,10,1,9,2,7,4,10,5,8,4,3,6,3,1,3,0,-1,-5,3,10,2,9,（1）,（2）,（1）,（-1）,（10）,（12）,当存在非基变量的检验数kl 0，说明现行方案为最优方案，否则目标成本还可以进一步减小。,表上作业法,当存在非基变量的检验数kl 0 且kl =minij时，令Xkl 进基。从表中知可选X24进基。,第3步 确定换入基的变量,第4步 确定换出基的变量,以进基变量xik为起点的闭回路中，标有负号的最小运量作为调整量，对应的基变量为出基变量，并打上“”以示换出作为非基变量。,表上作业法,3,11,3,10,1,9,
12、2,7,4,10,5,8,4,3,6,3,1,3,(),(),(),(),调整步骤为：在进基变量的闭回路中标有正号的变量加上调整量，标有负号的变量减去调整量，其余变量不变，得到一组新的基可行解。然后求所有非基变量的检验数重新检验。,1,2,5,表上作业法,当所有非基变量的检验数均非负时，则当前调运方案即为最优方案，如表此时最小总运费： Z =(13)(46)(35)(210)(18)(35)85元,3,11,3,10,1,9,2,7,4,10,5,8,5,3,6,3,1,2,0,-2,-5,3,10,3,9,（0）,（2）,（2）,（1）,（12）,（9）,表上作业法,表上作业法的计算步骤：,
13、表上作业法,表上作业法计算中的问题：,（1）若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代时，取它们中任一变量为换入变量均可使目标函数值得到改善，但通常取ij0中最小者对应的变量为换入变量。 （2）无穷多最优解 产销平衡的运输问题必定存最优解。如果非基变量的ij0，则该问题有无穷多最优解。,表上作业法, 退化解： 表格中一般要有(m+n-1)个数字格。但有时在分配运量时则需要同时划去一行和一列，这时需要补一个0，以保证有(m+n-1)个数字格作为基变量。一般可在划去的行和列的任意空格处加一个0即可。 利用进基变量的闭回路对解进行调整时，标有负号的最小运量（超过2个最小值）作为调
14、整量，选择任意一个最小运量对应的基变量作为出基变量，并打上“”以示作为非基变量。,表上作业法,12,4,11,4,8,3,10,2,9,5,11,6,(0),(2),(9),(2),(1),(12),8,12,4,2,8,14,如下例中11检验数是 0，经过调整，可得到另一个最优解。,表上作业法,11,4,4,3,1,3,7,7,8,2,10,6,3,4,1,6,0,6,在x12、x22、x33、x34中任选一个变量作为基变量，例如选x34,例：用最小元素法求初始可行解,运输问题的应用,求极大值问题 目标函数求利润最大或营业额最大等问题。,运输问题的应用,求解方法： 将极大化问题转化为极小化问
15、题。设极大化问题的运价表为C ，用一个较大的数M（Mmaxcij）去减每一个cij得到矩阵C，其中C=（Mcij）0,将C作为极小化问题的运价表，用表上用业法求出最优解。,运输问题的应用,例3.3 下列矩阵C是Ai（I=1，2，3）到Bj的吨公里利润,运输部门如何安排运输方案使总利润最大.,运输问题的应用,得到新的最小化运输问题，用表上作业法求解即可。,运输问题的应用,产销不平衡的运输问题 当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。,当产大于销时，即：,数学模型为：,运输问题的应用,由于总产量大于总销量，
16、必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，假设该仓库为一个虚拟销地Bn+1， bn+1作为一个虚设销地Bn+1的销量(即库存量)。各产地Ai到Bn+1的运价为零，即Ci,n+1=0,（i=1，m）。则平衡问题的数学模型为：,具体求解时,只在运价表右端增加一列Bn+1，运价为零,销量为bn+1即可,运输问题的应用,当销大于产时，即：,数学模型为：,由于总销量大于总产量,故一定有些需求地不完全满足,这时虚设一个产地Am+1，产量为：,运输问题的应用,销大于产化为平衡问题的数学模型为 ：,具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为am+1即可。,运输问题
17、的应用,例3.4 求下列表中极小化运输问题的最优解。,因为有：,运输问题的应用,所以是一个产大于销的运输问题。表中A2不可达B1，用一个很大的正数M表示运价C21。虚设一个销量为b5=180-160=20，Ci5=0，i=1,2,3,4，表的右边增添一列 ，得到新的运价表。,运输问题的应用,下表为计算结果。可看出：产地A4还有20个单位没有运出。,运输问题的应用,3. 生产与储存问题,例3.5 某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费
18、用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。,运输问题的应用,解： 设 xij为第 i 季度生产的第 j 季度交货的柴油机数目，那么应满足： 交货： x11 = 10 生产：x11 + x12 + x13 + x14 25 x12 + x22 = 15 x22 + x23 + x24 35 x13 + x23 + x33 = 25 x33 + x34 30 x14 + x24 + x34 + x44 = 20 x44 10,把第 i 季度生产的柴油机数目看作第 i 个生产厂的产量；把第 j 季度交货的柴油机数目看作第 j 个销售点的销量；设cij是第i季度生产
19、的第j季度交货的每台柴油机的实际成本，应该等于该季度单位成本加上储存、维护等费用。可构造下列产销平衡问题：,运输问题的应用,由于产大于销，加上一个虚拟的销地D，化为平衡问题，即可应用表上作业法求解。,运输问题的应用,该问题的数学模型： Min f = 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.25 x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44,运输问题的应用,最优生产决策如下表，最小费用z773万元。,Chapter4 整数规划 ( Integer Programming ),整数规
20、划的特点及应用 分支定界法 分配问题与匈牙利法,本章主要内容：,整数规划的特点及应用,整数规划（简称：IP） 要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若该松弛问题是一个线性规划，则称该整数规划为整数线性规划。,整数线性规划数学模型的一般形式：,整数规划的特点及应用,整数线性规划问题的种类：,纯整数线性规划：指全部决策变量都必须取整数值的整数线性规划。 混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。 0-1型整数线性规划：决策变量只能取值0或1的整数线性
21、规划。,整数规划的特点及应用,整数规划的典型例子,例4.1 工厂A1和A2生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij，见下表：,工厂A3或A4开工后，每年的生产费用估计分别为1200万或1500万元。现要决定应该建设工厂A3还是A4，才能使今后每年的总费用最少。,整数规划的特点及应用,解：这是一个物资运输问题，特点是事先不能确定应该建A3还是A4中哪一个，因而不知道新厂投产后的实际生产物资。为此，引入0-1变量：,再设xij为由Ai运往B
22、j的物资数量，单位为千吨；z表示总费用，单位万元。 则该规划问题的数学模型可以表示为：,整数规划的特点及应用,混合整数规划问题,整数规划的特点及应用,例4.2 现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj（j1,2,n），此外由于种种原因，有三个附加条件： 若选择项目1，就必须同时选择项目2。反之不一定 项目3和4中至少选择一个； 项目5,6,7中恰好选择2个。 应该怎样选择投资项目，才能使总预期收益最大。,整数规划的特点及应用,解：对每个投资项目都有被选择和不被选择两种可能，因此分别用0和1表示，令xj表示第j个项目的决策选择，记为：,投资问题可以表
23、示为：,整数规划的特点及应用,例4.3 指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表所示，如何安排他们的工作使总成绩最好。,整数规划的特点及应用,设,数学模型如下：,要求每人做一项工作，约束条件为：,整数规划的特点及应用,每项工作只能安排一人，约束条件为：,变量约束：,整数规划的特点及应用,整数规划问题解的特征：,整数规划问题的可行解集合是它松弛问题可行解集合的一个子集，任意两个可行解的凸组合不一定满足整数约束条件，因而不一定仍为可行解。 整数规划问题的可行解一定是它的松弛问题的可行解（反之不一定），但其最优解的目标函数值不
24、会优于后者最优解的目标函数值。,整数规划的特点及应用,例4.3 设整数规划问题如下,首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。,整数规划的特点及应用,用图解法求出最优解为：x13/2, x2 = 10/3，且有Z = 29/6,现求整数解(最优解):如用舍入取整法可得到4个点即(1，3),(2，3),(1，4),(2，4)。显然，它们都不可能是整数规划的最优解。,x1,x2,3,3,(3/2,10/3),按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如右图所示。其中(2,2),(3,1)点的目标函数值最大，即为Z=4。
25、,整数规划的特点及应用,整数规划问题的求解方法：,分支定界法和割平面法 匈牙利法（指派问题）,分支定界法,1）求整数规划的松弛问题最优解； 若松弛问题的最优解满足整数要求，得到整数规划的最优解,否则转下一步； 2）分支与定界： 任意选一个非整数解的变量xi，在松弛问题中加上约束： xixi 和 xixi+1 组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界。 检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存在非整数解并
26、且目标值大于(max)整数解的目标值，需要继续分枝，再检查，直到得到最优解。,分支定界法的解题步骤：,分支定界法,例4.4 用分枝定界法求解整数规划问题,解：首先去掉整数约束，变成一般线性规划问题(原整数规划问题的松驰问题),LP,IP,分支定界法,用图解法求松弛问题的最优解，如图所示。,x1,x2,3,(18/11,40/11),2,1,1,2,3,x118/11, x2 =40/11 Z=218/11(19.8) 即Z 也是IP最小值的下限。,对于x118/111.64， 取值x1 1， x1 2 对于x2 =40/11 3.64，取值x2 3 ，x2 4 先将（LP）划分为（LP1）和（
27、LP2）,取x1 1, x1 2,分支定界法,分支：,分别求出（LP1）和（LP2）的最优解。,分支定界法,先求LP1,如图所示。此时在B点取得最优解。 x11, x2 =3, Z(1)16 找到整数解，问题已探明，此枝停止计算。,x1,x2,3,3,(18/11,40/11),1,1,B,A,C,同理求LP2,如图所示。在C 点取得最优解。即: x12, x2 =10/3, Z(2)56/318.7 Z(2) Z(1)16 原问题有比16更小的最优解，但 x2 不是整数，故继续分支。,分支定界法,在IP2中分别再加入条件： x23, x24 得下式两支：,分别求出LP21和LP22的最优解,
28、分支定界法,x1,x2,3,3,(18/11,40/11),1,1,B,A,C,D,先求LP21,如图所示。此时D 在点取得最优解。 即 x112/52.4, x2 =3, Z(21)-87/5-17.4 Z(1)=-16 但x112/5不是整数，可继续分枝。即 3x12。,求LP22，如图所示。无可行解，故不再分枝。,分支定界法,在（LP21）的基础上继续分枝。加入条件3x12有下式：,分别求出（LP211）和（LP212）的最优解,分支定界法,x1,x2,3,3,(18/11,40/11),1,1,B,A,C,D,E,F,先求（LP211）,如图所示。此时 在E点取得最优解。即 x12,
29、x2 =3, Z(211)17 找到整数解，问题已探明，此枝停止计算。,求（LP212），如图所示。此时 F在点取得最优解。即x13, x2 =2.5, Z(212)31/215.5 Z(211) 如对LP212继续分解，其最小值也不会低于15.5 ，问题探明,剪枝。,分支定界法,原整数规划问题的最优解为: x1=2, x2 =3, Z* =17 以上的求解过程可以用一个树形图表示如右：,LP1 x1=1, x2=3 Z(1) 16,LP x1=18/11, x2=40/11 Z(0) 19.8,LP2 x1=2, x2=10/3 Z(2) 18.5,LP21 x1=12/5, x2=3 Z(
30、21) 17.4,LP22 无可 行解,LP211 x1=2, x2=3 Z(211) 17,LP212 x1=3, x2=5/2 Z(212) 15.5,x11,x12,x23,x24,x12,x13,分支定界法,例4.5 用分枝定界法求解,解: 先求对应的松弛问题（记为LP0）,用图解法得到最优解X(3.57,7.14),Z0=35.7,如下图所示。,分支定界法,10,10,松弛问题LP0的最优解X=(3.57,7.14),Z0=35.7,x1,x2,o,A,B,C,分支定界法,10,x2,o,A,B,C,LP1,LP2,3,4,LP1:X=(3,7.6),Z1=34.8,LP2:X=(4
31、,6.5),Z2=35.5,分支定界法,10,x1,x2,o,A,B,C,LP1,LP21,3,4,LP21:X=(4.33,6),Z21=35.33,6,分支定界法,10,x1,x2,o,A,C,LP1,3,4,6,LP211:X=(4,6), Z211=34,LP212:X=(5,5),Z212=35,5,LP212,分支定界法,上述分枝过程可用下图表示：,LP0:X=(3.57,7.14),Z0=35.7,LP1:X=(3,7.6) Z1=34.8,LP2:X=(4,6.5) Z2=35.5,x13,x14,LP21:X=(4.33,6) Z21=35.33,x26,LP211:X=(4
32、,6) Z211=34,LP212:X=(5,5) Z212=35,x14,x15,LP22 无可行解,x27,小结,学习要点： 掌握一般整数规划问题概念及模型结构 掌握分支定界法原理 能够用分支定界法求解一般整数规划问题,课后练习：,分配问题与匈牙利法,指派问题的数学模型的标准形式：,设n 个人被分配去做n 件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第i个人去做第j 件工作的效率（ 时间或费用）为Cij(i=1.2n;j=1.2n)并假设Cij 0。问应如何分配才能使总效率（ 时间或费用）最高？,设决策变量,分配问题与匈牙利法,指派问题的数学模型为：,分配问题与匈牙利法,克
33、尼格定理 : 如果从分配问题效率矩阵aij的每一行元素中分别减去(或加上)一个常数ui，从每一列中分别减去(或加上)一个常数vj，得到一个新的效率矩阵bij，则以bij为效率矩阵的分配问题与以aij为效率矩阵的分配问题具有相同的最优解。,分配问题与匈牙利法,指派问题的求解步骤：,1) 变换指派问题的系数矩阵(cij)为(bij)，使在(bij)的各行各列中都出现0元素，即 从(cij)的每行元素都减去该行的最小元素； 再从所得新系数矩阵的每列元素中减去该列的最小元素。,2) 进行试指派，以寻求最优解。 在(bij)中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵
34、(xij)中的元素为1，其余为0，这就得到最优解。,分配问题与匈牙利法,找独立0元素，常用的步骤为：,从只有一个0元素的行开始，给该行中的0元素加圈，记作 。然后划去 所在列的其它0元素，记作 ；这表示该列所代表的任务已指派完，不必再考虑别人了。依次进行到最后一行。 从只有一个0元素的列开始（画的不计在内），给该列中的0元素加圈，记作；然后划去 所在行的0元素，记作 ，表示此人已有任务，不再为其指派其他任务了。依次进行到最后一列。 若仍有没有划圈的0元素，且同行(列)的0元素至少有两个，比较这行各0元素所在列中0元素的数目，选择0元素少这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后
35、划掉同行同列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止。,分配问题与匈牙利法,若 元素的数目m 等于矩阵的阶数n（即：mn），那么这指派问题的最优解已得到。若m n, 则转入下一步。,3) 用最少的直线通过所有0元素。其方法：,对没有的行打“”； 对已打“” 的行中所有含元素的列打“” ； 再对打有“”的列中含 元素的行打“” ； 重复、直到得不出新的打号的行、列为止； 对没有打号的行画横线，有打号的列画纵线，这就得到覆盖所有0元素的最少直线数 l 。,注：l 应等于m，若不相等，说明试指派过程有误，回到第2步，另行试指派；若 lm n，表示还不能确定最优指派方案，须再变换当前
36、的系数矩阵，以找到n个独立的0元素，为此转第4步。,分配问题与匈牙利法,4) 变换矩阵(bij)以增加0元素 在没有被直线通过的所有元素中找出最小值，没有被直线通过的所有元素减去这个最小元素；直线交点处的元素加上这个最小值。新系数矩阵的最优解和原问题仍相同。转回第2步。,分配问题与匈牙利法,例4.6 有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？,分配问题与匈牙利法,解：1）变换系数矩阵，增加0元素。,5,2）试指派（找独立0元素）,找到 3 个独立零元素
37、但 m = 3 n = 4,分配问题与匈牙利法,3）作最少的直线覆盖所有0元素,独立零元素的个数m等于最少直线数l，即lm=3n=4；,4）没有被直线通过的元素中选择最小值为1，变换系数矩阵，将没有被直线通过的所有元素减去这个最小元素；直线交点处的元素加上这个最小值。得到新的矩阵，重复2）步进行试指派,分配问题与匈牙利法,试指派,得到4个独立零元素， 所以最优解矩阵为：,即完成4个任务的总时间最少为：241+8=15,分配问题与匈牙利法,例4.7 已知四人分别完成四项工作所需时间如下表，求最优分配方案。,分配问题与匈牙利法,解：1）变换系数矩阵，增加0元素。,2）试指派（找独立0元素）,独立0元素的个数为4 , 指派问题的最优指派方案即为甲负责D工作，乙负责B工作，丙负责A工作，丁负责C工作。这样安排能使总的工作时间最少，为4491128。,分配问题与匈牙利法,例4.8 已知五人分别完成五项工作耗费如下表，求最优分配方案。,分配问题与匈牙利法,-1,-2,解：1）变换系数矩阵，增加0元素。,