第三讲运输精选文档.ppt

《第三讲运输精选文档.ppt》由会员分享，可在线阅读，更多相关《第三讲运输精选文档.ppt（27页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第三讲运输本讲稿第一页，共二十七页3.最优性检验经济管理学院王垚本讲稿第二页，共二十七页l检查当前调运方案是不是最优方案的过程就是最优性检验。经济管理学院王垚本讲稿第三页，共二十七页l检查的方法：l计算非基变量（未填上数值的格，即空格）的检验数（也称为空格的检验数），若检验数全部大于等于零，则该方案就是最优调运方案，否则就应进行调整。经济管理学院王垚本讲稿第四页，共二十七页检验方法1：闭回路经济管理学院王垚本讲稿第五页，共二十七页l闭回路：在调运方案中，从一个空格处出发，以有数字格为顶点（或拐点），沿水平或垂直连线又回到空格处所形成的回路。经济管理学院王垚本讲稿第六页，共二十七页求某个空格(非

2、基变量)的检验数，先要找出它在运输表上的闭回路B1B2B3B4A1A2A3闭回路的特征:1.每个顶点都是转角点.2.每一边都是水平或垂直的.3.每一行(或列)若有闭回路的顶点,则必有两个。4.闭回路的顶点，除这个空格外，其它均为填有数字的格。经济管理学院王垚本讲稿第七页，共二十七页求某个空格(非基变量)的检验数，先要找出它在运输表上的闭回路B1B2B3B4A1A2A3闭回路的特征:5.每个空格都唯一存在这样的一条闭回路。6.某空格的检验数是以该空格为第一个顶点，回路的奇数顶点运价和减去其偶数顶点运价和。7.闭回路可以是简单的矩形，也可以是复杂的多边形。经济管理学院王垚本讲稿第八页，共二十七页注

3、意：位于闭回路上的一组变量，它们对应的运输问题约束条件的系数列向量线性相关，因而在运输问题基可行解的迭代过程中，不允许出现全部顶点由填有数字的格构成的闭回路。这就是说，在确定运输问题的基可行解时，除要求非零变量的个数为(mn1)个外，还要求运输表中填有数字的格不构成闭回路。经济管理学院王垚本讲稿第九页，共二十七页 下面的折线构成的封闭曲线连接的顶点变量哪些不可能是闭下面的折线构成的封闭曲线连接的顶点变量哪些不可能是闭回路？为什麽？回路？为什麽？（a）（b）（c）（d）（e）表中的折线构成一条封闭曲线，且所有的边都是水平或垂直的 表中的每一行和每一列由折线相连的闭回路的顶点只有两个 经济管理学院

4、王垚本讲稿第十页，共二十七页经济管理学院王垚本讲稿第十一页，共二十七页以某一空格(非基变量)为顶点，寻找一其他顶点均为数字格的闭回路（此闭回路存在且唯一）。经济管理学院王垚本讲稿第十二页，共二十七页在此闭回路上，已空格出发(起点编号为1)，沿顺时针或逆时针方向给顶点编号.在闭回路上，让奇数顶点的运量增加1，偶数顶点的运量减少1，计算目标函数的改变量。经济管理学院王垚本讲稿第十三页，共二十七页ll可以证明，如果对闭回路的方向不加区别，对于每一个非基变量而言，以其为起点的闭回路存在且唯一。经济管理学院王垚本讲稿第十四页，共二十七页现在，在用最小元素法确定例5-2初始调运方案的基础上，计算非基变量X

5、12的检验数：=（闭回路上奇数次顶点运距或运价之和）-（闭回路上偶数次顶点运距或运价之和）（5-6）经济管理学院王垚本讲稿第十五页，共二十七页调 销地 运 量产地 B1 B2 B3 产 量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销 量 100 150 200 450100 100100 150经济管理学院王垚本讲稿第十六页，共二十七页非基变量X12的检验数：=（c12+c23）-（c13+c22）=70+75-（100+65）=-20，经济含义：在保持产销平衡的条件下，该非基变量增加一个单位运量而成为基变量时目标函数值

6、的变化量。经济管理学院王垚本讲稿第十七页，共二十七页调 销地 运 量产地 B1 B2 B3 产 量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销 量 100 150 200 450100 100100 150经济管理学院王垚本讲稿第十八页，共二十七页非基变量X21的检验数：=（c21+c13）-（c11+c23）=80+100-（90+75）=15。经济含义：在保持产销平衡的条件下，该非基变量增加一个单位运量而成为基变量时目标函数值的变化量。经济管理学院王垚本讲稿第十九页，共二十七页调 销地 运 量产地 B1 B2 B3

7、产 量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销 量 100 150 200 450100 100100 150经济管理学院王垚本讲稿第二十页，共二十七页非基变量X12的检验数：非基变量X21的检验数：=（c12+c23）-（c13+c22）=70+75-（100+65）=-20，=（c21+c13）-（c11+c23）=80+100-（90+75）=15。经济含义：在保持产销平衡的条件下，该非基变量增加一个单位运量而成为基变量时目标函数值的变化量。经济管理学院王垚本讲稿第二十一页，共二十七页位势法位势法 的基本步骤位

8、势法（对偶变量法），利用对偶原理求空格（非基变量的检验数）对运输表的每行、每列赋予一个ui和vj，称之为位势，ui和vj由基变量的检验数确定：ij=cij-(ui+vj)=0然后再求非基变量的检验数ij=cij-(ui+vj)经济管理学院王垚解的最优性检验对偶变量法(位势法)本讲稿第二十二页，共二十七页调 销地 运 量产地 B1 B2 B3产 量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销 量 100 150 200 450位势变量vj v1 v2 v3100 100100 150位势变量 ui u1 u2经济管理学院王

9、垚令：u1=0v1=90v3=100u2=-25v2=90本讲稿第二十三页，共二十七页 令u1=0，则可解得v1=90，v3=100，u2=-25，v2=90，于是12=c12-（u1+v2）=70-（0+90）=-2021=c21-（u2+v1）=80-（-25+90）=15与前面用闭回路法求得的结果相同。经济管理学院王垚本讲稿第二十四页，共二十七页调 销地 运 量产地 B1 B2 B3产 量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销 量 100 150 200 450位势变量vj v1 v2 v3100 10010

10、0 150位势变量 ui u1 u2经济管理学院王垚令：v1=0u1=90v3=10u2=65v2=0本讲稿第二十五页，共二十七页 令u1=0，则可解得v1=90，v3=100，u2=-25，v2=90，于是12=c12-（u1+v2）=70-（0+90）=-2021=c21-（u2+v1）=80-（65+0）=15与前面用闭回路法求得的结果相同。经济管理学院王垚本讲稿第二十六页，共二十七页位势法计算非基变量xij检验数的公式 ij=cij-（ui+vj）=（闭回路上奇数次顶点运距或运价之和）-（闭回路上偶数次顶点运距或运价之和）闭回路法计算非基变量xij检验数的公式：复习比较检验数计算的两种方法经济管理学院王垚本讲稿第二十七页，共二十七页