第五章运输问题和指派问题.ppt

第五章 运输问题和指派问题,第一节 运输问题的数学模型,运输问题的一般描述：某种物质（粮食、棉花、煤等）有若干个产地和销地，现在需要把物质从各个产地运往各个销地，产量总数等于销量总数，调运方案很多。若已知各产地的产量、各销地的销量以及各产地到销地的单位运价（或运输距离）。又假定运费和运输量成正比，问如何调运，才能使总运费最省？,第一节 运输问题的数学模型,设Xij为第i个产地运往第j个销地的数量 这是m×n个变量，约束条件为m+n个的线性规划问题。,Min Z= CijXij xij =ai （i=1，2，m） xij =bj （j=1，2，n） xij0 （i=1，2，m；j=1，2，n）,第一节 运输问题的数学模型,一、运输问题约束条件系数矩阵,A =,1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1,（m+n）×（mn）,第一节 运输问题的数学模型,二、运输问题的基变量共有m+n-1个 三、 m+n-1个变量构成基变量的充要条件是它们不构成闭合回路,第二节 表上作业法,表上作业法求解运输问题的思路和单纯形法完全类似。 建立作业表 确定初始调运方案 现行方案的最优性检验 现行方案的调整,第二节 表上作业法,一、初始方案的确定： 1.西北角法（左上角法） 从表的左上角开始，保证产销平衡，每填上一个数划去一行或一列，直到有m+n-1行或列划去即可。填上数字为基变量，从而保证其个数为m+n-1个又不构成闭合回路。,第二节 表上作业法,一、初始方案的确定： 2.最小元素法 采用“就近供应”的思想。 从运输表的运费最小的元素开始，保证产销平衡，每填上一个数划去一行或一列，直到有m+n-1行或列划去即可。填上数字为基变量，从而保证其个数为m+n-1个又不构成闭合回路。,第二节 表上作业法,一、初始方案的确定： 3. 元素差额法（Vogel近似法） 是在最小元素法基础上的改进。 求每行和每列的行罚数和列罚数 从行罚数和列罚数最大的行或列的运费最小的元素开始，保证产销平衡，每填上一个数划去一行或一列。 重复和直到有m+n-1行或列划去即可。 填上数字为基变量，从而保证其个数为m+n-1个又不构成闭合回路。,第二节 表上作业法,二、最优性检验 1.闭合回路法： 2. 位势法： 三、调整,表上作业法的几点说明：,1.若运输问题的某一基可行解有多个非基变量的检验数为负时，在迭代时可取它们中任一非基变量进基均可使目标函数值得到改善，但通常取最小者对应的非基变量进基。 2.当迭代到最优解时，有某非基变量的检验数为 0 时，则问题有无穷多最优解。 3.当在表上作业时，同时划去了一行和一列运输价格时，就出现了退化，此时必须在当前划去的运价中某一空格填入一个 0 ，表示该格中的变量是取值为 0 的基变量。,第三节 产销不平衡的运输问题,一、产大于销的运输问题 虚设销地，其需要量为ai-bj,相应的运费为0，化成产销平衡的运输问题。,Min Z= CijXij xij ai （i=1，2，m） xij =bj （j=1，2，n） xij0 （i=1，2，m；j=1，2，n）,第三节 产销不平衡的运输问题,一、销大于产的运输问题 虚设产地，其产量为bj-ai,相应的运费为0，化成产销平衡的运输问题。,Min Z= CijXij xij = ai （i=1，2，m） xij bj （j=1，2，n） xij0 （i=1，2，m；j=1，2，n）,14,第四节 指派问题,指派问题的标准形式（以人和事为例）是： 有 n 个人和 n 件事，已知第 i 人做第 j 事的费用为 Cij（i，j = 1，2，n），要求确定人和事之间的一一对应的指派方案，使完成这件事的总费用最少。如,15,第四节 指派问题,一、指派问题的标准形式及其数学模型 令,1 当指派第 i 人完成第 j 项任务 0 当不指派第 i 人完成第 j 项任务,xij =,min z = cijxij xij = 1， j = 1，2，n xij = 1， i = 1，2，n xij = 1 或 0,16,第四节 指派问题,二、指派问题的匈牙利解法 标准的指派问题是一类特殊的 0-1 整数规划问题，可以用多种相应的解法来求解。但是，这些方法都没有充分利用指派问题的特殊性质来有效减少计算量。1955年，库恩（W.W.Kuhn）利用匈牙利数学家康尼格（D.König）的关于矩阵中独立零元素的定理，提出了指派问题的一种解法，由此，习惯上称之为匈牙利解法。,17,第四节 指派问题,二、指派问题的匈牙利解法 匈牙利解法的关键是利用了指派问题最优解的如下性质： 若从指派问题的系数矩阵 C = （ cij ）n×n 的某行（或某列）各元素分别减去一个常数 k ，得到一个新的系数矩阵C = （ cij ）则以 C 和 C 为系数矩阵的两个指派问题有相同的最优解。,匈牙利解法的一般步骤 步骤一： 变换系数矩阵。使其每行及每列至少有一个零元素，同时不出现负元素。 步骤二： 进行试指派，即确定独立零元素。 步骤三： 继续变换系数矩阵，然后返回步骤二。,19,第四节 指派问题,指派问题（assignment problem） 匈牙利解法的一般步骤,对没有加圈零元素的行打号； 对所有打号行的所有含零元素的列打号； 再对已打号的列中含零元素的行打号； 重复2）和3），直到再也不能找到可以打号行或列为止； 对没有打号的行画一横线，对打号的列画一竖线，这样就得到能覆盖所有零元素的最少直线数目的直线集合。,20,指派问题（assignment problem）,匈牙利解法的一般步骤 以上例说明步骤,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 2,2 4 9 7,min,（ cij ）=,21,指派问题（assignment problem）,匈牙利解法的一般步骤 以上例说明步骤,0 13 11 2 6 0 10 11 0 4 7 4 0 1 4 2,0 0 4 2,min,0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0,= （ cij ）,22,指派问题（assignment problem）,匈牙利解法的一般步骤 以上例说明步骤,0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0,此时加圈 0 元素的个数 m = n = 4，所以得到最优解,23,指派问题（assignment problem）,匈牙利解法的一般步骤 以上例说明步骤,0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0,（ xij ）=,24,指派问题（assignment problem）,匈牙利解法的一般步骤 例,25,指派问题（assignment problem）,匈牙利解法的一般步骤,12 7 9 7 9 8 9 6 6 6 7 17 12 14 9 15 14 6 6 10 4 10 7 10 9,7 6 7 6 4,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,26,指派问题（assignment problem）,匈牙利解法的一般步骤,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 元素的个数 m = 4， 而n = 5，所以解题没有完成。独立零元素（加圈零元素）少于 n 个，表示还不能确定最优指派方案。此时需确定能覆盖所有零元素的最少直线数目的直线集合。方法如下：,27,指派问题（assignment problem）,匈牙利解法的一般步骤,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,