新書推薦：
《
郭建龙亚洲三部曲：印度、穿越蒙古国、三千佛塔
》
售價：NT$
1305.0
《
工作：从平凡到非凡（原书第5版） ［英］理查德·泰普勒 陶尚芸 译
》
售價：NT$
330.0
《
带献帝去旅行--历史书写的中古风景（论衡系列）
》
售價：NT$
325.0
《
出行创新设计：概念、范式与案例
》
售價：NT$
559.0
《
爱的能力：为什么我们既渴望爱，又害怕走进爱（第13版）
》
售價：NT$
391.0
《
环艺设计手绘：景观/室内 马克笔 手绘效果图技法精解
》
售價：NT$
447.0
《
明清与李朝时代
》
售價：NT$
381.0
《
感动，如此创造
》
售價：NT$
335.0
|
| 編輯推薦： |
|
《网络流优化高效智能算法及其应用》可作为数学专业?计算机科学与技术专业、管理科学与工程专业等理工类和经管类高年级本科生与研究生学习网络流优化理论及其应用的教材或参考书,也可作为有关研究人员的参考书?
|
| 內容簡介： |
|
《网络流优化高效智能算法及其应用》从便于计算机求解角度深入探讨网络流优化的理论应用前沿问题,与实际紧密结合,具有实用价值?《网络流优化高效智能算法及其应用》首先介绍网络流优化的8个主要问题及其高效智能算法,接着介绍网络流优化高效智能算法在解决16个相关优化问题中的应用创新,最后介绍2个实际应用案例?《网络流优化高效智能算法及其应用》所有算法都已在计算机上编程实现?两个附录分别列出实现最小费用最大流算法MCMF-NA的C++核心源代码C++类和实现多级供应链优化基于生成树改进遗传算法rst-GA的C语言关键源代码?
|
| 目錄：
|
前言i
第1章网络最短路问题1
1.1图的基本概念1
1.2最短路问题3
1.3结论5
第2章网络最大容量路问题6
2.1基本概念与理论6
2.2数值算法8
2.3应用举例9
2.4结论10
第3章网络最大流问题11
3.1概念和依据11
3.2数值算法13
3.3应用举例14
3.4结论15
第4章网络最小费用最大流问题16
4.1概念与依据16
4.2数值算法24
4.3应用举例27
4.4结论30
第5章有上下界网络最大流与最小流问题31
5.1概念和依据31
5.2数值算法36
5.3应用举例38
5.4结论43
第6章有上下界网络最小费用流与最小费用最大流问题44
6.1理论与算法44
6.2应用举例49
6.3结论51
第7章网络最大利润流问题52
7.1概念和依据52
7.2数值算法56
7.3应用举例57
7.4结论58
第8章网络最小饱和流问题60
8.1遗传算法60
8.2数值实验64
8.3结论72
第9章管理安排问题73
9.1概念和依据73
9.2启发式数值算法76
9.3案例77
9.4结论80
第10章车间最优逐月生产计划问题82
10.1问题描述及其数学模型82
10.2数学模型的求解83
10.3数值算法84
10.4算例86
10.5结论86
第11章多阶段存储问题87
11.1问题描述及其数学模型87
11.2数学模型的求解88
11.3数值算法89
11.4应用举例91
11.5结论91
第12章最短工期项目计划问题92
12.1基于运输网络最大流最小截启发式数值算法92
12.2基于有上下界网络最大流最小截数值算法102
第13章有重要应用价值的一类线性规划问题115
13.1理论与算法115
13.2应用举例119
13.3结论120
第14章运输问题122
14.1问题描述及其数学模型122
14.2数学模型的求解124
14.3数值算法125
14.4应用举例126
14.5结论127
第15章指派问题128
15.1问题描述及其数学模型128
15.2数学模型的分析与求解129
15.3数值算法130
15.4 应用举例131
15.5结论132
第16章缺省指派问题133
16.1问题描述及其数学模型133
16.2数学模型的分析求解134
16.3数值算法136
16.4应用举例140
16.5结论142
第17章运输问题的多反而少悖论143
17.1模型与算法143
17.2应用举例145
17.3结论147
第18章有容量限制与边界条件约束运输问题148
18.1模型与算法148
18.2应用举例150
18.3结论151
第19章供给总量限定需求区间约束运输问题152
19.1问题描述及其数学模型152
19.2数学模型的求解153
19.3数值算法157
19.4应用举例161
19.5结论163
第20章运输时限费用优化问题164
20.1问题描述及其数学模型164
20.2数学模型的求解165
20.3应用举例169
20.4结论170
第21章固定费用运输问题171
21.1模型与算法171
21.2应用举例175
21.3结论176
第22章固定费用运输问题的多反而少悖论177
22.1模型与算法177
22.2应用举例182
22.3结论183
第23章非线性固定费用运输问题184
23.1问题描述及其数学模型184
23.2遗传算法185
23.3数值实验190
23.4结论195
第24章多级供应链优化问题196
24.1问题描述及其数学模型196
24.2基于生成树改进遗传算法198
24.3基于生成树改进遗传算法的C语言实现方法206
24.4数值例子207
24.5结论210
第25章应用案例211
25.1“协会+农户”生猪产业供应链网络饲料运送和生猪农产品销售运输最优方案计算及应用211
25.2银河杜仲沼液种植三层目标轮换六级储存网络系统设计218
参考文献230
附录A实现最小费用最大流数值算法MCMF-NA的C++核心源代码C++类238
附录B实现多级供应链优化基于生成树改进遗传算法rst-GA的C语言关键源代码254
|
| 內容試閱：
|
第1章网络最短路问题
1.1图的基本概念
生活中的示意图（由点、线组成）用来反映对象间的关系，点表示对象，线表示关系。这样的例子有很多，比如，铁路交通图、电话线分布图、煤气管道图、航空线图、比赛情况图。在示意图中，点的位置，线的长短曲直，对反映对象间的关系不重要。从本质上讲，示意图与工程图、几何图不同。关系有对称与非对称之分；对称关系用无向线（不带箭头的线）表示，非对称关系用有向线（带箭头的线）表示。
图是由点（顶点）、线组成，不带箭头的线（无向线）又称为边，带箭头的线（有向线）又称为弧。
无向图：由点（顶点）、边组成，记为G=V，E，V是G的点（顶点）集，E是G的边集。联结点（顶点）vi，vj∈V的边，记为[vi，vj]或[Vi，vj]。
有向图：由点（顶点）node，vertex、弧arc组成，记为D=V，A，V是D的点（顶点）集，A是D的弧集。一条方向从vi指向vj的弧记为vi，vj。
常用记号notation：pG表示G的点（顶点）数，pD表示D的点（顶点）数，viG表示G的边数，viD表示D的弧数。
专门名字nomenclature：考虑无向图G=V；E。若边e=[u，v]∈E，则称“u，是P的端点，也称u，v是相邻的。称e是点“（与点v）的关联边。若图G中，某个边P的两个端点相同，则称P是环loop。若两个点（顶点）之间有多于一条的边，称这些边为多重边。无环、无多重边的图称为简单图，无环、有多重边的图称为多重图。以点（顶点）v为端点的边的个数称为v的次（度）degree，环在计算次（度）时算作两次。称次（度）为1的点为悬挂点，悬挂点的关联边称为悬挂边，次（度）为零的点称为孤立点。
定理1.1.1图G=V，E中，所有点（顶点）的次（度）之和是边数的两倍，即次（度）为奇数的点，称为奇点，否则称为偶点。
定理1.1.2任一个图中，奇点的个数为偶数。
图G中，若任何两个顶点之间，至少有一条链，则称G是连通图，否则称为不连通图。若G是不连通图，它的每一个连通的部分称为G的一个连通分图（分图、分支）。
给定一个图G=V，E，如果图G’=V''，E''，使矿=V''及E''cE，则称G7是G的一个支撑子图。
设V∈VG，用G-V表示从图G中去掉点（顶点）V及v的关联边后得到的一个图。
现讨论有向图。给定一个有向图D=V，A，从D中去掉所有弧上的箭头，就得到一个无向图，称乏为D的基础图，记为GD。
给D中一条弧a=a，V，称“为a的始点，V为a的终点，称弧a是从“指向v的。
设是D中的一个点（顶点）弧交错序列，如果这个序列在基础图GD中所对应的点边序列是一条链，则称这个点弧交错序列是D的一条链。类似定义闭链和初等链（闭链）。
如果（是D中的一条链，并且对t=l，2，，k-l，均有，称之为从Vi．到VI1的一条途径。若途径的第一个点和最后一个点相同，称之为闭途径。类似定义初等途径（闭途径）。初等途径又称之为路，初等闭途径又称之回路。
对无向图，链与途径（圈与回路）这两个概念一致。类似无向图，可定义简单有向图，多重有向图。
权是指与顶点或边（弧）有关的数量指标；根据实际问题需要，可赋予权不同含义，如距离、时间、费用等；可赋一个权，也可赋多个权；权可a是非负数，也可a是负数；赋权越多的图，反映的问题越贴近实际，考虑起来也越复杂。
赋权图（网络）不仅指出各点（顶点）间的邻接关系，同时也表示各点之间的数量关系。赋权图被广泛用于解决工程技术与科学生严管理等领域的最优化问题。
本书中有关图的在此节未提到的其他一些基本概念参见GraphTheorywithApplications[1l]在本书中，我们不加区分地采用或表示正无穷大。
1.2最短路问题
1.2.1概念与定义
给定简单赋权连通有向图（网络）N=（s，t，v；A；W），其中V={1，2，，n}是N的顶点集，A=是N的弧集，W=是N的权关联矩阵，a%表示弧=t，j的权从顶点t到顶点j的弧以T=t，j的长（费用等））。当时，规定当t≠j时，如果弧不存在，规定给定两顶点s（始a点）、t（终点）。设P是从顶点s到顶点t的一条，定义路P的权是JP上所有弧的a权之和，记为wP。最短路问题就是在所有从顶点s到顶点t路中，求一条权最小a的路，即求一条从顶点s到顶点t的路Po，使，式中对N中所有a从顶点s到顶点t的路JP取最小，称Po是从顶点s到顶点t的最短路。路Po的权称a为从顶点s到顶点t的距离，记为ds，t。
最短路问题，是重要的最优化问题之一，可直接用于解决生产实际中的许多a问题（如管道铺设、线路安排、厂区布局、设备更新等），常被作为解决其他问题a的基本工具[2]。
1.2.2常用数值算法
以下算法Dijkstra-NA是基于Dijkstra算法给出的求网络N=（s，t，v；W）中从a始点s到所有其他顶点最短路的数值算法。
对任意顶点t∈v{s}，令。其中S表示永久标号顶点的集合，Pi表示给顶a点t赋予的永久标号（代表从始点s到顶点t的最短距离），Ti表示给顶点t赋予a的临时标号，previ表示在从始点s到顶点t的最短路中顶点t的紧前顶点（即前a点），尼表示此时进入永久标号顶点集合的顶点。
Step2如果S=V，则对任意顶点i∈S而言，从始点s到顶点t的最短距离ads，t=Pt，转Step5;否则，转Step3。
Step3对任意顶点，如果满足且Tj，则
Step4令，如果，否则，对任意顶点i∈S而言从始点s到顶点t的最短距离ds，i=Pi，而对任意顶点i∈V\S而言从始点s到顶点i的最短距离ds，i=Ti，转Step5?
Step5如果i?S，则不存在从顶点s到顶点t的最短路，停止?否则令转
Step6?在此，Paths，i表示由弧构成的从顶点s到顶点i的最短路，g代表空集?
Step6令P
Step7如果=s，则Paths，t是从顶点s到顶点t的最短路，停止;否则，令，转Step6.
Dijkstra-NA算法只适用于权都为非负数的情形，而对有些权为负数的情形不适用?Dijkstra-NA算法是多项式时间算法，在最坏情况下它的时间复杂性为On2?
以下算法I1oyd-NA是基于I1oyd算法给出的求网络Ⅳ=s，i，V;A;W中任意两顶点间最短路的数值算法?
Step1令，其中，UIj表示从顶点i到顶点的最短距离，S?表示在从顶点i到顶点的最短路中顶点i的紧后项点即后点?
Step2对任意，如果，则令;否则，保持不变?
Step3如果k=n，则转Step4;否则，令
Step4如果，则不存在从顶点s到顶点i的最短路，停止?否则，令，转Step5?在此，Paths，i表示由弧构成的从顶点s到顶点i的最短路，⑦代表空集?
Step5令Paths，t:=Paths，tU{l，，r}.
Step6如果r=t，则Paths，i是从顶点s到顶点i的最短路，停止;否则，令，转Step5?
F1oyd-NA算法仅适用于网络Ⅳ=s，i，V;A;W中不存在负费用回路的情形?而负费用回路是指回路上所有弧的权之和为负数的回路?显然，它不仅适用于权都为非负数的情形，对虽然有些权为负数但不存在负费用回路的情形也适用?算法也是多项式时间算法，在最坏情况下它的时间复杂性为On3?
1.2.3应用举例
我们考虑以下设备更新问题?
某企业使用一台设备，在每年年初，企业领导部门就要决定是购置新的，还继续使用旧的。若购置新设备，就要支付一定的购置费用；若继续使用旧设备，则需支付一定的维修费用。己知该设备在各年年初的价格为：第f年年初购进一台设备的价格为Pi，i=1，2，，n；显然，B≥0（i=1，2，，n），如表1-1所示。
己知使用不同时间（年）的设备所需的维修费用为：一台设备在被使用的第i-1年至第f年期间的维修费用为ci=1，2，，n；显然，ci≥0（i=1，2，，n），如表1-2所示。如何制订一个n年之内的设备更新计划，使总支付费最小。
表1-2设备维修费用我们可以按以下方法将上述设备更新问题转化为网络最短路问题来求解。
构造网络N=（s，t，A；W）；始点s=1，终点t=n+l，V={1，2，，f，，n+1}是顶点集，顶点i表示第i年年初购进一台新设备（i∈{1，2，，n}），顶点n+l表示第n年年底；A=是弧集，弧I，j表示在第f年年初购进的设备一直使用到第i年年初（即第j-l年底）；是权关联矩阵；当时，规定，当f≠j时，如果弧i，j不存在，规定，否则，于是，求（制订）最优设备更新计划等价于在网络中求从顶点s到顶点t的最短路，可用Dijkstra-NA算法或Floyd-NA算法来求解。
1.3结论
本章给出的两个求网络最短路的数值算法都是多项式时间算法，可作为有效工具用于解决其他复杂的相关优化问题（比如，用于解决第4章论述的网络最小费用最大流问题），因此具有重要的理论与应用价值。
第2章网络最大容量路问题
网络最大容量路问题在《网络最优化》[3]一书中已经提出，笔者通过改进建立[4，51了在运输网络中求最大容量路的两个高效数值算法f它们是强多项式时间算法，且易于在计算机上编程实现1。因为这两个算法在高效寻求网络最大流中发挥十分重要的作用[6，7]，因此本章主要介绍我们取得的这一研究结果。
2.1基本概念与理论
定义2.1.1把简单赋权连通有向图N=（V，s，f；A；C）称为运输网络，其中V={1，2，，n}为N中顶点的集合，顶点s是N的源（发点），顶点f是N的沟（收点），为N中弧的集合，为N的容量矩阵（C表示从顶点f到顶点／的直接运输通过能力）。当时，规定Cj=。当f≠i时，如果不存在弧以，规定Ci=0;否则规定，其中Caij表示弧aij的容量。
定理2.1.1给定运输网络N=（V，s，f；A；C），在引理2.1.2的假设条件下，记如，则有以下两个结论成立：①，取达到上述最大值的顶点为ji，则P1=Ps，j1其中，Ps，j1表示以s为始点j1为终点的路，由于
|
|
購物車/收銀台(
0
) | 在線留言板
| 付款方式
| 聯絡我們
| 運費計算
| 幫助中心 |
加入書簽
HOME
新書上架
