《第五章运输问题和指派问题.ppt》由会员分享，可在线阅读，更多相关《第五章运输问题和指派问题.ppt（27页珍藏版）》请在三一办公上搜索。
1、第五章 运输问题和指派问题,第一节 运输问题的数学模型,运输问题的一般描述：某种物质（粮食、棉花、煤等）有若干个产地和销地，现在需要把物质从各个产地运往各个销地，产量总数等于销量总数，调运方案很多。若已知各产地的产量、各销地的销量以及各产地到销地的单位运价（或运输距离）。又假定运费和运输量成正比，问如何调运，才能使总运费最省？,第一节 运输问题的数学模型,设Xij为第i个产地运往第j个销地的数量 这是mn个变量，约束条件为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）,第一节 运输问题的
2、数学模型,一、运输问题约束条件系数矩阵,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个
3、又不构成闭合回路。,第二节 表上作业法,一、初始方案的确定：2.最小元素法 采用“就近供应”的思想。从运输表的运费最小的元素开始，保证产销平衡，每填上一个数划去一行或一列，直到有m+n-1行或列划去即可。填上数字为基变量，从而保证其个数为m+n-1个又不构成闭合回路。,第二节 表上作业法,一、初始方案的确定：3.元素差额法（Vogel近似法）是在最小元素法基础上的改进。求每行和每列的行罚数和列罚数从行罚数和列罚数最大的行或列的运费最小的元素开始，保证产销平衡，每填上一个数划去一行或一列。重复和直到有m+n-1行或列划去即可。填上数字为基变量，从而保证其个数为m+n-1个又不构成闭合回路。,第二
4、节 表上作业法,二、最优性检验1.闭合回路法：2.位势法：三、调整,表上作业法的几点说明：,1.若运输问题的某一基可行解有多个非基变量的检验数为负时，在迭代时可取它们中任一非基变量进基均可使目标函数值得到改善，但通常取最小者对应的非基变量进基。2.当迭代到最优解时，有某非基变量的检验数为 0 时，则问题有无穷多最优解。3.当在表上作业时，同时划去了一行和一列运输价格时，就出现了退化，此时必须在当前划去的运价中某一空格填入一个 0，表示该格中的变量是取值为 0 的基变量。,第三节 产销不平衡的运输问题,一、产大于销的运输问题 虚设销地，其需要量为ai-bj,相应的运费为0，化成产销平衡的运输问题
5、。,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），要求确定人和事之间的一一对应的指派方案，使完成这件事的总
6、费用最少。如,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.Knig）的关于矩阵中独立零元素的定理，提出了指派问题的一种解法，由此，
7、习惯上称之为匈牙利解法。,17,第四节 指派问题,二、指派问题的匈牙利解法 匈牙利解法的关键是利用了指派问题最优解的如下性质：若从指派问题的系数矩阵 C=（cij）nn 的某行（或某列）各元素分别减去一个常数 k，得到一个新的系数矩阵C=（cij）则以 C 和 C 为系数矩阵的两个指派问题有相同的最优解。,匈牙利解法的一般步骤步骤一：变换系数矩阵。使其每行及每列至少有一个零元素，同时不出现负元素。步骤二：进行试指派，即确定独立零元素。步骤三：继续变换系数矩阵，然后返回步骤二。,19,第四节 指派问题,指派问题（assignment problem）匈牙利解法的一般步骤,对没有加圈零元素的行打号
8、；对所有打号行的所有含零元素的列打号；再对已打号的列中含零元素的行打号；重复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,2497,min,（cij）=,21,指派问题（assignment problem）,匈牙利解法的一般步骤以上例说明步骤,0 13
9、 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 proble
10、m）,匈牙利解法的一般步骤例,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,76764,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,
