运筹学结课论文
运筹学结课论文
——基于Matlab的运输问题求解方法探究
姓名:苍露露 学院:理学院 学号:2010052204 班级:信息102班 指导教师:葛仁东
摘要:运输行业的重要性随着中国经济的不断发展而快速提高,为了降低物流成本,我们有必要研究物流
运输中如何组织物资调运才能使总运输成本最少这一重要问题。而传统的手工解决方式存在着效率低、计算繁琐、数据易丢失等缺点,因此利用MATLAB软件来计算出最佳结果是很有必要的。本论文以运输问题中一个典型的案例为例阐述了基于MATLAB 的定量分析方法, 解决了运输最优方案编制中求解这一大难题,可以广泛应用于物流配送领域,对实践工作具有较强的指导意义。
关键字:Matlab 运输问题 产销不平衡问题
一、 线性规划与运输问题:
线性规划是运筹学的一个分支,它是最优化问题领域中最简单、最基本和使用最广泛的方法。在交通运输领域中,运输是一个最基本的功能,也是物流的核心问题。将同一种物资从几个不同的发货点运到另外几个不同的收货点,因为运费是单位运价和运输量的乘积,所以如何选择一个合理的运输方案,使总运费最省,这是一个很有应用价值的问题,这类问题就称为运输问题。研究物资运输过程中最优的运输方案,需要在满足各种资源限制的条件下,找到使运输总成本最少的调运方案。实践中如果建立数学模型,用线性规划的方法来解决这一问题,则可以节省大量的工作,但由于此类问题所涉及的条件变量较多, 一般的数学方法运算难度较大,结果不容易求出,而如果能有效的借助MATLAB 软件中强大的运算功能则可以得到事半功倍的效果。
二、 Matlab求解运输问题的原理:
在Matlab 中构建函数l(x)用来解决线性规划问题。众所周知,运输问题的最优解本质属于极值问题,极值有最大和最小两种,而极大值问题的求解可以转化为极小值问题, 因此在Matlab 中以求极小值为标准形式,构建的函数l(x)的具体格式如下:
[X,v,e,o,l]=l(F,A,b,m,n,M,N,P,Z)
式中:X 为问题的解向量;F 为由目标函数的系数构成的向量;A 为一个矩阵;b 为一个向量,表示线性规划中不等式约束条件,A,b 是系数矩阵和右端向量;m 和n 为线性规划中等式约束条件中的系数矩阵和右端向量;M 和N 为约束变量的下界和上界向量;P 为给定的变量的初始值;Z 为控制规划过程的参数系列;v 为优化结束后得到的目标函数值。e=0 表示优化结果已经超过了函数的估计值或者已声明的最大迭代次数,e>0 表示优化过程中变量收敛于解X,e<0 表示计算不收敛。
三、 具体问题分析:
我选择的是产销不平衡问题的求解,这里做的是产量大于销量的问题求解。
案例:某食品公司下属的A1,A2,A3,3个厂生产方便食品,要运输到B1,B2,B3,3 个销售点;公司的初始运输方案如表1所示;3 个厂到各销售点每吨方便食品的运价如表2所示。问该食品公司在满足 各销售点销售量的情况下如何安排运输使得总运费最小。 总产量为:15 + 18 +17 = 50
总销量为:18 + 12 + 16 = 46
属于 产 > 销问题。
表1:初始运输方案 (单位:t)
由表1和表2的数据可知,在初始运送方案下,总的运费为:S = 8*50 + 3*90 + 3*20 + 5*30 + 6*10 + 5*10+ 5*60 + 3*20+ 8*80= 1990元 表2:单位运价 (单位:元/t)
针对产销不平衡问题,核心方法是:将产销不平衡转换为产销平衡的情形,然后由表上作业
法进行求解。
(1)对于“产 > 销”情形:可虚拟一个销售地(库存),让多余的产量均运抵此销售地,则其销售量 = “产
-销”,同时令该虚拟的销售地的单位运价为0;(虚拟的销地)
(2)对于“销 > 产”,可虚拟一个产地,让其产量 = “销 - 产”,同时令该虚拟的产地的单位运价为0.
对于这个实际问题,虚设一销地,令其销量为产销量之差。 B4=∑ai-∑b j=(15+18+17) – ( 18+12+16 ) = 4
该列单位运价为0,即可化为产销平衡问题。如下表所示:
方案优化: 针对上述案例, 首先构建数学模型, 建立线性方程组。假设产地A1,A2,A3 向销地B1,B2,B3,B4配送的运输量分别是X1,X2, „„X12, 各变量如下表所示:
根据假设的运输条件及案例给出的限定条件,设最小运费为Smin,构建如下线性方程组: Smin = 50*X1 + 90*X2 + 20*X3 + 0*X4
+30*X5 + 10*X6 + 70*X7 + 0*X8 +60*X9 + 20*X10 + 80*X11 + 0*X12
约束条件如下:
X1+X2+X3+X4=15; X5+X6+X7+X8=18; X9+X10+X11+X12=17; X1+X5+X9=18; X2+X6+X10=12; X3+X7+X11=16; X4+X8+X12=4; Xi≥0(i=1,2,„,12) 上述方程和约束条件对应的Matlab代码如下: F = [50 90 20 0 30 10 70 0 60 20 80 0]; m = [1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1]; n = [15 18 17 18 12 16 4]; M = [0 0 0 0 0 0 0 0 0 0 0 0]; [v, e] = linprog(F, [], [], m, n, M) x = reshape(v, 4, 3); x = x'
运行后的结果为:
Optimization terminated. v =
0.0000 0.0000 15.0000 0.0000 18.0000 0.0000 0.0000 0.0000 0.0000 12.0000 1.0000 4.0000 e =
1.1600e+03
x =
0.0000 0.0000 15.0000 0.0000 18.0000 0.0000 0.0000 0.0000 0.0000 12.0000 1.0000 4.0000
由上图matlab的运行结果可知,优化后的运输方案如下表所示:
优化后的总运费为:1160元。优化后为该工厂节省运费:1990 - 1160 = 830(元)
Linprog函数介绍:
该函数用于求解线性规划问题:
其中,f, x, b, beq, lb, ub为向量, A, Aeq为矩阵。 x = linprog(f,A,b)
功能:求解最小化问题 min f*x 条件 A*x ≤ b。 x = linprog(f,A,b,Aeq,beq)
功能:求解最小化问题 min f*x 条件 A*x ≤ b Aeq*x = beq,如果没有等式就设置A = []和b = [] x = linprog(f,A,b,Aeq,beq,lb,ub)
功能:求解最小化问题 min f*x 条件 A*x ≤ b Aeq*x = beq lb ≤ x ≤ ub,如果没有等式就设置A =
[]和b = []
x = linprog(f,A,b,Aeq,beq,lb,ub,x0)
功能:求解最小化问题 min f*x 条件 A*x ≤ b Aeq*x = beq lb ≤ x ≤ ub,如果没有等式就设置A =
[]和b = []。设置初始点x0,这个选择项只是对medium-scale算法有效。默认的large-scale算法和简单的算法忽略任何初始点。
x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)
功能:最小化带有参数项的线性规划问题。其中options可以使用optimset来设置。 x = linprog(problem)
功能:对problem求最小值,其中problem是一个结构体。通过优化工具箱来创建,导入到MATLAB工
作空间。
[x,fval] = linprog(...)
功能:返回目标函数最优解x,和在x处的值:fval = f'*x. [x,fval,exitflag] = linprog(...)
功能:返回目标函数最优解x,和在x处的值:fval = f'*x,是否存在exitflag标志
[x,fval,exitflag,output] = linprog(...) Matlab中文论坛
功能:返回目标函数最优解x,和在x处的值:fval = f'*x,是否存在exitflag标志,优化解结构体output
[x,fval,exitflag,output,lambda] = linprog(...)
功能:返回目标函数最优解x,和在x处的值:fval = f'*x,是否存在exitflag标志,优化解结构
体output,拉格朗日乘子结构体lambda
结束语:
上述案例运算结果中 v为目标函数取得最小值的一组变量的值, m和 n一起构成线性规划的等式约束条件, M为变量的下界,由于是实际问题, 因此变量的下界均为 0 。e是优化结束后得到的目标函数值, 该案例最后的函数值为 229( 元) , 通过优化, 最后运输方案的总费用比该公司初始方案减少运费 116元,有效地优化了配送路线, 为公司节省了大量的资源。在物流运输定量分析过程中借助 MATLAB这一软件可应用于较为复杂的物流运输配送系统的分析,是一种比较理想的物流定量分析工具。
参考文献
[1] 中投顾问.中投顾问2009-2012年中国公路运输行业投资分析及前景预测报告[M].2009年4月. [2] 胡运权,郭耀煌.运筹学教程(第三版)[M]. 北京:清华大学出版社,2007年4月.
[3] 诸洪生,杜增吉,阎金华等.MATLAB7.2优化设计实例指导教程[M].北京:机械工业出版社,2007年3月.
[4] 宋兆基,徐流美等.MATLAB6.5在科技计算中的应用[M].北京:清华大学出版社,2005年1月.