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