zr线性规划的运输问题(PPT 27)运输问题

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,课题：,工学院计算机系年10月,线性规划的运输问题,1 运输问题的类型；,运输问题,3.1,3.2,1 产销平衡运输问题的求解步骤；,课堂内容,2 产销平衡运输问题的数学模型；,一 知识点回顾,3 西北角法；,2 最小元素法；,二 新学知识点,3.2,1 沃格尔法（差值法）；,2 解的最优性检验；,3 解的改进；,方法三,沃格尔法（也称差值法）,一、编制初始调运方案,求解运输问题的表上作业法的步骤：,从运价表上，计算各行各列中次小单位运价和最小单位运价之间的差值（行罚数,h,i,，列罚数,k,j,）。优先取最大差值的行或列中最小运价位于的格来确定运输关系，直到求出初始方案。,运价表,3.2 运输问题的表上作业法,一、编制初始调运方案,求解运输问题的表上作业法的步骤：,解,3,2,3,1,3,1,1,0,1,1,2,1,2,h,i,k,j,3.2 运输问题的表上作业法,一、编制初始调运方案,求解运输问题的表上作业法的步骤：,差值法初始方案如下：X,13,=3，X,14,=1，X,21,=2，X,22,=1，X,24,=3，X,32,=3，费用=3*3+4*1+4*2+4*1+5*3+6*3=58（元）,3.2 运输问题的表上作业法,要判断一个调运方案是否已是最优，就要判断方案所对应的初始可行解是否最优。在单纯形法中，根据非基变量的检验数进行判别，若检验数中没有正值，则已求得最优，运输问题是特殊,线性规划,问题，其也可以通过检验数的判别进行最优解的检验。,3.2 运输问题的表上作业法,求解运输问题的表上作业法的步骤：,二 解的最优性检验,根据初始调运表求检验数的方法：,闭回路法,对偶变量法（位势法）,求解运输问题的表上作业法的步骤：,在初始调运方案表中，从任意空格出发，沿着纵向或横向行进，遇到,适当,填有数据的方格,90度,转弯，继续行进，总能回到原来空格。这个,封闭,的曲线称为闭回路。,闭回路的概念,3.2 运输问题的表上作业法,可以证明：每个空格对应着唯一的闭回路(略)。,1,闭回路法,3.2 运输问题的表上作业法,闭回路,3.2 运输问题的表上作业法,闭回路,3.2 运输问题的表上作业法,闭回路,3.2 运输问题的表上作业法,表中（,x,11,x,12,x,22,x,23,x,31,x,33,）,不能,构成一条闭回路，因为,x,33,不是拐角点。,X,44,X,42,非闭回路,1 闭回路法,空格X,ij,(非基变量)的检验数=第奇数次拐角点运价之和减去第偶数次拐角点运价之和,空格X,21,的检验数=,6,-5,+4,-4,=,1,3.2 运输问题的表上作业法,1,解的最优性检验方法之一,空格X,14,的检验数=,闭回路法,5,-4,+5,-4,=2,3.2 运输问题的表上作业法,2,空格X,31,的检验数=,闭回路法,6,-5,+4,-5,+8,-7,=1,3.2 运输问题的表上作业法,1,检验数都为正值,原方案不是最优解(与对偶单纯形法一致),教材中,ij,偶拐角点运价之和减去奇拐角点运价之和。,3.2 运输问题的表上作业法,闭回路法,1,1,1,5,5,2,3.2 运输问题的表上作业法,对初始调运方案,定义一组新的变量（对偶）u,i,和v,j,(i=1,2,m;j=1,2,n)对于,基变量X,ij,有：,u,i,+v,j,=C,ij,称u,i,与v,j,为相应的各行与各列的位势。,对偶变量法（,位势法）,3.2 运输问题的表上作业法,对偶变量法（,位势法）,u,1,+v,1,=,由上知：六个方程组成的方程组中含有七个变量。为了求出7个解，一般令u,1,=0。,-1,0,6,5,8,6,2,8,6,u,1,+v,2,=,5,u,2,+v,2,=,4,u,2,+v,3,=,7,u,2,+v,4,=,5,u,3,+v,4,=,对偶变量法（,位势法）,3.2 运输问题的表上作业法,空格（非基变量）的检验数 =（u,i,+v,j,)-C,ij,与闭合回路法相同。,1,1,5,5,2,1,3.2 运输问题的表上作业法,从一个方案调整到最优方案的过程，就是单纯形法的过程。,选择检验数（一般取最大）为正值的空格所对应的变量为进基变量，在进基变量的回路中，比较奇数拐角点的运量，选择一个具有最小运量的基变量作为出基变量，进基变量的运量=min(奇数拐角点的运量)。,调整方案,解的改进,3.2 运输问题的表上作业法,解的改进,选择检验数最大的（A,1,B,3,）或（A,3,B,3,）调整,最小运量=,min(2,3),=2,1,1,1,5,2,5,6,5,8,6,0,-1,2,3.2 运输问题的表上作业法,解的改进,最小运量=2,奇拐点减2,偶拐点加2,得到新的方案。,原总运费=,2,4,1,新总运费=,+5*2+4*2+7*3,=80（元）,+3*2+4*4+7*1,=70（元）,6*2+5*1+8*3,6*2+5*1+8*3,3.2 运输问题的表上作业法,解的改进,继续求检验数,6,6,5,1,5,-3,0,1,3,0,6,7,4,3.2 运输问题的表上作业法,解的改进,继续调整运量,1,3,1,选择（A2，B1）（检验数最大）调整,最小运量=,min(1,2),=1,新总运费=,+3*3+6*1+4*1,=64（元）,4*4+5*1+8*3,原总运费=,+3*2+6*2+4*6,=70（元）,4*4+5*1+8*3,3.2 运输问题的表上作业法,解的改进,选择（A1，B4）（检验数最大）调整,最小运量=,min(1,1),=1,新总运费=,+4*1+4*2+5*0,=61（元）,3*3+4*4+8*3,原总运费=,+6*1+4*2+5*1,=64（元）,3*3+4*4+8*3,1,2,0,0,1,1,-1,-6,3,6,6,3,7,1,-2,0,3.2 运输问题的表上作业法,-3,-2,-3,0,1,2,解的改进,选择（A3，B3）（检验数最大）调整,最小运量=,min(3,3,),=3,新总运费=,+3*0+4*4+5*3,=55（元）,4*2+4*4+5*0,原总运费=,+3*3+4*1+8*3,=61（元）,4*2+4*4+5*0,4,0,3,3,3,3,4,0,1,4,3.2 运输问题的表上作业法,计算检验数:空格的检验数全为非正，此时是最优解。,-2,-3,-2,-1,-3,-2,解的改进,3,3,3,4,0,1,2,最优调运方案:,最小运费,4*4+,4*2+,4*4+,5*3,55(元),X,21,=2,X,14,=4,X,22,=4,X,33,=3,知识点回顾,3.2 运输问题的表上作业法,产销平衡运输问题的表上作业法,沃格尔法,2 解的最优性检验,3 解的改进,闭回路法,对偶变量法（位势法）,确定换入的非基变量；,确定换出的基变量；,GO TO 2,1 编制初始调运方案（运输问题的初始基可行解）,最小元素法,西北角法,谢谢观看,/,欢迎下载,BY FAITH I MEAN A VISION OF GOOD ONE CHERISHES AND THE ENTHUSIASM THAT PUSHES ONE TO SEEK ITS FULFILLMENT REGARDLESS OF OBSTACLES.BY FAITH I BY FAITH,内容总结,课题：。1 沃格尔法（差值法）。方法三 沃格尔法（也称差值法）。求解运输问题的表上作业法的步骤：。从运价表上，计算各行各列中次小单位运价和最小单位运价之间的差值（行罚数hi，列罚数kj）。优先取最大差值的行或列中最小运价位于的格来确定运输关系，直到求出初始方案。3.2 运输问题的表上作业法。要判断一个调运方案是否已是最优，就要判断方案所对应的初始可行解是否最优。在单纯形法中，根据非基变量的检验数进行判别，若检验数中没有正值，则已求得最优，运输问题是特殊线性规划问题，其也可以通过检验数的判别进行最优解的检验。对偶变量法（位势法）。对偶变量法（位势法）。对偶变量法（位势法）。在初始调运方案表中，从任意空格出发，沿着纵向或横向行进，遇到适当填有数据的方格90度转弯，继续行进，总能回到原来空格。表中（x11,x12,x22,x23,x31,x33）不能构成一条闭回路，因为x33不是拐角点。j=1,2,。min(1,1),