[理学]10运输问题模型.ppt

运输问题模型 杭州电子科技大学 运输问题的一般描述 运输问题的数学模型可以分以下3种情况讨论： 1. 产销平衡问题 2. 销大于产问题 产大于销问题 1.产销平衡问题的数学模型 产销平衡时， 各个产地的物资总和正好满足所有销地的需求，运输问题的数学模型为 2. 销大于产问题的数学模型 销大于产时， 各个销地的需求不一定能够得到满足，运输问题的数学模型为 2. 产大于销问题的数学模型 销大于产时， 各个销地的需求一定能够得到满足，但各个产地的物资不一定全部运走。运输问题的数学模型为 运输问题本质是一个线性规划问题 运输问题变量比较多，系数矩阵为0-1矩阵，其中大部分元素为零。计算运输问题我们有比单纯形法更好的专门求解运输问题的算法。 产销平衡运输问题的求解 定理 产销平衡运输问题一定存在最优解 。 产销平衡运输问题的Lingo模型 MODEL: sets: row/1..m/:a; arrange/1..n/:b; link(row,arrange):c,x; endsets data: a=a(1) a(2) … a(m); b=b(1) b(2) … b(n); C=c(1,1) c(1,2) … c(1,n), c(2,1) c(2,2) … c(2,n), … c(m,1) c(m,2) … c(m,n); enddata [OBJ]min=@sum(link(i,j):c(i,j)*x(i,j)); @for(row(i):@sum(arrange(j):x(i,j))=a(i);); @for(arrange(j):@sum(row(i):x(i,j))=b(j);); @for(link(i,j):x(i,j)=0;); END 产销不平衡运输问题也有类似的Lingo模型 产销平衡运输问题的初始解 1. 西北角法 在运价表的西北角选择运量和销量中的较小数作为运量（初始基变量），每确定一个初始基变量后，划去需求变成零的剩余列元素或划去运量变成零的剩余行元素。 填上x33=1后,自然少去一列(第3列),这时不要再去掉第3行。 注意到每填一个数据恰好减少一行或一列。 总共填写m+n个数据 填上去的m+n个数据为基变量 产销平衡运输问题的初始解 2. 最小元素法 选择运价表中最小运价，运量和销量中的较小数作为运量（初始基变量），每确定一个初始基变量后，划去需求变成零的剩余列元素或划去运量变成零的剩余行元素。 填上x14=4后,第4列自然被去掉 记住每填一个数据减少一行或一列。 3. 位势法求检验数 对每个基变量xij，计算ui和vj，使 ui+vj=cij 其中u1=0 再计算非基变量检验数 σij=cij-（ui+vj） σ11=-4 x11每增加一个单位，目标函数可以减少4个单位。 闭回路法调整 选x11进基，找到闭回路 x11 x14 4- x21 x24 2+ 3- 闭回路法调整 为了保证所有xij非负，x11最多增加3。 取x11=3 x11 +3 x14 4-3 x21 x24 2+3 3-3 重新计算检验数 σ22=-1 x22每增加一个单位，目标函数可以减少1个单位。 闭回路法调整 选x22进基，找到闭回路 x12 5- x14 1 + x22 + x24 5- X22最多增加5 x12 5-5 x14 1 +5 x22 + 5 x24 5-5 X22进基，x12和x24经过调整同时变成零。但是要注意只有一个变量出基。 例如：令x12出基 得调整后的运输表为： 重新计算检验数 所有非基变量检验数均非负，当前解为最优解 最优解为： X11*=3，x14*=6，x22*=5，x32*=3，x33*=4，其余xij*=0 最优目标值为 Z*=3×2+6×7+5×3+3×4+4×2=83 运输问题数学模型的应用实例 设某制造企业根据合同要求，从当年起需连续三年在年末提供3套型号规格相同的大型设备，已知该厂的生产能力及生产成本如下表所示： 生产能力与生产成本表 年度 正常生产可 加班生产可 正常生产