7第七章运输问题

管理运筹学第七章运输问题运输问题的计算机求解运输问题的应用运输问题的表上作业法本章内容1234§1运输模型例1.某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如表所示，问：应如何调运可使总运输费用最小？销地运费单价/元产地B1B2B3产量/件A1646200A2655300销量/件150150200§1运输模型解：产销平衡问题：总产量=总销量设xij为从产地Ai运往销地Bj的运输量，得到运输量表销地运输量产地B1B2B3产量/件A1x11x12x13200A2x21x22x23300销量/件150150200500§1运输模型minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200（产地A1）x21+x22+x23=300（产地A2）x11+x21=150（销地B1）x12+x22=150（销地B2）x13+x23=200（销地B3）xij≥0(i=1、2；j=1、2、3）§1运输模型一般运输问题的线性规划模型：产销平衡A1、A2、…、Am表示某物资的m个产地；B1、B2、…、Bn表示某物资的n个销地；si表示产地Ai的产量；dj表示销地Bj的销量；cij表示把物资从产地Ai运往销地Bj的单位运价。§1运输模型设xij为从产地Ai运往销地Bj的运输量，则一般运输问题模型：1111mins.t.1,2,1,2,1,2,,;1,2,,mnijijijnijijmijjiijfcxxsimxdjnximjn,,≥01111mins.t.1,2,1,2,1,2,,;1,2,,mnijijijnijijmijjiijfcxxsimxdjnximjn,,≥01111mins.t.1,2,1,2,1,2,,;1,2,,mnijijijnijijmijjiijfcxxsimxdjnximjn,,≥01111mins.t.1,2,1,2,1,2,,;1,2,,mnijijijnijijmijjiijfcxxsimxdjnximjn,,≥0(产地Ai)(销地Bj)§1运输模型变化：（1）求目标函数最大：利润最大或营业额最大。（2）运输线路上有能力限制时，模型中加入约束条件（等式或不等式约束)。（3）产销不平衡时，加入假想的产地（销大于产）或假想销地（产大于销）。运输问题的计算机求解运输问题的应用运输问题的表上作业法本章内容2341§2运输问题的计算机求解例2.某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示，问：应如何调运可使总运输费用最小？销地运费单价/元产地B1B2B3产量/件A1646300A2655300销量/件150150200600500§2运输问题的计算机求解解：销地运费单价/元产地B1B2B3产量/件A1646300A2655300销量/件15015020060000100B4600500产销平衡运输费用？增加一个虚设的销地B4，即增加一个仓库进行货物存储增加一个虚设的销地B4§2运输问题的计算机求解数据输入“管理运筹学”软件§2运输问题的计算机求解由软件得，最优解为：X11=50,X12=150,X13=0,X14=100,X21=100,X22=0,X23=200,X24=0.minf=2500.§2运输问题的计算机求解例3.某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示，问：应如何调运可使总运输费用最小？销地运费单价/元产地B1B2B3产量/件A1646200A2655300销量/件250200200500650§2运输问题的计算机求解解：销地运费单价/元产地B1B2B3产量/件A1646200A2655300销量/件250200200650增加一个虚设的产地A35006500150A300产销平衡运输费用？增加一个虚设的产地A3，即缺货§2运输问题的计算机求解数据输入“管理运筹学”软件§2运输问题的计算机求解由软件得，最优解为：X11=0,X12=200,X13=0,X21=100,X22=0,X23=200,X31=150,X32=0,X33=0.minf=2400.运输问题的计算机求解运输问题的应用运输问题的表上作业法本章内容3412§3运输问题的应用例4.石家庄北方研究院有三个区，即一区，二区，三区，每年分别需要用煤3000t、1000t、2000t，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500t、4000t，运价如表所示。销地运费单价产地一区二区三区山西盂县1.801.701.55河北临城1.601.501.75一、产销不平衡的运输问题单位/(百元/t)§3运输问题的应用由于需大于供，经院研究决定一区供应量可减少0-300t，二区必须满足需求量，三区供应量不少于1500t，试求总费用为最低的调运方案。§3运输问题的应用解：根据题意，作出产销平衡与运价表。销地运费单价/百元产地一区1一区2二区三区1三区2供应量/t山西盂县1.801.801.701.551.554000河北临城1.601.601.501.751.751500需求量/t2700300100015005006000需求必须满足需求必须满足需求必须满足55006000500产销平衡0MMM0假想生产点运输费用？这里M代表一个很大的正数，其作用是强迫相应的x31、x33、x34取值为0。非必须满足非必须满足§3运输问题的应用由软件计算可得，最优解为：X11=2200,X14=1500,X15=300,X21=500,X23=1000,X32=300,X35=200总运费为9050百元§3运输问题的应用例5.设有A、B、C三个化肥厂供应四个地区的农用化肥。假设等量的化肥在这些地区使用效果相同，有关数据如表。试求总费用为最低的化肥调拨方案。销地运费单价/（元/吨)产地IIIIIIIV产量/万吨A1613221750B1413191560C192023--50最低需求/万吨3070010最高需求/万吨507030不限§3运输问题的应用解：根据题意，作出产销平衡与运价表。销地运费单价/（元/吨)产地I′I″IIIIIIV′IV″产量/万吨A16161322171750B14141319151560C19192023MM50D50销量/万吨3020703010210210必须满足必须满足必须满足虚设产地运费为050MMM000虚设产地运费为0虚设产地运费为0运输费用？§3运输问题的应用应用软件计算，最优解如表。单位/万吨最小总费用为2460万元。销地运输量产地I′I″IIIIIIV′IV″产量A5050B20103060C3020050D302050销量302070301050210210§3运输问题的应用例6.某运输问题如下表所示，并假设各个产地的货物储存都发生费用，其中1、2、3产地的单位存储费用分别为3、2、1元。假定产地2的物资必须至少运出28个单位，产地3至少运出17个单位，试求费用最少的运输方案。单位：元销地运费单价/元产地123产量145320253430335220销量2030107060§3运输问题的应用产大于销问题，构造产销平衡与运价表。销地运费单价产地123产量1453202534282’53423352173‘3523销量20301070必须满足必须满足10MM32160704（库存）运输费用？存储费用存储费用存储费用产销平衡§3运输问题的应用由软件计算可得，最优解为：X11=13,X14=7,X22=28,X32=2,X41=7,X43=10,X54=3.总运费为207元。§3运输问题的应用例7.造船厂根据合同从当年起连续三年末各提供五条规格型号相同的大型客货轮。该厂这三年内生产大型客货轮的能力及每艘客户轮的成本如下：年度正常生产能力/台加班生产能力/台正常生产单位成本/万元133600242700323650二、生产与储存问题§3运输问题的应用已知加班生产时，每艘客货轮成本比正常高出10%，造出的客货轮如当年不交货，每艘每积压一年所造成的积压损失为60万元。在签合同时，该厂已积压了两艘未交货的客货轮，而该厂希望在第三年末完成合同后还能存储一艘。问该厂应如何安排每年客货轮的生产量，使在满足上述各项要求的情况下，总的生产费用为最少？§3运输问题的应用解：化为运输问题。考虑：每年生产与交货分别视为产地和销地（1）1-3年合计生产能力（包括第1年初积压量）为19艘，销量为16艘。设一假想销地销量为3艘；（2）第1年初积压量2艘，只有积压损失费，列为第0行；（4）1-3表示1-3年正常生产情况，1'-3'表示1-3年加班生产情况。（3）第3年的需求除5艘销量外，还要1艘库存，其需求为5+1=6艘；§3运输问题的应用产销平衡与运价表：销售年单价/万元生产年123正常产量/艘加班产量/艘0601201802160066072031′66072078032M70076042′M77083023MM65023′MM7153销量/台55619虚拟的销地，即为仓库假想销地产销平衡运输费用？316190000000§3运输问题的应用用管理运筹学软件解得：1-3年最低生产费用为9665万元，每年的生产销售安排如下。单位/艘销售年运输量生产年123假想销量011131′21242′2323′3§3运输问题的应用例8.某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表所示。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下，该厂全年生产总费用最小的决策方案。§3运输问题的应用季度生产能力/台单位成本/万元I2510.8II3511.1III3011.0IV1011.3解：设xij为第i季度生产的第j季度交货的柴油机数目§3运输问题的应用设cij为第i季度生产的第j季度交货的柴油机的实际成本，应是第i季度生产单位成本加上存储、维护费用。单位/万元jiIIIIIIIVI10.810.9511.1011.25II11.1011.2511.40III11.0011.15IV11.30不可能的情况，费用？MMMMMM§3运输问题的应用构造假想的需求D，产销平衡与运价表：销地运费单价/万元产地IIIIIIIV产量/台I10.810.9511.1011.2525IIM11.1011.2511.4035IIIMM11.0011.1530IVMMM11.3010销量/台10152520100虚拟的销地，即为仓库30100D产销平衡运输费用？700000§3运输问题的应用运用软件计算，最优解：单位/台最优值为773万元。销地运输量产地IIIIIIIVD产量I1015025II053035III25530IV1010销量1015252030§3运输问题的应用三、转运问题发点：发货量〉收货量中转站：发货量=收货量收点：发货量〈收货量§3运输问题的应用在原运输问题上增加若干中转站：允许物品从一个发点运往另一个发点或中转站或收点；允许物品从一个中转站运往另外一个中转站或发点或收点；允许物品从一个收点运往另外一个收点或中转站或发点。§3运输问题的应用例9.腾飞电子仪器公司在大连和广州有两个分厂生产同一种仪器，大连分厂每月生产400台，广州分厂每月生产600台。该公司在上海和天津有两个销售公司负责对南京、济南、南昌、青岛四个城市的仪器供应。另外因大连距青岛较近，公司同意大连分厂向青岛直接供货，运输费用如图，单位百元。问应该如何调运仪器，可使总运输费用最低？§3运输问题的应用腾飞公司运输网络图