《运输与指派问题.pptx》由会员分享，可在线阅读，更多相关《运输与指派问题.pptx（52页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、【例1】现有A1，A2，A3三个产粮区，可供应粮食分别为10，8，5(万吨)，现将粮食运往B1，B2，B3，B4四个地区，其需要量分别为5，7，8，3(万吨)。产粮地到需求地的运价(元/吨)如表1所示，问如何安排一个运输计划，使总的运输费用最少。地区地区产粮区产粮区B1B2B3B4产量产量A1326310A253828A341295需要量需要量578323运价表(元/吨)表1运输模型ModelofTransportationProblems第1页/共52页设xij(i=1,2,3；j=1,2,3,4)为i个产粮地运往第j个需求地的运量，这样得到下列运输问题的数学模型：【解】运输模型Modelo
2、fTransportationProblems第2页/共52页【例2】有三台机床加工三种零件，计划第i台的生产任务为a i(i=1,2,3)个零件，第j种零件的需要量为bj (j=1,2,3)，第i 台机床加工第j 种零件需要的时间为cij，如表2所示。问如何安排生产任务使总的加工时间最少？零件零件机床机床B1B2B3生产任务生产任务A152350A264160A373440需要量需要量703050150表2运输模型ModelofTransportationProblems第3页/共52页【解】设xi j (i=1,2,3；j=1,2,3,)为第i台机床加工第j种零件的数量，则此问题的数学模型
3、为运输模型ModelofTransportationProblems第4页/共52页运输问题的一般数学模型设有m个产地生产某种物资,记作A1,A2,A3,Am，其产量分别为a1,a2,am；有n个销地,记作B1，B2，Bn，其需要量分别为b1,b2,bn；且产销平衡，即。从第i个产地到第j 个销地的单位运价为cij，在满足各地需要的前提下，求总运输费用最小的调运方案。设xij(i=1,2,m；j=1,2,n)为第i 个产地到第j个销地的运量，则数学模型为：运输模型ModelofTransportationProblems第5页/共52页设平衡运输问题的数学模型为：模型特征:1.运输问题存在可行
4、解，也一定存在最优解;2.当供应量和需求量都是整数时，则一定存在整数最优解;3.有m+n个约束，mn个变量;4.有m+n1个基变量;运输模型ModelofTransportationProblems第6页/共52页为一个闭回路，集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边。x25x23B1B2B3B4B5A1A2A3x35A4 x43x11 x12x31x42表3表3中闭回路的变量集合是x11,x12,x42,x43,x23,x25,x35,x31共有8个顶点，这8个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。闭回路:运输模型ModelofTransportationPr
5、oblems第7页/共52页x11x12x32x33x41B1B2B3A1A2A3A4x43表4表4中闭回路是注：(1)一条回路中的顶点数一定是偶数，回路遇到顶点必须转90度与另一顶点连接。(2)有些变量组本身不构成回路，但其可能包含回路，例如：表3中变量组不能组成一条闭回路，但A中包含有 闭回路运输模型ModelofTransportationProblems第8页/共52页设平衡运输问题的数学模型为：运输单纯形法TransportationSimplexMethod运输单纯形法基本思路：是基可行解最优否否停第9页/共52页运输单纯形法也称为表上作业法，是直接在运价表上求最优解的一种方法，它
6、的步骤是：Step1：求初始基可行解(初始调运方案)。常用的方法 有最小元素法、元素差额法(Vogel近似法)、左上角法等。Step2：求检验数并判断是否得到最优解。常用于求检验数的方法有闭回路法和位势法，当非基变量的检验数ij全都非负时得到最优解，若存在检验数lk0，说明还没有达到最优，转第三步。Step3：调整运量，即换基。选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步。注:表上作业法的条件是产销平衡和运价非负。运输单纯形法TransportationSimplexMethod第10页/共52页初始基可行解的确定最小元素法：最小元素法的思想是就近优先运送，即最小运价cij 对
7、应的变量xij 优先赋值然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后得到一个初始基可行解。【例3】求表5所示的运输问题的初始基可行解。表5 销销 地地产地产地B1B2B3产产 量量A1A2A3847634758304525销销 量量603010100运输单纯形法TransportationSimplexMethod第11页/共52页 BjAiB1B2B3产产 量量A186730A243545A374825销销 量量603010100表6【解】3015102520运输单纯形法TransportationSimplexMethod第12页/共52页【例4】求表7给出的
8、运输问题的初始基本可行解 B1B2B3B4aiA14104420A2773815A31210615bj510251050表7运输单纯形法TransportationSimplexMethod第13页/共52页表8 BjAiB1B2B3B4aiA14104420A2773815A31210615bj510251050【解】5100151010运输单纯形法TransportationSimplexMethod第14页/共52页初始基本可行解可用下列矩阵表示表8中，基变量恰好是3+41=6个且不包含闭回路，是一组基变量，其余标有符号的变量是非基变量运输单纯形法TransportationSimple
9、xMethod第15页/共52页求出一组基可行解后，判断其是否最优，仍然是用检验数来判断，记xij的检验数为ij，由第一章知，求最小值的运输问题的最优判别准则是：所有非基变量的检验数都非负，则运输方案最优(即为最优解)。求检验数的方法有两种，闭回路法和位势法。1闭回路法求某一非基变量的检验数的方法是：在基本可行解矩阵中，以该非基变量为起点，以基变量为其它顶点，找一条闭回路，由起点开始，分别在顶点上交替标上代数符号+、-、+、-、，以这些符号分别乘以相应的运价，其代数和就是这个非基变量的检验数。求检验数运输单纯形法TransportationSimplexMethod第16页/共52页【解】用最
10、小元素法得到下列一组基本可行解【例5】求下列运输问题的一个初始基本可行解及其检验数。矩阵中的元素为运价Cij，矩阵右边的元素为产量ai，下方的元素为销量bj。运输单纯形法TransportationSimplexMethod第17页/共52页只求非基变量的检验数：求11，先找出x11的闭回路，对应的运价为再用正负号分别交替乘以运价有直接求代数和得运输单纯形法TransportationSimplexMethod第18页/共52页 BjAiB1B2B3B4aiA19384706010A27651502030A321092201010bj1060403080966-3第19页/共52页2位势法求检
11、验数:位势法求检验数是根据对偶理论推导出来的一种方法。设平衡运输问题为设前m个约束对应的对偶变量为ui(i=1,2,m)，后n个约束对应的对偶变量为vj(j=1,2,n),则运输问题的对偶问题是运输单纯形法TransportationSimplexMethod第20页/共52页加入松驰变量ij将约束化为等式:ui+vj+ij=cij记原问题基变量XB的下标集为I，由第二章对偶性质知，原问题xij的检验数的相反数是对偶问题的松弛变量ij，当（i，j）I时ij=0，因而有解上面第一个方程，将ui、vj 代入第二个方程求出ij运输单纯形法TransportationSimplexMethod第21页
12、/共52页【例6】用位势法求例7给出的初始基本可行解的检验数。【解】第一步求位势u1、u2、u3及v1、v2、v3、v4。10604030令u1=0得到位势的解为运输单纯形法TransportationSimplexMethod第22页/共52页再由公式求出检验数，其中cij是非基变量对应的运价。计算结果与例7结果相同。运输单纯形法TransportationSimplexMethod第23页/共52页用位势法求检验数通常可直接在表上进行计算：例如 BjAiB1B2B3B4uiA193846010A276512030A3210921010vj308-341189660-3运输单纯形法Trans
13、portationSimplexMethod第24页/共52页调整运量当某个检验数小于零时，基可行解不是最优解，总运费还可以下降，这时需调整运输量，改进原运输方案，使总运费减少，改进运输方案的步骤是：第一步：确定进基变量:第二步：确定出基变量:在进基变量xik的闭回路中，标有负号的最小运量作为调整量，对应的基变量为出基变量，并打上“”以示作为非基变量。第三步：调整运量:在进基变量的闭回路中标有正号的变量加上调整量，标有负号的变量减去调整量，其余变量不变，得到一组新的基可行解，然后求所有非基变量的检验数重新检验。运输单纯形法TransportationSimplexMethod第25页/共52页
14、 BjAiB1B2B3B4aiA15892704030A23647804535A31012145402515bj45655030190【例7】求下列运输问题的最优解表95.2运输单纯形法TransportationSimplexMethod【解】用最小元素法求得初始基本可行解如表9第26页/共52页用闭回路法求非基变量的检验数得：BjAiB1B2B3B4aiA15892704030A23647804535A31012145402515bj45655030190+_+_+_运输单纯形法TransportationSimplexMethod第27页/共52页因为有4个检验数小于零，所以这组基本可行
15、解不是最优解。对应的非基变量x11进基.对应的非基变量x11进基.x11的闭回路是x33最小，x33是出基量，调整量=15 BjAiB1B2B3B4aiA15892704030A23647804535A31012145402515bj45655030190+_+_+_第28页/共52页 BjAiB1B2B3B4aiA1589270152530A23647803050A310121454040bj45655030190在x11的闭回路上x11、x32、x23分别加上15，x12、x33、x21分别减去15，并且在x33处打上记号“”作为非基变量，其余变量不变，调整后得到一组新的基可行解：运输单纯
16、形法TransportationSimplexMethod第29页/共52页 BjAiB1B2B3B4aiA1589270152530A23647803050A310121454040bj45655030190重新求所有非基变量的检验数得13=3，22=0，24=7，31=1，33=4，34=134=10,说明还没有得到最优解，x34进基，在x34的闭回路中，标负号的变量x14和x32，调整量为运输单纯形法TransportationSimplexMethod第30页/共52页 BjAiB1B2B3B4aiA15892701555A23647803050A31012145401030bj456
17、55030190 x14出基，调整运量得到：再求非基变量的检验数：13=3，14=1，22=0，24=8，31=1，33=4运输单纯形法TransportationSimplexMethod第31页/共52页再求非基变量的检验数：13=3，14=1，22=0，24=8，31=1，33=4所有检验数ij0因而得到最优解最小运费运输单纯形法TransportationSimplexMethod第32页/共52页设数学模型为最大值问题运输单纯形法TransportationSimplexMethod第33页/共52页方法一：将极大化问题转化为极小化问题。设极大化问题的运价表为C=（Cij）mn，用一
18、个较大的数M（MmaxCij）去减每一个Cij得到矩阵C=（Cij）mn，其中Cij=MCij0,将C作为极小化问题的运价表，用表上用业法求出最优解，目标函数值为例如，下列矩阵C是Ai（i=1，2，3）到Bj的吨公里利润,运输部门如何安排运输方案使总利润最大.8149运输单纯形法TransportationSimplexMethod第34页/共52页用最小元素法求初始方案得11=8,12=4,21=2,23=2全部非负,得到最优运输方案X,最大利润Z=89+1010+68+54=240方法二:所有非基变量的检验数ij0时最优.求初始运输方案可采用最大元素法.如上例,用最大元素得到的初始运输方案
19、:8149求检验数:11=8,12=4,21=2,23=2,全部非正,得到最优解运输方案,结果与第一种方法相同.运输单纯形法TransportationSimplexMethod第35页/共52页当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。1.当产大于销时,即数学模型为不平衡运输问题运输单纯形法TransportationSimplexMethod第36页/共52页由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，库存量为xi，n+1（i=1，2，m），总的库存量为
20、运输单纯形法TransportationSimplexMethod第37页/共52页bn+1作为一个虚设的销地Bn+1的销量。各产地Ai到Bn+1的运价为零，即Ci，n+1=0,（i=1，m）。则平衡问题的数学模型为：具体求解时,只在运价表右端增加一列Bn+1，运价为零,销量为bn+1即可运输单纯形法TransportationSimplexMethod第38页/共52页2.当销大于产时,即数学模型为运输单纯形法TransportationSimplexMethod第39页/共52页由于总销量大于总产量,故一定有些需求地不完全满足,这时虚设一个产地Am+1，产量为xm+1,j是Am+1运到Bj
21、的运量，也是Bj不能满足需要的数量。Am+1到Bj的运价为零,即Cm+1,j=0(j=1,2,n)运输单纯形法TransportationSimplexMethod第40页/共52页销大于产平衡问题的数学模型为：具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为am+1即可。运输单纯形法TransportationSimplexMethod第41页/共52页指派问题assignmentproblem【例8】人事部门欲安排四人到四个不同的岗位工作，每个岗位一个人经考核四人在不同岗位的成绩（百分制）如下表所示，如何安排他们的工作使总成绩最好。工作工作人员人员ABCD甲甲85927390乙
22、乙95877895丙丙82837990 丁丁86908088【解】设指派问题的数学模型第42页/共52页数学模型为：甲乙丙丁ABCD图5.3指派问题assignmentproblem第43页/共52页假设m个人恰好做m项工作，第i个人做第j项工作的效率为cij0，效率矩阵为cij，如何分配工作使效率最佳(min或max)的数学模型为指派问题assignmentproblem第44页/共52页解指派问题的匈牙利算法匈牙利法的条件：问题求最小值、人数与工作数相等及效率非负【定理5.4】如果从分配问题效率矩阵cij的每一行元素中分别减去(或加上)一个常数ui(被称为该行的位势)，从每一列分别减去(或
23、加上)一个常数vj(称为该列的位势)，得到一个新的效率矩阵bij，其中bij=cij ui vj,则bij的最优解等价于cij的最优解，这里cij、bij均非负【定理5.5】若矩阵A的元素可分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列的“0”元素(称为独立元素)的最大个数如果最少直线数等于m，则存在m个独立的“0”元素，令这些零元素对应的xij等于1，其余变量等于0，这时目标函数值等于零，得到最优解指派问题assignmentproblem第45页/共52页【例9】某汽车公司拟将四种新产品配置到四个工厂生产，四个工厂的单位产品成本(元/件)如下表所示求最优生产配
24、置方案产品产品1产品产品2产品产品3产品产品4工厂工厂15869180260工厂工厂27550150230工厂工厂36570170250工厂工厂48255200280【解】问题求最小值。第一步：找出效率矩阵每行的最小元素，并分别从每行中减去最小元素，有指派问题assignmentproblem第46页/共52页第二步：找出矩阵每列的最小元素，再分别从每列中减去，有指派问题assignmentproblem第47页/共52页第三步：用最少的直线覆盖所有“0”，得第四步：这里直线数等于3(等于4时停止运算)，要进行下一轮计算从矩阵未被直线覆盖的数字中找出一个最小数k并且减去k，矩阵中k5直线相交处
25、的元素加上k，被直线覆盖而没有相交的元素不变，得到下列矩阵第四步等价于第1、3行减去5，同时第1列加上5得到的结果指派问题assignmentproblem第48页/共52页第五步：覆盖所有零最少需要4条直线，表明矩阵中存在4个不同行不同列的零元素容易看出4个“0”的位置()()()()或()()()()指派问题assignmentproblem第49页/共52页得到两个最优解有两个最优方案第一种方案：第一个工厂加工产品1，第二工厂加工产品3，第三个工厂加工产品4，第四个工厂加工产品2；第二种方案：第一个工厂加工产品1，第二工厂加工产品4，第三个工厂加工产品3，第四个工厂加工产品2；单件产品总成本Z5815025055513指派问题assignmentproblem第50页/共52页其它变异问题【例10】求例8的最优分配方案【解】则求此问题的最小值求解过程如下最优分配方案是：甲分配到B岗位；乙分配到A岗位；丙分配到D岗位；丁分配到C岗位；总成绩为357 工作工作人员人员ABCD甲甲85927390乙乙95877895丙丙82837990 丁丁86908088指派问题assignmentproblem第51页/共52页感谢您的观看！第52页/共52页