运筹学课程软件运输问答

1、第三章运输问题一、学习目的与要求1、掌握表上作业法及其在产销平衡运输问题求解中的应用2、掌握产销不平衡运输问题求解方法二、课时6学时第一节运输问题及其数学模型一、运输问题的数学模型单一品种运输问题的典型情况： 设某种物品有m个产地Ai,A2,Am,各产地的产量分别是 ai,a2,am； 有N个销地Bi,B2,Bn,各销地地销量分别为 bi,b2,bn。假定从产地Ai(i=1,2,m)向销地Bj(j=1,2,n) 运输单位物品的运价是 Cij,问怎样调运这些物品才能使总运费最小？为直观清楚起见，列出运输表：地产地、XB1B2Bn产量A1C11C12C1na1X11X12X1nA2C21C22C2

2、na2X21X22X2nC11C12C1nX11X12X1nAmCm1Cm2CmnamXm1Xm2Xmn销量b1b2b n表中xij为由产地Ai到销地Bj的物品数量，Cij表示产地Ai到销地Bj的单位运价。如果运输问题的总产量等于其总销量，即有 mnaibji 1j 1则称该运输问题为产销平衡运输问题；反之，称为产销不平衡运输问题。 产销平衡运输问题的数学模型如下：min z cj xji 1 j 1nxjai i 1,2,.,mj 1ms.t.xjbj j 1,2,.,n1 1Xj0这就是运输问题的数学模型，它包含mxn个变量，(n十m)个约束方程.其系数矩阵的结构比较松散，且特殊。二、运输

3、问题数学模型的特点1、运输问题有有限最优解，即必有最优基本可行解2、运输问题约束条件的系数矩阵A的秩为(m+n-1)n 力1 的上n1 1 , 1.11-1F行i ii jL 1 1 11 1 11 卜行-111J该系数矩陈中又应于变量Xij的系数向量pij,其分量中除第i个和第m十j个为1以外，其余的都为零.即Aj = (011 0)' =e i+e m+j对产销平衡的运输问题具有以下特点：(1)约束条件系数矩B$的元素等于0或1(2)约束条件系数矩阵的每一列有两个非零元素，对应于每一个变量在前m个约束方程中出现一次，在后 n个约束方程中也出现一次。此外，对于产销平衡问题，还有以下特

4、点(3)所有结构约束条件都是等式约束(4)各产地产量之和等于各销地销量之和第二节 用表上作业法求解运输问题解题步骤第1步：确定初始基本可行解。第2步：最优性判别，若最优准则b ij>0,则当前解最优，计算停止，否则转第3步。第3步：取一个检验数最小的非基变量做进基变量。第4步：调整当前基本可行解，转第 2步一、确定初始基本可行解（初始调运方案）以实例介绍：例 某部门有3个生产同类产品的工厂（产地）,生产的产品由4个销售点（销地）出售，各工厂的生产量、各 销点的销售量（假定产位均为 t）以及各工厂到各销售点的单位运价（元 /t）于下表中，要求研究产品如 何调运才能使总运费最小？销地产地B1

5、B2B3B4产量41241116A1A22103910A38511622销量8141214A最小元素法销地产地BiB2B3B4产量Ai41241116106A2210391082A38511622148销量814121434总运费（目标函数）：zCij Xij246这个解满足约束条件，其非零变量的个数为6 （等于i 1 j 1m+n-1=3+4-1=6)B西北角法销地产地BiB2B3B4产量2210391064A38511622814销量814121434总运费（目标函数）：zCij Xij 372这个解满足约束条件，其非零变量的个数为i 1 j 16 （等于m+n-

6、1=3+4-1=6）。C沃格尔（Vogel ）法销地产地BiB2B3B4产量行罚数12345Ai4124111600071124A221039101116682A3851162212148销量814121448列 罚 数12513221332124125234总运费（目标函数）：zcij xij244i 1 j 1、解的最优性检验1、闭回路法销地产地BiB2B3B4产量A141241116106A2210391082A38511622148销量8141214检验数表销地产地B1B2B3B4产量A112A21-1A31012销量由于240,故知解不是最优解。2、对偶变量法(也称位势法)对产销平衡

7、问题，若用Ui,U2,um,Vi ,V2,Vn分别表示前m个约束条件与后n个约束条件的对偶变量，即有对偶变量这时对偶问题的对偶规划写成Y (Ui,U2, Um,Vi,V2, Vn)mnmaxzaubjUji 1j 1Ui VjCijis.t.1.2,1.2,m,nUi,Vj的符号不限由上一章知道，线性规划问题变量Xj的检验数可表示为j Cj zj1CjCb B PjCjYPj由此可写出运输问题某变量Xij的检验数如下：ijCijzij CijYPijCij(U1,U2, ,Um,V1,V2,Vn)PjCij (Ui Vj)现设我们已得到解到了运输问题的一个基可行解，其基变量是Xi1j1,Xi1

8、2j2,Xisjs,Sm n 1由于基变量的检验数等于零，故对这组基变量可写出方程组Ui1Vj1Ci11,j1Ui21 Vj 2Ci2,j2Uis1Vjs Gf，js这个方程组有m+n-1个方程。解以上方程组，可得解(上方程组解不唯一)，此方程组解称为位势。由上章知当每个 ij Cij (Ui Vj)0达到最优解。例 用位势法对上例最小元素法有的解作最优性检验。销地产地BiB2B3B4产量U iAl41241116U1106A2210391082U28511622U3A3148销量814121448VjV1V2V3V4解：先建立方程组令U20得方程组的解：V计算检验数2y 3U1U1U2U2U

9、3U3U11,V4V34V4 11V12V3 3v2 5v4 610,U34,V2 9销地产地BiB2B3B4产量U iAi412411161A221039100A38511622-4销量814121448Vj29310由于。24<0 ,故知解不是最优解。三、解的改进(用闭回路法调整当前基可行解)解的改进步骤：(1)以Xij为换入变量，找出运输表中的闭回路;(2)对顶点进行编号；(3)确定换出变量：在闭回路上的所有偶数顶点中找出运输量量小的顶点，以该格中的变量为换出 变量；(4)以换出变量值为奇数顶点处的运输量增加值，得新的运输方案；(5)检验新的方案是否为最优，如否则重复以上步骤。例：

10、对上例进行改进求解。销地产地BiB2B3B4产量u iAi4i24iii62io6A22io39io0820A385ii622-3i48销量8i4i2i448Vj2829目标函数值为244Ui V34u1V4 11u2 V)2u2 v4 9u3 v2 5令U2U3 V46销地产地BiB2B3B4产量u iAi4i24iii620200A22i039i0002i0A385ii622-390i20销量8i4i2i448Vj28293,V28,V320得方程组的解：Vi 2,V49,ui 2,u3因此此方案为最优方案。四、表上作业法计算中的几个问题1、某个基本可行解有几个非基变量的检验数为负若运输问

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

12、个空格中填入数字0,表示这个格中的变量是取值为0的基变量，使迭代过程中基可行解的分量恰好为 m+n-1个。b.在用闭回路法调整当前基本可行解时，调整量。的取值应为。=minx u/（i,j）为闭回路上所有偶数号格点。这时可能出现有两个（或以上）偶数号格点的xij都相等且都为极小值，只能取其中一个为离基格，其余的仍作为基格，而在作运输量调整时，运输量与。相等的那些偶数号格点的 Xij都将调整为0,因此得到的也是一个退化了的基可行解。第三节运输问题的进一步讨论、产销不平衡的运输问题1、如果总产量大于总销量，即此时运输问题的数学模型为mnai bji 1j 1m nmin zcj xji 1 j 1

13、nxjaii 1,2,.,mj 1 ms.t.Xij bj j 1,2,.,ni 1X 0为借助产销平衡时表上作业法求解，可增加一个假想销地Bn+1 ,由于实际上它不存在，因而由产地 Ai(i=1,2,m)调运到这个假想销地的物品数量Xi,n+1 (相当于松驰变量)，实际上是就地存贮在Ai的物品数量。就地存贮的物品数量不经运输，故可令其运价Ci,n+1 =0 (i=1,2,m)。若令假想销地的销量为bn+1 ,且mnbn 1aibji 1j 1则模型变为n1Xij j1mxij i 1xijm n 1 min z q 为 i 1 j 1ai i 1,2,.,mbjj 1,2,.,n 10运输表

14、地产地B1B2BnBn+ 1产量AiXC1111X1C122XC1 n1n0a1A2X：C2121XC222X：C2 n2n0a2XC1111X1C122XC1 n1n0AmXnCm111XrCm2n2XrCm nnn0am销量b1b2b nb n+12、总销量大于总产量可假想增加一个产地 Am+1 ,它的产量等于 nam 1bjj 1由于这个产地并不存在，求出由它发往各销地的物品数量mai i 1xm+i,j (j=1,2,，n),实际上各销地所需物品的欠缺额，显然有Cm+1,j =0 (j=1,2,，n)。因此数学模型为min znXj j 1 mXj i 1Xijm 1 nCijXij

15、i 1 j 1ai i 1,2,.,m 1bjj 1,2,.,n0例 某市有三个造纸厂 A1,A2,A3,其纸产量分别为8,5, 9个单位，有4个集中用户B1,B2,B3,B4,其需用量销地产地B1B2B3B4产量A1312348A2112595A367159为4, 3, 5, 6个单位，由各厂到各用户的单位运价如表所示，试确定总运费最小的调运方案。解略:最优方案如下销量4356销地产地BiB2B3B4产量Ai31234844A21125953A36715952销量4356Min z= 49二、有转运的运输问题假定某一产品有 m个产地Al,A2,Am和n个销地Bl,B2,Bn,都可作为中间站使

16、用，从而发送物品的 地点和接收物品的地点都有 m+n个。这样一来，我们就得到一个扩大了的运输问题。令ai：表示第i个产地的产量（净供应量）；bj：表示第j个销地的销量（净需要量）；Xij：表示第i个发送地运到第j个接收地的物品数量；cu：表示第i个发送地运到第 j个接收地的单位运价； ci：表示第i个地点转运单位物品的费用。若将产地与销地统一编号，并把产地排在前，销地排在后，则有 am 1 am 2am n 0运输表：bi b2bm 0产地销地产地销地发送量1mm 1m n1X11X1mX1,m 1X1,m nQ a1产地mXm1XmmXm,m 1Xm,m nQ amm 1Xm 1,1Xm 1

17、,mXm 1 ,m 1Xm 1,m nQ销地n mXn m,1Xm m ,mXm n,m 1Xm n,m nQQ接收量QQQ bm 1Q bm n假定为产销平衡问题，即有 mm naibj Qi 1j 1产地销地产地销地发送里1mm1m n1Gc1mc1,m1c1,m nQa1产地mcm1cmcm,m1cm,m nQamm 1cm 1,1cm 1 ,mcm1cm 1,m nQ销地n mcn m,1cm m,mcm n,m1cm nQQ接收量QQQbm1Qbmn运价表:例：如下图示出了一个运输系统，它包括两个产地、两个销地及一个中转站，各产地产量和各销地销 量用相应节点处箭线旁的数字表示，节点连

18、线上的数字表示其间的运输单价，节点旁的数字为该地的转运 单价，试确定最优运输方案。40用最小元素法得初始运输方案，最经过解:销地产地产地转运销地发送 量12345产地150(-450)5310(210)M602550(-150)(220)2M020(420)90转运33250 (-330)(250)550销地42M550(-350)6505M45650(-550)50销量50505080702次迭代得最优解，总运费300 。第四节应用问题举例由于在变量个数相等的情况下，表上作业法的计算远比单纯形法简单得多.所以在解决实际问题时, 人们常常尽可能把某些线性规划的问题化为运输问题的数学模型.下面介

19、绍几个典型的例子.例1某厂按合同规定须于当年每个季度末分别提供10, 15, 25, 20台同一规格的柴油机.已知该厂各季度的生产能力及生产每台柴油机的成本如表所示.又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用0.15万元.要求在完成合同的情况下，做出使该厂全年生产（包括储存、维护）费用最小的决策.季 度生产能力（自）单位成本1万元）12511Ik 1111邦11*0IV1011,3Xij为第i季度生产的用于第j季度交货的柴解：由于每个季度生产出来的柴油机不一定当季交货，所以设 油机数.根据合同要求，必须满足：X1110X12X2215X13X23X33X14X24

20、X3425X4420又每季度生产的用于当季和以后各季交货的柴油机数不可能超过该季度的生产能力，故又有:X11X12X13x14 25X22X232X2435X33X3430X4410第i季度生产的用于j季度交货的每台柴油机的实际成本cij应该是该季度单位成本加上储存、维护等费用.Cij的具体数值见表表% 11C万元）、 iInHlIVIINID*9J+ U1011 .nnIL15IIIL l.UOIMSTV11/0设用ai表示该厂第i季度的生产能力，bj表示第j季度的合同供应量，则问题可写成：44min zCij 为i 1 j 14Xj aij i4xij bji 1Xj 0因为当j<i

21、时，xij=0所以当j<i时，取Cij=M,M 为一个充分大的正数。此外，由于是产量大于销量的不平衡问题，加上一个假想的需求 D,就可以把问题变成产销平衡的运输模型，并写出产销平衡表和单位运价表（合在一起，如下）1IT!inIV口产且1转025tlAJiiaoU-»n0IKM11.OU11.1，D蚪IVifMM门 ,却I#M盘n111IS即经用表上作业法求解，可得多个最优方案，表3-32中列出最优方案之一.即第 1季度生产25台，10台当季交货，15台H季度交货；n季度生产5台.用于出季度交货；出季度生产30台，其中20台于当季交货，10台于IV季度交货IV季度生产10台，于当季交货.按此方案生产，该厂总的生产（包括储存、维护）的费用为773万元.9 s 32箱W车度生产至应1til(V0CftJ 11 111 IV1015tl5*诃死25养,1010蟠 ft1U15却例2 某航运公司承担六个港口城市A、B、C、D、E、F的四条固定航线的物资运输任务.已知 （1）各条航线的起点、 终点城市及每天航班数.（2）假定各条航线使用相同型号的船只，又已知各城市间的航程 天数.（3）又知每条船只每次装卸货的时间各需1天。问该航运公司至少应配备多少条船，才能满足