单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,运输问题,2.7,运输问题,一、,运输问题及其数学模型,线性规划模型、运输表,二、初始基本可行解,西北角法、最小元素法,三、非基变量的检验数,对偶变量法,四、运输表迭代,典型背景单一物资运输调度问题,设某种物品有:,m,个产地：,产量：,n,个销地：,销量：,从产地 到销地 的单位运价是 。,求,总运费最小,的调度方案。,一、运输问题及其数学模型,产销平衡问题：,总产量=总销量,产销不平衡问题：,总产量,总销量,典型背景单一物资运输调度问题,设某种物品有:,m,个产地：,产量：,n,个销地：,销量：,从产地 到销地 的单位运价是 。,求,总运费最小,的调度方案。,产销平衡问题的数学模型,产能约束,需求约束,运输问题数学模型的特点,1.,运输问题存在有限最优解,2.,运输问题约束条件的系数矩阵结构,约束条件系数矩阵每一列只有两个1，其余为0；,产销平衡问题,约束条件均为等式，且产量之和=销量之和；,约束条件的独立方程最多有,m,+,n,-1,个，即,m,n,i,m+j,其中,运输问题的对偶对偶变量与原问题检验数的关系,对产销平衡运输问题，若用,分别表示前,m,个约束等式相应的对偶变量，,用 分别表示后,n,个约束等式相应的对偶变量，即对偶变量为,平衡运输问题的对偶问题可写为,线性规划问题变量 的检验数为,对偶变量与原问题检验数的关系,变量 的检验数为,设运输问题的一个基可行解的变量为,由于基变量的检验数为零，故有,对偶变量与原问题检验数的关系,方程组含有,m,+,n,-1,个方程，,m,+,n,个变量，,可证明方程组有解，且不唯一。,求出方程组的,解,（称为,位势,）,则变量 的检验数为,对偶变量与原问题检验数的关系,求运输问题检验数的一种方法,运输问题的求解,根据运输问题的数学模型、及其约束方程组的系数矩阵结构，我们可以构造比单纯形法更为简便的求解运输问题的方法,运输表迭代方法,。,运输表迭代是应用单纯形法求解运输问题时得到的一种特殊方法。,单纯形法过程,与,运输表迭代的过程,：,（1）找出初始基可行解,（2）求各非基变量的检验数,（3）判断是否最优解,计算表中空格检验数,表上给出,m,+,n,-1,个运输量,非基变量检验数符号,换基：,（4）确定换入变量和换出变量找出新的基可行解。,（5）重复（2）,（,4,）直至求出最优解。,表上调整（闭回路调整）,（运输问题必有最优解）,停止,最优解,？,是,否,A2,A3,B2,A1,B3,B4,B1,实例分析运输问题的运输表迭代,确定初始基本可行解；计算非基变量检验数；换基迭代。,s,2,=27,s,3,=19,d,1,=22,d,2,=13,d,3,=12,d,4,=13,s,1,=14,供应量,供应地,运价,需求量,需求地,6,7,5,3,8,4,2,7,5,9,10,6,线性规划模型,供应地约束,需求地约束,运输表,二、初始基本可行解,1.,西北角法：优先满足左上角运输量,(,350),8,13,13,14,6,6,二、初始基础可行解,2.,最小元素法：优先考虑运价最低的运输量,2.,最小元素法：,2.,最小元素法：,2.,最小元素法：,2.,最小元素法,：,2.,最小元素法：,232,三、检验数的计算,对偶变量法：先确定基变量的位势，再据此计算非基变量检验数。,三、检验数的计算,对偶变量法：先确定基变量的位势，再据此计算非基变量检验数。,三、检验数的计算,对偶变量法：,三、检验数的计算,对偶变量法：,三、检验数的计算,对偶变量法：,四、运输表迭代,确定包含最大检验数所属变量（即将进基）的闭回路，找出回路中偶数顶点最小运输量，改进运输方案。,四、运输表迭代,确定包含最大检验数所属变量（即将进基）的闭回路，找出回路中偶数顶点最小运输量，改进运输方案。,四、运输表迭代,确定包含最大检验数所属变量（即将进基）的闭回路，找出回路中偶数顶点最小运输量，改进运输方案。,四、运输表迭代,确定包含最大检验数所属变量（即将进基）的闭回路，找出回路中偶数顶点最小运输量，改进运输方案。,几点说明：,1.,当大于零的检验数超过两个，选择最大者对应的变量进基；,2.,在最优解的运输表中，若有检验数=0，则该运输问题有无穷多最优解；,3.,迭代过程中，若某一格运输量增加时，其同行和同列基变量均出现零，则出现退化。为保证,m,+,n,-1,个非空格，需,保留一个基变量（取值为0）,。,例,:,求有,6,个发点和,8,个收点的最小费用运输问题。产销单位运价如下表。,分析：先建立该运输问题的数学模型,x,ij,表示从第,i,个发点到第,j,个收点的货物运输量。,记,c,ij,表示从第,i,个发点到第,j,个收点的单位货物运价，,a,i,表示第,i,个发点的最大供货量，,d,j,表示第,j,个收点的需求量。,总运输费用最少,决策变量,目标函数,约束条件,各发点运出货物量不超过其产量,各收点收到货物量等于其销量,决策变量非负限制,各产、销点的产量和销量约束，决策变量限制,线性规划模型,model,:,!6,发点,8,收点运输问题,;,sets,:,!,集合段,;,wh/w1.w6/:ai;,vd/v1.v8/:dj;,links(wh,vd):C,X;,endsets,min,=,sum,(links:C*X);,!,目标函数,;,for,(vd(J):,sum,(wh(I):X(I,J)=dj(J);,!,需求约束,;,for,(wh(I):,sum,(vd(J):X(I,J)=ai(I);,!,产量约束,;,data,:,!,数据段,;,ai=60 55 51 43 41 52;,dj=35 37 22 32 41 32 43 38;,C=6 2 6 7 4 2 9 5,4 9 5 3 8 5 8 2,5 2 1 9 7 4 3 3,7 6 7 3 9 2 7 1,2 3 9 5 7 2 6 5,5 5 2 2 8 1 4 3;,enddata,end,集合段（,Sets-endsets,）,数据段（,data-enddata,）,目标函数与约束条件段,Global optimal solution found at iteration:20,Objective value:664.0000,Variable Value Reduced Cost,X(W1,V1)0.000000 5.000000,X(W1,V2)19.00000 0.000000,X(W6,V7)3.000000 0.000000,X(W6,V8)0.000000 3.000000,20,次迭代后得到全局最优解,总费用最少为,664,最优运输方案,最优解行数太多，略,运输问题的进一步讨论,前面讨论了产销平衡的运输问题，可以采用表上作业法求解。我们还可以讨论更多类型的运输问题。如：,2.,有转运的运输问题,1.,产销不平衡的运输问题,1.,产销不平衡的运输问题,（）若总产量大于总销量,，即,假设有一个虚拟销地，其单位运费为,0,，它的销量为,：,原产大于销运输问题的数学模型,修改后产销平衡问题的数学模型,（）若总产量小于总销量，,即,假设有一个虚拟产地，其单位运费为,0,，它的产量为：,1.,产销不平衡的运输问题,仿照上述类似处理。,2.,有转运的运输问题,中间转运站产地、销地、中转站；,建模思路：从发送及接受角度考虑。,最坏计算复杂性的,LP,实例,可行域有,2,n,个顶点,，如果从,初始顶点,x,=0,开始，单纯形法需要,2,n,-1,次迭代,达到最优点。,Klee,和,Minty,在,1972,年给出的,LP,实例,练习,1,：,某石油公司设有四个炼油厂，它们生产普通汽油，并为七个销售区服务，生产和需求情况如下：,从炼油厂运往第,j,个销售区每公升汽油平均运费（单位：,千元,/,万,公升），应如何调运，使运费最省,。,