基于单纯形算法的物流配送费用优化

陈玉仙

(长沙航空职业技术学院，湖南 长沙 410124)

随着国民经济的不断发展，作为“第三方利润源”的物流业也日益兴隆。为了节省物流成本，寻找一种合适的物流配送路径成为物流业亟待解决的问题。［1－4］由于配送环境的不确定性和约束条件的复杂性，不少智能优化算法被引入作为优化配送路径的决策工具。［5－8］一般的智能寻优算法难以找到合理的优化最值，并且软件维护成本较高，因此对于一些问题并不是首选的寻优工具。而一些传统的优化方案如单纯形算法，由于其理论框架的完整性、使用的方便性和软件界面的清晰性又重新被决策者所青睐。［9－10］文章通过引入合适的单纯形算法，并应用于物流配送成本的控制中，取得了良好的优化效果。

1 单纯形算法

1.1 算法基本思想

单纯形算法是一种求解优化问题的通用算法，由美国数学家Dantzig于1947年首先提出来的。其理论根据是:待优化问题的解空间是n维向量空间中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到，顶点所对应的可行解称为基本可行解。单纯形法的基本思想是:先找出一个基本可行解，对它进行鉴别，看是否是最优解;若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别;若仍不是，则再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。

1.2 算法一般优化步骤

单纯形法的一般解题步骤可归纳如下:

1)将待优化问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。

2)若基本可行解不存在，即约束条件有矛盾，则问题无解。

3)若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。

4)按步骤(3)进行迭代，直到对应检验数满足最优性条件(这时目标函数值不能再改善)，即得到问题的最优解。

5)若迭代过程中发现问题的目标函数值无界，则终止迭代。

2 物流运输问题的模型

已知有m个生产地Ai(i=1－m)，可供应某种物资，其供应的产量分别为ai(i=1－m)。有n个销地Bj(j=1－n)，其需要量分别为bi(i=1－n)。运输单位物资的运价(单价)为Cij，Xij表示从Ai到Bj的运量。在满足各地需要的前提下，要求总运输费用最小的配送方案。

根据物流运输问题模型的建立方法，可得其对应的数学模型如下:

3 单纯形算法在物流配送中的应用

3.1 实际问题建模

本节通过一个配送实例，说明单纯形算法在其中的应用。

设某公司从三个产地A1、A2、A3将物品运往四个销地 B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表1所示，求调度方案使总配送费用最小。

表1 配送费用表(运量单位:吨;运费单位:百元)

设xij表示从Ai到Bj的运量，故可以得到模型为:

3.2 基于WinQSB软件的配送费用优化

为了直观起见，采用WinQSB软件对单纯形算法进行仿真分析以求解物流配送优化问题。过程如下:

1)输入相关数据，如图1所示:

图1 WinQSB输入数据表

2)选择元素差额法(Vogel近似法)求初始基本可行解。第一次迭代后的数据如图2所示。

图2 第一次迭代后数据表

将图2中的优化结果看成原始调度方案，可以得到如下结论:A1→B2，运量为 30;A1→B3，运量为 20;A2→B3，运量为40;A3→B1，运量为60;A3→B3，运量为 10;A3→B4，运量为10;总运费为 =30*10+20*5+40*7+60*12+10*15+10*10=1650。由图2可以得知用元素差额法得到下列一组基本可行解:

其中x表示非基变量，其他为基变量。基于图2可得出进基、出基变量和位势即对偶变量(PualPi、PualPj)，从而求出检验数。

用位势法求检验数的公式如式(5)所示。

其中I为问题基变量XB的下标集合，λij是问题的松弛变量。因此可以得出检验数:

由检验数不全部非负可知得到的基可行解不是最优解。由X42得检验数最小，而X44得运费最高得，将X44的运量作为出基变量，而将X42作为进基变量换基进行第二次迭代，通过不断地改变基变量依次得到相应的优化值。经若干次迭代后得到数据如图3所示。

图3 迭代最终表

3)验证最优解

由图3可以得知用元素差额法得到下列一组基本可行解:

其中x表示非基变量，其他为基变量。在图3中还可以看出进基、出基变量，还可以得到位势即对偶变量(PualPi、PualPj)，从而求出检验数。

因此由公式(5)可以得出检验数:

图4 最优运输方案

由以上的检验数全部非负可知，得到最优解。最终得到的最优配送方案如图4所示。

故最优配送方案如下:A1→B3，运量为50;A2→B1，运量为 20;A2→B3，运量为 20;A3→B1，运量为 40;A3→B2，运量为 20;A3→B4，运量为 20;总运费为=50*5+20*6+20*7+40*12+20*14+20*10=1470。

将最终方案与初始方案相比较，初始方案的配送费用=1650，而最终方案的配送费用=1470，可以得知最终方案配送费用比初始方案要节约180，从而优化了物流配送费用。

4 结论

文章对基于单纯形算法优化的物流配送费用问题进行了分析，说明了方案优化的步骤，通过具体实例详细论述了算法的优化过程。可以看出，单纯形算法简明扼要，每一步迭代都不断逼近最优值，在一定程度上避免了智能优化算法的优化停滞现象。算法便于编程实现，有利于推出不断成熟的软件包，也为物流行业的数字化提供了良好的软件基础平台。

［1］M.Grazia Speranza，Paul Stahly.配送物流新趋势［M］.张耀平，王明志，黄艾舟，译.北京:清华大学出版社，2004:79－92.

［2］Shad Dowlatshahi.A modeling approach to logistics in concurrent engineering［J］.European Journal of Operational Research，1999，115:59－76.

［3］Sung Hun Song，Kwan Suk Lee，Gi Sub Kim.A practical approach to solving a newspaper logistics problem using a digital map［J］.Computer ＆ Industrial Engineering，2002，43:315 －330.

［4］Lifei Cheng，Marco A.Duran.Logistics for world－ wide crude oil transportation using discrete event simulation and optimal control［J］.Computer and Chemical Engineering，2004，28:897 －911.

［5］Hongbo Li，Zengqi Sun，Badong Chen，et al.Intelligent scheduling controller design for networked control systems based on estimation of distribution algorithm［J］.Tsinghua Science＆ Technology，2008，13(1):71－77.

［6］A.Sadegheih.Optimization of network planning by the novel hybrid algorithms of intelligent optimization techniques.Energy，2009，34(10):1539 －1551.

［7］Feizhou Zhang，Xuejun Cao，Dongkai Yang.Intelligent scheduling of public traffic vehicles based on a hybrid genetic algorithm［J］.Tsinghua Science ＆ Technology，2008，13(5);625 －631.

［8］Mohammad Reza Sadeghi Moghadam，Amir Afsar，Babak Sohrabi.Inventory lot－ sizing with supplier selection using hybrid intelligent algorithm［J］.Applied Soft Computing，2008，8(4):1523 －1529.

［9］卢厚清，张永良，王宁生.求解运输问题的一种算法［J］.运筹与管理，1999，8(1):27 －33.

［10］李军，郭耀煌.物流配送车辆优化调度理论与方法［M］.北京:中国物资出版社，2001:172－182.