运输问题模型与算法.ppt

该【运输问题模型与算法 】是由【小屁孩】上传分享，文档一共【52】页，该文档可以免费在线阅读，需要了解更多关于【运输问题模型与算法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。4运输问题—&T公司的配送问题案例Figure1LocationofthecanneriesandwarehousesfortheP&\ToSacramentoSaltLakeCityRapidCityAlbuquerqueCanneryBellingham75000Eugene565550AlbertLea0015852021/10/104卡车的运输成本WarehouseFrom\ToSacramentoSaltLakeCityRapidCityAlbuquerqueCanneryBellingham$464$513$654$867Eugene352416690791AlbertLea995682388685总的运输成本=75($464)+5($352)+65($416)+55($690)+15($388)+85($685)=$165,5952021/10/105运输问题的特点需求假设每一个出发地都有一个固定的供应量,所有的供应量都必须配送到目的地。每一个目的地都有一个固定得需求量,整个需求量都必须由出发地满足。可行解的特性当且仅当供应量的总和等于需求量的总和时,运输问题才有可行解。成本假设从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系。这个成本就等于配送的单位成本乘以所配送的数量。2021/10/106网络表示2021/10/,有n个地区需要该类物资令a1,a2,…,am表示各产地产量,b1,b2,…,bn表示各销地的销量,?ai=?bj称为产销平衡设xij表示产地i运往销地j的物资量,wij表示对应的单位运费,则我们有运输问题的数学模型如下:2021/10/108运输问题有m?n个决策变量,m+n个约束条件。由于产销平衡条件,只有m+n–1个相互独立,因此,运输问题的基变量只有m+n–1个2021/10/109例1某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示,问:应如何调运可使总运输费用最小?解:产销平衡问题:总产量=总销量设xij为从产地Ai运往销地Bj的运输量,得到下列运输量表:Minf=6x11+4x12+6x13+6x21+5x22++x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij≥0(i=1、2;j=1、2、3)2021/10/1010