(典型例题)《运筹学》运输问题.ppt

《(典型例题)《运筹学》运输问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章运输问题Transportationproblem2008/111--《运筹学》运输问题--3.1运输问题的典例和数学模型一、典例：某食品公司经营糖果业务，公司下设三个工厂A1、A2、A3，四个销售门市部B1、B2、B3、B4。已知每天各自的生产量、销售量及调运时的单位运输费用情况。问：如何调运可使总费用最小？生产量：A1——7吨，A2——4吨，A3——9吨销售量：B1——3吨，B2——6吨，B3——5吨，B4——6吨产地单位运价销地B1B2B3B4A1A2A33113101928741052008/1

2、12--《运筹学》运输问题--调运示意图A1A2A3B1B2B3B47吨4吨9吨3吨6吨5吨6吨x11x12x13x14x21x22x23x24x31x32x33x34产地销地2008/113--《运筹学》运输问题--二、建立模型设xij——第i产地到第j销地之间的调运量，则有Minz=cij·xij34i=1j=1x11+x12+x13+x14=7x11+x21+x31=3xij0,(i=1,2,┄,3；j=1,2,┄,4)产量限制销量限制x21+x22+x23+x24=4x31+x32+x33+x3

3、4=9x12+x22+x32=6x13+x23+x33=5x14+x24+x34=62008/114--《运筹学》运输问题--一般模型表示：设有个m产地、n个销地，其中第i个产地的产量为ai，第j个销地的销量为bj，且ai=bj。若第i个产地到第j个销地每调运单位物资的运费为cij，则使总费用最少的调运模型为：Minz=cij·xijni=1j=1m2008/115--《运筹学》运输问题--三、模型的特点1.变量数：mn个2.约束方程数：m+n个最大独立方程数：m+n-13.系数列向量结构：Pij

4、=0····1···1···0——第i个分量——第m+j个分量2008/116--《运筹学》运输问题--x11x12······x1nx21x22······x2n,············,xm1xm2······xmn11······100······0············00······000······011······1············00······000······000······0············11······110······010······0···········

5、·10······001······001······0············01······000······100······1············00······1i=1i=2i=mj=1j=2j=n·······················································································································································

6、····································2008/117--《运筹学》运输问题--3.2运输问题的表上作业算法和程序求解表上作业法步骤:初始方案最优性检验改进方案一、初始方案的确定1.最小元素法2.Vogel法二、最优性检验1.闭回路法2.位势法三、方案改进方法在闭回路内改进。2008/118--《运筹学》运输问题--产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产量销量311310192874105634313

7、36567493656749产量销量363521(1)(2)(1)(-1)(10)(12)△z=c11-c13+c23-c21=1=11△z=c12-c14+c24-c22=2=12(0)(2)(2)(9)(1)(12)单位运价表产销平衡表2008/119--《运筹学》运输问题--产地销地A1A2A3B1B2B3B4749产量销量3656635213产地销地A1A2A3B1B2B3B4行两最小元素之差列两最小元素之差31131019287410501125130122-1301-2-1276---12Vo

8、gel法:产销平衡表2008/1110--《运筹学》运输问题--产地销地A1A2A3B1B1B3B43101845位势法:(3)(9)(7)(-2)(1)(-2)2.计算行位势和列位势；令u1=1，则依cij=ui+vj计算各ui和vj3.计算空格处位势；ij=ui+vj行位势列位势12-1-42894.计算空格处检验数：ij=cij-ij1.数字格处上添上对应的运价；销地A1A2A3B1B1