现代物流运筹学 教学课件 作者 沈家骅 24320-电子教案-第3章运输问题（TP）.ppt

《现代物流运筹学 教学课件 作者 沈家骅 24320-电子教案-第3章运输问题（TP）.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第3章运输问题（TP）学习目标了解运输问题模型的特点。掌握产销平衡运输问题的表上作业法。学会产销不平衡运输问题的转化。学习表上作业法在物流管理中的典型应用。运输问题的模型3.1运输问题的表上作业法3.2产销不平衡的运输问题3.3运输问题的应用案例3.4运输问题的Excel处理3.53.1运输问题的模型•有时候为了书写简便，运输问题也被写做TP（TransportationProblem）。•对某种物资，设有m个产地A1,A2,…,Am，称它们为发点，其对应产量为a1,a2,…,am，称它们为产量；另有n个销地B1,B2,…,Bn，称它们为收点

2、，其对应销量为b1,b2,…,bn，称它们为销量。•又知，从产地（发点）Ai运至销地（收点）Bj，该种物资每单位的运价为cij（cij≥0）。•试问：应如何安排调运方案，在满足一定要求的前提下，使总运费最低？•根据上述参量的意义列出产量、销量和运价，如表3.1所示。•表中：ai的单位为吨、千克、件等；bj的单位为吨、千克、件等；cij的单位为元/吨、元/千克、元/件等；即ai,bj,cij的单位类别应该一致（i= 1,2,…,m；j= 1,2,…,n）。•表的右下角表示各产地产量的总和，即总产量或总发量；表示各销地销量的总和，即总销量或总收量。•这时

3、有两种可能：•下面先讨论产销平衡问题，再讨论产销不平衡问题。•令xij表示某物资从发点Ai到收点Bj的调拨量（运输量），可以列出产销平衡表，如表3.2所示。•将表3.1与表3.2合在一起，得到一个新表，这一新表被称为运输表（或称为产销矩阵表），如表3.3所示。•根据产销矩阵表，求上述问题的解等于求下面数学模型的解。xij（i= 1,2,…,m；j= 1,2,…,n）•从上述这一特殊的线性规划（LP）问题，可以得到下列三条结论。（1）该问题的基变量有m + n −1个。（2）该问题一定有最优解。（3）如果ai和bj全是整数，则该问题一定有整数最优解。3

4、.2运输问题的表上作业法3.2.1产销平衡运输问题的表上作业法•利用表上作业法求解运输问题时，与单纯形法类似，首先要求出一个初始方案（即线性规划问题的初始基本可行解）。•一般来讲这个方案不一定是最优的，因此需要给出一个判别准则，并对初始方案进行调整、改进。•每进行一次调整，我们就得到一个新的方案（基本可行解），而这个新方案一般比前一个方案要合理些，也就是对应的目标函数z值比前一个方案要小些。•经过若干次调整，我们就得到一个使目标函数达到最小值的方案—最优方案（最优解），而这些过程都可在产销矩阵表（运输表）上进行，故称为表上作业法。•例3.1设有3个产

5、煤基地A1、A2、A3，4个销煤基地B1、B2、B3、B4，产地的产量、销地的销量以及从各产地至各销地煤炭的单位运价列于表3.4中，试求出使总运费最低的煤炭调拨方案。（1）列出运输问题的产销矩阵表。•其中：xij为产地Ai到销地Bj的运量（i= 1,2,3；j1,2,3,4），而将Ai到Bj的单位运价cij用小型字写在每格的右上角，以便直观地制定和修改调运方案。•从表3.5的数据可知，例3.1是个满足产销平衡条件的产销平衡问题。（2）初始方案确定的方法—最小元素法。•这样，我们便得到这样问题的一个初始基本可行解，即x11= 0x12= 0x13= 

6、4x14= 3x21= 3x22= 0x23= 1x24= 0x31= 0x32= 6x33= 0x34= 3•它所对应的目标函数z值为z= 3 × 0 + 11 × 0 + 3 × 4 + 10 × 3 + 1 × 3 + 9 × 0 + 2 × 1 +8 × 0 +7 × 0 + 4 × 6+10 × 0 + 5 × 3 = 86（万元）•因此，在应用最小元素法确定初始方案时，必须注意以下两点。①当选定最小元素（不妨假定为cst）后，如果发现该元素所在行的产地的产量as恰好等于它所在列的销地的销量bt（即as=bt），这时，可在产销矩阵表上xst

7、处填上一个数as，并画上圈。•为了保证调运方案中画圈的数字为m+n −1个，只能在s行的其他格子里都打上“×”（或在t列的其他格子里都打上“”），不可以同时把s行和t列的其他格子里都打上“×”。②当最后只剩下一行（或一列）还存在没有填数和打“×”的格子时，规定只允许填数，不允许打“×”，其目的也是为了保证画圈数字的个数恰为m+n −1个。•在特殊情况下可填“0”并画上圈，这个“0”应与其他画圈的数字同样看待。•（不限于最后一行或最后一列）。•例如，在表3.7中，第一步的最小元素为c31= 1，在x31处填上数字min(13,19) = 13，并在x

8、11、x21处打上“×”。•第二步的最小元素为c32= 2，可在x32处填上数字min(6,6) = 6，并