第三章运输规划-PowerPointPresentat

本章重点第三章货物运输方案的优化方法产销平衡运输问题的数学模型产销平衡运输问题的表上作业法本章内容运输问题的数学模型表上作业法运输问题的扩展§1货物运输问题bn…b2b1需求量Bn…B2B1需方供方AmA2A1ama2a1供应量nijjm1iiba供需平衡运价bn…b2b1需求量BnB2B1需方供方AmA2A1ama2a1供应量nijjm1iibacmncm2cm1c2nc22c21c1nc12c11…………如何建立供需搭配，使总的运输费用最小？供需平衡表数学模型设从Ai到Bj的物资运量为xij，n1jm1iijijxczmin产销平衡运输问题的数学模型。n1jjm1iibaAi的产品全部供应出去m,,2,1iaxin1jijn,,2,1jbxjm1iijBj的需求全部得到满足n,,2,1j;m,,2,1i0xijm×n个变量，m+n个约束，独立的约束方程m+n-1个，每个变量的系数是有2个1、其它元素均为0的向量。1111111111111111mnm2m12n222111xxxxxxxxxn11211mn销产B1B2…Bn产量c11c12c1nA1x11x12…x1na1c21c22c2nA2x21x22…x2na2┇┇┇┇┇┇cm1cm2cmnAmxm1xm2…xmnam销量b1b1…bn平衡表、运价表和二为一：销产B1B2…Bn产量A1x11x12x1na1A2x21x22x2na2┇┇┇┇┇┇Amxm1xm2xmnam销量b1b1…bn约束条件或解可用产销平衡表表示:minjijijxczmin11)n,,j(bx)m,,i(axmijijnjiij1111)n,,j;m,,i(xij110ui‚vj无约束（i=1,2,…,m;j=1,2,…,n)uivj设ui,vj为对偶变量，对偶问题模型为nijjjm1iiivbuawmaxijjicvum个n个§2初始调运方案的编制计算步骤：(1)找出初始调运方案。即在(m×n)产销平衡表上给出m+n-1个数字格。(最小元素法或差值法）(2)求检验数。（闭回路法或位势法）判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。(3)对方案进行改善，找出新的调运方案。（表上闭回路法调整）确定m+n-1个基变量(4)重复（2）、（3），直到求得最优调运方案。空格例运输问题供需平衡表和运价表如下，求最优调运方案。供需B1B2B3B4供应量（T）A13113107A219284A3741059需求量（T）3656⑴最小元素法销产B1B2B3B4产量311310A171928A2474105A39销量3656314633Z=4×3+3×10+3×1+1×2+6×4+3×5=86该方案总运费：.②差额法分别计算各行、各列次小、最小运价的差额，优先在最大差额处进行供需搭配。销地产地B1B2B3B4行差额A1A2A3317119432101085011列差额2513步骤：10计算未划去行、列的差额；20找出最大差额对应的最小元素cij进行供需分配；30在未被划去的行、列重新计算差额。销产B1B2B3B4供量A17A24A39销量36566B1B2B3B4行差额A13113100A219281A3741051列差额2513销产B1B2B3B4供量A17A24A39销量36566B1B2B3B4行差额A13113100A219281A3741052列差额2133销产B1B2B3B4供量A17A24A39销量36566B1B2B3B4行差额A13113100A219281A374105列差额21233销产B1B2B3B4供量A17A24A339销量36566B1B2B3B4差额A13113107A219286A374105差额123512§3调运方案的改进①闭回路法闭回路：从空格出发顺时针(或逆时针)画水(或垂直)直线，遇到填有运量的方格可转90°，然后继续前进，直到到达出发的空格所形成的闭合回路。调运方案的任意空格存在唯一闭回路。销产B1B2B3B4供量A1527A2314A3639销量3656差额法方案一、最优调运方案的判定①闭回路法闭回路：从空格出发顺时针(或逆时针)画水平(或垂直)直线，遇到填有运量的方格可转90°，然后继续前进，直到到达出发的空格所形成的闭合回路。调运方案的任意空格存在唯一闭回路。销产B1B2B3B4供量A1527A2314A3639销量3656销产B1B2B3B4产量311310A171928A2474105A39销量3656314633最小元素法+-+-x11为换入变量，x11增加1，运费的变化为3-1+2-3=1。这个变化就是x11的检验数，故11=1基变量的检验数为零(基变量xij)，ij=cij-(ui+vj),ui,vj自由变量②.位势法标准型运输问题的对偶问题是：njjjmiiivbuamax11)n,,j;m,,i(cvuijji11XBXNXS0CN-CBB-1N-CBB-1-YS1-YS2-Y检验数得m+n-1个方程，令某个ui(或vj)=0，可解出m+n个ui和vj；由此得非基变量的检验数。对偶变量值等于原问题的检验数松弛变量销产B1B2B3B4产量311310A171928A2474105A39销量3656314633位势法令v1=0,由c21=3=u2+v1，得u2=3B1B2B3B4ui311310A11928A274105A3vj0112B1B2B3B4ui311310A11928A274105A3vj01128-37位势表2989-3-2)vu(cjiijij检验数B1B2B3B4ui311310A11928A274105A3vj01128-37检验数表121-1101224=-1＜0，当前方案不是最优方案。二、调运方案的调整pqijj,i)(min0xpq为换入变量=min{1，3}=1从(p,q)空格开始画闭回路，其它转角点都是填有运量的方格，并从(p,q)空格开始给闭回路上的点按+1，-1，+1，-1编号，-1格的最小运量为调整量。换出变量销地产地B1B2B3B4产量A1A2A3364(+1)…┇1(-1)……3(-1)┇…(+1)3749销量3656运价851186zz2401新的调运方案为：销地产地B1B2B3B4产量A1A2A3365213749销量3656B1B2B3B4产量A1527A2314A3639销量3656需供B1B2B3B4uiA10210A2218A39125Vj-7-1-70713491110231085