运筹学 04 运输问题

运输模型TransportModel运输问题的表上作业法TableMethodofTP运输问题的进一步讨论

FurtherDiscussionofTP运输问题的思考题及练习题QuestionsandExercisesforTP运输问题TransportationProblem11运输模型一般的运输问题就是要解决把某种产品从若干个产地Ai(i=1,2,…,m)调运到若干个销地Bj(j=1,2,…,n)，在每个产地的供应量ai(i=1,2,…,m)、每个销地的需求量bj(j=1,2,…,n)、Ai运输到Bj的单位运价cij已知的前提下，如何确定一个运输方案，使总运价最低。2设xij为从Ai运输到Bj的产品数量，若Σai=Σbj，则称为产销平衡的运输规划问题，数学模型为minf=c11x11+…+c1nx1n+c21x21+…+cmnxmnxi1+xi2+…+xin=ai(i=1,2,…,m)x1j+x2j+…+xmj=bj(j=1,2,…,n)xij≥0(i=1,2,…,m;j=1,2,…,n)3有时运输问题的一般模型会有一些变化，如求目标函数的最大值某些运输线路的运输能力有一定限制生产地产量有所限制销售地销量有所限制总产量不等于总销量，即产销不平衡某些地方只是中转站这些问题也可以转化为平衡运输问题4对产销平衡运输问题，若用u1,u2,…,um分别表示前m个约束等式相应的对偶变量，用v1,v2,…,vn分别表示后n个约束等式相应的对偶变量，即对偶变量为Y=(u1,u2,…,um,v1,v2,…,vn)T运输问题的对偶问题可以写成maxf=a1u1+…+amum+b1v1+…+bnvnui+vj≤cij(i=1,2,…,m;j=1,2,…,n)ui,vj任意5原问题变量xj的检验数σj=cj-zj=cj-CBB-1Pj=cj-YPj变量xij的检验数σij=cij-zij=cij-YPij=cij-(u1,u2,…,um,v1,v2,…,vn)Pij=cij-(ui+vj)62运输问题的表上作业法运输问题的数学模型及其约束方程组的系数矩阵结构具有特殊性，使用表上作业法解决运输问题，比单纯形法更为简便。表上作业法的步骤：第1步：确定初始基可行解第2步：解的最优性检验第3步：解的调整，转第2步7例1：某集团公司3个工厂A1、A2、A3生产同一产品的产量、4个销售点B1、B2、B3、B4的销量及单位产品的运价如下表。试确定使总运费最低的运输方案。8第1步：确定初始基可行解最小元素法(最低运价法)步骤：运价表中找出一个最低运价(即最小元素)cij在该处确定运量xij=min(ai,bj)计算剩余产量ai’=ai-xij和剩余销量bj’=bj-xij，则出现(1)ai’=0，bj’≠0——划去第i行运价；(2)ai’≠0，bj’=0——划去第j列运价；(3)ai’=0，bj’=0——划去第i行或第j列运价重复上述，直到获得(m+n-1)个运输数量910西北角法步骤运价表中找出西北角(左上角)运价cij在该处确定运量xij=min(ai,bj)计算剩余产量ai’=ai-xij和剩余销量bj’=bj-xij，则出现(1)ai’=0，bj’≠0——划去第i行运价；(2)ai’≠0，bj’=0——划去第j列运价；(3)ai’=0，bj’=0——划去第i行或第j列运价重复上述，直到获得(m+n-1)个运输数量11伏格尔法步骤运价表中计算每行和每列最小和次小运价之差，从差值最大的行或列中找出最小运价cij在该处确定运量xij=min(ai,bj)计算剩余产量ai’=ai-xij和剩余销量bj’=bj-xij，则出现(1)ai’=0，bj’≠0——划去第i行运价；(2)ai’≠0，bj’=0——划去第j列运价；(3)ai’=0，bj’=0——划去第i行或第j列运价重复上述，直到获得(m+n-1)个运输数量12罗素法步骤运价表中找出每行和每列的最大值ui和vj，每个单元格计算λij=cij-ui-vj，找到最小值λij在该处确定运量xij=min(ai,bj)计算剩余产量ai’=ai-xij和剩余销量bj’=bj-xij，则出现(1)ai’=0，bj’≠0——划去第i行运价；(2)ai’≠0，bj’=0——划去第j列运价；(3)ai’=0，bj’=0——划去第i行或第j列运价重复上述，直到获得(m+n-1)个运输数量任意方法也能获得初始运输方案，自己思考13第2步：解的最优性检验运输问题是否达到最优，可以这样考虑：在现有运输方案基础上作一点点调整，看看总成本作如何改变。如，某运输线路上原先没有运输数量，现在增加一个单位的运输数量，成本该如何改变？为了保证数量平衡，这就要用到闭合回路思路了。14闭回路法思路选定一个空格(非基变量)，顺次从垂直和水平两个方向交替寻找闭合回路(该空格和大于零的数字构成封闭多边形，只有横直线)从空格开始，把对应运价交替相加和相减，得到的结果填入该空格，即为检验数检验数>0，方案不能调整；检验数<0，必须调整方案；检验数=0，调整与否均可15(1)A1B1处检验数闭合回路：A1B1-A1B3-A2B3-A2B1检验数：4-4+3-2=1(2)A1B2处检验数闭合回路：A1B2-A1B4-A3B4-A3B2检验数：12-11+6-5=2(3)A2B2处检验数闭合回路：A2B2-A2B3-A1B3-A1B4-A3B4-A3B2检验数：10-3+4-11+6-5=1…16运输问题是否达到最优，还可以这样考虑：所有基变量xij的检验数λij=cij-ui-vj=0，其中ui是产量所在变量，vj是销量所在变量。由于ui和vj变量总数为(m+n)个，而λij=0的方程个数是(m+n-1)，因此只要令其中的一个ui=0或者vj=0，就可以计算其他的ui和vj值。那么非基变量xij的检验数λij=cij-ui-vj就可以计算出来了。此法称为位势法。17位势法思路令第1行的u1=0，在第1行有运输数量的地方根据cij-ui-vj=0计算对应列的vj=cij-u1；其他ui和vj类推根据λij=cij-ui-vj计算每一个空格的检验数检验数>0，方案不能调整；检验数<0，必须调整方案；检验数=0，调整与否均可18(1)计算ui和vj令u1=0，则v3=c13-u1=4-0=4v4=c14-u1=11-0=11u2=c23-v3=3-4=-1u3=c34-v4=6-11=-5v1=c21-u2=2-(-1)=3v2=c32-u3=5-(-5)=10(2)计算各空格处检验数λ11=c11-u1-v1=4-0-3=1λ12=c12-u1-v2=12-0-10=2λ22=c22-u2-v2=10-(-1)-10=1λ24=c24-u2-v4=9-(-1)-11=-1λ31=c31-u1-v1=8-(-5)-3=10λ33=c33-u3-v3=11-(-5)-4=1219第3步：解的调整、检验调整原则(1)只对检验数为负的地方进行调整(2)若有多个负数检验数，则调整最小的(3)在闭合回路中进行调整检验数≥0，停止计算总成本z=12*4+4*11+8*2+2*9+14*5+8*6=24420几点说明寻求初始运输方案时，若某一格填数时需同时划去一行和一列，此时出现退化，为保证m+n-1个非空格，需在上述的行或列中填入数字0；调整运输方案时也有可能同时出现多个0，只能去掉其中一个0作为空格每一个运输方案都必须对全部空格计算检验数当检验数为负数的变量个数超过两个时，选择最小者对应的变量换入在最优解的表中，若有检验数=0，则该运输问题有无穷多最优解可以转换为运输问题，但追求目标函数最大值，用最大元素法取得初始可行解，检验数要求小于等于0213运输问题的进一步讨论至此研究的都是产销平衡的运输问题，尚有产销不平衡、带中转站的运输问题需要研究，进一步讨论的问题包括：产销不平衡的运输问题有存储费用的运输问题目标函数求最大值的运输问题有转运的运输问题22产销不平衡的运输问题总产量不等于总销量的运输问题，统称产销不平衡的运输问题。产销不平衡，存在两者情况：(1)总产量Σai大于总销量Σbj；(2)总产量Σai小于总销量Σbj产销不平衡的运输问题总体思路：转换为产销平衡的运输问题即可：(1)设定一个假想的销地bn+1=Σai-Σbj，运价为0(2)设定一个假想的产地am+1=Σbi-Σaj，运价为023例2：某部门三个工厂生产同一产品的产量、四个销售点的销量及单位运价如下表。求最低运输费的运输方案。24解答由于总产量=8+5+9=22，总销量=4+3+5+6=18，总产量>总销量，属于产大于销的产销不平衡运输问题。增加一个销地，销量b5=22-18=4；运价为0。得到产销平衡表如左表。表上作业法结果见右表。25例3：设3个化肥厂供应4个地区的农用化肥。各化肥厂年产量(万吨)、各地区年需求量(万吨)以及各化肥厂到各地区单位运价(万元/万吨)见表。试求总运费最低的化肥调拨方案。26解答总产量=50+60+50=160(万吨)；最低需求量=30+70+0+10=110(万吨)，最高需求=∞。根据现有产量，地区Ⅳ最多需求数量=160-110+10=60(万吨)，这样最高需求=50+70+30+60=210(万吨)，大于总产量，产销不平衡。假定有一家化肥厂D生产化肥，产量=210-160=50(万吨)。地区Ⅰ最低需求30万吨，不能由D提供，运价设定为M；类似，所有地区最低需求都不能由D提供。而超过最低需求的部分可以由D提供，这时表明所需数量不能满足，设定运价为0。这样得到产销平衡的运输问题(如上表)，并求得其最优解(如下表)。2728有存储费用的运输问题例4：对下表所示的运输问题，若产地有一个单位物资没运出就发生存储费用，假设3个产地单位物资存储费用分别为4、4、3；又假设产地2的物资最多运出35，产地3的物资最少运出28。试求最优运输方案。2930目标函数求最大值的运输问题例5：某农场有土地900亩，分为3类(A1,A2,A3)，计划种植3种作物(B1,B2,B3)，各类型土地面积、各作物所需面积、每种作物单位产值如表。求使农作物总产值最多的布局方案。313233有转运的运输问题中转站运输问题存在中途临时储存的设施，即中转站。这类运输问题称为转运问题(Transshipmentproblem)。建模思路从发送及接受角度考虑产地只有发送而无接受销地只有接受而无发送中转站既有发送又有接受，且发送和接受数量相等此路不通者运价为无穷大(大M表示)344运输问题的思考题及练习题判断题(概念)1、运输问题是一种LP问题，其求解结果有四种情况。2、在运输问题中，只要给出一组含(m+n-1)个非零的xij，且满足Σxij=ai(i=1,2,…,n)，Σxij=bj(j=1,2,…,n)，就可以作为一个初始基可行解。3、按最小元素法(或伏格尔法)给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路。4、当所有产地产量和销地销量均为整数值，运输问题的最优解也为整数值。5、如果运输问题单位运价表的某一行(或某一列)元素分别加上一个常数k，最优调运方案将不会发生变化。6、如果运输问题单位运价表的某一个(或某一列)元素分别乘上一个常数k，最优调运方案将不会发生变化。35运输问题的对偶问题某运输问题可以叙述如下：有n个地区需