运输问答.ppt

第六章运输问题§1 运输模型§2 运输问题的计算机求解§3 运输问题的应用§4* 运输问题的表上作业法1问题的提出:一般的运输问题就是要解决把某种产品(或原料、资源等)从若干个产地调运到若干个销地,在每个产地的供给量与每个销地的需求量已知,并知道各地之间的运输单价的前提下,如何确定一个使得总的运输费用最小的方案。§1 运输模型2例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3,各产地的产量、各销地的销量和各产地运往各个销地每件物品的运费如下表所示,问:应如何调运可使总运输费用最小?§1 运输模型3解:产销平衡问题:总产量=总销量设xij为从产地Ai运往销地Bj的运输量,得到下列运输量表:§1 运输模型4MinZ=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)§1 运输模型5§1 运输模型一般运输模型:(1)A1、A2、…、Am表示某物资的m个产地;B1、B2、…、Bn表示某物质的n个销地;(2)si表示产地Ai的产量;dj表示销地Bj的销量;(3)cij表示把物资从产地Ai运往销地Bj的单位运价。xij表示从产地Ai运往销地Bj的运输量。(4)Z表示总的运输费用如果:s1+s2+…+sm=d1+d2+…+dn,则称该运输问题为产销平衡问题;否则,称产销不平衡。下面,首先讨论产销平衡问题。6运输问题数据表销地产地B1B2…Bn产量A1A2┇Amc11c12…c1nc21c22…c2n┇┇┇┇cm1cm2…cmns1s2┇sm销量d1d2…dn§1 运输模型7运输问题变量表§1 运输模型销地产地B1B2…Bn产量A1A2┇Amx11x12…x1nx21x22…x2n┇┇┇┇xm1xm2…xmns1s2┇sm销量d1d2…dn8§1 运输模型产销平衡运输问题的数学模型:mnMinZ=∑∑cijxiji=1j=.∑xij=sii=1,2,…,mj=1m∑xij=djj=1,2,…,ni=1xij≥0(i=1,2,…,m;j=1,2,…,n)在实际问题建模时,经常会出现如下一些变化(很值得关注):1)有时目标函数求最大,如求利润最大或营业额最大等;2)产销不平衡时,可增加一个假想的产地(销大于产时)或销地(产大于销时),从而使得总产量=总销量(因为计算机求解时需要保持是产销平衡的状态)。9§2 运输问题的计算机求解例2、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3,各产地的产量、各销地的销量和各产地运往各销地物品的单位运价如下表所示,问:应如何调运可使总运输费用最小?解:增加一个假想的销地B*4,由任意产地到该销地的单位运价为0,B*4的销量为100(600-500=100)。10