第五章运输与指派问题

第五章运输与指派问题Transportation

andAssignmentProblem5.1运输模型MathematicalModelofTransportationProblems5.2运输单纯形法TransportationSimplexMethod5.3指派问题Assignmentproblem15.1运输模型MathematicalModelofTransportationProblems2运输问题概念将生产基地的各类物资，分别运到需要这些物资的地区，根据各地的生产量和需要量及各地之间的运输费用，制定一个运输方案，使总的运输费用最小。5.1运输模型5.1.1数学模型产地销地A110A28A35B43B38B27B15354231682329图5.134例5-1：现有A1，A2，A3三个产粮区，可供应粮食分别为10，8，5（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需要量分别为5，7，8，3（万吨）。产粮地到需求地的运价（元/吨）如表5-1所示，问如何安排一个运输计划，使总的运输费用最少。地区产粮区B1B2B3B4产量A1326310A253828A341295需要量578323运价表（元/T）表5-15.1运输模型5设xij(i=1,2,3；j=1,2,3,4)为第i个产粮地运往第j个需求地的运量（万吨），得到下列运输问题的数学模型：运量应大于或等于零（非负要求），即5.1运输模型6【例5-2】有三台机床加工三种零件，计划第i台的生产任务为ai(i=1,2,3)个零件，第j种零件的需要量为bj(j=1,2,3)，第i台机床加工第j种零件需要的时间为cij，如表5－2所示。问如何安排生产任务使总的加工时间最少？零件机床B1B2B3生产任务A152350A264160A373440需要量703050150表5-25.1运输模型7解：设xij(i=1,2,3；j=1,2,3,)为第i台机床加工第j种零件的数量，则此问题的数学模型为：5.1运输模型8运输问题的一般数学模型设有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个销地的运量，则数学模型为：5.1运输模型9设平衡运输问题的数学模型为：5.1.2模型特征1.运输问题存在可行解，也一定存在最优解2.当供应量和需求量都是整数时，则一定存在整数最优解3.有m+n个约束，mn个变量4.有m+n－1个基变量5.1运输模型10证：因为产销平衡，即，将前m个约束方程两边相加得再将后n个约束相加得显然前m个约束方程之和等于后n个约束方程之和，m+n个约束方程是相关的，系数矩阵定理5.1：设有m个产地n个销地且产销平衡的运输问题，则基变量数为m+n-1。5.1运输模型中任意m+n阶子式等于零(因为相关)，取第一行到m+n－1行与对应的列x1n,x2n,…xmn,x11,x12,…x1n-1（共m+n-1列）组成的m+n－1阶子式m行n行5.1运输模型11故r(A)=m+n－1所以运输问题有m+n－1个基变量。为了在mn个变量中找出m+n－1个变量作为一组基变量，就是要在A中找出m+n-1个线性无关的列向量，下面引用闭回路的概念寻找这些基变量。5.1运输模型12m行n-1行为一个闭回路，集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边。在表5-3及表5-4中的变量组构成两个闭回路。x25x23

B1B2B3B4B5A1

A2

A3

x35A4

x43

x11x12x31x42表5－3表5－3中闭回路的变量集合是{x11,x12,x42,x43,x23,x25,x35,x31}共有8个顶点，这8个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。5.1运输模型13x11x12x32x33x41

B1B2B3A1

A2

A3

A4

x43表5－4一条回路中的顶点数一定是偶数，回路遇到顶点必须转90度与另一顶点连接(表5－3中的变量x32及x33不是回闭路的顶点，只是连线的交点)。表5－4中闭回路是表5－3中，例如变量组A不能组成一条闭回路，但A中包含有闭回路B的变量数是奇数，显然不是闭回路，也不含有闭回路；5.1运输模型14定理5.2：若变量组B包含有闭回路，则B中的变量对应的列向量线性相关。证：由线性代数知，向量组中部分向量组线性相关则该向量组线性相关，显然，将C中列向量分别乘以正负号线性组合后等于零，即因而C中的列向量线性相关，所以B中列向量线性相关。具体证明过程参见教材P111-112.5.1运输模型15由定理2可知，当一个变量组中不包含有闭回路，则这些变量对应的系数向量线性无关。求运输问题的一组基变量，就是要找到m+n－1个变量，使得它们对应的系数列向量线性无关，由定理2，找这样的一组变量是很容易的，只要m+n－1个变量中不包含闭回路，就可得到一组基变量。因而有：定理3：m+n－1个变量组构成基变量的充要条件是它不包含任何闭回路。定理3告诉了一个求基变量的简单方法，同时也可以判断一组变量是否可以作为某个运输问题的基变量。这种方法是直接在运价表中进行的，不需要在系数矩阵A中去寻找，从而给运输问题求初始基可行解带来极大的方便。5.1运输模型16表5-5BjAiB1B2B3B4aiA1c11c12c13c14a1x11x12x13x14A2c21c22c23c24a2x21x22x23x24A3c31c32c2c34a3x31x32x33x34bjb1b2b3b4例如，m=3,n=4，将xij与运价Cij放在同一张表中，如表5-5所示。5.1运输模型17这个运输问题的基变量数目是3+4－1=6。因此，变量组中有7个变量，不能构成一组基变量，又如：中有6个变量，但包含有一条闭回路故不能构成一组基变量。变量组有6个变量且不含有任何闭回路，故可以构成此问题的一组基变量。5.1运输模型18本节介绍了具有m个产地n个销地的平衡运输问题时：1.具有m+n－1个基变量2.闭回路的概念3.怎样判断m+n－1个变量是否构成一组基变量作业：教材习题5.5，仅建立数学模型5.1运输模型19小结：5.2运输单纯形法TransportationSimplexMethod2021设平衡运输问题的数学模型为：5.2运输单纯形法运输单纯形法也称为表上作业法，是直接在运价表上求最优解的一种方法，它的步骤是：第一步：求初始基行可行解（初始调运方案）。常用的方法有最小元素法、元素差额法（Vogel近似法）、左上角法。第二步：求检验数并判断是否得到最优解。常用求检验的方法有闭回路法和位势法，当非基变量的检验数λij全都非负时得到最优解，若存在检验数λlk<0，说明还没有达到最优，转第三步。第三步：调整运量，即换基。选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步。5.2运输单纯形法225.2.1初始基可行解1.最小元素法：最小元素法的思想是就近优先运送，即最小运价Cij对应的变量xij优先赋值然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后得到一个初始基可行解。5.2运输单纯形法23【例5-3】求表5－6所示的运输问题的初始基可行解。表5－6销地产地B1B2B3B4产量A1A2A39723610859412705020销量106040301405.2运输单纯形法24BjAiB1B2B3B4产量A1938

470A2765

150A32109

220销量10604030140表5－7解：30××10×××1060×20105.2运输单纯形法2526得到一组基可行解矩阵：表示，矩阵X中空白处对应的变量是非基变量，运量等于零，这组解就是初始调运方案。总运费：Z=3×60+8×10+5×20+1×30+2×10+9×10=5005.2运输单纯形法例5-4：求表5-8给出的运输问题的初始基本可行解。

B1B2B3B4aiA14104420A2773815A31210615bj510251050表5-85.2运输单纯形法27表5-9BjAiB1B2B3B4aiA14104420A2773815A31210615bj510251050解：5××10××××015×10105.2运输单纯形法28初始基本可行解可用下列矩阵表示5.2运输单纯形法292．元素差额法（Vogel近似法）最小元素法只考虑了局部运输费用最小。有时为了节省某一处的运费，而在其它处可能运费很大。元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运。例如下面两种运输方案。前一种按最小元素法求得，总运费是Z1=10×8+5×2+15×1=105后一种方案考虑到C11与C21之间的差额是8－2=6，先调运x21，再是x22，其次是x12这时总运费Z2=10×5+15×2+5×1=85<Z1。5.2运输单纯形法30基于以上思路，元素差额法求初始基本可行解的步骤是：第一步：求出每行次小运价与最小运价之差，记为ui，i=1,2,…,m；同时求出每列次小运价与最小运价之差，记为vj，j=1，2，…，n；第二步：找出所有行、列差额的最大值，即L=max{ui，vi}，差额L对应行或列的最小运价处优先调运；第三步：这时必有一列或一行调运完毕，在剩下的运价中再求最大差额，进行第二次调运，依次进行下去，直到最后全部调运完毕，就得到一个初始调运方案。用元素差额法求得的基本可行解更接近最优解，所以也称为近似方案。5.2运输单纯形法31表5-10例5-5：用元素差额法求表5-10运输问题的初始基本可行解。解：求行差额ui,i=1,2,3及列差额vj,j=1,2,3,4.计算公式为ui=i行次小运价—i行最小运价vj=j列次小运价—j例最小运价销地产地B1B2B3B4产量A1A2A39723610859412705020销量106040301405.2运输单纯形法32表5—11BjAiB1B2B3B4aiuiA19384701A27651504A321092207bj10604030140vj5331【】10××5.2运输单纯形法33表5-1210××BjAiB1B2B3B4aiuiA19384701×A27651504×A32109220710bj10604030140vj－331【】5.2运输单纯形法3435BjAiB1B2B3B4aiuiA19384701×A27651504×A32109220－10××10bj10604030140vj－333表5-13【】×205.2运输单纯形法表5-14【】603010×BjAiB1B2B3B4aiuiA19384705××A27651501×20A32109220－10××10bj10604030140vj－33－5.2运输单纯形法36基本可行解为总运费Z=3×60+8×10＋5×30+1×20+2×10+2×10=470比最小元素法的总运费（500）要小303.左上角法。左上角法(亦称西北角法)是优先从运价表的左上角的变量赋值，当行或列分配完毕后，再在表中余下部分的左上角赋值，依次类推，直到右下角元素分配完毕。当出现同时分配完一行和一列时，仍然应在打“×”的位置上选一个变量作基变量，以保证最后的基变量数等于m+n－15.2运输单纯形法37例5-6用左上角法求例5-3中表5-6的初始基本可行解表5-1510××60×0×1020BjAiB1B2B3B4产量A1938

470A2765

150A32109

220销量1060403040××5.2运输单纯形法3839基本可行解为用左上角法求得的基本可行解对应的目标函数值（总运费）是Z＝9×10＋3×60＋8×0＋5×40＋1×10+2×20=5205.2运输单纯形法求出一组基可行解后，判断是否为最优解，仍然是用检验数来判断，记xij的检验数为λij，求最小值的运输问题的最优判别准则是：所有非基变量的检验数都非负，则运输方案最优（即为最优解）。求检验数的方法有两种:闭回路法和位势法。1．闭回路法求检验数求某一非基变量的检验数的方法是：在基本可行解矩阵中，以该非基变量为起点，以基变量为其它顶点，找一条闭回路，由起点开始，分别在顶点上交替标上代数符号+、-、+、-、…，以这些符号分别乘以相应的运价，其代数和就是这个非基变量的检验数。5.2.2求检验数5.2运输单纯形法40解：用最小元素法求得的初始可行运输方案例5-7:用闭回路法求例5-3的检验数。BjAiB1B2B3B4产量A1938

470A2765

150A32109

220销量1060403014030××10×××1060×2010表5－165.2运输单纯形法41矩阵中打“×”的位置是非基变量，其余是基变量，这里只求非基变量的检验数。求λ11，先找出x11的闭回路，对应的运价为再用正负号分别交替乘以运价有直接求代数和得5.2运输单纯形法42BjAiB1B2B3B4aiA1938470×6010×A2765150××2030A3210922010×10×bj1060403080966-343同理可求出其它非基变量的检验数：这里λ34<0，说明这组基本可行解不是最优解。只要求得的基变量是正确的且数目为m+n－1，则某个非基变量的闭回路存在且唯一，因而检验数唯一。5.2运输单纯形法442．位势法求检验位势法求检验数是根据对偶理论推导出来的一种方法。设平衡运输问题为设前m个约束对应的对偶变量为ui,i=1,2,…,m，后n个约束对应的对偶变量为vj,j=1,2,…,n则运输问题的对偶问题是5.2运输单纯形法45加入松驰变量λij将约束化为等式ui+vj+λij=cij记原问题基变量XB的下标集合为I，由对偶性质知，原问题xij的检验数是对偶问题的松弛变量λij当（i，j）∈I时λij=0，因而有解上面第一个方程，将ui、vj代入第二个方程求出λij5.2运输单纯形法46例5-8：用位势法求例5-3给出的初始基本可行解的检验数。解：第一步求位势u1、u2、u3及v1、v2、v3、v4。10604030令u1=0得到位势的解为5.2运输单纯形法47再由公式求出检验数，其中Cij是非基变量对应的运价。计算结果与例5-7结果相同。5.2运输单纯形法485.2.3调整运量当某个检验数小于零时，基可行解不是最优解，总运费还可以下降，这时需调整运输量，改进原运输方案，使总运费减少，改进运输方案的步骤是：第一步：确定进基变量第二步：确定出基变量在进基变量xik的闭回路中，标有负号的最小运量作为调整量θ，θ对应的基变量为出基变量，并打上“×”以示作为非基变量。第三步：调整运量在进基变量的闭回路中标有正号的变量加上调整量θ，标有负号的变量减去调整量θ，其余变量不变，得到一组新的基可行解，然后求所有非基变量的检验数重新检验。5.2运输单纯形法49BjAiB1B2B3B4aiA1589270×40×30A236478045×35×A3101214540×2515×bj45655030190例5-9：求下列运输问题的最优解表5-17解：用最小元素法求得初始基本可行解如表5-175.2运输单纯形法50求非基变量的检验数,用闭回路法得：BjAiB1B2B3B4aiA1589270×40×30A236478045×35×A3101214540×2515×bj456550301905.2运输单纯形法51因为有4个检验数小于零，所以这组基本可行解不是最优解。对应的非基变量x11进基.对应的非基变量x11进基.x11的闭回路是x33最小，x33是出基量，调整量θ=15BjAiB1B2B3B4aiA1589270×40×30A236478045×35×A3101214540×2515×bj4565503019052BjAiB1B2B3B4ai30A236478030×50×A3101214540×40××bj45655030190在x11的闭回路上x11、x32、x23分别加上15，x12、x33、x21分别减去15，并且在x33处打上记号“×”作为基变量，其余变量不变，调整后得到一组新的基可行解：5.2运输单纯形法53BjAiB1B2B3B4ai30A236478030×50×A3101214540×40××bj45655030190重新求所有非基变量的检验数得λ13=3，λ22=0，λ24=7，λ31=1，λ33=4，λ34=－1λ34=－1<0,说明还没有得到最优解，x34进基，在x34的闭回路中，标负号的变量x14和x32，调整量为5.2运输单纯形法54BjAiB1B2B3B4ai×A236478030×50×A3101214540×10×30bj45655030190x14出基，调整运量得到：再求非基变量的检验数：λ13=3，λ14=1，λ22=0，λ24=8，λ31=1，λ33=45.2运输单纯形法55所有检验数λij≥0因而得到最优解最小运费5.2运输单纯形法56设数学模型为5.2.4最大值问题5.2运输单纯形法57第一种方法：将极大化问题转化为极小化问题。设极大化问题的运价表为C=（Cij）m×n，用一个较大的数M（M≥max{Cij}）去减每一个Cij得到矩阵C′=（C′ij）m×n，其中C/ij=M－Cij≥0,将C/作为极小化问题的运价表，用表上用业法求出最优解，目标函数值为例如，下列矩阵C是Ai（I=1，2，3）到Bj的吨公里利润,运输部门如何安排运输方案使总利润最大.81495.2运输单纯形法58用最小元素法求初始方案得λ11=8,λ12=4,λ21=2,λ23=2全部非负,得到最优运输方案X,最大利润：Z=8×9+10×10+6×8+5×4=2405.2运输单纯形法5960第二种方法:所有非基变量的检验数λij≤0时最优.求初始运输方案可采用最大元素法.如上例,用最大元素得到的初始运输方案:8149求检验数:λ11=－8,λ12=－4,λ21=－2,λ23=－2,全部非正,得到最优解运输方案,结果与第一种方法相同.5.2运输单纯形法当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。1.当产大于销时,即数学模型为5.2.5不平衡运输问题5.2运输单纯形法61由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，库存量为xi，n+1（i=1，2，…，m），总的库存量为5.2运输单纯形法6263bn+1作为一个虚设的销地Bn+1的销量。各产地Ai到Bn+1的运价为零，即Ci，n+1=0,（i=1，…，m）。则平衡问题的数学模型为：具体求解时，只在运价表右端增加一列Bn+1，运价为零,销量为bn+1即可5.2运输单纯形法642.当销大于产时,即数学模型为5.2运输单纯形法由于总销量大于总产量,故一定有些需求地不完全满足,这时虚设一个产地Am+1，产量为xm+1,j是Am+1运到Bj的运量，也是Bj不能满足需要的数量。Am+1到Bj的运价为零,即Cm+1,j=0(j=1,2,…,n)5.2运输单纯形法6566销大于产平衡问题的数学模型为：具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为am+1即可。5.2运输单纯形法例5-10：在下面运输问题中，假定B1的需要量是20到60之间，B2的需要量是50到70，试求极小化问题的最优解。B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20～6050～703545180150～2105.2.6需求量不确定的运输问题5.2运输单纯形法6768分析：

（1）总产量为180。而B1，…，B4的最低需求量20+50+35+45=150，这时属产大于销；（2）B1，…，B4的最高需求是60+70+35+45=210，这时属销大于产虚设一个产地A5，产量是210－180=30，A5的产量只能供应B1或B2。（3）将B1与B2各分成两部分的需求量是20，的需求量是40，的需求量分别是50与20，因此必须由A1，…，A4供应，可由A1、…、A5供应。（4）上述A5不能供应某需求地的运价用大M表示，A5到的运价为零。得到下表的产销平衡表。5.2运输单纯形法69B3B4aiA155992360A2MM447840A333664230A44488101150A5M0M0MM30bj204050203545210得到这样的平衡表后，计算得到最优方案见下表。5.2运输单纯形法

B3B4aiA1

352560A2

40

40A30

10

2030A42030

50A5

10

20

30bj204050203545210

表中：x131=0是基变量,说明这组解是退化基本可行解,空格处的变量是非基变量。B1，B2，B3，B4实际收到产品数量分别是50，50，35和45个单位。5.2运输单纯形法705.2.7中转问题产地销地A120A230A350A920A815A720A645354231682329图5.2A4A522715中转地34135.2运输单纯形法71设xij为Ai到Aj的运量，i，j=1，2，…，m+n+r。则中转运输问题的数学模型为产大于销时将式(5-3a)改为“≤”约束，销大于产时将式(5-3c)改为“≤”约束。5.2运输单纯形法72作业：教材习题5.3本节讲解了平衡运输问题的求解方法：运输单纯形法1.求初始运输方案，用最小元素法、元素差额法（Vogel近似法）2.求检验数，用闭回路法和位势法3.调整运量，用闭回路法4.极大值问题的求解方法、不平衡问题、需求量不确定问题（建模）5.2运输单纯形法73小结：5.3指派问题Assignmentproblem745.3指派问题例5-11：人事部门欲安排四人到四个不同的岗位工作，每个岗位一个人．经考核四人在不同岗位的成绩（百分制）如表所示，如何安排他们的工作使总成绩最好。工作人员ABCD甲85927390乙95877895丙82837990丁86908088【解】设5.3.1数学模型75数学模型为甲乙丙丁ABCD图5.35.3指派问题76指派问题的一般描述：假设m个人恰好