四章运输问题

1、第四章运输问题I、基本要求教学目标了解运输问题的基本原理，掌握运输问题表上作业法的计算方法。 能够进行 产销平衡与产销不平衡的运输问题的优化安排。重点问题运输问题表上作业法的计算方法。II、基本内容第一节运输问题的基本原理和表上作业法一、运输问题的基本原理二、运输问题表上作业法第二节运输问题优化实例一、产销平衡的运输问题二、产销不平衡的运输问题III 学时分配表序号教学内容课时分配1运输问题的基本原理和表上作业法22运输问题优化实例2合计4IV、教学方法本章主要采取讲授课外练习相结合的方法教学。第一节运输问题的概念和模型一、运输问题的概念一般运输问题，就是为解决把某种产品从若干个产地调运到若干

2、个销地， 在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的情 况下，确定使总运输费用最小的方案的数学问题。二、运输问题数学模型例4.1某公司从两个产地Al、A将物品运往三个销地Bi、B2、B3,各产地 的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示， 问：应 如何调运可使总运输费用最小？表4.1商品产销调运表BiB2B3产量Ai646200A655300销量150150200解：两个产地的总产量为：200+300=500 三个销地的总销量为150+150+200=500 总产量=总销量，故称产销平衡问题。设Xj为从产地A运往销地B的运输量，得到下列运输量表:

3、表4.2商品运量表BiB2B3产量AixiiX12X13200AX21X22X23300销量150150200500根据题意可写出如下数学模型:s.t.X11+ X12 + X13 = 200x21 + X22+ x23 = 300X11 + X21 = 150X12 + X22 = 150X13 + X23 = 200（满足产地产量约束条件 （满足产地产量约束条件 （满足销地销量约束条件 （满足销地销量约束条件 （满足销地销量约束条件) ) ) ) )Min f = 6x11+4x12+6x13+6x21+5x22+5x23XjA0(i=1,2; j=1,2,3)。若设A1, A2,Am表示

4、某物资的m个产地；B1,B2,Bn表示某物资的n个销地；Si表示产地Ai的产量；dj表示销地Bj的销量；q表示把物资从产地 Ai运往销地Bj的单位运价则可得如下运价表（表4-3)。则称该运输问题为产销平衡问题，其一般线性规划模型如下：设Xij为从产地Ai运往销地Bj的运输量，根据这个运输问题的要求，可 以建立一般运输变量表（表 4.4）。m nMin f八 ' 胪耳i d j =1s.t ' Xj _Si(i =1,2,m)j 4m、'Xij mdi(j =1,2;,n)i 4Xij _0（i =1,2- ,m; j =1,2,n）第二节运输问题的表上作业法一、确定基本

5、初始可行解例：某食品公司下属的 A、A、A 3个厂生产方便食品，要运送到B、B2、Ba、B 4个销售点，数据如下：表4.5某食品公司商品供销调运资料表BB2B3产量aiA311310 :7A19284A374105 :9销量bj365620求最优运输方案。解：确定初始可行解主要有西北解法、最小元素法和伏格尔（Vogl ）近似法等方法。下面，我们根据教材的介绍，简述西北解法和最小元素法。（一）西北角法从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。然 后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，贝肿把该行 （列）的其他格划去。如此进行下去，直至得到一个基本可行解。如

6、上例：在变量格的左上角填入运输费用，右下角准备填入基变量值，划 去的格用括号“ ”标注（准备将来填写检验数）。其求解过程如下表所示:表4.6西北角法求初始基本可行解肖地 产地、BB3产量A1331143100A1922280A7410356(9) 0销量ooo020（产销平衡）第一步:首先，从表的西北角（左上角）开始，给该单元格的变量Xn尽可能大的数值。因为冷表示从产地A运往销地B的产品的数量，已知A1产量是7,B1的需求量是3,可以满足Bi的全部需求，所以令 心=min73 =3其次，修改第1行的“产量”数据和第1列的“销量”数据：因为产地 A 运往销地Bi3个单位，因此应从当前产量中减去

7、3,将其改写为4（7-3=4）;销地 Bi从产地A运来了 3个单位，因此应从当前的需求量中减去 3,将其改写为0， 即该地需求量已饱和。第三,由于销地B需求量已满足,不需再供应,因此,Bi列的剩余变量x21和x31 应取值0,即这两个单元格不再赋值，在其右下角加注“ ”，表示该两格已被划 去。第二步：从第二个左上角xi2开始。首先，由于第1行的产量（供应量）还剩4个单 位，销地B的需求量是6个单位，故应令x12 = min4,® =4其次，修改第1行的“产量”数据和第2列的“销量”数据：第 1行产地 A1当前的产量是4,再供应销地R4个单位以后没有剩余了，故应修改为 0;销 地B2原

8、需求量是6个单位，从A调来4个单位后，尚需2个单位，故应修改为2。第三，由于第1行产地A的产量已供应完毕，第1行剩余的两个变量X13和X14 应取值0,即这两个单元格不再斌值，对其右下角加注“ ”，表示该两格已被划 去。第三步：从第三个左上角X22开始。首先，由于第2行的产量（供应量）是4个单位,销地B2的当前需求量是2个单位，故应令x22二min4,2 =2其次，修改第2行的“产量（供应量）”数据和第2列的“销量（需求量）” 数据：第2行产地A的产量是4,供应销地B2个单位以后还剩余2个单位，故 应修改为2;销地 B当前需求量是2个单位，从 A调来2个单位后，需求量已 满足，故应修改为0。第

9、三，由于销地B2需求量已满足,不需再供应,因此,B2列的剩余变量x32应取值0,即这个单元格不再赋值，对其右下角加注“ ”，表示该单元格已被划去。 第四步：从第四个左上角X23开始。首先，由于第2行的当前产量（供应量）是2个 单位，销地B3的需求量是5个单位，故应令x23二min5,2 =2其次，修改第2行的“产量（供应量）”数据和第3列的“销量（需求量）” 数据：第2行产地A的当前产量是2 ,再供应销地Bs2个单位以后无剩余，故 应修改为0;销地B3当前需求量是5个单位，从 A2调来2个单位后，尚需3个 单位，故应修改为3。第三，由于第2行产地A的产量（供应量）已供应完毕，第2行剩余的-个

10、变量X24应取值0,即这个单元格不再赋值,对其右下角加注“ ”，表示该单元 格已被划去。第五步：从第五个左上角X33开始。首先，由于第3行的产量（供应量）是9个单位,销地B3的当前需求量是3个单位，故应令x33=min9,3=3其次，修改第3行的“产量（供应量）”数据和第3列的“销量（需求量）” 数据：第3行产地A的产量是9,供应销地B33个单位以后剩余6个单位，故应 修改为6;销地B3当前需求量是3个单位，从A3调来3个单位后，需求已饱和， 故应修改为0。第六步：从第六个左上角X34开始。首先，由于第3行产地 A3的产量（供应量）还剩6个单位，销地B4的需求量是6个单位，故应令x34二min

11、6,6 =6其次，修改第3行的“产量（供应量）”数据和第4列的“销量（需求量）” 数据：第3行产地A的当前产量是6 ,再供应销地B36个单位以后无剩余，故 应修改为0;销地B4需求量是6个单位，从 A3调来6个单位后，需求已饱和， 故应修改为0。由于这时表中已没有未被划掉的元素了，故求解已经完成。填入的数据为6个，等于行数加列数减1,即3+4-仁6。该问题的一个基本可行解为：X11=3， X12 二 4，x22= 2，x23= 2，X33- 3，X34二 6，其余的兀素Xjj= 0。表4.7最小元素法求初始基本可行解销地产地、BB3产量Ai311310043A192 18（1） 031A741

12、05(9) 063销量000020（产销平衡）（二）最小元素法最小元素法的所谓元素，是指单位运输价格。最小元素法的基本思路是：运输价格最便宜的优先调运。即从运输问题数据表（或单位运输价格表）中寻找最小数值，并以这个数值所对应的变量 Xj作为第一个基变量，在该变量格内的右下角填入允许取得的最大数。然后一直按此方法继续下去，若某行（列）的产量（销量）已满足，则该行（列）的其他变量 Xj只能取0值或说“把该行（列）的其他格划去，直到取得一个基本可行解为止。下面，我们仍以前例资料说明 最小元素法的求解过程。解：把变量格的左上角填入运输价格，右下角准备填写基变量的值，划去的 格用中括号“ ”来标注（准备

13、将来填写检验数）。第一步：首先，从运价最小（C2i=1）的变量x21开始分配运输量，并使x21取尽可能大 的数值。因为x21表示从产地A往销地Bi运送产品的数量，已知Bi的需求量是3 个单位，而A的产量是4个单位，可以满足B的全部需求，所以令X21 =mi n（4,3） =3。其次，修改第2行的“产量（供应量）”数据和第1列的“销量（需求量）” 数据：因为产地A的产量是4个单位，供应B3个单位后尚剩余1个单位，故应 将4修改为1;销地B1的需求量是3个单位，已从产地A得到满足，不再需要供 应，因此应将3修改为0。第三，由于销地B1的需求量已得到满足，第1列的其余两个变量x,1和X31均应取0值

14、，分别加注 第二步：首先，给运价最小（C23=2）的变量X23分配运输量，并使X23取尽可能大的数 值。因为3表示从产地A往销地E3运送产品的数量，已知B3的需求量是5个单 位，而A的当前产量只有1个单位，所以令x23 =min（1,3）=1其次，修改第2行的“产量（供应量）”数据和第3列的“销量（需求量）” 数据：因为产地 A的当前产量是1个单位，供应 E3后已无剩余，故应将1修改 为0;销地B3的需求量是5个单位，已从产地 A得到1个单位，因此应将5修 改为4。第三，由于产地A的产量已分配完毕，第2行尚未分配的两个变量X22和X24 均应取0值，分别加注“ ”表示划去。第三步：首先，给运价

15、最小（Ga=3）的变量X13分配运输量，并使X13取尽可能大的数 值。因为X13表示从产地A往销地B3运送产品的数量，已知B3当前的需求量是4 个单位，而A的产量是7个单位，所以令x13二min（7,4）=4其次，修改第1行的“产量（供应量）”数据和第3列的“销量（需求量）” 数据：因为产地A的产量是7个单位，供应B4个单位后剩余3,故应将7修改 为3;销地B3的当前需求量4个单位，已从产地A得到满足，因此应将4修改为 0。第三，由于销地R的需求量已得到满足，不再需要分配，所以第 3列尚未分配的变量X33应取0值，加注“ ”表示划去。第四步:首先，给运价最小（G2=4）的变量x32分配运输量，

16、并使x32取尽可能大的数 值。因为x32表示从产地A往销地R运送产品的数量，已知 R的需求量是6个单位，A的产量是9个单位，所以令x32=min（9,6） = 6其次，修改第3行的“产量（供应量）”数据和第2列的“销量（需求量）” 数据：因为产地A的产量是9个单位，供应R6个单位后剩余3个单位，故应将 9修改为3;销地B2的需求量是6个单位，从产地A得到6个单位后已满足，因 此应将6修改为0。第三，由于销地E 2的需求量已得到满足，所以第2列尚未确定分配的变量X12应取0值，加注“ ”表示划去。第五步：首先，给运价最小（G4=5）的变量X34分配运输量，并使X34取尽可能大的数 值。因为X34

17、表示从产地A往销地B运送产品的数量，已知 b的当前需求量是6个单位，A的当前产量是3个单位，所以令x34二min（3,6） = 3。其次，修改第3行的“产量（供应量）”数据和第4列的“销量（需求量）” 数据：因为产地Ab的当前产量是3个单位，供应 B2 3个单位后已无剩余，故应 将3修改为0;销地B4的需求量是6个单位，从产地A得到3个单位后还需要3 个单位，因此应将6修改为3。第六步：首先，给运价最小（C4=10）的变量X14分配运输量，并使X14取尽可能大的 数值。因为x14表示从产地Ai往销地B运送产品的数量，已知B4的当前需求量是3个单位，A的当前产量是3个单位，所以令 4二min（3

18、,3） = 3。其次，修改第1行的“产量（供应量）”数据和第4列的“销量（需求量）” 数据：因为产地 Ai的当前产量是3个单位，供应 B 3个单位后已无剩余，故应 将3修改为0;销地 B的当前需求量是3个单位，从产地 A】得到3个单位后已 饱和，因此应将3修改为0。至此，基本可行解计算表中已无未被分配或划去的变量，故求解结束。这时的基本可行解为：X21 =3， X23 =1，为3 =4， X32 =6， X34 =3， X14 =3，其余的元素 Xj =0。二、基本可行解的最优性检验检查的方法与单纯形方最优性检验就是检查所得到的方案是不是最优方案法中的原理相同，即计算检验数。由于目标要求极小，

19、因此，当所有的检验数都 大于或等于零时该调运方案就是最优方案；否则就不是最优，需要进行调整。下面介绍两种求检验数的方法：闭回路法和位势法（一）闭回路法为了方便，我们以表4.7给出的初始基本可行解方案为例，考察初始方案的 任意一个非基变量，比如X24。根据初始方案，产地 A2的产品是不运往销地B4 的。如果现在改变初始方案，把 A的产品运送1个单位给B4，那么为了保持 产销平衡，就必须使X 14或X 34减少1个单位；而如果X 14减少1个单位，第 1行的运输量就必须增加1个单位，例如X13增加1个单位，那么为了保持产 销平衡，就必须使X23减少1个单位。这个过程就是寻找一个以非基变量 X24为

20、起始顶点的闭回路一 X 24，X14， X13，X23 ，这个闭回路的其他顶点均为基变量（对应着填上数字的格）。容易计 算出上述调整使总的运输费用发生的变化为 8 - 10 + 3- 2 = -1 ，即总的运费 减少1个单位，这就说明原始方案不是最优方案，可以进行调整以得到更好的可以证明，如果对闭回路的方向不加区别（即只要起点及其他所有顶点完全 相同，而不区别行进方向），那么以每一个非基量为起始顶点的闭回路就存在而 且唯一。因此，对每一个非基变量可以找到而且只能找到唯一的一个闭回路。表4.8中用多边形画出的是以非基变量 X22为起始顶点的闭回路。表4.8以非基变量X22为起始顶点的闭回路销地产

21、地B1B2B3B4产量A1311310743A21928431|A374105963销量365620（产销平衡）可以计算出以非基变量X22为起始顶点的闭回路调整使总的运输费用发生的变化为9-2 + 3- 10 + 5- 4 = 1即总的运费增加1个单位，这就说明这个调整不能改善目标值。从上面的讨论可以看出，当某个非基变量增加一个单位时，有若干个基变量 的取值受其影响。这样，利用单位产品变化（运输的单位费用）可计算出它们对目标函数的综 合影响，其作用与线性规划单纯形方法中的检验数完全相同。 故也称这个综合影 响为该非基变量对应的检验数。上面计算的两个非基变量的检验数为 二24 = -1 ， 22

22、 = 1。闭回路方法原理就是通过寻找闭回路来找到非基变量的检验数。如果规定作为起始顶点的非基变量为第 1个顶点，闭回路的其他顶点依次为 第2个顶点、第3个顶点那么就有：G =（闭回路上的奇数次顶点单位运费之和）-（闭回路上的偶数次顶点单 位运费之和），其中ij为非基变量的下角指标。按上述作法，可计算出表1的所有非基变量的检验数，把它们填入相应位置的方括号内，如图4.9所示。二 11=3-1+2-3=1,亍2=11-4+5-10=2匚22=9-4+5-10+3-2=1；24=8-10+3-2=-16=7-5+10-3+2-1=10匚 33=10-3+10-5=12表4.9初始基本可行解及检验数肖

23、地产地'B1B2B3B4产量A131112341037A21391218-14A3710461012539销量365620（产销平衡）显然，当所有非基变量的检验数均大于或等于零时， 现行的调运方案就是最优方案，因为此时对现行方案作任何调整都将导致总的运输费用增加。闭回路法的主要缺点是：当变量个数较多时，寻找闭回路以及计算两方面都 会产生困难。（二）位势法第一步，计算位势值所谓位势法，就是对运输表上的每一行赋予一个数字Ui ,对每一列赋予一个数字Vj ,使它们的和等于其所对应单元格的运输价格,即：Ui+Vj=Cj （i=1,2,m;j=1,2,n）这些Ui和Vj分别称为第i行和第j列的位

24、势，它们的数值是相互关联的，填 写时可任意给定其中的一个数值。下面，我们仍用前例计算位势值。第一步，作位势计算表。仿照前面已计算制作的调运方案表作一新表，将表 中调运量数值换成相应的运输价格数值（见下表）：表4.10运输问题表上作业位势计算表销地 产地、B1B2B3B4UiA13105A2124A3450Vj-34-25第二步，计算位势值。假设从基变量Xu开始，给定U1=5，则应有:U1+V4=C14=10，所以 V4=C14-u 1=10-5=5;U1+V3=C13=3， 所以 V3=C13-u 1=3-5=-2 ;U3+V4=C34=5， 所以 U3=C34-V4=5-5=0 ；U2+V3

25、=C23=2，以 U2=C23-V 3=2-（-2）=4 ；U2+V1=C21=1， 所以 V1=C21-U2=1-4=-3 ;U3+V2=C32=4， 所以 V2=C32-U3=4-0=4 ；第二步，计算非基变量的检验数现在，我们来计算各空格（非基变量）的检验数。令二4代表空格（A,B4）的检验数，由闭回路计算可知：二4= C24-C 14+C13-C23=C24-（U 1+V4）+（U l+V3）-（ U 2+V3）= C 24- U 2-V 4 ；同理：C31 = C31-C 34+C14-C 13+C23-C 21=C31-（U 3+V4）+ （U 计V4）-（U l+V3）+ （U

26、2+V3）-（U 2+Vl）=C 31-U 3-V 1总结以上两例可知：Cj是空格（A,Bj）所对应的单位运输价格；（Ui+Vj）恰 好就是该空格所在行的位势和所在列的位势之和，于是，我们可概括出任一空格检验数的计算公式为：Cij =Cij -U i -V j，如二24=C24- U 2-V 4，:二31= C 31- U 3-V 1 o依据上述资料，根据该计算公式可求得：11= C 11 U1 V1=3-5-（-3）=112= C 12 U1 V2=11-5-4=2C22= c 22 - U2 - V2=9-4-4=1C24= C 24 U2 V4=8-4-5=-1二31= c 31 - U

27、3 - V1=7-0-（-3）=10-33= C 33 U3 - V3=10-0-（-2）=12由于检验数还有负数，所以这个可行解不是最优解，需要找新的基本可行解， 使费用不高于当前的基本可行解。三、求新的基本可行解当非基变量的检验数出现负值时，则表明当前的基本可行解不是最优解。在这种情况下，应该对基本可行解进行调整，即找到一个新的基本可行解使目标函 数值下降，这一过程通常称为换基（或主元变换）过程。在运输问题的表上作业法 中，换基的过程是如下进行：首先,选负检验数中最小者6，那么Xrk为主元，作为进基变量（本例为X24 ） o在本例中只有一个负检验数二24=-1其次,以Xrk为起点找一条闭回

28、路，除Xrk外其余顶点必须为基变量格（如本 例以X24为起点的闭回路）。这里所谓闭回路，是指从一个非基变量所在格出发， 沿水平或垂直方向前进，遇到代表基变量的填入数字的格才向左或向右90°继续前进，直到回到出发的那个格。如本例从X24出发，垂直向上，遇X14向左900继续前进，遇X13后再转弯900 垂直向下前进，遇X23后再向右900转弯，最后回到变量X24所在格（见下表）：表4.11初始调运方案调整表产地、B1B2B3B4产量A14(+1)3(-1)7A231(-1)(+1)4A3639销量365620（产销平衡）第三，为闭回路的每一个顶点编序号，Xrk为1，沿一个方向（顺时针或

29、逆时针）依次给各顶点标号。如本例X24为1，X14为2，X13为3，X23为4。第四，取闭回路偶数顶端调运量的最小值作入基变量值本例为：X24=min（3,1）=1第五，为保持产销平衡，把所有闭回路上偶数顶端的调运量都减去一个入基变量值，所有闭回路上奇数顶端的调运量都加上一个入基变量值（见上表），这样便得到调整后的方案。调整后的方案如下表所示：表4.12调整后的调运方案表产地B1B2B3B4产量A1527A2314A3639销量3656通过调整得到的最优方案是：Ai产地运5吨到销地B3,运2吨给销地B4；A2产地运3吨到销地B1,运1吨给销地B;A3产地运6吨到销地B2,运3吨给销地B; 这时

30、总运费最低，其运费为85百元，即：最优方案运费=5X 3+2X 10+3X 1+1 X 8+6X 4+3X 5=85。本例只有一个负检验数，故求解至此就结束，如果有若干负检验数，则需 重复以上步骤，直到所有检验数均非负，得到最优解。四、产销不平衡问题的处理 在实际中遇到的运输问题常常不是产销平衡的，而是下列的一般运输问题模型：m nMin f _ qXjji j dns.t 送 Xij 兰 s(i =1,2,m)j m m' Xij <dj(j =1,2,n)i AXij -0(i =1,2,m; j =1,2,n)我们已经介绍过，可以通过增加虚设产地或销地（加、减松弛变量）把问

31、题 转换成产销平衡问题，下面分别来讨论。（一）产量大于销量的情况mn考虑7 s八dj的运输问题，得到的数学模型为i ±j 3Minm nf _ Cj Xjjij Ts.t 瓦 Xij 兰 s(i =1,2,m)j 4mXj 乞 dj(j =1,2厂，n)i 4Xj _0(i =1,2, ,m; j =1,2厂,n)只要在模型中的产量限制约束(前m个不等式约束)中引入m个松驰变量Xi (i=1,2，,m)即可，变为：nZ Xj +Xg = s(i =1,2,m)j 4然后，虚设一个销地Bn 1，它的销量为：mnbn 1 S 二 dji =1j =1这里松驰变量Xn卅可以视为从产地A运往

32、销地Bn卅的运输量，由于实际并不运输，它们的运输费用Cin .1 =0(i=1,2,m),于是这个运输问题就转化成了一个产 销平衡的问题。例4.5 某公司从两个产地 A、A将物品运往三个销地 B、B2、B3,各产地 的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？表4.16运输费用表产地B1B2B3产量A13151278Ar 11292245销量533625(产销不平衡)解：这里，总产量78+45=123,总销量为53+36+25=114产销不平衡，因此,应该虚设一个销地，于是得到虚设销地的产销平衡运输费用表4.17。1. 用最小元素法求初始基

33、本可行解将运输费用表中的运输价格放在各相应单元格的左上角，右下角准备填写 基变量值，划去的单元格用“ ”表示。表4.17运输费用表产地B1B2B3吕产量A131512078Ar 11:2922 :045销量5336259123(产销平衡)表4.18最小元素法初始基本可行解地产地7BB2B3B4产量A1315120(78)(53)(45)836259(9)0A114529220(45)0销量(53)(8)0(36)0(25)0(9)0123（产销平衡）第一步,令x21 = min45,53 = 45 ,将销地B的销量53改为8 ,将产地A的产量45改为0;由于产地A的产量已分配完，故划去第2行剩

34、余单元格（即划去X22、x23、X24 ）（以注“ ”表示划去）第2步，令x,3二min78,2$ =25,将销地B3的销量25改为0,将产地Ai的产 量78改为53;第3步，令冷=min53,8 =8,将销地Bi的销量8改为0,将产地A的产量53 改为45。第4步，令x,2 =min45,36 =36,将销地B2的销量36改为0,将产地Ai的产 量45改为9。第5步，令&二min9,9二9，将销地印的销量9改为0,将产地A的产量9 改为0。2. 用闭回路法检验基本可行解是否最优解非基变量X22的闭回路为：X22-； X21-；心一；x12 ，其检验数22 =29-11+13-15=1

35、6;非基变量X23的闭回路为：他一X1L X21 ，其检验数-23 =22-12+13-11=12。非基变量x24的闭回路为：x24； x14-；冷；x21，其检验数二24 =0-0+13-11=2。由于检验数无负数，所以，此基本可行解就是最优解。其解为：冷=8， X|2 = 36， x13 = 25， x14 = 9 （虚设），x21 = 45。即从产地A调8个单位到销地B，调36个单位到销地B2,调25个单位到 销地Ba,调9个单位到销地B,（实际上等于库存9个单位）；从产地A2调45个单 位到销地B。这时运费最少，其运输费用是：运输费用=8X 13+36X 15+25X 12+45X 1

36、1=1439课堂练习：已知A、A、A三个产地的产量依次是 3500、3250和3750,要 供应的B、B2> R、B4四个销地的需求量依次是 1500、2000、2500和3500,并 知各产地运往各销地单位产品的运输价格如下表所示，试确定调运费用最少的运输方案。运输价格表销地 产地'BBB3B4产量A151822263500A212516233250A14P 192024 n3750销量1500200025003500（产销不平衡）解：1.虚设销地R将此问题转化成产销平衡问题。 列产销平衡运输问题求解表如下：2.求初始基本可行解第一步，令x31=min375Q150CJ =15

37、00;将产地 A的产量改为2250,销地B1的销量改为0 ;由于销地的销量已满足，第1列其它单元格应划去（注“口”。第二步，令x23二min3250,250C =2500;将产地A的产量改为750,销地B3的销量改为0 ;由于销地B3的销量已满足，第3列其它单元格应划去（注“口”。第三步，令x12 =min3500,200C =2000;将产地A的产量改为1500,最小元素法初始基本可行解B1B2RBB5产量A151822260(3500)(1500)-1 1200035001000(1000)0A212516230(3250)(750)0811025007501A141920240(3750

38、) (2250)150033225010销(1500)(2000)(2500)(3500)(1000)10500量000(2750)(500)00销地B2的销量改为0 ;由于销地B2的销量已满足，第2列其它单元格应划去（注第四步，令x24二min750,350Q =750;将产地A的产量改为0,销地B4的销 量改为2750;由于产地A的产量已分配完，划去第2行尚未分配的单元格（X25）， 表示不再分配。第五步，令x34二min 2250,275（ =2250;将产地A3的产量改为0,销地B4 的销量改为500;由于产地A的产量已分配完，划去第 3行尚未分配的单元格(X35)，表示不再分配。第六

39、步，令Xgmin1500,50CJ =500;将产地A的产量改为1000,销地B 的销量改为0。第七步，令x15二min1000,100C =1000;将产地 A的产量改为0 ,销地B5 的销量改为0。得初始基本可行解为：x12 = 2000, x14 = 500 , x15 =1000 (虚设)，x23 = 2500 , x24 = 750 , x31 =1500X34 = 2250。3. 用闭回路法对初始基本可行解进行检验以非基变量x11为起点的闭回路为心一；x14-； x34-； x31 ,检验数；11 =15 -26 24 -14 - -1 ;以非基变量x21为起点的闭回路为X21 r

40、 X24 X34 x31 ,检验数；21 =21 -23 24 -14 = 8;以非基变量x22为起点的闭回路为x22>x12>x14>x24,检验数二 22 =25-18 26 -23 = 10 ;以非基变量X32为起点的闭回路为X32 -； X34 -； X|4 -； X12 ,检验数；二2 =19 _24 26 _18=3;以非基变量X13为起点的闭回路为X13r X14r X24r X23 ,检验数；13 =22 _26 23_16 =3;以非基变量X33为起点的闭回路为X33 “ X23X24 " X34 ,检验数33 =20-16 23 -24 =3。以

41、非基变量X25为起点的闭回路为X25 “ X15 X14 X24 ,检验数；25 =0_0 26 _23 = 3。以非基变量X35为起点的闭回路为X35>X15>X14>X34,检验数25 =0-0 * 26 - 24 二 2 o将检验数填入相应的非基变量单元格的中括弧中。由于检验数1 =-1说明此基本可行解不是最优解，还需要进行调。4. 通过调整求最优解以闭回路Xu > X4 > X34 > x“的偶数顶点上调运量的最小数为调整量，即以min 500,1500 =500为调整量。在此闭回路的奇数顶点上都加一个调整量，偶数 顶点上都减去一个调整量。销地 产地

42、B1B3B5产量A+5002000500-50010003500A25007503250A1500-5002250+5003750销量1500200025003500100010500调整后的调运方案如下:产地 销地、B1B2B4产量A1500200010003500A25007503250A100027503750销量1500200025003500100010500由于只有一个检验数为负数且已调整了其相应的调运量，故此方案已为最优 解，其解为：x11 =500，x12 = 2000, , & 二 1000 （虚设），x23 二 2500 , x24 = 750 , x31 = 10

43、00，X34 = 2750 o即从产地A1调往销地B500个单位、B2 2000个单位、B51000个单位（虚设）; 从产地 A调往销地B3 2500个单位、B4750个单位；从产地 As调往销地Bi 1000 个单位、B2750个单位。这样既可满足销售需要，又可使运输费用最少。这时运 输费用是：运 输费用=500 X 15+2000 X 18+2500 X 16+750 X 23+1000 X 14+2750 X 24=180750（二）销量大于产量的情况mn考虑7 S八dj的运输问题，得到的数学模型为i ±j ziMinm nf HCj Xiji d j=1ns.tXij =s(

44、i =1,2, ,m)j 4 mXj 乞 dj(j =1,2厂，n)i 4Xj _0(i =1,2, ,m; j =1,2厂,n)只要在模型中的销量限制约束(后 n个不等式约束)中引入n个松驰变量Xm ij (j=1,2，,n )即可，变为:mv XijXm .ij =dj( j =1,2,n)i =1然后，虚设一个产地Am 1 ,它的销量为:nmam d dj -.二.Sj£i A这里松驰变量Xm1j可以视为从产地Am1运往销地Bj的运输量，由于实际并不运送，它们的运费Cm .ij =0 (j=1,2，,n ).于是这个运输问题就转化成了一个产 销平衡的问题。例4.6某公司从Ai、

45、A将物品运往三个销地B、B2、B3，各产地的产量、各 销地的销量和各产地运往销地每件物品的运费如表 4.19所示，冋应如何调运可 使总运输费用最小？表4.19运输费用表产地7BB2B3产量A13151278A211292245销量533665(产销不平衡)解：1.虚设产地构建产销平衡运输费用表这里总产量是78+45=123,总销量为53+36+65=154,产销不平衡，因此应该增加一个虚设的产地，得到表4.20所示的产销平衡的运输费用表表4.20虚设产地后的运输费用及调运量分配表销地产地B1B2B3产量A131512(78)(13 )(5) 08565A2114529162212(45)0A0

46、203103(31)0销量(53)(8)0(36)(31)(65)0154 （产销平衡）2.求基本初始可行解第一步,令Xr =min 45,5可=45,将产地A?的产量45改为0,将销地B的销 量53改为8,由于产地A的产量已分配完,划去第2行尚未分配的单元格（注“ ”）；第二步，令$ =min 78,65 =65，将产地A的产量78改为13,将销地比的销量65改为0,由于销地B3的销量已满足，划去第3列尚未分配（或划去）的单元格（注“ ”）；第三步，令Xu =min13,8 =8,将产地A的产量13改为5,将销地的销量8 改为0,由于销地B的销量已满足，划去第1列尚未分配（或划去）的单元格（

47、注“ ”）；第四步，令X12=min5,36=5,将产地A的产量5改为0,将销地B?的销量36改为31;第五步，令心二min31,31 =31,将产地A的产量31改为0,将销地B?的销量31改为0。3.用闭回路法对初始基本可行解进行检验以非基变量X31为起点的闭回路为X31 X11 - X12 X32 ,检验数 嘉=0-13 15-0 =2 ;以非基变量X22为起点的闭回路为X22 “ X12rX21 ,检验数二 22 =29-15 13-11 =16 ;以非基变量X23为起点的闭回路为X23r X13r X“r X21 ,检验数二 23 =22 -12 13 -11 =12 ;以非基变量X3

48、3为起点的闭回路为X33X32 ,检验数-33 =0 -12 15-0 =3。将各检验数填入调运量分配表中相应的非基变量单元格的中括号（“口”中。由于所有检验数已无负数，所以，此基本可行解已是最优解。最优调运方 案如下表所示：表4.21最优调运方案表销地产地BB2B3产量A856578A4545A31销量5336 （其中虚设31,实 际调运量5）65即由A产地向销地Bi调运8个单位、B2调运5个单位、B3调运65个单位； 由A2产地向销地Bi调运45个单位；由虚设的 A产地向销地B2调运31个单位， 即从运输费用最少的角度考虑，产量缺口应安排在销地 B2。这时，运输总费用 是：运输费用=8X

49、13+5X 15+12X 65+45X 1仁 1454第三节运输问题的应用例4.7 有A1、A2、A3三个生产某种物资的基地，五个地区 B1、B2、B3 B4、B5对这种物资有需求。现将该种物资从三个产地运往五个需求地区，各产 地的产量和各需求地区的需要量及运输价格如下表所示。其中B2地区的115单位必须满足。问应如何调运可使总运输费用最小？表4.22运输价格及运量表需求地生产地B1B2B3B4B5产地aiA1101520204050A22040153030100A330r 35405525130需求量bj25115603070（产销不平衡）解：由于产量小于需求量，因此需要虚设一个产地A4,它

50、的产量是:（25+115+60+30+70 -（50+100+130）=20,但虚设产量由于不能真正运输，故其 运输费用为0。又因为B2的115单位必须满足，所以不能有物资从A4运往B2地区，于是 取相应的运输价格为M（M是一个充分大的正数），以保证在求最小费用的前提 下，该变量的值为0。于是，根据题意可建立如下产销平衡运输价格和运量表。表4.23产销平衡运输价格和运量表生产地B1B2B3B4B5产地aiA1101520204050A22040153030100A33035405525130A40M00020需求量bjP 25P 115603070300（产销平衡）解：1.求初始基本可行解表4.24基本初始可行解计算表需求地 生产地B1B2B3B4B5产地aiA11015202040(50)2525-10=1525+10=3530-535A22040153030(100)(40)+10010-10=0(10)0-15 6030A33035405525(130)(40)0090-10=80303040+10=50A40M0 0020M20-5 -100需求量bj(25)0(115)(90)0(60)0(30)0(70)(30)(20)0第一步，令心=min50,25 =25,将产地A的产量50改为25,