请输入关键字
Delbert Ray Fulkerson
网络流理论奠基人
时间: 2026.08.21
字号:

 

Delbert Ray Fulkerson(1924—1976)出生于美国伊利诺伊州塔姆斯。Fulkerson 16岁便以年级第一的成绩高中毕业,1942年进入南伊利诺伊大学学习。1944年,他因第二次世界大战中断学业,加入美国陆军航空队服役,1946年重返校园,并于1947年获得数学学士学位。随后,他进入威斯康星大学继续深造,1948年获得数学硕士学位,1951年获得数学博士学位。博士毕业后,Fulkerson 受邀加入兰德公司数学部,并在那里工作了20年。1971年,他转入康奈尔大学,担任工程学教授以及运筹学与应用数学教授,直至1976年去世。

Fulkerson 最具代表性的贡献,是与 Lester R. Ford Jr. 共同奠定现代网络流理论的基础。这项研究最初源于一个具有明确军事背景的实际问题,即如何评估东欧铁路网络在常规战争条件下所能承担的运输能力。围绕这一问题,Ford 和 Fulkerson 于1956年提出并证明了著名的最大流—最小割定理,随后又进一步发展了最大流、最小费用流和动态网络流等一系列理论。1962年,两人合著的经典著作 Flows in Networks 出版,并长期成为网络流领域的重要教材和基础文献。

除网络流理论外,Fulkerson 对整数规划和组合优化的发展同样具有重要影响。1954年,他与 George Dantzig、Selmer Johnson 合作研究旅行商问题,尝试寻找穿越当时美国48个州首府和华盛顿特区的最短巡回路线。三人利用线性规划和单纯形法求解该问题,并针对整数解结构发展出后来被称为子回路消除约束的方法,通过按需加入约束逐步逼近整数最优解。由于这些约束仍不足以完全确定最优解,他们还采用了与后来分支定界法非常接近的求解思想。这项工作被视为割平面方法和多面体组合优化发展的重要起点。

Fulkerson 在大规模优化方法方面也留下了深远影响。1958年,他与 Ford 研究多商品网络流问题,将不同商品共享网络容量的运输问题表示为一个包含大量路径变量的线性规划模型。面对指数级增长的变量数量,他们提出无需预先生成全部变量,而是利用对偶信息和最短路计算按需加入新的路径变量,由此形成了最早的列生成思想之一。这一方法后来直接启发了 Dantzig-Wolfe 分解以及 Gilmore-Gomory 切割库存算法,并成为现代大规模线性规划、车辆路径、排程和供应链优化中极为重要的求解框架。

此外,Fulkerson 还针对天然气运输网络中的大规模计算问题提出了 out-of-kilter 算法,通过原始变量调整与对偶价格调整交替进行,提高最小费用流问题的求解效率。他与 Dantzig、Ford 等人关于原始—对偶算法的研究,也为后来网络设计和组合优化中的原始—对偶方法奠定了重要基础。与此同时,他还将网络流理论应用于 CPM/PERT 项目分析,并进一步研究极值组合学中的路径、割、链和反链问题,发展了 blocking 与 anti-blocking 多面体理论,从几何和多面体角度揭示不同组合结构之间的内在联系。

Delbert Ray Fulkerson 是现代网络优化和组合优化领域最重要的奠基者之一。他从铁路运输、旅行商和天然气网络等现实问题出发,却发展出了具有普遍意义的数学结构和优化方法。今天网络流、列生成、割平面、分支定界以及大规模组合优化中的许多基本思想,都可以追溯到他的研究。他的学术生涯也充分体现了运筹学从实际问题中提炼数学结构、再以理论创新反哺现实决策的鲜明传统。