1、本科毕业设计（20届）表上作业法在物品运输上的应用所在学院专业班级数学与应用数学学生姓名学号指导教师职称完成日期年月I【摘要】物品运输问题在当今经济建设中是十分常见的问题，运输问题及运输成本的优化是运输企业制定调运方案时必须要考虑的内容。如何选择一个合理的运输方案使得运输费用最低是十分关键的，表上作业法可以较好地解决这类问题。本文主要目的便是系统全面的对表上作业法进行研究，以及表上作业法的改进。【关键词】物品运输，表上作业法，运输费用【ABSTRACT】GOODSTRANSPORTPROBLEMSINCURRENTECONOMICCONSTRUCTIONISVERYCOMMONPROBLEM，
2、TRANSPORTATIONPROBLEMANDTRANSPORTATIONCOSTOPTIMIZATIONISTOTRANSPORTENTERPRISESTOMAKESCHEDULINGSOLUTIONSMUSTCONSIDERCONTENT。HOWTOCHOOSEAREASONABLETRANSPORTSCHEMEMAKESTHETRANSPORTCOSTSISVERYCRUCIAL,TABULARMETHODWHICHCANSOLVETHISKINDOFPROBLEM。THEPURPOSEOFTHISARTICLEISTOSYSTEMICALLYTABULARMETHODFORRESEA
3、RCH，ANDIMPROVETABULARMETHOD。【KEYWORDS】GOODSTRANSPORT，TABLEWORKINGMETHOD，TRANSPORTCOSTSII目录目录II1引言111课题提出1111课题背景1112课题意义112运输问题研究现状1121运输问题国外研究情况1122国内运输问题研究情况113研究方法22表上作业法321表上作业法具体介绍322确定初始基可行解4221最小元素法4222伏格尔法523基可行解是否最优的判别6231闭回路法6232位势法6233闭回路调整法73表上作业法实际应用831产销平衡问题8311实际运输例子8312数学模型的建立8313选定初
4、始调运方案9314检验已确定的初始方案是否最优10315调整初始调运方案10316小结1132产销不平衡运输问题11321实例分析11322应用表上作业法求解124表上作业法与其他方法比较1341LINGO软件求解13411实例分析13412表作业法求解13413LINGO软件求解13414比较分析1342图上作业法14421运输实例14422图上作业法求解14423图上作业法与表上作业法的同异1543网络计算法1544各种方法小结155表上作业法的改进16III51国内对表上作业法改进研究情况16511李时椿的流水原理改进16512王德敬最优方案判别法则改进16513蒋宏锋的一种新的表上作业
5、法1752运用改进表上作业法解决实际问题17521表上作业法初始基可行解的求法和改进17522表上作业法调运方案的改进18523实际应用18524小结206总结20致谢错误未定义书签。参考文献211引言11课题提出111课题背景运输问题是当今社会经济生活中经常出现的优化问题。在经济建设中，经常遇到物资的调运问题，如何制定调运方案，将物资运往指定地点，而且实现运输费用最小，即为运输问题。运输问题是特殊的线性规划问题，它是线性网络最优化的一个例子。最早研究这种运输问题的是美国学者希奇柯克（HITCHCOCK），1941年他在研究生产组织和铁路运输方面的线性规划问题的时候提出运输问题的基本模型；后来
6、柯普曼（KOOPMANS）在1947年独立地提出运输问题并详细地加以讨论；从上世纪40年代早期开始，康脱洛维奇（KANTOROVICH）围绕着运输问题作了大量的研究，所以运输问题又称为希奇柯克问题或康脱洛维奇问题。与一般线性规划问题不同的是它的约束方程组的系数矩阵具有特殊结构，这就需要采用不同甚至更为简便的方法来解决这种在实际工作中遇到的问题。运输问题代表了物资合理调运、车辆合理调度等问题，其他类型问题经过一系列变换后也可以归结为运输问题。112课题意义物品运输问题在当今经济建设中是十分常见的问题，运输问题及运输成本的优化是运输企业制定调运方案时必须要考虑的内容。如何选择一个合理的运输方案使得
7、运输费用最低是十分关键的。表上作业法可以较好地解决这类问题。本文主要目的便是系统全面的对表上作业法进行研究，以及表上作业法的改进。12运输问题研究现状121运输问题国外研究情况由于运输问题的特殊数学结构，人们很早就想到到通过给出基变量，离基变量的最优性条件，可以更有效地利用单纯形法对运输问题进行求解。DANZIG提出的单纯形法作为求解运输问题最初单纯形方法（PRIMALSIMPLEXTRANSPORTATIONMETHOD，PSTM）1。随后CHARNES和COOPER（1954）发展逐级算法（STEPPINGSTONEMETHOD，SSM），这种算法提供了决定单纯形方法信息的可选择途径。表上
8、作业法是解决运输问题常用的解法，因为它在求解工作均在运输表上进行而得名。它是一种迭代算法，他的迭代步骤主要为先按某种规则找出一个初始解；再对现行解作出最优性判别；若该解不是最优解，就在运输表上进行调整改进，得出一个新的解，再重复判别改进，直至得到运输问题的最优解。122国内运输问题研究情况国内学者对于运输问题的研究大致可以分为三个角度第一是在国外算法的基础上，对运输问题算法的改进研究；第二是从目标函数的角度研究，在运输问题中有时要同时考虑运输成本最小、运输过程中货物损坏率最低以及单位运价变化的调整等多个目标；第三是从约束函数的角度研究，有研究供给量和需求量在某个区间变化的不确定型运输问题、有时
9、间窗口的运输问题等。213研究方法本文主要采用文献研究方法，文献研究法主要是指搜集、鉴别、整理文献，并通过研究文献，形成对事实科学认识的方法。本文通过搜集大量相关文献资料，阅读、分析、研究课题。32表上作业法21表上作业法具体介绍表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法。但具体计算和术语有所不同。可归纳为1找出初始基可行解。即在MN产销平衡表上用西北角法或最小元素法，VOGEL法给出MN1个数字，称为数字格。它们就是初始基变量的取值。2求各非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。3确定换入变量和换出变
10、量，找出新的基可行解。在表上用闭回路法调整。4重复2，3直到得到最优解为止。以下通过一个案例分析研究表上作业法2某公司经销甲产品。它下设三个加工厂。每日的产量分别是A1为7吨，A2为4吨，A3为9吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为B1为3吨，B2为6吨，B3为5吨，B4为6吨。已知从各工厂到各销售点的单位产品的运价为表33所示。问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。先作出这问题的产销平衡表和单位运价表，见表31，表32销地加工厂B1B2B3B4A1A2A3317119432101085表31销地加工厂B1B2B3B4产量A1A2A3749
11、销量3656表32422确定初始基可行解确定初始基可行解的方法很多如西北角法，最小元素法和伏格尔VOGEL法。一般希望的方法是既简便，又尽可能接近最优解。下面介绍几种方法最小元素法和伏格尔法。221最小元素法最小元素法的基本思想是就近供应，即从最小的运价开始确定供销关系，然后次小。一直到给出初始基可行解为止。以例1进行讨论。第一步从表31中找出最小运价为1，这表示先将A2的产品供应给B1。因A2B1，A2除满足B1的全部需要外，还可多余1吨产品。在表32的A2，B1的交叉格处填上3。得表33。并将表31的B1列运价划去。得表34。销地加工厂B1B2B3B4产量A1A2A33749销量3656表
12、33销地加工厂B1B2B3B4A1A2A3317119432101085表35。第二步在表34未划去的元素中再找出最小运价2，确定A2多余的1吨供应B3，并给出表35，表36。销地加工厂B1B2B3B4产量A1A2A331749销量3656表35销地加工厂B1B2B3B4A1A2A3317119432101085表365第三步在表36未划去的元素中再找出最小运价3；这样一步步地进行下去，直到单位运价表上的所有元素划去为止，最后在产销平衡表上得到一个调运方案，见表37。这方案的总运费为86元。销地加工厂B1B2B3B4产量A1A2A3364133749销量3656表37用最小元素法给出的初始解是
13、运输问题的基可行解。222伏格尔法伏格尔法是从一行或一列的整体出发考虑会更加的合理，一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运输量就会加多从而运费增加越多。因而对差额最大处，要优先考虑，应当采用最小运费调运。伏格尔法的步骤如下第一步在表31中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行，见表38。销地加工厂B1B2B3B4行差额A1A2A3317119432101085011列差额2513表38第二步从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表38中B2列是最大差额所在列。B2列
14、中最小元素为4，可确定A3的产品先供应B2的需要。得表39销地加工厂B1B2B3B4产量A1A2A36749销量3656表39同时将运价表中的B2列数字划去。如表310所示销地加工厂B1B2B3B4行差额6A1A2A3317119432101085012列差额213第三步对表310中未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。重复第一、二步。直到给出初始解为止。用此法给出例1的初始解列于表311销地加工厂B1B2B3B4产量A1A2A3365213749销量3656由以上可见伏格尔法和最小元素法除在确定供求关系的原则上不同外，其余步骤基本相同。伏
15、格尔法给出的初始解比用最小元素法给出的初始解更接近最优解。本例用伏格尔法给出的初始解就是最优解。23基可行解是否最优的判别最优解的检验检验的方法是查看空格非基变量的检验数是否有不符合最优性条件的。为此，先介绍空格检验数的求法。基可行解是否最优的判别法有闭回路法、位势法、闭回路调整法231闭回路法对每个非基变量如X11求它的闭回路求它的检验数312310检验数无负是最优解，否则可调整销地加工厂B1B2B3B4产量A131113411037A2131921184A374610539销量3656232位势法新方案再检验,逐个非基变量求检验数太繁，可用位势法求检验数；检验数全部非负,找到最优解不唯一对
16、应运输问题的MN个约束条件的对偶变量。B是含有一个人工变量XA的初始基7矩阵。233闭回路调整法当在表中空格处出现负检验数时，表明未得最优解。若有两个和两个以上的负检验数时，般选其中最小的负检验数，以它对应的空格为调入格。即以它对应的非基变量为换入变量。由表31得2，4为调入格。以此格为出发点，作一闭回路，如表销地加工厂B1B2B3B4产量A1A2A33641113113749销量36562，4格的调入量是选择闭回路上具有1的数字格中的最小者。即MIN1,31其原理与单纯形法中按规划来确定换出变量相同。然后按闭回路上的正、负号，加入和减去此值，得到调整方案，如表320所示销地加工厂B1B2B3
17、B4产量A1A2A3365213749销量3656表320对表320给出的解，再用闭回路法或位势法求各空格的检验数，见表321。表中的所有检验数都非负，故表320中的解为最优解。这时得到的总运费最小是85元。销地加工厂B1B2B3B4A1A2A3092211283表上作业法实际应用31产销平衡问题产销平衡是指生产量与销售量相同，即AIBJ公路货运企业时常会遇到若干货源地向若干需求地的货物运输问题，供货量与需求量不尽相同，怎样合理组织运输，满足货主的运输要求，同时使完成运输计划的运输费用最低，这是运输企业制定计划时优先考虑的问题。显然，调运方案可以有很多个，但最优方案只有一个，表上作业法可以找到
18、这个最优方案。表上作业法求解线性规划问题也是取迭代选优的办法，即给出一个初始可行方案，经过反复迭代，每次迭代使目标函数有所降代以成本为目标函数，最后取得最优方案。311实际运输例子宁波现有一运输企业承担一项运输任务有，A1、A2、A3个砖厂，它们生产砖的质量相同。其产量分别为7000X10块，5000冰10块，9000X10块3。这三个砖厂的砖可供B1、B2、B3、B4个建筑工地使用，它们需用量分别为4000X10块，3000X10块，6000XL0块，8000XL0块。从各个砖厂运一千块砖到各建筑工地的运价如表所列，产量B1B2B3B4发货量（X10块）A175387000A24626500
19、0A382579000收货量（X10块）400030006000800021000应如何组织调运才能使总的运费最省。下面就此实例进行分析。312数学模型的建立首先要确定决策变量。运输问题决策变量经济意义很明显，就是从某一发货点运到某一收货点的货物的数量。现在设从第I个发货点运往第J个收货点的砖数为XIJIL，2，3，J1，2，3，4，其次确定目标函数，运输问题的目标函数是使总的运费最省，取极小值。设FX为目标函数，XIJ表示从第I个产地运往第J个销地的运输量，CIJ表示从第I个产地运一个单位货物到第J个销地的运价。那么有F（X）7X115X123X138X144X216X122X236X248
20、X312X325X337X34最后列出约束条件。运输问题的约束条件山发货量限制条件与收货量限制条件及非负条件三部分组成。发货约束条件X11X12X13X147000（X10块）X21X22X23X245000（X10块）9X31X32X33X349000（X10块）收货约束条件X11X21X114000（X10块）X12X22X323000（X10块）X13X23X336000（X10块）X14X24X348000（X10块）非负约束条件XIJ0IL，2，3，J1，2，3，4313选定初始调运方案先将有关数据列成一个表格如表2，然后按最小元素法确定发收货物的数量关系。以此类推，直到编出一个调运
21、方案。产量B1B2B3B4发货量（X10块）A175387000A246265000A382579000收货量（X10块）400030006000800021000表2在表2中，C23C322，是最小元素，可任选二者中任意一个，先确定收发物资数量关系即沙的物资优先供给B3，A2的产量是500X10块，而及需6000X10块，把A2的5000X10块全部运给及，沙这时的物资全部运出，不能再进行调运了，所以242221XXX都等于零，如表上划“X”，表明以后不再考虑此处的调运问题。划去第2行，因此计算结果如表3所示。B1B2B3B4发货量（X10块）A14000X1000200075387000A
22、2XX5000X46265000A3X3000X600082579000收货量（X10块）40003000600080002100010X114000X131000X142000X235000X323000X346000FX1050元314检验已确定的初始方案是否最优利用闭回路法检验可得下表B1B2B3B4发货量（X10块）A1400021000200075387000A2245000146265000A3230003600032579000收货量（X10块）400030006000800021000由于各个空格的检验数不全大于等于0所以需要进行调整315调整初始调运方案在调整方案的时候，首先
23、要确定换入与换出变量。可选择检验数中最小最负的非基础变量为换入变量。以该换入变量为顶点做一闭回路，该闭回路上偶数顶点的最小调运量为调整量，该变量为换出变量调整方法在该闭回路的偶数顶点的调运量均减去调整量，奇数顶点的调运量均加上调整量包括换入变量，其它格子不变。按此方案调整表3所列调运方案以X21为换入变量，X11为换出变量，如下表所示。B1B2B3B4发货量（X10块）A1XX5000200075387000A24000X1000X46265000A3X3000X600082579000收货量（X10块）40003000600080002100011此时FX970元该方案比原来方案节省80元，
24、继续利用闭回路法检验调整后可以得出最优方案为下表B1B2B3B4发货量（X10块）A1XX6000100075387000A24000XX100046265000A3X3000X600082579000收货量（X10块）400030006000800021000此时FX960元为最小值316小结总之，社会主义公路运输企业在生产经营活动中要根据国家计划和市场需要，运用线性规划的科学方法，测算出每一调运计划最低消耗，获最高的利润，满足社会需要，进而做到社会效益与企业效益的统一，全局利益与局部利益的统一。选择一个合理的运输方案使得运输费用最低，将大大降低运输成本，提高企业市场竞争力。32产销不平衡运
25、输问题对于产销平衡的问题可用表上作业法求解，但对于产销不平衡的问题则需要进行处理，要先将其化成平衡问题，才能用使用表上作业法求解321实例分析某运输问题有三个产地和三个销地，产地的总供应量小于销地的最高需求量之和，但超过了销地的最小需求量之和。现在，各销地的最低需求必须满足，最低需求到最高需求的之间的需求若不能满足，会造成经济损失，其中B1销量必须满足，B2、B3不能满足的单位损失分别为3元和2元。单位运价、供应量与需求量见下表。求出最优调运方案。2销地产地B1B2B3供应量A1517200A2646800A332515012最低需求最高需求6006001202003004301150322应
26、用表上作业法求解B2的最高需求与最低需求不相等，而B1的最低需求必须满足，因此可将B2看成两个销地B21和B22，其中B21的需求量为B2的最低需求量，该需求量必须全部满足；B22的需求量为B2的最高需求量减去最低需求量，即为20012080，该需求量可以不被满足。对销地B3也可作同样的处理。这样问题就变为一个三个产地、五个销地的运输问题，其中总产量为1150，总供应量为1230，因此是一个销大于产的问题。为解此问题，又要假设一个产地A4，其产量为1230115080。为了使各销地的最低销量得到满足，可令A4运往B1、B21、B31的运价为M，即给出一个很高的运价。这样就可以得到如下产销平衡表
27、，销地产地B1B21B22B31B32供应量TA151177200A264466800A332255150A4MM3M280需求量6001208030013012301230用表上作业法求解，可以得到如下表所示的调运方案。销地产地B1B21B22B31B32供应量TA112080200A245030050800A3150150A48080需求量6001208030013012301230从最优调运表中可以看出，B1和B2的需求量得到全部满足，而B3的需求量满足了350。总费用（包括缺货损失费160元）为8100元134表上作业法与其他方法比较41LINGO软件求解作为一类特殊的线性规划问题,运
28、输问题的求解一般是上采用表上作业法,但是其求解过程复杂、繁琐,求解受到很大限制随着计算机科学技术的发展,LINGO软件在求解运输问题中逐步得到了广泛应用,以下通过实例求解,对两种求解方法进行比较分析411实例分析设有5个产地A1、A2、A3、A4、A5和4个销地B1、B2、B3、B4的运输问题,他们的供应量和需求量及单位运费如表1,试求其最优运输规划及最小运输成本4单位百元T412表作业法求解利用表上作业法经过8轮求解可得初始方案，再对初始方案进行调整，4轮调整后可得最优方案即产地1向销地3运输10T,产地2向销地2运输20T,产地3向销地1运输30T,产地4向销地2运输30T,产地4向销地4
29、运输10T,产地5向销地1运输30T,产地5向销地2和销地3各运输10T其最小总运输成本5109204307300103301210510820百元413LINGO软件求解在LINGO软件中,新打开一个窗口,输入相关程序代码后即可最后得出X1310,X2220,X3130,X4230,X4410,X5130,X5210,X5310目标函数值为820百元,与使用表上作业法求解结果完全相同414比较分析表上作业法计算繁琐,方案调整的工作量大,容易出错。表上作业法一方面是在求解过程中首先要找出初始基可行解，需要一定计算工作量，即需要经过多次运算才给出初始方案。另一方面是在初始基可行解基础上，还要用繁
30、琐的闭回路法计算所有空格（非基变量）的检验数，再判别是否最优解。如果不是最优解，还需要在表上用闭回路法进行调整，确定换入变量和换出变量，找出新的14基可行解，再进行检验等步骤，直到求出最优解。而LINGO软件只需要输入集合定义、目标函数、约束条件和初始数据,就可以一步到位计算出最优解,省却了中间计算、检验环节,所有计算工作交给计算机实现表上作业法只适合变量数量较少情况下的求解利用软件求解线性规划问题非常简单,而且速度很快42图上作业法图上作业法也是单纯形法在求解运输问题的简化方法。它的实质也是单纯形法。421运输实例已知某一运输问题的产销平衡及单位运价表1，求运费最小的调运方案5。422图上作
31、业法求解采用最小元素法求出初始方案如下表转化为图解即部图有7个顶点，而图为含有5条边的一棵树，故不是支撑树。因此，该运输方案是退化的，可以考虑再添加一条边。只要所要添加的边不构成圈就得到一个7个顶点、6条边的树，即得到该2图的一棵支撑树。该题中可以添加。EA3B4可得下图采用闭回路法检验该方案不是最优解重复以上步骤得下表15经检验该方案为最优解423图上作业法与表上作业法的同异相同点由于这2种方法的本质都是单纯形法，即求解过程都是分为3步。确定初始基本可行解；判定是否最优；若是最优则问题得解，若不是最优则按闭回路法进行调整运输方案不同点在求解的第1步。表上作业法可用最小元素法，伏格尔法而图上作
32、业法只能用最小元素法而且比较复杂。在求解的第3步中调整迭代，若不是最优解，可在检验数为负的闭回路上进行调整。故用图上作业法较简单。图上求解法与表上作业法相比，用图上求解法判别最优解时，需要验证（MN1）基变量边是否可以用非基变量对应边代替（其中M、N分别是产地和销地的数量）。当M、N较大时，MN（MN1）远远大于（MN1），因此当M、N较大时，理论上用图上求解法较方便。但同时当M、N很大时，图上边、权及边线太多，易混淆，不利于实际操作。43网络计算法运输问题也可以转化为最小费用最大流问题,即通过网络图来计算。其基本思路是首先以最小费用满足最大需求的销地,依次类推。其基本步骤可归纳为61绘制相应
33、的网络图2分别给每条弧以相应的权单位运价（3）找出需求量最大的销地（4）继续寻找第二大需求量,直到全部满足要求为止。按以上方法可以确定初始调配方案,再用检验数法检验方案的最优性。通过对表上作业法和网络计算法的比较分析可以看出,运用网络图求解运输问题,可以更直观、快速、形象地得到初始解,并且该初始解更接近最优解或已经是最优解,可以大大减少计算工作量。但对于产销地数量较多时网络图绘制可能相对麻烦些,同时,对于调配方案的调整还有待进一步探讨。表上作业法和网络解法相比，运用网络图求解运输问题，可以更直观、快速、形象地得到初始解，并且该初始解更接近最优解或已经是最优解，可以大大减少计算工作量。但当产销地
34、数量较多时，网络图绘制可能相对麻烦些。而表上作业法无论用闭回路法或位势法，其检验数的计算都比较麻烦，特别是当初始解选取不合理时，中间的运输量调整过程增多，计算量的增加是可观的。44各种方法小结解决各种运输问题的算法有多种，但是每一种算法都有局限性，也就是说每一种算法都是在满16足某些条件下给出的算法，而且这些算法分别解决某一项或两项问题的优化，无法兼顾所有情况。因此，在考虑实际运输问题优化的时候，有时必须综合地应用各种优化方法来解决问题，或采用不同的算法解决问题的不同环节的子问题优化，最终得到运输问题的最优方案。5表上作业法的改进51国内对表上作业法改进研究情况511李时椿的流水原理改进在传统
35、的“闭回路法”和“位势法”基础上,提出利用“流水原理”来寻求运输问题最优解7。即以“最小元素法”求得初始调运方案后,将表中各栏单位物资的运价视为“水位”的高低,将已安排的运输量视为处于一定水位高度的“蓄水量”,依据“水往低处流”的自然界基本原理,考察处于最高“水位”的“蓄水量”沿其所在的行或列的“渠道”流向最低“水位”的可能性,来确定“流向”及其相应的“闭回路”,据此调配运输方案,直至总体“蓄水量”处于最低水位状态,则方案达最优。512王德敬最优方案判别法则改进平衡运输间题数学模型的约束条件XIJ0，表明只讨论从发车点驶往收车点，不讨论任何形式的“逆向行驶”，但“逆向行驶”在运输实际中往往发生
36、。通过改进平衡运输问题表上作业法中的判别法则，解决“逆向行驶”间题，使平衡运愉方案真正达到最优化8。改进最优方案判别法则对调运方案表中每一空格作一条闭回路，求出检验数。如果检验数中没有正数，则可以判定这一调运方案为最优方案若检验数中有正数，则要对方案进行调整。改进为如果检验数中没有正数，而且任一空格的闭回路中第偶数次拐角点除空格外所对应的里程数或运价不大于闭回路的周长或运价和的一半，则可以判定这一调运方案为最优方案若检验数中有正数，或某一偶数次拐角点所对应的里程数或运价大于闭回路的周长或运价和的一半，则要调整方案。方案的调整若某一闭回路的第偶数次拐角点A的里程数或运价大于闭回路的周长或运价和的
37、一半时，则在这一闭回路中的每个第奇数次拐角点增加A点的运量每个第偶数次拐角点减去A17点的运量后，取差的绝对值A点变为空格发车数和收车数重新计算。513蒋宏锋的一种新的表上作业法蒋宏锋提出的运输问题逐块选优解法,是一种有效算法9。根据运输问题逐维选优算法,结合目标函数梯度向量的投影,设计给出求解运输问题最优解集的表上作业法,并用一些实例说明运输问题逐块选优表上作业解法的具体操作过程这与传统的表上作业法用西北角法求出初始运输方案、用位势法计算判别数、用闭回路调整法改进运输方案所得最优解相同该算例表明,新的表上作业能很快求出全部最优解52运用改进表上作业法解决实际问题参考了上述3种表上作业法的改进
38、后，接下来将通过研究如何获取最佳初始解这一过程，改进运输问题上最佳初始解的获得，从而减少表上作业法的调整工作，继而减少表上作业法的工作量。表上作业法是求解运输问题一种有效简便的方法但是它在迭代计算过程中，检验数计算和运输量调整的计算量非常的大，那么怎样确定初始方案才能堪可能的减少迭代次数，从而削减计算量这正是十分关键而具有重大意义的，也是下文的主要探讨问题521表上作业法初始基可行解的求法和改进上文中已经阐述过了一般表上作业法的初始基可行解的求法了，即最小元素法和伏格尔法，下面将介绍一种表上作业法的初始基可行解的差额算法。用差额法确定的初始方案作为运输问题最优解的近似解,在一定程度上可以减少迭
39、代次数,从而削减计算工作量,有时甚至可以直接就能得到最优解。虽然有人习惯于用最小元素法,但工作量的角度上来看,还是用差额法比较好。在用差额法确定基变量时,首先要算出各行各列中次小元素与最小元素单位运价之差,接着在具有最大差额的行或列中以具有最小元素的变量为基变量。差额法的具体步骤有五步第一算出各行各列中次小元素与最小元素的差额,并标示出最大的差额第二若有几个差额同为最大,的找单位运价最小的那行或那列第三在具有最大差额的行、列中的最小元素处填上尽可能大的数,在已满足的行或列上打第四当在表中某一变量处填入一数后,可能使该变量所在的行和列同时被满足。此时,我们规定,只能画去一行或一列,而不能将两者同
40、时画去。而当表中只剩下一行或一列还有空格时,我们规定,在空格中只能填数可填0,不能打第五对未画去的行及列重复以上步骤,直至得到一个初始解差额法确定基变量时不仅考虑了各个变量单位运价的绝对值,而且还考虑了其相对值,因此差额要优于最小元素法再研究本文要研究的初始基可行解改进算法18我们在确定基变量的时候不仅要考虑各个变量单位运输价格的绝对值相对值、而且还将各个变量的运输量考虑进去，将会得到一种新的改进算法首先算出各行中次小元素与最小元素的运费差，然后在具有最大差额的行中以具有最小元素的变量为基变量若具有最大差领的行有几个，则以这几行中单位运价最大的那个最小元素为基变量。这种方法虽然在确定初始方案时
41、的计算量稍大，但由于与差额法相比，该方法不必计算列差，能够直接得到最优解，从而能大大减少总的计算工作量。当然，在确定各行中次小元素与最小元素的运费差时也是需要遵循以下原则的1当某行次小元素的可调运量大于或等于最小元素的可调运量时，运费差等于最小元素的可调运量乘该行次小元素与最小元素单位运价之差2当某行次小元素的可调运量小于最小元素的可调运量时，运费差由两个部分组成，一个部分是次小元素的可调运量乘该行次小元素与最小元素单位运价之差。另外一部分是将最小元素与次小元素的可调运景的差值作为调运量，乘该调运量所在元素与该行最小元素的单位运价之差。将这两部分相加就是佳确的运费差。522表上作业法调运方案的
42、改进传统的调运方案的检验主要是闭回路调整法，下面介绍一种改进后的方法第一先确定基变量。将具有最大正检验数的变量作为基变量，由基变量出发，找出一条闭合回路，在其偶数号中，取值最小的变量为出基变量。第二，调整运输量。对所有奇数号的变量都调整量的值，所有偶数号的变量减掉调整量。最后，在新的基础可行解的基础上重新计算检验数，直至所有的检验数都为负数。在调整过程中遵守以下两点原则，可以减少调整次数若具有最大正检验数的变量有好几个，则选调整量最大的那个具有最大正检验数的变量作为基变量若有几个偶数号的变量均可以作为换出基变量，则选共中单位运价最大的为换出基变量。523实际应用现在，宁波一化肥生产公司要将一些
43、化肥运到4个销售地点改公司有3个化肥生产点。经过市场调查得到以下运输费用和化肥生产量和需求量的资料见下表销地生产地B1B2B3B4A1A2A391451271310615881120运输费用表（运价元/吨）销地生产地B1B2B3B4产量A1A22408019A3180销量90120130160生产量和需求量关系表现在应用改进的表上作业法制订一最佳运输方案。（1）先用差额法计算应用差额法确定如下表初始方案，表格中右上角红色数字为调运量黑色数字为检验数运价（元/吨）B1B2B3B4生产量行差A194801602401222912108A21580348011/147611A390405071806
44、2225131520需求量（吨）90120130160列差4543/542/15/15/由于表中存在正检验数，故需要重新调整方案，调整后的方案如下表运价（元/吨）B1B2B3B4生产量A16180160240912108A2153050780147611A390903010180513152020需求量（吨）90120130160该标准所以检验数都为负数，所以该方案为最优方案（2）应用改进的算法确定初始方案见下表，表格中右上角红色数字为调运量黑色数字为检验数，其中运运输费用差额YIJ也如下表运价（元/吨）B1B2B3B4生产量运输费用差额YIJA161801602402303801606091
45、2108A215305078080808030147611A39090310180720180180/5131520需求量（吨）90120130160由于表中已经没有正检验数。所以该初始调运方案即为最优调运方案。最优调运方案为X1380X14160X2230X2350X3190X3290最优调运方案下的运费为4210元该最优方案与用差额法求出的最优方案一致，显然它比差额法简便多了。524小结表上作业法相对于单纯形法来说是一个较为简便的方法，可是实际迭代计算仍较为繁琐，迭代次数过多。差额法来确定初始调运方案虽然能减少迭代次数，却不如保证直接得到最优解，通过上述2个算法，可以得出如果在遵循表上作业
46、法的基本原理基础上，运用本文提出的改进算法，并遵循定的原则进行处理，在一般情况下无须经过方案调整就能直接得到最优调运方案。6总结21经济迅速发展的今天，物品运输问题是十分常见的，市场竞争日益激烈，合理选择最优的调运方案是至关重要的。通过分析影响制造企业运输环节费用的主客观因素可知，短期内产品特点、运输方式、产量、运输距离和市场需求都不会发生太大变化，因此制造企业只有在单位运费一定的情况下充分考虑市场需求和产地产量从而确定合理的运输量才能有效减少运输费用。运用表上作业法确定最佳调运方案既最大限度满足了市场需求使市场机会成本损失大大减少，同时又能保证合理库存不会因为产品积压产生更多的成本或造成损失
47、。因此，表上作业法为制造企业有效降低运输费用提供了可行的方法。1个最优的运输方案将给企业节省大量的资金，从而降低物品成品，大大提高了企业的竞争力。表上作业法是物品运输问题中最常用的一种方法，虽然现在表上作业法仍然比较复杂，但是它便不需要什么特殊工具，任何时候都能使用，相信在不久的将来表上作业法将会一步一步的得到改进，更加简便，易于使用。参考文献1王有鸿,费威运输问题国内外研究评述J,东北财经物流研究2010247137182钱颂迪运筹学M北京清华大学出版社,2005,063李彦臣,魏丽雅产销平衡运输最低成本的表上作业法J交通科技与经济,2000,01251574张家善,LINGO软件求解运输问
48、题与表上作业法的比较J湛江师范学院学报2001（3）1371405盛秀艳窦志伟,农业运输问题的表上作业法与图上作业法的比较J安徽农业科学报,2010，10720272036,金峻炎表上作业法与网络计算法求解运输问题的比较分析J科技咨询导报20071320217李时椿运输问题表上作业法的改进研究J南京航空航天大学学报200032（6）3243298王德敬,改进平衡运输问题表上作业法中的最优方案判别法则J江西农业大学学报199618（4）4834879蒋宏锋,运输问题一种新的表上作业法J科学技术与工程2006,6243941394810杜子平运输问题表上作业法的解析C第六届中国青年运筹与管理学者大
49、会论文集20040711刘耀表上作业法的改进J兰州大学自然科学学报196101171912伍学滨，刘国良，彭友霖表上作业法在物资调运问题中的应用M商场现代化200113郭秀英论运输问题表上作业法J科技与管理20073333514田荣表上作业法的一种理论证明J北京职工医学院学报20013333515刘大为，张方华，运输问题表上作业法的改进J科技资讯2008，1224825016XINFENGYANG,YINZHENLI,RUICHUNHE,LINZHONGLIUMODELANDALGORITHMOFTRANSPORTATIONPROBLEMONNETWORKJJOURNALOFSYSTEMSSCIENCEANDINFORMATION2008，6（4）32533217CHENHAIFENGCHOJOONGRAELEEJEONGTAE，SOLVINGHITCHCOCKSTRANSPORTATIONPROBLEMBYAGENETICALGORITHMJ重庆大学学报英文版20043（2）5457
