运筹学04-运输问题

1

运筹学第五章

运输问题

TransportationProblems2

本章内容重点运输模型数学模型表上作业法运输模型的应用3人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的生产量和需要量及各地之间的运输费用，如何制定一个运输方案，使总的运输费用最小。这样的问题称为运输问题。实际背景4运输问题举例某公司有三个生产设施分别位于杜鲁斯

(DL),

纳瑞多(LR),和坦帕(TP),三个仓库分别位于摩德斯托(MD),奥玛哈(OM)和波斯顿(BS)。各个工厂的生产能力不同，每个仓库的需求也不同。对于给出的不同的生产和运输成本，如何编制运输方案才能使总成本最小？5运输模型方法举例DL生产能力：100单位TP生产能力：300单位LR生产能力：300单位工厂位置6MD需求：300单位BS需求：200单位OM需求：200单位DL生产能力：100单位LR生产能力：300单位TP生产能力：300单位运输模型方法举例仓库位置7DL生产能力：100单位TP生产能力：300单位BS需求：200单位OM需求：200单位LR生产能力：300单位运输模型方法举例从坦帕发货MD需求：300单位8DL生产能力：100单位MD需求：300单位TP生产能力：300单位BS需求：200单位OM需求：200单位LR生产能力：300单位运输模型方法举例从杜鲁斯发货9DL生产能力：100单位MD需求：300单位TP生产能力：300单位BS需求：200单位OM需求：200单位LR生产能力：300单位运输模型方法举例从纳瑞多发货10DL生产能力：100单位MD需求：300单位TP生产能力：300单位BS需求：200单位OM需求：200单位©1984-1994T/MakerCo.LR生产能力：300单位运输模型方法举例$5$3$4$7$8$9$5$4$3每条路线上应当运多少以实现最低成本?11运输问题的表格

仓库生产工厂MDOMBS供应量DL534100LR834300TP957300需求量30020020012产销平衡运输问题的一般数学模型设有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个销地的运量，则数学模型为：13设平衡运输问题的数学模型为：运输问题的特点：1.有m+n个约束，mn个变量2.特殊的系数矩阵3.有m+n－1个基变量4.运输问题一定存在可行解，也一定存在最优解

14m行n行15故r(A)=m+n－1所以运输问题有m+n－1个基变量。为了在mn个变量中找出m+n－1个变量作为一组基变量，就是要在A中找出m+n-1个线性无关的列向量，也即是在运输表格中确定m+n-1个格的运输量不为零，而剩下的(m-1)(n-1)格为零。16运输单纯形法

表上作业法17设平衡运输问题的数学模型为：18运输单纯形法也称为表上作业法，是直接在运价表上求最优解的一种方法，它的步骤是：

第一步：求初始基行可行解（初始调运方案）。常用的方法有最小元素法、元素差额法（Vogel近似法）。

第二步：求检验数并判断是否得到最优解。常用求检验的方法有闭回路法和位势法，当非基变量的检验数λij全都非负时得到最优解，若存在检验数λlk<0，说明还没有达到最优，转第三步。

第三步：调整运量，即换基。选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步。19初始基可行解1.最小元素法最小元素法的思想是就近优先运送，即最小运价Cij对应的变量xij优先赋值然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后得到一个初始基可行解。20【例】求表所示的运输问题的初始基可行解。销地产地B1B2B3产量A1A2A3847634758304525销量60301010021

BjAiB1B2B3产量A186730A243545A374825销量603010100【解】30××15×10×252022【例】求表给出的运输问题的初始基本可行解．

B1B2B3B4aiA14104420A2773815A31210615bj51025105023

BjAiB1B2B3B4aiA14104420A2773815A31210615bj510251050【解】5××10××××015×101024初始基本可行解可用下列矩阵表示表5－11中，基变量恰好是3+4－1=6个且不包含闭回路，是一组基变量，其余标有符号×的变量是非基变量252．元素差额法（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。26基于以上思路，元素差额法求初始基本可行解的步骤是：第一步：求出每行次小运价与最小运价之差，记为ui，i=1,2,…,m；同时求出每列次小运价与最小运价之差，记为vj，j=1，2，…，n；第二步：找出所有行、列差额的最大值，即L=max{ui，vi}，差额L对应行或列的最小运价处优先调运；

第三步：这时必有一列或一行调运完毕，在剩下的运价中再求最大差额，进行第二次调运，依次进行下去，直到最后全部调运完毕，就得到一个初始调运方案。用元素差额法求得的基本可行解更接近最优解，所以也称为近似方案。27B1B2B3B4aiA15891215A2172425A361013820bj201052560【例】用元素差额法求表5—13运输问题的初始基本可行解。【解】求行差额ui,i=1,2,3及列差额vj,j=1,2,3,4.计算公式为

ui=i行次小运价—i行最小运价

vj=j列次小运价—j例最小运价28

BjAiB1B2B3B4aiuiA158912153A21724251A3610138202bj201052560vj4174【】5××29

BjAiB1B2B3B4aiuiA158912153×A217242535A3610138202×bj201052560vj41－420×××0【】×30

BjAiB1B2B3B4aiuiA158912154×A2172425－5A3610138202×bj201052560vj－2－420×××0【】10×20531基本可行解为总运费Z=10×8+20×1+5×2+20×8=270。32求出一组基可行解后，判断是否为最优解，仍然是用检验数来判断，记xij的检验数为λij由第一章知，求最小值的运输问题的最优判别准则是：所有非基变量的检验数都非负，则运输方案最优（即为最优解）。求检验数的方法有两种，闭回路法和位势法。1．闭回路法求检验数求某一非基变量的检验数的方法是：在基本可行解矩阵中，以该非基变量为起点，以基变量为其它顶点，找一条闭回路，由起点开始，分别在顶点上交替标上代数符号+、-、+、-、…，以这些符号分别乘以相应的运价，其代数和就是这个非基变量的检验数。求检验数33为一个闭回路，集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边。

x25

x23

B1B2B3B4B5A1

A2

A3

x35A4

x43

x11x12x31

x42表3－3表3－3中闭回路的变量集合是{x11,x12,x42,x43,x23,x25,x35,x31}共有8个顶点，这8个顶点间组成一条封闭的回路。34x11x12x32x33x41

B1B2B3A1

A2

A3

A4

x43闭回路的几何特征：

1、相邻两个顶点的连线都是水平的或者竖直的。2、每个顶点都是直角的拐角点。回路遇到顶点必须转90度与另一顶点连接3、每一行每一列只要存在某一闭回路的顶点，则必有该闭回路的两个顶点4、一条回路中的顶点数一定是4或4以上的偶数35【定理2】若变量组B

包含有闭回路，则B中的变量对应的例向量线性相关。【证】由线性代数知，向量组中部分向量组线性相关则该向量组线性相关，显然，将C中列向量分别乘以正负号线性组合后等于零，即因而C中的列向量线性相关，所以B中列向量线性相关。从每一个空格出发一定存在和可以找到唯一的闭回路36【解】用最小元素法得到下列一组基本可行解【例】求下列运输问题的一个初始基本可行解及其检验数。矩阵中的元素为运价Cij

，矩阵右边的元素为产量ai

，下方的元素为销量bj

。37矩阵中打“×”的位置是非基变量，其余是基变量，这里只求非基变量的检验数。求λ11，先找出x11的闭回路，对应的运价为再用正负号分别交替乘以运价有直接求代数和得38

BjAiB1B2B3B4aiA1938470×6010×A2765150××2030A3210922010×10×bj1060403080966-339同理可求出其它非基变量的检验数：这里λ34<0，说明这组基本可行解不是最优解。只要求得的基变量是正确的且数目为m+n－1，则某个非基变量的闭回路存在且唯一，因而检验数唯一。402．位势法求检验位势法求检验数是根据对偶理论推导出来的一种方法。设平衡运输问题为设前m个约束对应的对偶变量为ui,i=1,2,…,m，后n个约束对应的对偶变量为vj,j=1,2,…,n则运输问题的对偶问题是41加入松驰变量λij将约束化为等式ui+vj+λij=cij记原问题基变量XB的下标集合为I，由第二章对偶性质知，原问题xij的检验数是对偶问题的松弛变量λij当（i，j）∈I时λij=0，因而有解上面第一个方程，将ui、vj代入第二个方程求出λij42【例】用位势法求例7给出的初始基本可行解的检验数。【解】第一步求位势u1、u2、u3及v1、v2、v3、v4。10604030令u1=0得到位势的解为43再由公式求出检验数，其中Cij是非基变量对应的运价。44调整运量前面讲过，当某个检验数小于零时，基可行解不是最优解，总运费还可以下降，这时需调整运输量，改进原运输方案，使总运费减少，改进运输方案的步骤是：第一步：确定进基变量第二步：确定出基变量在进基变量xik的闭回路中，标有负号的最小运量作为调整量θ，θ对应的基变量为出基变量，并打上“×”以示作为非基变量。第三步：调整运量在进基变量的闭回路中标有正号的变量加上调整量θ，标有负号的变量减去调整量θ，其余变量不变，得到一组新的基可行解，然后求所有非基变量的检验数重新检验。45

BjAiB1B2B3B4aiA1589270×40×30A236478045×35×A3101214540×2515×bj45655030190【例】求下列运输问题的最优解【解】用最小元素法求得初始基本可行解如表46求非基变量的检验数,用闭回路法得：

BjAiB1B2B3B4aiA1589270×40×30A236478045×35×A3101214540×2515×bj4565503019047因为有4个检验数小于零，所以这组基本可行解不是最优解。对应的非基变量x11进基.对应的非基变量x11进基.x11的闭回路是x33最小，x33是出基量，调整量θ=15

BjAiB1B2B3B4aiA1589270×40×30A236478045×35×A3101214540×2515×bj4565503019048

BjAiB1B2B3B4ai30A236478030×50×A3101214540×40××bj45655030190在x11的闭回路上x11、x32、x23分别加上15，x12、x33、x21分别减去15，并且在x33处打上记号“×”作为非基变量，其余变量不变，调整后得到一组新的基可行解：49

BjAiB1B2B3B4ai30A236478030×50×A3101214540×40××bj45655030190重新求所有非基变量的检验数得λ13=3，λ22=0，λ24=7，λ31=1，λ33=4，λ34=－1λ34=－1<0,说明还没有得到最优解，x34进基，在x34的闭回路中，标负号的变量x14和x32，调整量为50

BjAiB1B2B3B4ai×A236478030×50×A3101214540×10×30bj45655030190x14出基，调整运量得到：再求非基变量的检验数：λ13=3，λ14=1，λ22=0，λ24=8，λ31=1，λ33=451再求非基变量的检验数：λ13=3，λ14=1，λ22=0，λ24=8，λ31=1，λ33=4所有检验数λij≥0因而得到最优解最小运费52解的几种情况无穷多：某个空格的检验数为0退化解：退化的格中必须要填一个0，表示是数字格53

当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。1.当产大于销时,即数学模型为不平衡运输问题54由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，库存量为xi，n+1（i=1，2，…，m），总的库存量为55bn+1作为一个虚设的销地Bn+1的销量。各产地Ai到Bn+1的运价为零，即Ci，n+1=0,（i=1，…，m）。则平衡问题的数学模型为：具体求解时,只在运价表右端增加一列Bn+1，运价为零,销量为bn+1即可562.当销大于产时,即数学模型为57由于总销量大于总产量,故一定有些需求地不完全满足,这时虚设一个产地Am+1，产量为xm+1,j是Am+1运到Bj的运量，也是Bj不能满足需要的数量。Am+1到Bj的运价为零,即Cm+1,j=0(j=1,2,…,n)58销大于产平衡问题的数学模型为：具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为am+1即可。59B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20603545180160因为有：【例】求下列表中极小化运输问题的最优解。

所以是一个产大于销的运输问题。60表中A2不可达B1，用一个很大的正数M表示运价C21。虚设一个销量为b5=180－160=20的销地B5，Ci5=0，i=1，2，3，4。表的右边增添一列这样可得新的运价表：B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj206035452018061B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj2060354520180下表为计算结果。可看出：产地A4还有20个单位没有运出。62上例中，假定B1的需要量是20到60之间，B2的需要量是50到70，试求极小化问题的最优解。B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20～6050～703545180150～210需求量不确定的运输问题63先作如下分析：

（1）总产量为180，B1，…，B4的最低需求量

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

B3B4aiA1

352560A2

40

40A30

10

2030A42030

50A5

10

20

30bj204050203545210

表中：x131=0是基变量,说明这组解是退化基本可行解,空格处的变量是非基变量。B1，B2，B3，B4实际收到产品数量分别是50，50，35和45个单位。66运输模型的应用67DF公司在接下来的三个月内每月都要按照销售合同生产出两种产品。表中给出了在正常时间（RegularTime，缩写为RT）和加班时间（OverTime，缩写为OT）内能够生产这两种产品的总数。月最大生产总量产品1/产品2销售产品1/产品2单位生产成本(1000元/件)单位储存成本（1000元/件）RTOTRTOT123108103235/33/54/415/1617/1519/1718/2020/1822/221/22/1（1）对这个问题进行分析，描述成一个运输问题的产销平衡表，使之可用运输单纯形法求解．（2）建立总成本最小的数学模型并求出最优解68【解】表中括号内的数据为产品序号

i↓j→123456生产能力ai1月(1)1月(2)2(1)2(2)3(1)3(2)11月RTx11x12x13x14

x15x161021月OTx21x22x23x24x25x26332月RTx33x34x35x36842月OTx43x44x45x46253月RTx55x561063月OTx65x663需要量bj533544691月(1)1月(2)2(1)2(2)3(1)3(2)剩余能力生产能力1月RT15