运筹学专题报告书

1、运筹学专题报告2Lingo语言求解东方服装集团童装配送系统设计问题user2011/5/22目录 TOC o 1-5 h z HYPERLINK l bookmark11 o Current Document 引言3 HYPERLINK l bookmark14 o Current Document 1、案例介绍3 HYPERLINK l bookmark18 o Current Document 1.1基本介绍3 HYPERLINK l bookmark21 o Current Document 1.2初步分析.4 HYPERLINK l bookmark24 o Current Docum

2、ent 2、建模思想5 HYPERLINK l bookmark28 o Current Document 2.1 0-1混合整数规划法5 HYPERLINK l bookmark31 o Current Document 2.2模型描述5 HYPERLINK l bookmark34 o Current Document 2.3假设条件6 HYPERLINK l bookmark42 o Current Document 2.4费用构成和变量规范62.5模型描述.7 HYPERLINK l bookmark55 o Current Document 3、案例求解8 HYPERLINK l b

3、ookmark59 o Current Document 3.1编写lingo程序8 HYPERLINK l bookmark95 o Current Document 3.2运行求解10 HYPERLINK l bookmark98 o Current Document 4、讨论：11 HYPERLINK l bookmark102 o Current Document 4.1非零库存政策11 HYPERLINK l bookmark105 o Current Document 4.2各配送中心有年吞吐量上限11 HYPERLINK l bookmark137 o Current Docum

4、ent 4.3外部采购情况14 HYPERLINK l bookmark140 o Current Document 5、结束语15 HYPERLINK l bookmark144 o Current Document 6、参考文献157、附录16引言一般研究物流配送中心选址的方法较多，大致可以分为定性和定量两类方法。定性方法 主要是结合AHP （层次分析法）和模糊综合评价法对各方案进行指标评价，找出最优选址。定 量方法主要有重心法、运输规划法、Cluster法与CFLP法、Baumol-Wolfe法、遗传算法和 0- 1混合整数规划法等。Lingo是美国LINDO系统公司开发的一套专门用于求

5、解最优化问 题的软包。主要用于求解线性规划问题、二次规划问题、非线性问题和一些线性和非线性方 程的求解。Lingo优化软件的最大特色在于可以允许优化模型中决策变量为整数（支持整数 规划），而且快捷、准确。同时Lingo还是最优化问题的一种建模语言，其程序使用自己的 专用语言编写，普通人难以看懂，为此Lingo又提供其他文件（如文本文档、Excel电子表 格、数据库文件等）的接口，易于方便地输入、求解和分析大规模的优化问题。因此Lingo在 数学、科研和工业界得到广泛应用。以下案例将全部基于ling o语言的运算解释。1、案例介绍1.1基本介绍东方服装集团考虑生产一种童衣系列。童衣产品将先运至配

6、送中心，再由配送中心将产 品运至分销店。该集团有5家工厂可生产这类童衣，有3家配送中心可以分配童衣产品，有4家分销店可以经营童衣产品。这些工厂和配送中心的下一年度的年固定成本如下表1。表1工厂与配送中心的固定成本单位工厂1工厂2工厂3工厂4工厂5配送中心1配送中心2配送中心3年固定成本（元）3 500045 00040 00042 00040 00040 00020 00060 000下一年度工厂的生产能力、工厂到被选的配送中心的单位运价如表2所示。表2各工厂至配送中心的运输成本与生产能力终点f f、八、起点运输成本（元/箱）生产能力（箱）配送中心1配送中心2配送中心3工厂18001 0001

7、 200300工厂2700500700200工厂3800600500300工厂4500600700200工厂5700600500400从配送中心运至分销店的运输成本和各分销店的需求量如表3所示。终点ff、八、起点、运输成本（兀/箱）分销店1分销店2分销店3分销店4配送中心140809050配送中心270406080配送中心380305060需求量（箱）200300150250假定各配送中心的库存政策为零库存，即配送中心从工厂得到的产品均分配给分销店， 不留作库存。集团要设计一种童衣分配系统，在满足需求的前提下，确定使用哪些工厂与配 送中心进行童衣的生产与配送，以使得总成本最小。1.2初步分析通

8、过初步分析，我们可以认定此例题的性质，即一般意义上的物流选址模型。主要分析物流 系统中库存管理、运输、配送中心之间的联系，应用最优化方法建立了物流配送中心选址 的数学模型。该模型是一个混合整数规划。物流系统中配送是重要一环，因此搞好配送中心 选址对提高整个物流系统的效益具有重要意义，配置配送中心应考虑下述必要性：首控制物流成本。再按照集约库存来维持合理的库存量，为了防止库存过剩和库存偏颇， 把过去分散在数家的自家仓库，集约到配送中心进行管理，提高服务水平，扩大销售。把配送中心配置在兼顾消费地和生产地处，既可以及早掌握发生的销售信息，把顾客的 实际需要和需要动向迅速地反映到生产计划部门和采购计划

9、部门;也可以迅速将产地货物输 送各地。具体选址还要视货物情况而定。商物分离。把进行商品交易的场所和进行物流活动的场所分离，明确商品交易功能和物 流功能，以配送中心为中心来提高物流的效益化。防止交错运输。分散在全国各地的工厂生产着不同品种的商品，从各个工厂到消费地难 免发生交错运输，使成本提高，因此，在适当的场所配置配送中心，把从各个工厂集约起来 的商品有计划地运输到消费地。2、建模思想2.10-1混合整数规划法01混合整数规划法的主要优点是它能够把固定成本以最优的方式考虑进去，它是商 业选址模型中最受欢迎的方法。用0- 1混合整数规划来解决选址模型时，目标是使各种成 本费用的总和最小，而用整数

10、变量表示各种选择，用连续变量表示工厂的生产能力、各种资 源的分配等，用约束表示物流平衡关系和供需关系等。其主要思想是将每一个备选配送中心 （RDC）分别纳入目标函数中看各自对目标函数的影响程度，最后决定是否需要该RDC。2.2模型描述假设有J个（备选）配送中心可从I个工厂中进货，同时又必须给K个客户提供配送服 务，于是商品的供需关系和流动况将形成了一个完整的物流配送网络结构。工厂和客户的数 量和位置是固定的，从J个备选RDC中选出j个RDC，并求出工厂和配送中心、配送中心 与客户的供需关系，使总费用最小。如图1所示。1模型示意E工厂旧1模型示意E工厂旧客户邮）V被透RDC(W)2.3假设条件企

11、业物流配送中心选址问题是在给定某一地区所有备选点的地址集合中选出一定数目 的地址建立配送中心，从而建立一系列的配送区域，以实现选出点建立的配送中心与各需求 点和工厂(供货点)形成的配送系统总物流费用最小。为了便于建立数学模型，作如下假设：由工厂到配送中心、由配送中心到客户的单位运输价格和运距均已知。各工厂的总生产能力已知；配送中心的容量及个数有限制；各客户的需求量己知；配送中心的固定费用、单位管理费用为已知常数。2.4费用构成和变量规范由于配送中心选址中包括多种费用，所涉及的变量不下十个，在配送中心选址模型中说 法太多，且很乱，于是下面将对各种费用和所涉及到得变量做以科学的规范：费用界定将与配

12、送中心选址有关的物流环节细分为进货运输、存货仓、送货配送三个环节，于是 费用也就考虑以下三种：从工厂到配送中心的进货运输费用，简称运输费用(Transportation costs)、从配送中心到客户的送货配送费用，简称配送费用(Distributioncosts)和货物流经 配送中心时的仓储费用，其中仓储费用又包括新建配送中心的固定投资费用(Warehouse fixed costs)和保管暂存货物可变仓储费用(Variable warehousing costs)。即总费用主要包 括运输费用、仓储费用、配送费用三部分。规范变量T：运输费用；D：配送费用；W：仓储费用；Pij：备选区域配送中

13、心Wj向工厂Fi的单位 进货费用；Xij:备选区域配送中心Wj向工厂Fi进货数量；Mij:备选区域配送中心Wj到 工厂珏的运距；Qij：备选区域配送中心Wj到客户区Rk单位配送费用；Yij：备选区域配 送中心Wj到客户区Rk送货数量；Nj k：备选区域送中心Wj到客户区Rk的运距；Hj:备选 区域配送中心Wj单位库存成本；Sj：新建配送中心Wj需要投资的固定费用；Zj： 0-1变量， 1表示开设配送中心Wj；人1：是工厂Fi的供应总量；Bj：配送中心Wj的仓储容量；Ck： 是客户区Rk的需求量。通过以上对配送中心选址问题的研究，我们结合0-1整 数规划建立如下的模型。目标函数：总费用运输费用仃

14、=骂心冲衫4配送费用w B=Q”侦M VZj;仓储费用：卬=WER=HjX*+S由，即】总费用=卒/*+H占 4 淄4+Q* Y职 V*由上式可得目标函数如下：I IJ K岫二 XX Xi = J i = JJ = J k = J+ 砰夺移i = /j = J约束条件；各工厂（Q调出的物资总量不应大于其生产、供应能力 CVo *声枷 H3X = 1各配送中心（B9,其进货量不应大于器仓储能力凸玄*及 广1,2,3 i = 1各经销商（AQ调运进来的物资总量不应小于其需求总量勇匕QG123i = 1对于每-区域配送中心（叫）由于其既不能成产也不能消 耗物资，因此每个区域配送中心调出的物资总量等于

15、调入的物 资总量：I X尸邕.1 - i - f3、案例求解假定各配送中心的库存政策为零库存，即配送中心从工厂得到的产品均分配给分销店，不留 作库存。集团要设计一种童衣分配系统，在满足需求的前提下，确定使用哪些工厂与配送中 心进行童衣的生产与配送，以使得总成本最小。参考物流选址模型，本题也是物流选址模型的一个实例。由于本题没有单位物资的可变仓储 费用，即不考虑物资在配送中心内部所发生的费用。3.1编写lingo程序MODEL:!设置变量；sets:!工厂3, b，u分别表示产量，固定费用，01变量；factory/1.5/:a，b，u;!配送中心臼v分别表示固定费用，0-1变量；warhous

16、e/1.3/:f，v;customer/1.4/:c;而工厂到配送中心的价格数据，乂各工厂到配送中心的运量；link1(factory，warhouse):m，x;!n配送中心到客户的价格数据，y各配送中心到客户的运量；link2(warhouse，customer):n，y;endsets!数据区；data:a=300 200 300 200 400;b=35000 45000 40000 42000 40000;c=200 300 150 250;f=40000 20000 60000;m=800 1000 1200 700 500 700 800 600 500 500 600700 7

17、00 600 500;n=40 80 90 50 70 40 60 80 80 30 50 60;enddata!目标函数；min=sum (warhouse (j):sum (factory (i):m (i, j)*x (i, j)*v (j)+sum (customer (k):sum (warhouse (j):n (j, k)*y (j, k)*v (j)+sum(warhouse(j):f(j)*v(j)+sum (factory(j):b(j)*u(j);!约束条件，工厂输出小于产能；for(factory(i):sum(warhouse(j):x(i, j)=c(k);for(

18、warhouse:bin(v);for(factory:bin(u);for(warhouse(j):sum(factory(i):x(i, j)=99999999*v(j);for(factory(i):sum(warhouse(j):x(i, j)=99999999*u(i);3.2运行求解根据Lingo的解答得到下表:各工厂至配送中心的运输量与产量、终点、八、运七F俞成本（兀/箱）起点、配送中心1配送中心2配送中心3生产能力（箱）工厂1工厂2工厂3工厂4工厂5200300400表：配送中心至分销店运量终点%、八、起点、运输量（箱）分销店1分销店2分销店3分销店4配送中心1配送中心2 配送

19、中心3200300150250需求量（箱）200300150250从上表中可以看出，在最满足要求的情况下最小成本为700500元。其中使用工厂2、3、5, 配送中心2、3,具体产量和配送额如上图。4、讨论：4.1非零库存政策如各配送中心的库存不实行零库存政策，即配送中心有一定的期初、期末库存。首先考虑期末库存的情况：在本例中，工厂可以提供的最大产能远大于顾客需求。如果配送中心追求最小成本，其 必须支持零库存，显而易见，当工厂产能大于需求时，多余部分即可储存在配送中心，但在 目标函数的限制下，计算机算法是减少工厂的产量来达到零库存。举例来说，假如工厂2的 产能为250箱，通过此l ing o程序

20、求解最终工厂2只是生产了200箱物资，如果富余产能50生产 的话会相对原来增加工厂2到配送中心2的运费。因为费用的限制，此例中供给是满足需求的。假设限定一项条件为：开工工厂必须按照最大产能生产，则结果就会相应变化。同样以 工厂2为例，假如工厂2的产能为250箱，其必须生产250箱以满足最大设备利用率，则供给减 去需求剩余的50箱物资就会储存在配送中心2,费用也相应的增加。现在考虑期初库存的情况：如果配送中心中本来就有期初库存，则相应的工厂就会减少产量以减少成本。同样的有 一种情况，即追求设备利用率最大，开工工厂必须按照最大产能生产，此时会怎样？简单阐 述为，在配送中心的库存尚不能一次满足配送点

21、需求时，相应工厂会不断增加配送中心的库 存。当下一期配送中心的库存可以满足配送需要，则本期工厂暂停使用，需求由库存解决。 同样以工厂2为例，假如工厂2的产能为250箱，其必须生产250箱以满足最大设备利用率，每 期在配送中心2中积累50箱物资。第四期末积累200箱，则第五期工厂2暂停使用，将库存200 配送。4.2各配送中心有年吞吐量上限1、现在配送中心最大的实际吞吐700箱，即如果限额大于700箱，最优结果不变化。2、如果最大吞吐量小于700箱，利用原代码修改，对配送中心吞吐量进行限制。比如最大吞吐量为 650 箱，在代码中加入for(warhouse(j):sum(link1(i，j):x

22、(i，j)650);进行限制，得到结果图为Lingo 12.0 Solver Status 演箸学ySolver btatGsModel Cla-MINLPStat己Local I3ptObisctive:7 0 6 0 0 0Infeasibility 2 . 3885Ge-010Iterations2 6 4 4variaulesTotal:35Nonlinear:30Integers:8Total:症 4Nonlinear:1I al II lrril I IATotal:1 彼Nonlinear:&0Solver Tvpe：B-and-BBest Obj:0G000 bj Bound7

23、060005teps:4 0Active:0Generator M emory U aed K31-Elapsed Runtime (hh;mnn;)00:00:01Update Interval: 2口。范即最优解变为706000元，比原来增加了 5500元。此时各工厂各配送中心量如下表:各工厂至配送中心的运输量与产量终点、八、起点运输成本（元/箱）生产能力（箱）配送中心1配送中心2配送中心3工厂1工厂2工厂3工厂4工厂520050250400表：配送中心至分销店运量、终点起点运输量（箱）分销店1分销店2分销店3分销店4配送中心1配送中心2配送中心320030050100250需求量（箱）2

24、00300150250对比发现，工厂3原来向配送中心3输送的300箱物资中50箱转移至配送中心2.最多转移多少可达到极限？通过计算吞吐量450是配送中心1启用的临界条件。加入for(warhouse(j):sum(link1(i，j):x(i，j)450);结果为Lingo 12.0 Solver Status 旗碧学ySolver StatusModel Class:MINLPState:local OptObjective:72 80 00Inreasibility:2 ,42267e-010Iterations:14 51VariablesTotal:3 5Nonlinear:3 01

25、ntegers:8JUI IMI 口II 113Total:24Nonlinear1Total:142Nonlinear:3 0Solver T卯日：B-and-BBesl0b|：72 80 00Obj Bound:72 80 00Generator M&nory UsedKJ31p Elapsed Runtime (hh:mnn:s3)心妃000:00:01Update Interval; 2Jnt日ri叩t 5口由 | U瓯关于配送中心01变量取值为U( 1)0.0000000.000000U( 2)1.00000045000.00U( 3)1.00000040000.00将代码改为for

26、(warhouse(j): sum(link1(i，j):x(i，j)449);结果为最优解变化很大，V( 1)1.000000148000.0V( 2)1.000000173640.0V( 3)1.000000305470.0三个配送中心全部启用。4.3外部采购情况本题目考虑的是一家集团企业内部的问题，如果是企业向外部采购呢？随着市场经济的发展和完善，采购已由单纯的商业买卖发展成为一种职能、一门专业。 现代企业经营管理中，采购越来越重要，外购件与原材料的采购成功与否，大大影响到企业 的竞争力。对于企业向外部采购的话，我们依然基于此模型讨论。假设：1物资必须经过配送中心才可以到客户2费用计算只

27、核算直接采购费用模型的最优解也是基于费用最小理论。如果企业只采购物资，物资的下一步配送即由配送中心到客户仍由企业来做，则此模型 中的工厂即可代表供应商。模型求解如前例。如果企业将物资采购和配送全部外包，其只提供技术设计、资金等，则只需要在投资和 收益之间权衡。所选第三方可提供最大化的利润则为最优解。5、结束语0-1混合整数规划法，由于其处理数据是在整数中进行，运算结果更加符合现实情况， 因此0- 1混合整数规划法被广泛运用于RDC选址模型中，但有其现实情况中备选RDC的 数目较大，不同地区的运输、配送、仓储费用又有较大的差别，这将使模型变的十分的复杂， 我们无法再用传统的运筹学方法去解决问题，

28、于是我们引ALING O编程的方法，使配送中 心选址问题得到了快速、精确、科学的解决。6、参考文献1丁小东，姚志刚,程高.LINGO语言与0- 1混合整数规划选址模型的再结合J.物流工 程与管理,2009,(31) 魏光兴.物流配送中心选址综述J.物流与交通,2007, (2).徐国松.LINGO软件在运输问题中的应用J.科技创新导报，2008, NO.3杨涤尘.数学软件与数学建模J.湖南人文科技学院学报，2006, (12).解答数据（原始解）Local optimal solution found.Objective value:Objective bound:Infeasibilitie

29、s:Extended solver steps:Total solver iterations:700500.0700500.00.000000634684Model Class:INLPTotal variables:35Nonlinear variables:30Integer variables:8Total constraints:21Nonlinear constraints:1Total nonzeros:127Nonlinear nonzeros:30VariableValueReduced CostA( 1)300.00000.000000A( 2)200.00000.0000

30、00A( 3)300.00000.000000A( 4)200.00000.000000A( 5)400.00000.000000B( 1)35000.000.000000B( 2)45000.000.000000B( 3)40000.000.000000B( 4)42000.000.000000B( 5)40000.000.000000U( 1)0.0000000.000000U( 2)1.00000045000.00U( 3)1.00000040000.00U( 4)0.0000000.000000U( 5)1.00000040000.00F( 1)40000.000.000000F( 2

31、)20000.000.000000F( 3)60000.000.000000V( 1)0.000000-0.5699975E+110.4500000E-030.1000000E-030.2200000E-03V(2)1.00000077000.00V(3)1.000000441500.0C(1)200.00000.000000C(2)300.00000.000000C(3)150.00000.000000C(4)250.00000.000000,M1)1800.00000.000000,M2)11000.0000.000000,M3)11200.0000.000000,M1)2700.0000

32、0.000000,M2)2500.00000.000000,M3)2700.00000.000000,M1)3800.00000.000000,M2)3600.00000.000000,M3)3500.00000.000000,M1)4500.00000.000000,M 2)4600.00000.000000,M3)4700.00000.000000,M1)5700.00000.000000,M2)5600.00000.000000,M3)5500.00000.000000,X1)10.000000,X 2)10.000000499.9999,X 3)10.000000699.9997,X 1)20.0000000.000000,X2)2200.00000.000000,X3)20.000000199.9998,X1)30.000000,X2)30.00000099.99990,X3)3300.00000.000000,X1)4