（系统分析与集成专业论文）库存—订货联合优化模型及算法研究.pdf

北京交通大学硕士学位论文 yf i 8 6 0 5 0 摘要 随着世界经济的迅速发展和科学技术的不断进步，现代物流对 经济贸易活动的影响与日俱增，也越来越受到人们的关注。在国际 上，物流作为新兴的服务产业被认为是国民经济发展的动脉，被视 为继原材料、劳动力之外的“第三利润源泉”。库存一订货作为物流 系统的重要组成部分，其目的是为了保证供应链运行的连续性和应付 不确定需求。通过合理的控制策略和控制方法，在保证生产的情况下， 将库存控制在合理范围内，可以减少流动资金的占用，缩短生产周期、 降低成本。 物流中心的库存成本是其成本因素中很大的一部分，传统的经 济批量模型及其他一些有关模型仅从供应方或需求方单方面考虑， 没有同时考虑双方利益。在垄断市场环境中( 或当需求方与供应方 建立了长期合作关系后) ，即需求方只在此供应商处订货的情况下， 假设供应商有优先决策权，我们建立双层规划模型来描述这种关系。 在开放的市场经济中，供应商与订货商都具有独立的行为能力，在供 应链活动中有着自己的行为策略，两者处于完全平等的地位，我们用 交叉规划模型来描述这种关系。 本文首先在第一章和第二章中简要介绍了库存一订货问题和双 层规划模型及交叉规划模型。第三章对遗传算法进行了简单的介绍。 第四章研究了及时条件下的订货策略优化模型及求解算法。第五章是 基于交叉规划的订货策略优化模型及算法研究。在大跨度的对象区域 中空间价格平衡原理是商品出行普遍遵循的运输价格规律，第六章介 绍了基于空间价格平衡的双层规划订货策略模型及算法研究。第七章 是基于n a s h 平衡的订货策略模型及算法研究。 其中第四章及时条件的订货策略优化模型打破了传统一次订货， 一次运输的模式，考虑到一次订货多次运送的情况。上层规划从供应 商的角度出发，为获得收益的最大化确定合理的货物订购单价：下层 规划从订货商的角度出发，在已知供应商价格的条件下，确定最优订 货批量和每次订货最优的运送次数，使订货商总订货费用最小。 双层规划模型描述的是具有很强局限性的经济行为人之间的主 从关系，然而在现代开放市场经济中，更多出现的是经济行为人之间 的平等互利的伙伴式协作关系，第五章中我们采用新的优化模型一交 叉规划模型来描述这种关系。交叉规划是国内学者近几年刚提出的一 孝磐竺萝、导师同意 匆全文公布 北京交通大学硕士学位论文 种数学规划，主要是用来解释经济问题。 另外，在大跨度的对象区域中空间价格平衡原理是商品出行普遍 遵循的运输价格规律，在供应链管理中确定订货策略时，可以基于此 原理考虑商品在各供应商之间的分配。上层考虑整个物流系统的利益 是指导者，下层考虑一个大跨度的区域货物的平衡分配问题为跟随 者。第六章正是基于此建立的模型。 最后我们借助n a s h 平衡和变分不等式理论建立订货策略优化模 型，并做算法研究。 关键词：订货策略，双层规划，交叉规划，遗传算法，空间价格 平衡，n a s h 平衡 靶索交通大学臻士学谴谂文 a b s t r a c t w i t ht h ed e v e l o p m e n to fe c o n o m ya n dt e c h n o l o g y ，l o g i s t i c ss y s t e m p l a y sa ni m p o r t a n tr o l eo nt r a d ea n d i st r e a t e da st h et h i 斑- p r o f i ts o u r c e b e s i d e st h el a b o ra n dr a w m a t e r i a l s e s p e c i a l l ya f t e r1 9 8 0 s w i t ht h e 如e p o f s p e c i a l i z a t i o n t h e r ec o m e s t oan e w s t a g ef o rt h er e s e a r c ho f m o d e m l o g i s t i c s 。a st h ei m p o r t a n tp a r to fl o 西s t i c ss y s t e m ，i n v e n t o r yc o s to f l o g i s t i c s c e n t e r si sa ng r e a t p e r c e n t a g e o ft h et o t a lc o s t r e a s o n a b l e i n v e n t o r y c a r lg u a r a n t e ep r o d u c tw e l l - b a l a n c e d t h e r e f o r e ，t h ep e r i o do f p r o d u c t c o u l db er e d u c e da n dt h ec o s tc o u l db ea l s ok n o c k e dd o w n t h et m d i t i o n a le c o n o m ym o d e la n do t h e rr e l a t i v em o d e l sc o n s i d e r t h ep r o b i e mo n l yf r o mt h es u p p l i e rs i d eo rf r o mt h ep u r c h a s e rs i d e ，a n d d i d n tt a k eb o t ho ft h e mi n t oa c c o u n tt o g e t h e r t h e s u p p l y c h a i n m a n a g e m e n te m p h a s i so n t h ec o m n l o n p r o f i t ，t h e r e f o r e i nm o n o p o l i z e d e c o n o m yw e u s et h eb i l e v e lm o d e lt od e s c r i b et h em l 撕o n s h i p i no p e n e c o n o m y , w ee m p l o yi n t e r a c t i o np r o g r a m m i n gt or e f l e c tt h er e l a t i o n s h i p b e t w e e nt h es u p p l i e r sa n d p u r c h a s e r s i nt h ef i r s tt w o p a r t s ，t h ei n v e n t o r y - o r d e r i n gp o l i c yo p t i m a lp r o b l e m s ， b i - l e v e l p r o g r a m m i n gm o d e l s ，i n t e r a c t i o np r o g r a m m i n g m o d e l sa r e i n t r o d u c e d a n dt h e ni nt h et h i r d p a r t b a s i cc o n c e p t sa n dn e c e s s a r y p r o p e r t i e s o fg e n e t i c a l g o r i t h ma r e d i s c u s s e d i nt h ef o u r t h p a r t w e p r e s e n tt h eo p t i m a lm o d e la n di t ss o l u t i o na l g o r i t h mf o ro r d e r i n gp o l i c y u n d e r ；u s t i n - t i m ec o n d i t i o n t h e o p t i m a l m o d e la n di t ss o l u t i o n a l g o r i t h m f o r o r d e r i n gp o l i c y b a s e do ni n t e r a c t i o np r o g r a m m i n ga r e p r o p o s e d nt h ef i f t hc h a p t e 墓i nt h el a s tt w op a r t sw eb f n gf o r w a r d 氆e o p t i m a l m o d e la n di t ss o l u t i o n a l g o r i t h m s b a s e do n s p a t i a lp r i c i n g e q u i l i b r i u ma n d t h e o p t i m a lm o d e lb a s e do nn a s he q u i l i b r i u m 。 w eb r e a kt h r o u g ht h et r a d i t i o n a lm o d e lo fo n c e o r d e r i n g o n c e t r a n s p o r t a t i o na n dc o n s i d e rt h ec o n d i t i o no fo n c eo r d e r i n gm o r et i m e s t r a n s p o r t a t i o ni nc h a p 把rf o u r c o n s i d e r i n gt h ep r o f i t so fb o t hs u p p l i e r s a n dp u r c h a s e r s ，w ea d o p ts u i t a b l e o r d e r i n gp r i c e ，o r d e r i n gb a t c ha n d d e l i v e r i n gf r e q u e n c yi nt h es u p p l yc h a i nm a n a g e m e n t i nt h i sc h a p t e r , a b i l e v e l p r o g r a m m i n g m o d e i r e p r e s e n t i n g t h ed e c i s i o n p r o b l e m o f o r d e r i n gp o l i c yu n d e rj u s t i n - t i m ec o n d i t i o ni sf i r s t l yp r o p o s e d t h e n a n ! ! 塞塞鎏查兰璧主茎簦鲨塞一 i d e ao f u s i n gg a t os o l v et h eb i - l e v e lp m g r a r n m i n gp r o b l e m i sd e s c r i b e d 研l a t $ m o r e ，w ed e s i g nt h ed e t a i l e da l g o r i t h m f i n a l l y , t h ea p p l i c a t i o no f t h em o d e la n di t sa l g o r i t h ma r ei l l u s t r a t e dw i t hap r a c t i c a le x a m p l e i nc h a p t e rf i v e ，a ni n t e r a c t i o np r o g r a m m i n gm o d e r e p r e s e n t i n gt h e d e c i s i o np r o b l e mo fo r d e r i n gp o l i c yi sf i r s t l yp r o p o s e d + t h e n w ed e s i g n t h ed e t a i l e da l g o r i t h m sb a s e do nr e l a xa l g o r i t h ma n db a r r i e rf u n c t i o n a l g o r i t h m f i n a l l y , t h ea p p l i c a t i o no ft h em o d e la n di t sa l g o r i t h m s 8 r o i l l u s t r a t e dw i t ha p r a c t i c a le x a m p l e s p a t i a lp r i c 魄e q u i l i b r i u m i st h eb a s i cr u l eo f t r a n s p o r t a t i o n c o m m o d i t i e s c o n s i d e r i n gt h i sw ep u tf o r w a r da no p t i m a lm o d e lb a s e d b i - l e v e l p r o g r a m m i n g i n c h a p t e r s i x a n dw e d e s i g n t h ed e t a i l e d a l g o r i t h m sb a s e do ng e n e t i ca l g o r i t h m s + k e yw o r d s ：o r d e r i n gp o l i c y , p r o g r a m m i n g ，g e n e t i ca l g o r i t h m s ， e q u i l i b r i u m + b i - l e v e l p r o g r a m m i n g , i n t e r a c t i o n s p a t i a lp r i c i n ge q u i l i b r i u m ，n a s h 北京交通大学硕士学位论文 1 1 选题背景 第1 章绪论 物流作为一个富有现代内涵的概念，被定义为“为了符合顾客所 需要的必要条件，所发生的从生产地到销售地的物质、服务、信息的 流动过程，以及为使保管能有效、低成本地进行而从事的计划、实施 和控制行为。”在国际上，物流作为新兴的服务产业被认为是国民经 济发展的动脉，被视为继原材料、劳动力之外的“第三利润源泉”。 特别是进入2 0 世纪8 0 年代以后，专业化分工进一步深化，对现代物 流的研究也进一步细化，世界各国的物流研究也进入了一个崭新的阶 段。相对于经济发达国家而言，中国的物流技术发展受整个经济发展 水平不高、人们对物流的认知观念没有完全形成等影响，尚处于发展 的初始阶段，如物流设施、装备技术水平较低，物流作业效率不高； 信息技术应用水平较低，物流信息系统应用滞后：物流管理水平较低， 现代化程度不高等。由于专业化、社会化程度不高，物流以及物流技 术的发展尚不能适应国民经济发展的需要。进入新的世纪后，中国已 顺利加入世界贸易组织( w t o ) ，这对中国物流产业的形成与发展带 来了机遇。2 l 世纪的中国将是信息化、网络化、标准化、智能化的社 会。在这种社会中，发展物流产业的障碍越来越少，市场机制的完善、 经济的增长、法制的健全，为物流合理化创造了良好的条件。从前几 年“物流”概念的普及，到具备“物流”意识与理念，再到大力投资 物流产业，中国物流业发展迅速。 物流活动包括多种功能如：供货商的选择、运输、仓储及设施规 划与选址，除了这些直接涉及的功能外，物流活动还影响生产、市场 销售、产品设计决策等诸多方面。库存一订货作为物流系统的重要组 成部分，其目的是为了保证供应链运行的连续性和应付不确定需求。 它包括的范围很广，既可以指生产企业为生产需要储备的原材料、生 产过程中出现的成品、半成品，也可以指批发、零售商为满足销售需 北京交通丈学硕士学垃论嶷 要惑贮冬熬游费晶。痒存燕缳迁供疲链功戆念理载一个必要步骤。不 同经营组织嚣根据他们的经营特点执行不同类型的库存决策。零售商 定期维持产成品痒移，铡造崧维持殿材料、半残品积产或晶痒存，服 务缎缓如修瑷商店可能维持大量的斑活用品库存等。根据供应链中的 不同阶段库存可分为原材料库存、在制品库存、产成品库存、废品麟 存。通常来讲，库存管理应解决这样两个闻越：仟么对候订货，订多 少货。因此，库存问题与订货问题关系密切。在众多的现代物流研究 残栗中，定镰分褥磷究较多，缺少寇藿疆究。本硕士论文力求稻定蘩 的优化方法来描述和解决现代物流发展过程中的库存问题，为提高物 渡效率、簿稳兹滚残本、瑶翻妨滚效蹙提供纂疆理论与方法支臻。冀 主要目的在于使物流决策部门或物流规划人员用尽可能少的资金，充 分发撵物流磺传款漤力，实瑷最台璎静应雳，获缮最佳经济效莱。 1 。2 研究物渡系统中库存一订货阑题的意义 鹰存是攒企业在生产经群活动中所需的备用物品。库存的存在有 其一定静必然往和目的往，童要作餍为：使念业获褥窥模经济：育韵 于物流系统的合理化 平衡供求方面的关系；预防需求和订赞周期的 不确定淫；夜禁些关键锈壤怒餐缓渖、调节的作蕉。霹存是众监管毽 中重爱的组成部分，也是关键之一。通过合理的控制策略和控制方法， 在缳诞生产懿媾嚣下，穗痒兹羟裁在会理范嚣连，双嚣胃戳减少滚麓 资金的占用，缩短生产周期、降低成本。 物流及供应链管骥孛供鬟关系始终螫穿熬令过程。霹鼗，谈翥礤 究是物流管理的一个缳重要，也是最基本的内容。库存成本鼹供应链 成本的重要缀成部分之一，般占总成本豹3 0 以上，因此，要想优 化整个物流系统，就必须先做好库存管理。 库存费用是总的物流费用中重要的部分，它包括物品在保管、运 输途审静维持、缺货赞蔫。露存费用氇受英 眩费餍函索影响，耐鲡， 采购价格和逡输费率取决于订单及运输量的火小，这魑反过来又影响 库存爨弼。褒鸯垡涛浇下，当列货霹滴己翔戢为绦簿及对控翻进行蕊 量订赞时，库存决策可简单确定。 北京交通大学硕士学位论文 库存策略的制定主要依赖于对生产过程和市场行情的仔细分析， 在企业内持有库存主要有以下五个方面的作用。 ( 1 ) 使企业获得规模经济 一个企业要想实现在采购、运输和制造等物流过程方面的规模经 济，拥有一个适当的库存是必要的。大批量的订货能够使企业在众多 方面获得优势：如降低原材料的采购价格和运输费用i 降低单位产品 的制造成本：减少因缺货而形成的订单损失和信誉下降等。 ( 2 ) 平衡供求方面的关系 季节性的供给和需求使企业不得不持有库存。例如在节日期间， 产品需求量剧增，这就要求企业能够有充足的货源来迅速满足市场的 需要；另一方面，某些产品的需求在一定的时期可能相对比较平稳， 但其相应原材料的供给和需求变化较大，这同样要求企业保留适当的 原材料库存以维持生产的连续性，避开不利的价格变动。 ( 3 ) 有助于物流系统的合理化 合理的仓库选址可以带来诸多方面的便利，减少耗费在运输配送 方面的时间和费用。原材料能够从仓库中被合理地配送到各地的生产 基地，满足生产的需要；产成品能够被迅速运往仓库，然后配送到各 地满足顾客的需求。这些方面的专业化极大地节省了运输环节的费 用。 ( 4 ) 预防需求和订货周期的不确定性 由于市场需求情况的瞬息万变以及订货周期的不确定性，常常使 库存不足，从而导致缺货损失，这时库存就显得十分重要。存贮生产 所需要的原材料不仅能够保持正常生产的连续性，而且常常会在未来 原材料价格上涨或原材料短缺时赚取额外的利润。 c 5 ) 在某些关键领域起到缓冲、调节的作用 库存在整个供应链的某些关键环节起着缓冲、调节的作用，它可 以缓和由于物资供应的延迟、短缺而造成的对生产过程的冲击，可以 作为配送环节的中介，调节生产过程中因原材料、半成品的不足丽可 能发生的比例失调。 同时有效的合作机制在现代制造和配送系统中起着很重要的作 用。以确定销售价格和订货量为主要特征的联合决策策略一般是通过 薹壅塞鋈盔釜璧圭兰垒鎏塞 一一 数量摭扣枫露来实现戆。以缀济批爨( e o q ) 原理戈基礁确建订货策 略，往往还攥以数量折扣的形式反映出来，即购买不同数薰的产品其 价格优惠程度不同。对买方来说，邂过每次的订购批量，一方面可以 获得价格上的优惠，爨一方馘，可酞减少订购费用；对于察方来漉， 虽然价格的数量折扣导致销售收入的减少，却可以使企业的生产装酉已 费爱耱订单憝莲费霜簿低。鬻诧，蒂l 定台理酌良折翔为基础的订贷策 略无论对需求方还魑供应方都是有利的。 我们戋蒌遴津存 蠡题与蠢赘策海关系密翻，函踅，宥登要强先遗豁 优化技术来确定物流管理中供需双方的库存一订货问题。 1 3 库存订货问题的一般模型 簿存是众监的一颈庞大鼹昂贵的投资。髓好的库存管理能够加快 资金的周转遮度、提离资金救使鼹效率、增热投资的收益。对予意4 遗 韭来说，原材料短跌将影响警产，导蔽费盾增加，产品短缺。而库存 积压将增加仓储，积艇资金，提高成本，减少盈利。这些都反映了库 存警壤对企照豹重要穗。库存管理是物漉营璞的核心内容之，库存 的合理优化怒众多学者广泛关心的问题。库存问题缀长期研究已得出 一些嚣之有效黪模型，太嚣分嚣类：类鬻徽确定经模墅，帮模墼申 的数据皆为确定的数值；另一类叫做随机性模型，即模型中岔有随机 变量。 1 3 1 确定性库存模型 确定性条件下的库存是攒当一个对期内的产晶需求量确定以后， 稆应豁库存成本就基本上确寇了。如莱暂时不考虑缺赞成本，库存成 本由产品成本、存贮成本和订馈成本三部分织成。最缝典的订货模型 是经济订货懿囊( e o q ) 模蘩，经济订贷撤黧是存货绦持与订货相结 合使成本最低的补给订货批爨。模型成立需要以下几个假设条件：缺 爨羹鼷无穷大；兰存贮洚受零蒌重，霹戮立瑟撂裂静充：需求是连续靛、 均匀的；每次订货量不变；单位存贮赞不变。由于经济批量模型需要 4 熬塞奎堡态黧塑圭兰堡鎏窒 襁当严格麴瑕设才毙壹接斑鼹，联弘在其延 率的摸型中 妻 妻寿以下诸 多假设：不允许缺货，生产需一定时间；允许缺货( 缺赞需补充) ， 生产时间缀短：允许缺费( 震 鼹缺货) ，生产霉定时闻。不麟的 骰设模型不尽稆同。另外，为了利用特殊的购买彤势和单位亿特徼而 必须做出某些调熬，与e o q 有关的两种调整分别是：运攫费率和数 羹圣蓐据。我们常鬻掰一军辛麓蕞畜豚谓的零售价、批发价和獭厂徐，购 买同一种商品的数量不同，商品单价也不同，一般情况下购买数爨越 多，裔鑫犟份越鼹。在少鼗请嚣下，菜释藩磊袋髹供应越过限额帮分 的商品单价要提商( 钱颂遇，2 0 0 0 ) 。最近，对库存费用模型，阶段 淤耗库存模型( 时糖毒黎声玉环等，2 0 0 1 ) ，最饯孛孝辩痒襻模型( 零 弋，2 0 0 1 ) ，生产与销售模型( 刘倍斌和马良河，2 0 0 1 ) 等方面的研究 g 起了国内努学卷熬极大洪趣。 1 3 2 随机性库存模型 随机性库存模型的莺鬻特点是需求为随机的，其概率分布为已 袈，逶鬻分为需求是连续帮需求怒离散两释情况研究。奁随税滢群存 问题中，如果想让商品既不因缺货而失去销售机会，又不因滞销丽过 多投压资愈，可攥选择赞策旗主要骞三秭。第一静荣硌：定麓订赞， 但订货数麓需要根据上一个周期剩下货物的数量决定订货凝。剩下的 数蹙少，霹默多订费；剩下熬数量多，可弘少订袋蠹不订赞。第二释 策略：定点订货，襻贮降到某一确定的数爨时即订货，不张考虑问隔 的时间。这数量臻穗为订货点，每次订货豹数量不变。纂三署申策蝮： 把定期订货和定点订货综含起来的方法，隔定时间检查次存贮， 如果存贮数量高予一个数值s ，则不订货。小于5 时则订货补充存贮， 订赞量要使存贮豢达到s ，这种策路可以简称为( 乩s ) 存贮策略。存 贮繁略豹傥劣，避鬻鞋赢利麓望壤抟六枣佟为囊爨鹚稼准 钱颂邈， 2 0 0 0 ) 。 另一种更为复杂的模型是具蠢髓机霰求过程秘照规供赞时间嬲 库存模型。由于随孝兄库存模型与排队论和靛制论联系紧密，这就加大 了冀复杂性。 以往的研究模型大多只考虑了供方( 供_ 陂商或物流中心) 的利益- 两没有考虑灏方( 颗客或甥流中心) 的剩懿。两在现代物浚体系中， 顾容的需要被放瓢了首位，谯库存一订货问题中也不应例外。事实上， 某个客户的需求不饭可以由多个供成商共同满足，搿且由于每个供应 商的库存取决于客户的选耩行为，简时这种选择行为在很大程度上熟 有较高的随机性。因此，有必要以考虑客户选择行为的新模型、新方 法、瑟技术来求释鬻存一订畿联合俊纯淹嚣。 。4 论文框架 第l 章为缝论郝分，麓簧分绍了现 弋物流兹基零游提、簿存一订 货联合优化问题在物流系统中的意义、库存订货联合优化问题的一 般模趔和论文的框架。 第2 章介绍了双膳规翔与交叉规划在库存一订贷联合优化问题中 的应用。 在垄断市场经济中，我们可班怒律存一订货闻题看作一个指导者 一跟随者( l e a d e r - f o l l o w e r ) 问题，其中上游供应商是指导者( l e a d e r ) ， 订费藏碡定订赞策路懿行为楚跟隧者( f o l l o w e r ) 。上游供应髓可敬逶 过管理和决策( 比如确定货物订购单价) 来改变某个订货商的购买成 零，飙嚣彩旗订货囊瓣订货繁漆( 毙魏订货趱量) 。订货囊粼霹理露 的货物单价谶行比较，根据自己的需求特点和行为习惯来选撵订货批 量。这聋孛关系我们可以暖双鼹规划( b i 1 e v e lp r o g r a m m i n g ) 谶嚣搓述。 双层舰划模黧描述的擅断市场经济下，经济行为人之间的主从关系， 然蔼在开放的市场经济中，熨多出现骢是经漆行为人之闻的平等互剥 盼伙伴式协作关系，供应商与订货商都具有独立的 予为能力，在供应 链活动中有辫自己的行为策赂，两者处于完全平等的地位。所以研究 这群怼援鬣溺瑟静特征及箕求解方法是十分有意义酶。本论文圊时 讨论在库存管理中，供应商、订货商以各自的行为决策为基础，双方 又稳甄影璃魏订费蓑戆闯题，震交叉蕊囊( i n t e r a c t i o n p r o g r a m m i n g ) 建立数学模型。 6 j 末交通大学舔士学位论文 第3 章麓要介绍了非数值计算方法一遗传算法。 遗传算法是一种借臻生物界自然选择和进仡机制发熊起来的高 度并行、随机、自适应搜索算法。简单而离，它使用了群体搜索技术， 将释群代袭一组霹题解，遴过对警箭释群藏热选择、交叉裙变异等一 系列遗传攥作，从而产生新一代的种群，并逐步使种群进化到包含近 龟爻最优勰耱获态。 第4 津介绍及时条件下订货策略的优化模型及求解算法。 掳漉孛款及孵( j u s t - i n 。t i m e ) 篱理方式指故楚将必要熬赞穆以宓 要的数量在必要的时间送到目的地。一般来讲，供应商为取得自融利 藏躲最大化尽量掇藩货物盼订购份播，并降低订孳处理费月；订赞齑 则在供应商提供的货物订购单价的基础上选择合适的订货批量和每 次订货合疆的运送次数来降低自熙的费用。这对相互制约，相互影响 煞矛蘑俸懿何筏羁平衡支点就是本模堑要解决酶阏题。在供应商肖优 先决定权的情况下可以用双层规划模型来解决这个问题。上层规划从 供疲巍豹麓凄凄菠，必获褥寝薤鹩最大话确定合疆静货物订辫擎价； 下层规划从订货商的角度出发，在已知供应商价格的条件下，确定最 挠订货萎乏爨零每次订货最援豹运送次数，侵订货囊总订货爨舔最小。 第5 章介绍基于交叉规划的订货蘸略优化模裂及求鳃算法。 在开放的市场经济中，供应齑与订货麓都具露独立熬 亍为能力， 在供应链活动中膏着自己的行为策略，两者处于完全平等的地位。我 们用交叉规划模型来描述这种关系。供应巍的耳捶是使自放的收益缓 大，订贷祷剃是霞他们的稳费最小。我们缀常看到种商黼有所谓的 零售价和批发价，购买同种商晶的数量不周，商龆价格媳不周。 救缯凝下黥买数蘩越多，释嚣荤徐怒 氐。搿潋销定台理酶裔磊萃徐秘 订购批量熙订货策路中应解决的重娶问题，另外还揍考虑存贮费用和 运簸费霜露供应慈裙订货襄黪影噙。 第6 章介绍基于空间价格平衡的双层规划订贷策略模型及算法研 究。 空间价格平衡( s p a t i a lp r i c i n ge q u i l i b r i u m ) 问题就是豢求得满足 平嫩条件( 印需求价格等予供绘价磺船上运徐费用) 豹商品供绘徐掺、 需求价格鞠商品流鬃。如暴某个供需市场上有商品流，则需求价格等 ? j 京交暹丈学磺士学位论文 于供给徐掺麴土运滚费用；落器求价接，j 、予供绘侩楱知上遂辕费臻， 则该对供需市场没有商品流。在大跨度的对象区域中空间价格平衡原 理是蕊品出 亍普遍遂循的运输价格规律，在供应链餐理中确定订货策 略时，可以熬于此原理考虑商品在备供应商之间的分配。上层考虑熬 个物流系统的利益魑指导者，下层考虑一个大跨度的区域货物的平衡 分配闯题为鼹随者。 第7 章是基于n a s h 平衡的订货策略模烈及算法研究。 筏销懿遂镤瘦窝与订爨巍是以饕合箨兹影态存在靛，n a s h 平篱 描述的是多人非合作对策问题，本章借助n a s h 平德和变分不等式理 论磅究开教枣场经济中载订爨燕路模翌及冀法。 8 韭塞奎婆盔堂塑主堂垡丝塞 一 第2 章双层规划及交叉规划在库存 一订货联合优化问题中的应用 2 。1 双层规划模型及其在库存一订货联合优化问题 中的应用 由于实际的规划、决策问题都是庞大而异常复杂的系统，涉及各 种各样的影响因素，关系着各个部门、单位和个人的具体利益，因此 所采用的决策方法应该是多层次的系统决策方法，而不能是单一层次 的决策方法。一般而言，决策机构都是一个分级或分层次的管理机构， 在总体目标一致的前提条件下，各级都有其各自独立或相互矛盾的目 标。因此，在做出科学而系统的最终决策之前，需要综合考虑彼此之 间存在相互作用的、有其各自目标的各个层次上的部门、机构和个人 的意见，力求最终的决策能使整个系统达到最优的目的。 多层规划问题的一个重要特点就是可以应用在多层决策问题中， 多层规划使用一个分层次的结构，在各个层次上的决策者都有其各自 的目标函数，在某种程度上，本层的决策空间是出其他层次决定的。 此外，某一层次上的决策者通过特定的方法和手段影响其他各层的决 策制定，从而达到优化其自身目标函数的目的。例如，这些方法和手 段可以是控制较低层次的资源分配和使用、调整分配给各层的利益 等。在多层规划中，所有的决策者优化其自身的目标函数，而不考虑 他们的决策对其他各个层次的影响。 多层规划问题的另一个重要特点是：决策变量的控制权分别属于 各层的决策者，而在传统的单层规划中，决策者同时控制所有的决策 变量。但在政府部门的实际决策过程中，对决策变量的控制和处理并 不是同时进行的，而是采用自上而下的多层次决策方法。例如，在大 多数国家中，中央政府首先在各个省之间分配资源( 指的是广义的资 源) ，然后各个省在中央政府所分配的资源基础上，决定其各自的行 北京交通大学硕士学位论文 为、政策等。 在多层规划中，以优化自己的目标函数为目的的决策者在高层决 策者事先确定决策变量值之后，对自己能控制的决策变量进行优化， 以达到晟优目的。多层规划比单层规划具有优势，它能够明确表示不 同层次优化过程或不同决策系统之间的相互作用。 双层规划( b i - l e v e lp r o g r a m m i n g ) 问题是多层规划问题的一种特 例，其中只有两个层次，两种决策者。在垄断经济条件下，库存一订 货联合优化阅题涉及供应商与订货商的相互作用或者他们之间的联 合决策行为，是一个典型的双层决策问题，因此双层规划模型成为描 述库存一订货联合优化问题的理想工具。 2 1 1 双层规划模型的定义和特性 1 定义 一般来说，双层规划模型具有如下形式 ( p 2 1 ) ( u 2 1 ) r a i n f ( x ，y ) 1 s t c ( x ，y ) 0 其中y = y ( x ) 由下述规划求得： ( l 2 i ) m i n f ( x ，y ) y s t g ( x ，y ) 0 ( 2 1 1 ( 2 - 2 ) ( 2 3 ) r 2 - 4 ) 其中x e 川，y f 2 ，f ：e “2 j ，g ：f 点砬斗占枷， f ：e “x e “呻，g ：f 1 x e ”2 寸f 2 。 双层规划模型( p 2 1 ) 是由上层模型( u 2 1 ) 和下层模型( l 2 1 ) 组成，式( 2 i ) 一( 2 2 ) 构成上层问题，式( 2 3 ) 一( 2 4 ) 构成 下层问题。上层决策者通过设置x 的值影响下层决策者，因此限制了 下层决策者的可行约束集，上层决策者通过下层决策者的目标函数与 o 北京交通大学硕士学位论文 下层决策者相互作用。必须注意到：下层决策变量y 是上层决策变量 x 的函数，即y = y ( x ) ，这个函数一般被称为反应函数。 2 可行性和最优性 假设上层决策者控制的决策变量的集合为zce ，下层决策者 控制的决策变量的集合为y c e “，并且假设x n y = 。在双层优化 过程中，上层决策者首先选择变量x ，这样来，就会影响下层决策 者的可行策略集合。对固定的x ，下层决策者所要解决的问题变为： m i n ( f ( x ，y ) ：yix )( 2 - 5 ) s t x ，y s = ( x ，y ) ：g ( x ，y ) 0 ，g ( x ，y ) 0 )( 2 - 6 ) 下层决策者的解集属于定义如下的合理反应集( r a t i o n a lr e a c t i o n s e t ) ： 定义2 1 如果对于给定的一个点x x ，存在唯一的解y 王， 由方程( 2 - 6 ) 所定义的集合s 上，的合理反应集如下： ( - 5 ) ； x 爿，y e y ：( 墨y ) s ，f ( x , y ) = m i n ( f ( x ，y ) ：y l x ) ( 2 7 ) 进一步，对于每一个x ，如果存在一个y 使f ( x ，y ) 在所有的点 ( x ，y ) j 上唯一晟小，那么可定义如下的合理映射： y = 中r ( x )( 2 8 ) 上层决策者控制两个变量的问题变为： r a i n ( f ( x ，y ) ：( x ，y ) 盯( s ) )( 2 - 9 ) 定义2 2 如果满足歹= 。，( i ) ，这里映射中，为点i 处的合理映 射，即点y 对点x 来说就是最优的，则称这样的一对点( i ，- ) 是双层规 北京交通大学硕士学位论文 划问题( p 2 1 ) 的可行解。 定义2 3 如果( x ，y ) 满足以下两条就认为( x ，y ) 是双层规划 的最优解。 ( 1 ) ( x + ，y ) 是可行的。 ( 2 ) 对所有的( x ，y ) s ，都有： f ( x ，y ) f ( 一x ，歹) 其中：假设s 为非空有界紧集合( n o n e m p t ya n d c o m p a c t ) 。 设( x ，y ) 是双层规划的最优解，则其一阶必要条件为： ( 1 ) f ，g ，厂，g 邦是一次连续可微函数； ( 2 ) 对x e x ，下层问题( 2 3 ) 一( 2 4 ) 有唯一解： ( 3 ) 存在口e “，使得( x ，y ，肛) 是下列问题的可行解： m i n f ( x ，y ) ( 2 - 1 0 ) x ，y ，p s t g ( x ，y ) 0( 2 - 1 1 ) v y f ( x ，y ) 一肛v y g ( x ，y ) = 0( 2 - 1 2 ) 口( g ( x ，y ) ) 7 = 0( 2 - 1 3 ) g ( x ，y ) 0( 2 - 1 4 ) 口0 f 2 - 1 5 ) 这里，向量p 是下层问题的k t ( k u h n - t u c k e r ) 乘子向量。 实际上，等式( 2 1 0 ) 一( 2 1 5 ) 恰好是台理反映集盯( s ) 的一 阶必要条件。 北京交通大学硕士学位论文 3 计算复杂性 一般来说，双层规划问题的求解都是非常复杂的，原因之一就是 由于双层规划问题是一个n p - h a r d 问题。b e n - a y e d 和b l a i r ( 1 9 8 8 ) 在j e r o s l o w ( 1 9 8 5 ) 的研究基础上继续深入探讨了这一问题，指出： 即使是很简单的双层线性规划问题也是n p h a r d 问题，不存在多项式 求勰算法。双层规划的非凸性、可行域( 又称诱导域) 的不连通性及 合理反应映射的非单值性是造成双层规划问题求解异常复杂的另一 重要原因。即使上层问题和下层问题均为凸问题，整个双层问题仍然 为非凸问题的可能性非常大。而双层问题的非凸性表明：即使能找出 _ 双层问题的解，通常也只可能是局部最优解而非全局最优解。 这样，即使是对于某类双层规划存在精确算法，显然对于本文所 欲研究的库存一订货联合优化问题也是难以运用的，因此为使计算简 便易行，本文后面所采用的求解算法大都是启发式的，实际计算表明 这些启发式算法是有效的，具体内容详见后续几章。 由于双层规划问题和博弈论具有一些基本的相同特性，因此可以 利用博弈论中的一些方法来限定双层规划问题解的范围。在博弈论 中，同两个选手分别控制各自的决策变量相比，如果一个选手能控制 所有的决策变量，那么，这个选手就能更好的优化其自身的目标。基 于上述观点，根据所控制的决策变量的不同，可以将双层规划问题重 新表示为以下两个不同的规划问题。 ( 1 ) 如果上层决策者控制所有的决策变量，则双层问题变为： ( p 2 2 ) m i n y ( x ，y )( 2 1 6 ) s t c ( x ，y ) 0 ( 2 1 7 ) g ( x ，y ) 0( 2 - 1 8 ) ( 2 ) 如果上层决策者和下层决策者分别独立地控制各自的决策 变量，则双层问题变为： ( p 2 3 ) ( u 2 3 ) m i nf ( x ，y ) x s , t c ( x y 1 0 ( 2 1 9 ) f 2 2 0 ) 北京交通大学礤士学位论文 荚中 ( l 2 3 ) m r tf ( x ，y ) ， s , t g ( x ，y ) 0 ( 2 - 2 1 ) ( 2 2 2 ) 必须注意裂；在趣嚣( p 2 。3 ) 中，下层决策交童y 不器是上鼷涣蒙变 量x 的函数。 俊设：x ，y ”) 、( x ”，y 2 + ) 稻( x ”，y ) 分掰代表问题( p 2 1 ) 、( p 2 + 2 ) 和( p 2 ，3 ) 的解，则有： f ( x ”，y 2 + ) f ( x ”，y ”) f ( x ，y 3 )( 2 - 2 3 ) 毅霖蠢，蕈层藏越涟麓( p 2 。2 ) 窝( p 2 3 ) 比双瑟瓣蘩藏藤( p 2 ) 更容易求解，因此，不必直接求解双层规划问题( p 2 ，1 ) ，简直接求 解攀层蔑鬣淘蘧( p 2 2 ) 秘( 琵。3 ) ，然麓器量减，j 、尹( x ”，y ”) 与 f ( x p ，y 2 + ) ，( x ”，y ”) 与f ( x 3 。, y ”) 之间的熬异，可以得到避议鳃。 s h a w ( 1 9 8 0 ) 和b e n - a y e d ( 1 9 8 8 ) 就设计了基于上述思想的求解双 层规划豹痘发式算法。 2 1 。2 用双层规划表示的库= | 譬一订货联合优化模型 程垄断市场经济中，我们可以把库存订赞问题看作一个指导者一 舔隧誊( l e a d e r - f o l l o w e r ) 麓遂，箕中上游供应裔簸决策烧指导者 ( l e a d e r ) ，订货商确定订货策略的行为为跟随者( f o l l o w e r ) 。上游 供应巍霹瑷遴遘管理器庆策( 篦魏礁定货秘订魏擎徐) 来改交菜个订 货商的购买成本，从1 i 百影响订货商的订货策略( 比如订货批凝) 。订 货窝划对现蠢载货物攀秘避嚣比较，壤据垂积瓣簧求特点秘孬荛习镤 来选择订货批量。这种关系我们可以用双层规划进行描述。 供应链中供需关系决策怒按以下过程进行的：上层供应方绘下屡 需求方一定酶信息，下层需求方在这些信息下，按自嚣的利蘸或偏好 1 4 北京交通文学硕士学位论文 做出反应( 决策) ，上层再根据这些反应，做出符合全局利益的决策。 上层给出的信息是以一种可能的决策形式给出的，下层的反应实际上 是对上层决策的对策，这种对策在下层看来是最好的，它显然与上层 给出的信息有关，为了使整个系统获得“最好的”利益，上层必须综 合下层的决策，调整自己的决策。这正好符合供应链要求其成员尽量 互相合作，促进信息共享，以实现全局最优的基本思想。 尽管双层规划理论已经应用到了许多领域，但还没有发现其在物 流技术研究中有影响的研究成果，本硕士论文利用双层规划及交叉规 划为基本工具来描述几种条件下库存订货联合优化问题。 2 1 3 求解双层规划模型的算法概述 到目前为止，对于双层规划的求解大约有十几种求解算法。但归 纳起来说，用于求解双层规划问题的算法可以分为四大类，即极点搜 索法( e x t r e m ep o i n ts e a r c hm e t h o d ) 、库恩一塔克法( k u h n t u c k e r m e t h o d ，简称k - t 法) 、下降法( d e s c e n tm e t h o d ) 和直接搜索法( d i r e c t s e a r c h m e t h o d ) 和非数值启发式方法，下面分别加以介绍。 ( 1 ) 极点搜索法：这种方法主要用于求解双层线性规划问题， 其基本观点就是：双层线性规