您好,欢迎访问三七文档
第1页•运输问题的典例•运输问题的数学模型•求解方法——表上作业法第三章运输问题特殊的线性规划第2页•运输问题的典例•运输问题的数学模型•求解方法——表上作业法第三章运输问题特殊的线性规划第3页运输问题的典例例1.某食品公司经销的主要产品之一是糖果.它下面设有三个加工厂,每天的糖果产量分别为:A1-7t,A2-4t,A3-9t.该公司把这些糖果分别运往四个地区的门市销售,各地区每天的销售量分别为:B1-3t,B2-5t,B3-6t.已知从每个加工厂到各销售门市部每吨的运价如表3-1所示,问该食品公司应如何调运,在满足各门市部销售需要的情况下,使得总的运费支出为最少.8291A251047A3103113A1B4B3B2B1门市部加工厂表3-1单位:元/t第4页运输问题的一般提法现有一批货物,从m个供应地运往n个销售地,Ai(i=1,‥‥,m)处有货物aj吨,Bj(j=1,‥‥,n)处需货物bj吨,已知从Ai到Bj的运价为cij元/吨.问如何安排,既可以满足各销地需要,又使总费用最小?第5页A1A2Am︰︰B1B2Bn︰︰a1a2am︰︰b1b2bm︰︰运输问题的框图表示供应量需求地供应地需求量运价xij第6页产销平衡表运输问题的数学模型第7页单位运价表运输问题的数学模型第8页运输表(运价,运量)1B2BnB1A1a11x12xnx12A2a21x22xnx2mA2mc11c12cnc121c22cnc21mcmncma1mx2mxmnx1b2bnbnjjbmiia11销量产量销地产地产销平衡条件下第9页设xij为从产地Ai运往销地Bj的物资数量(i=1,…m;j=1,…n)从Ai运出的物资总量应等于Ai的产量ai,xij应满足:miaxnjiij,,2,11运到Bj的物资总量应该等于Bj的销量bj,xij还应满足:mijijnjbx1,,1运输问题的数学模型第10页总运费为:11minmnijijijzcx运输问题的数学模型第11页njmixnjbxmiaxtsxczijmijijnjiijminjijij,,1;,1,0,,1,,1..min1111minjjiba11产销平衡条件运输问题的数学模型第12页1.约束条件都是等式约束minjjiba112.总产量=总销量产销平衡的运输问题的特点与性质第13页3.系数矩阵是一个结构特殊的稀疏矩阵将约束方程组展开约束方程组共包含m×n个变量,(m+n)个约束条件产销平衡的运输问题的特点与性质第14页系数矩阵A:mnmmnnxxxxxxxxx,,,,,,,,,;,,,212222111211111111111111111111m行n行第15页矩阵的元素均为1或0;每一列只有两个元素为1,其余元素均为0;将矩阵分块,特点是:前m行构成m个m×n阶矩阵,而且第k个矩阵只有第k行元素全为1,其余元素全为0(k=1,…,m);后n行构成m个n阶单位阵。A的秩为m+n-10110ijimjPeemnmmnnxxxxxxxxx,,,,,,,,,;,,,212222111211111111111111111111m行n行为什么?第i行第m+j行第16页•运输问题的典例•运输问题的数学模型•求解方法——表上作业法第三章运输问题特殊的线性规划第17页•运输问题的典例•运输问题的数学模型•求解方法——表上作业法第三章运输问题特殊的线性规划第18页表上作业法作业表(产销平衡表):将运输问题的有关信息表和决策变量——调运量结合在一起构成“作业表”(产销平衡表)。第19页运输问题的典例1B2B3B4B1A2A3A1023206563销量95634748292171011433产量销地产地填有数字的格:对应运输问题解中的基变量取值,这里为3+4-1=6个空格:对应解中非基变量第20页表上作业法的基本思想是:先设法给出一个初始方案(如典例所示),然后根据确定的判别准则对初始方案进行检查、调整、改进,直至求出最优方案。表上作业法和单纯形法的求解思想完全一致,但是具体作法更加简捷。表上作业法第21页确定初始方案(初始基可行解)改进调整(换基迭代)否判定是否最优?是结束最优方案——求解思路图表上作业法第22页1.最小元素法2.沃格尔(Vogel)法(一)初始方案的给定给定初始方案的方法很多(如前例),一般来说,希望方法简便易行,并能给出较好的方案。减少迭代次数。这里介绍第23页1.最小元素法基本思想:就近供应,即优先考虑单位运价最小(或运距最短)的供销业务,最大限度地满足其供销量。销地产地产量311310719284741059销量3656203-3-31-1-1-4-4-6-66433-3-3-3-31B2B3B4B1A2A3A第24页销地产地产量311310719284741059销量365620316433Z=4*3+3*10+3*1+1*2+6*4+3*5=861B2B3B4B1A2A3A第25页最小元素法的说明退化现象:部分产量和=部分销量和在迭代过程中,可能出现一行和一列同时被划去。第26页销地产地产量31145777384121069销量36562034-4-4-1-1-6-6616-3-3-6-61B2B3B4B1A2A3A0为使迭代过程中基变量的个数恰好为(m+n-1)个,应在同时划去的一行或一列中的某个格中填入数字0,表示这个格中的变量是取值为0的基变量。以便当做有数字的格看待。第27页销地产地产量31145777384121069销量365620346161B2B3B4B1A2A3A0(一)初始方案的给定第28页基本思想:优选考虑最大差额(最小运价优势)方案行(列)差额(罚数)=次小运价系数-最小运价系数2.沃格尔(Vogel)法(差额法)行罚数列罚数1B2B3B4B1A2A3A1023206563销量95474891710113产量销地产地1B2B3B4B1A2A3A0112513()6220071312121162()33()521108()第29页1B2B3B4B1A2A3A1023206563销量95474891710113产量销地产地1B2B3B4B1A2A3A633521一般当产销地数量不多时,(Vogel)法给出的初始方案有时就是最优方案。沃格尔法Z=5*3+2*10+3*1+1*8+6*4+3*5=85最小元素法Z=4*3+3*10+3*1+1*2+6*4+3*5=8685第30页30练习.求下表给出的运输问题的初始基本可行解.B1B2B3B4产量A14104420A2773815A31210615销量510251050(一)初始方案的给定第31页31销地产地B1B2B3B4aiA14104420A2773815A31210615销量5102510505100151010(一)初始方案的给定第32页32BjAiB1B2B3B4aiA14104420A2773815A31210615bj5102510505100151010(一)初始方案的给定第33页最小元素法或Vogel法给出的是一个运输问题的基可行解,需要通过最优性检验判别该解得目标函数值是否最优,当为否时,应进行调整得到优化.(二)最优性检验与方案的调整基本思想:计算非基变量(未填上数值的格,即空格)的检验数(也称为空格的检验数),若全部大于等于零,则该方案就是最优调运方案,否则就应进行调整。1.闭回路法2.对偶变量法(位势法)第34页在已给出的初始调运方案的运输表上从一个代表非基变量的空格出发,沿水平或垂直方向前,只有遇到代表基变量的填入数字的格才能向左或右转90度(当然也可以不改变方向)继续前进,这样继续下去,直至回到出发的那个空格,由此形成的封闭折线叫做闭回路。运输问题中的闭回路注意:由于任意非基变量均可表示为基向量的唯一线性组合,因此通过任一空格可以找到唯一的闭回路第35页x25x23B1B2B3B4B5A1A2A3x35A4x43x11x12x31x42表中闭回路的变量集合是{x11,x12,x42,x43,x23,x25,x35,x31}共有8个顶点,这8个顶点间用水平或垂直线段连接起来,组成一条封闭的回路。运输问题中的闭回路第36页将如下表中6个顶点间用水平或垂直线段连接起来,组成一条封闭的回路。1B2B3B4B1A2A3A1023206563销量95346748191371034113产量销地产地(A2,B1),(A3,B2)无法连入闭回路中运输问题中的闭回路孤立格是指在所在行或列中唯一出现的变量。孤立格一定不会成为闭回路的顶点第37页目的:计算解中各非基变量(空格)的检验数基本思路:1.对于代表非基变量的空格(其调运量为零),把它的调运量调整为1;2.由于产销平衡的要求我们必须对这个空格的闭回路的顶点的调运量加上或减少1(可行条件);3.计算出由这些变化给整个运输方案的总运输费带来的变化,这里称之为检验数。如果所有代表非基变量的空格的检验数也即非基变量的检验数都大于等于零,则已求得最优解,否则进行方案调整(后续)闭回路法求检验数ijijkkxzz)()1()()1(,1kkijijzzx则若第38页1B2B3B4B1A2A3A23206563销量9544113710产量销地产地64333同理可以找出所有空格(即非基变量)的检验数。+1-1+1-1总运费变化=11131231即此新可行解较原来解运费增加1元闭回路法求检验数第39页闭回路法求检验数1B2B3B4B1A2A3A23206563销量9544113710产量销地产地6433-1+1-1+1-1+1总运费变化=3110122224332;1;1;12;7510321107约定作为起始顶点的非基变量为第一个奇数次顶点,相邻顶点为偶次顶点,其它顶点依次排列,那么,该非基变量xij的检验数:ij=(闭回路上奇数次顶点运价之和)-(闭回路上偶数次顶点运价之和)第40页-11A21210A321A1B4B3B2B1销地产地检验数表闭回路法求检验数当至少有一个非基变量的检验数是负值时,说明作业表上当前的调运方案不是最优的,应进行调整。第41页闭回路法求调整方案选一个非基变量变为基变量进基选一个基变量变为非基变量离基反映在运输表上就是要选一个空格填上大于0的数选择入基的原则是:}0,min{ijijkl从绝对值最大的负检验数格(k,l)出发第42页闭回路法求调整方案-11A21210A321A1B4B3B2B1销地产地检验数表(A2,B4)为起点作一条除该空格外其余顶点均为有数字格组成的闭回路第43页闭回路法求调整方案(A2,B4)为起点作一条出该空格外其余顶点均为有数字各组成的闭回路1B2B3B4B1A2A3A206563销量941374产量销地产地633调运方案(最小元素法得到)+1-1+1-1调整量=min{3,1}=1离基?在这条闭回路上,在保持产销平衡的条件下对偶数顶点格子的运量做最大可能的调整第44页闭回路法求调整方案(A2,B4)为起点作一条出该空格外其余顶点均为有数字各组成的闭回路1B2B3B4B1A2A3A206563销量94375产量销地产地632调运方案(最小元素法得到)1调整量=min{3,1}=1第45页4.在作业表上从绝对值最大的负检验数格(k,l)出发,即xkl为起始变量作出闭回路。5.以空格(k,l)为第一个奇数顶点,沿闭回路的顺(或逆)时针方向依次对顶点编号。6.在闭回路上的所有偶数顶点中,找出运输量最小的格子,以该格对
本文标题:运输问题的典例
链接地址:https://www.777doc.com/doc-239349 .html