最新运输问题(1)教学讲义PPT.ppt

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

1、运输问题(1)3-1运输问题问题的提出从m个发点A1,A2,…..Am向n个收点B1,B2…..Bn发送某种货物。Ai发点的发量为ai，Bj收点的收量为bj。由Ai运往Bj单位货物的运费为Cij，由Ai运往Bj货物的运量为Xij。问如何调配，才能使运费最省？当发点的发量总和为ai，收点的收量总和为bj相等时，称此运输问题为平衡运输问题。否则称此运输问题为非平衡运输问题。若没有特别说明，均假定运输问题为平衡的运输问题。运输问题解的结构由于ai=bj成立ij其m+n个约束方程并不是独立的。实际上只有m+n-1

2、个是独立的。即约束方程系数矩阵的秩为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，X22=2，X23=3，X24=1，

3、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）得到初始方案：X13=3，X14=1

4、，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，总运费=6*

5、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（元）差值法初始方案如下：X

6、13=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与闭合回路法相同。调整方案从一个方案调整到最优方案的过程，就是单纯形法的过程。选择检验数（一般取最大）为正值的空格所对应的变量为进基变量，在进基变量的回路中，