《数据、模型与决策》课件-Ch7 网络最优化模型

网络最优化模型网络无处不在图(Graph)图G=（V，E）顶点集：V={v1,…,vm}；边集：E={e1,…,en}无向图边ek=(vi,vj),其中vi和vj是ek的端点有向图有向边（弧）ek=<vi,vj>,vi和vj是ek的起点和终点网络网络：给图G的每一条边e（每个顶点v）赋予一个权值w(e)(w(v))这种图称为网络或赋权图，记作G=(V,E,w)路径：一个顶点(边）序列，例：P=(A,C,B,E)路径中的每个顶点，都存在一条连接到下一个顶点的边路径的长度：路径上所有边的权值之和网络最优化问题特点：以网络的形式对问题进行描述和建模常见问题：运输问题； 转运问题指派问题； 最短路径问题网络线路布局问题……实例：产品运输如何安排产品运输？单位运价分销中心1分销中心2分销中心3分销中心4供给量工厂A10865230工厂B4563200工厂C3454350需求量180150250200

实例：网路图表示

数学建模

OptimalObjectiveValue:3220.000 VariableValueReducedCost

x110.0006.000

x12 0.0003.000

x13230.0000.000

x14 0.0002.000

x21 0.0000.000

x22 0.0000.000

x23 0.0000.000

x24200.0000.000

x31180.0000.000

x32150.0000.000

x3320.0000.000

x34

0.0002.000工厂A工厂B工厂C分销中心1分销中心2分销中心3分销中心4供给量

需求量

运输路线

180

150

200

250

230200

350

工厂

分销中心

单位运输成本

10运输量

86[230]

54563[200]3[180]4[150]5[20]4数据：有n个出发地S1,S2,…,Sn和m个目的地D1,D2,…,Dmsi

表示出发地i的供应量或生产能力dj表示目的地j的需求量cij表是从出发地i到目的地j的单位运输成本目标：制定运输方案使总运费（成本）最低成本假设：从任何一个出发地到任何一个目的地配送货物的成本与配送货物的数量呈线性比例关系运输问题决策变量：xij表示起点i到终点j的运输量目标函数：s.t.

整数解性质：只要它的供应量和需求量都是整数，任何有可行解的运输问题必然存在所有决策变量都是整数的最优解。运输问题的数学模型整数解性质

问题变形供给不足：总供给小于总需求增加虚拟起点路线容量或路线最小运量增加限制条件不可接受的路线删除对应的弧线和决策变量×××实例：转运问题

OptimalObjectiveValue:2900

VariableValueReducedCost

x112300

x1202

x212000

x2201

x3101

x323500

y111800

y121500

y1301

y141000

y2100

y2200

y232500

y241000工厂A工厂B工厂C分销中心1分销中心2分销中心3分销中心4供给量

需求量

运输路线

180

150

200

250

230200

350

工厂

分销中心

转运节点

中转站1中转站2单位运输成本2[230]42[200]321[350]3[180]2[150]23[100]321[250]3[100]运输量

转运问题运输问题的扩展在起点和终点之间增加转运节点目标：制定运输方案使总运费（成本）最低可选的运输路线：从起始节点直接到终点从起始点经由转运节点再到终点从一个起始节点到另外一个起始节点从一个终点到另外一个终点起点和终点都可作为运输路线中的转运节点流量守恒：转运节点的净流量为零，即输入量等于输出量。起始节点i转运节点终点j流量守恒：转运节点的净流量为零，即输入量等于输出量。转运问题的数学模型实例：人员指派问题3项任务由3名业务人员分别负责每位业务员至多负责一个任务任务人员任务1任务2任务3人员141715人员212616人员3111618

数学模型问题描述：n个代理完成m项任务每个代理至多负责一项任务每项任务至少由一个代理负责代理i完成任务j的时间为cij目标：制定工作安排方案使总时间最少指派问题决策变量：xij表示是否由代理i负责任务j目标函数：s.t.

指派问题的数学模型问题变形总的代理数小于总的任务数目标函数最大化：利润或收入不可接受的任务一个代理可以负责多项任务?最短路径问题目标：确定网络内两个节点间的最短路径例：某公司的总部在节点1处，并在其它四个节点都设有办事处。公司会定期派送业务员从总部（节点1）到节点5的办事处进行视察，需制定合理的交通方案以使得所走路径距离最短。基于线性规划的求解基本思想：将最短路径问题转化为转运问题将除起点和终点外的其它节点都设为中转节点最短路径问题目标：确定网络内节点间的最短路径例：某公司的总部在节点1处，并在其它四个节点都设有办事处。公司会定期派送业务员从总部到各办事处进行视察，需制定合理的交通方案以使得所走路径距离最短。Dijkstra算法：基本思想将顶点集合V分为两组S：已求出最短路径的顶点的集合（初始只包含起点）T=V-S：尚未确定最短路径的顶点的集合每个顶点对应一个距离值S中顶点：从v1到此顶点的最短路径长度T中顶点：从v1经过S中顶点到此顶点的最短路径长度将T中顶点按最短路径长度递增的次序加入到S中保证：从源点v1到S中各顶点的最短路径长度都不大于从v1到T中各顶点的最短路径长度根据相邻关系采用局部扩散的方式寻找最短路径并更新最短距离初始化：S={v1},T=V-S，d(v1)=0对T中每个顶点vi如果<v1,vi>∈E,则d(vi)=w(<v1,vi>)，p(vi)=1否则，d(vi)=+∞，p(vi)=-1迭代：从T中选取距离值d最小的顶点u加入S并将其从T中删除更新距离：对T中每个顶点vi如果<vj,vi>∈E且vj∈S且d(vi)>w(<vj,vi>)+d(vj)，则d(vi)=w(<vj,vi>)+d(vj)

，p(vi)=j回溯：查找从起点v1到任意顶点vi的最短路径从顶点vi开始通过函数值p(vi)

逐个找出最短路径上的先前节点Dijkstra算法：步骤根据相邻关系采用局部扩散的方式寻找最短路径并更新最短距离回溯：5←3←4←2←15←3{1,1,4,2,3}3←4{1,1,4,2,3}4←2{1,1,4,2,3}2←1{1,1,4,2,3}Dijkstra算法：步骤已找到路径集合S剩余节点集合T到起始节点距离D前置节点P初始化12,3,4,50,5,

∞,10,∞1,1,-1,1,-1迭代更新1,

2

3,4,50,5,

14,7,∞1,1,2,2,-11,2,4

3,50,5,

8,7,111,1,4,2,41,2,3,4

50,5,

8,7,101,1,4,2,31,2,3,4,5

0,5,

8,7,101,1,4,2,3根据相邻关系采用局部扩散的方式寻找最短路径并更新最短距离最优网络布局问题我国西部的某地区共有6个乡镇（标记为1-6）