《第三讲运输优秀课件.ppt》由会员分享，可在线阅读，更多相关《第三讲运输优秀课件.ppt（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三讲运输第1页，本讲稿共27页3.最优性检验最优性检验经济管理学院王垚第2页，本讲稿共27页l检查当前调运方案是不是最优方案的过程就检查当前调运方案是不是最优方案的过程就是最优性检验。是最优性检验。经济管理学院王垚第3页，本讲稿共27页l检查的方法：检查的方法：l计算非基变量计算非基变量（未填上数值的格，即空格未填上数值的格，即空格）的检验数的检验数（也称为（也称为空格的检验数空格的检验数），若），若检检验数验数全部全部大于等于零大于等于零，则该方案就是，则该方案就是最优最优调运方案调运方案，否则就应进行调整。，否则就应进行调整。经济管理学院王垚第4页，本讲稿共27页检验方法检验方法1：闭回
2、路：闭回路经济管理学院王垚第5页，本讲稿共27页l闭回路：闭回路：在调运方案中，从一个空格处出发，在调运方案中，从一个空格处出发，以有数字格为顶点（或拐点），沿水平或以有数字格为顶点（或拐点），沿水平或垂直连线又回到空格处所形成的回路。垂直连线又回到空格处所形成的回路。经济管理学院王垚第6页，本讲稿共27页求某个空格求某个空格(非基变量非基变量)的检验数，先要找出它在运输表上的闭回路的检验数，先要找出它在运输表上的闭回路B1B2B3B4A1A2A3闭回路的特征闭回路的特征:1.1.每个顶点都是转角点每个顶点都是转角点.2.2.每一边都是水平或垂直的每一边都是水平或垂直的.3.3.每一行每一行(
3、或列或列)若有闭回路的顶点若有闭回路的顶点,则必有两个则必有两个。4.4.闭回路的顶点闭回路的顶点，除这个空格外，其它均为填除这个空格外，其它均为填有数字的格。有数字的格。经济管理学院王垚第7页，本讲稿共27页求某个空格求某个空格(非基变量非基变量)的检验数，先要找出它在运输表上的闭回路的检验数，先要找出它在运输表上的闭回路B1B2B3B4A1A2A3闭回路的特征闭回路的特征:5.5.每个空格都唯一存在这样的一条闭回路每个空格都唯一存在这样的一条闭回路。6.6.某空格的检验数是以该空格为第一个顶点，某空格的检验数是以该空格为第一个顶点，回路的奇数顶点运价和减去其偶数顶点运价和。回路的奇数顶点运
4、价和减去其偶数顶点运价和。7.7.闭回路可以是简单的矩形，也可以是复杂的闭回路可以是简单的矩形，也可以是复杂的多边形。多边形。经济管理学院王垚第8页，本讲稿共27页注意：注意：位于闭回路上的一组变量，它们对应的运输问题约束条件的位于闭回路上的一组变量，它们对应的运输问题约束条件的系数列向量线性相关，因而在运输问题基可行解的迭代过程中，系数列向量线性相关，因而在运输问题基可行解的迭代过程中，不允许出现全部顶点由填有数字的格构成的闭回路。不允许出现全部顶点由填有数字的格构成的闭回路。这就是说，在确定运输问题的基可行解时，除要求这就是说，在确定运输问题的基可行解时，除要求非零变非零变量的个数为量的个
5、数为(m(mn n1)1)个个外，还要求外，还要求运输表中填有数字的格不构运输表中填有数字的格不构成闭回路成闭回路。经济管理学院王垚第9页，本讲稿共27页 下面的折线构成的封闭曲线连接的顶点变量哪些不可能下面的折线构成的封闭曲线连接的顶点变量哪些不可能下面的折线构成的封闭曲线连接的顶点变量哪些不可能下面的折线构成的封闭曲线连接的顶点变量哪些不可能是闭回路？为什麽？是闭回路？为什麽？是闭回路？为什麽？是闭回路？为什麽？（a）（b）（c）（d）（e）表表中中的的折折线线构构成成一一条条封封闭闭曲曲线线，且且所所有有的的边都是边都是水平水平或或垂直垂直的的 表表中中的的每每一一行行和和每每一一列列由
6、由折折线线相相连连的的闭闭回回路的顶点路的顶点只有两个只有两个经济管理学院王垚第10页，本讲稿共27页经济管理学院王垚第11页，本讲稿共27页以以某某一一空空格格(非非基基变变量量)为为顶顶点点，寻寻找找一一其其他他顶顶点点均均为为数数字字格格的的闭闭回回路路（此此闭闭回回路路存存在在且且唯一）唯一）。经济管理学院王垚第12页，本讲稿共27页在在此此闭闭回回路路上上，已已空空格格出出发发(起起点点编编号号为为1 1)，沿沿顺顺时时针针或或逆逆时时针针方方向向给给顶顶点点编编号号.在在闭闭回回路路上上，让让奇奇数数顶顶点点的的运运量量增增加加1 1，偶偶数数顶顶点的运量减少点的运量减少1 1，计
7、算目标函数的改变量。，计算目标函数的改变量。经济管理学院王垚第13页，本讲稿共27页l l可以证明可以证明，如果对闭回路的方向不加区别，如果对闭回路的方向不加区别，对于每一个非基变量而言，以其为起点的闭对于每一个非基变量而言，以其为起点的闭回路回路存在且唯一存在且唯一。经济管理学院王垚第14页，本讲稿共27页现在，在现在，在用最小元素法确定例用最小元素法确定例5-2初始调运初始调运方案的基础上，方案的基础上，计算非基变量计算非基变量X12的检验数的检验数：=（闭回路上奇数次顶点运距或运价之和）（闭回路上奇数次顶点运距或运价之和）-（闭回路上偶数次顶点运距或运价之和）（闭回路上偶数次顶点运距或运
8、价之和）（5-6）经济管理学院王垚第15页，本讲稿共27页调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450100100100150经济管理学院王垚第16页，本讲稿共27页非基变量非基变量X X1212的检验数：的检验数：=（c12+c23）-（c13+c22）=70+75-（100+65）=-20，经经济济含含义义：在在保保持持产产销销平平衡衡的的条条件件下下，该该非非基基变变量量增增加加一一个个单单位位运运量量而而成成为
9、为基基变变量量时时目目标函数值的变化量标函数值的变化量。经济管理学院王垚第17页，本讲稿共27页调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450100100100150经济管理学院王垚第18页，本讲稿共27页非基变量非基变量X21的检验数：的检验数：=（c21+c13）-（c11+c23）=80+100-（90+75）=15。经经济济含含义义：在在保保持持产产销销平平衡衡的的条条件件下下，该该非非基基变变量量增增加加一一个
10、个单单位位运运量量而而成成为为基基变变量量时时目目标函数值的变化量标函数值的变化量。经济管理学院王垚第19页，本讲稿共27页调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450100100100150经济管理学院王垚第20页，本讲稿共27页非基变量非基变量X12的检验数：的检验数：非基变量非基变量X21的检验数：的检验数：=（c12+c23）-（c13+c22）=70+75-（100+65）=-20，=（c21+c13）-（c
11、11+c23）=80+100-（90+75）=15。经经济济含含义义：在在保保持持产产销销平平衡衡的的条条件件下下，该该非非基基变变量量增增加加一一个个单单位位运运量量而而成成为为基基变变量量时时目目标函数值的变化量标函数值的变化量。经济管理学院王垚第21页，本讲稿共27页位势法位势法位势法位势法 的基本步骤的基本步骤位势法（对偶变量法），利用对偶原理求空格（非位势法（对偶变量法），利用对偶原理求空格（非基变量的检验数）基变量的检验数）对运输表的每行、每列赋予一个对运输表的每行、每列赋予一个uiui和和vjvj，称之为位势，称之为位势，uiui和和vjvj由基变量的检验数确定：由基变量的检验数
12、确定：ij=cij-ij=cij-(ui+vj)=0(ui+vj)=0然后再求非基变量的检验数然后再求非基变量的检验数ij=cij-(ui+vj)ij=cij-(ui+vj)经济管理学院王垚解的最优性检验对偶变量法解的最优性检验对偶变量法(位势法位势法)第22页，本讲稿共27页调调 销地销地 运运 量量产地产地 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 v3100100100150位势位势变量变量 ui u1 u2经济管
13、理学院王垚令：令：u1=0v1=90v3=100u2=-25v2=90第23页，本讲稿共27页 令令u u1 1=0=0，则则可可解解得得v v1 1=90=90，v v3 3=100=100，u u2 2=-25=-25，v v2 2=90=90，于是，于是1212=c=c1212-（u u1 1+v+v2 2）=70-=70-（0+900+90）=-20=-202121=c=c2121-（u u2 2+v+v1 1）=80-=80-（-25+90-25+90）=15=15与前面用闭回路法求得的结果相同。与前面用闭回路法求得的结果相同。经济管理学院王垚第24页，本讲稿共27页调调 销地销地
14、运运 量量产地产地 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 v3100100100150位势位势变量变量 ui u1 u2经济管理学院王垚令：令：v1=0u1=90v3=10u2=65v2=0第25页，本讲稿共27页 令令u u1 1=0=0，则则可可解解得得v v1 1=90=90，v v3 3=100=100，u u2 2=-25=-25，v v2 2=90=90，于是，于是1212=c=c1212-（u u1 1
15、+v+v2 2）=70-=70-（0+900+90）=-20=-202121=c=c2121-（u u2 2+v+v1 1）=80-=80-（65+065+0）=15=15与前面用闭回路法求得的结果相同。与前面用闭回路法求得的结果相同。经济管理学院王垚第26页，本讲稿共27页位势法计算非基变量位势法计算非基变量xij检验数的公式检验数的公式 ij=cij-（ui+vj）=（闭回路上奇数次顶点运距或运价之和）（闭回路上奇数次顶点运距或运价之和）-（闭回路上偶数次顶点运距或运价之和）（闭回路上偶数次顶点运距或运价之和）闭回路法计算非基变量闭回路法计算非基变量x xijij检验数的公式：检验数的公式：复习比较检验数计算的两种方法复习比较检验数计算的两种方法经济管理学院王垚第27页，本讲稿共27页