最短路径、指派、运输问题

1、1,2,3,指派问题,一、指派问题数学模型,引例：今有4辆装载不同货物的待卸车，派班员要分派给4个装卸班组，每个班组卸1辆，由于各个班组的技术专长不同，各个班组卸不同车辆所需的时间如下表，问派班员应该如何分配卸车任务可使卸车所花费的时间最小？,4,二、指派问题算法匈牙利算法,定理：如果对系数矩阵任意行或列的各元素（cij）分别减去该行或列的最小元素，得到新矩阵（bij），则以新矩阵为系数的指派问题的最优解和原问题的最优解相同。,5,匈牙利算法步骤：,第一步：使系数矩阵经变换，在各行各列中都出现0元素： （1）从系数矩阵的每行元素减去该行的最小元素； （2）再从所得矩阵的每列元素中减去该列的最小

2、元素。 若某行（列）已有0元素，那就不必再减了。引例的计算为：,6,第二步：进行试指派以寻求最优解。 （1）进行行检验：从只有一个0元素的行开始，给这个0元素加（），记作（0）；再划去（0）所在列的其它0元素，记作。若遇到有两个0元素以上的行，先放下。 （2）进行列检验：给只有一个0元素的列0元素加（），记作（0）；然后划去（0）所在行的0元素，记作。 （3）再对两个以上0元素的行和列标记，任意取一个加（）。,若（0）的个数为n个，则得出最优解，否则转第三步。,7,第三步：若mn，作最少的直线覆盖所有的0元素，以确定在该系数矩阵中能找到最多的独立元素，按下列步骤进行： （1）对没有(0)的行打

3、号； （2）对已打号的行中所在列打号； （3）再对打有号的列中，含(0)元素的行打号； （4）重复(2)、(3)直到得不出新的打号的行、列为止。 （5）对没有打号的行画一横线，有打号的列画一纵线， 这就得到覆盖所有0元素的最少直线数。,8,第四步：在没有被直线覆盖的部分元素中找出最小元素，然后： （1）对没有画横线的行中各元素中减去这一最小元素； （2）在打列中各元素加上这个最小元素； 目的是保证原来的0元素不变，这样得到新系数矩阵（它的最 优解与原问题相同）。 （3）若得到n个独立的0元素，则问题已取得最优解，否则再 回到第三步重复进行。,1,-1,-1,+1,最优解为c13+c21+c34

4、+c42=20此类问题有多个解结构（指派方案）？,9,例：某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知各建筑公司对新商店的建造费用报价如下图所示。商业公司应对5家公司怎样分配建造任务，才能使总的建造费用最少？,10,11,（1）目标函数求最大值的指派问题,三、其它指派问题,对于此问题可做一个新的矩阵B=(bij)。找出原矩阵的最大元素m，令B=(bij)=m-cij,12,例：需要分派5人去做5项工作，每人做各项工作的能力评分见表，应如何分派，才能使总得分最大？,13,（2）非标准指派问题,1、人数和事数不等的指派问题； 若人少事多，则虚拟人，系数为

5、0.若人多事少，则虚拟事，系数为0.,14,（2）非标准指派问题,2、一个人可做几件事的指派问题； 可将该人化作相同的几个人来接受指派。这几个人做同一件事的费用系数当然一样。,15,（2）非标准指派问题,3、某事一定不能由某人做的指派问题。 可将相应的费用系数取做足够大的数M。,16,例：某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知各建筑公司对新商店的建造费用报价如下图所示。商业公司应对5家公司怎样分配建造任务，才能使总的建造费用最少？,17,18,对于上述问题，为了保证工程质量，经研究决定，舍弃建筑公司A4和A5，而让技术力量较强的建筑公司A1、A

6、2、A3来承建。根据实际情况，可以允许每家建筑公司承建一家或两家商店。求使总共费用最少的指派方案。,19,指派问题复习,1、某物流公司安排四个人：甲、乙、丙、丁去完成四项任务A、B、C、D，他们完成任务所需时间如表所示，问应指派何人去完成何工作，所需总时间最少？,20,2、现有4份工作，6个人应聘，由于个人的技术专长不同，他们承担各项工作所需时间如表所示，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求总时间最少的指派方案。,21,22,运输问题,引例：某公司设有A1、A2、A3三个加工厂，产量分别为：9吨、5吨、7吨；有B1、B2、B3、B4四个销售点，销量分别为：3吨、8吨、4吨

7、、6吨；从各工厂到销售点的单位产品的运价为下表所示，问该公司应该如何调运产品使总运费最少？,23,6.1 运输问题线性规划模型,某公司有m个产地A1，A2， ，Am，产量分别为a1，a2， ，am；有n个销售地B1，B2， ，Bn，销量分别为b1，b2， ，bm；从产地Ai到销地Bj的单位产品的运价为Cij，问该公司应该如何调运产品使总运费最少？,前提条件：,产量与销量平衡,解：,设产地Ai到销地Bi的运量为xij，由问题构造运量平衡表,可以知道：,（1）产销平衡,（2）Ai运出量等于产量,（3）Bj运入量等于销量,将问题归纳为线性规划问题：,约束方程,目标函数,（1）所有的约束条件（不包括非

8、负约束）都是等式。 （2）产量之和等于销量之和。 （3）运输问题显然是一个线性规划问题，可以用学过的单纯形法求解，但求解时对每一个等式必须加上一个人工变量（参考当约束条件方程为等式约束时求初始基本可行解的方法），这样将使一个很小规模的运输问题变得较为烦琐。,表上作业法是一种迭代算法 ，也是从先求出初始基本可行解，然后用检验数判定是否最优解，若是就停止计算，否则就要对解进行调整、判定，直到求出最优解为止。因为关于以上计算都可以在产销平衡表中进行，所以叫表上作业法。,一般单纯形法,表上作业法,简便方法,6.2 初始基本可行解的求法,运输问题有m+n个约束条件、m*n个变量。在运输问题中有一个是多余

9、的，所以起作用的约束只有m+n-1个。这是因为运输问题约束条件方程中前m个约束相加正好得出一个与后n个约束相加完全相等似的约束，这说明约束条件中起作用的约束只有m+n-1个。,相关知识,下面的变量就构成一个闭回路。尽管闭回路有多种形式，但是所有“连线”不是垂直就是平行，这样才符合行列一个变另一个不变的要求；“连线”不能是“斜线”，因为只有行列全变化时才出现“斜线”。,相关定理,利用前面相关知识、闭回路概念及相关定理即可求出运输问题的初始基本可行解。,一、西北角法,西北角法步骤： （1）将运价表和平衡表合并为综合表，将运价Cij左下角，运量xij标在右上角。,（2）由下式决定 左上角变量 的值，

10、并将 这个数字标 在对应运费的右上角。,（3）在填数的格子所在的行或列应该为0的格子上打“”； 若行或列都应该取0，则在行上打“”后，就不能在列 上打“”；反之，在列上“”后就不能在行上打“”。,（4）对没有填数及打“”的地方重复上述步骤，若剩余空格 对应的变量应该取0，则应写上0，而不能打“”，以保 证初始解的个数为m+n-1个。,得到可行解x11=3,x12=6,x22=2,x23=3,x33=1,x34=6. z=2*3+9*6+3*2+4*3+2*1+5*6=110,二、最小元素法,西北角法不足之处是只满足了约束方程，没围绕目标函数处理问题，即没考虑Cij值。若将Cij考虑进去，得到的

11、基本可行解就会使目标函数更小些，即更接近最优解，也使迭代次数减小。,利用西北角法思路，但取值是从Cij最小的位置开始。,（1）从运费（一般用cij表示）取最小值的空格开始（若有几个地方同时达到，可任选一个）。 （2）与它对应的变量按照西北角法取最大值。 （3）在不可能分配运量的地方画“”，以此类推，直到选够m+n-1个变量为止。 （4）若只剩下一行或一列未填数和打“”的格子时，只能填数不能打“”，目的是保证解的个数为m+n-1个。,规则：,得到可行解x21=3,x12=5,x32=3,x33=4,x14=4,x34=2. z=1*3+9*5+4*3+2*4+7*4+2*2=100,最小元素法的

12、缺点是：为节省一处的费用，有时要造成其它处多花几倍的运费，,三、差值法,某地产品若不能按最小运费就近供应，就考虑次小运费，这就有一个差额，差额越大，说明不能按最小运费调运时，运费增加越多，因而对差额最大处，就应当采用最小运费调运。,差值法步骤： （1）将运价表和平衡表合并为新的综合表，在新综合表中包含 最下的差值行和最右的差值列。 （2）在表中分别计算出各行和各列的最小运费和次最小运费的 差额，并填入该表的最右列和最下行。 （3）从最下的差值行和最右的差值列中选出最大者，选择最大 者所在行或列中的最小Cij元素。 （4）按照西北角法的思路进行标示，然后依次对表中未标示的 元素再分别计算出各行、

13、各列的最小运费和次最小运费的 差额，再填入该表的最右列和最下行。 （5）重复第一、二步。直到给出初始解为止。用此法给出例1 的初始解列于下表。,产地Ai,销地Bi,运价,销量,产量,A1,A2,A3,B1,B2,B3,2,9,10,1,3,4,8,4,2,3,8,4,9,5,7,B4,7,2,5,6,21,3,5,5,3,4,1,选择最大差值所在行或列的最小Cij可以避免将运量调配到同一行或同一列的次小的空格中去；另外，最小元素法的规则在差值法中仍然适用。,差值,差值,1,1,2,3,5,1,2,得到可行解x11=3,x12=5,x32=3,x33=4,x14=1,x24=5. z=2*3+9

14、*5+4*3+2*4+7*1+2*5=88,定理：西北角法、最小元素法、差值法得到的xij值是一组基 本可行解，没有画“”的地方对应变量正好是基变量。,定理：任何运输问题都有最优解。 一是有唯一最优解；二是有无限多个最优解,6.3 求检验数的求法,线性规划中，通过检验数cj-zj非负来判定最小化目标函数的基本可行解是最优解。针对特殊的运输问题，判定基本可行解是否最优仍然采用线性规划准则，只是求检验数有独特的方法。,如何求运输问题的检验数有两种方法： （1）闭回路法 （2）位势法,一、闭回路法,定理：运输问题的表上作业法中，任一个非基变量都能和若干个基变量构成唯一的闭回路。,示例：以上面最小元素

15、法的基本可行解为例，求非基变量检验数。 23=c11-c14+c24-c21=2-7+2-1=-4，同样， 23=2， 。将检验数另画一张表。从表中看出，存在负的检验数，不是最优解。,把运量给x11处分配一个单位，看看会对目标函数值带来什么影响（增加还是减少）。,由于表上作业法中表的每行上分配的运量之和是一个常数（等于对应产地的产量），所以若给x13（分配前x11=0，是非基变量）分配了1个单位的运量，将增加110个单位的运费；同时为保持产量平衡，对应的x14处就要减少一个单位的运量，这样将减少17个单位的运费；与此同时，由于表上作业法中表的每列上分配的运量之和是一个常数（等于对应销地的销量）

16、所以当x14减少了1个单位的运量时，为保持销量平衡x24将增加1个单位的运量，这样将增加12个单位的运费；同理可知对应的x33处就要减少一个单位的运量，将减少12个单位的运费。综上所述，目标函数值增加了10+2，同时又减少了7+2。所以目标函数总变化量为：（10+2）-（7+2）=3。这就是说，每给x11分配一个单位的运量，目标函数（总运费）将增加一个单位。因此在表上作业法中对检验数大于零的地方不再分配运量，若所有非基变量的检验数全大于零，任何形式的运量调整只能使目标函数值增加，所以算法终止，此时的解就是最优解。请大家参考上面的例子仔细想一想，若非基变量的检验数小于零，是否应该给该处分配运量把

17、非基变量调整成基变量？答案是肯定的，为什么？,二、位势法,用闭回路法求检验数，需要对每一个非基变量（表上画“”地方）寻找闭回路，然后再去求检验数，当一个运输问题的产销点很多时，这种方法的计算工作量是很大的，所以介绍一下位势法。,基本原理是： 针对基变量Xij给定系数ui和vj，建立方程组： ui+vj=cij 知道基变量有m+n-1个，所以系数ui和vj的个数也为m+n-1个，那么方程组的方程数也为m+n-1个，解方程组即可求出ui和vj。,定理： 对于非基变量的检验数有： ij=cij-ui-vj。 简单证明： 根据闭回路法和方程组有：,表上作业法是将方程组求出的解ui和vj分别列在表的左边

18、和上边，然后将利用定理求出的检验数列在相应的格子中。（书86页例题）,40,6.4 方案的调整,前面已经知道，在已求得的基本可行解及检验数的平衡表中，若有负的检验数，此时的解就不是最优解，应进行调整，以求出另外一组基本可行解，使目标函数值下降。求出下一组基本可行解，首先要决定哪一个非基变量要进入基中去，哪一个要被换出来，调整量是多少，然后如何进行调整。,1 确定换入变量 同单纯形法一样，在负的检验数中，一般要取检验数最小的 非基变量作为换入变量。,2 确定换出变量和调整量 由定理（课本定理4），由换入变量（此时还是非基变量）和 一组基变量可以组成唯一的一个闭回路，则以换入变量为起点，可以找到唯

19、一的闭回路，取此回路偶数顶点中基变量取值最小的做为换出变量，调整量即为此基变量的值。,3 调整方法 （1）上述闭回路以外的变量的值均不变。 （2）上述闭回路寄顶点上的变量均加上调整量，偶顶点上的变量均减去调整量。,6.5 应用问题,无穷多最优解,退化,产销不平衡问题,产量、销量不确定问题,表上作业法如何处理现实中复杂现象,表上作业法两个特殊问题,有转运点问题,复合问题,一、表上作业法两个特殊问题的处理,（1）无穷多个最优解问题：产销平衡的运输问题必定存在最优解（唯一或无穷）。若某个非基变量的检验数为0，则有无穷个最优解，处理方式是将此非基变量作为换入变量，即以此作闭回路，按照调整规则找出换出变

20、量，从而得到另一个最优解，不断迭代。,（2）退化问题：用表上作业法时在求初始解或者调整时会出现退化问题，处理方法是在相应处用0进行运量处理，即必须保证基变量个数为m+n-1个。 （教材8890页）,二、表上作业法处理现实中几种复杂现象,（1）总产量大于总销量，即 可虚增一个销售点，令其销量为a-b。实际问题中可以看 作存贮点，若不考虑存贮费用，则单位运费为零；若考虑， 则单位运费就等于单位存贮费Ci 。,1、产销不平衡问题。,（2）总产量小于总销量，即 可虚增一个产地，令其产量为b-a，实际问题中可以看作 缺货量。若不考虑缺货费用，则单位运费为零；若考虑，则单 位运费就等于每单位缺货费用cj

21、，若某地不能缺货，则对应 的缺货费用为大M（是一个非常大的正数），表明若缺货总费 用将是任意大。,通过以上两步，可以把产销不平衡问题化为产销平衡问题用表 上作业法求解。,示例：,此处Ci5为0，但有时根据具体情况定。,针对产量小于销量可以同样处理,2、产量（发送量）、销量不确定问题的处理,在有些问题中，给出某产地的产量（销量）在一个数字范围内，如（aaib或aaib ）。 这种情况下就要把一个产地拆成两个“产地”，一个产量为a，另一个产量为b-a，单位运费参照上面所讲的内容设置。如课本92页例题7中A1 、A3 两个产地均属这种情况。对需求量不确定的问题也可以参照上面的方法进行处理，化为确定型的标准运输问题。,示例：,某物资从产地A1、A2、A3到销