第3章-运输问题

1、 某种物资有若干产地和销地，现某种物资有若干产地和销地，现在需要把这种物资从各个产地运到在需要把这种物资从各个产地运到各个销地。已知各产地的各个销地。已知各产地的和各和各销地的销地的以及各产地到各销地的以及各产地到各销地的，问应如何组织调运，才，问应如何组织调运，才能使能使？例例1： 甲、乙两个煤矿供应甲、乙两个煤矿供应A、B、C三三个城市用煤，各煤矿产量（吨）及各个城市用煤，各煤矿产量（吨）及各城市需煤量（吨）、各煤矿到各城市城市需煤量（吨）、各煤矿到各城市的单位运价（元的单位运价（元/吨）见下表，求使总吨）见下表，求使总运费最少的调运方案。运费最少的调运方案。 200 150 100 日销

2、量（需求量吨） 250 75 65 80 乙 200 100 70 90 甲 日产量日产量（供应量吨）（供应量吨） C B A 单位运价单位运价 城市城市 煤矿煤矿数学模型数学模型; 3 , 2 , 1; 2 , 1, 0200150100250200. .7565801007090min231322122111232221131211232221131211jixxxxxxxxxxxxxt sxxxxxxZij需求约束日产量约束总运费设xij是从第i产地到第j销地的运输量，则：100100010010001001111000000111单位单位 运价运价 销销 地地产地产地B1 B2 Bn产

3、产 量量A1 A2 Amc11 c12 c1 n c21 c22 c2n cm1 cm2 cm na1 a2 am销销 量量 b1 b2 bn njmixnjbxmiaxtsxcMinZijmijijnjiijminjijij,1;,1,0,1,1.1111minjjiba11产销平衡条件 单纯形法单纯形法 表上作业法表上作业法（一）、确定初始调运方案（一）、确定初始调运方案（初始基本可行解）（初始基本可行解）； 方法：最小元素法、伏格尔（差值法）方法：最小元素法、伏格尔（差值法）（二）、求检验数判别是否为最优方案；（二）、求检验数判别是否为最优方案； 方法：闭回路法、位势法方法：闭回路法、位

4、势法（三）、若不是最优，则需要调整现有方案，以得（三）、若不是最优，则需要调整现有方案，以得到新的调运方案。到新的调运方案。 方法：闭回路调整方法：闭回路调整（四）、不断反复，最终得到最优调运方案。（四）、不断反复，最终得到最优调运方案。基本步骤：基本步骤：（一）、确定初始基本可行解1、最小元素法 最小元素法思路： 从单价中最小运价确定供应量 “就近供应”例2、某部门三个工厂生产同一产品的产量、 四个销售点的销量及单位运价如下表：41228543961111104814121482210163214321AAABBBB销量产量销地产地最小元素法4122854396111110481412148

5、2210163214321AAABBBB销量产量销地产地822010100614868000060最小元素法初始运输方案：41228543961111104814121482210163214321AAABBBB销量产量销地产地821014682466811632410514280z最小元素法缺点：会出现顾此失彼 （运价差额问题）考虑运价差 200 150 100 日销量（需求量吨） 250 75 65 80 乙 200 100 70 90 甲 日产量日产量（供应量吨）（供应量吨） C B A 单位运价单位运价 城市城市 煤矿煤矿例1：运输问题基本可行解的特点：运输问题基本可行解的特点： 45

6、0 200 150 100 日销量（需求量吨） 250 10075 1506580 乙 200 100100 70 10090 甲 日产量日产量（供应量吨）（供应量吨） C B A 单位运费单位运费 城市城市 煤矿煤矿特点分析：基变量（数字格）、非基变量（空格）特点分析：基变量（数字格）、非基变量（空格）运输问题基本可行解的特点：运输问题基本可行解的特点： X11X13X21X24X33 B1 B2 B3 B4 A1X12X14 A2X22X23 A3X31X32X34,313424231311xxxxxx X11X13X21X24X33 B1 B2 B3 B4 A1X12X14 A2X22X

7、23 A3X31X32X34,212434331311xxxxxx差额=次小运价-最小运价差额的解释：;差额大，则不按最小运费调运，运费增加大。差额大，则不按最小运费调运，运费增加大。;差额小，则不按最小运费调运，运费增加不大。差额小，则不按最小运费调运，运费增加不大。对差额最大处，采用最小运费调运。伏格尔法思路：2伏格尔法 结合例题说明这种方法。结合例题说明这种方法。4814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地行差04-4=0第一次第一次4814121482210163214321AAABBBB41228543961111

8、10销量产量销地销地产地产地行差013-2=1第一次第一次4814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地行差011第一次第一次4814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地行差011列差4-2=22153第一次第一次4814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地行差011列差21531480优先安排销地，否则运价会更高2B下次不考虑该列第一次第一次第二次第二次行差012列差213优先安排销地，

9、否则运价会更高4B84814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地148006下次不考虑该行行差01列差21284814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地148006下次不考虑该列802第三次第三次行差76列差1284814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地1480068024120下次不考虑该列第四次第四次行差00列差2284814121482210163214321AAABBBB4

10、122854396111110销量产量销地销地产地产地148006802412004第五次第五次4 用伏格尔法得到的初始基本可行解4814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地48148122244685149228114412z目标函数值目标函数值用最小元素法求出的目标函数z=246练习练习1：最小元素法、伏格尔法求初：最小元素法、伏格尔法求初始运输方案始运输方案.收收点点发发点点B1B2B3B4发发量量A16533414A24244756A376583 3收收量量243413 若在（i,j）格填入数字后，出现ai处的供应量

11、正好等于bj 处的需求量。这时在产销平衡表上填一个数，而在单位运价表上相应要划去一行和一列。为使产销平衡表上有（m+n-1）个数字格，需要添加一个“0”。它的位置可在对应同时划去的行或列得任一空格处。特殊情况处理： （判别定理：检验数全部大于或等于0，即为最优。检验数计算方法：检验数计算方法：ij例例1：在最小元素法确定的初始调运方案的基：在最小元素法确定的初始调运方案的基础上，计算非基变量的检验数础上，计算非基变量的检验数 ：1221例2：最小元素法得到的初始方案，试计算检验数。41228543961111104814121482210163214321AAABBBB销量产量销地产地8210

12、14682466811632410514280z闭回路法计算检验数41228543961111104814121482210163214321AAABBBB销量产量销地产地82101468211-11012,0124表中的解不是最优解。用伏格尔法得到的初始运输方案：4814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地48148122244685149228114412z目标函数值目标函数值41228543961111104814121482210163214321AAABBBB销量产量销地产地821214482209112闭回路法得

13、到检验数,0ij表中的解是最优解。初始调运方案位势变量对应表初始调运方案位势变量对应表 调调 销地销地 运运 量量产地产地 B1 B2 B3产产 量量 A1 90 X11=100 70 X12 100X13=100 200 A2 80 X21 65 X22=150 75X23=100 250 销销 量量 100 150 200 450位势变量位势变量vj v1 v2 v3100位势位势变量变量 ui u1 u27565100902332222213311111cvucvucvucvu例1中可得到方程组： 答案： （ij调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90

14、 X11=100 7012 = -20 100 X13=100 200 A2 80 21=15 65 X22=150 75 X23=100 250 销销 量量 100 150 200 450调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11=100 70X12 = 100 100 200 A2 80 65 X22=50 75 X23=200 250 销销 量量 100 150 200 450调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11=50 70 X12=150 100 X13 200 A2 80 X21=50 65 X

15、22 75 X23=200 250 销销 量量 100 150 200 450 得到了最优方案 单纯形法与表上作业法的对应关系：（1）找出初始基本可行解 （2）求各非基变量的检验数（3）判断是否最优解计算表中空格检验数表上给出m+n-1个数字格判断方法j0换基：（4）确定进基变量和出基变量，找出新的基本可行解。（5）重复（2）（4）直至求出最优解。表上调整（闭回路调整）（运输问题必有最优解）停止最优解？是否例2：表上作业法完整步骤41228543961111104814121482210163214321AAABBBB销量产量销地产地1、最小元素法41228543961111104814121

16、482210163214321AAABBBB销量产量销地产地821014682466811632410514280z2、检验数表41228543961111104814121482210163214321AAABBBB销量产量销地产地82101468211-11012,0124表中的解不是最优解。3、解的调整 调整位置（2，4）非空，回路角上的格至少为空，且保证数字的非负性。41228543961111104814121482210163214321AAABBBB销量产量销地产地82101468-1（-2）（-2）（+2）（+2） 调整后的解为：41228543961111104814121482210163214321AAABBBB销量产量销地产地8212144822091122246244689211441251428, 0zij此时的解为最优解。 观察检验数41228543961111104814121482210163214321AAABBBB销量产量销地产地821214482209112有多个最优解 另一最优运输方案为：41228543961111104814121482210163214321AAABBBB销量产量销地产地82121448（+4）（-4）（+4）（-4） 即：41228543961111104814121482210163214321AA