怎样掌握运输问题的数学模型.ppt

《怎样掌握运输问题的数学模型.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、OPERATIONSRESEARCH运筹学Ⅱ——怎样把事情做得最好OR21第四章运输问题本章要求：掌握运输问题的数学模型掌握运输问题的求解方法化产销不平衡问题为平衡问题学会用计算机求解OR224.1运输问题的数学模型运输问题一般表述为：某企业有m个产地（生产厂）Ai，其产量分别为ai,i=1,2,…m,n个销地（销售商）Bj，其销售量分别为bj,j=1,2,…n,从Ai到Bj的每单位物资的运费为Cij.要求拟定总运费最小的调运方案。OR23运输表.销地产地B1B2…Bn产量A1C11C12…C1na1A2C21C22…C2na2…

2、……………AmCm1Cm2…Cmnam销量b1b2…bnOR24运输问题的数学模型设从Ai到Bj的运输量为xij,（假定产销平衡）则总运费：minZ=∑∑Cijxij产量约束：∑xij=aii=1,2,…m,销量约束：∑xij=bjj=1,2,…n,非负性约束：xij≥0nmj=1i=1nj=1mi=1OR254.2表上作业法计算步骤：1、给出初始方案2、检验是否最优3、调整调运方案,Goto2OR26例题1某建材公司有三个水泥厂A1、A2、A3，四个经销商B1、B2、B3、B4，其产量、销量、运费如下表：销地产地B1B2B3B4

3、产量A1A2A3842774359216194销量324514OR274.2.1求初始调运方案用最小元素法（也可用西北角法或vogel法）给出初始基可行解：在运费表中找出最小元素，尽最大可能用完一个厂的产量，或满足一个商家的销量。得到满足者用线划去。逐次寻找最小元素，直至分配完毕注意：如填写一个数字同时满足了一厂一商，则需在同行或同列中填写一个数字0，以保证恰好有m+n-1个数字。OR28例1之初始方案（P119）最小元素法：圈定C24B1B2B3B4产量A187321A2475/594A324964销量3245OR29例1初始

4、方案（续1）圈定C31B1B2B3B4产量A187321A2475/594A3/349641销量3245OR210例1初始方案（续2）圈定C13B1B2B3B4产量A187/121A2475/594A3/349641销量32435OR211例1初始方案（续3）圈定C32B1B2B3B4产量A187/121A2475/594A3/3/19641销量321435OR212例1初始方案（续4）圈定C23B1B2B3B4产量A187/121A247/3/5941A3/3/19641销量321435OR213例1

5、初始方案（续5）圈定C22B1B2B3B4产量A187/121A24/1/3/5941A3/3/19641销量321435OR214例1初始方案——初始基可行解中心数字为分配的运输量B1B2B3B4产量A111A21359A3314销量3245此方案费用为40OR2154.2.2最优性检验最优性检验与单纯形法原理一致，计算方法有位势法和闭回路法，这里讲位势法。位势法是任意给出一组数ui和vj，称之为位势，有数字的格满足：ui+vj=cij没数字的格计算：σij=cij-(ui+vj)OR216位势计算：ui+vj先填写

6、初始方案相应的运费，任意给出一个ui或vj值，推出其它位势值。计算ui+vj，填于空格处B1B2B3B4uiA1（3）（5）3（-1）2A2（5）7514A324（2）（-2）1vj131-3OR217检验数计算：σij=cij-(ui+vj)B1B2B3B4uiA18-（3）=57-（5）=23-3=02-（-1）=32A24-（5）=-17-7=05-5=01-1=04A32-2=04-4=09-（2）=76-（-2）=81vj1313σ21=-1OR218方案调整：σij<0处，增加运输量，可节约运费。故做如下调整：B1B2

7、B3B4产量A111A2+11-1359A33-11+14销量3245OR219新方案：B1B2B3B4产量A111A21359A3224销量3245此方案费用为：13+14+35+51+22+42=39OR220新方案检验新方案相应的运费填于表上,给定位势初值，计算各位势值。B1B2B3B4uiA1（2）（4）3（-1）0A24（6）512A324（3）（-1）0vj243-1OR221新方案检验计算空格处（即非基变量）的检验数，σij=cij-(ui+vj)，所有σij≥0，已得最优解。B1B2B3B4uiA163

8、03A20100A30067vjOR2224.3产销不平衡问题产销不平衡是最常见的现象，此类问题可以转化为产销平衡的模型，而后求解。运输问题产销平衡模型，实质上就是一个求解运输问题的标准型。解决的办法是：增加一个虚拟的产地或销地，从而变成标准型——