2运输问题解析

第二章运输问题【教学内容】运输问题的基本概念，表上作业法，不平衡运输问题的求解。【教学要求】要求学生理解运输问题基本概念、解的性质，掌握表上作业法，并能将不平衡运输问题转化为平衡运输问题求解，复杂的运输问题可用LINGO软件求解。【教学重点】运输问题解的性质，运输问题的表上作业法，检验数的求法及运量的调整，运输模型的建立。【教学难点】表上作业法、求检验数的闭回路法及位势法。【教材内容及教学过程】运输问题（TransportationProblem，简记为TP）是一类常见而且极其特殊的线性规划问题.它最早是从物资调运工作中提出来的，是物流优化管理的重要的内容之一.从理论上讲，运输问题也可用单纯形法来求解，但是由于运输问题涉及的变量及约束条件较多，而其数学模型具有特殊的结构，所以存在一种比单纯形法更简便的计算方法，一一表上作业法，用表上作业法来求解运输问题比用单纯形法可节约计算时间与计算费用.但表上作业法的实质仍是单纯形法.本章首先介绍运输问题的数学模型及其特点；接着介绍表上作业法及主要步骤，表上作业法与单纯形法的关系；通过运输问题的解决，可充分体现表上作业法的简便和单纯形法的魅力.最后给出运输问题的一些应用例子.第一节运输问题的模型§1・1问题的提出一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。例2・1・1某公司从两个产地气、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费最小？

表2.1.1销产、、地地BBB3产量A1646200A2655300销量150150200解：此为产销平衡的运输问题，总产量=总销量设七.为从产地Ai运往销地Bj的运输量，得到下列运输量表表2.1.2地B]B2B3产量Axx12x13200Ax21x22x23300销量150150200模型为minf-6x+4x+6x+6x+5x+5x@十工+x+x+300s・l212223x+x=150<x12+x22=150x13+x23=200^xj>0(i=1,2;j=1,2,3)系数矩阵为111000000111100100010010001001可以看出运输问题模型系数矩阵有如下特征:（1）共有m+n行，分别表示各产地和销地；mxn列，分别表示各决策变量；（2）每列只有两个1，其余为0,分别表示只有一个产地和一个销地被使用。一般运输问题的提法：

假设A,A,...A表示某物资的m个产地；B,B，…,B表示某物资的n个销地;12m12nS表示产地A,的产量；dj表示销地B的销量；*表示把物资从产地A,运往销地Bj的单位运价。如果则称该运输问题为产销平衡的运输问题;否则，称为产销不平衡的运输问题。则称该运输问题为产销平衡的运输问题;否则，称为产销不平衡的运输问题。将变量与数据表合并起来表2.1.3运输问题数据表将变量与数据表合并起来\销产\地地\B]B2■…Bn产量ACC■…CS111121n1ACC■…CS221222n2::::::ACC■…CSmm1m2mnm销量dd■…d12n表2.1.4运输问题变量表销产^\地地B]B2■…Bn产量Axx■…xS111121n1Axx■…xS221222n2::::::Axx■…xSmm1m2mnm销量dd■…d12n

1C11xC12x12■…C1nx1nS]气C21x21C22x22■…C2nx2nS2:■■■1■■■1:■■■1:AmCm1xm1Cm2xm2■…CmnxmnSm销量d1d2■…dn于是得到一般运输问题的数学模型minf空i=1J=1Ex<S(i=1,2,—m)J=1(2.1.1)s.t2x寸J(>,=)dj(J=1,2,...n)iTxj>0(i=1,2,…m;J=1,2,…n)(2.1.1)此约束中前m个为产量约束，后n个为销量约束。平衡的运输问题其约束条件为：minf点i=1J=1

Ex=S(i=1,2,...m)j=i(2.1.2)s.t<Ex=d(j=1,2,…n)i=1x>0(i=1,2,…m;j=1,2,…n)(2.1.2)可以看出：在产销平衡问题中，前m个为产量约束式、后n个为销量约束式成为等式。在实际问题建立运输问题模型时，还会出现如下一些变化：（1）有时问题表面看不是运输问题，但其仍要求费用最低或要求目标函数（利润最大或营业额）最大化，仍可看成运输问题；（2）当某些运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束；（3）产销不平衡的情况。当销量大于产量时可加入一个虚设的产地去生产不足的物资，这相当于在前m个产量约束式每一式中加上1个松弛变量，共m个；当产量大于销量时可加入一个虚设的销地去消化多余的物资，这相当于在后n个为销量约束式每一式中加上1个松弛变量，共n个。运输问题是一种特殊的线性规划问题，在求解时仍可以采用单纯形法的思路，如图所示。图2.1.1图2.1.1由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，则无法利用这些有利条件。人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法。下面主要讨论运输问题的一些性质基本可行解、检验数以及基的转换等问题。§1.2运输问题数学模型解的性质定理2.1.1产销平衡运输问题（2.1.2）必有可行解，也必有最优解.证明：设

则取乙=£b=diji=1j=则取乙=£b=diji=1j=1xij-,(i=1,2,…,m;j=1,2,..•n)d(2.1.3)显然有Xjj>0,ijj=1二iji=1所以(2.1.3)又=£ab=a&ddjj=1j=1=&。气=七&ddii=1i=1=a(i=1,2,…m)=b(j=1,2,…m)j是(2.1.2)的一个可行解.又因为七＞0,(i=1,2,—m;j=1,2,—n)，故对于任一可行解£〃£模型(2.1.2)的目标函数值都不会为负数，即目标函数值有下界零，对于求极小化问题，目标函数值有下界，则必有最优解.运输问题的矩阵属于一种大型稀疏矩阵，所谓“大型”是指矩阵的规模大，矩阵A共有m+n行，mn列。当m和n较大时，矩阵A的规模是很大的，所谓“稀疏”是指矩阵中的非零元素较少.如果将平衡运输问题的模型写成矩阵形式记：X=(x11，x，12…气，x21，x22…x2n，…，xm1，xm2C=(C11，c…12C1n,C21,C，…22•C2n，…，Cm1,Cm2，…',^mn)A=[P11,P12,…,P1n,P21,P22,..,Cn,m1,七2,…,Pmn]d,d，…d]t氏巳，S2,...，皿,，…x)T模型(3.1.2)的矩阵表示为minf=CX(2.1.4)XXXX•••1n21222nXXX•mlm2mn11…11XXXX•••1n21222nXXX•mlm2mn11…111…1A=1111111(m+n)xmn(2.1.5)矩阵A中相应于x〔j的列的量为PjP=e.+e(i=1,2,…m;j=1,2,—n)imm+jei=(0,-0,1,0,-0)tem+j=(0,-0,0,-0,1,0,-0)t即%中的第i个分量和第m+j个分量为1,其余的元素均为0.定理2.1.2产销平衡运输问题（2.1.2）约束方程系数矩阵A的秩等于m+n-1.证明：显然m+n<mn,（m,n>2）,于是秩（A）Wm+n.又由平衡条件（2.1.2）可知，A的前m行之和等于后n行之和，因此A的行是线性相关的，故必须秩（A）Wm+n-1,但A中有m+n-1阶子式其行列式不为零。定理2.1.3运输问题（2.1.2）的基可行解中应包含m+n-1个基变量.因平衡运输问题有一个约束条件多余，而其系数矩阵的秩为m+n-1。定理2.1.4运输问题（2.1.2）的约束条件的系数矩阵A的所有各阶子式只取0，1或-1三个值.可由数学归纳法证得。定理2.1.5如果运输问题（2.1.2）中的所有产量和销量^,,气都是整数，那么，它的任一基可行解都是整数解.'7证明：在约束条件Ax=b中，去掉多余约束，得到A'x=b'，b‘的分量都是整数.设x是任一基可行解，其基变量为detBitjtdetBXjx2j,…XijB为对应的基矩阵，(t=1,2,…，m+n-1)容易看出，detBt是个整数，而detB是A的某一个m+n-1阶子式.由定理2.1.3知

detB=1.因此，XitJt(t=1,2,…，m+n-1)都是整数.§1.3运输问题的基变量与基可行解运输问题是特殊的线性规划，单纯形法的原理仍适合于运输问题，为此需要了解其基可行解的性质。为了说明基变量与基本可行解的特征，此处需要引入一些概念。下面的讨论建立在表（2.1.4）中决策变量格的基础上。定义2.1.1在上表的决策变量格中，凡是能够排列成下列形式的x,x,x,x，…，x,x（2.1.6）abaddcdestsb(2.1.7)或x,x,x,x，…，x,xabcbcdedstat(2.1.7)其中，a,d,…,s各不相同；b,c,・・・,t各不相同，我们称之为变量集合的一个闭回路，并将式（2.1.6）和式（2.1.7）中的变量称为这个闭回路的顶点。例如，x，x，x，x，x，x；x，x，x，x，x，x131636342423235355454121等都是闭回路。若把闭回路的各变量格看作节点，在表中可以画出如下形式的闭回路图2.1.2根据定义可以看出闭回路的一些明显特点，闭回路是一个具有如下条件的顶点格子的集合（1）每一个顶点格子都是转角点；（2）每一行（或列）若有闭回路的顶点，则有两个顶点；（3）每两个顶点格子的连线都是水平的或垂直的；（4）闭回路中顶点的个数必为偶数.根据运输问题（2.1.2）的约束方程系数矩阵A中的列向量%的特征，可以推出闭回路有如下代数性质：性质2.1.1构成闭回路的变量组x,x,x,x，…，x,x所对应的系数abaddcdestsb列向量P,P,P,P，…，P,P（2.1.8）abaddcdestsb必线性相关.证明：由直接计算可知P-P+P-P+•••+P-P=0abaddcdestsb故向量组（2.1.8）必线性相关性.性质2.1.2若变量组x,x,x,x，…，x,x中有一个部分组构成闭回abaddcdestsb路，则变量组对应的列向量组七，七，P，P，…，P，七abaddcdestsb是线性相关的.证明：由性质2.1.1知，向量组（2.1.8）中有一个部分组（与闭回路的顶点相对应的向量组）是线性相关的.根据线性代数理论知，若向量组中有一部分线性相关，则全体也线性相关，因此向量组必线性相关.推论2.1.2若变量组对应的列向量组线性无关，则该变量组一定不包含闭回路.根据以上结论以及线性规划基变量的特点，可以得到下面的定理。定理2.1.6变量组x，x，x，x，…，x，x所对应的系数列向量abaddcdestsbP，P，P，P，…，P，P线性无关的充分必要条件是这个变量组中不包含闭回abaddcdestsb路。定理2.1.7产销平衡运输问题的m+n-1个变量构成基变量的充分含闭回路。定理2.1.7给出了运输问题基本解的重要性质，也为寻求基本可行解提供了依据。第二节表上作业法表上作业法（又称为运输单纯形法）是根据单纯形法的原理和运输问题的特征，设计出来的一种在表上运算的求解运输问题的简便而有效的方法，作为一种迭代算法，它的主要步骤是：（1）求一个初始调运方案；（2）根据最优性判别准则来检查这个基本可行解是不是最优的？若是则迭代停止；否则转下一步；（3）改进当前方案，得到新的方案，再返回（2）.直至求出最优解为止§2.1初始基本可行解的确定根据上面的讨论，要求得运输问题的初始基本可行解，必须保证找到m+n-1个不构成闭回路的基变量。一般的方法步骤如下：（1）在运输问题求解作业数据表中任选一个单元格七（A,行Bj列交叉位置上的格）,令x「=min｛气,b｝，即从A,向B运最大量（使行或列在允许的范围内尽量饱和，即使一个约束方程得以满足），填入七的相应位置；（2）从气和气中分别减去x：的值，修正为新的气和b，即调整a,的拥有量及Bj的需求量；（3）若气=0,则划去对应的行（已经把拥有的量全部运走），若气=0则划去对应的列（已经把需要的量全部运来），且每次只划去一行或一列（即每次要去掉且只去掉一个约束）；（4）当最终的运输量选定时，其所在行、列同时满足，此时要同时划去一行和一列。这样，运输平衡表中所有的行与列均被划去，则得到了一个初始基本可行解。否则在剩下的运输平衡表中选下一个变量，返回（1）。上述计算过程可用流程图描述如下：注：为了方便，这里总记剩余产量和销量为图2.2.1注：为了方便，这里总记剩余产量和销量为按照上述方法所产生的一组变量的取值将满足下面条件：（1）所得的变量均为非负，且变量总数恰好为m+n-1个；（2）所有的约束条件均得到满足；（3）所得的变量不构成闭回路。因此，根据定理2.1.7，所得的解一定是运输问题的基本可行解。在上面的方法中，X的选取方法并没有给予限制，若采取不同的规则来选取七/则得到不同的方法，较常用的方法有西北角法和最小元素法。下面分别举例并予以介绍。西北角法从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。用西北角法初始方案的方法，虽然比较简单，但因为它没有考虑到运价，因此得到的初始方案一般离最优方案较远.最小元素法是一种考虑运价的求初始方案的方法，遵循如下规则:优先安排单位运价最小的产地与销地之间的运输业务.一般来说，用这种方法制定的调运方案，其总运费会比用西北角法得到的调运方案更省，当然也不一定是最省的.最小元素法最小元素法是从运价最小的格开始，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。一般地说在用西北角法和最小元素法求初始方案时，应注意以下几点：（1）在填入一个数时，如果行和列同时饱和，规定只划去一行或一列，而不能同时划去行和列，这时行和列的修正量均为0.如果划去的是行（或列）下次到修正量为0的列（或行）时，就必须取相应的变量的值为0，填入相应的格子，划去该列（或行），以保证填数字的格子为m+n-1.（2）在剩下最后一个空格时，只能填数（必要时可取0），并划去所在行和列.（3）在某一行（或列）填最后一个数时，如果行和列同时饱和，则规定只划去该行（或列）.例2.2.1某食品公司下属的A,A,A三个厂生产方便食品，要运送到B,B,B,B四1231234个销售点，数据如下表：表2.2.1销产、^地B1B2B3B4产量气3113107A219284A3741059销量bj365620（产销平衡）西北角法的初始调运方案（基本可行解）表2.2.2产\地地B]B2BB4产量a43113o1°CZ57A2［。9284

气74103569销量bj365620最小元素法的初始调运方案（基本可行解）表2.2.3^\销产、地地、B2B3B4产量ai3^_^113107A2139^_^28o4A3741059销量bj365620§2.2基本可行解的最优性检验最优性检验就是检查所得到的方案是不是最优方案。检查的方法与单纯形方法中的原理相同，即计算检验数。由于目标函数要求取得极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案；否则就不是最优，需要进行调整。下面介绍两种求检验数的方法。1.闭回路法下面是闭回路法的理论基础。（s=m+n-1）是运输问题（2.1.2）的一组基变定理2.2.1设l1j，l1j2，（s=m+n-1）是运输问题（2.1.2）的一组基变lrjrXlsXlsjs，Xirjr（2.2.1）中存在唯一的以xi］为顶点的闭回路.证明：首先证明存在性，写出变量组中存在唯一的以xi］为顶点的闭回路.证明：首先证明存在性，写出变量组P，P，l1j1l2j2对应的列向量jPlj

srr…，Plsj由定理2.1.3，它们必线性相关，再由定理2.1.6，变量组（2.2.1）中一定存在闭回路.其次，再让唯一性.设变量组（2.2.1）存在两个不同的闭回路，那么，P就可用两种lrj不同的方式表示成P，P，…，P的线性组合.显然，这与P，P，…，P线l1j1l2j2lsjsl1j1l2j2lsjs性无关相矛盾，故变量组（2.2.1）存在唯一的闭回路.这样，如果对闭回路的方向不加区别（即只要起点及其他所有顶点完全相同，而不区别行进方向是顺时针还是逆时针），那么以每一个非基量为起始顶点的闭回路就存在而且唯一。因此，当基变量确定后对每一个非基变量可以找到而且只能找到唯一的一个闭回路。下表中用虚线画出以非基变量七为起始顶点的闭回路表2.2.4地_—B?BB4产量a.311\410i37气1392；8；41气74；105；96■-■3销量气365620根据单纯形法原理，检验数是将基变量用非基变量表示代入目标函数时，非基变量的系数，因此在运输问题中，要计算非基变量（即空格处）的检验数.表2.2.4为运输问题的一个基可行解，工=工=工=3，x=6，工=4，x=1，213414321323其余x^=0，将运输问题作线性规划处理，在该基可行解下单纯形表的目标函数为f=86+。x+bx+bx+bx+bx+bx111112122222313133332424。〃为非基变量x^的检验数，现利用运量的变化及运输的单位费用可计算出该变量对目标函数的综合影响，进而求出检验数。。22为非基变量x22对运费的影响，其经济意义表述为当其余非基变量x〃保持不变时，x22增加一个单位时，总运费的增加量。如果仅x22变化其余非基变量与基变量保持不变，约束条件将被破坏。所以当x22增加时部分基变量一定会发生变化。在上例中，x22增加一个单位，由B2的销量约束及根据其余非基变量保持不变的，x32必减少一个单位，由A的产量约束x必增加一个单位，x必减少一个单位，x必增加3341413一个单位，x23必减少一个单位。至此，从x22出发，依次途经基变量x—x—x—x—x—x，又回到x（也可选择沿相反的方向）。这就得到22323414132322以x22为顶点，其余顶点为基变量的闭回路。运费增加的数目为。=9-4+5-10+3-2=1，这就是求检验数的闭回路法。22用闭回路法求检验数时，对于给定的调运方案（基可行解）从非基变量x〃出发作一条闭回路，要求该闭回路上其余的顶点均为基变量，并从x^开始将该闭回路上的顶点顺序编号（顺时针或逆时针均可），起点为零，余类推。称编号为奇数的点为奇点，编号为偶数的点为偶点，则x^处对应的检验数。〃等于该闭回路上偶点处运价的总和与奇点处运价的总和之差，即'二偶点处运价的总和一奇点处运价的总和（2.2.2）下面求x的检验数，以x为顶点的闭回路为x—x—x—x（也可选顺时针242424141323方向），检验数为。24=8-10+3-2=-1（或。24=8-2+3-10=-1）这就是求检验数的闭回路法，其原理就是通过寻找闭回路来计算非基变量的检验数。

按上述作法，可计算出表2.2.4中的所有非基变量的检验数，把它们填入相应位置的方括号内，如表2.2.5所示。表2.2.5产:yBBB3B4产量ai气3[1]11[2]3107A2139[1]28[-1]4A37[10]410[12]59销量气365620显然，当所有非基变量的检验数均大于或等于零时，现行的调运方案就是最优方案，因为此时对现行方案作任何调整都将导致总的运输费用增加。闭回路法的主要缺点是当变量个数较多时，寻找闭回路以及计算两方面都会产生困难。2.位势法当运输向量的产地与销地很多时，空格的数目很大，用闭回路法计算检验数，要找很多的闭回路，计算量很大，而用位势法(也称对偶变量法)就要简便得多.对产销平衡运输问题，约束方程的系数矩阵的秩为m+n-1，模型为minf=SnCxi=1j=1ijij乙x=ai=1(i=1,2,—m)(2.2.3)s.t.▽Zx=bijjj=1(j=1,2,…n)x>0(i=1,2,…m;n=1,2,…n)设"],u2,-um分别表示前m个约束等式相应的对偶变量，用V,七,…v分别表示后n个等式约束相应的对偶变量，即有对偶变量向量，"],u尸…气件运输问题的对偶规划写成WmaxZ=^u+，viijji=1j=1(2.2.4)u+v<c(i=1,2,•••m;j=1,2,•••n)ijij".，V为任意实数(2.2.4)由互补松弛定量可知，若X**,V*｝分别为原问题和对偶问题的可行解ij1j(i=1,2,…m;j=1,2,…n)，它们同为最优解的充要条件是对一切i与j，有X*(u*+v*-C)=0(2.2.5)ijijij

对于原问题的任意基可行解X*LX*为非基变量时，式（3.2.5）显然成立，当x*为ijijij基变量时可令X*据是原问题的ij然后代入（2.2.4）u*+v*-C.=0（2.2.6）X*据是原问题的ij然后代入（2.2.4）U*与v*同时满足（2.2.6）与（2矿4），常常是不现实的，这恰说明最优解。实际中对于给定的基可行解X*庆通过（2.2.6）求出u*与v*，ijij检验u*+v*-C.V0是否对（i=1,2,…m;j=1,2,…n）成立。原问题的任意基可行解所对应的（2.2.6）给出了m+n个变量的m+n-1个方程，其系数矩阵为原问题的系数矩阵^中基变量所对应的列向量的转置，该方程组的系数矩阵与增广矩阵的秩相等，都是m+n-1，从而该方程组永远有解。这样求得伽*与v*分别对应、一-一,、一x*一.一调运方案的弟1行的行位势”与弟j列的列位势”，而u*+v*为变量万的位势。可以通ij过求位势求得非基变量的检验数。仍将例2.2.1中b的计算过程进行分析，按闭回路法得七=C22-CLC34Y14+C1广C23由于闭回路上其余变量都为基变量b=C一(u+v)+(u+v)一(u+v)+(u+v)一(u+v)=C-u-v222232341413232222所以，一般的结论是(2.2.7)b..=C—u—v式中C为x对应的运价，u,v分别为x对应的行位势和列位势，这样可用位势法求出检ijijijij验数。(2.2.7)位势法的步骤：（1）求出的运输问题的基可行解，设其基变量是：%j，七2,/•••，七,人（s=m+n-1）（2）解方程组：u+v=cTOC\o"1-5"\h\zij1ij1u+v=ci2j2i2j2(2.2.8)u+v=cijij(2.2.8)求出一个特解（解不唯一）（3）求检验数：b=C-u-v.§2.2出基变量的选择（方案的调整）'当非基变量的检验数出现负值时，则表明当前的基本可行解不是最优解。在这种情况下，应该对基本可行解进行调整，即找到一个新的基本可行解使目标函数值下降，这一过程通常称为换基（或主元变换）过程。在运输问题的表上作业法中，换基的过程是如下进行：（1）选负检验数中最小者o诙，那么乂诙为主元，作为进基变量（表2.2.5中的x24）；（2）以乂化为起点找一条闭回路，除；汶外其余顶点必须为基变量格；（3）对闭回路的每一个顶点标号，x「为0,沿一个方向（顺时针或逆时针）依次给各顶点标号；'（4）求0=min{xIx对应闭回路上的奇数标号格}=x那么确定^（当有若干可ijpqpq个时只选一个）为出基变量，0为调整量；（5）对闭回路的各偶标号顶点调整后的结果为：x^+0，对各奇标号顶点调整后的结果为：x「-0，特别x-0=0，x变为非基变量。重复（2）、（3）步，直到所有检验数均司非负，得到最优解。在例2.2.1中以x24为顶点的闭回路为xTxTxTx，0=min（x,x}=1241413231423x23出基并对闭回路的运量调整，调整后为x24=1,气4=2,x13=3,x23=0，其余变量不变。调整后求检验数（位势法）。表2.2.6v■-24-25uBBB3B4产量a53[0]11[2]31073气139[2]2[1]840A37[9]410[12]59销量bj365620bN0，得到最优解x=5,x=2,x=3,x=1,x=6,x=3,ij131421243234其余x^=0;最优值：f*=3X5+10X2+1X3+8X1+4X6+5X3=85第三节不平衡的运输问题§3.1产销不平衡运输问题前面讲述的解运输问题的算法，是以总产量等于总销量（产销平衡）为前提的.实际上，在很多运输问题中总产量不等于总销量.这时，为了使用前面的表上作业法求解，就需将产销不平衡运输问题化为产销平衡运输向量.如果总产量大于总销量乙＞为Iji=1j=1这时的数学模型是（以下取a=s,b=d）minz空乙..x..i=0j=0

s.t.2X1j=1<aii=1,2,…，m.(2.3.1)栏X=bj=1,2,…s.t.2X1j=1<aii=1,2,…，m.(2.3.1)栏X=bj=1,2,…,n..ji=1X.,>0为借助于产销平衡时的表上作业法，可增加一个假想的销地B，由于实际上它不存n+1在，因而由产地气（.=1,2,…,m）调运到这个假想销地的物品数量X.（n+1）（相当于松驰变量），实际上是就地存贮在A的物品数量，就地存贮的物品不经运输，故其单位运价C('=1,2,…,m).i,(n+1)=0令假想销地的销量为b(n+1)则模型（2.3.1）变为=£a—£bjj=1aii=12x=ai=1,2,…,m.s.tj=1lJ1（2.3.2）*x=bj=1,2,,n+1.i=1x..>0例2.3.1某公司从两个产地A、A将物品运往三个销地B、B、B，各产地的产量、12123各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？表2.3.1地'、、、B]B2B3产量A1646300A655300销量150150200解：增加一个虚设的销地运输费用为0,得表2.3.2

表2.3.2地'、B]B2B3B4(虚销产量A16460300A26550300销量150150200100总产量小于总销量的情形二v以

Iji=1j=1这时的数学模型是（以下取a=s,b=d）minzU乙.x.i=0j=0命=a（i=1,2,...,m）j=1（2.3.3）s.t并x..<b(j=1,2,…,n)i=1x>0ij（2.3.3）可仿照上述类似方法处理，即增加一个假想的产地A，它的产量等于m+1am+1（2.3.4）j=1iam+1由于这个假想的产地并不存在，求出的由它发往各个销地的物品数量x(m+1)jC(m+1)=0(j=1,2,…n)但当这种短缺有其他成本(违约赔偿或机会成本)，cm+1)•不为零为其成本。(j=1,2,…n)，实际上是各销地知所需物品的欠缺额，所以一般地有例C(m+1)=0(j=1,2,…n)但当这种短缺有其他成本(违约赔偿或机会成本)，cm+1)•不为零为其成本。表2.3.3地\B]BB3产量A646200

A655300销量250200200增加虚拟销地后得到表2.3.4地、'、'B2B3产量A】646200A655300a3（虚产地）000150销量250200200§3.2运输问题的应用例2.3.3石家庄北方研究院有一、二、三，三个区。每年分别需要用煤3000、1000、2000T，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000T，运价如下表。由于需大于供，经院研究决定一区供应量可减少0—300T，二区必须满足需求量，三区供应量不少于1700T，试求总费用为最低的调运方案。表2.3.5地、'\一区二区三区产量山西孟县1.651.71.754000河北临城1.601.651.701500需要量300010002000解:根据题意，作出产销平衡问题的运价表：取M代表一个很大的正数，其作用是强迫相应的X31，%3,*34取值为0。表2.3.6地\表2.3.6地\一区一区二区三区三区产量山西孟县1.651.651.71.751.754000河北临城1.601.601.651.701.701500假想生产点M0MM0500需要量270030010001700300例2.3.3设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相同，有关数据如下表。试求总费用为最低的化肥调拨方案。表2.3.7地、\1234产量A1613221750B1413191560C19202350最低需求量3070010最高需求量507030不限解：根据题意，作出产销平衡问题及运价表:最低要求必须满足，因此把相应的虚设产地运费取为M，而最高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为0。对应4”的销量50是考虑问题本身适当取的数据，根据产销平衡要求确定D的产量为50。表2.3.8\销产、地地\1'1''234'4''产量A16161322171750B14141319151560C19192023MM50DM0M0M050最高需求量302070301050下面是生产与储存问题例2.3.4某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况

下，使该厂全年生产总费