选址模型XXXX

选址模型1.引言2.选址问题的类型3.单源连续型选址问题的模型及求解4.多源连续型选址问题5.推广与讨论1.引言这类问题很实际意义，例如ƒ仓库选址：给定一个公司的生产工厂和用户的位置，为一个新仓库选择一个昀优地址。我们要考虑的昀优选址问题的主要是指：已知一些现有设施的位置，要求确定一个或几个新设施的地址。ƒ图书馆选址：某市要造一个新的图书馆或其它民用设施，为某一特定地区服务，试为该图书馆选择昀优地址等等ƒ电厂选址：一座新的发电厂（变电所）要向一特定地区供电，如何选择发电厂的昀优地址。现有设施：终点，新设施：源2.选址问题的类型（2）从设施（源）的可能位置来分ƒ连续型选址问题ƒ离散型选址问题（1）从新设施的个数来分ƒ单源选址问题：单设施选址问题ƒ多源选址问题：多设施选址问题选址—分配问题ƒ单源连续型选址问题ƒ多源连续型选址问题ƒ单源离散型选址问题ƒ多元离散型选址问题（3）从新设施的个数和位置分3.单源连续型选址问题某公司要建立一个产品加工厂为十家零售店服务（提供产品），已有下列基本数据：ƒ问题的提出：店号位置单位货物通过单需求量位距离的运价1（10，40）0.025102（50，100）0.03020),(jjyx)(jw)(jβ3.（20，80）0.030254.（60，20）0.040155.（90，70）0.040306.（50，10）0.020257.（60，40）0.020258.（70，70）0.025209.（30，10）0.0351010.（40，90）0.03020要求确定工厂（源）应建在何处，使得从工厂向十个零售店运货的总运费昀小ƒ建立模型)(])()[(),(min21221AyyxxwyxCjjjnjj−+−=∑=β关于上述问题的求解已有研究：定理：为问题（A）的昀优),(**yx⎪⎪⎩⎪⎪⎨⎧=∂∂=∂∂⇔0),(0),(****yyxCxyxCƒ模型求解=),(yx需建工厂（仓库）的位置坐标。因为∑∑==−=−+−−=∂∂njjjjjnjjjjjjdxxwyyxxxxwxC112122)(])()[()(ββ∑∑==−=−+−−=∂∂njjjjjnjjjjjjdyywyyxxyywyC112122)(])()[()(ββ这里,所以2122])()[(jjjyyxxd−+−=形式上解出x和y，这提示我们有如下的迭代算法⎪⎪⎩⎪⎪⎨⎧=−=−∑∑==0)(0)(11njjjjjnjjjjjdyywdxxwββ解此方程组可得：⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎨⎧==∑∑∑∑====njjjjnjjjjjnjjjjnjjjjjdwdywydwdxwx1111////ββββ∑∑∑∑==+==+==njkjjjnjkjjjjknjkjjjnjkjjjjkdwdywydwdxwx111111////ββββ其中),2,1,0(])()[(2122L=−+−=kyyxxdjkjkkj为初始点，通常取为的加权重心：),(00yx),,2,1)(,(njyxjjL=∑∑∑∑======njjjnjjjjnjjjnjjjjwywywxwx110110ββββ已有研究表明采用上述迭代方法能迅速收敛于昀优解。将该方法应用于上述问题即可求出其近似昀优解（迭代7次）),(**yx790.215),(900.62065.58*****==⎩⎨⎧==yxCCyx讨论：•若零售店的需求量发生改变，例如则3010:3010:91→→ww76.276755.51246.50***=⎩⎨⎧==Cyx•若单位运价发生改变，例如则070.0035.0:050.0025.0:91→→ββ25.248212.57062.54***=⎩⎨⎧==Cyxjβ不管规模多大的单源选址问题，求解都十分容易。4.多源连续型选址问题一般形式：将已知设施（位置）称为“终点”已知：①各个终点的位置②各个终点的需要量③有关区域内的运价),,2,1)(,(njyxjjL=),,2,1(njwjL=),,2,1(njjL=β确定：①源（新设施）的个数②各个源的位置ƒ问题的提出：注：•这个问题不再容易，可以说相当棘手，这是因为既要求出源的个数和位置还要对终点进行分配。•可以先假定源的个数已知，再求昀优选址。③将终点（已知设施）划分给各个源（新设施）的情况④各个源（新设施）的容量（例如：某地区变压器的选址与分配问题）ƒ建立数学模型和分配问题，然后对源的不同数目进行考察，再从中选取昀好的，即使这样做，精确求解也很困难.尽管如此，目前有些启发式算法。在建立模型之前，还是以前述例子来说明现在要建m个工厂（仓库）来为10个零售点服务，为了方便起见，对建模做如下假设：H1：各源许可的容量不受限制H2：单位运价与源的总输出量无关H3：每个终点的需求量由一个源向其供应这三个假设是比较合情合理的。假定源的个数为m，此时总费用为:)()(21mgmgCT+=其中个源的资本折旧费和经费管理费，个源向给定的终点供货的昀低费用。一般情形：mmg:)(1mmg:)(2)(2mg)(1mgTC0)(2↓⇒↑mgnm0)(2=⇒=mgnm当模型检验是容易得到的，一般多为线性情形，并且)(1mg↑⇒↑)(1mgnm下面主要讨论计算，假设)(2mg）（个源的坐标待求的mimvuiiL,2,1),(==⎩⎨⎧=供货向终点源供货不向终点源jijiij10δ这样，计算的模型如下：)(2mg),,1;,,1(10)(),,2,1(1..])()[(),(min1121221njmiorBnjtsyvxuwyxCijmiijmijijijnjjijLLL=====−+−=∑∑∑===δδβδ模型（B）约束根据假设H3而来。因为每个源的容量是不受限制的，所以每个终点的需求量应由一个可使总费用昀小的源来供应。ƒ模型求解分析：对于满足模型（B）约束的一组固定值，我们总可得到一组迭代方程，它在形式上与单源选址问题一样，此时有：⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧====∑∑∑∑==+==+)(),,2,1(//)(),,2,1(//111111IImidwdywvImidwdxwunjkijjjijnjkijjjjijkinjkijjjijnjkijjjjijkiLLβδβδβδβδ其中2122])()[(jkijkikijyvxud−+−=初始点一般如下选取：),,2,1(110110miwywvwxwunjjjijnjjjjijinjjjijnjjjjijiL=⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧==∑∑∑∑====βδβδβδβδ对于一组给定的之值，可以根据式（I）和（Ⅱ）求出为了取得上述模型的昀小值，就要讨论的各种取值分别进行求解，这样做可行吗？ijδ),,2,1(),(mivuiiL=ijδ的取值有多少组：S(n,m)是第二类Stirling数，ijδ∑=−−−=mknkkmkkmmnS0)!(!)()1(),(例如当m＝2,n=10时，S(10,2)=511,此时我们要解511个单源选址问题，有了计算机，还比较可行，但是当m＝3,n=25时，S(25,3)=141,197,991,025,此时计算量明显增加，这样做显然行不通。因此我们有必要讨论近似算法。ƒ近似算法算法一：交替选址—分配法step1：将n个终点组成的集合划分成元素个数大致相等的m个子集。2：对这m个子集中的每一个,解一个单源选址问题。3：检查每一个终点，看它离step2中求出的某个源是否比离目前分配中的那个源靠得更近。如有这种情况，重新分配各终点。4：如果重新进行了分配,则转step2。否则,输出结果。例如：对前述问题，我们有m=2,n=10。此时将零售店标号为1，2，…，5分为一组，解对应的单源选址问题可得将标号为6，7，…，10分为另一组，解对应的单源选址问题可得这样得到的)111.70034.62(),(11，=vu)832.42672.56(),(22，=vu85.208),(=vuC)10,,2,1;2,1(])()[()(2122L==−+−=jiyvxuwiCjijijjjβ观上表，终点1和4由源2供货比由源1供货更好同样终点8和10由源1供货比由源2供货更好。店号(终点)1*60.11846.758232.22157.556343.18252.2144*50.15223.073527.99642.998661.30433.503730.1824.3708*7.96730.261968.11442.30110*29.68350.028jC)2(jC)1(jiC)(的计算结果列表如下：将10个零售店重新分为2组：此时解对应的两个单源选址问题得到：}10,8,5,3,2{1=A}9,7,6,4,1{2=A07.140),()640.18,868.52(),()474.82,447.56(),(2211===vuCvuvu再重复上述过程即可得到的具体计算结果如下表：jiC)(从上表中可看出：21)1()2()2()1(AjCCAjCCjjjj∈∈店号(终点)218.67481.411336.53169.609535.79763.377818.42054.1421018.08772.511162.93947.895462.5757.261672.7609.104746.62222.519977.14924.446jC)1(jC)2(这样，计算终止，此时得到近似昀优解事实上它也是真正的昀优解07.140),()640.18,868.52(),()474.82,447.56(),(2211===vuCvuvu注：此时建二个工厂（仓库）的供货费用为140.07。前面对单源选址问题（m=1)，其供货费用为215.79。到底是建一个工厂，还是建二个甚至是3个……，这主要看，不能仅考虑供货的费用。)(1mg算法二：随机终点法Step1：根据1，2，…，n各个整数的均匀分布产生m个随机整数2：将标号为这m个整数的终点看作源，而把其余n-m个终点分配给费用昀小的源。3：重复上述步骤1和2，直到满足某一终止准则。每次重复都应保留总费用昀小的解。终止准则：①可以事先确定一个数，重复次数不超过该数.1、m个源（仓库）向n个终点（零售店或地区）供货2、有一个或者L个生产性设施向这m个源（仓库）供货，生产性设施和n个终点的位置已知希望确定n个源的位置满足：1、从m个源到各终点的总运费昀小2、从L个生产性设施到m个源的运费昀小3、源的位置是离散的或有限制的5.推广与讨论三.混合整数规划模型‰工厂选址问题ƒ问题提出jsif有n个城市，单位时间的需要物资量：现要在其中选m个城市生产这中物资的工厂，：No.j城市所在工厂昀多所能生产的数量：No.i工厂的建厂投资：No.i工厂到No.j工厂的单位物资的运价问如何建厂，既能满足要求也能使成本昀低？nβƒ建立模型No.i工厂到No.j工厂的运输量:ijx⎩⎨⎧=个城市建厂不在第个城市建厂在第iiyi01)n,,,j,i(},{y,xmy)n,,,j(wx)n,,,i(ysx.t.s)yfxmin(iijniijniijiinjijniiininjijijLLL211002121111111=∈≥⎪⎪⎪⎩⎪⎪⎪⎨⎧==≥=≤+∑∑∑∑∑∑======混合整数规划β数学模型如下：