运筹学基础 课件 宋志华 第8、9章 库存优化、旅行商问题

第8章库存优化8.1库存系统8.2经典EOQ8.3分段价格EOQ8.4带有储存上限的多种货物EOQ8.5动态EOQ

8.1库存系统

大多从事产品制造、贸易、销售和修理的单位都不可避免地持有一系列实物资产的库存,以协助将来的利用和销售。一般而言,库存系统模型如图8-1所示。图8-1库存系统模型

库存优化就是寻找最优的进货策略(进货时间、进货量),以使库存系统的总费用最低。库存管理的总费用包括进货成本、持有成本、短缺代价等。

(1)进货成本包括实物资产本身的购买成本(实物资产单价可能会随着订单大小的变化而变化)和固定费用(如手续费、派人外出采购、包装和运输费用等)。

(2)持有成本需要考虑的因素包括资金的占用、空间的占用、实物资产的防护保险等产生的费用、实物资产折旧等。

(3)出货产生的费用一般只考虑短缺代价,也就是由于实物资产短缺不能满足需求而导致丧失订单或者停产等带来的机会损失。

进货策略就是要决定什么时间进多少货物。常见的进货策略有以下三种:

(1)周期性补充策略,即每隔固定的时间进货一次,进货的数量固定。

(2)库存阈值策略,即持续地检查库存数量,每当库存数量达到某个阈值的时候进货一次,进货的数量要使库存达到某个固定值。

(3)混合策略,即周期性地检查库存数量,每当库存数量达到某个阈值的时候进货一次,进货的数量要使库存达到某个固定值。

8.2经典EOQ

定义8-1经济订货数量(EconomicOrderQuantity,EOQ)是库存系统进货时应该在每笔订单中订购货物的数量,这个数量使周期性补充策略的库存系统的总费用最小。

经典EOQ对库存系统的假设如下:

(1)每次当库存水平达到特定的重新订购点b时,进货数量固定为Q,进货过程是没

有时延的;

(2)出货速率v是固定的,也就是库存以固定的速度消耗;

(3)单位数量的货物单位时间的持有成本为c1;

(4)单位数量的货物的价格为c2;

(5)每次订购都会产生一个固定费用c3。

根据假设可得进货周期为

则库存货物数量的变化如图8-2所示。

图8-2经典EOQ模型的库存数量变化曲线

例8-1假设某学校每年要使用3500升油漆,每升油漆的价格为50元,每次批量购买的固定费用为15元,每升油漆每年的持有成本为3元。请为这样的需求及价格状况制订最优的订货策略。

8.3分段价格EOQ

“量大从优”是市场经济下很常见的现象。在经典EOQ的基础上,我们考虑针对不同订货量有不同单位商品价格的分段价格EOQ问题。分段价格EOQ与经典EOQ唯一的不同在于单位商品的进货价格不再为常数,而是一个订货量Q的函数c2(Q)。

分段价格EOQ问题的假设如下:

(1)每次当库存水平达到特定的重新订购点b时,进货数量固定为Q,进货过程是没有时延的;

(2)出货速率v是固定的,也就是库存以固定的速度消耗;

(3)单位数量的货物单位时间的持有成本为c1;

(4)单位数量的货物的价格为c2(Q),是订货量Q的分段函数;

(5)每次订购都会产生一个固定费用c3。

例8-2设某学校每年要使用3500升油漆,每次订货300升以上每升价格为45元,否则为50元,每次批量购买的固定费用为15元,每升油漆每年的持有成本为3元。请为这样的需求及价格状况制订最优的订货策略。

根据已知条件,分段价格为

8.4带有储存上限的多种货物EOQ

当经典EOQ和分段价格EOQ用于求解多个货物的最优库存策略时,如果多个货物相互之间没有关联,则只需分别求解。现在考虑一种有关联的情况,也就是多个货物存放到一个仓库里,而仓库的容积是有限的,这也是一种很常见的情形。

带有储存上限的多货物EOQ问题的假设如下:

(1)每次当货物i库存水平达到特定的重新订购点bi时,进货数量固定为Qi,进货过程是没有时延的;

(2)货物i的出货速率vi是固定的,也就是库存以固定的速度消耗;

(3)单位数量的货物i单位时间的持有成本为ci1;

(4)单位数量的货物i的价格为ci2;

(5)每次订购货物i都会产生一个固定费用ci3;

(6)单位货物i占用仓库容积为si,仓库的总容积为S。

例8-3假设要确定三种货物的最优库存策略,仓库的最大可用面积为150平方米,其他参数如表8-1所示。

代入相关参数,得到数学模型:

这是一个带约束的非线性规划模型,可以使用Excel的规划工具求解。图8-3给出了所用的公式和Excel规划求解的参数。注意决策变量必须要给出一个非零的初始值,因为目标函数中决策变量出现在分母中。

图8-3例8-3的Excel规划求解

Excel求解得到的最优解如图8-4所示。因此,三种货物的订货周期分别为

图8-4例8-3的Excel规划求解得到的最优解

8.5动态EOQ

动态EOQ问题的假设如下:(1)库存优化分为多个周期,第i个周期的进货数量为Qi,进货过程是没有时延的;(2)第i个周期的货物需求量为Di;(3)单位数量的货物在第i个周期的持有成本为ci1;(4)单位数量的货物在第i个周期的价格为ci2;(5)第i个周期每笔订货的固定费用为ci3。

例8-4已知某单位年初剩余原材料为2吨,假设原材料的需求量、持有成本、价格以及进货的固定费用每个季度都各不相同,表8-2给出了未来一年各个季度的数据,请为其生产使用的原材料制订未来一年的最优库存策略。

由于总的货物的购买成本是常数,因此在规划的时候可以不予考虑。

将库存数量作为模型的状态,增加一个虚拟的起始状态和一个虚拟的结束状态,中间每个阶段考虑一个季度的库存,将问题分成5个阶段。

第1阶段:年初剩余原材料的数量为2吨,因此第1阶段的状态x1=2。

第2阶段:将第1阶段的状态作为起始状态,其对应的决策(进货数量)、到达状态(库存数量)及行动成本(持有成本+固定费用)如表8-3所示。假设每个季度的货物的需求在本季度不计算持有成本。

第3阶段:将第2阶段的状态作为起始状态,其对应的决策(进货数量)、到达状态(库存数量)及行动成本(持有成本+固定费用)如表8-4所示。假设每个季度的货物的需求在本季度不计算持有成本。

第4阶段:将第3阶段的状态作为起始状态,其对应的决策(进货数量)、到达状态(库存数量)及行动成本(持有成本+固定费用)如表8-5所示。假设每个季度的货物的需求在本季度不计算持有成本。

第5阶段:将第4阶段的状态作为起始状态,其对应的决策(进货数量)、到达状态(库存数量)及行动成本(持有成本+固定费用)如表8-6所示。假设每个季度的货物的需求在本季度不计算持有成本。第9章旅行商问题9.1TSP的构造启发式算法9.2线性规划模型9.3TSP路径构造的贪婪启发式算法9.4TSP的改进启发式算法9.5TSP的遗传算法

9.1TSP的构造启发式算法

旅行商问题(TravelingSalesmanProblem,TSP)是这样一个问题:给定一系列城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。TSP是运筹学中目前研究最为广泛的问题之一,但对于一般情况,还没有有效的解决方法。虽然TSP的复杂性未知,但60多年来,其求解方法在不断改进。表9-1显示了TSP问题的求解记录。

9.2线性规划模型

此模型的决策变量有n(n-1)个,式(9-2)和式(9-3)均有n个,连通性约束有2n-2n-2个,因此共有2n-2个约束条件,即使对于n=318这样小规模的TSP问题,也有5.34e+95个约束条件,比宇宙中的原子数量还要多!

一般来讲,通过算法构建一条可行的旅行商路径并不困难,虽然一般情况下证明是最优的很困难。在这种情况下,我们不知道找到的路径是否是最优解,但是知道这个解还不错,因此可以称之为优化解,它可能是最优的,也可能不是,并且很多情况下,可以通过解的下界大概估计优化解的优化程度。

9.3TSP路径构造的贪婪启发式算法

9.3.1最近邻算法所谓最近邻算法,就是从一个点开始逐步增加距离当前点最近的点构造出一个TSP路径。

例9-1在Matlab上实现最近邻函数,并随机生成城市节点进行验证。

使用Matlab编写最近邻函数的代码如下:

在平面上随机生成30个点,使用最近邻方法构造TSP路径的代码如下:

进行4次实验,算法构造生成的TSP路径如图9-1所示。图9-1最近邻算法生成的几个TSP路径

9.3.2插入算法

插入算法是从一个较小的圈开始,逐步将不在圈上的点插入圈上,直到扩充为一条TSP路径为止。

例9-2在Matlab上实现插入函数,并随机生成城市节点进行验证。

在平面上随机生成30个点,使用插入算法构造TSP路径的代码如下:

进行4次实验,算法构造生成的TSP路径如图9-2所示。由图可见,生成的不是最优解,而是优化解。图9-2插入算法生成的几个TSP路径

9.3.3Merger算法

9.4TSP的改进启发式算法

9.4.12opt操作

例9-3在如图9-3所示的TSP路径上,查看有没有两条边能满足交叉消除操作的条件。图9-3TSP路径的交叉消除操作

如图9-3所示,当前TSP路径上有(1,2)和(3,4)两条边在平面上是有交叉的,于是根据三角不等式可得

因此,在TSP路径上去掉(1,2)和(3,4)两条边,并增加(1,3)和(2,4)两条边,TSP路径的总长度缩短,解得到改进。

例9-4在Matlab上实现2opt函数,并随机生成城市节点进行验证。

进行实验,结果如图9-4所示,可以发现在平面上已经没有交叉了。图9-42opt操作通过消除平面交叉改进TSP路径

9.4.2k－opt操作

所谓k－opt操作,就是在TSP路径上去掉k条边,并使用另外的k条总长度更小的边将其代替并重新连接成一条可行TSP路径的操作。

如果一条TSP路径无法通过kopt操作改进,则称其为k－optimal的。如果一条TSP路径是koptimal的,则对于比k小的自然数k',这条路径一定也是k'optimal的。

如果一条TSP路径是n－optimal的,则这条TSP路径是最优的。

虽然能够验证k－optimal中的k越大,解越接近最优,但是随着k的增大,k－optimal的验证难度呈指数级增加,因此一般情况下只利用k=2,3来改进。

9.5TSP的遗传算法

9.5.1基本原理与步骤TSP路径构造的贪婪启发式算法通过贪婪规则从无到有构造一个优化解,TSP的改进启发式算法对一个已有的解进行改进,而TSP的遗传算法中上述两个算法的工作都要做,因此,也称之为元启发式算法。遗传算法计算的过程框架如图9-5所示。

图9-5遗传算法(元启发式算法)计算的过程框架

遗传算法的基本步骤如下:

步骤1:将问题的解编码为染色体,并生成初始染色体群,每个染色体代表一个解。

步骤2:进行交叉、变异、选择等操作,计算每个染色体的适应度函数值,更新染色体群。

步骤3:直到满足算法停止条件的时候,停止计算,最优的染色体代表的解即为所得的优化解,否则转步骤2。

9.5.2算法设计要点

1.解的编码

在旅行商问题中,对问题解的编码应该采用城市编号序列的方法,这样更加有利于交叉、变异等操作生成可行解,否则一个交叉之后,生成可行解的概率很低。

2.生成初始种群

所谓生成初始种群,就是生成一定数量的可行解,一般随机生成,而不太采用构造启发式算法。作为全局性算法,