运筹学课件08运输问题

1、本章重点本章重点第三章第三章 运输问题运输问题 产销平衡运输问题的数学模型产销平衡运输问题的数学模型 产销平衡运输问题的产销平衡运输问题的表上作业法表上作业法 本章内容本章内容运输问题的数学模型运输问题的数学模型表上作业法表上作业法运输问题的扩展运输问题的扩展1 1 运输问题的数学模型运输问题的数学模型bnb2b1需求量需求量BnB2B1 需方需方供方供方AmA2A1ama2a1供应量供应量nijjm1iiba供需平衡供需平衡运价运价1 1 运输问题的数学模型运输问题的数学模型bnb2b1需求量需求量BnB2B1 需方需方供方供方AmA2A1ama2a1供应量供应量nijjm1iibacmnc

2、m2cm1c2nc22c21c1nc12c11如何建立供需搭配，使总的运输费用最小？如何建立供需搭配，使总的运输费用最小？供供需需 平平衡衡表表数学模型数学模型设从设从Ai到到Bj的物资运量为的物资运量为xij ， n1jm1iijijxczmin产销平衡产销平衡运输问题的数学模型。运输问题的数学模型。n1jjm1iibaAi的产品全部的产品全部供应出去供应出去m, 2 , 1iaxin1jijn, 2 , 1jbxjm1iijBj的需求全的需求全部得到满足部得到满足n, 2 , 1j ;m, 2 , 1i0 xijm mn n 个变量，个变量，m+nm+n 个约束，独立的约束方程个约束，独立

3、的约束方程m+nm+n- -1 1 个，每个变量的系数是有个，每个变量的系数是有 2 2 个个 1 1、其它元、其它元素均为素均为 0 0 的向量。的向量。 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 mnm2m12n222111xxxxx xx xxn11211mn销销 产产 B1 B2 Bn 产产量量 c11 c12 c1n A1 x11 x12 x1n a1 c21 c22 c2n A2 x21 x22 x2n a2 cm1 cm2 cmn Am xm1 xm2 xmn am 销销量量 b1 b1 bn 平衡表、运价表和二为一：平衡表、运价表和二为一：销产B1B2Bn

4、产量A1x11x12x1na1A2x21x22x2na2Amxm1xm2xmnam销量b1b1bn约束条件或解可用产销平衡表表示约束条件或解可用产销平衡表表示: minjijijxczmin11 )n,j(bx)m,i (axmijijnjiij1 1 11 )n,j;m,i (xij11 0 uivj无约束无约束 （i=1,2, ,m;j=1,2, ,n)uivj设设u ui i,v,vj j为对偶变量，对偶问题模型为为对偶变量，对偶问题模型为nijjjm1iiivbuawmaxijjicvum个个 n个个2 2 表上作业法表上作业法计算步骤：计算步骤：(1) 找出初始调运方案。即在找出初始

5、调运方案。即在(mn)产销平衡表产销平衡表上给出上给出m+n- -1个数字格。个数字格。(最小元素法或差值法）最小元素法或差值法）(2) 求检验数。（闭回路法或位势法）求检验数。（闭回路法或位势法） 判别是否判别是否达到最优解。如已是最优解，则停止计算，否则达到最优解。如已是最优解，则停止计算，否则转到下一步。转到下一步。(3) 对方案进行改善，找出新的调运方案。（表上对方案进行改善，找出新的调运方案。（表上闭回路法调整）闭回路法调整）确定确定m+n-1个基变量个基变量 (4) (4) 重复（重复（2 2）、（）、（3 3），直到求得最优调运方案。），直到求得最优调运方案。空格空格 例例 运输

6、问题供需平衡表和运价表如下，求最优调运输问题供需平衡表和运价表如下，求最优调运方案。运方案。 供 需B1B2B3B4供应量（T）A13113107A219284A3741059需求量（T）3656最小元素法最小元素法销销 产产 B1 B2 B3 B4 产产量量 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 销销量量 3 6 5 6 314 633Z=4Z=43+33+310+310+31+11+12+62+64+34+35=865=86该方案总运费：该方案总运费：. 差额法差额法 分别计算各行、各列次小、最小运价的差额，分别计算各行、各列次小、最小运价的差

7、额，优先在最大差额处进行供需搭配。优先在最大差额处进行供需搭配。销 地产 地B1B2B3B4行 差 额A1A2A3317119432101085011列 差 额2513步骤：步骤：10 计算未划去行、列的差额；计算未划去行、列的差额； 20 找出最大差额对应的最小元素找出最大差额对应的最小元素cij进行供需分配；进行供需分配；30 在未被划去的行、列重新计算差额。在未被划去的行、列重新计算差额。 销销产产B1B2B3B4供量供量A17A24A39销量销量 3656 6B1B2B3B4行差额行差额A13113100A219281A3741051列差额列差额2513 销销产产B1B2B3B4供量供

8、量A17A24A3 9销量销量 3656 6B1B2B3B4行差额行差额A13113100A219281A3741052列差额列差额213 3 销销产产B1B2B3B4供量供量A17A24A3 9销量销量 3656 6B1B2B3B4行差额行差额A13113100A219281A374105列差额列差额212 3 3 销销产产B1B2B3B4供量供量A17A24A3 39销量销量 3656 6B1B2B3B4差额差额A13113107A219286A374105差额差额12 3 5 1 22.1 最优解的判别最优解的判别 （检验数的求法）（检验数的求法） 闭回路法闭回路法 闭回路：从空格出发顺

9、时针闭回路：从空格出发顺时针(或逆时针或逆时针)画水画水(或垂或垂直直)直线，遇到填有运量的方格直线，遇到填有运量的方格可转可转90，然后继续，然后继续前进，直到到达出发的空格所形成的闭合回路。前进，直到到达出发的空格所形成的闭合回路。调运方案的任意空格存在唯一闭回路。调运方案的任意空格存在唯一闭回路。 销销产产B1B2B3B4供量供量A1 5 27A23 14A3 6 39销量销量 3656差额法方案差额法方案2.1 最优解的判别最优解的判别 （检验数的求法）（检验数的求法） 闭回路法闭回路法 闭回路：从空格出发顺时针闭回路：从空格出发顺时针(或逆时针或逆时针)画水平画水平(或或垂直垂直)直

10、线，遇到填有运量的方格直线，遇到填有运量的方格可转可转90，然后继续，然后继续前进，直到到达出发的空格所形成的闭合回路。前进，直到到达出发的空格所形成的闭合回路。调运方案的任意空格存在唯一闭回路。调运方案的任意空格存在唯一闭回路。 销销产产B1B2B3B4供量供量A1 5 27A23 14A3 6 39销量销量 3656销销 产产 B1 B2 B3 B4 产产量量 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 销销量量 3 6 5 6 314 633最小元素法最小元素法+-+- x11为换入变量，为换入变量，x11增加增加1，运费的变化为，运费的变化为3-

11、 -1+2- -3=1。这个变化就是。这个变化就是x11的检验数，故的检验数，故 11=1 基变量的检验数为零基变量的检验数为零( 基变量基变量xij)， ij=cij-(ui+vj), ui,vj自由变量自由变量. 位势法位势法标准型运输问题的对偶问题是：标准型运输问题的对偶问题是： njjjmiiivbuamax11 )n,j;m,i (cvuijji11 XBXNXS0CN-CBB-1N-CBB-1-YS1-YS2-Y检验数检验数 得得m+n- -1个方程，令某个个方程，令某个ui ( 或或vj)=0，可解出，可解出m+n个个ui 和和vj；由此得非基变量的检验数。；由此得非基变量的检验

12、数。对偶变量值等于原问题对偶变量值等于原问题的检验数的检验数松弛变量松弛变量销销 产产 B1 B2 B3 B4 产产量量 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 销销量量 3 6 5 6 314 633位势法位势法 令令v1=0, 由由c21=1= u2 +v1，得，得 u2=1调调运运方方案案表表调调运运量量B1B2B3B4ui311310A11928A274105A3vj 0 1 1 2B1B2B3B4ui311310A11928A274105A3vj 0 1 1 28-3 7检验数表检验数表121-11012 24=-10，当前方案，当前方案

13、不是最优方案。不是最优方案。检检验验数数运运价价)(jiijijvuc检验数检验数21闭回路调整法改进方案闭回路调整法改进方案pqijj , i)(min 0 xpq为换入变量为换入变量 =min1，3=1 从从(p,q)(p,q)空格开始画闭回路，其它转角点都是空格开始画闭回路，其它转角点都是填有运量的方格，并从填有运量的方格，并从(p,q)(p,q)空格开始给闭回路上空格开始给闭回路上的点按的点按+1+1，-1-1，+1+1，-1-1编号，编号，-1-1格的最小运量格的最小运量为为调整量。调整量。换出变量换出变量销销地地 产产地地 B1 B2 B3 B4 产产量量 A1 A2 A3 3 6

14、 4(+1) 1(- -1) 3(- -1) (+1) 3 7 4 9 销销量量 3 6 5 6 运价运价 851186zz2401新的调运方案为：新的调运方案为：销销 地地 产产 地地 B1 B2 B3 B4 产产 量量 A1 A2 A3 3 6 5 2 1 3 7 4 9 销销 量量 3 6 5 6 销销 地地 产产 地地 B1 B2 B3 B4 产产 量量 A1 A2 A3 3 6 5 2 1 3 7 4 9 销销 量量 3 6 5 6 调运方案调运方案 需供B1B2B3B4uiA10210A2218A39125Vj -7-1-70713491110231085检验数表检验数表21 表上

15、作业法计算中的问题(1). 有无穷多最优解最终解中有非基变量检验数为零时，以此非基变量为换入变量，可求得另一基最优解。基最优解的任一凸组合都是最优解。如上例另一基最优解是：销地销地 产地产地 B1 B2 B3 B4 产量产量 A1 A2 A3 2 1 6 5 3 3 7 4 9 销量销量 3 6 5 6 (2). 退化 解中非零基变量个数小于 m+n-1 时，为退化解。求初始解时，当 minai，bj=ai =bj，在第 i 行或第 j 列任一空格上加 0；求改进解时，当 在 k( k 2)个格中达到，要在其中 k-1 个格中求 0。4 4 运输问题的扩展运输问题的扩展本本节节重重点点供需不平

16、衡的运输问题供需不平衡的运输问题供不应求供不应求供过于求供过于求转运问题转运问题一、供需不平衡的运输问题一、供需不平衡的运输问题1、供不应求的运输问题、供不应求的运输问题 平衡平衡 到站到站发站发站B1B2B3发量（发量（T）A150907055A285358055收量（收量（T）304060130 110虚设一个供应地，其虚供应量为供不应求部分。虚设一个供应地，其虚供应量为供不应求部分。虚设一个供应地虚设一个供应地A3，其供应量，其供应量=130-110=20 到站到站发站发站B1B2B3发量（发量（T）A150907055A285358055A3 20收量（收量（T）304060 130

17、0 0 0用最小元素法或差值法求初始方案。用最小元素法或差值法求初始方案。2、供过于求的运输问题、供过于求的运输问题虚设一个需求地，其需求量为供过于求部分。虚设一个需求地，其需求量为供过于求部分。例：设有三个化肥厂供应四个地区的农用化例：设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量、各地区需要量及从各同。各化肥厂年产量、各地区需要量及从各化肥厂到各地区运送单位化肥的运价如下表。化肥厂到各地区运送单位化肥的运价如下表。试求出总的运费最节省的化肥调拨方案。试求出总的运费最节省的化肥调拨方案。 销销产产1234产量产

18、量A1613221750B1413191560C192023- -50最低需求（万吨）最低需求（万吨）最高需求（万吨）最高需求（万吨）3050707003010不限不限解：转化为产销平衡的运输问题，虚设产解：转化为产销平衡的运输问题，虚设产地地D的产量为的产量为50，1 161419204 1715MD5050703060M003010050MM 销销产产1234产产量量A1613221750B1413191560C192023- -50需求需求M二、转运问题二、转运问题出现下列问题：出现下列问题：1. 产地与销地之间没有直达路线，货物由产地到销产地与销地之间没有直达路线，货物由产地到销地必须

19、通过中转站转运；地必须通过中转站转运；2. 某些产地可以输入货物，销地也可以输出货物，某些产地可以输入货物，销地也可以输出货物，3. 产地与销地之间虽然有直达运输线，但直达运输产地与销地之间虽然有直达运输线，但直达运输的费用（距离）比经过某些中转站的还要高。的费用（距离）比经过某些中转站的还要高。解法：解法：无转运问题。无转运问题。1. 根据问题求出最大可能周转量根据问题求出最大可能周转量Q；2. 纯转运点纯转运点产地：输出量产地：输出量Q；销地：输入量销地：输入量Q；3. 兼中转站的产地兼中转站的产地Ai=销地：输入量销地：输入量Q；产地：输出量产地：输出量Qi+ai；4. 兼中转站的销地兼中转站的销地Bj=销地：输入量销地：输入量bj+Q；产地：输出量产地：输出量Qi；列出各产地的输出量和各销地的输入量及各产列出各产地的输出量和各销地的输入量及各产销地之间的运价表，用表上作业法求解。销地之间的运价表，用表上作业法求解。例例 某货物，其产地某