cs-关于运输问题表上作业法之研究

安徽大学数学科学学院《《《《运筹学》运筹学》运筹学》运筹学》期末论文期末论文期末论文期末论文论文题目：论文题目：论文题目：论文题目：关于关于关于关于运输问题表上作业运输问题表上作业运输问题表上作业运输问题表上作业法之研究法之研究法之研究法之研究学院：数学科学学院数学科学学院数学科学学院数学科学学院姓名：陈笋陈笋陈笋陈笋专业：信息与计算科学信息与计算科学信息与计算科学信息与计算科学年级：07070707级级级级学号：A20714088A20714088A20714088A207140882010.1《运筹学》期末论文07信息—陈笋2关于关于关于关于运输问题表上作业运输问题表上作业运输问题表上作业运输问题表上作业法之研究法之研究法之研究法之研究陈笋（数学科学学院07信息与计算科学A20714088）【摘要】货物从生产商到销售商的分配问题称为运输问题[1](TransportationProblem)，在现实中具有极其广泛的应用。它是一类典型的线性规划问题，本文就运输问题的解法进行研究探讨，在传统的表上作业法的基础上，根据表上作业法迭代计算的原理，说明了位势法求检验数的唯一确定性。针对表上作业法迭代计算的繁琐，提出了2个提高初始调运方案质量的运算法则，2个能使迭代次数明显减少的调运方案调整改进法则，并从理论和实例上证明了该法则的合理性。【关键字】线性规划运输问题表上作业法迭代改进研究综述一、一、一、一、引言引言引言引言经典的运输问题是一个线性规划模型。假定某种物资有m个产地，n个销地，为第i产地的供应量，为第j个销地的需求量，为从产地i到销地j的单位iajbijc运费，为产地i到销地j的调运数量，≥0，其中i=1,2,…,m；j=1,2,…,n。ijxijx问如何组织调运才能使得总运费最省?该问题为了寻找最佳调运方案，即求解所有的值．使总的运输费用ijx达到最少。其中当时为平衡型运输问题；当ijminjijxc∑∑==11∑∑===minjjiba11∑∑==≠njjmiiba11时为不平衡型的运输问题[2-4]。实际上不平衡型的运输问题通过转换可以变成平衡型的问题。当产量总量等于销售总量时，运输问题有可行解，且有最优解。且当产量和销售量均为整数时，必存在决策变量均为整数的最优解。平衡型运输问题的数学模型如下[2]：minZ=ijminjijxc∑∑==11S.t.,j=1,2,…,n，i=1,2,…,mjmiijbx=∑=1injijax=∑=1≥0，对所有的i,jijx《运筹学》期末论文07信息—陈笋3运输问题的解法通常用表上作业法。表上作业法是单纯形法在求解运输问题时的一种简化方法，一般分为确定初始解和最优性检验两步。【8】但在其迭代计算过程中，初始方案确定、方案的调整改进处理不一样，计算工作量就不一样，有时相差很大。那么，怎样才能使迭代计算工作量尽可能小?迭代次数尽可能少?下面将予以探讨。二、二、二、二、初始基可行解的求法初始基可行解的求法初始基可行解的求法初始基可行解的求法初始基可行解的确定，常用的方法有三种：最小元素法、Vogel（伏格尔）法、西北角法。一般地，Vogel法确定的初始方案质量最好，最接近最优解；最小元素法次之；西北角法最差。常用Vogel法确定的初始方案作运输问题最优解的近似解。[3](1)用Vogel法求初始方案时，最大罚数有2个以上。理论上，由任意最大罚数所在行或所在列的最小运价确定填运量格均可。但若最大罚数所在行或所在列的各最小运价不等，那么，由此确定的初始方案质量就不一样。我认为，由最大罚数所在行或所在列的各最小运价的最小者，确定填运量格而获得的初始调运方案质量最好，即由此迭代而获得最优方案的迭代次数最少。(2)确定初始方案，填某一运量格时，若同时满足其所在行和所在列的供销关系，则为保证初始方案的填运量格为m+n一1(m为产地数，n为销地数)个，应在何处填一个0？理论上，应在该填运量格的所在行或所在列的未划去或未填运量格中，任找一格填上一个O即可。但该填0的位置不一样，由此而获得的初始方案的质量就不一样。应在该填运量格的所在行或所在列的未划去或未填运量格中找一运价最小的空格填0，由此而获得的初始调运方案质量较好。因为，若由此而获得的初始方案不是最优解，在以后的迭代中，该填运量格《运筹学》期末论文07信息—陈笋4的所在行或所在列的其他未划去或未填运量格，对应变量成为进基变量的可能性将减少，从而减少迭代次数，提高由此而获得的初始方案的质量。[5]三、三、三、三、调运方案的检验调运方案的检验调运方案的检验调运方案的检验调运方案的检验通过检验数来完成。常用的求检验数的方法有闭回路法和位势法，而位势法计算检验数要简便得多，所以实际中常使用位势法计算检验数。任意空格对应变量的检验数，即。式中：为该空格的单ijxijσ)(jiijijvuc+−=σijc位运价；、分别为该空格所在行的行位势和所在列的列位势。iujv由位势法原理，、（i=1,2,…,m；j=1,2,…,n）不能唯一确定，需先确iujv定其中一个的值，其余m+n一1个的值才能唯一确定。那么，对同一调运方案(基可行解)，确定不同的或的值，所得的各变量的检验数是相同的。为简化iujvijσ用位势法求检验数的计算，常常任意指定某一位势等于零。【6】四、四、四、四、调运方案的调整与改进调运方案的调整与改进调运方案的调整与改进调运方案的调整与改进(1)若某一调运方案对应空格变量存在负检验数，则该调运方案不是最优调运方案，需对该调运方案进行调整改进。方案调整改进，是以绝对值最大的负检验数对应空格对应变量为进基变量，但当绝对值最大的负检验数对应空格对应变量有2个或2个以上时，应以可增加调运量最多的绝对值最大的负检验数，对应空格对应变量作进基变量进行方案调整而得的新方案质量较好，因为这样可使目标函数值减少最多，从而减少迭代次数。【5】(2)进基变量确定以后，进行方案调整。在以进基变量对应空格为顶点，其余顶点均为有数字格的闭回路上，以空格为始点，顺时针或逆时针方向给闭回路上各顶点编号，偶数顶点即为调运量减少的格子，奇数顶点即为调运量增加的格子，闭回路上各顶点调运量的调整量即为该闭回路上偶数顶点的最小调运量《运筹学》期末论文07信息—陈笋5如若对应口有2个或2个以上顶点，则应取口对应各顶点的单位运价最大者，对应变量作出基变量进行方案调整，而得的新方案质量较好。因为，如此确定的出基变量是可作为出基变量中单位运价最大的，因此，在以后的迭代中其再成为进基变量的可能性将减少，从而减少迭代次数。例有3个产地A1、A2、A3，4个销地B1、B2、B3、B4的产销平衡运输问题，见表1。试用表上作业法求最优调运方案。表1产销平衡运输问题解：用西北角法确定初始调运方案，见表2；用位势法求得该初始调运方案的检验数，见表3(表中只列出非基变量即空格的检验数，基变量的检验数为0，未列出)。AB产量/tB1B2B3B4A1362470A2533480A3175250销量/t40307060200《运筹学》期末论文07信息—陈笋6表2初始调运方案表3检验数以绝对值最大的负检验数对应变量作进基变量，进行方案调整，得新的调22x运方案，见表4；及其对应的各非基变量的检验数，见表5。AB产量/tB1B2B3B4A1403070A2701080A35050销量/t40307060200ABiuB1B2B3B4A110A20-41A3-224-1jv4623《运筹学》期末论文07信息—陈笋7表4调运方案表5检验数以绝对值最大的负检验数对应变量翔作进基变量，并按调整方案的检验中调整方案的确定原则进行方案调整，得新的调运方案，见表6。可检验该调运方案为最优调运方案，但若不按上述方法处理，获得的调运方案就不是最优调运方案，还需迭代。AB产量/tB1B2B3B4A1403070A230401080A35050销量/t40307060200ABB1B2B3B4A1410A201A3-264-1jv4223iu《运筹学》期末论文07信息—陈笋8表6调运方案五、五、五、五、结论结论结论结论表上作业法相对单纯形法来说是一个较为简便的方法，但实际迭代计算仍较为繁琐，弄不好迭代次数会增多。【5】若迭代计算中，在遵循表上作业法的基本原理基础上，按本文上述提出的改进方法原则处理，会使迭代次数明显减少，简化计算工作量，得到最优调运方案。【参考文献】[1]王春晓.《求解运输问题的新算法》.《高校理科研究》.[2]运筹学教材编写组．《运筹学(第三版)》.清华大学出版社.2005．[3]胡运权．《运筹学教程》.清华大学出版社.2004．[4]韩伯棠．《管理运筹学》.高等教育出版社.2000．[5]郭秀英.《论运输问题表上作业法》.《科技与管理》.2007.[6]韩伟一，张庆普.《有整数限制的运输问题》.《运筹与管理》.2008.[7]白国仲.《求解多目标运输问题的表上作业法》.《信阳师范学院学报》.2007.[8]刘茂华.《线性规划在运输问题中的应用》.《大庆师范学院学报》.2007.[9]蒋翔等.《工商管理常见运输问题的运筹学解法》.《商场现代化》.2007.[10]刘大为,张方华.《运输问题表上作业法的改进》.《科技资讯》.2008.AB产量/tB1B2B3B4A1407070A23005080A31050销量/t40307060200