运输问题(1)复习进程.ppt

运输问题(1)复习进程.ppt

ID:59928179

大小:905.50 KB

页数:82页

时间:2020-11-28

运输问题(1)复习进程.ppt_第1页
运输问题(1)复习进程.ppt_第2页
运输问题(1)复习进程.ppt_第3页
运输问题(1)复习进程.ppt_第4页
运输问题(1)复习进程.ppt_第5页
资源描述:

《运输问题(1)复习进程.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、运输问题(1)当发点的发量总和为ai,收点的收量总和为bj相等时,称此运输问题为平衡运输问题。否则称此运输问题为非平衡运输问题。若没有特别说明,均假定运输问题为平衡的运输问题。运输问题的数学模型:MinS=cijxijijxij=ai(i=1,2…..m)jxij=bj(j=1,2……n)ixij0(i=1,2…..m;j=1,2……n)运输问题的数学模型:其中ai0,bj0,cij0且共有m+n个约束方程。并成立:ai=bjij运输问题的图表形式运输问题解的结构由于ai=bj成立ij其m+n个

2、约束方程并不是独立的。实际上只有m+n-1个是独立的。即约束方程系数矩阵的秩为m+n-1。3-2运输问题的求解确定初始方案1西北角法(1)从图的西北角开始,填入a1与b1较小的值,b1=2,即从A1运给B1(2吨)B1已经满足,划去b1列,并将a1=4-2=2(2)向a1,b1较大方向移动一格(或向右,或向下)此时向右移动一格(A1,B2)B2需要4吨,而A1只有2吨,A1已发完,划去A1行,并把b2改成(4-2)=2。(3)继续进行(4)继续进行(5)继续进行(6)继续进行(7)得到初始方案:X11=2,X12=2,X2

3、2=2,X23=3,X24=1,X34=3,总运费=6*2+5*2+4*2+7*3+5*1+8*3=80(元)2最小元素法(1)从最小元素开始(3)即A1优先满足B33个单位,B3已经满足,划去B3列,(2)再从最小元素开始(4)即A1优先满足B41个单位,A1已经满足,划去A1行,(3)再从最小元素开始(4)即A2优先满足B12个单位,B1已经满足,划去B1列,(4)再从最小元素开始(4)即A2优先满足B24个单位,B2A2已经满足,划去B2列A2行。(4)最后把A3满足B43个单位,得到初始方案。。(5)得到初始方案:

4、X13=3,X14=1,X21=2,X22=4,X34=3总运费=3*3+4*1+4*2+4*4+8*3=61(元)3.差值法(伏格法)每次从当前运价表上,计算各行各列中两个运价之差值(行差值hi,列差值kj),优先取最大差值的行或列中最小的格来确定运输关系,直到求出初始方案。差值法初始方案如下:X13=3,X14=1,X21=2,X22=1,X24=3,X32=3,费用=3*3+4*1+4*2+4*1+5*3+6*3=58(元)西北角法得到初始方案:X11=2,X12=2,X22=2,X23=3,X24=1,X34=3,

5、总运费=6*2+5*2+4*2+7*3+5*1+8*3=80(元)最小元素法得到初始方案:X13=3,X14=1,X21=2,X22=4,X34=3总运费=3*3+4*1+4*2+4*4+8*3=61(元)西北角法得到初始方案:X11=2,X12=2,X22=2,X23=3,X24=1,X34=3,总运费=6*2+5*2+4*2+7*3+5*1+8*3=80(元)最小元素法得到初始方案:X13=3,X14=1,X21=2,X22=4,X34=3,总运费=3*3+4*1+4*2+4*4+8*3=61(元)差值法初始方案如下:

6、X13=3,X14=1,X21=2,X22=1,X24=3,X32=3,总运费=3*3+4*1+4*2+4*1+5*3+6*3=58(元)求最优方案1闭回路在初始调运方案表中,从任意空格出发,沿着纵向或横向行进,遇到适当填有数据的方格90度转弯,继续行进,总能回到原来空格。这个封闭的曲线称为闭回路。可以证明:每个空格对应着唯一的闭回路。如下表:求检验数判断一个调运方案是否已是最优,就要判断方案所对应的基础可行解是否最优。在单纯形法中,根据非基变量(空格)的检验数来判别的。若检验数中没有正值,则已求得最优。如何根据初始调运表

7、求得检验数?(1)闭回路法空格Xij的检验数=(第奇数次拐角点运价之和减去第偶数次拐角点运价之和)空格X21的检验数=6-5+4-4=1空格X14的检验数=5-4+5-4=2空格X31的检验数=6-5+4-5+8-7=1检验数都为正值,原方案不是最优解(2)位势法对初始调运方案,定义一组新的变量(对偶)ui和vj(i=1,2,…m;j=1,2,…n)对于基变量Xij有:ui+vj=Cij称ui与vj为相应的各行与各列的位势。u1+v1=6u1+v2=5u2+v2=4u2+v3=7u2+v4=5u3+v4=8有七个变量,但只

8、有六个方程,有一个自由变量,一般令u1=0u1+v1=6u1+v2=5u2+v2=4u2+v3=7u2+v4=5u3+v4=8一般令u1=0,求出解。空格(非基变量)的检验数=(ui+vj)-Cij与闭合回路法相同。调整方案从一个方案调整到最优方案的过程,就是单纯形法的过程。选择检验数(一般取最大)为正

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。