第三章--运输问题的应用--运筹学

例1:某石油公司设有四个炼油厂，它们生产普通汽油，并为七个销售区服务，生产和需求情况如下：4.运输问题的应用炼油厂1234日产量（万公升）35251540销售区1234567日最大销售量（万公升）25201025101510从炼油厂运往第j个销售区每公升汽油平均运费（单位：角/公升），应如何调运，使运费最省。4.运输问题的应用123456716526363237586923486558547447474解：平衡问题，用最小元素法求初始方案。4.运输问题的应用1234567165263633523758692253486558515474474744025201025101510用最小元素法求初始方案。4.运输问题的应用123456716521063633523758692253486558515474474744025201025101510用最小元素法求初始方案。4.运输问题的应用12345671652106363352375869210253486558515474474744025201025101510用最小元素法求初始方案。4.运输问题的应用1234567165210631063352375869210253486558515474474744025201025101510用最小元素法求初始方案。4.运输问题的应用123456716521063106335231575869210253486558515474474744025201025101510用最小元素法求初始方案。4.运输问题的应用12345671652106310633523157586921025341086558515474474744025201025101510用最小元素法求初始方案。4.运输问题的应用1234567165210631063352315758692102534108655851547420474744025201025101510用最小元素法求初始方案。4.运输问题的应用12345671652106310633523157586921025341086555851547420474744025201025101510用最小元素法求初始方案。4.运输问题的应用1234567165210615310633523157586921025341086555851547420474744025201025101510用最小元素法求初始方案。4.运输问题的应用1234567165210615310633523157586921025341086555851547420475471544025201025101510用最小元素法求初始方案。4.运输问题的应用1234567165210615310633523157586921025341086555851547420475471544025201025101510计算检验数。4.运输问题的应用1234567ui165210615310630231575869210-234108655585-147420475471541vj5326364计算检验数。4.运输问题的应用1234567ui16152210615310603-1023157655846595210-2341086655553852-14714204175407154-11vj5326364（1，7）闭回路。4.运输问题的应用1234567ui16152210615310603-1023157655846595210-2341086655553852-14714204175407154-11vj5326364总运费=480000（元）4.运输问题的应用1234567ui1652106531063102325758692034865155854742047547154vj计算检验数。4.运输问题的应用1234567ui16252210653106031002325755483649420-13418665515538353-1472420417540715401vj4326363最优方案如下，最小运费=480000元4.运输问题的应用1234567ai11051010352250253151542051540bj25201025101510有非基变量的检验数=0，有无穷多组解，另外一个解如下：4.运输问题的应用1234567ai110105103522525315015420101040bj25201025101510例2:石家庄北方研究院有一、二、三，3个区。每年分别需要用煤3000、1000、2000t，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000t，运价如下表。由于需大于供，经院研究决定一区供应量可减少0—300t，二区必须满足需求量，三区供应量不少于1700t，试求总费用为最低的调运方案。4.运输问题的应用解:根据题意，作出产销平衡与运价表：取M代表一个很大的正数，其作用是强迫相应的x31、x33、x34取值为0。4.运输问题的应用生产与储存问题例3:某企业和用户签订了设备交货合同，已知该企业各季度的生产能力、每台设备的生产成本和每季度的交货量如下表。若生产出来的设备当季不交货，每台设备每季度需支付储存、维护等费用0.1万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。4.运输问题的应用季度生产能力（台）交货量（台）每台设备成本（万元）1251512.02352011.03302511.54202012.5交货：生产：x11=15x11+x12+x13+x14≤25x12+x22=20x22+x23+x24≤35x13+x23+x33=25x33+x34≤30x14+x24+x34+x44=20x44≤20解：设xij为第i季度生产的第j季度交货的设备台数，那么应满足：4.运输问题的应用把第i季度生产的设备数目看作第i个生产厂的产量；把第j季度交货的设备数目看作第j个销售点的销量；成本加储存、维护等费用看作运费。可构造下列产销平衡问题：3.运输问题的应用第一季度第二季度第三季度第四季度D产量第一季度12.012.112.212.30.025.0第二季度M11.011.111.20.035.0第三季度MM11.511.60.030.0第四季度MMM12.50.020.0销量15.020.025.020.030.0例4：有三个产地A1、A2和A3生产同一种物品，使用者为B1、B2和B3，各产地到各使用者的单位运价如下表。这三个使用者的需求量分别为10、4和6个单位。由于销售需要和客观条件的限制，产地A1至少发出6个单位的产品，它最多只能生产11个单位的产品；A2必须发出7个单位的产品；A3至少至少要发出4个单位的产品。试用表上作业法求该问题最优方案。4.运输问题的应用B1B2B3生产量A1243[6，11]A21567A3324[4,+∞]使用量10464.运输问题的应用B1B2B3B4生产量A1243M6A1'24305A2156M7A3324M4A3'32403使用量10465总需量＝10＋4＋6＝20；A1至少生产6个单位，A2必须生产7个单位；为保持供销平衡，A3至多生产？个单位：？＝20－6－7＝7