P-中值模型

FP&D选址模型VI.P—中值模型P—中值模型是指在一个给定数量和位置的需求集合和一个给数量和候选位置的设施集合的前提下，分别为P个设施找到合适的位置并指派每个需求点到一个特定的设施，使之达到在设施与需求点之间的运输费用最低。如下图所示。P—中值模型FP&D选址模型P—中值数学模型为：P—中值模型N－区域中的需求点（客户）集合，N={1,2,…,n}；M－区域中可建设设施的候选点集合，M={1,2,…,m}；di－第i个需求点的需求量；cij－从需求点i到设施点j的单位运输费用；p－允许建设的设施的数目，pm；xj为0-1变量，xj=1,在j点建立设施；xj=0,不在j点建立设施，j∈Myij为0-1变量，yij=1,表示需求点i由节点j提供服务；yij=0,表示需求点i不由节点j提供服务；。MjNiyMjxMjNixypxNiyycdijjjijMjjMjijNiMjijiji,},1,0{},1,0{,,,1minFP&D选址模型例3：某饲料公司的仓库选址问题某饲料公司在某新地区经过一段时间的宣传广告后，得到了8个超市的定单，由于该新地区离总部较远，该公司拟在该地区新建2个仓库，用最低的运输成本来满足该地区的需求。经过一段时间的实地调查之后，已有4个候选地址，如下图所示；各候选地址到不同超市的运输成本、各个超市的需求量如下表所示。P—中值模型123456781234ijdi1234cij1412206100221025105033416141204659280518127320061424970720302116082412622100FP&D选址模型P—中值贪婪取走启发式算法（GreedyDroppingHeuristicAlgorithm）:P—中值模型贪婪取走启发式算法第一步，初始化，令循环数k=m，将所有m个候选位置都选中，然后将每个需求点分配给离其最近的一个侯选位置。123456781234400100360600160140120600设施点费用1860214037204760总费用2480FP&D选址模型P—中值模型贪婪取走启发式算法第二步，选择并取走一个位置点，满足以下条件：假如将它取走并将它的客户重新指派后，总费用增加量最小，然后令k=k-1。12345678234600160140120600需求点移走位置1后总费用增加量1+2002+4003+120总费用增加量+720600500480FP&D选址模型P—中值模型贪婪取走启发式算法12345678134400100360600160280120600需求点移走位置2后总费用增加量6+140总费用增加量+140移走位置2：FP&D选址模型P—中值模型贪婪取走启发式算法需求点移走位置2后总费用增加量7+5408+600总费用增加量+1140移走位置3：123456781244001003606001601406601200FP&D选址模型P—中值模型贪婪取走启发式算法需求点移走位置2后总费用增加量4+2405+800总费用增加量+1040移走位置4：123456781234001003601400400140120600因此，移走位置2，总费用为2620，令k=k-1=3.FP&D选址模型P—中值模型贪婪取走启发式算法12345678346005001680600160280120600第三步，重复步骤二。移走位置1：需求点移走位置1后总费用增加量1+2002+4003+1320总费用增加量+1920FP&D选址模型P—中值模型贪婪取走启发式算法12345678144001003606001606302200660移走位置3：需求点移走位置1后总费用增加量6+3507+5408+1600总费用增加量+2490FP&D选址模型P—中值模型贪婪取走启发式算法移走位置4：需求点移走位置1后总费用增加量4+3205+800总费用增加量+112012345678134001003601400480280120600因此，移走位置4，总费用为3740，令k=k-1=2.此时k=p，计算结束。FP&D选址模型P—中值模型贪婪取走启发式算法Lingo软件求解：model:data:M=4;N=8;p=?;enddatasets:warehouse/1..M/:x;supermarket/1..N/:d;cost(supermarket,warehouse):c,y;endsetsmin=@sum(cost(i,j):c(i,j)*y(i,j)*d(i));@for(supermarket(i):@sum(warehouse(j):y(i,j))=1);p=@sum(warehouse(k):x);@for(cost(i,j):y(i,j)=x(j));@for(cost(i,j):@bin(y(i,j)));@for(warehouse(i):@bin(x(i)));data:d=10050120802007060100;c=412206210251034161465921812731424920302112412622;enddataend