运输问题资料

1、运输问题运输问题及其数学模型表上作业法产销不平衡的运输问题应用举例运输问题及其数学模型一、运输问题的数学模型单一品种运输问题的典型情况：设某种物品有m个产地 Ai,A2,Am,各产地的产量分别是ai,a2,am；有N个销地 Bi,B2,Bn,各销地地销量分别为bi,b2,bn。假定从产地 Ai(i = 1,2,m)向销地Bj(j = 1,2,n)运输单位物品的运价是5，问 怎样调运这些物品才能使总运费最小？数据如下标所示。表1产销平衡表表2单位运价表有时可把两表合一如果运输问题的总产量等于其总销量，即有Wfli = 1f - I则称该运输问题为产销平衡运输问题；反之，称为产销不平衡运 输问题。

2、运输问题的数学模型如下：min z =产行i =1 f « imX H" = 5" J = 1，,，制i-l用 =: = 1 j 2 >1$ = iM厅0这就是运输问题的数学模型，它包含MX n个变量，(M十M)个约 束方程.其系数矩阵的结构比较松散，且特殊.二、运输问题数学模型的特点1、运输问题有有限最优解，即必有最优基本可行解2、运输问题约束条件的系数矩阵A的秩为(m+n-1)以1Ml 丽'年用-2* * *汇川 1 11下1 1 * ' 4 1 |. 行1 1 1 j1 1 1 :1 1 1 _， 行« « - 1

3、1 1该系数矩陈中对应于变量xij的系数向量pij ,其分量中除第i个和第m十j个为1以外，其余的都为零.即Pij = (0-1-1-0) =ei+em+j对产销平衡的运输问题，由于有以下关系式存在：特点：(1)约束条件系数矩阵的元素等于0或1约束条件系数矩阵的每一列有两个非零元素，对应于每一个变量在前m个约束方程中出现一次，在后n个约束方程中也出现一次。.R(A)Wm+n-1此外，对于产销平衡问题，还有以下特点所有结构约束条件都是等式约束(4)各产地产量之和等于各销地销量之和表上作业法、解题步骤 第1步：用西北角法或最小元素法确定初始基本可行解。第2步：位势法求非基变量的检验数（解的最优性检

4、验），若最优 准则（TijA0,则当前解最优，计算停止，否则转第3步。第3步：取一个检验数最小的非基变量做进基变量。第4步：用闭回路法调整当前基本可行解，转第2步1 .确定初始基本可行解（初始调运方案）以实例介绍：例 某公司生产糖果，它有三个加工厂A1,A2,A3,每月产量分别 为7t,6t,5t,6t。已知从第i个加工厂到第j个销售店的每吨糖果的运 价Cij见表，试设计在满足各销售店需求量的前提下，各加工厂 到各销售店的每月调运方案，使总的运费最小。运价表表3-3单位：丸吨加工厂% 出跖3nr-.-3JO41g2B74；ID5A西北角法B最小元素法2 .解的最优性判别（位势法，也称对偶变量法

5、）3 .用闭回路法调整当前基可行解二、表上作业法计算中的几个问题1、某个基本可行解有几个非基变量的检验数为负若运输问题的某个基可行解有几个非基变量的检验数均为 负，在继续进行迭代时，取它们中的任一变量均可使目标函数值 得到改善，但通常取。产0中最小者对应的变量为换入变量。 2、无穷多个最优解当迭代到运输问题的最优解时，如果有某非基变量的检验数 =0,则说明该运输问题有无穷多最优解。（如上例，为得到另一 个最优解，只需让 = 0的非基变量进基）3、退化问题当运输问题某部分产地的产量和与另一部分销地的销量和 相等时，在迭代过程中有可能在某个格填入一个运量时需同时划 去运输表的一行和一列，这时就出现

6、了退化。在运输问题中，退化解是时常发生的，为了使表上作业法的 迭代工作进行下去，退化解应在同时划去的一行或一列中的某个 空格中填入数字0,表示这个格中的变量是取值为 0的基变量， 使迭代过程中基可行解的分量恰好为 m+n-1个。b.在用闭回路法调整当前基本可行解时， 调整量0的取值应 为0=minXj/（ i,j ）为闭回路上所有偶数号格点。这时可能出现 有两个（或以上）偶数号格点的xij都相等且都为极小值，只能 取其中一个为离基格，其余的仍作为基格，而在作运输量调整时， 运输量与0相等的那些偶数号格点的Xij都将调整为0,因此得到 的也是一个退化了的基可行解。4、循环问题练习产销不平衡的运输

7、问题一、总产量大于总销量即mn' ai' bji =1j =1此时运输问题的数学模型为m nmin z "" cj xj1 =1 j =1n'、Xij - aii = 1,2,., mjmXj = bj j = 1,2,., ni=1xj - 0m n 1min z 、c q 为1j，n+1£ %& i = 1,2,.,mjmv Xj =bjj =1,2,.,n 1一Xij - 0、总销量大于总产量m 1 nmin z = " " CijXiji & j工/ n£ 为=aji =1,2,.,m+

8、1j苴m，乙 Xij bj j 1,2,., ni 二Xj之0例1 某市有三个造纸厂A1,A2,A3,其纸产量分别为8, 5, 9个 单位，有4个集中用户B1,B2,B3,B4,其需用量为4, 3, 5, 6个单 位，由各厂到各用户的单位运价如表所示，试确定总运费最小的 调运方案。例2较为复杂的产销不平衡问题设有三个化肥厂供应四个地区的农用化肥，假设每个地区使用各 厂的化肥效果相同，各化肥厂的年产量，各地区的需求量以及它 们之间的单位运价如表，求总运费最少的化肥调运方案。需求地区北肥厂III11IV产盘（万吨）A132117葡BH131915C2023一50酷陆需求（万吨）5070010最高需

9、求L万吨）5Q70叫不限衰 3 如运渐t万元/万吨分析：（1）这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限.根据现有产量及I, n,m地区的最低需求，第 Iv个地区 每年最多能分配到（50+60+50）-（30+70+0）=60万吨，这样四个地 区的最高需求为50+ 70+30+ 60= 210万吨，大于总产量.（2）为了求得平衡，在产销平衡表中增加一个假想的化肥厂 D,其年产量为210-160=50万吨.（3）由于各地区的需要量包含两部分， 最低需求和额外需求。 如地区I,其中30万吨是最低需求，故不能由假想化肥厂 D供 给，令相应运价为M

10、（任意大正数）.而另一部分20万吨满足或 不满足均可以，因此可以由假想化肥厂 D供给，按前面讲的， 令相应运价为0。这样，凡是需求分两种情况的地区，实际上可 按照两个地区看待.这样可以写出这个问题的产销平衡表（表3 26）和单位运价表（表327）.产销平衡表、地严嫌r严IIin1VFwA B C Dso raso蜩*3Q307030ID5D表3T8产-平皿单位运价表我377单位运批集产地VItinIVIV"AuB121?17B141413n15L5rc191920打MMDM0M00两个表也可以合在一起写。根据表上作业法计算，可以求得这个问题的最优方案如下:销鼬产地r”111111Vr

11、JVJH产更A5050B201030的C30200soD30如50销ftJO20703010加应用举例由于在变量个数相等的情况下，表上作业法的计算远比单纯 形法简单得多.所以在解决实际问题时，人们常常尽可能把某些 线性规划的问题化为运输问题的数学模型. 下面介绍几个典型的 例子.例1某厂按合同规定须于当年每个季度末分别提供10,15,25,20台同一规格的柴油机.已知该厂各季度的生产能力及生产每 台柴油机的成本如表所示.又如果生产出来的柴油机当季不交货 的，每台每积压一个季度需储存、维护等费用0.15万元.要求在完成合同的情况下，做出使该厂全年生产（包括储存、维护）费 用最小的决策.季 度生产

12、能力（台）单位成本（万元）2510 .S113311.1U3011.0IV10113解：由于每个季度生产出来的柴油机不一定当季交货， 所以设xij 为第i季度生产的用于第j季度交货的柴油机数.根据合同要求，必须满足：一I。卜n+而一15#必+物，十工势一25Xh +%.+痴 + " -20又每季度生产的用于当季和以后各季交货的柴油机数不可 能超过该季度的生产能力，故又有：工 十符？十聚k子。G 25知+知+和 35+毒药+ *“ V 3。.、W 10第i季度生产的用于j季度交货的每台柴油机的实际成本 Cij 应该是该季度单位成本加上储存、维护等费用. Cij的具体数值 见表X111“

13、1IV1曾810*95Il At)U)|HU011.1511.40IIIJ kuo11.1;IVLI JO巧，彼（万元）设用ai表示该厂第i季度的生产能力，bj表示第j季度的合 同供应量，则问题可写成：min考2 2%户HW %, 一 包11。因为当j<i时,xij=0 所以当j<i时，取Cij=M,M为一个充分大的正数。此外，由于是产量大于销量的不平衡问题，加上一个假想的需 求D,就可以把问题变成产销平衡的运输模型， 并写出产销平衡 表和单位运价表（合在一起，如下）销地卢足5KHIIV口产敢1io. aUk”.If)11*25Q25111.】。IH2511谭口Qlit-MIf11

14、-001 U5D3C-IVMM口.打0mtt ftIQ15以20就经用表上作业法求解，可得多个最优方案，表332中列出最优 方案之一.即第1季度生产25台，10台当季交货，15台II季度 交货；II季度生产5台.用于田季度交货；田季度生产 30台， 其中20台于当季交货，10台于IV季度交货IV季度生产10台， 于当季交货.按此方案生产，该厂总的生产（包括储存、维护）的 费用为773万元.餐 3-32销囱季度生产季曳J- j1uinV口产量I LI 111 IVLOft5机卜103025351010销 ftI'OL52510如例2某航运公司承担六个港口城市 A、B、C、D、E、F的四

15、条固定航线的物资运输任务.已知（1）各条航线的起点、终点城 市及每天航班数.（2）假定各条航线使用相同型号的船只，又已 知各城市间的航程天数.（3）又知每条船只每次装卸货的时间各 需1天。问该航运公司至少应配备多少条船，才能满足所有航线的运输需求？ 每天航班数表航 线起点城市终春城市每天航班船1EDS2C23AF1AD1各城市之间的航程天数IACPEF4(J121477R0135eC,S01555D1501720E7B517 'G7&52030解：该公司所需配备船只分两部分：(1)载货航程需要的周转船只数。例如航线1,在港口 E装货1天，ED航程l 7天，在 D卸货1天，总计19天.每天3航班，故该航线周转船只需57 条.各条航线周转所需船只数见表.以上累计共需周转船只数91条.航域转值天数航程天教卸货天野小计航琥歌帚周转船只放11171jy357213152加317191413115115(2)各港口间调度所需船只数.有些港口每天到达船数多于需要 船数.例如港口 D,每天到达3条，需求1条；而有些港口到达 数少于需求数，例如港口 B.各港口每天余缺船只数的计算见表.港口城市督天到达每天需京i余域数A01B121C2Q2D31彳E03一 3F1A1为使配备船只数最少，应做到周转的空船数为最少.因此建 立以下运输问题