收稿日期:2014－05－15基金项目:中央高校基本科研资助基金(项目编号:3142013027和3142014127);华北科技学院校级重点学科资助项目(项目编号:HKXJZD201402)。作者简介:张晓瑾(1980－)，女，山西临汾人，硕士，华北科技学院基础部讲师，研究方向:调和分析。E－mail:xjzhang2008@ncist.edu.cn运输问题的表上作业法中初始方案的优化张晓瑾，刘海生(华北科技学院基础部，北京东燕郊101601)摘要:在运用表上作业法寻找运输问题最优方案时，初始方案的质量尤为重要。本文给出了一个优化初始方案质量的规则，并提出了两个提高初始方案质量的方法，且结合实例说明了该方法的合理性。关键词:表上作业法;初始方案;Vogel法;优化中图分类号:O232文献标识码:A文章编号:1672－7169(2014)06－0073－03OptimizationoftheInitialProgramonTable－workingSchemeofTransportationProblemZHANGXiao－jin，LIUHai－sheng(DepartmentofBasicCourses，NorthChinaInstituteofScienceandTechnology，Yanjiao，101601，China)Abstract:Thequalityoftheinitialprogramisparticularlyimportant，whenusingtable－workingschemetofindtheoptimalsolutionoftransportationproblems.Thispaperpresentsaruleforoptimizinginitialprogram，andproposestwomethodstoimprovethequalityoftheinitialprogram，andwithexamplesillustratingthera-tionalityofthemethod.Keywords:table－workingscheme;initialprogram;Vogelmethod;optimization0引言运输问题是特殊的线性规划问题，表上作业法是运用了单纯形法的原理，结合运输问题自身的特点，而得到的一种求解产销平衡运输问题的简便而有效的方法。但在其迭代计算过程中，其初始方案的确定、检验和方案的调整改进处理不一样时，计算工作量大相径庭。如何才能减少迭代次数，用最少的工作量来求得最优方案，本文对表上作业法中初始方案的确定进行了一定的思考和改进。对于产销平衡运输问题初始方案的确定，常用的方法有三种:最小元素法、西北角法和Vogel法。一般地，Vogel法确定的初始方案质量最好，最接近最优解;最小元素法次之;西北角法最差。本文重点研究利用Vogel法确定初始方案过程中存在的不足和改进的工作。1方法存在的问题用Vogel法确定初始方案时，其过程中出现的问题:1)当一次计算中出现最大罚数有2个及2个以上时，究竟选取哪一个罚数对应的行或列来填数字，选取不当时，后期迭代步骤不同，初始方案质量不同。针对此问题，教材［7］中以及相关文献中未做出明确的说明。37第11卷第6期2014年6月华北科技学院学报JournalofNorthChinaInstituteofScienceandTechnologyVol.11No.6Jun.2014中国煤炭期刊网 www.chinacaj.net

2)在Vogel法确定初始方案过程中出现退化解时，如何确定填“0”的位置。先后有多篇文章讨论过这个问题，如［1］－［6］。在文献［1］中指出:“填到数字格所在行或所在列的未划去或未填数字格中单位运价最小的位置，可以避免可能存在的多余的计算。”实践表明，这一说法不完善。例如表1(表中“()”中为检验数;“○”中为初始方案，下表中相同).表1产销平衡运输表销地产地B1B2B3产量A110(7)2③5①4A29(5)3(0)6⑦7A32②1○02(－2)2销量238在A3B1位置填入数字2时，供销关系同时得到满足，此时有四个位置A1B1，A2B1，A3B2和A3B3可以填0。而单位运价最小者为位置A3B2，选其位置填0，得到初始方案，并计算其检验数见表1。空格位置A3B3检验数小于零，当前方案不是最优方案(见表1)。而如果选择将0填入位置A3B3，计算得到其初始方案和检验数见表2。此时，所有检验数都大于零，得到的初始方案为最优方案。故选择填到“数字格所在行或所在列的未划去或未填数字格中单位运价最小的位置”，这一说法未必能减少迭代次数。表2产销平衡运输表销地产地B1B2B3产量A110(5)2③5①4A29(3)3(0)6⑦7A32②1(2)2○02销量238下面针对以上两个问题，谈谈本文的改进工作:2方法的补充和改进1)用Vogel法确定初始方案时，当一次计算中最大罚数有2个及2个以上时，可以改进提高初始方案的质量。在理论上，由任意最大罚数所在行或所在列的最小运价确定数字格均可。但是，当最大罚数所在行或所在列的各最小单位运价不等时，选取最大罚数对应的不同的行或列，初始调运方案质量就不一样，迭代次数也不同。实践证明:由最大罚数所在行或所在列的各最小单位运价的最小者，确定数字格而获得的初始方案质量好。而且当产地和销地较少时，有时得到的初始方案就是最优方案。例如表3中的产销平衡问题。表3产销平衡运输表销地产地B1B2B3B4产量A13(0)11(2)3⑤10②7A21③9(2)2(1)8①4A37(9)4⑥10(12)5③9销量3656在利用Vogel法确定初始方案，填A2B1时，遵从这一规则:有相同最大罚数为2，选取了罚数为2的所在行和列中未被划去的行和列中单位运价最小的位置A2B1，优先得到满足。方案确定后，经检验其方案为最优(见表3)。2)用Vogel法确定初始方案，在填数字格时，若同时满足其所在行和所在列的供销关系，需选择某一位置填“0”，此时出现退化解。填“0”的位置不同，由此而获得初始方案的质量不一样，后期迭代次数也不一样。下面从客观上分析此问题:在书［7］中明确指出“通过任一空格可以找到，并且只能找到唯一的闭回路，并由此计算出全部空格处的检验数”。据此任一空格位置检验数的正负，唯一取决于闭回路各个拐点处数字格单位运价数值的相对大小。由于具体不同问题中各个单位运价之间没有必然的关联，客观上导致检验数计算结果的正负随机性，填“0”位置没有一个统一的规律。47华北科技学院学报2014年第6期中国煤炭期刊网 www.chinacaj.net

于是想从填“0”这方面减少迭代的次数，没有一个统一的规则。虽然如此，我们还是可以从两方面着手去优化Vogel法确定初始方案:一方面，通过后期观察法选取填“0”位置，减少空格位置检验数出现负值的可能性。下面举例说明，具体步骤如下:第一步:计算行和列的罚数，确定出第一个数字格。销地B1对应罚数为最大，其值为8;选择在A3B1位置填入数字5时。此时供销关系同时得到满足，划去第3行和第1列，需选某一位置填0。有A1B1，表4产销平衡运输表销地产地B1B2B3B4产量A1102⑤3(16)5⑩15A2127⑩9瑏瑥20(4)25A32⑤1416185销量5151510A2B1，A3B2，A3B3和A3B4对应的5个位置可以填0，具体位置待定(见表4)。第二步:视A3B1所在行和列已划去，依据第一步中的规则，继续确定出其它位置的数字格(见表4)。第三步:依据当前5个数字格，利用闭回路法确定出部分空格的检验数(见表4)。表5产销平衡运输表销地产地B1B2B3B4产量A110(3)2⑤5(16)5⑩15A212○07⑩9瑏瑥20(4)25A32⑤1417161918(12)5销量5151510第四步:填“0”的位置影响其它空格位置检验数的正负，通过位置筛选法，选择某一位置填0。从5个位置中选择一个填0，具体作法:当A1B1位置填0时，观察与之相关的空格，发现其在A2B1对应闭回路中，空格A2B1检验数12－7+2－10=－3＜0，放弃此位置;同理当A3B2位置填0时，发现其在A3B4对应闭回路中，空格A3B4的检验数18－14+7－20=－9＜0，放弃此位置;据此适当排除一些位置，一定程度上提高初始方案的质量，减少迭代次数，见表5。表5产销平衡运输表销地产地B1B2B3B4产量A110(3)2⑤5(16)5⑩15A212○07⑩9瑏瑥20(4)25A32⑤1417161918(12)5销量5151510当产销平衡的运输问题中产地和销地数相对较少时，此法效果很好。当产地和销地比较多时，试图通过后期观察法填“0”，实现初始方案的优化，减少迭代次数已经不易操作。另一方面，在符合条件的任意位置填“0”，依据检验数为负的空格调整量来判断，实现优化。具体作法是:运用Vogel法确定出初始方案，当出现一个空格处检验数为负时，运用闭回路法进行调整;若调整量为0时，结合文献［6］的说明，文献［2］中判别方法，可知此时已经得到最优方案，无需继续迭代。若调整量不为0时，说明当前方案不是最优方案，运用闭回路法调整方案，继续迭代寻找最优方案;当出现多个空格处检验数均为负值但调整量都为0时，结合［2］可知，此时已经得到最优解;否则闭回路调整方案。此方法对于检验数为负值且调整量为0的情形，大大减少了方案迭代的次数，优化了初始方案。3结论本文中作者给出一个处理“出现相同最大罚数问题”的规则，提高了Vogel法确定初始方案的质量;运用两个方法，从两个角度优化了填“0”的问题，减少了方案迭代次数，提高了初始方案的质量。(下转第79页)57第6期张晓瑾等:运输问题的表上作业法中初始方案的优化中国煤炭期刊网 www.chinacaj.net

5许可程序，矿业权竞争性申请日本矿业法确立了竞争性申请的原则。根据日本矿业法第27条的规定，同等条件下最先申请的企业或个人将优先获得矿业权。因此，矿业权的取得依据申请的先后顺序确定。相比之下，按照德国和法国法律规定，获得地下使用许可要通过招标、拍卖或投标程序。例如在法国，申请者应将许可申请提交到主管部门。根据法规第2006－648法令(2006年6月2日)第19条规定，矿产资源部长通过欧盟和法国官方杂志发出通知。因此，有兴趣的公司应在90天内完成投标申请。部长依据上面提到的标准作出最终的决定。实践中，部长将会见每一名申请者并试图鼓励他们联合申请。如申请者无法达成一致，部长会对矿产所在区域进行分配。因为相信绝大多数申请者将会从采矿活动中受益。而且，通常情况下，采矿权利人有可能被要求按照《法国民法典》1871－1873条的规定建立伙伴关系。在俄罗斯，官方通过《地下资源法》第15条确定的招标程序或者通过“PSA”法律程序授予采矿许可。PSA法律是基于民法的地下资源使用个人支付体系。然而，由于种种原因，PSA法律并不受俄罗斯联邦的欢迎，只是在极少的情况下实施。在招标程序中，招标委员会根据标准进行招标。投标人要求公平竞争时，招标委员会当着所有申请人的面打开密封的申请信封，每个信封装着申请人的出价，当然，出价最高者获胜。相比之下，德国法确立了“最优获胜”的原则，监管部门将评估拟开发矿产的工作程序，证明每个申请者资金能力的评估文件，从中评估出最富效率、合理并能系统开发矿产资源的申请者。然而，德国矿业法第14章第1条确立了优先原则，即已经与第三方合作进行勘探的申请人或企业优先获得许可。这一条要求监管部门要通知勘探方有关第三人提出申请的情况。6结论因为国家利益、能源短缺、气候变化以及其他原因，矿产和地下资源利用将来仍将受到政治、经济、法律等影响。因此，各方都在寻求利益平衡。这种平衡受到共同利益的影响。然而，这需要相关领域深厚的专业知识。在当今矿业市场交易过程中，法律顾问的技能，市场的透明度，以及公平负责的合作伙伴等因素都不可忽视。毕竟，矿业市场给有兴趣的玩家们，提供了在未来创造可持续发展的前景櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋櫋。(上接第75页)参考文献:［1］谢凡荣，产销平衡运输问题的表上作业法解法的一个注记［J］.运筹与管理，2005，14(4):44－46.［2］杨莉，等，运输问题的改进算法探讨［J］.运筹与管理，2002，11(4):77－80.［3］刘琳，退化运输问题最优解求法的一个注记［J］.高等数学研究，2006，9(4):125－127.［4］郭鹏，关于运输问题最优解的进一步讨论［J］.数学实践与认识，2006，36(5):140－146.［5］唐文广，等，运输问题退化解及其表解中0元的添加［J］.数学实践与认识，2009，39(1):160－166.［6］郝自军，等，运输问题表上作业的再探讨［J］.西南民族大学学报，2011，37(2):209－211.［7］胡运权，等.运筹学基础及应用(第5版)［M］.北京:高等教育出版社，2008.97第6期代海军:德国、法国、俄罗斯和日本矿业法的共同点与区别中国煤炭期刊网 www.chinacaj.net