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