第5章 运输模型

1、第5章 运输模型 5.1 运输问题及其数学模型 5.2 5.2 表上作业法表上作业法 5.2.1 初始方案的确定 5.2.2 最优性检验 5.2.3 非最优方案的调整 5.2.4 产销不平衡问题的解法 5.3 运输模型的应用 运输模型是线性规划诸多模型中较早引起人们关注的一类模型，由美国学者希奇柯克（Hitchcock，1941）和库普曼（Koopmans，1947）提出。 中国 “图上作业法”（1958年） 1975年康托洛维奇和库普曼因资源配置理论研究获得诺贝尔经济学奖（丹茨格）（24、12、4）（日内瓦国际应用系统分析研究所） 运输模型是线性规划诸多模型中的特例，其约束方程组对应的系数矩

2、阵具有特殊的结构，使得有可能找到比单纯形法更为简便的求解方式。 运输问题的专门求解方法专门求解方法不仅适用于运输问题本身，还适用于其他相当多的应用问题（如指派问题），更使其得到人们的高度重视和深入的系统研究。 在经济建设中经常会碰到大宗物资的调运问题。如煤、铁、木材、粮食等大宗物资，在全国有若干生产基地，根据现已有的交通网络，应该如何制定调运方案，将这些物资运往各消费地点。1）“产地”货物发出的地点2）“销地”货物接收的地点3）“产量”各产地的可供货量4）“销量”各销地的需求数量 【运输问题的描述】 运输问题就是研究如何组织调运，在满足各销地需求的前提下，追求总的运费（或里程、时间等）达到最少

3、？ 运输问题所建立的模型就称为运输模型运输模型。5.1 运输问题及其数学模型【例例1 1】 某饮料集团在国内有3个生产工厂，分布在城市 A1，A2，A3；其一级分销商有4个，分布在城市B1，B2，B3 ， B4 。现已知每月各生产工厂的产量、各分销商的需求量； 以及从Ai到Bj的每吨饮料的运费cij（见下表）。 销地销地产地产地B B1 1B B2 2B B3 3B B4 4产量产量A A1 16 63 32 25 55 5A A2 27 75 58 84 42 2A A3 33 32 29 97 73 3销量销量2 23 31 14 4为发挥集团优势，公司需要统一筹划运销问题，求使为发挥集团

4、优势，公司需要统一筹划运销问题，求使运费最小运费最小的的调运方案。调运方案。解：建立该运输问题的解：建立该运输问题的LPLP模型如模型如下下343332312423222114131211792348 57523621xxxxxxxxxxxxminBAxjiij）目标函数：的数量（吨）到销地为每月从产地设）决策变量：4,3,2,1;3,2,104132325.3342414332313322212312111343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxtsij）约束条件：运输问题的一般提法： 设某种物资有m个产地 ，其产量分别为 ；有n

5、个销地 ，其销量分别为 ；从 到 的单位运价为 。问应该如何组织调运才能使总的运费最少？miAi, 2 , 1iajbnjBj, 2 , 1iAijcjB设 为把这种物资从Ai运到Bj的数量，简称为Ai至Bj的运量运量；设z为总运费，则一般运输问题及其数学模型可以简洁地表示为下表这种形式，称为表格形式的一般运输模型表格形式的一般运输模型，简称表式表式运输模型运输模型。ijxp136p136表式运输模型 销地销地产地产地A1A2Am产量产量a1a2amB1B2Bn销量销量b1b2bnc11c12c1nc21 c22c2ncm1cm2cmn x11 x12 x1nx21 x22 x2n xm1 x

6、m2 xmnnjmixbxaxtsxcminijjmiijinjijminjijij, 2 , 1;, 2 , 10. . 1111产销平衡产销平衡njmixbxaxtsxcminijjmiijinjijminjijij, 2 , 1;, 2 , 10. . 1111产大于销产大于销njmixbxaxtsxcminijjmiijinjijminjijij, 2 , 1;, 2 , 10. . 1111产小于销产小于销【运输模型运输模型 系数矩阵系数矩阵】111111111111111111Am m行行n n行行 【讨论】运输模型系数矩阵的特征？ 表面任意一个运输模型系数矩阵同一个与之规模相当的

7、普通LP模型的系数矩阵相比都大为简洁，且其中只含有0和1这两个元素，且0的个数远远多于1的个数，一般我们把这样的矩阵称为稀疏阵稀疏阵。 深层次对任意产销平衡的运输模型来说，其系数阵的前m行之和等于后n行之和。意味着？意味着？ 可以证明：平衡模型的系数阵和增广阵的秩均为m+n-1，这也意味着平衡模型的基本可行解所含基变量的个数必为m+n-1个。 【结论】m+n-1 【讨论】上述运输问题所建立的LP模型如果用传统的 单纯形法进行求解会出现什么情况？ 【友情提示友情提示】 1）表上作业法仅仅适用于产销平衡产销平衡的运输问题 2）表上作业法基于一种作业表 “产销平衡及运价表”特征？特征？5.2 5.2

8、 表上作业法表上作业法 用单纯形法求解LP式运输模型，必须删掉一个函数约束，而且计算量很大，但表上作业法不必如此费力，而是另辟蹊径。 表上作业法是一种专门求解运输问题的特殊方法，其实质仍是单纯形法，只是具体计算和术语有所区别。 与一般的LP问题不同的是，平衡运输问题总是存在最优解。 销地销地产地产地B B1 1B B2 2B B3 3B B4 4产量产量A A1 16 63 32 25 55 5A A2 27 75 58 84 42 2A A3 33 32 29 97 73 3销量销量2 23 31 14 41010 表上作业法的基本思想及基本步骤 【基本思想基本思想】类似于单纯形法，只是叫法

9、不同而已，如基本 可行解称为“方案”；迭代称为“调整改进”等。 【基本步骤基本步骤】 1）确定初始方案； 2）对初始方案进行最优性检验； 3）调整、改进非最优方案； 4）直至得到最优方案（惟一方案或多重方案）运输问题求解思路运输问题求解思路确定初始方案确定初始方案（初始基本可（初始基本可行解）行解） 输出最优方案输出最优方案改进调整改进调整（换基迭代）（换基迭代）判断是判断是否最优否最优结果结果是是否否5.2.1 5.2.1 初始方案的确定初始方案的确定 确定初始方案的方法有很多，原理各不相同确定初始方案的方法有很多，原理各不相同 左上角法（西北角法、阶梯法）最小元素法最小元素法最大差额法最大

10、差额法 Russell概算法销地销地产地产地B1B2B3B4产量产量A163255A275842A332973销量销量231410左上角法左上角法 最小元素指？ 最小元素法的基本思想？最小元素法“最小运价最小运价”“就近运给就近运给” 先给作业表中最小运价那格安排运量，然后划去该运价所在的行或列；继续这样做，每次总在表中剩余运价的最小元素那格确定运量，直至求出初始方案为止。销地销地产地产地B1B2B3B4产量产量A163255A275842A332973销量销量231410(0)(0)初始方案：初始方案：x x1111=2,x=2,x1313=1,x=1,x1414=2,x=2,x2424=2

11、,x=2,x3131=0,x=0,x3232=3=3，Z=38Z=38【结论结论】最小元素法确定初始方案的4条原则 运量选择时必须遵循产、销量比较取其小的原则 确定某格的运量后，其所在行或列其余格运量为0，并划去满足约束的行或列，同时满足只能划去其中之一 中间遇到0运量也必须画上 最后一个格产地、销地同时满足，同时划去最小元素法确定的有效的有效的初始方案满足 初始作业表中有 m+n-1m+n-1 个画圈数字（运量） 画圈数字（运量）恰好符合产销平衡运输问题的约束条件 作业表中不存在以画圈数字为顶点的闭回路【闭回路闭回路】从表中任一画圈数字所在格出发，沿水平或垂直方 向前进，当碰到另一个画圈数字

12、后，可沿原方向继 续前进，也可以转90继续前进，如此进行下去最 终回到出发点。 注意：用最小元素法得到的初始方案肯定不会形成闭回路！销地销地产地产地B1B2B3B4产量产量A163255A275842A332973销量销量231410B B1 1B B2 2B B3 3B B4 4B B5 5A A1 1X11X12A A2 2X23X25A A3 3X31X35A A4 4X42X43 最大差额法 “差额” 行差和列差 “最大差额” 两最小元素之差（正值） 不能按最小运费就近供应，就考虑次小运费 差额越大，说明当不能按最小运费调运时，运费增加的越多v5.2.2 5.2.2 最优性检验最优性检

13、验v确定初始方案后，就要对它进行最优性检验，即检验初始基本可行解对应的目标函数值是否达到最优。v运输问题要求目标函数求最小值，故当检验数 时，表示该方案为最优。v计算检验数的方法有 vA 位势法vB 闭回路法0ij 1 1、位势法、位势法 A 两个位势量：产地的位势量 ；销地的位势量 B 两个基本公式：1）该公式仅仅适用于基变量所在格（基格）2）决策变量的检验数计算公式：jiijvucjiijijvuciujv销地销地产地产地B1B2B3B4产量产量uiA162 321 52 50A2758422-1A330 23 973-3销量销量2314vj6525-2217105非基变量非基变量x x1

14、212的检验数的检验数 1212= c= c12 12 u u1 1 v v2 2 = -2= -2，即让非基变量，即让非基变量x x1212从从0 0增增到到1 1，可使总运费减少，可使总运费减少2 2百元。百元。 2 2、闭回路法、闭回路法 这里的闭回路是指以非基变量的格子为始点和终点，而其余顶点均为画圈数字（基变量）的一条封闭回路，用水平或者垂直线向前画，每碰到一数字格转90度后继续前进，直到回到始点。 偶点（偶点（+ +） 奇点（奇点（- -） 结论结论1 1：闭回路都是唯一的。：闭回路都是唯一的。 结论结论2 2：任一非基变量的检验数都等于它的闭回路上所有：任一非基变量的检验数都等于

15、它的闭回路上所有偶点运价的总和与所有奇点的运价总和之差。偶点运价的总和与所有奇点的运价总和之差。 5.2.3 非最优方案的调整 当作业表中出现负检验数时，表明此方案仍不是最优方案，需要进行调整，调整时仍用闭回路法闭回路法。（1 1）进基变量的确定）进基变量的确定若同时有多个负检验数一样最小，则选其中最小运价所对应的那个进基。（2 2）离基变量的确定）离基变量的确定在进基变量的闭回路上，按确定离基变量，同时也确定了调整量t。若有多个奇点的运量值一样，则选其中最大运价所对应的那个离基。（3 3）非最优方案的调整）非最优方案的调整所有偶点的运量 + t 所有奇点的运量 - t0ijijmin为奇点i

16、jpqijxxxmint x x12 12 进基进基最小调整量为最小调整量为2 2，即，即t=2t=2， x x11 11 离基离基销地产地B1B2B3B4产量A162 3 x1221 52 5A275842 2A330 23 973销量2314+ +- -+ +- -销地销地产地产地B B1 1B B2 2B B3 3B B4 4产量产量A A1 16 6 3 3 2 21 1 5 52 2 5 5A A2 27 75 58 84 42 2 2 2A A3 33 3 2 2 9 97 73 3销量销量2 23 31 14 4 调整后新方案：调整后新方案：x x1212=2,x=2,x1313

17、=1,x=1,x1414=2,x=2,x2424=2,x=2,x3131=2,x=2,x3232=1=1，Z=34Z=34 22 1 定理定理1(惟一最优解的判定定理惟一最优解的判定定理) 如果在表上作业法得到的最终表如果在表上作业法得到的最终表中中,非基变量的检验数全都大于零非基变量的检验数全都大于零,则该运输问题存在惟一最优解则该运输问题存在惟一最优解。 定理定理2(多重最优解的判定定理多重最优解的判定定理)对于一个运输问题对于一个运输问题,在得到的第一在得到的第一个最优解的最终表中个最优解的最终表中,若至少存在一个检验数为零的非基变量若至少存在一个检验数为零的非基变量,并并且在以这个非基

18、变量为出发点的闭回路上且在以这个非基变量为出发点的闭回路上,在需要减少运输量的在需要减少运输量的顶点中顶点中,最小运量不等于零最小运量不等于零,那么该运输问题存在多重最优解那么该运输问题存在多重最优解。 运输问题的多重解运输问题的多重解运输问题多重解运输问题多重解B1B2B3B4产量A13113107A219284A3741059销量3656 5.2.4 产销不平衡问题的解法 A 产大于销 虚设销地（经济意义：贮存）虚设销地（经济意义：贮存） B 产小于销 虚设产地（经济意义：脱销）虚设产地（经济意义：脱销） 虚设的产地的产量或销地的销量等于产销量之差的绝对值，且其运价全部为0。 用最小元素法确定初始方案时，尽管虚设产地或销地对应的运价为0，均为最小，但我们先不考虑它，先给有实际运输任务的其他产销地之间安排运量，这样处理往往能获得较好的初始方案，减少调整的次数（为什么？）。 5.3 运输模型的应用 短缺资源的分配问题 转运问题 生产调度问题（*） 这里所说的生产调度问题生产调度问题是指对某产品在一个总的计划周期内的某项既定总生产指标（总产量），应怎样分解到各个生产周期，才能既保证在总计划期内完成该项总生产指标，又能使总生产费用最少。案例 拖拉机生产调度问题前进拖拉机厂与农机供销站签订了一项生产100台某种