第七章运输问题

第七章运输问题一、运输问题模型及其求解思路二、几种特殊情况三、运输问题的应用一、运输问题模型及其求解思路1、问题的提出：某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3。各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示。问：应如何调运可使总运输费用最小？一、运输问题模型及其求解思路B1B2B3产量A1646200A2655300销量150150200运价表销量和＝产量和产销平衡一、运输问题模型及其求解思路B1B2B3产量A1x11x12x13200A2x21x22x23300销量150150200为建立模型，设xij为从产地Ai运往销地Bj的运输量，得到下表：运量表一、运输问题模型及其求解思路据题意，可建立线性规划模型：Minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200

x21+x22+x23=300

x11+x21=150

x12+x22=150

x13+x23=200xij≥0(i=1,2；j=1,2,3）一、运输问题模型及其求解思路2、产销平衡运输问题模型的特点从模型的建立可知：列数为2（产地数）×3（销地数）＝6；行数为2（产地数）+3（销地数）＝5；再观察模型的系数矩阵：一、运输问题模型及其求解思路111000200

000111300100100150

010010150

001001200前2行之和＝后3行之和一、运输问题模型及其求解思路对于产销平衡的运输问题，若产地为m个，销地为n个，则变量个数为m×n个，线性无关的约束条件个数为m+n-1，故基本解中的基变量个数为m+n-1。一、运输问题模型及其求解思路3、运输问题求解思路——表上作业法由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，则无法利用这些有利条件。人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法。（表上作业法略）运输问题的应用1、产销不平衡的运输问题例：某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示。问：应如何调运可使总运输费用最小？销量<产量运输问题的应用B1B2B3产量A1646300A2655300销量150150200运输问题的应用100x24x14库存量200150150销量300x23x22x21A2300x13x12x11A1产量B3B2B1多余的产量100作为库存，A1和A2各库存多少待定。运输问题的应用10000库存量200150150销量300556A2300646A1产量B3B2B1在运价表中也增加库存的相应列：库存量运价为0。运输问题的应用结论：对于产量大于销量的运输问题，在运输作业表上增加一列，其销量等于总产量和总销量之差，运价均为0。可以将增加的一列理解为假想销地，其销量即库存量。思考：对于销量大于产量的问题怎么办？销量>产量运输问题的应用B1B2B3产量A1646200A2655300销量250150200运输问题的应用办法：增加一行表示缺货量。100000缺货量200150250销量300556A2200646A1产量B3B2B1运输问题的应用实际应用中，可能出现的其他情况：（1）某些运输线路上的运输能力有限制；处理办法：直接在约束条件中增加该约束，即保证X14的取值不超过产量、销量和线路最大运输能力。（2）目标函数求最大值不是最小值；运输问题的应用（3）销量大于产量，但某些销地的销量必须完全满足，不能有缺货；处理办法：对缺货量到该销地的运价定为一个充分大的值M。（类似于大M法）运输问题的应用如表中B2销量不能短缺：1000M0缺货量200150250销量300556A2200646A1产量B3B2B1运输问题的应用（4）销量大于产量时，若某地的销量可以有一定量缺货，但供应量必须不小于某个值p；处理办法：将该销地分解为两个销地Bj1和Bj2，Bj1对应必须满足的销量p，Bj2对应缺货的销量bj-p。其中，缺货量到Bj1的运价为“大M”。运输问题的应用如表中B2销量不能低于100：10000缺货量200150250销量300556A2200646A1产量B3B2B1B21B22100504455M0运输问题的应用例1：石家庄北方研究院有一、二、三，三个区。每年分别需要用煤3000、1000、2000t，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000t，运价如下表。由于需大于求，经院研究决定一区供应量可减少0—300t，二区必须满足需求量，三区供应量不少于1500t，试求总费用为最低的调运方案。一区二区三区产量临城1.801.701.554000盂县1.601.501.751500销量300010002000运输问题的应用一区一区二区三区三区产量临城1.801.801.701.551.554000盂县1.601.601.501.751.751500假想产地M0MM0500销量270030010001500500解：根据题意，作出产销平衡的运价表，取M代表一个很大的正数，其作用是强迫相应的x31、x33、x34取值为0。运输问题的应用1234产量A1613221750B1413191560C192023——50最低需要量3070010最高需要量507030不限例2：设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相同，有关数据如下表。试求总费用为最低的化肥调拨方案。运输问题的应用1’1’’234’4’’产量A16161322171750B14141319151560C19192023MM50DM0M0M050销量302070301050解：根据题意，作出产销平衡的运价表运输问题的应用2、生产与储存问题例1：某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如下表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。运输问题的应用运输问题的应用解：设xij为第i季度生产的第j季度交货的柴油机数目，那么应满足：交货：

生产：x11

=10x11+x12+x13+x14≤25

x12+x22=15x22+x23+x24≤35

x13+x23+x33

=25x33+x34≤30

x14+x24+x34+x44=20x44≤10

运输问题的应用把第i季度生产的柴油机数目看作第i个生产厂的产量；把第j季度交货的柴油机数目看作第j个销售点的销量；成本加储存、维护等费用看作运费。可构造下列产销平衡问题：例2：光明仪器厂生产电脑绣花机是以产定销的。已知1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表：运输问题的应用已知上年末库存103台绣花机，如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本0.1万元,每台机器每月的平均仓储费、维护费为0.2万元。在7—8月份销售淡季，全厂停产1个月，因此在6月份完成销售合同后还要留出库存80台。加班生产机器每台增加成本1万元。问应如何安排1—6月份的生产，可使总的生产费用（包括运输、仓储、维护）最少？运输问题的应用解：这个生产存储问题可化为运输问题来做。考虑：各月生产与交货分别视为产地和销地。1）1-6月份合计生产能力（包括上年末储存量）为743台，销量为707台。设一假想销地销量为36；2）上年末库存103台，只有仓储费和运输费，把它列为的0行；3）6月份的需求除70台销量外，还要80台库存，其需求应为70+80=150台；4）1-6表示1-6月份正常生产情况，1’-6’表示1-6月份加班生产情况。运输问题的应用产销平衡的运价表：运输问题的应用3、转运问题原运输问题上增加若干转运站。运输方式有：产地转运站、转运站销地、产地产地、产地销地、销地转运站、销地产地等。例：某公司有A1、A2、A3三个分厂生产某种物质，分别供应B1、B2、B3、B4四个地区的销售公司销售。假设质量相同，有关数据如下表：运输问题的应用假设：

1、每个分厂的物资不一定直接发运到销地,可以从其中几个产地集中一起运；

2、运往各销地的物资可以先运给其中几个销地，再转运给其他销地；

3、除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与销地之间转运。运价