资源描述：
《lingo软件求解运输问题与表上作业法的比较》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、2010年6月湛江师范学院学报Jun1,2010第31卷第3期JOURNALOFZHANJIANGNORMALCOLLEGEVol131No13LINGO软件求解运输问题与表上作业法的比较张家善(湛江师范学院商学院,广东湛江524048)摘要:作为一类特殊的线性规划问题,运输问题的求解传统上采用表上作业法,但是其求解过程复杂、繁琐,求解维数受到很大限制.随着计算机技术的发展,LINGO软件在求解运输问题中逐步得到了广泛应用,该文通过实例求解,对两种求解方法进行了对比1关键词:运输问题;表上作业法;LINGO;对比中图分类号:
2、F252.5文献标识码:A文章编号:1006-4702(2010)03-0137-04作为一类特殊的线性规划问题,运输问题约束方程组的系数矩阵具有特殊的结构,传统上求解运输问题[1]多采用表上作业法.表上作业法是求解运输问题的一种简便的方法,实质仍是单纯形法.计算步骤如下:1)找出初始基可行解,即在产销平衡表上给出m+n-1个数字格.确定初始基可行解常用的方法:最小元素法和伏格尔法(Vogel).2)求各非基变量的检验数,即在表上计算空格的检验数,判别是否达到最优解.如果已是最优解,则停止计算,否则转入下一步.[2]但表上作
3、业法求解过程复杂、繁琐,求解维数也受到很大限制.随着计算机技术的发展,LINGO软件在求解运输问题中逐步取代了表上作业法.下面以一个运输问题为例,来比较表上作业法求解与使用LIN2GO软件求解的差异.1表上作业法求解设有5个产地A1、A2、A3、A4、A5和4个销地B1、B2、B3、B4的运输问题,他们的供应量和需求量及单位运费如表1,试求其最优运输规划及最小运输成本.(单位:百元;t)表1运费表B1B2B3B4供应量A110205710A213912820A34157930A41471040A531251950需求量606
4、02010150这是供需平衡问题,下面直接用最小元素法求出初始调运方案.在所有运价中,找出最小运价为0,该运价对应的需求量为10,供应量为40,即需求量可以得到全部满足.将调运数量和A4、B4的剩余供需数量在收稿日期:2010-03-25基金项目:湛江师范学院科研基金资助项目(QW0712)1作者简介:张家善(1979—),男,四川巴中人,湛江师范学院商学院教师,硕士,从事物流管理方面研究.©1994-2010ChinaAcademicJournalElectronicPublishingHouse.Allrightsres
5、erved.http://www.cnki.net138湛江师范学院学报(自然科学)第31卷表上做出记号,同时由于B4的需求已经满足,可以划去该列其他的各个运价.计算结果如表2所示:表2第1轮求解表表3初始调运方案表B1B2B3B4供应量B1B2B3B4A110205710A11020/1057A213912820A2139/20128A34157930A34/1015/2079A414710/1040/30A4147/101/200/10A531251950A53/5012519需求量60602010/0150以此类推,经
6、过8轮求解,求得初始调运方案如表3所示:即X12=10,X22=20,X31=10,X32=20,X42=10,X43=20,X44=10,X51=50;这只是运输问题的基可行解.在此,用位势法检验初始方案是否为最优.设有调运数量的运价Dij=Ui+Vj,i为行数,j为列数.可以列出如下方程组:20=U1+V2;9=U2+V2;4=U3+V1;15=U3+V2;7=U4+V2;1=U4+V3;0=U4+V4;3=U5+V1;设U4=0,分别求出U1～U5和V1～V4,如表4所示.表4第1轮检验表表5最优调运方案表B1B2B3
7、B4最优方案B1B2B3B4A11020/1057U1=13A110205/107A2139/20128U2=2A2139/20128A34/1015/2079U3=8A34/301579A4147/101/200/10U4=0A4147/3010/10A53/5012519U5=7A53/3012/105/1019V1=24V2=7V3=1V4=0设没有调运量的运价为Cij,如果Cij不小于Ui+Vj,检验通过;否则在该运价上做记号,等待下一步调整.以此类推,经过4轮调整后,通过检验,所有的Cij均大于Ui+Vj,此调运方
8、案为最优方案,如表5所示.求解结果:X13=10,X22=20,X31=30,X42=30,X44=10,X51=30,X52=10,X53=10;即产地1向销地3运输10t,产地2向销地2运输20t,产地3向销地1运输30t,产地4向销地2运输30t,产地4向销地4运输10t,产地5向销
