供应与选址问题

供应与选址问题摘要本论文主要讨论并解决了某公司每天给工地的供应计划与临时料场选址的相关问题。为使总吨千米数达到最小，在考虑有直线道路连通的情况下建立相应的数学模型，给出了相关算法。并运用Lingo、matlab等软件编程和处理相关数据，得到最优决策方案。问题一是一个线性规划问题，我们首先建立单目标的优化模型，也即模型一。借助Lingo软件得到了该公司每天向六个建筑工地运输水泥的供应计划如下表，从而可使得总的吨千米数最小为157.473.料场向各工地的水泥运输量（吨）工地123456料场A460002料场B006789问题二是一个非线性规划模型，要求改变临时料场的位置以使吨千米数进一步减少，在改变临时料场的同时，料场向各个工地的水泥运输量的计划也会随之而改变。用matlab中的fmincon函数求解，得到料场的新位置及料场向各工地的水泥运输量计划如下表，总的吨千米数最小为118.9878。与第一问的线比较，节省的吨千米数最小为38.4852。料场的新位置及料场向各工地的水泥运输量计划表工地123456新料场的位置料场A462000（6.0464，0.0893）料场B0047811（5.0014，6.0020）关键词选址与供应非线性规划fmincon函数最优化1问题背景随着经济的发展，工地的建设选址与供应问题也越来越重要，供应与选址问题是运筹学中经典的问题之一。我国是一个人口众多的国家，供应与选址问题在生产生活、物流、甚至军事中都有着非常广泛的应用，如工厂、仓库、急救中心、消防站、垃圾处理中心、物流中心、导弹仓库的选址等。供应和选址是最重要的长期决策之一，供应的位置和选址的好坏直接影响到工地建设服务方式、服务质量、服务效率、服务成本等，从而影响到工地的建设效益，甚至决定了建设工地所在单位的命运。好的选址和供应会给工地的建设和服务带来便利，降低成本，扩大利润和市场份额，提高服务效率和竞争力，对进一步加快公司的工地建设和创新创业发展步伐，突出产业创新，在本行业中打造现代产业体系中做先锋，激活创新主体，在加快提升公司与企业创新能力上实现重大突破有重大意义。差的选址与供应往往会带来很大的不便和损失，甚至是灾难。所以，供应与选址问题的研究有着重大的经济、社会和军事意义。2问题重述有一公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：千米）及水泥日用量d(吨)由下表给出.目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有30吨。（1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少吨水泥，使总的吨千米数最小？（2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为30吨，问应建在何处，节省的吨千米数会多大？123456a180538b104667d46678113模型符号说明符号符号说明),(biai工地i的位置),(yixi料场j的位置iS1料场A到工地（ai，bi）的距离（千米）iS2料场A到工地（ai，bi）的距离（千米）iD工地i的水泥日用量（吨）jE料场j的日储量（吨）ijC从料场j向工地i的运输量（吨）f目标函数注：i=1、2、、、6，j=1、24问题分析记工地的位置为（ia，ib），工地的水泥日用量为id，i＝1，…，6；料场位置为（jx，jy），料场的日储量为je，j＝1，2；从料场j向工地i的运送量为ijc。这个优化问题的目标函数（总吨千米数）可表为minf＝262211()()ijjijijicxayb（1）各工地的日用量必须满足，所以有21jijc＝id，i＝1，…，6（2）各料场的运送量不能超过日储量，所以有61iijc≤je，j＝1，2（3）对于第一问，决策变量A、B两料场往各地的运输量为ijc，问题归结为在约束条件（2）、（3）及决策变量为非负的情况下求运送量ijc使（1）的总吨千米数最小。由于目标函数f对ijc是非线性的，所以在求运送量f最小时是非线性规划模型。对于第二问，则该问题的决策变量为料场位置jx，jy和A、B两料场往各工地的运送量ijc，问题归结为在约束条件（2）、（3）及决策变量为非负的情况下求料场位置（jx，jy）和运送量ijc使（1）的总吨千米数最小。由于目标函数f对jx，jy是非线性的，所以在求新建料场位置和用料时是非线性规划模型。5基本假设1、在一段时间内（或每天）工地所需要的水泥量不变；2、在一段时间内不增加新的工地；3、两个临时料场日储量满足题目所给的条件；4、假设其他突发事件的影响可以忽略；5、每天分配给工地的水泥都用完，不能在第二天继续用；6、假设从料场到工地之间均有直线道路相连；7、每个工地的位置用平面坐标的形式表示。6模型的建立及求解6.1对于问题一，采用线性规划模型求解6.1.1线性规划问题数学模型的一般表示min)(xf()0,1,2,,.()0,1,2,,ijgximsthxjk（4）其中x∈nR，)(xf为目标函数，)(xgi，)(xhj为约束函数，在这些函数中都是线性函数。令S＝｛x｜)(xgi≤0i＝1，2，…，m；)(xhj＝0j＝1，2，…，k｝称S为可行集或可行域，S中的点称为可行点。这样（4）可用集约束的形式来表示min)(xf，..tsx∈S设)(xf为目标函数，S为可行域，*x∈S，若对每一个x∈S均有)(xf≥)(*xf，则称*x为极小化问题（4）的最优解（整体最优解）；若存在*x的某邻域，使得对该邻域中每个x成立)(xf≥)(*xf，则称*x为极小化问题的局部最优解。6.1.2根据题目所给的条件，列出目标函数和约束条件。我们可以先算出料场到个工地之间的距离(1,,6,1,2)()ijSij千米，利用matlab求解，求解代码见附录1，得到结果如下：工地xi至料场A的距离（千米）工地xi123456料场A43.1622785.83095255.3851656.708204工地xi至料场B的距离（千米）工地xi123456料场B6.0827639.2195443.6055513.1622781.4142146要求从A，B两料场分别向各工地运送多少吨水泥，使总的吨千米数最小，假设料场向各工地运送(1,,6,1,2)()ijCij吨，则有：目标函数y=4*c11+3.162278*c21+5.830952*c31+5*c41+5.385165*c51+6.708204*c61+6.082763*c12+9.219544*c22+3.605551*c32+3.162278*c42+1.414214*c52+6*c62;约束条件c11c124;c21c226;c31c326;c41c427;c51c528;c61c6211;c11c21c31c41c51c6130;c12c22c32c42c52c6230;6.1.3应用非线性规划软件lingo求解，求解代码参见附录2，得到结果如下：料场向各工地的水泥运输量（吨）工地123456料场A460002料场B006789总的吨千米数最小为157.473。6.2对于问题二，采用多变量非线性规划模型求解6.2.1求解的非线性规划模型：min)(xf（5）()0..()0AxbcxstAeqxbeqlbxupcepxx=fmincon(fun,x0,A,b)求解非线性规划模型（5），目标函数非线性；x=fmincon(fun,x0,A,b,Aeq,beq)求解非线性规划模型（5），有等式约束条件；x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub)求解线性规划模型（5），指定了决策变量的上下界（lb和up）；x=fmincon(fun,x0,A,b,Aeq,beq,lb,up,nonlcon)非线性约束条件写成M函数形式（nonlcon.m）；function[c,ceq]=nonlconc=c(x)；ceq=ceq(x)；用［x,Fval］代替上述各命令行中左边的x，则可得到在最优解x处的函数值Fval；其中x为n维变元向量，()cx与Ceq(X)均为非线性函数组成的向量，其它变量的含义与线性规划、二次规划中相同，用Matlab求解上述问题，6.2.2这里的求解过程分三步进行。1.首先建立M文件gongying.m,定义目标函数()Fx:functionf=gongying(x);f=F(X);其中262211()()(),1,2.1,2,,6ijjijijiFxcxaybji，具体的求解代码详见附录3。2.把题目中的约束条件中的非线性约束G(X)0或Ceq(X)=0表示出来，根据题中的约束条件，构造下列矩阵：111111000000000010000001111110000A1000001000000000010000010000000000100000100000002000100000100000000001000001000000000010000010000A')30,30(1B)118,7,6,6,4,(2B变量的下限V1)0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0(1V变量的上限V2)11,8,8,8,88,7,6,6,11,4,8,7,6,6,4,(2V迭代的初值x0)7,2,1,5,0,0,0,0,0,0,0,0,0,0,0,0(0x3.根据上述约束条件和目标函数，在matlab中求解，代码参见附录4，得到结果如下：料场的新位置及料场向各工地的水泥运输量（吨）工地123456新料场的位置料场A462000（6.0464，0.0893）料场B0047811（5.0014，6.0020）总的吨千米数最小为118.9878。与第一问的线比较，节省的吨千米数最小为38.4852。6.2.3再利用matlab画出各个工地的位置、临时料场的位置及新料场的位置，画图代码参见附录5，得到图形如下：01234567801234567+4+6+6+7+8+11新A新B临时A临时B在上图中画出了工地、临时料场及新料场的位置（+为工地，旁边的数字为用量，新A、新B分别表示新料场的位置，临时A、临时B分别表示临时料场的位置），可以看出，新料场应建在两个用量最大的工地旁边。7模型的评价、改进和推广7.1模型评价优点建立了规划模型，通过lingo软件的线性求解和matlab的非线性求解，得出各种供应计划方案的最优解。缺点对于题中工地与料场的位置，我们假设是直线，因而在处理供应计划与选址的关系上比较含糊，没有深入讨论。7.2模型改进在求解第一问时，可以直接在matlab中应用相关的线性规划函数求解，求解过程较为简单。对于模型二，可以采用随机搜索法求解。由于要求料场的位置及相应的供应计划方案，对于料场的位置进行随机搜索，在带入目标函数求解出相应的最优解。7.3模型推广线性规划及非线性规划在日常生活中有着重要的应用，是一种比较简单的优化模型，运算简便，操作不复杂，易于求解。8参考文献1）、《最优化方法及其应用》高等教育出版社郭科陈聆魏友华；2）、《MATLAB及其在理工课程中的应用指南》（第三版）西安电子科技大学出版社陈怀琛编著；3）、供应与选择问题）、《数学建模方法与分析》（原书第3版）机械工业出版社（美）Mark.Meerschaert著刘来福杨淳黄海洋译9附录附录1%计算料场A、B到各个工地i的距离S1（i）和S2（i）closeall,clear,clca=[180538];%工地的横坐标b=[104667];%工地的横坐标fori=1:6s1(i)=sqrt((a(i)-5)^2+(b(i)-1)^2);s2(i)=sqrt((a(i)-2)^2+(b(i)-7)^