《运筹学运输问题》由会员分享，可在线阅读，更多相关《运筹学运输问题（55页珍藏版）》请在金锄头文库上搜索。
1、第四章 运输问题运输问题的表示网络图、线性规划模型、运输表初始基础可行解西北角法、最小元素法非基变量的检验数闭回路法、对偶变量法确定进基变量，调整运量，确定离基变量运输问题的提出运输问题的直接背景是单一品种的物质的运输调度问题，其典型情况是：设某物品有m个产地A1,A2,Am,各产地的产量分别为a1, a2, , am; n个销地B1, B2, , Bn,各销地的销量分别为b1, b2, , bn. 假定从产地Ai(i=1,2, ,m)向销地Bj(j=1, 2, , n) 运输单位物质的运价为cij, 问怎样调运这些物品才能使得总运费最小？运输问题的表示网络图A1A2Am产地B1B2Bn销地a
2、1a2amb1b2bnc11c12c1nc21c22c2ncm1cm2cmn若 则称该问题为平衡运输问题，否则称为非平衡运输问题。运输问题的表示表格表示这个表常称为运输表运输问题的数学模型平衡问题的数学模型为各产地运出的物资数量等于其产量各销地接受的物资数量等于其销量其中运输问题数学模型的特点运输问题一定存在最优解实际上 是平衡运输问题的一个可行解。此外由于目标函数有下界，因此平衡运输问题存在最优解。 运输问题系数矩阵的特点mn上述矩阵的列向量具有形式第i个第(m+j)个因此运输问题约束条件系数矩阵的元素只能是0或1，对应变量xij列除了第i个与第(m+j)个分量为1外，其它分量均为零此外产销
3、平衡运输问题的数学模型还具有特点：所有约束条件都是等式前m个约束条件的和等于后n个约束条件的和（可以证明尽管有m+n个约束条件，但独立的约束条件只有m+n-1个）运输问题的例子表格表示运输问题的例子线性规划模型供应地约束需求地约束运输问题的解运输问题的解运输问题的解可以表示为X=(xij), 它表示一个运输方案，其中xij表示从产地Ai到销地Bj 运送的物质数量在用运输表表示运输问题时，也常将xij取的值填入对应的格子表示一个解。但是对基可行解，通常仅将基变量取的值填入相应的格中，称之为数字格，而对应着非基变量的格子，则不填数字，称之为空格。注：在一个基可行解中，所有mn个变量（格子）中，只有
4、m+n-1个基变量（数字格）求解运输问题的表上作业法求初始基可行解（初始调运方案）西北角法最小元素法沃格尔法初始基可行解西北角法8864814初始基可行解初始基可行解最小元素法最小元素法82101486沃格尔（沃格尔（VogelVogel）法）法2（5）130111421（3）0128（2）1201812（7）61224检验数的计算两种方法：闭回路法和对偶变量法闭回路法的原理：非基变量的检验数等于非基变量增加一个单位时，目标函数的改变量检验数的计算闭回路法（1）821014861检验数的计算闭回路法（2）8210148612检验数的计算闭回路法（3）82101486121检验数的计算闭回路法（
5、4）82101486121-1检验数的计算闭回路法（5）82101486121-110检验数的计算闭回路法（6）82101486121-11012检验数的计算对偶变量法对偶变量法也称为位势法，它是利用运输问题的对偶问题求检验数。设运输问题的对偶变量矩阵为则对偶问题为利用单纯形法的矩阵表示可知，变量xij的检验数可以表示为另一方面，对于(m+n-1)个基变量而言，检验数等于零，故可以得到包含(m+n)个变量的(m+n-1)个方程由该方程组求出对偶变量后即可计算出所有的检验数。检验数的计算检验数的计算对偶变量法对偶变量法82101486u1=0v3=4v4=11u2=-1u3=-5v1=3v2=1
6、0121-11012解的改进82101486-1解的改进81214842解的改进81214842u1=0v3=4v4=11u2=-2u3=-5v1=4v2=100221912最优解（最优调运方案）81214842最小运费：表上作业法的几个问题换入变量的确定换入变量的确定退化（两种情况）退化（两种情况）无穷多个最优解的判别无穷多个最优解的判别产销不平衡的运输问题解决的基本思路：将其转化为产销平衡的运输问题求解产大于销的运输问题这时有，数学模型为，数学模型为处理的办法为增加一个假想的销地Bn+1，其销量为各个产地运送物质到假想销地的单位运价为零，即ci(n+1)=0假想的销地这时有，数学模型为销大
7、于产的运输问题处理的办法为增加一个假想的产地Am+1，其产量为假想产地运送物质到各个销地的单位运价为零，即c(m+1),1=0假想的产地表上作业法的计算步骤：分析实际问题列出产销平衡表及单位运价表确定初始调运方案（最小元素法或Vogel法）求检验数（位势法）所有检验数0找出绝对值最大的负检验数，用闭合回路调整，得到新的调运方案得到最优方案，算出总运价表上作业法计算中的问题：表上作业法计算中的问题：（1）若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代时，取它们中任一变量为换入变量均可使目标函数值得到改善，但通常取ijB3(15)A2-B1(18)A3-B2(12);B3(1);B
8、4(4)总费用93.但方案不唯一(浙大2005年研究生考题)第4组作业 某厂按合同规定须于当年每个季度末分别提供某厂按合同规定须于当年每个季度末分别提供15、20、30、25台同一规格的柴油机。已知该厂各季度台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用度需储存、维护等费用0.18万元。试求在完成合同万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方的情况下，使该厂全年生产总费用为最小的决策方案。案。季度季度生产能力生产能力/台台单位成本单位成本/万元万元30114011.33511.21511.5第五组P91页 4.4
