第七章运输问题

第七章运输问题一、运输问题模型及其求解思路二、几种特殊情况三、运输问题的应用一、运输问题模型及其求解思路1、问题的提出：某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3。各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示。问：应如何调运可使总运输费用最小？一、运输问题模型及其求解思路B1B2B3产量A1646200A2655300销量150150200运价表销量和＝产量和产销平衡一、运输问题模型及其求解思路B1B2B3产量A1x11x12x13200A2x21x22x23300销量150150200为建立模型，设xij为从产地Ai运往销地Bj的运输量，得到下表：运量表一、运输问题模型及其求解思路据题意，可建立线性规划模型：Minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij≥0(i=1,2；j=1,2,3）一、运输问题模型及其求解思路2、产销平衡运输问题模型的特点从模型的建立可知：列数为2（产地数）×3（销地数）＝6；行数为2（产地数）+3（销地数）＝5；再观察模型的系数矩阵：一、运输问题模型及其求解思路111000200000111300100100150010010150001001200前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万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。运输问题的应用生产能力（台）单位成本（万元）一季度2510.8二季度3511.1三季度3011.0四季度1011.3运输问题的应用解：设xij为第i季度生产的第j季度交货的柴油机数目，那么应满足：交货：生产：x11=10x11+x12+x13+x14≤25x12+x22=15x22+x23+x24≤35x13+x23+x33=25x33+x34≤30x14+x24+x34+x44=20x44≤10运输问题的应用把第i季度生产的柴油机数目看作第i个生产厂的产量；把第j季度交货的柴油机数目看作第j个销售点的销量；成本加储存、维护等费用看作运费。可构造下列产销平衡问题：第一季度第二季度第三季度第四季度D产量第一季度10.8010.9511.1011.2025第二季度M11.1011.2511.40035第三季度MM11.0011.15030第四季度MMM11.30010销量1015252030例2：光明仪器厂生产电脑绣花机是以产定销的。已知1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表：正常生产能力（台）加班生产能力（台）销量（台）单台费用（万元）1月份6010104152月份501075143月份902011513.54月份10040160135月份10040103136月份80407013.5运输问题的应用已知上年末库存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月份加班生产情况。运输问题的应用产销平衡的运价表：1月2月3月4月5月6月虚销地正常产量加班产量00.30.50.70.91.11.3010311515.315.515.715.916.10601’1616.316.516.716.917.10102M1414.314.514.714.90502’M1515.315.515.715.90103MM13.513.814.014.20903’MM14.514.815.015.20204MMM13.013.313.501004’MMM14.014.314.50405MMMM13.013.301005’MMMM14.014.30406MMMMM13.50806’MMMMM14.5040销量1047511516010315036------------------------运输问题的应用3、转运问题原运输问题上增加若干转运站。运输方式有：产地转运站、转运站销地、产地产地、产地销地、销地转运站、销地产地等。例：某公司有A1、A2、A3三个分厂生产某种物质，分别供应B1、B2、B3、B4四个地区的销售公司销售。假设质量相同，有关数据如下表：B1B2B3B4产量A13113107A219284A3741059销量365620运输问题的应用假设：1、每个分厂的物资不一定直接发运到销地,可以从其中几个产地集中一起运；2、运往各销地的物资可以先运给其中几个销地，再转运给其他销地；3、除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与销地之间转运。运价如下表，试求总费用为最少的调运方案。运输问题的应用A1A2A3T1T2T3T4B1B2B3B4A1132143311310A21--35--21928A33--1--2374105T12311322846T215--1114527T34--23121824T43232121--26B13172411142B21194858--121B332104222423B410856746213解：把此转运问题转化为一般运输问题：1、把所有产地、销地、转运站都同时看作产地和销地；2、不可能方案的运费取作M，自身对自身的运费为0；3、产量及销量可定为：中转站产量和销量均为20，产地产量为原产量+20，销量为20销地产量为20，销量为原销量+20。其中，20为各点可能变化的最大流量；4、对于最优方案，其中xii为自身对自身的运量，实际上不进行运作。运输问题的应用A1A2A3T1T2T3T4B1B2B3B4产量A1013214331131027A210M35M2192824A33M01M237410529T12310132284620T215M1011452720T34M23102182420T432321201M2620B13172411014220B21194858M102120B332104222420320B410856746213020销量2020202020202023262526可得到扩大的产销平衡运输问题表：