本科毕业设计论文--多商品配送问题的数学模型及快速算法.doc

《本科毕业设计论文--多商品配送问题的数学模型及快速算法.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、多商品配送问题的数学模型及快速算法摘要:多商品的配送问题日益成为现实社会的热点。本文描述了商品价格，需求以及销售网络已定的前提下，一个多货栈多商品多客户的供货商如何制定商品配送计划，以实现供应成本的最小化。在考虑了运输成本与时间的关系以及提前/推迟供货带来的惩罚之后，以实现运输成本与惩罚之和最小为目标，进行了系统建模。首先建立了原始模型，分析模型结构后，讨论了几种可行的算法。然后在运输时间小于一个订货时段，惩罚与误期的时段成正比的假定下，将模型转化为可求解的线性规划模型，并由最简单的情况开始逐级深化讨论模型。对各个简化模型，给出相应的具体算

2、例，用lingo进行求解，结果分析表明了模型的正确性和有效性。当深化为多货栈多商品多零售商模型时，通过深入分析模型，提出一种快速算法，并由lingo编程实现，极大地减少了线性规划的变量个数（由O（）减少为O（）），降低了线性规划的复杂度。通过两种算法对带有个变量的大规模销售网络的计算比较，验证了快速算法的优越性。最后根据一种更符合实际情况的假设，进一步优化，建立了更加有效，更加节省成本的供销模型。关键词：多商品配送提前/推迟供货惩罚运输成本二次规划线性规划快速算法优化模型16一、问题的重述：考虑供货商的多种商品配送问题．假设该供货商在某地区

3、有多个仓储的货栈，它们位于该地区的不同地点．供货商的目标是按照不同零售商的需求将商品及时发送给零售商，使总成本尽可能小．这里的总成本主要由以下几部分组成．（1）运输成本，它与运输的时间和运输的商品相关．（2）由于货栈可以以不同价格将同一种商品供给不同的零售商，且同一种商品在不同货栈的售价也可以不同，这样零售商会按照价格优先的原则选择发货的货栈．另一方面，每一时段每个商品在货栈中的存储量有一个上限．当一个货栈被指派为一个特定的零售商提供规定数量的商品的时候，可能会出现零售商的需求和货栈储量不平衡的情况．当某时段容量不足的时候，货栈通过提前或推

4、迟供货给零售商的方式来补偿需求．如果提前供应，将会导致零售商的商品持有成本上升,因此零售商会向供货商索要赔偿；若推迟,则会降低货栈的信誉，且零售商也会向供货商索要赔偿．所以，提前和推迟所带来的赔偿都是供应成本的一部分，而赔偿费用与商品的价格和提前、推迟的时间有关．现假设在一个周期（例如一年）开始时，每个零售商对所有商品在不同时间(时段)的需求已知，以及商品的价格已知，问题是供货商如何安排不同时间(时段)的供货，使得一个周期的总成本尽可能小．1．对此问题，并针对你所理解的实际中的多商品配送问题，建立数学模型,讨论求解算法的设计．2．分析当运输

5、成本和运输的时间是什么关系,提前、推迟惩罚与商品的价格以及提前、推迟的时间是什么关系时，或在其他你认为合理的假设下，该问题可以有快速算法求解．这里，你对这些关系的假设应与实际背景较吻合．3．举一个和几个实际算例来说明你的算法或模型．二、问题的分析考虑某地区的一个供货商，有J个货栈，分布在该地区的不同地方。该供货商可提供K种商品，每一个货栈可拥有全部的商品也可以是其中的一部分，每一个货栈又给多个零售商供货。假设供货商给I个零售商供货。在一个周期T（例如一年，并分为T个时段）开始时，每个零售商对所有商品在不同时段的需求已知，每种商品的价格已知，

6、且这一价格在一个周期内保持不变。零售商选择价格最低的一个货栈给它供货（如果存在多个最低价格时，由零售商任意选择其中的一个），因此一个周期内货栈与零售商间的销售网络已经确定。我们认为根据所给价格既定的销售网络是健康的，不存在极度不平衡的供需关系。该问题考虑的供应成本由两部分组成：运输成本和由于提前或延误供货造成的赔偿：（1）、运输成本。该供货商在不同的地方设有多个货栈，而该地区的零售商也位于不同的地方，因此存在运输问题，即运输时间、运输费用。设运输成本为G，它与运输时间，运输商品的种类k及运输量有关。（2）、由于提前或延误供货造成的赔偿，，称

7、为惩罚函数，表示x单位价格的商品提前或延误时段对零售商的赔偿。当＝0或x＝0时，F＝0；当<0时，表示提前供货；当>0时表示推迟供货。三、基本假设161、零售商以时段为时间间隔向零售商订货，且每一时段至多订一次货。2、货栈以时段为时间间隔给零售商发货，且每一时段至多发一次货。3、当某货栈某时段容量不足时，供货商只通过由零售商按价格最低原则选定的货栈提前或推迟供货的方式来补偿需求，而不考虑货栈之间的相互调货，或者由其它货栈给该零售商供货。4、供货商有充足的运输能力，运输成本只与时间与运输商品以及运输量有关，而不考虑具体的运输细节。5、当配送区

8、域比较大的时候，运输的时间可能比较长，货物经过几个时段才能送到零售商处。这时，供货商为了协调供货以达到总成本的最小，可以选择不同的方式，改变运输时间，从而改变运输成本。[1]当配