第24讲-运输问题

《第24讲-运输问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、运输问题本讲主要介绍运输问题的表上作业求解法，要求同学掌握。介绍利用运输模型处理某些实际问题的例子。求解例8：运输问题A1，A2两个煤矿给B1，B2，B3三个城市供煤，各煤矿产量和各城市需求量以及各地之间的单位运价如下表所示：问应该如何调运，才能既满足城市需求，又使总运费最小？线性规划模型？煤矿日产量（吨）城市需求量（吨）A1A2200250B1B2B3100150200运价（元/吨）B1B2B3A1A29070100806580模型说明Xij：决策变量，表示从第i个产地Ai到第j个销地Bj的运输量.Cij:表示

2、从Ai到Bj的单位运价.ai:表示第i个产地Ai的产量。∑ai为总产量。bj:表示第j个销地Bj的销量.∑bj为总销量。注：i=1,2,…,mj=1,2,…,n表格形式的运输模型目标函数:MinZ=B1B2…Bn产量A1A2…AmC11C12…C1nC21C22…C2n……Cm1Cm2…Cmna1a2…am销量b1b2…bn例8的表格形式cijB1B2B3产量A1A29070100806580200250销量100150200450产=销关于运输问题运输问题一定有最优解。运输问题的约束方程组系数矩阵的秩为m+n-

3、1,其基可行解中基变量个数为m+n-1。什么是基可行解？基可行解是这样的可行解，它包含基变量和非基变量两个部分。其中，基变量取非负值，个数为m+n-1，其余为非基变量，都取零值。一个基可行解就是一个调运方案。产销平衡问题表上作业法基本步骤：（1）确定初始调运方案。（2）对方案进行最优性检验。（3）非最优方案的调整。（4）得到最优方案，停止计算。关于初始调运方案初始调运方案，即在m×n运输表上给出m+n-1个满足运量要求的数字格，其中数值代表从对应的产地到销地的运输量，叫做基变量，而其余的数字格一律取值为0，称为非

4、基变量。表上作业法中的每一个调运方案对应于运输问题的一个基可行解，初始调运方案又称初始基可行解。得到初始调运方案的方法有最小元素法，最大差额法西北角法等例8的初始调运方案利用最小元素法求初始调运方案（即初始基可行解）：基变量个数为m+n-1=2+3-1=490701008065802002501001502001500100200基变量：x12,x13,x21,x22；非基变量：x11,x23,关于最优性检验：位势法（1）求出当前调运方案的位势，即寻找一组数ui和vj满足ui+vj=Cij其中i,j是运输表中对应

5、于基变量的数字格。（2）计算非基变量对应的空格（i,j)的检验数ij：ij=Cij-（ui+vj）（3）判断：当目标函数要求最小化时，如果所有非基变量检验数都非负，则当前调运方案为最优方案；否则，须进行方案调整。注意：当目标函数要求最大化时，如果所有非基变量检验数都非正数，则当前调运方案为最优方案。例8初始调运方案的位势求位势：寻找一组数ui和vj满足ui+vj=Cij其中i,j是运输表中对应于基变量的数字格。90701008065802002501001502001500100200基变量：x12,x13,

6、x21,x22u1=70u2=65v2=0v3=30v1=15初始调运方案是否最优？计算非基变量对应的空格（i,j)的检验数ij：ij=Cij-（ui+vj）90701008065802002501001502001500100200非基变量：x11,x23u1=70u2=65v2=0v3=30v1=1511=90-（70+15）=5>0,23=80-（65+30）=-15<0,判断结果：由于23<0,因此当前方案非最优方案非最优调运方案的调整（1）当目标函数要求最小化时，选取某检验数为负数的空格为调入

7、格，即将非基变量调整为基变量。（2）从调入格出发寻找一条闭回路，方法为：沿水平或垂直方向行走，遇到基变量空格则转90°后继续前进，直到回到起始点为止。（3）在闭回路上作运量调整，调整量=min{各偶数顶点运量}将所有偶顶点运量减去，所有奇数顶点运量加上，得到调整后新的调运方案。例8：调运方案的调整由于23<0，选取检验数为负数的空格（2，3）为调入格，即将非基变量x23调整为基变量，给它运量从调入格出发寻找一条闭回路：x23→x22→x12→x13→x23调整量=min{各偶数顶点运量}=min{x

8、22，x13}=min{150，200}=15090701008065802002501001502001500100200运量调整：在闭回路上面进行，如表所示+150-150+150-150新调运方案的位势法检验计算非基变量对应的空格（i,j)的检验数ij：ij=Cij-（ui+vj）907010080658020025010015020015015010050u1