P中值模型.ppt

《P中值模型.ppt》由会员分享，可在线阅读，更多相关《P中值模型.ppt（12页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、FP&D选址模型选址模型VI.P中值模型中值模型P中值模型是指在一个给定数量和位置的需求集合和一个给数量和候选位置的中值模型是指在一个给定数量和位置的需求集合和一个给数量和候选位置的设施集合的前提下，分别为设施集合的前提下，分别为P个设施找到合适的位置并指派每个需求点到一个特定的个设施找到合适的位置并指派每个需求点到一个特定的设施，使之达到在设施与需求点之间的运输费用最低。设施，使之达到在设施与需求点之间的运输费用最低。如下图所示。如下图所示。P中值模型中值模型FP&D选址模型选址模型P中值数学模型为：中值数学模型为：P中值模型中值模型N区域中的需求点（客户）集合，N=1,2,n；M区域中可建

2、设设施的候选点集合，M=1,2,m；di第i个需求点的需求量；cij从需求点i到设施点j的单位运输费用；p 允许建设的设施的数目，pm；xj为0-1变量，xj=1,在j点建立设施；xj=0,不在j点建立设施，jMyij为0-1变量，yij=1,表示需求点i由节点j提供服务；yij=0,表示需求点i不由节点j提供服务；。FP&D选址模型选址模型例例3：某饲料公司的仓库选址问题：某饲料公司的仓库选址问题某饲料公司在某新地区经过一段时间的宣传广告后，得到了某饲料公司在某新地区经过一段时间的宣传广告后，得到了8个超市的个超市的定单，由于该新地区离总部较远，该公司拟在该地区新建定单，由于该新地区离总部较

3、远，该公司拟在该地区新建2个仓库，用最低个仓库，用最低的运输成本来满足该地区的需求。经过一段时间的实地调查之后，已有的运输成本来满足该地区的需求。经过一段时间的实地调查之后，已有4个个候选地址，如下图所示；各候选地址到不同超市的运输成本、各个超市的需候选地址，如下图所示；各候选地址到不同超市的运输成本、各个超市的需求量如下表所示。求量如下表所示。P中值模型中值模型123456781234ijdi1234cij141220610022 210251050334161412046592 28051812732006142 24970720302 2116082412622100FP&D选址模型选址

4、模型P中值中值贪婪取走启发式算法贪婪取走启发式算法（Greedy Dropping Heuristic Algorithm）:P中值模型贪婪取走启发式算法中值模型贪婪取走启发式算法第一步，初始化，令循环数第一步，初始化，令循环数k=mk=m，将所有，将所有m m个候选位置都选中，然后将个候选位置都选中，然后将每个需求点分配给离其最近的一个侯选位置。每个需求点分配给离其最近的一个侯选位置。123456781234400100360600160140120600设施点设施点费用费用1860214037204760总费用总费用2480FP&D选址模型选址模型 P中值模型贪婪取走启发式算法中值模型贪婪

5、取走启发式算法第二步，选择并取走一个位置点，满足以下条件：假如将它取走并将第二步，选择并取走一个位置点，满足以下条件：假如将它取走并将它的客户重新指派后，总费用增加量最小，然后令它的客户重新指派后，总费用增加量最小，然后令k=k-1k=k-1。12345678234600160140120600需求点需求点移走位置移走位置1后总后总费用增加量费用增加量1+2002+4003+120总费用总费用增加量增加量+720600500480FP&D选址模型选址模型 P中值模型贪婪取走启发式算法中值模型贪婪取走启发式算法12345678134400100360600160280120600需求点需求点移走

6、位置移走位置2后总后总费用增加量费用增加量6+140总费用总费用增加量增加量+140移走位置移走位置2 2：FP&D选址模型选址模型 P中值模型贪婪取走启发式算法中值模型贪婪取走启发式算法需求点需求点移走位置移走位置2后总后总费用增加量费用增加量7+5408+600总费用总费用增加量增加量+1140移走位置移走位置3 3：123456781244001003606001601406601200FP&D选址模型选址模型 P中值模型贪婪取走启发式算法中值模型贪婪取走启发式算法需求点需求点移走位置移走位置2后总后总费用增加量费用增加量4+2405+800总费用总费用增加量增加量+1040移走位置移走

7、位置4 4：123456781234001003601400400140120600因此，移走位置因此，移走位置2 2，总费用为，总费用为26202620，令，令k=k-1=3.k=k-1=3.FP&D选址模型选址模型 P中值模型贪婪取走启发式算法中值模型贪婪取走启发式算法12345678346005001680600160280120600第三步，重复步骤二。第三步，重复步骤二。移走位置移走位置1 1：需求点需求点移走位置移走位置1后总后总费用增加量费用增加量1+2002+4003+1320总费用总费用增加量增加量+1920FP&D选址模型选址模型 P中值模型贪婪取走启发式算法中值模型贪婪取

8、走启发式算法12345678144001003606001606302200660移走位置移走位置3 3：需求点需求点移走位置移走位置1后总后总费用增加量费用增加量6+3507+5408+1600总费用总费用增加量增加量+2490FP&D选址模型选址模型 P中值模型贪婪取走启发式算法中值模型贪婪取走启发式算法移走位置移走位置4 4：需求点需求点移走位置移走位置1后总后总费用增加量费用增加量4+3205+800总费用总费用增加量增加量+112012345678134001003601400480280120600因此，移走位置因此，移走位置4 4，总费用为，总费用为37403740，令，令k=k

9、-1=2.k=k-1=2.此时此时k=pk=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=100 50 120 80 200 70 60 100;c=4 12 20 6 2 10 25 10 3 4 16 14 6 5 9 2 18 12 7 3 14 2 4 9 20 30 2 11 24 12 6 22;enddataend