表上作业法解决运输
问题
表上作业法解决运输问题
谢荣华、林建、岳钱华、叶俊君
【摘要】在物资调运问题中,希望运输费用最少总是人们最为关心的一个目标。在各种设定条件的约束下,如何寻找使得总运输费用最少的最优的运输方案是运输问题的核心。为给社会生产(生活)提供既便捷又经济实惠的物资调运方案,运输问题模型的求解方法可以产生最优的决策方案。因此对运输问题的深入研究具有极其重要的理论意义和实际应用价值。表上作业法是解决运输问题的重要方法本文讨论了产销平衡运输问题的表上作业法，利用伏格尔法求初始方案，位势法求检验数，闭合回路发对可行解进行调整和改进，直至求出最优解。
【关键词】运筹学、运输问题、改善优化、表上作业法
一、理论依据
运输问题的表上作业法步骤
1、制作初始平衡表
用“西北最大运量，然后，每增加角方法”：即在左上角先给予最大运量，然后，每增加一个运量都使一个发量或手里饱。如果所有运量的数字少于
（m+n-1），则补0使之正好（m+n-1）个。
（注:补零时不能使这些书构成圈。）
2、判断初始方案是否最优
（1）求位势表：对运价表加一行一列，圈出运价表中相应于有运量的项，在增加的行列上分别添上数，使这些元素之和等于圈内的元素。这些元素称为位势数。
（2）求检验数，从而得到检验数表。
结论：若对任意检验数小于等于0，则该方案最优，否则进入3进行调整.
3、调整
（1）找回路：在检验数大于0对应的应量表上对应元素为起点，沿横向或纵向前进，如遇到有运量的点即转向，直至起点，可得到一个回路。
（2）找调整量：沿上述找到的回路，从起点开始，在该回路上奇数步数字的最小者作为调整量ε。
（3）调整方式：在该回路上奇数步-ε，偶数步+ε，得到新回路。
重复上述步骤，使所有检验数小于0，即得到最优方案。
二、背景
鉴于市场竞争日益激烈，消费者需求渐趋多样，工厂作为市场消费品的产出源头，唯有对这种趋势深刻理解、深入分析，同事具体的应用于实际中，才能使自身手艺，断发展壮大，不被新新行业所淘汰。对于今天的重点研究对象食品工厂而言，由于在不同产品在原料使用、物料损耗、市场价格等方面均存在各种差异，如何确定各产品的生产配比，以及在最优的生产配比方案之下工厂能够达到最大的产值，都是值得进行探讨研究的现实问题。
三、实例
甲、乙、丙三个城市每年需要煤炭分别为：320、250、350万吨，由A、B 两处煤矿负责供应。已知煤炭年供应量分别为：A—400万吨，B—450万吨。
由煤矿至各城市的单位运价(万元/万吨)见表1。由于需大于供，经研究平衡决定，甲城市供应量可减少0～30万吨，乙城市需要量应全部满足，丙城市供应量不少于270万吨。试求将供应量分配完又使总运费为最低的调运方案。
表1：
分析：甲、乙、丙三个城市每年的煤炭总需求量为：320+250+350=920万吨，A、B两处煤矿年煤炭总供应量为：400+450=850万吨。虚拟一个C煤矿，其供应量为70万吨，其单位运价如表2所示。
表2:
运输问题的求解方法 ——表上作业法 产销平衡表与单位运价表 表上作业法 一、产销平衡表与单位运价表 运输问题还可用产销平衡表与单位运价表进行描述。 假设某种物资有m个生产地点Ai（i=1，2，…，m），其产量（供应量）分别为ai（i=1，2，…，m），有n个销地Bj（j=1，2，…，n），其销量（需求量）分别为bj（j=1，2，…，n）。从Ai到Bj运输单位物资的运价（单价）为Cij。将这些数据汇总可以得到产销平衡表和单位运价表5.3.1。 表5.3.1 产销平衡表与单位运价表 二、表上作业法 运输这一类特殊问题可用更加简便的求解方法———表上作业法求解，实质仍是单纯形法，步骤如下： （1）确定初始调运方案，即找出初始基可行解,在产销平衡表上给出m+n-1个数字格。 （2）求非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解：是否存在负的检验数？如果存在负的检验数，则初始调运方案不是最优方案；如果所有检验数都非负，则初始调运方案已经是最优方案了。如果已经得到最优调运方案，则停止计算，否则转入下一步。 （3）确定换入变量和换出变量，找出新的调运方案（新的基可行解），即在表上用闭回路法进行调整。 (4）重复（1）～（2），直到求出最优解为止。 （一）确定初始可行基的方法 ?最小元素法 从单位运价表中最小的运价开始确定供销关系，然后考虑运价次小的，一直到给出初始基可行解为止。 ?伏格尔法 采用最小元素法可能造成其他处的更多浪费，伏格尔法考虑最小运费与次小运费之间的差额，差额越大，就按次小运费调运。
（二）最优解的判别 计算非基变量（空格）的检验数,当所有的检验数时，为最优解。 求空格检验数的方法有： ?闭回路法 以某一空格为起点找一条闭回路，用水平或垂直线向前划，每碰到一数字格转900后，继续前进，直到回到起始空格为止。 闭回路如图5.3.1的（a）、（b）、（c）等所示。从每一个空格出发一定存在并且可以找到唯一的闭回路。因为，m+n-1个数字格（基变量）对应的系数向量是一个基，任一空格（非基变量）对应的系数向量是这个基的线性组合。 ?位势法 一种较为简便的求检验数的方法。 设是对应运输问题的m+n个约束条件的对偶变量。B是含有一个人工变量X a的初始基矩阵。X a在目标函数中的系数Ca ，由线性规划的对偶理论可知 而每一个决策变量Xij的系数向量，所以 由单纯形法可知，所有基变量的检验数等于0，即 下面用具体例子说明表上作业法的计算步骤。 例1：假设某种物资共有3个产地，其日产量分别是：A1为7 t，A2为4 t，A3为9 t；该种物资的4个销售地，其日销量分别：B1为3 t，B2为6 t，B3为5 t，B4为6 t；各产地到销售地的单位物资的运价如表5.3.2所示。在满足各销售点需要量的前提下，如何调运该种物资，才能使总运费达到最小？ 表5.3.2
谢荣华、林建、岳钱华、叶俊君 【摘要】在物资调运问题中,希望运输费用最少总是人们最为关心的一个 目标。在各种设定条件的约束下,如何寻找使得总运输费用最少的最优的运输方案是运输问题的核心。为给社会生产(生活)提供既便捷又经济实惠的物资调运方案,运输问题模型的求解方法可以产生最优的决策方案。因此对运输问题的深入研究具有极其重要的理论意义和实际应用价值。表上作业法是解决运输问题的重要方法本文讨论了产销平衡运输问题的表上作业法，利用伏格尔法求初始方案，位势法求检验数，闭合回路发对可行解进行调整和改进，直至求出最优解。 【关键词】运筹学、运输问题、改善优化、表上作业法 一、理论依据 运输问题的表上作业法步骤 1、制作初始平衡表 用“西北最大运量，然后，每增加角方法”：即在左上角先给予最大运量，然后，每增加一个运量都使一个发量或手里饱。如果所有运量的数字少于 （m+n-1），则补0使之正好（m+n-1）个。 （注:补零时不能使这些书构成圈。） 2、判断初始方案是否最优 （1）求位势表：对运价表加一行一列，圈出运价表中相应于有运量的项，在增加的行列上分别添上数，使这些元素之和等于圈内的元素。这些元素称为位势数。 （2）求检验数，从而得到检验数表。 结论：若对任意检验数小于等于0，则该方案最优，否则进入3进行调整. 3、调整 （1）找回路：在检验数大于0对应的应量表上对应元素为起点，沿横向或纵向前进，如遇到有运量的点即转向，直至起点，可得到一个回路。 （2）找调整量：沿上述找到的回路，从起点开始，在该回路上奇数步数字的最小者作为调整量ε。 （3）调整方式：在该回路上奇数步-ε，偶数步+ε，得到新回路。 重复上述步骤，使所有检验数小于0，即得到最优方案。 二、背景 鉴于市场竞争日益激烈，消费者需求渐趋多样，工厂作为市场消费品的产出源头，唯有对这种趋势深刻理解、深入分析，同事具体的应用于实际中，才能使自身手艺，断发展壮大，不被新新行业所淘汰。对于今天的重点研究对象食品工厂而言，由于在不同产品在原料使用、物料损耗、市场价格等方面均存在各种差异，如何确定各产品的生产配比，以及在最优的生产配比方案之下工厂能够达到最大的产值，都是值得进行探讨研究的现实问题。 三、实例
第三章 运输问题 主要内容 运输问题的模型、算法 讲授重点 运输问题的模型、算法 讲授方式 讲授式、启发式 第一节 运输问题及其数学模型 一、运输问题的数学模型 设某种物品有m 个产地A 1,A 2,…,A m ，各产地的产量分别是a 1,a 2,…,a m ；有n 个销地B l ,B 2,…,B n ,各销地的销量分别为b l ,b 2,…,b n 。假定从产地A i (i ＝1,2,…,m)向销地B j (j ＝1,2,…,n)运输单位物品的运价是c ij ，问怎样调运这些物品才能使总运费最小? 这是由多个产地供应多个销地的单品种物品运输问题。为直观清楚起见，可列出该出该问题的运输表，如表3-1所示。 设 ij x 表示从A i 运往B j 的物品数量， ij c 表示从A i 运往B j 的单位物品的运价。则对于平 衡运输问题（ ∑∑=== n j j m i i b a 1 1），其数学模型的一般形式可表示为： ∑∑=== n j m i ij ij x c s 11 min ()()()????? ???? ==≥====∑∑==n j m i x n j b x m i a x ij j m i ij i n j ij ,2,1;,2,10 ,,2,1,,2,11 1 (3.1) 二、运输问题数学模型的特点 对于平衡运输问题( ∑∑=== n j j m i i b a 1 1 )，可以证明其有如下两个特点： (1)矩阵A 的秩R(A)＝m+n-1。 (2)问题必有最优解，而且当j i b a ,皆为整数时，其最优解必为整数最优解。 第二节 表上作业法求解运输问题 一、给出运输问题的初始可行解（初始调运方案） 1、最小元素法 解题步骤： ⑴在运价表中找到最小运价c 1k ； ⑵将的A L 产品给B k ；
表上作业法解决运输 问题
表上作业法解决运输问题 谢荣华、林建、岳钱华、叶俊君 【摘要】在物资调运问题中,希望运输费用最少总是人们最为关心的一个目标。在各种设定条件的约束下,如何寻找使得总运输费用最少的最优的运输方案是运输问题的核心。为给社会生产(生活)提供既便捷又经济实惠的物资调运方案,运输问题模型的求解方法可以产生最优的决策方案。因此对运输问题的深入研究具有极其重要的理论意义和实际应用价值。表上作业法是解决运输问题的重要方法本文讨论了产销平衡运输问题的表上作业法，利用伏格尔法求初始方案，位势法求检验数，闭合回路发对可行解进行调整和改进，直至求出最优解。 【关键词】运筹学、运输问题、改善优化、表上作业法 一、理论依据 运输问题的表上作业法步骤 1、制作初始平衡表 用“西北最大运量，然后，每增加角方法”：即在左上角先给予最大运量，然后，每增加一个运量都使一个发量或手里饱。如果所有运量的数字少于 （m+n-1），则补0使之正好（m+n-1）个。 （注:补零时不能使这些书构成圈。） 2、判断初始方案是否最优
（1）求位势表：对运价表加一行一列，圈出运价表中相应于有运量的项，在增加的行列上分别添上数，使这些元素之和等于圈内的元素。这些元素称为位势数。 （2）求检验数，从而得到检验数表。 结论：若对任意检验数小于等于0，则该方案最优，否则进入3进行调整. 3、调整 （1）找回路：在检验数大于0对应的应量表上对应元素为起点，沿横向或纵向前进，如遇到有运量的点即转向，直至起点，可得到一个回路。 （2）找调整量：沿上述找到的回路，从起点开始，在该回路上奇数步数字的最小者作为调整量ε。 （3）调整方式：在该回路上奇数步-ε，偶数步+ε，得到新回路。 重复上述步骤，使所有检验数小于0，即得到最优方案。 二、背景 鉴于市场竞争日益激烈，消费者需求渐趋多样，工厂作为市场消费品的产出源头，唯有对这种趋势深刻理解、深入分析，同事具体的应用于实际中，才能使自身手艺，断发展壮大，不被新新行业所淘汰。对于今天的重点研究对象食品工厂而言，由于在不同产品在原料使用、物料损耗、市场价格等方面均存在各种差异，如何确定各产品的生产配比，以及在最优的生产配比方案之下工厂能够达到最大的产值，都是值得进行探讨研究的现实问题。 三、实例 甲、乙、丙三个城市每年需要煤炭分别为：320、250、350万吨，由A、B 两处煤矿负责供应。已知煤炭年供应量分别为：A—400万吨，B—450万吨。
第3章运输问题
第三章运输问题 一、选择 1.运输问题在用表上作业法计算的时候，用闭回路法进行调整检验时，通过任 一空格可以找到（）闭回路 A、惟一 B、多个 C、零个 D 不能确定 2.在产销不平衡的运输问题中，如果产大于销，我们（B ）把他变成一个产销 平衡的运 输问题 A 假想一个产地 B 假想一个销地 C 去掉一个产地 D 没有办法 3.最小元素法的基本思想就是（ D）。 A依次供应B全面供应 C 选择供应 D就近供应 4.运输问题中在闭回路调整中，使方案中有数字的格为（ C ）。 A m B n C m+n D m+n-1 5.在表上作业法中，调运方案中有数字的格为（ C ） A m+n B m-n C m+n-1 D m*n 6.运输问题的数学模型中，包含有（ D）变量。 A m+n B m-n C m+n-1 D m*n 7. 运输问题的数学模型中，包含有（ A）个约束条件。 A m+n B m-n C m+n-1 D m*n 8. 运输问题的数学模型中,系数矩阵中线性独立的列向量的最大个数为（C ） A m+n B m-n C m+n-1 D m*n 9. 运输问题的解中的基变量数一般为（C ） A m+n B m-n C m+n-1 D m*n
10.运输问题中，在检验数表上所有检验数都（C ），此时运输表中给出的方案就是最优方案。 A大于零B等于零C大于等于零D小于零 11.在产销不平衡的运输问题中，如果销大于产时，可以在产销平衡表上 （ A），把他变成 一个产销平衡的运输问题 A 假想一个产地 B 假想一个销地 C 去掉一个产地 D 没有办法 12.运输问题数学模型的特点之一是（） A 一定有最优解 B 不一定有最优解 C 一定有基可行解 D 不一定有基可行解 13.运输问题的数学模型的约束条件的系数矩阵的元素由（）组成。 A 0B1C0,1D 不确定 14. 二、填空 1.求解不平衡的运输问题的基本思想是(设立虚供地或虚需求点，化为供求平衡的标准形式) 。 2.运输问题中求初始基本可行解的方法通常有 (最小元素法 )、 (伏格尔法 ) 两种方法。 3.伏格尔法有时就用作求运输问题最优方案的（近似解） 4.运输问题最优性检验通常有（闭回路法、位势法）两种方法。 5.
第32卷第3期2000年6月 南 京 航 空 航 天 大 学 学 报 Jo urnal o f Nanjing Univ ersity o f Aeronautics&Astronautics V o l.32No.3 Jun.2000 运输问题表上作业法的改进研究 李时椿 (南京经济学院管理系 南京,210042) 摘要 在传统的“闭回路法”和“位势法”基础上,提出利用“流水原理”来寻求运输问题最优解。即以“最小元素法”求得初始调运方案后,将表中各栏单位物资的运价视为“水位”的高低,将已安排的运输量视为处于一定水位高度的“蓄水量”,依据“水往低处流”的自然界基本原理,考察处于最高“水位”的“蓄水量”沿其所在的行或列的“渠道”流向最低“水位”的可能性,来确定“流向”及其相应的“闭回路”,据此调配运输方案,直至总体“蓄水量”处于最低水位状态,则方案达最优。 关键词:输运理论;流水原理;闭回路法 中图分类号:F224.3 引 言 运输问题通常用“表上作业法”求解——先以“最小元素法”或“西北角法”给出一个初始方案,再以“闭回路法”或“位势法”进行调整改进,直至获得最优方案。但在实际优化调整时,无论采用何种方法,都必须逐一计算每个空栏处的检验数,才可分析比较并作出调整,其过程重复、计算繁冗,极大地影响了实际应用和推广。本文借助自然界“水往低处流”的基本规律,利用“流水原理”寻求最有效的调配路线进行优化,从而使求解过程简捷而又直观,大大克服了传统方法繁锁重复的弊端。 1 流水原理求解供求平衡的运输问题 某运输问题如下,运价(元/吨)标在图1中各栏斜线左上方,问该如何调运可使总运费支出为最少[1](图中O表示产量,S表示销售量或需求量,下同)。 解 (1)以“最小元素法”确定初始方案。图1中圈内数据表示初始方案所安排的运输量,初始方案总运费为86元。 (2)以“流水原理”对初始方案优化调整。 (A)确定“最高水位”。“水位”指各栏中单位运量的运价,“最高水位”系指已安排有运 收稿日期:1999-06-02;修改稿收到日期:1999-09-13 作者:李时椿,男,副教授,1949年9月生。
第八章运输及配送路线的优化 教学目的：使学生理解各种运输方式的特点及运输方式选择的原则，掌握运输方式选择的定量分析法，理解存在中间运转的物资调配方法，掌握旅行 商问题和中国邮递员问题的解法以及扫描法和节约法。 基本要求：1、理解各种运输方式的特点； 2、掌握运输方式选择的定量分析法； 3、理解存在中间运转的物资调配方法； 4、掌握旅行商问题和中国邮递员问题的解法。 教学重点：扫描法、节约法 教学时数：6学时 第一节运输方式的选择 ?运输方式选择的原则 当同时存在多种运输方式可供选择的情况下，就需要进行选优抉择。通常根据各种运输方式的经济特性和服务特征来选择合适的运输方式，即主要依据运输成本、运输速度、可靠性、安全性等指标进行判断和选择。 安全性原则——首要的原则 及时性原则 准确性原则 经济性原则——主要原则 货物运输的六大方式： 根据运输工具的不同，可分为：水路、公路、铁路、航空、管道和多式联运等运输形式。 在各种运输方式中，如何选择适当的运输方式是物流合理化的重要问题。可以选择一种运输方式也可以选择使用联运的方式。 运输方式的选择，需要根据运输环境、运输服务的目标要求，采取定性分析与定量分析的方法进行考虑。 ?运输方式选择的定性分析法 定性分析法主要是依据完成运输任务可用的各种运输方式的运营特点及主要功能、货物的特性以及货主的要求等因素对运输方式进行直观选择的方法。 1.单一运输方式的选择 单一运输方式的选择，就是选择一种运输方式提供运输服务。公路、铁路、水路、航空和管道五种基本运输方式各有自身的优点与不足，可以根据五种基本运输方式的优势、特点，结合运输需求进行恰当的选择。 一般要考虑的因素是：
任务1.3 优化物流运输的线路 ●任务描述 面对高油价以及公路计重收费的到来，物流运输企业的成本剧增，如何应对挑战？运输公司普遍的做法是：强化经营管理，在降本减耗上下功夫，抵御高物流成本经营风险。其中重要的一条就是不断优化运输线路，减少人为加大的运距，节约油耗，避免油资源浪费，提高运输效率。案例1.3就是广西运德物流公司成功地为康鑫全药业集团运输药品的经验。 ■案例放送 【案例1.3】康鑫全药业集团公司有4个药品生产厂：A1（南宁四塘）、A2（巴马）、A3（南丹）和A4（柳州），2008年第二季度生产供应高科技产品——“护肝王”特效药（针剂）分别为＋20、＋60、＋100、＋20万盒（供应量记“+”）；有5个批发配送中心B1（平果）、B2（合山）、B3（宜州）、B4（河池）、B5（贵州黔南县），负责推销配送“护肝王”分别是-30、-30、-50、-70、-20万盒（需求量或销售量记“-”）。“护肝王”配送的交通线路用图表示，见图1.3-1。图中○表示生产供应点，□表示配送点，站点旁边的数字表示生产（正数）或配送（负数）“护肝王”数量。线路旁括号内标注的数字表示相邻两点间的距离（为了计算方便，未取实际准确数）。 ■案例研讨 优化物流运输线路与运输线路开发有区别，它是在已知货物名称及数量、货源地和目的地的情况下，根据运输合理化原则对运输线路的选择与优化。 物流运输合理化要求以最佳的运输线路、最快的运输速度和最低的运输费用等将物品从原产地运送到目的地，案例中康鑫全集团的4个生产供应点，5个批发配送点，线路图中有成圈的，有不成圈的，属于相对复杂的情况。应该如何安排，才能达到路程最近和时间及费用最省？经过本单元以下内容的学习，可以找到解决问题的办法。