P-中值模型课件

选址模型,P中值模型P中值模型是指在一个给定数量和位置的需求集合和一个给数量和候选位置的设施集合的前提下，分别为P个设施找到合适的位置并指派每个需求点到一个特定的设施，使之达到在设施与需求点之间的运输费用最低。如下图所示。,P中值模型,1,PPT学习交流,选址模型,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点建立设施，jMyij为0-1变量，yij=1,表示需求点i由节点j提供服务；yij=0,表示需求点i不由节点j提供服务；。,2,PPT学习交流,选址模型,例3：某饲料公司的仓库选址问题某饲料公司在某新地区经过一段时间的宣传广告后，得到了8个超市的定单，由于该新地区离总部较远，该公司拟在该地区新建2个仓库，用最低的运输成本来满足该地区的需求。经过一段时间的实地调查之后，已有4个候选地址，如下图所示；各候选地址到不同超市的运输成本、各个超市的需求量如下表所示。,P中值模型,3,PPT学习交流,选址模型,P中值贪婪取走启发式算法（GreedyDroppingHeuristicAlgorithm）:,P中值模型贪婪取走启发式算法,第一步，初始化，令循环数k=m，将所有m个候选位置都选中，然后将每个需求点分配给离其最近的一个侯选位置。,4,PPT学习交流,选址模型,P中值模型贪婪取走启发式算法,第二步，选择并取走一个位置点，满足以下条件：假如将它取走并将它的客户重新指派后，总费用增加量最小，然后令k=k-1。,1,2,3,4,5,6,7,8,2,3,4,600,160,140,120,600,600,500,480,5,PPT学习交流,选址模型,P中值模型贪婪取走启发式算法,1,2,3,4,5,6,7,8,1,3,4,400,100,360,600,160,280,120,600,移走位置2：,6,PPT学习交流,选址模型,P中值模型贪婪取走启发式算法,移走位置3：,1,2,3,4,5,6,7,8,1,2,4,400,100,360,600,160,140,660,1200,7,PPT学习交流,选址模型,P中值模型贪婪取走启发式算法,移走位置4：,1,2,3,4,5,6,7,8,1,2,3,400,100,360,1400,400,140,120,600,因此，移走位置2，总费用为2620，令k=k-1=3.,8,PPT学习交流,选址模型,P中值模型贪婪取走启发式算法,1,2,3,4,5,6,7,8,3,4,600,500,1680,600,160,280,120,600,第三步，重复步骤二。移走位置1：,9,PPT学习交流,选址模型,P中值模型贪婪取走启发式算法,1,2,3,4,5,6,7,8,1,4,400,100,360,600,160,630,2200,660,移走位置3：,10,PPT学习交流,选址模型,P中值模型贪婪取走启发式算法,移走位置4：,1,2,3,4,5,6,7,8,1,3,400,100,360,1400,480,280,120,600,因此，移走位置4，总费用为3740，令k=k-1=2.此时k=p，计算结束。,11,PPT学习交流,选址模型,P中值模型贪婪