运输问题表上作业法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,7.4 表上作业法,一、,表上作业法迭代步骤,1,按某种规则找出一个初始基可行解；,2,对现行解作最优性判断，即求各非基变量的检验数，判别是否达到最优解，如已是最优解，则停止计算，如不是最优解，则进行下一步骤；,3,在表上对初始方案进行改进，找出新的基可行解，再按第二步进行判别，直至找出最优解。,1,确定初始,方案,(初 始,基本可行解),改进调整,（换基迭代）,否,判定是否,最 优？,是,结 束,最优方案,图 1运输问题求解思路图,2,二、初始基本可行解的确定,例2：甲、乙两个煤矿供应A、B、C三个城市用煤，各煤矿产量及各城市需煤量、各煤矿到各城市的运输单价见表所示，求使总运输费用最少的调运方案。,3,例题有关信息表,450,200,150,100,日销量,（需求量）,250,75,65,80,乙,200,100,70,90,甲,日产量,（供应量）,C,B,A,运距 城市,煤矿,4,例题 数学模型,5,（1）最小元素法：从运价最小的格开始，在格内的标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。,6,调 销地,运,量,产地,B,1,B,2,B,3,产 量,A,1,90,X,11,70,X,12,100,X,13,200,A,2,80,X,21,65,X,22,75,X,23,250,销 量,100,150,200,450,用最小元素法确定初始调运方案,150,100,100,100,100,100,100,7,得到初始调运方案为：,x,11,=100，x,13,=100，x,22,=150，x,23,=100,8,（,2）西北角法,不是优先考虑具有最小单位运价的供销业务，而是优先满足运输表中西北角（左上角）上空格的供销要求,9,调 销地,运,量,产地,B,1,B,2,B,3,产 量,A,1,90,X,11,70,X,12,100,X,13,200,A,2,80,X,21,65,X,22,75,X,23,250,销 量,100,150,200,450,用西北角法确定初始调运方案,100,100,100,50,50,200,200,10,得到初始调运方案为：,x,11,=100，x,12,=100，x,22,=50，x,23,=200,11,三、,最优性检验,根据最小元素法或西北角法求得运输问题的初始基可行解之后，按照表上作业法的第二步，下面需对这个解进行最优性判别，看它是否为本运输问题的最优解.,12,、闭回路法,思路：要判定运输问题的初始基可行解是否为最优解，可仿照一般单纯形法，检验这个解的各非基变量（对应于运输表中的空格）的检验数。,检验数：,运输问题中非基变量（对应于空格）的检验数定义为给某空格增加单位运量导致总费用的增加量。,如果有某空格（,i,、B,j,）的检验数为负，说明将X,ij,变为基变量将使运输费用减少，故当前这个解不是最优解。若所有空格的检验数全为非负，则不管怎样变换，均不能使运输费用降低，即目标函数值已无法改进，这个解就是最优解。,13,闭回路：在给出的调运方案的运输表上，从一个空格（非基变量）出发，沿水平或垂直方向前进，只有碰到代表基变量的数字格才能向左或向右转,90,继续前进，直至最终回到初始空格而形成的一条回路。,从每一空格出发，一定可以找到一条且只存在唯一一条闭回路,。,14,以,x,ij,空格为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的每个折点依次编号；,非基变量,x,ij,的检验数：,现在，在,用最小元素法确定例2初始调运方案的基础上，,计算非基变量X,12,的检验数：,=（闭回路上奇数次顶点运距或运价之和）-（闭回路上偶数次顶点运距或运价之和）,15,调 销地,运,量,产地,B,1,B,2,B,3,产 量,A,1,90,X,11,70,X,12,100,X,13,200,A,2,80,X,21,65,X,22,75,X,23,250,销 量,100,150,200,450,100,100,100,150,初始调运方案中以X,12,(X,21,)为起点的闭回路,16,非基变量X,12,的检验数：,非基变量X,21,的检验数：,=（c,12,+c,23,）-（c,13,+c,22,）,=70+75-（100+65）=-20，,=（c,21,+c,13,）-（c,11,+c,23,）,=80+100-（90+75）=15。,经济含义,：在保持产销平衡的条件下，该非基变量增加一个单位运量而成为基变量时,目标函数值的变化量,。,17,2、对偶变量法（位势法）,检验数公式：,分别表示前m个约束等式对应的对偶变量；,分别表示后n个约束等式对应的对偶变量。,18,初始调运方案对偶变量对应表,调 销地,运,量,产地,B,1,B,2,B,3,产 量,A,1,90,X,11,70,X,12,100,X,13,200,A,2,80,X,21,65,X,22,75,X,23,250,销 量,100,150,200,450,对偶变量v,j,v,1,v,2,v,3,100,100,100,150,对偶变量,u,i,u,1,u,2,19,以初始调运方案为例，设置,对偶,变量,和 ，然后构造下面的方程组：,20,在式中，令u,1,=0，则可解得v,1,=90，v,3,=100，u,2,=-25，v,2,=90，于是,12,=c,12,-（u,1,+v,2,）=70-（0+90）=-20,21,=c,21,-（u,2,+v,1,）=80-（-25+90）=15,与前面用闭回路法求得的结果相同。,21,方程组的特点：,方程个数是m+n-1=2+3-1=4个，对偶变量共有m+n=2+3=5。,初始方案的每一个基变量x,ij,对应一个方程-,所在行和列对应的对偶变量之和等于该基变量对应的运距（或运价）,：u,i,+v,j,=c,ij,；,方程组恰有一个自由变量，,可以证明,方程组中任意一个变量均可取作自由变量。,这个时候方程的解可以称为位势。,22,在式中，令u,1,=0，则可解得v,1,=90，v,3,=100，u,2,=-25，v,2,=90，于是,12,=c,12,-（u,1,+v,2,）=70-（0+90）=-20,21,=c,21,-（u,2,+v,1,）=80-（-25+90）=15,与前面用闭回路法求得的结果相同。,23,位势法计算非基变量x,ij,检验数的公式 ,ij,=c,ij,-（u,i,+v,j,）,=（闭回路上奇数次顶点运距或运价之和）-（闭回路上偶数次顶点运距或运价之和）,闭回路法计算非基变量x,ij,检验数的公式：,复习比较检验数计算的两种方法,思考：试解释位势变量的含义（提示：写出运输问题的对偶问题）,24,四、解的改进,如检验出初始解不是最优解，即某非基变量检验数为负，说明将这个非基变量变为基变量时运费会下降。根据表上作业法的第三步，需对初始方案进行改进。,25,（一）解改进的步骤为：,1,（如存在多个非基变量的检验数为负时，以最小负检验数所在空格对应的变量）为换入变量，找出它在运输表中的闭回路；,2,以这个空格为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的每个折点依次编号；,26,解的改进步骤续：,3,在闭回路的所有偶数折点中，找出运输量最小的一个折点，以该格中的变量为换出变量；,4,将闭回路上所有奇数折点的运输量都增加这一换出变量值，所有偶数折点处的运输量都减去这一数值，最终得出一个新的运输方案。,对得出的新方案再进行最优性检验，如不是最优解，就重复以上步骤继续进行调整，一直到得出最优解为止。,27,调 销地,运,量,产地,B,1,B,2,B,3,产 量,A,1,90,X,11,70,X,12,100,X,13,200,A,2,80,X,21,65,X,22,75,X,23,250,销 量,100,150,200,450,100,100,100,150,+,+,-,-,因,12,=-20，画出以x,12,为起始变量的闭回路,0,200,50,100,28,计算调整量：=Min（100，150）=100。,按照下面的方法调整调运量：,闭回路上，,奇数次顶点,的,调运量,加上,，,偶数次顶点,的调运量,减去,；闭回路之外的变量调运量不变。,得到新的调运方案：,29,调 销地,运,量,产地,B,1,B,2,B,3,产 量,A,1,90,X,11,70,X,12,100,X,13,200,A,2,80,X,21,65,X,22,75,X,23,250,销 量,100,150,200,450,34250,100,100,200,50,重复上面的步骤，直至求出最优调运方案：,30,调 销地,运,量,产地,B,1,B,2,B,3,产 量,A,1,90,X,11,70,X,12,100,X,13,200,A,2,80,X,21,65,X,22,75,X,23,250,销 量,100,150,200,450,150,50,200,50,31,结 果,最优调运方案是：,x,11,=50，x,12,=150，x,21,=50，x,23,=200,相应的最小总运输费用为：,Z,min,=9050+70150+8050+75200,=34000,32,课堂练习：,销,产,B1,B2,B3,B4,产量,A2,4,12,4,11,16,A2,2,10,3,9,10,A3,8,5,11,6,22,销量,8,14,12,14,48,33,五、几点说明,（1）、若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代中。通常取 中最小者对应的变量为换入变量；,（2）、当迭代到运输问题的最优解时，如果有某非基变量的检验数等于0，则说明该运输问题有多重最优解；,34,（3）,当运输问题某部分产地的产量和，与某部分销地的销量和相等时，在迭代过程中间有可能有某个格填入一个运量时需同时划去运输表的一行和一列，这时就出现了退化。为了使表上作业法的迭代工作能顺利进行下去，退化时应在同时划去的一行或一列中的某个格中填入0，表示这个格中的变量是取值为0的基变量，使迭代过程中基变量个数恰好为（m+n-1)个。,35,