MBA数据模型与决策-09图与网络规划

第九章图与网络规划本章内容大纲9.1图论的基本概述9.2网络最大流问题9.3最小费用流问题9.4最短路问题9.5最小支撑树问题9.6网络设施选址问题9.7车辆路径问题9.8选址路线问题9.1图的基本概念

经典案例：哥尼斯堡七桥问题是否存在一条路线，可不重复地走遍七座桥，回到原点？9.1图的基本概念

一个图就是点与边的集合，记作

点与边的关联

有向图与无向图度、奇顶点、偶顶点链、闭链、开链欧拉图

一个非空连通图图G是E图的充分必要条件是图G只含有偶顶点

赋权图与网络

9.1图的基本概念

中国邮递员问题(CPP)

：一个邮递员负责某些街道的邮件投递工作，每次都要从邮局出发走遍他负责的所有街道，再回到邮局。那么他应如何安排投递路线，使得所走过的总路程最短?9.1图的基本概念CPP模型及LINGO主程序min=@sum(ij(i，j)|c(i，j)#gt#0：c(i，j)*f(i，j))；@for(ii(j)：@sum(ii(i)：f(i，j))=@sum(ii(k)：f(j，k)))；@for(ij(i，j)|c(i，j)#gt#0：@gin(f))；@for(ij(i，j)|c(i，j)#gt#0：f(i，j)+f(j，i)>=1)；@for(ij(i，j)|c(i，j)#eq#0：f(i，j)=0)；end9.2网络最大流问题案例：某企业的产品需要经过多道加工工序，有多个设备可以完成这些工序的工作，而企业现有设备加工每道工序的能力也不同，即每道工序在一个工作日内加工产品的最大数量是有限制的，图中，边上的数字即为该工序的最大加工能力。9.2网络最大流问题概念：给定有向赋权图其中有两个特殊的节点s和t。s称为发点，t称为收点。而剩下的结点称之为转运点。图中各边的方向和权数表示允许的流向和最大可能的流量（容量），并假设容量均为整数。问在这个网络图中从发点流出到收点汇集，最大可通过的实际流量为多少？流向分布情况怎样？9.2网络最大流问题网络最大流问题模型及LINGO主程序max=f；@for(ii(i)|i#gt#1#and#i#lt#6：@sum(ii(j)：x(i，j))-@sum(ii(j)：x(j，i))=0)；@sum(ii(j)：x(1，j))-@sum(ii(j)：x(j，1))=f；@sum(ii(j)：x(6，j))-@sum(ii(j)：x(j，6))=-f；@for(ij(i，j)：x(i，j)<=u(i，j))；end9.2网络最大流问题__程序计算结果9.3最小费用流问题案例：某配送公司拥有一个固定的配送网络，网络中某些地方需要送货，某些地方需要发货，公司现为每条路线配备固定的运输车辆，每辆车都有固定的装载容量限制。9.3最小费用流问题_概念9.3最小费用流问题最小费用流问题模型及LINGO程序min=@sum(ij(i，j)：c(i，j)*x(i，j))；@for(ii(i)：@sum(ii(j)|c(i，j)#gt#0：x(i，j))-@sum(ii(j)：x(j，i))=b(i))；@for(ij(i，j)|u(i，j)#gt#0：x(i，j)<=u(i，j))；

9.3最小费用流问题_程序计算结果9.4最短路问题案例：某服务公司几乎时刻都往返于一个城市的不同社区，需要事先确定城市各个社区之间的最短线路。要求总旅程最短的旅行路线：实际上就是在一个赋权连通图上，求一条从起点到另一节点的路P，使得通路P上的总权和W(P)最小，这样的问题称为最短路问题。9.4最短路问题__模型9.4最短路问题__floyd算法9.4最短路问题__matlab程序D=aa；fori=1：nforj=1：n

R(i，j)=j；

endendR；fork=1：n9.5最小支撑树问题案例：企业有五个数据中心，中心之间用光缆连接，己知这五个车间的位置、可供铺设光缆的地方及数据中心之间的距离，问光缆怎样铺设才能使管线总长最省?9.5最小支撑树问题__概念设图G=(V、E)是一个赋权连通图，T是G的一棵支撑子树，称T中所有边的权之和为支撑树T的权，记为w(T)，即w(T)=，如果支撑树T*的权w(T*)是G所有支撑树的权中最小的，则称T*为G的最小支撑树(简称为最小树)9.5最小支撑树问题__破圈法求一个赋权连通图G的最小支撑树的方法还有“破圈法”，此方法简单易行。“破圈法”：在图G中任取一个圈，去掉圈上权最大的一条边，反复进行，直到没有圈为止。对例9-6依此去掉的边为：(v5、v6)，(v2、v5)，(v3、v1)，(v6、v4)。也得到图9-12所示的最小树，总权和为14。9.6网络设施选址问题P-中位问题：不考虑建站成本，而选P个服务站最小化总路线成本。P-中心问题：是探讨如何在网络中选择P个服务站，使得任意一需求点到距离该需求点最近的服务站的最大距离最小。最大覆盖问题：在服务站的数目和服务半径已知的条件下，如何设立P个服务站使得可接受服务的需求量最大。集覆盖问题：覆盖所有需求点顾客的前提下，服务站总的建站个数或建设费用最小。9.6网络设施选址问题__中位问题案例：商业公司希望从它的10个零售店中选择3个进行扩建，成立物流中心为它的10个零售店进行配送服务，已知每个零售店每天的配送量，零售店之间的距离，问：如何选择最合适的物流中心使得总配送成本最低。9.6网络设施选址问题__中位问题min=@sum(ij(i，j)：h(i)*d(i，j)*y(i，j))；@for(ii(i)：@sum(ii(j)：y(i，j))=1)；@sum(ii(j)：x(j))=3；@for(ij(i，j)：y(i，j)-x(j)<=0)；

@for(ii(i)：@bin(x(i)))；

@for(ij(i，j)：@bin(y(i，j)))；end

9.6网络设施选址问题__中位问题9.6网络设施选址问题__集覆盖问题9.6网络设施选址问题__最大覆盖问题9.6网络设施选址问题__中心问题9.7车辆路径问题案例：车辆路径问题(VehicleRoutingProblem，VRP)是指对一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。9.7车辆路径问题9.7车辆路径问题为何需要约束式(6)？为了避免一辆车子产出多个回路的现象。01234567012345679.7车辆路径问题车辆路径问题LINGO主程序min=@sum(ijk(i，j，k)：c(i，j)*x(i，j，k))；@for(kk(k)：@sum(ii(i)：g(i)*y(i，k))<=15)；@for(ii(j)|j#gt#1：@sum(kk(k)：y(j，k))=1)；@for(ii(j)|j#eq#1：@sum(kk(k)：y(j，k))=3)；@for(ik(j，k)：@sum(ii(i)|i#ne#j：x(i，j，k))=y(j，k))；@for(ik(i，k)：@sum(ii(j)|i#ne#j：x(i，j，k))=y(i，k))；@for(ij(i，j)|i#ne#j#and#i#gt#1#and#j#gt#1：u(i)-u(j)+11*@sum(kk(k)：x(i，j，k))<=10)；@for(ijk：@bin(x))；@for(ik：@bin(y))；end9.7车辆路径问题__程序计算结果9.8选址路线问题案例：某企业有6个稳定的经销商，现决定为其建立配送中心，已知该企业候选的2辆5吨及其估算的车辆成本，2个候选的建站场地及其估算的建站费用，6个客户每天的大致配送量，建站场地及客户的位置及距离，7、8为候选的建站场地；1至6为经销商位置。9.8选址路线问题__概念选址路线问题是一个结合选址问题与车辆路径问题的决策。该问题研究如何选址配送中心，并且安排最优的配送车辆与配送路线，以使总建站成本、车辆成本、行驶成本最小。9.8选址路线问题__模型9.8选址路线问题__LINGO主程序min=@sum(ijk(i，j，k)：c(i，j)*x(i，j，k))+@sum(jj：f*z)+@sum(jk(j，k)：h(k)*y(j，k))；@for(ii(j)：@sum(nk(i，k)|i#ne#j：x(i，j，k))=1)；@for(nk(j，k)：@sum(nn(i)|i#ne#j：x(i，j，k))-@sum(nn(i)|i#ne#j：x(j，i，k))=0)；@for(jk(j，k)：@sum(ii(i)：x(i，j，k))=y(j，k))；@for(iijj(i，j)|i#ne#j：u(i)-u(j)+6*@sum(kk(k)：x(i，j，k))<=5)；@for(jk(j，k)：@sum(ii(i)：x(j，i，k))=y(j，k))；@for(jk(j，k)：y(j，k)<=z(j)